On Irregularities of Distribution of Binary Sequences Relative to Arithmetic Progressions, II (Constructive Bounds)

Dartyge, Cécile; Gyarmati, Katalin; Sárközy, András

doi:10.2478/udt-2018-0008

Abstract

In Part I of this paper we studied the irregularities of distribution of binary sequences relative to short arithmetic progressions. First we introduced a quantitative measure for this property. Then we studied the typical and minimal values of this measure for binary sequences of a given length. In this paper our goal is to give constructive bounds for these minimal values.

References

[1] BURGESS, D. A.: On character sums and primitive roots, Proc. London Math. Soc. 12 (1962), no. 3, 179–192.10.1112/plms/s3-12.1.179
Search in Google Scholar Back to article
[2] DARTYGE, C.—GYARMATI, K.—SÁRKÖZY, A.: On irregularities of distribution of binary sequences relative to arithmetic progressions, I. (General results), Unif. Distrib. Theory 12 (2017), no. 1, 55–67.10.1515/udt-2017-0004
Search in Google Scholar Back to article
[3] DAVENPORT, H.—ERDŐS, P.: The distribution of quadratic and higher residues, Publ. Math. Debrecen 2 (1952), 252–265.10.5486/PMD.1952.2.3-4.18
Search in Google Scholar Back to article
[4] ERDŐS, P.—SÁRKÖZY, A.: Some solved and unsolved problems in combinatorial number theory, Math. Slovaca 28 (1978), 407–421.
Search in Google Scholar Back to article
[5] GONG, K.: An elementary approach to character sums over multiplicative subgroups, Integers 16 (2016), #A13.
Search in Google Scholar Back to article
[6] MATOUŠEK, J.—SPENCER, J.: Discrepancy in arithmetic progression, J. Amer. Math. Soc. 9 (1996), 195–204.10.1090/S0894-0347-96-00175-0
Search in Google Scholar Back to article
[7] MAUDUIT, C.—SÁRKÖZY, A.: On finite pseudorandom binary sequences, I. Measure of pseudorandomness, the Legendre symbol, Acta Arith. 82 (1997), 365–377.10.4064/aa-82-4-365-377
Search in Google Scholar Back to article
[8] MAUDUIT, C.—SÁRKÖZY, A.: On finite pseudorandom binary sequences, II. The Champernowne, Rudin–Shapiro, and Thue–Morse sequences, a further construction, J. Number Theory 73 (1998), 256–276.10.1006/jnth.1998.2286
Search in Google Scholar Back to article
[9] MONTGOMERY, H. L.—VAUGHAN, R. C.: Mean values of character sums, Canad. J. Math. 31 (1979), no. 3, 470–487.10.4153/CJM-1979-053-2
Search in Google Scholar Back to article
[10] PÓLYA, G.: Über die Verteilung der quadratischen Reste und Nichtreste, Göttinger Nachrichten 1918, 21–29.
Search in Google Scholar Back to article
[11] QUEFFÉLEC, M.: Substitution Dynamical Systems—Spectral Analysis. In: Lecture Notes in Math. Vol. 1294, Springer-Verlag, Berlin, 1987.10.1007/BFb0081890
Search in Google Scholar Back to article
[12] ROTH, K. F.: Remark concerning integer sequences, Acta Arith. 9 (1964), 257–260.10.4064/aa-9-3-257-260
Search in Google Scholar Back to article
[13] RUDIN, W.: Some theorems on Fourier coefficients, Proc. Amer. Math. Soc. 10 (1959), 855–859.10.1090/S0002-9939-1959-0116184-5
Search in Google Scholar Back to article
[14] SÁRKÖZY, A.: Some remarks concerning irregularities of distribution of sequences of integers in arithmetic progressions, IV, Acta Math. Acad. Sci. Hungar. 30(1-2) (1977), 155–162.10.1007/BF01895660
Search in Google Scholar Back to article
[15] SHAPIRO, H. S.: Extremal Problems for Polynomials and Power Series. Doctoral Thesis, M. I. T., Massachusetts Institute of Technology, ProQuest LLC, Ann Arbor, MI, 1953.
Search in Google Scholar Back to article
[16] VINOGRADOV, A. I.: On the symmetry property for sums with Dirichlet characters, Izv. Akad. Nauk UZSR, Ser. Fiz.-Mat. Nauk 1965 (1965), no. 1, 21–27. (In Russian)
Search in Google Scholar Back to article
[17] WINTERHOF, A.: Some Estimates for Character Sums and Applications, Designs, Codes and Cryptography 22 (2001), 123–131.10.1023/A:1008300619004
Search in Google Scholar Back to article
[18] ZHAO, L.: Burgess bound for character sums, January 2007, http://www.researchgate.net/publication/237203641
Search in Google Scholar Back to article

On Irregularities of Distribution of Binary Sequences Relative to Arithmetic Progressions, II (Constructive Bounds)

Abstract

Paradigm

My account