Pseudorandomness of the Ostrowski sum-of-digits function

Lukas Spiegelhofer

doi:10.5802/jtnb.1042

Lukas Spiegelhofer ¹

¹ Institute of Discrete Mathematics and Geometry, Vienna University of Technology Wiedner Hauptstrasse 8–10 1040 Vienna, Austria

Journal de Théorie des Nombres de Bordeaux, Volume 30 (2018) no. 2, pp. 637-649.

Abstract
Résumé

For an irrational $α \in (0, 1)$ , we investigate the Ostrowski sum-of-digits function $σ_{α}$ . For $α$ having bounded partial quotients and $ϑ \in ℝ ∖ ℤ$ , we prove that the function $g : n \mapsto e (ϑ σ_{α} (n))$ , where $e (x) = e^{2 π i x}$ , is pseudorandom in the following sense: for all $r \in ℕ$ the limit

γ_{r} = lim_{N \to \infty} \frac{1}{N} \sum_{0 \leq n < N} g (n + r) \bar{g (n)}

exists and we have

lim_{R \to \infty} \frac{1}{R} \sum_{0 \leq r < R} {|γ_{r}|}^{2} = 0 .

Pour un nombre irrationnel $α \in (0, 1)$ , nous étudions la fonction somme des chiffres d’Ostrowski $σ_{α}$ . Étant donné un nombre $α$ à quotients partiels bornés et un nombre $ϑ \in ℝ ∖ ℤ$ , nous montrons que la fonction $g : n \mapsto e (ϑ σ_{α} (n))$ , où $e (x) = e^{2 π i x}$ , est pseudo-aléatoire dans le sens suivant : pour tout $r \in ℕ$ la limite

γ_{r} = lim_{N \to \infty} \frac{1}{N} \sum_{0 \leq n < N} g (n + r) \bar{g (n)}

existe et on a

lim_{R \to \infty} \frac{1}{R} \sum_{0 \leq r < R} {|γ_{r}|}^{2} = 0 .

Received: 2016-11-21
Revised: 2017-04-26
Accepted: 2017-06-21
Published online: 2018-12-06

DOI: 10.5802/jtnb.1042
Classification: 11A55, 11A67
Keywords: Ostrowski numeration, pseudorandomness, Fourier–Bohr spectrum
Author's affiliations:

Lukas Spiegelhofer ¹

¹ Institute of Discrete Mathematics and Geometry, Vienna University of Technology Wiedner Hauptstrasse 8–10 1040 Vienna, Austria

@article{JTNB_2018__30_2_637_0,
     author = {Lukas Spiegelhofer},
     title = {Pseudorandomness of the {Ostrowski} sum-of-digits function},
     journal = {Journal de Th\'eorie des Nombres de Bordeaux},
     pages = {637--649},
     publisher = {Soci\'et\'e Arithm\'etique de Bordeaux},
     volume = {30},
     number = {2},
     year = {2018},
     doi = {10.5802/jtnb.1042},
     language = {en},
     url = {https://jtnb.centre-mersenne.org/articles/10.5802/jtnb.1042/}
}

TY  - JOUR
TI  - Pseudorandomness of the Ostrowski sum-of-digits function
JO  - Journal de Théorie des Nombres de Bordeaux
PY  - 2018
DA  - 2018///
SP  - 637
EP  - 649
VL  - 30
IS  - 2
PB  - Société Arithmétique de Bordeaux
UR  - https://jtnb.centre-mersenne.org/articles/10.5802/jtnb.1042/
UR  - https://doi.org/10.5802/jtnb.1042
DO  - 10.5802/jtnb.1042
LA  - en
ID  - JTNB_2018__30_2_637_0
ER  -

%0 Journal Article
%T Pseudorandomness of the Ostrowski sum-of-digits function
%J Journal de Théorie des Nombres de Bordeaux
%D 2018
%P 637-649
%V 30
%N 2
%I Société Arithmétique de Bordeaux
%U https://doi.org/10.5802/jtnb.1042
%R 10.5802/jtnb.1042
%G en
%F JTNB_2018__30_2_637_0

Lukas Spiegelhofer. Pseudorandomness of the Ostrowski sum-of-digits function. Journal de Théorie des Nombres de Bordeaux, Volume 30 (2018) no. 2, pp. 637-649. doi : 10.5802/jtnb.1042. https://jtnb.centre-mersenne.org/articles/10.5802/jtnb.1042/

References
Cited by

[1] Guy Barat; Valérie Berthé; Pierre Liardet; Jörg Thuswaldner Dynamical directions in numeration, Ann. Inst. Fourier, Volume 56 (1987) no. 7, pp. 1987-2092 | Zbl: 1138.37005

[2] Guy Barat; Pierre Liardet Dynamical systems originated in the Ostrowski alpha-expansion, Ann. Univ. Sci. Budap. Sect. Comput, Volume 24 (2004), pp. 133-184 | Zbl: 1109.37010

[3] Valérie Berthé Autour du système de numération d’Ostrowski, Bull. Belg. Math. Soc. Simon Stevin, Volume 8 (2001) no. 2, pp. 209-239 | Zbl: 0994.68100

[4] Jean-Paul Bertrandias Suites pseudo-aléatoires et critères d’équirépartition modulo un, Compos. Math., Volume 16 (1964), pp. 23-28 | Zbl: 0207.05801

[5] Jean Coquet Sur les fonctions $q$ -multiplicatives pseudo-aléatoires, C. R. Math. Acad. Sci. Paris, Volume 282 (1976), pp. 175-178 | Zbl: 0316.10032

[6] Jean Coquet Contribution à l’étude harmonique des suites arithmétiques, 1978 (Thèse d’Etat, Orsay (France))

[7] Jean Coquet Répartition modulo $1$ des suites $q$ -additives, Commentat. Math., Volume 21 (1980), pp. 23-42 | Zbl: 0434.10030

[8] Jean Coquet Répartition de la somme des chiffres associée à une fraction continue, Bull. Soc. R. Sci. Liège, Volume 51 (1982) no. 3-4, pp. 161-165 | Zbl: 0497.10040

[9] Jean Coquet; Teturo Kamae; Michel Mendès France Sur la mesure spectrale de certaines suites arithmétiques, Bull. Soc. Math. Fr., Volume 105 (1977) no. 4, pp. 369-384 | Zbl: 0383.10035

[10] Jean Coquet; Georges Rhin; Philippe Toffin Représentations des entiers naturels et indépendance statistique. II, Ann. Inst. Fourier, Volume 31 (1981) no. 1, pp. 1-15 | Zbl: 0437.10026

[11] Jean Coquet; Georges Rhin; Philippe Toffin Fourier–Bohr spectrum of sequences related to continued fractions, J. Number Theory, Volume 17 (1983) no. 3, pp. 327-336 | Zbl: 0521.10044

[12] Peter J. Grabner; Pierre Liardet; Robert F. Tichy Odometers and systems of numeration, Acta Arith., Volume 70 (1995) no. 2, pp. 103-123 | Zbl: 0822.11008

[13] Hugh L. Montgomery The analytic principle of the large sieve, Bull. Am. Math. Soc., Volume 84 (1978) no. 4, pp. 547-567 | Zbl: 0408.10033

[14] Lukas Spiegelhofer Correlations for Numeration Systems (2014) (Ph. D. Thesis)

Cited by Sources: