On the discrepancy of quasi-progressions

Sujith Vijay

The electronic journal of combinatorics, Tome 15 (2008)

Résumé

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.

Détail

DOI : 10.37236/828

Classification : 05C65, 11B25
Mots-clés : quasi progression, Beatty sequence, hypergraph, discepancy, tower function