5
$\begingroup$

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?
$\endgroup$
  • 2
    $\begingroup$ Controlling the diameter of such a graph seems hard. Do you have examples where $S$ is meager? $\endgroup$ – Tom De Medts Apr 8 '15 at 10:17
  • $\begingroup$ 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/…). $\endgroup$ – Dominic van der Zypen Apr 8 '15 at 10:40
  • 1
    $\begingroup$ 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... $\endgroup$ – Tom De Medts Apr 8 '15 at 11:59
  • $\begingroup$ 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? $\endgroup$ – Dominic van der Zypen Apr 8 '15 at 12:18
  • 1
    $\begingroup$ 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. $\endgroup$ – Tom De Medts Apr 8 '15 at 12:30
3
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ In the first claim, a number $z$ may happen to be negative... $\endgroup$ – Ilya Bogdanov Apr 8 '15 at 11:37
  • $\begingroup$ @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. $\endgroup$ – Ben Barber Apr 8 '15 at 11:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.