DescriptionA beautiful result in the study of arithmetic progressions modulo 1 is the three distance theorem, conjectured by Steinhaus and proved by Sós, Świerczkowski et al. According to this theorem, there are at most three distinct gaps between consecutive elements in any finite initial segment of the sequence of fractional parts of integer multiples of any real number. We interpret this theorem as a statement about the finiteness of the number of champions in a suitably defined tournament, and obtain higher-dimensional generalizations.
A famous open problem in combinatorial discrepancy theory, raised by Erdős many decades ago, is whether the hypergraph of homogeneous arithmetic progressions has unbounded discrepancy. We investigate a variant of this question. In 1986, Beck showed that given any 2-coloring, the hypergraph of quasi-progressions {lfloor n alpha rfloor} corresponding to almost all real numbers α in [1, ∞) has unbounded discrepancy, in fact, at least log* N, the inverse of the tower function. We make a substantial improvement on this lower bound, replacing log* N by (log N) 1/4 - o(1) and also show that there is some quasi-progression with discrepancy at least (1/50) N 1/6.
A fundamental result in Ramsey theory is the theorem of Hales and Jewett, which states that any 2-coloring of the nd hypercube admits a monochromatic line for any fixed n and sufficiently large d. We show that the Hales-Jewett number HJ(n) is at least exponential in n, improving the linear lower bound in the original paper of Hales and Jewett.
We also study a game-theoretic variant of the unbounded discrepancy problem where two players, Maker and Breaker, take turns coloring the integers from 0 to N with their own colors. Maker's goal is to obtain a lead on some homogeneous arithmetic progression that exceeds a pre-specified target, and Breaker's goal is to prevent this from happening. We show that given ε > 0$, Maker wins if the target is below N 1/2 - ε and Breaker wins if the target is above N 1/2 + ε for sufficiently large N.