The Eberhard-Green-Manners Sum-free Subset Theorem, and `What is Sum-free(13)?’
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 . 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 such that
.
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 (for
) due to Bourgain (1995) using Fourier analysis. It seems likely that there is a function
such that one may take
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
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
and that Klarner improved this to
. In 1990 Alon and Kleitman improved this further to
, and Malouf in her thesis (as well as Furedi) improved this further to
. A couple years ago I improved this to
(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
(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
, 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 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 define the sum-free subset number Sum-free
to be the largest number such that every set of
natural numbers is guaranteed to contain a sum-free subset of size at least Sum-free
.
Thus by Bourgain’s theorem we have that Sum-free (and the Eberhard-Green-Manners theorem states Sum-free
). It turns out that Bourgain’s result is sharp for sets of size
and smaller. However, Bourgain’s theorem only tells us that a set of size
must contain a sum-free subset of size
while it seems likely (from computer calculations) that every set of size
must in fact contain a sum-free subset of size
. Indeed, I’ll even
Conjecture: Sum-free.
While the asymptotic lower bound problem (showing that there ) 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
sum-free subset numbers.
Bourgain’s lower bound on Sum-free |
Best known upper bound on Sum-free |
Upper bound set example | |
1 | 1 | 1 | |
2 | 1 | 1 | |
3 | 2 | 2 | |
4 | 3 | 3 | |
5 | 3 | 3 | |
6 | 3 | 3 | |
7 | 3 | 3 | |
8 | 4 | 4 | |
9 | 4 | 4 | |
10 | 4 | 4 | |
11 | 5 | 5 | |
12 | 5 | 5 | |
13 | 5 | 6 | |
14 | 6 | 6 | |
15 | 6 | 7 |
An Exact Asymptotic for the Square Variation of Partial Sum Processes
Allison and I just arxiv’ed our paper An Exact Asymptotic for the Square Variation of Partial Sum Processes.
Let be a sequence of independent, identically distributed random variables with mean
. The strong law of large numbers asserts that
almost surely. Without loss of generality, one can assume that are mean-zero by defining
. If we further assume a finite variance, that is
, the Hartman-Wintner law of the iterated logarithm gives an exact error estimate for the strong law of large numbers. More precisely,
where the constant can not be replaced by a smaller constant. That is, the quantity
gets as large/small as
infinitely often. The purpose of our current work is to prove a more delicate variational asymptotic that refines the law of the iterated logarithm and captures more subtle information about the oscillations of a sums of i.i.d random variables about its expected value. More precisely,
Theorem Let be a sequence of independent, identically distributed mean zero random variables with variance
and satisfying
. If we let
denote the set of all possible partitions of the interval
into subintervals, then we have almost surely:
.
Choosing the partition , to contain a single interval
immediately recovers the upper bound in the law of the iterated logarithm. This result also strengthens earlier work of J. Qian.
An interesting problem left by this work is deciding if the moment condition can be removed. Without an auxiliary moment condition we are able to establish the following weaker `in probability’ result.
Theorem Let be a sequence of independent, identically distributed mean zero random variables with finite variance
. We then have that
The millennium problems and football
From a discussion thread on CNN’s story Footballer: ‘Are you OK with destroying a kid’s brain for this game?’:
How to leak on key updates
Leakage resilient cryptography is an exciting area of cryptography that aims to build cryptosystems that provide security against side channel attacks. In this post I will give a nontechnical description of a common leakage resilient security model, as well as describe a recent paper in the area with Allison Lewko and Brent Waters, titled “How to Leak on Key Updates”.
Review of Public Key Encryption
Let us (informally) recall the definition of a public key cryptography system. Alice would like to send Bob a private message over an unsecured channel. Alice and Bob have never met before and we assume they do not share any secret information. Ideally, we would like a procedure where 1) Alice and Bob engage in a series of communications resulting in Bob learning the message
2) an eavesdropper, Eve, who intercepts all of the communications sent between Alice and Bob, should not learn any (nontrivial) information about the message
. As stated, the problem is information theoretically impossible. However, this problem is classically solved under the heading of public key cryptography if we further assume that:
1) Eve has limited computational resources,
2) certain computational problems (such as factoring large integers or computing discrete logarithms in a finite group) are not efficiently solvable, and
3) we allow Alice and Bob to use randomization (and permit security to fail with very small probability).
More specifically, a public key protocol works as follows: Bob generates a private and public key, say and
respectively. As indicated by the names,
is publicly known but Bob retains
as secret information. When Alice wishes to send a message
to Bob she generates an encrypted ciphertext
using the message
, Bob’s public key
and some randomness. She then sends this ciphertext to Bob via the public channel. When Bob receives the ciphertext he decrypts it using his secret key
and recovers
. While Eve has access to the ciphertext
and the secret key
, she is unable to learn any nontrivial information about the message
(assuming our assumptions are sound). In fact, we require a bit more: even if this is repeated many times (with fixed keys), Eve’s ability to decrypt the ciphertext does not meaningfully improve.
Leakage Resilient Cryptography and our work
In practice, however, Eve may be able to learn information in addition to what she intercepts over Alice and Bob’s public communications via side channel attacks. Such attacks might include measuring the amount of time or energy Bob uses to carry out computations. The field of leakage resilient cryptography aims to incorporate protection against such attacks into the the security model. In this model, in addition to the ciphertext and public key, we let Eve select a (efficiently computable) function where
is the bit length of
and
is a constant. We now assume, in addition to
and
, Eve also gets to see
. In other words, Eve gains a fair amount of information about the secret key, but not enough to fully determine it.
Moreover, we allow Eve to specify a different function every time Alice sends Bob a message. There is an obvious problem now, however. If the secret key
remained static, then Eve could start by choosing
to output the first
bits, the second time she could choose
to give the next
bits, and if she carries on like this, after
messages she would have recovered the entire secret key. To compensate for this we allow Bob to update his secret key between messages. The public key will remain the same.
There has been a lot of interesting work on this problem. In the works of Brakerski, Kalai, Katz, and Vaikuntanathan and Dodis, Haralambiev, Lopez-Alt, and Wichs many schemes are presented that are provably secure against continual leakage. In these schemes, however, information about the secret key is permitted to be leaked between updates, but only a tiny amount is allowed to be leaked during the update process itself.
In our current work, we offer the first scheme that allows a constant fraction of the information used in the update to be leaked. The proof is based on subgroup decision assumptions in composite order bilinear groups.
Adam Smith on mathematicians (circa 1759)
I recently came across the following passage regarding the mathematical profession from Adam Smith’s influential work The Theory of Moral Sentiments that I thought others might find interesting:
Mathematicians, on the contrary, who may have the most perfect assurance, both of the truth and of the importance of their discoveries, are frequently very indifferent about the reception which they may meet with from the public. The two greatest mathematicians that I ever have had the honour to be known to, and, I believe, the two greatest that have lived in my time, Dr Robert Simpson of Glasgow, and Dr Matthew Stewart of Edinburgh, never seemed to feel even the slightest uneasiness from the neglect with which the ignorance of the public received some of their most valuable works. The great work of Sir Isaac Newton, his Mathematical Principles of Natural Philosophy, I have been told, was for several years neglected by the public. The tranquillity of that great man, it is probable, never suffered, upon that account, the interruption of a single quarter of an hour. Natural philosophers, in their independency upon the public opinion, approach nearly to mathematicians, and, in their judgments concerning the merit of their own discoveries and observations, enjoy some degree of the same security and tranquillity.
The morals of those different classes of men of letters are, perhaps, sometimes somewhat affected by this very great difference in their situation with regard to the public.
Mathematicians and natural philosophers, from their independency upon the public opinion, have little temptation to form themselves into factions and cabals, either for the support of their own reputation, or for the depression of that of their rivals. They are almost always men of the most amiable simplicity of manners, who live in good harmony with one another, are the friends of one another’s reputation, enter into no intrigue in order to secure the public applause, but are pleased when their works are approved of, without being either much vexed or very angry when they are neglected.
The entire text is available here.
Restriction estimates for the paraboloid over finite fields
Allison and I recently completed a paper titled Restriction estimates for the paraboloid over finite fields. In this note we obtain some endpoint restriction estimates for the paraboloid over finite fields.
Let denote a hypersurface in
with surface measure
. The restriction problem for
is to determine for which pairs of
does there exist an inequality of the form
We note that the left-hand side is not necessarily well-defined since we have restricted the function to the hypersurface
, a set of measure zero in
. However, if we can establish this inequality for all Schwartz functions
, then the operator that restricts
to
(denoted by
), can be defined whenever
. In the Euclidean setting, the restriction problem has been extensively studied when
is a sphere, paraboloid, and cone. In particular, it has been observed that restriction estimates are intimately connected to questions about certain partial differential equations as well as problems in geometric measure theory such as the Kakeya conjecture. The restriction conjecture states sufficient conditions on
for the above inequality to hold. In the case of the sphere and paraboloid, the question is open in dimensions three and higher.
In 2002 Mockenhaupt and Tao initiated the study of the restriction phenomena in the finite field setting. Let us introduce some notation to formally define the problem in this setting. We let denote a finite field of characteristic
. We let
denote the unit circle in
and define
to be a non-principal character of
. For example, when
, we can set
. We will be considering the vector space
and its dual space
. We can think of
as endowed with the counting measure
which assigns mass 1 to each point and
as endowed with the normalized counting measure
which assigns mass
to each point (where
denotes the size of
, so the total mass is equal to 1 here).
For a complex-valued function on
, we define its Fourier transform
on
by:
For a complex-valued function on
, we define its inverse Fourier transform
on
by:
It is easy to verify that and
.
We define the paraboloid as:
. This is endowed with the normalized “surface measure”
which assigns mass
to each point in
. We note that
.
For a function , we define the function
as follows:
For a complex-valued function on
and
, we define
For a complex-valued function on
, we similarly define
Now we define a restriction inequality to be an inequality of the form
where denotes the best constant such that the above inequality holds. By duality, this is equivalent to the following extension estimate:
We will use the notation to denote that quantity
is at most a constant times quantity
, where this constant may depend on the dimension
but not on the field size,
. For a finite field
, the constant
will always be finite. The restriction problem in this setting is to determine for which
can we upper bound
independently of
(i.e. for which
does
hold).
Mockenhaupt and Tao solved this problem for the paraboloid in two dimensions. In three dimensions, we require not be a square in
(without this restriction the parabaloid will contain non-trivial subspaces which lead to trivial counterexamples, but we will not elaborate on this here). For such
, they showed that
and
for every
. When
, their bounds were polylogarithmic in
. Mockenhaupt and Tao’s argument for the
estimate proceeded by first establishing the estimate for characteristic functions. Here one can expand the
norm and reduce the problem to combinatorial estimates. A well-known dyadic pigeonhole argument then allows one to pass back to general functions at the expense of a logarithmic power of
. Following a similar approach (but requiring much more delicate Gauss sum estimates), Iosevich and Koh proved that
and
in higher dimensions (in odd dimensions some additional restrictions on
are required). Again, however, this argument incurred a logarithmic loss at the endpoints from the dyadic pigeonhole argument.
In this note we remove the logarithmic losses mentioned above. Our argument begins by rewriting the norm as
. We then adapt the arguments of the prior papers to the bilinear variant
in the case that
and
are characteristic functions.
To obtain estimates for arbitrary functions , we can assume that
is non-negative real-valued and decompose
as a linear combination of characteristic functions, where the coefficients are negative powers of two (we can do this without loss of generality by adjusting only the constant of our bound). We can then employ the triangle inequality to upper bound
by a double sum of terms like
, where
and
are characteristic functions, weighted by negative powers of two. We then apply our bilinear estimate for characteristic functions to these inner terms and use standard bounds on sums to obtain the final estimates.
Our method yields the following theorems:
Theorem For the paraboloid in dimensions with
not a square, we have
and
.
Theorem For the paraboloid in dimensions when
is even or when
is odd and
for a prime
congruent to 3 modulo 4 such that
is not a multiple of 4, we have
and
.
We recently learned that in unpublished work Bennett, Carbery, Garrigos, and Wright have also obtained the results in the -dimensional case. Their argument proceeds rather differently than ours and it is unclear (at least to me) if their argument can be extended to the higher dimensional settings.
An improved upper bound for the sum-free subset constant
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 is sum-free if there is no solution to the equation
with
. The following is a well-known theorem of Erdős.
Theorem Let be a finite set of natural numbers. There exists a sum-free subset
such that
.
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 . Bourgain has improved this further, showing that the conclusion can be strengthened to
. 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
cannot be replaced by a larger constant, however this is an open problem. In Erdős’ 1965 paper, he showed that the constant
could not be replaced by a number greater than
by considering the set
. In 1990, Alon and Kleitman improved this to
. In a recent survey of open problems in combinatorics, it is reported that Malouf has shown the constant cannot be greater than
. While we have not seen Malouf’s proof, we note that this can be established by considering the set
. In this note we further improve on these results by showing that the optimal constant cannot be greater than
.
Sets of large doubling and a question of Rudin
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 set of density
. Hence, the construction of a
set that doesn’t contain a large
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 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 sets —
Before describing the problem we will need some notation. Let and define
to be the number of unordered solutions to the equation
with
. We say that
is a
set if
for all
. 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
. For
we define
to be the number of solutions to the equation
with
. If
for all nonzero
we say that
is a
set.
Let be a subset of the integers
, and call
an
-polynomial if it is a trigonometric polynomial whose Fourier coefficients are supported on
(i.e.
if
). We say that
is a
set (for
) if
holds for all -polynomials where the constant
only depends on
and
. If
is an even integer, we can expand out the
norm in 1. This quickly leads to the following observation: If
is a
set then
is also an
set (
,
). One can also easily show using the triangle inequality that the union of two
sets is also a
set. It follows that the finite union of
sets is a
set. In 1960 Rudin asked the following natural question: Is every
set is a finite union of
sets?
In this paper we show that the answer is no in the case of sets. In fact, we show a bit more than this. One can easily show that a
set is also a
set. Our first counterexample to Rudin’s question proceeded (essentially) by constructing a
set which wasn’t the finite union of
sets. This however raised the following variant of Rudin’s question: Is every
set the mixed finite union of
and
sets? We show that the answer to this question is no as well. To do this we construct a
set, A, which isn’t a finite union of
sets, and a
set,
, which isn’t the finite union of
sets. We then consider the product set
which one can prove is a
subset of
. It isn’t hard to deduce from this that
is a
subset of
that isn’t a mixed finite union of
and
sets. Moreover, one can (essentially) map this example back to
while preserving all of the properties stated above. Generalizing this further, we show that there exists a
set that doesn’t contain (in a sense that can be made precise) a large
or
. 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 sets for
. 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
fraction of errors. To modify this construction (at least in a direct manner) to address the problem for, say,
sets it appears one would need arbitrary large binary codes that can correct strictly more than a
fraction of errors. However, one can show that such objects do not exist.
— Is there an anti-Freiman theorem? —
Let be a finite set of integers and denote the sumset of
as
. A trivial inequality is the following
In fact, it isn’t hard to show that equality only occurs on the left if is an arithmetic progression and only occurs on the right if
is a
set. A celebrated theorem of Freiman states that if
then
is approximately an arithmetic progression. More precisely, if
is a finite set
satisfying
for some constant
, then
is contained in a generalized arithmetic progression of dimension
and size
where
and
depend only on
and not on
.
It is natural to ask about the opposite extreme: if , what can one say about the structure of
as a function only of
? A first attempt might be to guess that if
for some positive constant
, then
can be decomposed into a union of
sets where
and
depend only on
. This is easily shown to be false. For example, one can start with a
of
elements contained in the interval
and take its union with the arithmetic progression
. It is easy to see that
regardless of
. However, the interval
cannot be decomposed as the union of
sets with
and
independent of
.
There are two ways one might try to fix this problem: first, we might ask only that contains a
set of size
, where
and
depend only on
. (This formulation was posed as an open problem by O’Bryant here). Second, we might ask that
hold for all subsets
for the same value of
. 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
where
holds for all of their subsets for the same value of
, but if we try to locate a
set,
, of density
in
then
must tend to infinity with the size of
. As above, our initial construction of such a sequence of
‘s turned out to be
sets. This leads us to the even weaker anti-Freiman conjecture:
(Weak Anti-Freiman) Suppose that satisfies
and
for all subsets
. Then
contains either a
set or a
set of size
, where
and
depend only on
.
We conclude by showing that even this weaker conjecture fails. The constructions are the same as those used in the results above. The two problems are connected by the elementary observation that if
is a subset of a
set
then
holds where
only depends on the
constant
of the set
.
— A variant of the Erdös-Newman conjecture —
In the early 1980’s Erdös and Newman independently made the following conjecture: For every there exists a
that isn’t a finite union of
sets for any
. This conjecture was later confirmed by Erdös for certain values of
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
reversed.
Theorem 1 For every there exists a union of
sets that isn’t a finite union of
sets for any
.
The dense model theorem
A key component in the work of Green, Tao, and Ziegler on arithmetic and polynomial progressions in the primes is the dense model theorem. Roughly speaking this theorem allows one to model a dense subset of a sparse pseudorandom set by dense subset of the the ambient space. In the work of Green, Tao, and Zeigler this enabled them to model (essentially) the characteristic function of the set of primes with (essentially) the characteristic function of a set of integers with greater density. They then were able to obtain the existence of certain structures in the model set via Szemerédi’s theorem and its generalizations.
More recently, simplified proofs of the dense model theorem have been obtained independently by Gowers and Reingold, Trevisan, Tulsiani and Vadhan. In addition, the latter group has found applications of these ideas in theoretical computer science. In this post we give an expository proof of the dense model theorem, substantially following the paper of Reingold, Trevisan, Tulsiani and Vadhan.
With the exception of the min-max theorem from game theory (which can be replaced by (or proved by) the Hahn-Banach theorem, as in Gowers’ approach) the presentation is self-contained.
(We note that the the theorem, as presented below, isn’t explictly stated in the Green-Tao paper. Roughly speaking, these ideas can be used to simplify/replace sections 7 and 8 of that paper.) (more…)
Halstead has a home!
Two weeks ago, not far from the UT math department, I found (or rather I was found by) a very friendly stray dog (pictured below). Since it was raining and the nearby streets were busy, I fed the dog and then brought it to Austin’s Town Lake animal shelter. The next day I called the shelter to learn that if the dog wasn’t adopted within three days it would likely be euthanized. With the help of several other members of the UT mathematical community, dozens of emails, phone calls, and Internet postings were made in an effort to find the pup a home. (In fact, the mathematical blogsphere was represented in these efforts.) (more…)
7 comments