On digital blocks of polynomial values and extractions in the Rudin–Shapiro sequence
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Special issue dedicated to the 15th "Journées Montoises d'Informatique Théorique", Tome 50 (2016) no. 1, pp. 93-99.

Let P(x)[x] be an integer-valued polynomial taking only positive values and let d be a fixed positive integer. The aim of this short note is to show, by elementary means, that for any sufficiently large integer NN 0 (P,d) there exists n such that P(n) contains exactly N occurrences of the block (q-1,q-1,...,q-1) of size d in its digital expansion in base q. The method of proof allows to give a lower estimate on the number of “0” resp. “1” symbols in polynomial extractions in the Rudin–Shapiro sequence.

Reçu le :
Accepté le :
DOI : 10.1051/ita/2016009
Classification : 11A63, 11B85
Mots-clés : Rudin–Shapiro sequence, automatic sequences, polynomials
Stoll, Thomas 1, 2

1 Université de Lorraine, Institut Elie Cartan de Lorraine, UMR 7502, 54506 Vandœuvre-lès-Nancy, France
2 CNRS, Institut Elie Cartan de Lorraine, UMR 7502, 54506 Vandœuvre-lès-Nancy, France
@article{ITA_2016__50_1_93_0,
     author = {Stoll, Thomas},
     title = {On digital blocks of polynomial values and extractions in the {Rudin{\textendash}Shapiro} sequence},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     pages = {93--99},
     publisher = {EDP-Sciences},
     volume = {50},
     number = {1},
     year = {2016},
     doi = {10.1051/ita/2016009},
     zbl = {1419.11014},
     mrnumber = {3518161},
     language = {en},
     url = {http://archive.numdam.org/articles/10.1051/ita/2016009/}
}
TY  - JOUR
AU  - Stoll, Thomas
TI  - On digital blocks of polynomial values and extractions in the Rudin–Shapiro sequence
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2016
SP  - 93
EP  - 99
VL  - 50
IS  - 1
PB  - EDP-Sciences
UR  - http://archive.numdam.org/articles/10.1051/ita/2016009/
DO  - 10.1051/ita/2016009
LA  - en
ID  - ITA_2016__50_1_93_0
ER  - 
%0 Journal Article
%A Stoll, Thomas
%T On digital blocks of polynomial values and extractions in the Rudin–Shapiro sequence
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2016
%P 93-99
%V 50
%N 1
%I EDP-Sciences
%U http://archive.numdam.org/articles/10.1051/ita/2016009/
%R 10.1051/ita/2016009
%G en
%F ITA_2016__50_1_93_0
Stoll, Thomas. On digital blocks of polynomial values and extractions in the Rudin–Shapiro sequence. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Special issue dedicated to the 15th "Journées Montoises d'Informatique Théorique", Tome 50 (2016) no. 1, pp. 93-99. doi : 10.1051/ita/2016009. http://archive.numdam.org/articles/10.1051/ita/2016009/

J.-P. Allouche and J. Shallit, Automatic Sequences: Theory, Applications, Generalizations. Cambridge University Press, Cambridge (2003). | MR | Zbl

J. Brillhart and P. Morton, A case study in mathematical research: the Golay–Rudin–Shapiro sequence. Amer. Math. Monthly 103 (1996) 854–869. | DOI | MR | Zbl

C. Dartyge and G. Tenenbaum, Congruences de sommes de chiffres de valeurs polynomiales. Bull. London Math. Soc. 38 (2006) 61–69. | DOI | MR | Zbl

M. Drmota and T. Stoll, Newman’s phenomenon for generalized Thue–Morse sequences. Discrete Math. 308 (2008) 1191–1208. | DOI | MR | Zbl

A.O. Gelfond, Sur les nombres qui ont des propriétés additives et multiplicatives données. Acta Arith. 13 (1967/1968) 259–265. | DOI | MR | Zbl

M. Lothaire, Applied Combinatorics on Words. Vol. 105 of Encycl. Math. Appl. Cambridge University Press, Cambridge (2005). | MR | Zbl

C. Mauduit and J. Rivat, Prime numbers along Rudin–Shapiro sequences. J. Eur. Math. Soc. 27 (2015) 2595–2642. | DOI | MR | Zbl

D.J. Newman, On the number of binary digits in a multiple of three. Proc. Amer. Math. Soc. 21 (1969) 719–721. | DOI | MR | Zbl

The Online Encyclopedia of Integer Sequences (OEIS), edited by N.J.A. Sloane. Available at https://oeis.org/. | Zbl

W. Rudin, Some theorems on Fourier coefficients. Proc. Amer. Math. Soc. 10 (1959) 855–859. | DOI | MR | Zbl

H.S. Shapiro, Extremal Problems for Polynomials and Power Series. Master thesis, M.I.T. (1951). | MR

T. Stoll, The sum of digits of polynomial values in arithmetic progressions. Functiones et Approximatio 47 (2012) 233–239. | MR | Zbl

Cité par Sources :