Skip Navigation


Proceedings of the London Mathematical Society Advance Access originally published online on August 21, 2007
Proceedings of the London Mathematical Society 2007 95(3):778-812; doi:10.1112/plms/pdm027
This Article
Right arrow Full Text (PDF)
Right arrow All Versions of this Article:
95/3/778    most recent
pdm027v1
Right arrow Alert me when this article is cited
Right arrow Alert me if a correction is posted
Services
Right arrow Email this article to a friend
Right arrow Similar articles in this journal
Right arrow Similar articles in ISI Web of Science
Right arrow Alert me to new issues of the journal
Right arrow Add to My Personal Archive
Right arrow Download to citation manager
Right arrow Search for citing articles in:
ISI Web of Science (1)
Right arrowRequest Permissions
Google Scholar
Right arrow Articles by Alon, N.
Right arrow Articles by Rödl, V.
Right arrow Search for Related Content
Social Bookmarking
Add to CiteULike   Add to Connotea   Add to Del.icio.us  
What's this?

© 2007 London Mathematical Society

Measures of pseudorandomness for finite sequences: typical values

N. Alon

Raymond and Beverly Sackler Faculty of Exact Sciences
Tel Aviv University
Tel Aviv 69978
Israel
noga{at}math.tau.ac.il

Y. Kohayakawa

Instituto de Matemática e Estatística
Universidade de São Paulo
Rua do Matão 1010
05508–090 São Paulo, SP
Brazil

C. Mauduit

Institut de Mathématiques de Luminy
CNRS-UPR901
163 av. de Luminy, case 907
13288 Marseille cedex 9
France
mauduit{at}iml.univ-mrs.fr

C. G. Moreira

IMPA
Estrada Dona Castorina 110
22460–320 Rio de Janeiro, RJ
Brazil
gugu{at}impa.br

V. Rödl

Department of Mathematics and Computer Science
Emory University
Atlanta, GA 30322
USA
rodl{at}mathcs.emory.edu

Received 12 April 2006.

Mauduit and Sárközy introduced and studied certain numerical parameters associated to finite binary sequences EN isin {–1, 1}N in order to measure their ‘level of randomness’. Those parameters, the normality measure N(EN), the well-distribution measure W(EN), and the correlation measure Ck(EN) of order k, focus on different combinatorial aspects of EN. In their work, amongst others, Mauduit and Sárközy (i) investigated the relationship among those parameters and their minimal possible value, (ii) estimated N(EN), W(EN) and Ck(EN) for certain explicitly constructed sequences EN suggested to have a ‘pseudorandom nature’, and (iii) investigated the value of those parameters for genuinely random sequences EN.

In this paper, we continue the work in the direction of (iii) above and determine the order of magnitude of N(EN), W(EN) and Ck(EN) for typical EN. We prove that, for most EN isin {–1, 1}N, both W(EN) and N(EN) are of order {surd} N, while Ck(EN) is of order Formula for any given 2 ≤ k ≤ N/4.

2000 Mathematics Subject Classification 68R15.

Part of this work was done at IMPA, whose hospitality the authors gratefully acknowledge. This research was partially supported by IM-AGIMB/IMPA. The first author was partially supported by the Israel Science Foundation, by a USA-Israeli BSF grant, by NSF grant CCR-0324906, by the James Wolfensohn fund and by the State of New Jersey. The second author was partially supported by FAPESP and CNPq through a Temático-ProNEx project (Proc. FAPESP 2003/09925-5) and by CNPq (Proc. 306334/2004-6 and 479882/2004-5). The third author was partially supported by the Brazil/France Agreement in Mathematics (Proc. CNPq 60-0014/01-5 and 69-0140/03-7). The fourth author was partially supported by MCT/CNPq through a ProNEx project (Proc. CNPq 662416/1996-1) and by CNPq (Proc. 300647/95-6). The fifth author was partially supported by NSF Grant DMS 0300529. The authors gratefully acknowledge the support of a CNPq/NSF cooperative grant (910064/99-7, 0072064).


Add to CiteULike CiteULike   Add to Connotea Connotea   Add to Del.icio.us Del.icio.us    What's this?




Disclaimer:
Please note that abstracts for content published before 1996 were created through digital scanning and may therefore not exactly replicate the text of the original print issues. All efforts have been made to ensure accuracy, but the Publisher will not be held responsible for any remaining inaccuracies. If you require any further clarification, please contact our Customer Services Department.