Chromatic number of distance graphs over the integers

Assume that the chromatic number is $k$. Among the numbers $1,2,\dots, N$ there are at least $N/k$ numbers of the same color, say $a_1,\dots, a_t$. Then $D$ does not contain at least $t-1\geq N/k-1$ numbers not exceeding $N-1$, namely $a_i-a_1$, $i\geq2$. Thus the density of $D$ is at most $1-1/k$. Surely, this estimate is tight...


I'll show that if $G_D$ has chromatic number $k$ then $D$ has upper Banach density at most $(k-1)/k$.

So suppose $G_D$ has chromatic number $k$. Let $\mathbb{N}$ be partitioned into $P_1,\ldots,P_k$, where each $P_i$ is independent with respect to $G_D$. Without loss of generality, $P:=P_1$ has upper Banach density at least $1/k$. Let $Q=\{|x-y|:x,y\in P\text{ are distinct}\}$. Then $Q\subseteq \mathbb{N}^+\backslash D$ since $P$ is $G_D$-independent. We claim that $Q$ has lower Banach density at least $1/k$, which implies the desired result for $D$.

(The proof of the claim is an adaptation of Ruzsa's Covering Lemma and/or the well-known fact that if a set $A$ of integers has positive upper Banach density then $A-A$ is syndetic.)

Call a set $X\subset\mathbb{N}$ $P$-separating if $(x+P)\cap (y+P)=\emptyset$ for all distinct $x,y\in X$. Since $P$ has upper Banach density at least $1/k$, it follows that any $P$-separating subset of $\mathbb{N}$ has size at most $k$. So we may choose a $P$-separating set $X$ of maximal size. Now fix $a\in\mathbb{N}^+$ such that $a>\max X$. By maximality, there is some $x\in X$ such that $(a+P)\cap (x+P)\neq\emptyset$. So there are $p,q\in P$ such that $a+p=x+q$. Since $a>x$ it follows that $a\in x+Q$.

Altogether, we have shown that $X+Q$ is cofinite in $\mathbb{N}^+$. Since $|X|\leq k$, it follows that $Q$ has lower Banach density at least $1/k$.


Remark. The proof actually shows that if $G_D$ has chromatic number $k$ then there are $k$ translates of the complement of $D$ whose union is cofinite in $\mathbb{N}^+$, which I suppose is stronger than saying $D$ has upper Banach density at most $(k-1)/k$.