On the Discrepancy of Quasi-Progressions

Sujith Vijay

Abstract


A quasi-progression, also known as a Beatty sequence, consists of successive multiples of a real number, with each multiple rounded down to the largest integer not exceeding it. In 1986, Beck showed that given any $2$-colouring, the hypergraph of quasi-progressions contained in $\{0,1,\ldots,n \}$ 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}$. The results remain valid even if the $2$-colouring is replaced by a partial colouring of positive density.


Full Text: PDF