On Irregularities of Distribution of Binary Sequences Relative to Arithmetic Progressions, I. (General Results)

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

doi:10.1515/udt-2017-0004

Abstract

In 1964 K. F. Roth initiated the study of irregularities of distribution of binary sequences relative to arithmetic progressions and since that numerous papers have been written on this subject. In the applications one needs binary sequences which are well distributed relative to arithmetic progressions, in particular, in cryptography one needs binary sequences whose short subsequences are also well-distributed relative to arithmetic progressions. Thus we introduce weighted measures of pseudorandomness of binary sequences to study this property. We study the typical and minimal values of this measure for binary sequences of a given length.

References

[1] AISTLEITNER, C.: On the limit distribution of the well-distribution measure of random binary sequences, J. Thor. Nombres Bordeaux 25 (2013), no. 2, 245-259.
Search in Google Scholar Back to article
[2] ALON, N.-KOHAYAKAWA, Y.- MAUDUIT, C.-MOREIRA, C. G. - RÖDL, C. G.: Measures of pseudorandomness for finite sequences: typical values, Proc. Lond. Math. Soc. 95 (2007), 778-812.10.1112/plms/pdm027
Search in Google Scholar Back to article
[3] BECK, J.: Roth’s estimate of the discrepancy of integer sequences is nearly sharp, Combinatorica 1 (1981), 319-325.10.1007/BF02579452
Search in Google Scholar Back to article
[4] BECK, J.-SÁRKÖZY, A.-STEWART, V.: On irregularities of distribution in shifts and dilatations of integer sequences, II, in: Number Theory in Progress, Vol. 2 (K. Gy˝ory et al. eds.) Walter de Gruyter, Berlin-New York, 1999), pp. 633-638.10.1515/9783110285581.633
Search in Google Scholar Back to article
[5] CASSAIGNE, J.-MAUDUIT, C.-SÁRKÖZY, A.: On finite pseudorandom binary sequences VII: The measures of pseudorandomness, Acta Arith. 103 (2002), 97-118.10.4064/aa103-2-1
Search in Google Scholar Back to article
[6] CHERNOFF, H.: A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations, Ann. Math. Stat. 23 (1952), 493-507.10.1214/aoms/1177729330
Search in Google Scholar Back to article
[7] 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
[8] GYARMATI, K.: Measures of pseudorandomness, in: Finite fields and their Applications, (P. Charpin et al. eds.) Radon Ser. Comput. and Appl., De Gruyter, 2013, pp. 43-64.10.1515/9783110283600.43
Search in Google Scholar Back to article
[9] KOHAYAKAWA, Y.- MAUDUIT, C.- MOREIRA, C. G. - RÖDL, V.: Measures of pseudorandomness for finite sequences: minimum and typical values, in: Proc. of WORDS ’03, TUCS Gen. Publ.,Vol. 27, Turku Cent. Comput. Sci., Turku, 2003, 159-169.
Search in Google Scholar Back to article
[10] 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
[11] 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
[12] MÉRAI, L.: The higher dimensional analogue of certain estimates of Roth and S´ark¨ozy, Period. Math. Hung. (to appear)
Search in Google Scholar Back to article
[13] 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
[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 no. 1-2 (1977), 155-162. 10.1007/BF01895660
Search in Google Scholar Back to article
[15] SÁRKÖZY, A.-STEWART, C. L.: Irregularities of sequences relative to long arithmetic progressions, in: Analytic Number Theory, Essays in Honour of Roth, (W. W. R. Chen et al. eds.), Cambridge Univ. Press, Cambridge, (2009), 389-401.
Search in Google Scholar Back to article
[16] VALKÓ, B.: On irregularities of sums of integers, Acta Arith. 92 (2000), 367-381.10.4064/aa-92-4-367-381
Search in Google Scholar Back to article
[17] VALKÓ, B.: Discrepancy of arithmetic progressions in higher dimensions, J. Number Theory 92 (2002), 117-130.10.1006/jnth.2001.2704
Search in Google Scholar Back to article
[18] Chernoff bound, Wikipedia, http://en.wikipedia.org/wiki/Chernoff-bound
Search in Google Scholar Back to article

On Irregularities of Distribution of Binary Sequences Relative to Arithmetic Progressions, I. (General Results)

Abstract

Paradigm

My account