标题： 关于稀疏序列的两个爱尔特希问题：色数与丢番图逼近 显示英文标题

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

摘要： 设 ${n_k}$ 是一个增的稀疏序列，即 $n_{k+1}/n_k>1+r$ 对于某个 $r>0$ 成立。 1987 年，P. Erdős 询问整数图 $G$ 的色数，其中两个整数 $a,b$ 通过一条边相连当且仅当它们的差 $|a-b|$ 属于序列 ${n_k}$。 Y. 卡兹纳尔森发现了一个与丢番图逼近问题的联系（同样由埃尔德什提出）：在 $x$ 中存在一个元素 $(0,1)$，使得所有倍数 $n_j x$ 距离整数集至少为 $\delta(x)>0$。 卡兹纳尔森将 $G$ 的色数限制在 $Cr^{-2}|\log r|$ 以内。 我们应用了洛瓦兹局部引理来证明存在某个$x$使得$\delta(x)>cr|\log r|^{-1}$成立，这意味着$G$的色数至多为$Cr^{-1} |\log r|$。 这一结果在对数因子内是最优的。 显示英文摘要

摘要： 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 $Cr^{-2}|\log r|$. We apply the Lov\'asz 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 $Cr^{-1} |\log r|$. This is sharp up to the logarithmic factor.