# Diameter of sum-graph over a non-meager set

Given $S\subseteq \mathbb{N}$, we associate to $S$ the sum-graph $G_S = (\mathbb{N}, E)$ where $$E = \big\{\{m,n\}: m,n \in \mathbb{N} \text{ and } m+n\in S\big\}.$$

We say that $S\subseteq \mathbb{N}$ is meager if $$\text{lim sup}\frac{S\cap\{1,\ldots, n\}}{n} = 0.$$

Is there a set $S\subseteq \mathbb{N}$ such that

• $S$ is not meager;
• $G_S$ is connected;
• $\text{diam}(G_S)$ is infinite?
• Controlling the diameter of such a graph seems hard. Do you have examples where $S$ is meager? – Tom De Medts Apr 8 '15 at 10:17
• For instance the set of square numbers $S = \{n^2: n\in \mathbb{N}\}$ is meager. Moreover, it appears that the associated $G_S$ has diameter 4 (see mathoverflow.net/questions/201930/…). – Dominic van der Zypen Apr 8 '15 at 10:40
• Well, my question was of course whether you have examples where $S$ is meager but nevertheless the two other claims are valid, i.e. $G_S$ is connected but $\operatorname{diam}(G_S)$ is infinite... – Tom De Medts Apr 8 '15 at 11:59
• Sorry for misunderstanding. I think this would be a good question to ask - please go ahead. Or if you prefer not to, is it OK if I do it? – Dominic van der Zypen Apr 8 '15 at 12:18
• Sure, go ahead. It's just that because of the way you asked the question, I thought that perhaps you already had such an example in mind. – Tom De Medts Apr 8 '15 at 12:30

This is now an answer for the similar construction on $\mathbb Z$ rather than $\mathbb N$. To adapt the argument to $\mathbb N$ you would want to show that the intermediate $z$'s can be chosen to be positive. This can be ensured at the first stage using the ideas of Lemma 6 of http://arxiv.org/abs/1308.0488 (deleted the elements of $S$ that are less than $x$ or $y$), but for later stages things are not as clear. Thanks to Ilya Bogdanov for spotting the problem.

My guess is still that no such $S$ exist, and that these methods can be used to give a proof, but the details might take a while to work out.

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 Z$. 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 Z$. 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 if $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.

• In the first claim, a number $z$ may happen to be negative... – Ilya Bogdanov Apr 8 '15 at 11:37
• @IlyaBogdanov, you're quite right. I don't think this is serious, because we can restrict attention to just the large elements of $S$ without harming the density, and we still get one $m$ that works for all final segments of $S$ (see Lemma 6 of arxiv.org/abs/1308.0488). I'll have a look: hopefully the details won't be too messy. – Ben Barber Apr 8 '15 at 11:52