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

.blurhash-client-img { display: none !important; }

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

Uniform distribution theory

Volume 12 (2017): Issue 1 (June 2017)

By: Cécile Dartyge, Katalin Gyarmati and András Sárközy

Open Access

|Jul 2017

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

Articles in this issue

DOI: https://doi.org/10.1515/udt-2017-0004 | Journal eISSN: 2309-5377 | Journal ISSN: 1336-913X

Journal RSS Feed

Language: English

Page range: 55 - 67

Submitted on: Oct 22, 2015

Accepted on: Jan 23, 2016

Published on: Jul 22, 2017

Published by: Slovak Academy of Sciences, Mathematical Institute

In partnership with: Paradigm Publishing Services

Publication frequency: 2 issues per year

Keywords:

arithmetic progressions,

well-distribution,

binary sequence

Related subjects:

Mathematics,

Algebra and number theory,

Discrete mathematics,

Probability and statistics,

Numerical and computational mathematics

© 2017 Cécile Dartyge, Katalin Gyarmati, András Sárközy, published by Slovak Academy of Sciences, Mathematical Institute
This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 License.

Volume 12 (2017): Issue 1 (June 2017)