Erdős Problem 894: colouring lacunary differences
Statement and result.
Suppose $n_{j+1}\geq(1+\epsilon)n_j$, where $\epsilon>0$. There is a finite colouring of the positive integers such that no two equally coloured integers have difference $n_j$. We give the circle-colouring deduction explicitly, including its quantitative bound. The Diophantine input is external.
The precise input.
Peres and Schlag, Theorem 3.1 of
Two Erdős problems on lacunary sequences: chromatic number and Diophantine approximation,
https://arxiv.org/abs/0706.0223, prove that an increasing integer sequence satisfying \[
n_{j+M}>2n_j,\qquad M\geq4,
\] admits $\theta\in[0,1)$ with $\|n_j\theta\|\geq\delta=c/(M\log M)>0$ for every $j$; here $c>0$ is an absolute constant, decreased if necessary. The local-lemma proof of this theorem is not repeated here. Taking \[
M=\max\left(4,1+\left\lceil
\frac{\log2}{\log(1+\epsilon)}\right\rceil\right)
\] verifies its strict doubling hypothesis.
Construction and verification of the colouring.
Choose an integer $q>1/\delta$, and colour $a\in\mathbb N$ by the unique $i\in\{0,\ldots,q-1\}$ such that \[
\{a\theta\}\in[i/q,(i+1)/q).
\] These are fractional parts, rather than distances to the nearest integer: the latter would identify opposite points of the circle. If $a,b$ have the same colour, their fractional parts differ by less than $1/q$. Consequently \[
\|(a-b)\theta\|<1/q<\delta.
\] Thus $|a-b|$ cannot equal any $n_j$. This verifies every forbidden difference simultaneously and does not require $\theta$ to be irrational. For $0<\epsilon\leq1/2$, we obtain \[
q=O\!\left(\epsilon^{-1}\log(1/\epsilon)\right).
\] For larger $\epsilon$, a fixed absolute number of colours follows from the same formula for $M$.
Why dependence on lacunarity is necessary.
For $0<\epsilon\leq1/2$, put $K=\lfloor1/\epsilon\rfloor$. The initial segment $1,2,\ldots,K$ satisfies the required successive-ratio bound. Extend it indefinitely by choosing each next integer at least $1+\epsilon$ times its predecessor. The vertices $1,2,\ldots,K+1$ form a clique in its difference graph, because all their positive pairwise differences belong to the initial segment. Hence some such sequences require at least $K+1$ colours. The upper bound therefore has the correct reciprocal dependence up to a logarithmic factor.
Attribution and assessment.
The circle-colouring argument is the standard deduction associated with Katznelson's formulation; see
https://www.erdosproblems.com/894, checked 24 September 2026. This is a complete deduction from the stated Peres--Schlag theorem, not a new-discovery claim or a local formal verification.
Completion estimate.
COMPLETION: 100%