Mathematics – Combinatorics
Scientific paper
2006-04-24
Mathematics
Combinatorics
15 pages
Scientific paper
The 2-colouring discrepancy of arithmetic progressions is a well-known problem in combinatorial discrepancy theory. In 1964, Roth proved that if each integer from 0 to N is coloured red or blue, there is some arithmetic progression in which the number of reds and the number of blues differ by at least (1/20) N^{1/4}. In 1996, Matousek and Spencer showed that this estimate is sharp up to a constant. The analogous question for homogeneous arithmetic progressions (i.e., the ones containing 0) was raised by Erdos in the 1930s, and it is still not known whether the discrepancy is unbounded. However, it is easy to construct partial colourings with density arbitrarily close to 1 such that all homogeneous arithmetic progressions have bounded discrepancy. A related problem concerns the discrepancy of quasi-progressions. A quasi-progression consists of successive multiples of a real number, with each multiple rounded down to the nearest integer. In 1986, Beck showed that given any 2-colouring, the quasi-progressions corresponding to almost all real numbers in (1, \infty) have discrepancy at least log* N, the inverse of the tower function. We improve the lower bound to (log N)^{1/4 - o(1)}, and also show that there is some quasi-progression with discrepancy at least (1/50) N^{1/6}. Our results remain valid even if the 2-colouring is replaced by a partial colouring of positive density.
No associations
LandOfFree
On The Discrepancy of Quasi-progressions does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with On The Discrepancy of Quasi-progressions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On The Discrepancy of Quasi-progressions will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-583030