Archive for April, 2012

When subsets can be sumsets

April 27, 2012

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.

On the non-monotonocity of the denominator of the sum of consecutive (generalized) unit fractions

April 12, 2012

I indeed merged the two articles mentioned in the two previous posts, into one glorious piece of awesome, if I may say so. I rewrote almost everything, gave new definitions, found better proofs, made more lemmas, etc. etc. I even changed the title. So now I’m waiting for some feedback from my thesis advisor, and then I can resubmit On the non-monotonicity of the denominator of the sum of consecutive (generalized) unit fractions to Integers: The Electronic Journal of Combinatorial Number Theory 🙂

Edit: under heavy influence of MathOverflow (those guys are awesome), I wrote an introduction for my paper. The above version is updated.

Edit2: Although I didn’t get any feedback from my thesis advisor, I resubmitted! The waiting can begin.

Edit3 (05-12-2012): My paper got accepted!! The Referee Report was quite positive, actually. It asked me to change, out of 23 mathematically dense pages, exactly one letter. The above version is, probably, the final version.

On the non-monotonicity of the denominator of the sum of consecutive unit fractions

April 3, 2012

Within 24 hours I managed to solve a problem I posed in my first article (see previous post), and (!!) write the whole thing up. Maybe I’ll merge the two, or maybe this will be my second article: On the non-monotonicity of the denominator of the sum of consecutive unit fractions. Anyway, good day!