Erdős Problem #894

Let \(A=\{n_1<n_2<\cdots\}\subset \mathbb{N}\) be a lacunary sequence (so there exists some \(\epsilon>0\) with \(n_{k+1}\geq (1+\epsilon)n_k\) for all \(k\)). Is it true that there must exist a finite colouring of \(\mathbb{N}\) with no monochromatic solutions to \(a-b\in A\)? Asked by Erdős in 1987, according to Katznelson [Ka01]. In other words, does the Cayley graph defined on \(\mathbb{Z}\) by a lacunary sequence have a finite chromatic number? Katznelson observed that a positive solution to the problem follows from the answer to [464](https://www.erdosproblems.com/464), which yields an irrational \(\theta\) and \(\delta>0\) such that \(\inf_k \| \theta n_k\|>\delta\). In particular, the solution to [464](https://www.erdosproblems.com/464) implies the answer to this question is yes, with the best known quantitative bound, due to Peres and Schlag [PeSc10], being that there is a colouring with no solutions using at most \(\ll \epsilon^{-1}\log(1/\epsilon)\) colours.