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?



Diameter of sum-graph over a non-meager set
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](http://arxiv.org/abs/1212.6648).)



> 
> 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.


