## When subsets can be sumsets

Let $A$ and $B$ be sets of integers. With $A + B$ we denote the set of all integers that can be written as a sum of one term in $A$ and one term in $B$. That is, $A + B = \{a + b | a \in A, b \in B\}$. Let $n$ be any positive integer. If $S$ is any set of integers, we shall say that $S$ is n-summable, if sets $A$ and $B$ exist with $|A| = \infty$, $|B| = n$, and $A + B \subseteq S$. Note that being 1-summable is equivalent to being infinite. We call $S$ n-large if there exists a non-negative integer $m = m(n)$ and infinitely many $k$ such that $|\{k, k+1, .., k + m\} \cap S| \ge n$. Note that being 1-large is also equivalent to being infinite. And thus, $S$ is 1-summable if, and only if, $S$ is 1-large. In this post we will prove the following cute generalization of this fact:

A set $S$ is n-summable if, and only if, $S$ is n-large.

First we will prove that if $S$ is n-large, then $S$ is n-summable. To this end, let $k_1, k_2, ..$ be an infinite sequence such that for all $i \in \mathbb{N}$, we have: $|\{k_i, k_i+1, .., k_i + m\} \cap S| \ge n$. Define $S_i = (\{k_i, k_i+1, .., k_i + m\} \cap S) - k_i \subseteq \{0, 1, .., m\}$. Then we have infinitely many $S_i$, but at most $2^{m+1}$ distinct $S_i$. And thus, there exists an infinite subsequence $i_1, i_2, ..$ with $S_{i_1} = S_{i_2} = ..$. Now, define $A = \{k_{i_1}, k_{i_2}, .. \}$ and $B = S_{i_1}$. Then, by construction, we have $A + B \subseteq S$.

To prove the converse direction, assume $A$ is any infinite set of integers and assume $B = \{b_1, b_2, .., b_n\} \subseteq \mathbb{Z}$, with $b_1 < b_2 < .. < b_n$. Then we will prove that if $S$ is not n-large, then $A + B \not\subseteq S$. So assume that $|\{k, k+1, .., k + m\} \cap S| \le n-1$ for all $k$ with $|k| > k_m$. Now, let $a \in A$ be any integer larger (in absolute value) than $k_{b_n - b_1} + \max(|b_1|, |b_n|)$. Then $a + B$ is a set of $n$ integers, all larger (in absolute value) than $k_{b_n - b_1}$, with the difference between largest and smallest element being: $(a + b_n) - (a + b_1) = b_n - b_1$. In particular, $a + B \not\subseteq S$. And since $a + B \subseteq A + B$, we also have $A + B \not\subseteq S$.

Now, if we say $S$ is $\infty$-summable if $A, B$ exist with $|A| = |B| = \infty$ and $A + B \subseteq S$, then, unfortunately, it is not true that $S$ is $\infty$-summable if $S$ is n-summable for all $n \in \mathbb{N}$. A counterexample:

Define sets $S_1, S_2, ..$ as follows:

1) $|S_k| = l$, where $l$ is the $k$-th entry of https://oeis.org/A002260
2) If $|S_k| = l$, then $S_k = \{10^k + l, 10^k + 2l, .., 10^k + l^2 \}$

Define $S = \bigcup_{k=1}^{\infty} S_k$. Then $S$ is n-summable for all $n$, because $S$ is n-large for all $n$, with $m(n) = n(n-1)$. Although it is also easy to construct explicit sets $A$ and $B$ with $|A| = \infty$, $|B| = n$, and $A + B \subseteq S$. We claim, however, that $S$ is not $\infty$-summable. If $S$ were $\infty$-summable, then, by some appropriate addition or subtraction, we have $A + B \subseteq S$ for some infinite sets $A = \{a_1, a_2, .. \}$ and $B = \{b_1, b_2, .. \}$, with $0 < a_1 < a_2 < ..$ and $0 = b_1 < b_2 < ..$. In particular, $A \subseteq S$. Now, if $a_j \in S_k \subseteq S$ with $|S_k| > b_2$, then $a_j < a_j + b_2 < a_j + |S_k| < 10^{k+1}$. And thus, $a_j + b_2$ either lies strictly between two elements of $S_{k}$, or $a_j + b_2$ lies strictly between the largest element of $S_k$ and the smallest element of $S_{k+1}$. Either way, $a_j + b_2 \notin S$. So $A$ is contained in the sets $S_k$ that have no more than $b_2$ elements. Now, let $b_i$ be any element of $B$ larger than  $(b_2)^2$, and let $a_j \in S_k$ be any element of $A$ larger than $b_i$. Then, since $|S_k| \le b_2$, we have that $a_j + b_i > 10^k + (b_2)^2 \ge 10^k + |S_k|^2$. And thus, $a_j + b_i$ is larger than the largest element of $S_k$. On the other hand, $a_j + b_i \le 2a_j \le 2*(10^k + k^2) < 10^{k+1}$, which is thus smaller than the smallest element of $S_{k+1}$. And we must conclude that $a_j + b_i$ is not an element of $S$; contradiction.

I realize that the above proof that our counterexample works may be somewhat inelegant, so I might rewrite it soon. In which case I’ll probably explicitly prove something like the following: if $S$ is as above, $A$ is an infinite set, $B = \{b_1, b_2, .. \}$ with $0 = b_1 < b_2 < ..$, and $A + B \subseteq S$, then $|B| \le b_2$.

At last, I have the following hunch, on which I’ll probably be working for the next few days/years:

If there exists an absolute constant $c$, such that for all $n \in \mathbb{N}$ there exist infinitely many $k$ for which $|\{k, k+1, .., k + cn \} \cap S| \ge n$, then $S$ is $\infty$-summable.