Systèmes de numération et fonctions fractales relatifs aux substitutions. (Numeration systems and fractal functions related to substitutions). (French) Zbl 0679.10010

Dumont, Jean-Marie; Thomas, Alain

Theor. Comput. Sci. 65, No. 2, 153-169 (1989).

Let s(n) be the number of ones in the binary expansion of the integer n, and r(n) be the number of (possibly overlapping) 11’s in this expansion. J. Coquet proved [Invent. Math. 73, 107-115 (1983; Zbl 0528.10006)] that the sum \(\sum_{n<N}(-1)^{s(3n)}\) has an oscillating behaviour. More precisely \[ \sum_{n<N}(-1)^{s(3n)}=N^{Log 3/Log 4}F(N)+O(1), \] where F is a real continuous and nowhere differentiable function such that \(F(4x)=F(x)\). J. Brillhart, P. Erdős and P. Morton [Pac. J. Math. 107, 39-69 (1983; Zbl 0469.10034)] proved a similar result for r(n), indeed \(\sum_{n<N}(-1)^{r(n)}\sim \sqrt{N} G(N)\) where G is continuous, almost nowhere differentiable, and satisfies \(G(4x)=G(x).\)
In the paper under review the authors considerably generalize these results: for a wide class of sequences v, obtained as images of fixed points of certain substitutions (not necessarily of constant length) one has \[ \sum_{n<N}v_ n\quad \sim \quad C(Log N)^{\alpha} N^{\beta} F(N), \] where F is continuous and multiplicatively periodic. The main tool is a “numeration system associated to a fixed point of a substitution”.
Note that, showing that \(x^{\beta}F(x)\) is self-affine (generalization of the definition of T. Kamae [Japan J. Appl. Math. 3, 271-280 (1986; Zbl 0646.28005)], the authors prove that F is nowhere differentiable (which implies that the function G in the second example above is actually nowhere differentiable).

Reviewer: J.-P.Allouche

MSC:

11A63	Radix representation; digital problems
11B99	Sequences and sets
68Q42	Grammars and rewriting systems

Keywords:

numeration systems; substitution; self-affine functions; finite alphabet; asymptotic formula; sums of digits; binary expansion; fixed points

Citations:

Zbl 0505.10029; Zbl 0528.10006; Zbl 0469.10034; Zbl 0646.28005

References:

[1]	Allouche, J. P.; Mendes-France, M., Suite de Rudin-Shapiro et modèle d’Ising, Bull. Soc. Math. Fr., 113, 273-283 (1983) · Zbl 0592.10049
[2]	Bertrand-Mathis, A., Développement en base θ; répartition mod 1 de la suite \((x θ^n)\); langages codés et θ-shift, Bull. Soc. Math. Fr., 114, 271-323 (1986) · Zbl 0628.58024
[3]	Brillhart, J.; Erdös, P.; Morton, P., On sums of Rudin-Shapiro coefficients II, Pacific J. Math., 107, 39-69 (1983) · Zbl 0469.10034
[4]	Christol, G.; Kamae, T.; Mendes-France, M.; Rauzy, G., Suites algébriques, automates et substitutions, Bull. Soc. Math. Fr., 108, 401-418 (1980) · Zbl 0472.10035
[5]	Cobham, A., Uniform tag sequences, Math. Systems Theory, 6, 164-192 (1972) · Zbl 0253.02029
[6]	Coquet, J., A summation formula related to the binary digits, Invent. Math., 73, 107-115 (1983) · Zbl 0528.10006
[7]	Dekking, F. M., On the distribution of digits in arithmetic sequences, Séminaire Théorie des Nombres, Bordeaux (1982/83) · Zbl 0529.10047
[8]	Dumont, J. M., Discrepance des progressions arithmétiques dans la suite de Morse, C.R. Acad. Sci., 297, 145-146 (1983) · Zbl 0533.10005
[9]	Dumont, J. M., Discrepance des progressions arithmétiques dans la suite de Morse, (Thèse de 3ème cycle (1984), Univ. Aix-Marseille I) · Zbl 0533.10005
[10]	Gantmacher, F. R., Théorie des Matrices (1966), Dunod: Dunod Paris, Chapitre 13 · Zbl 0136.00410
[11]	Kamae, T., A characterization of self-affine functions, Japan J. Appl. Math., 3, 271-280 (1986) · Zbl 0646.28005
[12]	Knuth, D., The Art of Computer Programming, Vol. 1 (1969), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0191.18001
[13]	Kono, N., On self-affine functions, Japan J. Appl. Math., 3, 259-269 (1986) · Zbl 0646.28004
[14]	Mauduit, C., Sur l’ensemble normal des substitutions de longueur quelconque, J. Number Theory, 29, 235-250 (1988) · Zbl 0655.10053
[15]	Parry, W., On the β expansion of real numbers, Acta Math. Acad. Sci. Hungar., 11, 401-416 (1960) · Zbl 0099.28103
[16]	M. Queffelec, Une nouvelle propriété des suites de Rudin-Shapiro, Pré-publications Mathématiques No. 62, Université Paris-Nord.; M. Queffelec, Une nouvelle propriété des suites de Rudin-Shapiro, Pré-publications Mathématiques No. 62, Université Paris-Nord. · Zbl 0597.10054
[17]	Rauzy, G., Nombres algébriques et substitutions, Bull. Soc. Math. Fr., 110, 147-178 (1982) · Zbl 0522.10032