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.


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

%d bloggers like this: