Discrepancy Results for The Van Der Corput Sequence

Spiegelhofer, Lukas

doi:10.2478/udt-2018-0010

Abstract

Let d_N = ND_N (ω) be the discrepancy of the van der Corput sequence in base 2. We improve on the known bounds for the number of indices N such that d_N ≤ log N/100. Moreover, we show that the summatory function of d_N satisfies an exact formula involving a 1-periodic, continuous function. Finally, we give a new proof of the fact that d_N is invariant under digit reversal in base 2.

References

[1] ALLOUCHE, J.-P.—SHALLIT, J.: The ring of k-regular sequences, Theoret. Comput. Sci. 98 (1992), no. 2, 163–197.10.1016/0304-3975(92)90001-V
Search in Google Scholar Back to article
[2] BECK, J.: Probabilistic Diophantine Approximation. Randomness in lattice point counting. (Ohkubo, Yukio ed.), Springer Monographs in Mathematics, Springer, Cham, 2014.10.1007/978-3-319-10741-7
Search in Google Scholar Back to article
[3] BÉJIAN, R.—FAURE, H.: Discrépance de la suite de Van der Corput, In: Séminaire Delange-Pisot-Poitou, 19e année: 1977/78, Théorie des Nombres, Fasc. 1, Exp. no. 13, (1978), Secrétariat Math., Paris, 14 pp.
Search in Google Scholar Back to article
[4] COONS, M.: Proof of Northshield’s conjecture concerning an analogue of Stern’s sequence for ℤ[√2], (2017). Preprint, http://arxiv.org/abs/1709.01987.
Search in Google Scholar Back to article
[5] COONS, M.—SPIEGELHOFER, L.: The maximal order of hyper-(b-ary)-expansions, Electron. J. Combin. 24 (2017). Paper 1.15.10.37236/5441
Search in Google Scholar Back to article
[6] COONS, M,—TYLER, J.: The maximal order of Stern’s diatomic sequence, Mosc. J. Comb. Number Theory 4 (2014), no. 3, 3–14.
Search in Google Scholar Back to article
[7] DELANGE, H.: Sur la fonction sommatoire de la fonction”somme des chiffres”, Enseignement Math. (2) 21 (1975), no. 1, 31–47.
Search in Google Scholar Back to article
[8] DRMOTA, M.—LARCHER, G.—PILLICHSHAMMER, F.: Precise distribution properties of the van der Corput sequence and related sequences, Manuscripta Math. 118 (2005), no. 1, 11–41.10.1007/s00229-005-0577-y
Search in Google Scholar Back to article
[9] DRMOTA, M.—SZPANKOWSKI, W.: A master theorem for discrete divide and conquer recurrences, J. ACM, 60 (2013), no. 3, Art. 16, 49 pp.10.1145/2487241.2487242
Search in Google Scholar Back to article
[10] FAURE, H.: Discrépances de suites associées à un système de numération (en dimension un), Bull. Soc. Math. France 109 (1981), no. 2, 143–182.10.24033/bsmf.1935
Search in Google Scholar Back to article
[11] _____Discrepancy and diaphony of digital (0, 1) -sequences in prime base, Acta Arith. 117 (2005), no. 2, 125–148.10.4064/aa117-2-2
Search in Google Scholar Back to article
[12] FAURE, H.—KRITZER, P.—PILLICHSHAMMER, F.: From van der Corput to modern constructions of sequences for quasi-Monte Carlo rules, Indag. Math. (N.S.) 26 (2015), no. 5, 760–822.10.1016/j.indag.2015.09.001
Search in Google Scholar Back to article
[13] FLAJOLET, P.—GRABNER, P.—KIRSCHENHOFER, P.—PRODINGER, H.—TICHY, R. F.: Mellin transforms and asymptotics: digital sums, Theoret. Comput. Sci. 123 (1994), no. 2, 291–314.10.1016/0304-3975(92)00065-Y
Search in Google Scholar Back to article
[14] GRABNER, P.-J.—HWANG, H.-K.: Digital sums and divide-and-conquer recurrences: Fourier expansions and absolute convergence, Constr. Approx., 21 (2005), no. 2, 149–179.10.1007/s00365-004-0561-x
Search in Google Scholar Back to article
[15] LARCHER, G.—PILLICHSHAMMER, F.: Sums of distances to the nearest integer and the discrepancy of digital nets, Acta Arith. 106 (2003), no. 4, 379–408.10.4064/aa106-4-4
Search in Google Scholar Back to article
[16] LEHMER, D. H.: On Stern’s Diatomic Series, Amer. Math. Monthly 36 (1929), no. 2, 59–67.10.1080/00029890.1929.11986912
Search in Google Scholar Back to article
[17] LIND, D. A.: An extension of Stern’s diatomic series, Duke Math. J. 36 (1969), 55–60.10.1215/S0012-7094-69-03608-4
Search in Google Scholar Back to article
[18] MORGENBESSER, J. F.—SPIEGELHOFER, L.: A reverse order property of correlation measures of the sum-of-digits function, Integers, 12 (2012), Paper No. A47.
Search in Google Scholar Back to article
[19] F. PILLICHSHAMMER, F.: On the discrepancy of (0, 1) -sequences, J. Number Theory 104 (2004), no. 2, 301–314.10.1016/j.jnt.2003.08.002
Search in Google Scholar Back to article
[20] PROĬNOV, P. D.—ATANASSOV, E. Y.: On the distribution of the van der Corput generalized sequences, C. R. Acad. Sci. Paris Sér. I Math. 307 (1988), no. 18, 895–900.
Search in Google Scholar Back to article
[21] ROBBINS, H.: A remark on Stirling’s formula, Amer. Math. Monthly 62 (1955), 26–29.10.2307/2308012
Search in Google Scholar Back to article
[22] SÓS, V. T.: On strong irregularities of the distribution of {nα} sequences, in: Studies in Pure Mathematics, Birkhäuser, Basel, 1983, pp. 685–700.10.1007/978-3-0348-5438-2_59
Search in Google Scholar Back to article
[23] SPIEGELHOFER, L.: A digit reversal property for an analogue of Stern’s sequence, J. Integer Seq. 20 (2017), no. 10, Art. 17.10.8.
Search in Google Scholar Back to article
[24] _____A digit reversal property for Stern polynomials, Integers 17 (2017), Paper No. A53.
Search in Google Scholar Back to article
[25] TIJDEMAN, R.—WAGNER, G.: A sequence has almost nowhere small discrepancy, Monatsh. Math. 90 (1980), no. 4, 315–329.10.1007/BF01540851
Search in Google Scholar Back to article

Discrepancy Results for The Van Der Corput Sequence

Abstract

Paradigm

My account