Discrepancy of (centered) arithmetic progressions in Z(p).

Hebbinghaus, Nils and Srivastav, Anand (2014) Discrepancy of (centered) arithmetic progressions in Z(p). European Journal of Combinatorics, 35 . pp. 324-334.

Full text not available from this repository.


One of the celebrated and deep theorems in discrepancy theory says that the 2-color discrepancy of the hypergraph of arithmetic progressions in the first n integers is Theta(n(1/4)) (lower bound by Roth (1964), upper bound Matousek, Spencer (1996)). In this paper we consider the problem of finding the c-color discrepancy, c >= 2, of arithmetic progressions and centered arithmetic progressions resp. in Z(p). We will show that its discrepancy is much larger than for arithmetic progressions in the first n integers. It is easy to prove that for p = 2 the discrepancy of the arithmetic progressions in Z(p) is exactly (c - 1)/c and it is 1 for any p and c = 2 for the centered arithmetic progressions. But no matching upper and lower bounds were known beyond these special cases. We show that for both hypergraphs the lower bound is tight up to a logarithmic factor in p: the lower bound is Omega(root p/c) and the upper bound is O(p/c In p). The main work is the proof of the lower bounds with Fourier analysis on Z(p). We consider the result for the centered arithmetic progressions as our main achievement because here due to the lack of translation-invariance of the hypergraph Fourier analysis alone does not work and has to be combined with a suitable decomposition of such progressions. Techniques of this type may be useful also in other areas where lower bounds for combinatorial functions are sought. (C) 2013 Elsevier Ltd. All rights reserved.

Document Type: Article
Additional Information: Times Cited: 0 SI 6th European Conference on Combinatorics, Graph Theory and Applications (EuroComb) AUG 29-SEP 02, 2011 Budapest, HUNGARY 0
Research affiliation: OceanRep > The Future Ocean - Cluster of Excellence
OceanRep > The Future Ocean - Cluster of Excellence > FO-R11
Kiel University
Refereed: Yes
ISSN: 0195-6698
Projects: Future Ocean
Date Deposited: 30 Mar 2015 12:19
Last Modified: 30 Mar 2018 03:47
URI: http://oceanrep.geomar.de/id/eprint/27710

Actions (login required)

View Item View Item