Symbolic representation of piecewise linear functions on the unit interval and application to discrepancy. (English) Zbl 0813.11045

Let \(D_ N^*(U)\) denote the star-discrepancy of a sequence \(U\) in the unit interval. “Self-similar sequences” \(U\) are known for having a small discrepancy, i.e. \(L(U) : = \lim \sup ND_ N^*(U)/ \log N\) is finite, under some additional assumptions. In this paper the author applies techniques concerning substitutions on finite alphabets and automata to prove upper bounds for \(L(U)\), in a special case of such sequences. In an appendix (by H. Faure) the best possible values for the discrepancy of van der Corput and \((n \alpha)\)-sequences are given.
Reviewer: R.F.Tichy (Graz)


11K38 Irregularities of distribution, discrepancy
11B85 Automata sequences
Full Text: DOI


[1] Bejian, R., Minoration de la discrépance à l’origine d’une suite quelconque, Ann. Fac. Sci. Toulouse Math., 1, 201-213 (1979) · Zbl 0426.10039
[2] Borel, J.-P., Suites ayant de bonnes discrépances, J. Arith. Valenciennes (1982)
[3] Borel, J.-P., Self-similar measures and sequences, J. Number Theory, 31, 208-241 (1989) · Zbl 0673.10039
[4] Borel, J.-P., Contribution à l’étude de la distribution des suites, (Thèse d’Etat (1989), Marseille-Luminy)
[5] Borel, J.-P., Sur une suite de fonctions liées à un processus itératif, Publ. Dép. Math. Limoges, 12, 1-16 (1990)
[7] Borel, J.-P.; Pages, G.; Xiao, Y.-J., Suites à discrépance faible et intégration numérique, (Bouleau, N.; Talay, D., Probabilités numériques (1992), INRIA: INRIA Versailles), 7-22
[8] Dupain, Y., Discrépance à l’origine de la suite \((n(1+√ 5/2))\),, Ann. Inst. Fourier, 29, 81-106 (1979) · Zbl 0386.10021
[9] Eilenberg, S., Automata, Languages and Machines, Vol. A (1974), Academic Press: Academic Press London · Zbl 0317.94045
[10] Faure, H., Discrépance de suites associées à un système de numération (en dimension un), Bull. Soc. Math. France, 109, 143-182 (1981) · Zbl 0488.10052
[11] Faure, H., Etude des restes pour les suites de van der Corput généralisées, J. Number Theory, 16, 376-394 (1983) · Zbl 0513.10047
[12] Faure, H., Good permutations for extreme discrepancy, J. Number Theory, 42, 47-56 (1992) · Zbl 0768.11026
[13] Haber, S., On a sequence of points of interest for numerical quadrature, Res. Nat. Bur. Standards Sect. B, 70, 127-134 (1966) · Zbl 0158.16002
[14] Hedlund, G. A.; Morse, M., Symbolic dynamics II, sturmian trajectories, Amer. J. Math., 62, 1-42 (1940)
[15] Hofbauer, F., On intrinsic ergodicity of piecewise monotonic transformations with positive entropy, Israel J. Math., 34, 213-237 (1979) · Zbl 0422.28015
[16] Hofbauer, F., The maximal measure for linear mod one transformations, J. London Math. Soc., 23, 92-112 (1981) · Zbl 0431.54025
[17] Hofbauer, F., The structure of piecewise monotonic transformations, Ergodic Theory Dynamical Systems, 1, 159-178 (1981) · Zbl 0474.28007
[18] Kuipers, L.; Niederreiter, H., Uniform Distribution of Sequences (1974), Wiley: Wiley New York · Zbl 0281.10001
[19] Milnor, J.; Thurston, W., On iterated maps of the interval, (Dold, A.; Eckmann, B., Lecture Notes in Mathematics. Lecture Notes in Mathematics, Dynamical Systems, Vol. 1342 (1988), Springer: Springer Berlin), 465-563 · Zbl 0664.58015
[20] Ostrowski, A., Bemerkung zur Theorie der Diophantischen Approximationen III, Abh. Math. Sem. Univ. Hamburg, 4, 224 (1926)
[21] Queffelec, M., Substitution Dynamical Systems, (Lecture Notes in Mathematics, Vol. 1424 (1987), Springer: Springer Berlin) · Zbl 0642.28013
[22] Ramshaw, L., On the discrepancy of the sequence formed by the multiples of an irrational number, J. Number Theory, 13, 138-175 (1981) · Zbl 0458.10035
[23] Schmidt, W., Irregularities of distributions VII, Acta Arith., 21, 45-50 (1972) · Zbl 0244.10035
[24] Takahashi, Y., Isomorphism of β-isomorphisms to Markov automorphisms, Osaka J. Math., 10, 175-184 (1973) · Zbl 0268.28006
[25] van der Corput, J. G., Verteilungsfunctionen I and II, Proc. Akad. Amsterdam, 39, 1058-1066 (1936) · Zbl 0013.05703
[26] Varga, R. S., Matrix Iterative Analysis, ((1962), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ), Automatic Comp. Series · Zbl 0133.08602
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.