# Additive Combinatorics Lecture Notes (part 2)

I finished my additive combinatorics class, and placed all of the lecture notes in the pdf files page. This quarter was rather short and I did not get to do several topics I had in mind. Perhaps I’ll add notes for some of these at some point. For now, let me just list the chapters that did not appear in the previous post.

• Chapter 4 is about arithmetic progressions in dense sets. It includes Behrend’s construction, Meshulam’s theorem, and Roth’s theorem. Due to the recent developments, Meshulam’s theorem already seems somewhat outdated…
• Chapter 5 consists of Sander’s proof of the quasi-polynomial Freiman-Ruzsa theorem in ${\mathbb F}_2^n$ (following Lovett’s presentation). This includes proving a special case of the probabilistic technique of Croot and Sisask.
• Chapter 6 presents the technique of relying on the third moment energy. It then uses this technique to study convex sets. I hope to also add a variant of the Balog-Szemerédi-Gowers theorem.

# An End to the Happy Ending Problem

Andrew Suk just placed on arXiv a paper with an almost tight bound for the happy ending problem. These are exciting news for discrete geometers! I’ll use the opportunity to describe the problem and its non-technical history.

Andrew Suk and the Anonymous statue.

In the early 1930’s in Budapest, several students used to regularly meet on Sundays in a specific city park bench. This was the bench next to the statue of Anonymous, the first medieval Hungarian chronicler. Among these students were Paul Erdős, George Szekeres, and Esther Klein.

On one such Sunday meeting, Klein pointed out that for any set of five points with no three on a line, four of the points are the vertices of a convex quadrilateral. This easy observation can be proved by considering the convex hull of the five points. If at least four of the points are on the boundary of the convex hull, then we are done. If the convex hull consists only of three of the points, then we consider the line $\ell$ that passes through the two interior points. We take the two interior points and the two points that are on the same side of $\ell$.

The Budapest students started to think about whether there exists an $n$ such that every set of $n$ points with no three on a line contains the vertices of a convex pentagon. More generally, does a similar condition hold for every convex $k$-gon? The first to prove the claim was Szekeres. A couple of years later, Esther Klein, who suggested the problem married George Szekeres who solved it. Since then, this problem is called the happy ending problem. They lived together up to their 90’s.

For every integer $m \ge 3$, let $N(m)$ denote the smallest integer such that any set of $N(m)$ points with no three on a line contains a subset of $m$ points that are the vertices of a convex $m$-gon. Erdős and Szekeres published a paper on the problem in 1935. They proved that

$2^{m-2}+1 \le N(m) \le \binom{2m-4}{m-2}+1.$

Erdős and Szekeres conjectured that $N(m)=2^{m-2}+1$, and this is sometimes called “the Erdős–Szekeres conjecture”. Erdős offered a 500$` for proving or disproving this conjecture, and a few years ago Ron Graham (who is handling Erdős’ problem awards) increased the amount to 1000$. So far the conjecture was verified up to $m=6$ by a computer. Over the years several improved bounds were published, but the improvements were always sub-exponential. That is, the value of $N(m)$ remained between $2^m$ and $4^m$ (ignoring sub-exponential factors). In his new paper, Suk derives the impressive bound $N(m)\le 2^{m+4m^{4/5}}$, settling the problem up to sub-exponential factors. Surprisingly, after 81 years of small progress, Suk’s impressive improvement requires a short proof that does not seem to rely on any kind of heavy machinery.

I recently started teaching an “Additive combinatorics” class, and am writing lecture notes for it. So far I put the first three chapters online. I’d appreciate any comments about these, from pointing out serious mistakes, to pointing out minor typos, or even a recommendation for the final topic (which I have not chosen yet). The chapters that are already up are:

• In Chapter 1 we start to study the principle that sets with small doubling must have structure. We prove some basic results such as Ruzsa’s triangle inequality, Plünnecke’s inequality, and variants of Freiman’s theorem.
• Chapter 2 studies the sum-product problem over the reals. In addition to showing the proofs of Elekes and Solymosi, we see how the same techniques can be applied to several other problems.
• Chapter 3 discusses the The Balog-Szemerédi-Gowers theorem. Specifically, we present the variant of Schoen and the variant by Sudakov, Szemerédi, and Vu.

# Distinct Distances for Sets with no Repeated Bisectors

This post is about a distinct distances problem which I think is quite interesting. As we shall see, solving this problem would also lead to significant progress in characterizing point sets with a small number of distinct distances. Recall that a perpendicular bisector of two points $p,q\in {\mathbb R}^2$ is the line that consists of the points $a$ satisfying $|pa|=|qa|$ (where $|pa|$ is the distance between $a$ and $p$). For brevity, we will simply refer to these as bisectors.

We say that a set ${\cal P}$ of $n$ points in ${\mathbb R}^2$ has no repeated bisectors if for every four distinct points $a,b,c,d\in {\cal P}$ the bisector of $a$ and $b$ is not identical to the bisector of $c$ and $d$ (that is, the configuration in the above figure is forbidden).

Conjecture. Let ${\cal P}$ be a set of $n$ points in ${\mathbb R}^2$ with no repeated bisectors. Then for any $\varepsilon>0$ the points of ${\cal P}$ determine $\Omega(n^{2-\varepsilon})$ distinct distances, .

Update July 2017: The conjecture is false, as pointed out by Cosmin Pohoata. A known construction is a counterexample, and I should be ashamed for not observing this on my own. Erdős, Füredi, Pach, and Ruzsa constructed a set of $n$ points in ${\mathbb R}^2$ with $O(n^{1+\varepsilon})$ distinct distances for any $\varepsilon >0$ and no four points on a common circle. Having a repeated bisector requires having four points on a circle, so there are no repeated bisectors. Oh well…

For some initial intuition, consider the point sets that determine a small number of distinct distances. I am only aware of two types of configurations that yield $O(n)$ distinct distances: the vertices of a regular $n$-gon and lattices.

We can also play a bit with these examples. For example, by taking two regular $n$-gons whose vertices are on two concentric circles, or by taking $n$ evenly spaced points on a line (that is, an $n\times 1$ lattice). All of these examples have a significantly large amount of repeated bisectors.

So far I only managed to find a set with no repeated bisectors and $O(\frac{n^2}{\sqrt{\lg n}})$ distinct distances. From the other direction, I can only show that every such set determines $\Omega(n)$ distinct distances. This is unfortunate, since a stronger bound for this problem would lead to a breakthrough in characterizing planar point sets that determine a small number of distinct distances. Below I describe how this can be done, and also how to obtain simple lower and upper bounds for this problem.

# Incidences Outside of Discrete Geometry

Starting the 1980’s, more and more applications of geometric incidences have been found in discrete geometry. By now, one can arguably claim that there are countless such applications. More surprising are the applications of incidences outside of discrete geometry. In the past decade such applications have been discovered in harmonic analysis, theoretical computer science, number theory, and more. This post is my attempt to list these applications. If you are familiar with additional applications that I did not include, I’d be very interested to hear about them (in the comments below or by email).

Additive combinatorics: One of the main milestones in the study of the sum-product problem is a seminal paper by Elekes, in which he reduced the problem to a point-line incidence problem in ${\mathbb R}^2$. This led to a variety of results in additive combinatorics that rely on incidences. Tao and Vu’s additive combinatorics book contains a full chapter that is dedicated to incidences. Konyagin and Shkredov’s recent improvement of the sum-product bound also relies indirectly on incidences (to bound the number of collinear triples in a lattice). For more examples, see here and here. Also, several additive combinatorics results in finite fields rely on incidence bounds in finite fields (e.g., see this paper).

Fourier restriction problems: Bourgain and Demeter rely on incidences to derive bounds for the discrete Fourier restriction to the four and five dimensional spheres. Incidences also appear in several related papers by the same authors (e.g., see here and here).

Number theory: A recent paper of Bombieri and Bourgain studies a type of additive energy of the Gaussian integers by relying on incidences with unit circles in ${\mathbb R}^2$.

Error correcting codes: A family of papers by Dvir, Saraf, Wigderson, and others use incidences to study error correcting codes. For example, see this paper and this paper. These papers rely mainly on Sylvester-Gallai problems, which do not exactly fit the standard incidence problem formulation. Still, the authors of these paper and others consider these as proper incidence problems.

Extractors: Yet another novel use of incidences by Jean Bourgain. Bourgain relied on a finite field point-line incidence bound to build 2-source extractors. Recently this result has been superseded, as far as I understand without relying on incidences in any way.

Minors of totally positive matrices: Farber, Ray, and Smorodinsky used incidences to bound the number of times that a $d\times d$ minor can repeat in $d\times n$ a totally positive matrix.

It might also be interesting to state results that do not rely on incidences but do rely on the same polynomial partitioning technique (applied in the same way):

More restriction problems: Guth recently relied on polynomial partitioning to derive improved restriction estimates for smooth compact surface in ${\mathbb R}^3$ with strictly positive second fundamental form.

Range searching algorithms: Agarwal, Matoušek,and Sharir used polynomial partitioning to derive range searching algorithms for semialgebraic sets. A later simplification of this result, also based on polynomial partitioning, was derived by Matoušek and Patáková.

# Incidences: Lower Bounds (part 8)

We continue to survey the known lower bounds for incidence problems (the previous post in this series can be found here). After a couple of posts in ${\mathbb R}^3$ we now return to ${\mathbb R}^2$, to introduce a new technique that I recently learned about. This technique was discovered by Jozsef Solymosi, and is described in a work of Solymosi and Endre Szabó that is unpublished at this point. As seems to often be the case with results of Solymosi, it is quite simple and elegent. In ${\mathbb R}^2$ this technique yields bounds that can also be obtained from Elekes’ technique (discussed in a previous post), but in higher dimensions it leads to new bounds that are also tight (which would hopefully discuss in a future post). I would like to thank Jozsef Solymosi for allowing me to describe his technique in this blog, and to Frank de Zeeuw for discussions that led to this post.

Jozsef Solymosi.

# A Boxes Riddle

I just recalled a nice mathematical riddle. I can’t remember where I originally read it, but it was likely in one of the blogs that are in the blogroll to the right.

Riddle. A game takes place where person A and person B are on the same team while person Z is their adversary. There are 100 boxes and 100 notes containing the numbers 1 to 100 (that is, each number is on exactly one note). The game goes as follows:

• First, only Z and A are in the room. Z places one note in each box.
• A sees the actions of Z and may afterwards pick two boxes and switch the notes in them (with each other). He may only perform one such switch.
• Z sees the actions of A and then chooses a number N between 1 and 100.
• A leaves the room while B enters it (they cannot exchange information during this process). Z tells B the number N.
• Finally, B needs to find the box that contains the note with the number N. For this purpose, B may open up to 50 boxes.
If A chooses the 50 boxes at random, his probability of success is obviously 0.5. Do A and B have a strategy for increasing their chances? Or does Z have a strategy for which 0.5 is the best possible?

Feel free to write the answer as a comment. However, I think that it would be nice not to provide a full explanation here (that is, only to write whether it’s 0.5 or what better probability you can get).

(Later edit: I seem to be getting senile! I just noticed that I wrote the same riddle in a post two years ago…)