Two Erdos problems on lacunary sequences: Chromatic number and Diophantine approximation

Abstract

Let $n_k$ be an increasing lacunary sequence, i.e., $n_{k+1}/n_k>1+r$ for some $r>0$. In 1987, P. Erdos asked for the chromatic number of a graph $G$ on the integers, where two integers $a,b$ are connected by an edge iff their difference $|a-b|$ is in the sequence $n_k$. Y. Katznelson found a connection to a Diophantine approximation problem (also due to Erdos): the existence of $x$ in $(0,1)$ such that all the multiples $n_{j}x$ are at least distance $\delta (x)>0$ from the set of integers. Katznelson bounded the chromatic number of $G$ by $C{r}^{-2}|\log r|$. We apply the Lovász local lemma to establish that $\delta (x)>cr|\log r{|}^{-1}$ for some $x$, which implies that the chromatic number of $G$ is at most $C{r}^{-1}|\log r|$. This is sharp up to the logarithmic factor.

9 pages

Cited by in corpus (2)

• On Furstenberg's Diophantine result
• Some refined results on mixed Littlewood conjecture for pseudo-absolute values