Sumsets not containing a power of two

June 26, 2012

Let A = \{a_1, a_2, .. \} be an infinite set of positive integers under the following constraints:

1) a_1 = 1.
2) For all k we have: a_k < a_{k+1} \le 2a_k + 1.

Let n be a non-negative integer and let S \subseteq \{0, 1, .., n\} be a set of non-negative integers containing 0. Define S + S = \{x + y | x,y \in S\}. That is, since S contains 0, the set S + S is the set of all integers that can be written as a sum of at most two non-zero elements of S. We now have the following theorem:

Theorem. If (S + S) \cap A = \emptyset, then |S| \le (n+j)/2, where j is either 1 or 2, according to whether the smallest element of A larger than n (which we shall call a_{k+1}) is even or odd.

In particular, if |S| \ge n/2 + 1, then some power of two can be written as sum of at most two elements of S. In Additive Number Theory: Inverse Problems and the Geometry of Sumsets (which is an awesome book, by the way!) this special case is proved and then used to prove the neat fact that if S \subseteq \{1, 2, .., n\} and |S| > n/3, then some power of two can be written as sum of at most four elements of S. We will now prove the general version.

Proof. When n \in A, then, for i = 0, 1, .., \lfloor (n-1)/2 \rfloor,  at most one of i, n-i lies in S (why does n/2 not lie in S?), so we then immediately have |S| \le (n+1)/2. So we may assume that n \notin A. Furthermore, for n = 0, we obviously have |S| \le (n+2)/2. Now assume that, for all n' < n we have that the largest set S' \subseteq \{0, 1, .., n'\} for which no a_i is the sum of at most two elements of S', has cardinality at most (n'+2)/2. We will use this induction hypothesis to prove our Theorem.

Case I. a_{k+1} is even.

First some definitions:

Let S \subseteq \{0, 1, .., n\} be a set such that no element of A can be written as a sum of at most two elements of S.
Let k be such that a_k < n < a_{k+1}.
Let m be such that n + m = a_{k+1} (note that m = a_{k+1} - n \le a_{k+1} - a_k - 1 \le (a_{k+1}-1)/2 \le a_k < n).
Let S_0 = S \cap \{0, 1, .., m-1\} (on which we will use the induction hypothesis, which is allowed, since m-1 < n).
Let S_{i-m+1} = S \cap \{i, a_{k+1} - i\}, for i = m, m+1, .., a_{k+1}/2.

Now note that, for all relevant i \ge 1, we get |S_i| \le 1, while for i = a_{k+1}/2 we even know |S_{i-m+1}| = 0 (again, why?). What’s left is a direct computation.

|S| = |S_0| + \displaystyle \sum_{i=1}^{a_{k+1}/2 - m} |S_{i}| \\  \le (m+1)/2 + a_{k+1}/2 - m \\  = a_{k+1}/2 - (m-1)/2 \\  = (n+1)/2

Case II. a_{k+1} is odd.

We carry over all definitions of Case I, with the exception of the fact that the sets S_{i-m+1} are now defined for i = m, m+1, .., (a_{k+1} - 1)/2, and we may no longer deduce the existence of an index i for which |S_i| = 0. The obvious computation now yields:

|S| = |S_0| + \displaystyle \sum_{i=1}^{(a_{k+1} + 1)/2 - m} |S_i| \\  \le (m+1)/2 + (a_{k+1} + 1)/2 - m \\  = (a_{k+1} + 1)/2 - (m-1)/2 \\  = (n+2)/2

And we’re done.

Removing Schanuel

May 14, 2012

Let u_{a,b} and v_{a,b} be coprime integers such that v_{a,b} is positive and \dfrac{u_{a,b}}{v_{a,b}} = \displaystyle \sum_{i=a}^b \dfrac{r_i}{i s_i}, where \{r_i\}_{i \in \mathbb{N}} and latex \{s_i\}_{i \in \mathbb{N}} are assumed to be given periodic sequences of integers. That is, for all i we have r_{i+t} = r_i for some t \in \mathbb{N} and s_{i+t'} = s_i for some t' \in \mathbb{N}. In my paper I prove the following statement:

If Schanuel’s Conjecture holds, then for every a \in \mathbb{N}, there exists an integer b > a, such that v_{a,b} < v_{a,b-1}. Furthermore, if \max_i |s_i| = 1, then the smallest such b grows at most linearly in a.

I now believe I can prove the above, without assuming Schanuel’s Conjecture! Although I haven’t fully convinced myself that my ideas work, I’m getting more confident by the minute. I will now present an (admittedly very brief) overview of my ideas. I will expand on this as time goes on. Also, for definitions and lemma’s I refer to, check my preprint.

I use Schanuel’s Conjecture for two things:

1) To get an arbitrarily large prime p dividing X_b. (Theorem 2 in my preprint)
2) To make sure \gcd(X_{a,b}, ls_b) < p.

It is, if I’m not mistaken, not hard to do the second part without Schanuel. We can prove that l < p (as I do on page 14, beginning with ‘Now that we have shown that X_n has arbitrarily large prime divisors’), and since \gcd(X_{a,b}, ls_b) < p is immediate when ls_b < p, we may assume l > ps_b^{-1}. Since p is arbitrarily large, l is arbitrarily large too. In particular, it must be divisible by a large prime power. On the other hand, we can use Lemma 4, 5, or 6 to make sure that X_{a,b} is not divisible by a large power of that prime, and we are done.

A proof of the first statement is somewhat more involved, but the idea is to take the following assumption:

There exists a finite set of primes, \{p_1, p_2, .., p_m\} such that, for all n, |X_n| can be written as |X_n| = p_1^{e_{1,n}} \cdots p_m^{e_{m,n}}.

And derive a contradiction  by using nested intervals I_1 \supset I_2 \supset .. \supset I_m such that for all k \in \{1,2,..,m\}, there exists a j \in \{1,2,..,m\}, such that p_k^{e_{k,n}} < n for all n \in I_j. In particular, p_k^{e_{k,n}} < n for all k and all n \in I_m, which is, for large enough n, a contradiction, since |X_n| > n^m, by Lemma 3.

To do this, realize that the last sentence implies that, for all n large enough, there exists an index k = k(n), such that p_k^{e_{k,n}} > n. But if c is an arbitrary constant, n is large enough and n' is the smallest integer larger than n such that p_{k(n)}^c divides n', then p_{k(n)}^{e_{k(n),n'}} < n'. Now, if we take c to be suitably large, then we have a large interval where p_{k(n)}^{e_{k(n),n''}} < n'' for all n'' inside this interval. Then, inside this interval, we repeat this trick with a different index k', and a slightly smaller constant c, such that inside this interval, we find a slightly smaller interval, such that for all n''' inside this smaller interval, we have p_{k'}^{e_{k',n'''}} < n'''. Repeat this process m times, and we have that p_k^{e_{k,n''''}} < n'''' for all k and all n'''' in the last, smallest, interval (which, to be clear, is thus contained in all the others).

Hopefully the above made some sense. If not, just have a little patience and look forward to more elaboration, which will come in due time. In the mean time, try to embrace the glorious notation I laid out in this post.

EDIT (9 december 2012): Have a look here.

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!

Sums of consecutive (generalized) unit fractions

March 10, 2012

Wow, I just submitted my very first article!! Big moment for me :D Let’s all hope Integers: The Elecronic Journal of Combinatorial Number Theory soon publishes Sums of consecutive (generalized) unit fractions. Woohooo! And, obviously, any feedback is greatly appreciated :)

A proof from the book

December 16, 2011

We shall prove the following identity:

1 + 2 + 4 + 8 + .. + 2^{k-1} = 2^k - 1,

with perhaps the most beautiful proof I have ever found.

Assume that we play a tournament with 2^k players, in which every game is a knock-out game between 2 players. So in the first round there are 2^{k-1} games to be played, one for every 2 people. Then in the second round only half of the players remains (i.e. 2^{k-1}), so there are another 2^{k-2} games to be played, and so forth. Right up to the semi final and final, which are just 2^1 and 2^0 = 1 games, respectively. So the total amount of games played in the tournament is: 1 + 2 + 4 + 8 + .. + 2^{k-1}. Another way to see how many games total there are played is the following: in every game, exactly 1 player gets eliminated. There is only one winner, so the other 2^k - 1 players must get elimated somewhere. So the total amount of games played must equal 2^k - 1. Kablam.

Conjecture concerning sequences with a lot of consecutive elements with small lcm

December 7, 2011

Let 1 \le a_1 < a_2 < .. be an infinite sequence of positive integers, such that, if we define A(n) to be the number of indices i such that \text{lcm}(a_i, a_{i+1})\le n, then we have for every \epsilon > 0 infinitely many n such that A(n) > (c - \epsilon)\sqrt{n}, where c = \displaystyle \sum_{j=1}^{\infty} \dfrac{1}{(j+1)\sqrt{j}} \approx 1.86. In my previous post I claimed that such sequences exist, and in due time I will prove this claim, but for now, let’s assume it.

Now, let \epsilon be small and n_1 < n_2 < .. be the sequence of all n such that A(n) > (c - \epsilon)\sqrt{n}. Then I’d like to bluntly conjecture that there exist infinitely many i such that \dfrac{n_{i+1}}{n_i} > c_1\epsilon^{-4}, for some absolute c_1. In particular, \displaystyle \limsup \dfrac{n_{i+1}}{n_i} goes to \infty as \epsilon goes to 0, that is: \displaystyle \lim_{\epsilon \rightarrow 0} \limsup_{i \rightarrow \infty} \dfrac{n_{i+1}}{n_i} = \infty

Sequences with bounded lcm for consecutive elements

December 6, 2011

On page 83 of the pdf-file of Old and New Problems and Results in Combinatorial Number Theory, the following is asked: If we have an infinite sequence 1 \le a_1 < a_2 < .. of positive integers and set A(n) to be the number of indices i such that \text{lcm}(a_i, a_{i+1}) \le n, do we then have A(n) = O(\sqrt{n})? In the following very short article I answer the finite version of this question, which also implies an affirmative answer to the original question: Sequences with bounded lcm for consecutive elements . I conjecture that the term \log(2n) is superfluous, but to get rid of it completely, a more detailed approach is needed. By the way, the constant c \approx 1.86 is best possible, in the sense that it is possible to construct an infinite sequence such that, for every \epsilon > 0 and infinitely many n, we have A(n) > (c-\epsilon)\sqrt{n}.

Hello World!

December 6, 2011

A reminder for myself: my name is woutervandoorn


Follow

Get every new post delivered to your Inbox.