Skip to main content
1 of 2
Ben Barber
  • 4.6k
  • 2
  • 25
  • 38

For every dense (not meager) $S$ such that $G_S$ is connected, $\text{diam}(G_S)$ is finite.

Write $A \pm B = \{a \pm b : a \in A, b \in B\}$ and $kA = A + A + \cdots + A$ with $k$ $A$'s.

Claim. Let $x, y \in \mathbb N$. Then $x$ and $y$ are joined by a walk of length $2$ in $G_S$ if and only if $x - y \in S - S$.

Proof. $x$ and $y$ are joined by a walk of length $2$ if and only if there is a $z$ such that $x + z$ and $y + z$ are both in $S$. If there is such a $z$, write $x + z = s_1$ and $y + z = s_2$. Then $x - y = s_1 - s_2 \in S-S$. Conversely, if $x - y \in S-S$, then $x - y = s_1 - s_2$ for some $s_1, s_2 \in S$, and setting $z = s_1 - x = s_2 - y$ provides a suitable centre for a walk of length 2 joining $x$ and $y$.

Claim. Let $x, y \in \mathbb N$. Then $x$ and $y$ are joined by a walk of length $4$ in $G_S$ if and only if $x - y \in 2S - 2S$.

Proof. $x$ and $y$ are joined by a walk of length $4$ if and only if there is a $z$ such that $x-z$ and $z - y$ are both in $S-S$. If there is such a $z$, then $x-y \in (S-S) + (S-S) = 2S-2S$. Conversely, if $x - y \in S-S$ then there is a $z$ such that $x - z \in S-S$ and $z-y \in S-S$.

Inductively:

$x$ and $y$ are joined by a walk of length $2^k$ if and only in $x-y \in 2^{k-1}S - 2^{k-1}S$.

Write $d(S)$ for the value of the limit in the question. The following is a result of Stewart and Tijdeman. (A refinement of this result can be found online as Lemma 7 in this paper of mine.)

If $2^k > 2/d(S)$, then there is an $m \in \mathbb N$ such that $2^kS - 2^kS = m \cdot \mathbb Z$ (the set of multiples of $m$).

So there is a $d$ and an $m$ such that $x-y$ are at distance at most $d$ whenever $x - y$ is divisible by $m$, hence every residue class modulo $m$ has diameter at most $d$ in $G_S$. Since $G_S$ is connected, there is at least one path joining any pair of residue classes, so the diameter of $G_S$ is finite.

Ben Barber
  • 4.6k
  • 2
  • 25
  • 38