## 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!