Lewko's blog

The Eberhard-Green-Manners Sum-free Subset Theorem, and `What is Sum-free(13)?’

Posted in math.CO, Open Problem by Mark Lewko on February 19, 2013

The first research level math problem I seriously worked on (without much success) was the sum-free subset problem. A sum-free set (in an additive group) is a set that contains no solution to the equation x+y=z.  The sum-free subset problem concerns the following theorem of Erdős, which is one of the early applications of the probabilistic method.

Theorem: (Erdős, 1965) Let A be a finite set of natural numbers. There exists a sum-free subset S \subseteq A such that |S| \geq \frac{1}{3}|A| + \frac{1}{3}.

The natural problem here is to determine how much one can improve on this result. Given the simplicity of the proof, it seems that one should be able to better. However, the best result to date is \frac{|A|}{3}+ \frac{2}{3} (for |A|>2) due to Bourgain (1995) using Fourier analysis. It seems likely that there is a function f(n) \rightarrow \infty such that one may take |S| \geq \frac{|A|}{3}+ f(|A|) in the above theorem, however proving this seems to be quite challenging.  On the other hand proving a good upper bound also was a longstanding open problem, namely deciding if the constant \frac{1}{3} could be replaced by a larger constant. This problem, in fact, has received a fair amount of attention over the years. In his 1965 paper Erdos states that Hinton proved that the constant is at most \frac{7}{15} \approx .467 and that Klarner improved this to \frac{3}{7}. In 1990 Alon and Kleitman improved this further to \frac{12}{29} \approx 0.414, and Malouf in her thesis (as well as Furedi) improved this further to \frac{2}{5} = .4. A couple years ago I improved this to \frac{11}{28} \approx .393 (I recently learned that Erdős claimed the same bound without a proof in a handwritten letter from 1992). More recently, Alon improved this to \frac{11}{28} - 10^{-50000} (according to Eberhard, Green and Manners, Alon’s paper doesn’t appear to be electronically available. UPDATE: Alon’s paper can be found here). All of these results (with the exception of Alon’s) proceed simply be constructing a set and proving its largest sum-free subset is at most a certain size (then an elementary argument can be used to construct arbitrarily large sets with the same constant: see this blog post of Eberhard). On the other hand, it is obvious from the statement of the theorem above that one can’t have a set whose largest sum-free subset is exactly \frac{|A|}{3}, thus a simple proof by example is hopeless. The futile industry of constructing examples aside,  I spent a lot of effort thinking about this problem and never got very far.

About a month ago Sean Eberhard, Ben Green and Freddie Manners solved this problem, showing that \frac{1}{3} is indeed the optimal constant!  I don’t yet fully understand their proof, and will refer the reader to their introduction for a summary of their ideas.  However, having learned the problem’s difficulty firsthand, I am very pleased to see it solved.

In the wake of this breakthrough on the upper bound problem, I thought I’d take this opportunity to highlight a toy case of the lower bound problem.

Definition: For a natural number n define the sum-free subset number Sum-free(n) to be the largest number such that every set of n natural numbers is guaranteed to contain a sum-free subset of size at least Sum-free(n).

Thus by Bourgain’s theorem we have that Sum-free(n) \geq \frac{n+2}{3} (and the Eberhard-Green-Manners theorem states Sum-free(n)=\frac{n}{3}+o(1)). It turns out that Bourgain’s result is sharp for sets of size 12 and smaller. However, Bourgain’s theorem only tells us that a set of size 13 must contain a sum-free subset of size 5 while it seems likely (from computer calculations) that every set of size 13 must in fact contain a sum-free subset of size 6. Indeed, I’ll even

Conjecture: Sum-free(13)=6.

While the asymptotic lower bound problem (showing that there f(|A|) \rightarrow \infty) seems very hard and is connected with subtle questions in harmonic analysis (such as the now solved Littewood conjecture on exponential sums), this problem is probably amenable to elementary combinatorics (although, it certainly does not seem easy!). Below is a chart showing what I know about the first 15 sum-free subset numbers.

 

n Bourgain’s lower bound
on Sum-free(n)
Best known upper
bound on Sum-free(n)
Upper bound set example
1 1 1 \{1\}
2 1 1 \{1,2\}
3 2 2 \{1,2,3\}
4 3 3 \{1,2,3,4\}
5 3 3 \{1,2,3,4,5\}
6 3 3 \{1,2,3,4,5,6\}
7 3 3 \{1,2,3,4,5,6,8\}
8 4 4 \{1,2,3,4,5,6,7,9\}
9 4 4 \{1,2,3,4,5,6,7,8,10\}
10 4 4 \{1,2,3,4,5,6,8,9,10,18\}
11 5 5 \{1,2,3,4,6,10,20,70,140,210,420\}
12 5 5 \{1,2,3,4,5,6,7,8,9,10,14,18\}
13 5 6 \{1,2,3,4,6,10,20,35,70,105,140,210,420\}
14 6 6 \{1,2,3,4,5,6,7,10,12,14,30,35,60,70\}
15 6 7 \{1,2,3,4,6,10,20,30,35,60,70,105,140,210,420\}

An improved upper bound for the sum-free subset constant

Posted in math.CO, Paper, Uncategorized by Mark Lewko on August 27, 2010

I recently arXiv’ed a short note titled An Improved Upper Bound for the Sum-free Subset Constant. In this post I will briefly describe the result.

We say a set of natural numbers A is sum-free if there is no solution to the equation x+y=z with x,y,z \in A. The following is a well-known theorem of Erdős.

Theorem Let A be a finite set of natural numbers. There exists a sum-free subset S \subseteq A such that |S| \geq \frac{1}{3}|A|.

The proof of this theorem is a common example of the probabilistic method and appears in many textbooks. Alon and Kleitman have observed that Erdős’ argument essentially gives the theorem with the slightly stronger conclusion |S| \geq \frac{|A|+1}{3}. Bourgain  has improved this further, showing that the conclusion can be strengthened to |S| \geq \frac{|A| + 2}{3}. Bourgain’s estimate is sharp for small sets, and improving it for larger sets seems to be a difficult problem. There has also been interest in establishing upper bounds for the problem. It seems likely that the constant 1/3 cannot be replaced by a larger constant, however this is an open problem. In Erdős’ 1965 paper, he showed that the constant \frac{1}{3} could not be replaced by a number greater than 3/7 \approx .429 by considering the set \{2,3,4,5,6,8,10\}. In 1990, Alon and Kleitman improved this to 12/29 \approx .414. In a recent survey of open problems in combinatorics, it is reported that Malouf has shown the constant cannot be greater than 4/10 = .4.  While we have not seen Malouf’s proof, we note that this can be established by considering the set \{1,2,3,4,5,6,8,9,10,18\}. In this note we further improve on these results by showing that the optimal constant cannot be greater than 11/28 \approx .393.

Tagged with: ,

Sets of large doubling and a question of Rudin

Posted in Fourier Analysis, math.CA, math.CO, Paper by Mark Lewko on April 2, 2010

Update (May 2, 2010): After posting this preprint, Stefan Neuwirth informed us that Rudin’s question had been previously answered by Y. Meyers in 1968. It appears that Meyers’ construction doesn’t, however, say anything about the anti-Freiman problem. Indeed Meyers’ set (and all of its subsets) contains a B_{2}[2] set of density 1/4. Hence, the construction of a \Lambda(4) set that doesn’t contain a large B_{2}[2] set still appears to be new. A revised version of the paper has been posted reflecting this information.  Most notably, we have changed the title to “On the Structure of Sets of Large Doubling”.

Allison Lewko and I recently arXiv’ed our paper “Sets of Large Doubling and a Question of Rudin“. The paper (1) answers a question of Rudin regarding the structure of {\Lambda(4)} sets (2) negatively answers a question of O’Bryant about the existence of a certain “anti-Freiman” theorem (3) establishes a variant of the (solved) Erdös-Newman conjecture. I’ll briefly describe each of these results below.

— Structure of {\Lambda(4)} sets —

Before describing the problem we will need some notation. Let {S \subset {\mathbb Z}^d} and define {R_{h}(n)} to be the number of unordered solutions to the equation {x_{1}+\ldots + x_{h}=n} with {x_{1},\ldots,x_{h} \in S}. We say that {S} is a {B_{h}[G]} set if {R_{h}(n) \leq G} for all {n \in Z^d}. There is a similar concept with sums replaced by differences. Since this concept is harder to describe we will only introduce it in the case {h=2}. For {S \subset Z^{d}} we define {R_{2}^{\circ}(n)} to be the number of solutions to the equation {x_{1}-x_{2} = n} with {x_{1},x_{2}\in S}. If {R_{2}^{\circ}(n)\leq G} for all nonzero {n} we say that {S} is a {B_{2}^{\circ}[G]} set.

Let {S} be a subset of the integers {{\mathbb Z}^{d}}, and call {f : \mathbb{T}^{d} \rightarrow {\mathbb C}} an {S}-polynomial if it is a trigonometric polynomial whose Fourier coefficients are supported on {S} (i.e. {\hat{f}(n) = 0} if {n \in {\mathbb Z^{d}} \setminus S}). We say that {S} is a {\Lambda(p)} set (for {p>2}) if

\displaystyle ||f||_{L^p} \leq K_{p}(S) ||f||_{L^{2}} \ \ \ \ \ (1)

holds for all {S}-polynomials where the constant {K_{p}(S)} only depends on {S} and {p}. If {p} is an even integer, we can expand out the {L^{p}} norm in 1. This quickly leads to the following observation: If {S} is a {B_{h}[G]} set then {S} is also an {\Lambda(2h)} set ({h>1}, {h \in Z}). One can also easily show using the triangle inequality that the union of two {\Lambda(p)} sets is also a {\Lambda(p)} set. It follows that the finite union of {B_{h}[G]} sets is a {\Lambda(2h)} set. In 1960 Rudin asked the following natural question: Is every {\Lambda(2h)} set is a finite union of {B_{h}[G]} sets?

In this paper we show that the answer is no in the case of {\Lambda(4)} sets. In fact, we show a bit more than this. One can easily show that a {B_{2}^{\circ}[G]} set is also a {\Lambda(4)} set. Our first counterexample to Rudin’s question proceeded (essentially) by constructing a {B_{2}^{\circ}[2]} set which wasn’t the finite union of {B_{2}[G]} sets. This however raised the following variant of Rudin’s question: Is every {\Lambda(4)} set the mixed finite union of {B_{2}[G]} and {B_{2}^{\circ}[G]} sets? We show that the answer to this question is no as well. To do this we construct a {B_{2}[G]} set, A, which isn’t a finite union of {B_{2}^{\circ}[G]} sets, and a {B_{2}^{\circ}[G]} set, {B}, which isn’t the finite union of {B_{2}[G]} sets. We then consider the product set {S= A \times B \subset Z^{2}} which one can prove is a {\Lambda(4)} subset of {Z^{2}}. It isn’t hard to deduce from this that {S} is a {\Lambda(4)} subset of {Z^2} that isn’t a mixed finite union of {B_{2}[G]} and {B_{2}^{\circ}[G]} sets. Moreover, one can (essentially) map this example back to {Z} while preserving all of the properties stated above. Generalizing this further, we show that there exists a {\Lambda(4)} set that doesn’t contain (in a sense that can be made precise) a large {B_{2}[G]} or {B_{2}^{\circ}[G]}. This should be compared with a related theorem of Pisier which states that every Sidon set contains a large independent set (it is conjectured that a Sidon set is a finite union of independent sets, however this is open).

We have been unable to extend these results to {\Lambda(2h)} sets for {h>2}. Very generally, part of the issue arises from the fact that the current constructions hinges on the existence of arbitrary large binary codes which can correct strictly more than a {1/2} fraction of errors. To modify this construction (at least in a direct manner) to address the problem for, say, {\Lambda(6)} sets it appears one would need arbitrary large binary codes that can correct strictly more than a {2/3} fraction of errors. However, one can show that such objects do not exist.

— Is there an anti-Freiman theorem? —

 Let {A} be a finite set of integers and denote the sumset of {A} as {A+A = \{a+b : a,b \in A\}}. A trivial inequality is the following

\displaystyle 2|A|-1 \leq |A+A| \leq {|A| \choose 2}.

In fact, it isn’t hard to show that equality only occurs on the left if {A} is an arithmetic progression and only occurs on the right if {A} is a {B_{2}[1]} set. A celebrated theorem of Freiman states that if {|A+A| \approx |A|} then {A} is approximately an arithmetic progression. More precisely, if {A} is a finite set {A \subseteq {\mathbb Z}} satisfying {|A+A| \leq \delta |A|} for some constant {\delta}, then {A} is contained in a generalized arithmetic progression of dimension {d} and size {c |A|} where {c} and {d} depend only on {\delta} and not on {|A|}.

It is natural to ask about the opposite extreme: if {|A+A| \geq \delta |A|^2}, what can one say about the structure of {A} as a function only of {\delta}? A first attempt might be to guess that if {|A+A|\geq \delta |A|^2} for some positive constant {\delta}, then {A} can be decomposed into a union of {k} {B_2[G]} sets where {k} and {G} depend only on {\delta}. This is easily shown to be false. For example, one can start with a {B_2[1]} of {n} elements contained in the interval {[n+1,\infty)} and take its union with the arithmetic progression {[1,n]}. It is easy to see that {|A+A| \geq \frac{1}{10} |A|^2} regardless of {n}. However, the interval {[1,n]} cannot be decomposed as the union of {k} {B_2[G]} sets with {k} and {G} independent of {n}.

There are two ways one might try to fix this problem: first, we might ask only that {A} contains a {B_2[G]} set of size {\delta' |A|}, where {\delta'} and {G} depend only on {\delta}. (This formulation was posed as an open problem by O’Bryant here). Second, we might ask that {|A'+A'|\geq \delta |A'|^2} hold for all subsets {A' \subseteq A} for the same value of {\delta}. Either of these changes would rule out the trivial counterexample given above. In this paper we show that even applying both of these modifications simultaneously is not enough to make the statement true. We provide a sequence of sets {A \subseteq {\mathbb Z}} where {|A'+A'|\geq \delta |A'|^2} holds for all of their subsets for the same value of {\delta}, but if we try to locate a {B_2[G]} set, {B}, of density {1/k} in {A} then {k} must tend to infinity with the size of {A}. As above, our initial construction of such a sequence of {A}‘s turned out to be {B^\circ_2[2]} sets. This leads us to the even weaker anti-Freiman conjecture:

(Weak Anti-Freiman) Suppose that {A \subseteq {\mathbb Z}} satisfies {|A'+A'|\geq \delta |A'|^2} and {|A'-A'|\geq \delta |A'|^2} for all subsets {A' \subseteq A}. Then {A} contains either a {B_2[G]} set or a {B^\circ_2[G]} set of size {\geq \delta' |A|}, where {G} and {\delta'} depend only on {\delta}.

We conclude by showing that even this weaker conjecture fails. The constructions are the same as those used in the {\Lambda(4)} results above. The two problems are connected by the elementary observation that if {A'} is a subset of a {\Lambda(4)} set {A} then {|A'+A'|\geq \delta |A'|^2} holds where {\delta} only depends on the {\Lambda(4)} constant {K_{4}(A)} of the set {A}.

— A variant of the Erdös-Newman conjecture —

In the early 1980’s Erdös and Newman independently made the following conjecture: For every {G} there exists a {B_{2}[G]} that isn’t a finite union of {B_{2}[G']} sets for any {G'\leq G-1}. This conjecture was later confirmed by Erdös for certain values of {G} using Ramsey theory, and finally resolved completely by Nešetřil and Rödl using Ramsey graphs. One further application of our technique is the following theorem which can be viewed as an analog of the Erdös-Newman problem with the roles of the union size and {G} reversed.

Theorem 1 For every {k >1} there exists a union of k {B_{2}[1]} sets that isn’t a finite union of {k'\leq k-1} {B_{2}[G]} sets for any {G}.

Condemned prisoners and random permutations

Posted in expository, math.CO by Mark Lewko on September 2, 2009

In this post I will present one of my favorite logic puzzles. As with many great logic puzzles (see the blue-eyed islanders puzzle, for example), the mathematics is embedded in a gruesome storyline. The puzzle can be stated as follows:

There are 100 prisoners. The warden places 100 wooden boxes in a row in an empty room. He writes the name of each prisoner on 100 separate slips of paper and places one of these slips into each of the 100 boxes, in a manner of his choosing.

Each prisoner is lead into the room, one at a time. The prisoner is allowed to open up to 50 boxes. If the prisoner does not find his own name, all prisoners are executed. If a prisoner finds his own name, the prisoner must reset the boxes exactly as he found them. The process then continues onto the next prisoner. If all 100 prisoners find their own name, all of the prisoners will be released the next morning.

The prisoners are allowed to agree on a strategy before this process starts, however they may not communicate in any way after the process has started. What strategy should the prisoners use to minimize the chance of execution?

Notice that if each of the prisoners open 50 randomly selected boxes, then each prisoner will find his own name with probability {1/2}. Thus the prisoners will escape execution with probability

\displaystyle \left(1/2\right)^{100}\approx 0.7888609052\times 10^{-30}.

This is roughly 1 divided by the number of grams of matter composing the Earth. Below the fold we present a strategy that succeeds with probability about .307 (highlight to see probability). (more…)

Lattice points in l^{1} balls

Posted in math.CO, math.NT by Mark Lewko on July 31, 2009

For positive integers {n} and {m}, let {L(n,m)} denote the number of points {x = (x_1, \ldots, x_n) \in \mathbb{Z}^n} such that {\sum_{i=1}^n |x_i| \leq m}.  In other words, {L(n,m)} is the number of lattice points in an n-dimensional l^1-ball of radius mBump, Choi, Kurlberg and Vaaler have observed that the function {L(n,m)} enjoys the following symmetry

\displaystyle {L(n,m) = L(m,n)}

This is to say that the n-dimensional l^1-ball of radius m contains exactly the same number of lattice points as the m-dimensional l^1-ball of radius n.  The original proof follows from establishing the generating function identity

\displaystyle \sum_{n=1}^{\infty}\sum_{m=1}^{\infty}L(m,n)x^m y^n = (1-x-y-xy)^{-1}

and noting that it is symmetric in x and y.  Some time ago Jeff Vaaler mentioned to me that it would be nice to find a bijective proof of this fact.  In this post I will give a simple bijective proof that Allison Bishop and I found. 

(more…)

Tagged with: