# Joints tightened

I’m happy to announce a new paper titled Joints tightened coauthored with Hung-Hsun Hans Yu, an undergraduate student at MIT. In this paper, we determine the tight constant in the joints problem.

The joints problem is a classic problem in incidence geometry. A typical question in incidence geometry concerns what kinds of configurations can be built using just points and lines.

Suppose you are allowed to draw L lines in space. What is the maximum possible number of points that lie on three lines (let’s call these points “triple intersections” for now)?

It turns out this is not a great question, since you can “cheat” by drawing a 2-dimensional picture from a grid as below. This configuration of L lines has $\Theta(L^2)$ triple intersections, and you cannot do much better since L lines have at most $L^2$ intersections.

The issue with the above example is that it is really a 2-dimensional configuration, whereas we really want to ask a 3-dimensional question. One way to make the problem much more interesting is only count “truly 3-dimensional” intersection points.

Given a collection of lines in space, we define a joint to be a point that is contained in three of our lines and not all lying on the same plane.

Joints problem. What is the maximum number of joints that can be formed by L lines in 3-dimensional space?

The joints problem was raised in early 1990’s, and it turned out to be a very interesting problem! Besides its intrinsic interest as a combinatorial geometry problem, it also caught the attention of analysts as the joints problem is connected to the Kakeya problem, a central problem in analysis (this connection was popularized by Wolff).

Here are some examples of configurations of lines that have a lot of joints.

Example 1. The easiest example to visualize is by considering a k × k × k grid of lines, which has $L = 3k^2$ lines and $J = k^3 = (L/3)^{3/2}$ joints:

Example 2. Actually, there is another example that has even more joints (by a constant factor). Think about a tetrahedron, formed by 4 faces (planes), and whose edges form 6 lines, and the vertices form 4 joints. We can generalize the tetrahedron example by taking k generic planes in space, and have the planes pairwise intersect to make $L = \binom{k}{2}$ lines, and triplewise intersect to make $J = \binom{k}{3}$ joints. (This example appeared in the original paper on the joints problem.)

In both examples, the number of joints is $\Theta(L^{3/2})$. A matching upper bound on the number of joints turned out to be much less obvious. A stunning breakthrough took place in 2008 when Guth and Katz proved an $O(L^{3/2})$ upper bound on the number of joints in using the polynomial method. Their solution was partly inspired by Dvir’s stunning solution to the finite field Kakeya problem, and it was also a precursor to Guth and Katz’s subsequent celebrated solution of the Erdős distinct distances problem.

Larry Guth conjectured in his book The Polynomial Methods in Combinatorics that the second example above is best possible. I first learned about this very nice conjecture as a graduate student in Guth’s class on the polynomial method.

The main result of our paper is a new improved upper bound on the joints problem, matching the constant in the second example above. More precisely, we prove that L lines in space make at most $\frac{\sqrt{2}}{3}L^{3/2}$ joints, thereby confirming Guth’s conjecture up to a 1+o(1) factor. Our results also hold in arbitrary dimensions and over arbitrary fields.

It was quite unexpected to us that such a tight bound can even be proved, especially given how long it took just to obtain an upper bound of the right order of magnitude on the joints problem. In pretty much all other classical problems in incidence geometry (i.e., the Szemerédi–Trotter theorem), the optimal constant factor is not known. In fact, our result might be the first one in incidence geometry that obtains a tight constant factor.

# Equiangular lines with a fixed angle

I’m happy to announce our new paper Equiangular lines with a fixed angle joint with four MIT coauthors: Zilin Jiang, Jonathan Tidor, Yuan Yao, and Shengtong Zhang.

Zilin is an Instructor (postdoc), Jonathan is my PhD student who just finished his second year, and Yuan and Shengtong are undergraduates who just finished their second and first respective years.

Our paper solves a longstanding problem in discrete geometry concerning equiangular lines, which are configurations of lines in space that are pairwise separated by the same angle. How many such lines can exist simultaneously in a given dimension?

We determine, for every fixed angle, the maximum number of equiangular lines with the given angle in high dimensions.

Our paper builds on a long sequence of earlier ideas. There were some important progress on this problem by Igor Balla, Felix Dräxler, Peter Keevash, and Benny Sudakov, as featured in this earlier Quanta Magazine article written for a lay audience.

In the end we finished off the problem in a clean and crisp manner, in a 10-page paper with a self-contained proof.

It has been known that the study of equiangular lines is closed linked to spectral graph theory, which seeks to understand graphs via their spectrum (i.e., eigenvalues). We prove our main result via a new insight in spectral graph theory, namely that a bounded degree graph must have sublinear second eigenvalue multiplicity.

# Impartial digraphs

I just finished a new paper, Impartial digraphs, coauthored with Yunkun Zhou, who just completed his undergraduate studies at MIT and will be moving to Stanford to start his PhD this fall.

The problem (along with the conjecture that we proved) was proposed by Jacob Fox, Hao Huang, and Choongbum Lee. Ron Graham had also told me about this problem with much enthusiasm during tea time one afternoon at the Berkeley Simons Institute a couple of years ago, after learning about it from Jacob.

I really enjoyed working on this paper with Yunkun. The problem is natural and simple to state, the answer appears somewhat unexpected (at least initially), and the solution ended up being quite tricky yet clean, employing a variety of tools in combinatorics, ranging from analytic methods (graph limits), algebraic considerations (polynomial identities and factorization), as well basic combinatorial techniques such as bijections.

We are going to talk about directed graphs (which graph theorists like to abbreviate as digraphs). These are graphs where every edge is given an orientation.

A tournament is a directed graph where there is a directed edge between every pair of vertices (think of it as recording the outcome of a round-robin tournament where every player plays against every other player).

Given a directed graph H (think of it as a pattern), we can ask: how many different copies of the pattern H appear in a given tournament?

Look at the following 4-vertex tournament H. It has the following curious property: all tournaments of a fixed size contains the same number of copies of H, no matter how the edges in the tournament are oriented.

Hmm, why is this true? And are there other directed graphs H with the same property, namely that all tournaments of a given size contain the same number of copies of H?

In the good old mathematical tradition, we came up with a name for directed graphs H with this curious property: we called them impartial (as in: impartial judges of a tournament).

Okay. So why is the above directed graph impartial? Are there any other impartial directed graphs? What are all the impartial directed graphs?

Here is a simple example of an impartial digraph:

Here is another one:

Indeed, given any 10-vertex tournament, we can count the number of copies of the first edge (it doesn’t depend on the tournament), and then count the number of copies of the second edge among the remaining 8 vertices (it still doesn’t depend on the tournament).

Once these two edges are placed in a tournament, there are two ways to join their tips, but they result in identical patterns (one flipped from the other):

It must then follow that this directed graph is impartial as well:

We can follow the same logic and continue this procedure, iterate, and build up even larger impartial directed graphs. Each step, take two copies of the previous tree (keeping the same edge orientations), and then add a new edge between a twin pair of vertices.

We call any directed graph that can building up as above a recursively bridge-mirrored tree.

The same argument as earlier shows that every recursively bridge-mirrored tree is impartial.

Are there other impartial digraphs? Did we miss any?

It turns out, there are actually no others. We have found them all, and that is the main result of our paper:

Theorem. A directed graph is impartial if and only if every component is recursively bridge-mirrored trees.

Just a word about how about this problem is related to a bigger picture. It is related to a number of other graph homomorphism inequalities that are central in extremal graph theory. It can be considered as the “equality case” for a directed analog of an open problem known as Sidorenko’s conjecture. See our paper for some further discussions and open problems.

# A reverse Sidorenko inequality

Together with undergraduates Ashwin Sah, Mehtaab Sawhney, and David Stoner (the same team that proved Kahn’s conjecture on independent sets that I blogged about earlier), we are excited to announce our new paper A reverse Sidorenko inequality. This paper solves several open problems concerning graph colorings and homomorphisms, including one of my favorite problems regarding maximizing the number of q-colorings in a d-regular graph. I had previously blogged about some of these problems.

It has been truly a pleasure working with Ashwin, Mehtaab, and David on this project. I have learned so much from them.

Here are some highlights of our new results.

1. Graph colorings. Among d-regular graphs, which graph has the most number of proper q-colorings, exponentially normalized by the number of vertices of G?

We show that the extremal graph is the complete bipartite graph Kd,d (or disjoint unions thereof, as taking disjoint copies does not change the quantity due to the normalization).

2. Graph homomorphisms. Among d-regular graphs, which triangle-free graph G has the most number of homomorphisms into a fixed H, again exponentially normalized by the number of vertices of G?

We show that the extremal graph G is the complete bipartite graph Kd,d.

The triangle-free hypothesis on G is best possible in general. For certain specific H, such as Kq, corresponding to proper q-colorings as earlier, the triangle-free hypothesis can be dropped. It remains a wide open problem to determine for which H can one drop the triangle-free hypothesis on G.

3. Partition functions of Ferromagnetic spin models. Among d-regular graphs, which graph maximizes the log-partition function per vertex of a given Ferromagnetic spin model (e.g., Ising model)?

We show that the extremal graph is the clique Kd+1.

For each setting, we establish our results more generally for irregular graphs as well, similar to our earlier work on independent sets.

Our results can be interpreted as a reverse form of the inequality in Sidorenko’s conjecture, an important open problem in graph theory stating a certain positive correlation on two-variable functions.

One can also view our results as a graphical analog of the Brascamp-Lieb inequalities, a central result in analysis.

This paper resolves one of my favorite open problems on this topic (the number of graph colorings). It also points us to many other open problems. Let me conclude by highlighting one of them (mentioned in #2 earlier). I’ll state it in a simpler form for d-regular graphs, but it can be stated more generally as well.

Open problem. Classify all H with the following property: among d-regular graphs G, the number of homomorphisms from G to H, exponentially normalized by the number of vertices of G, is maximized by GKd,d.

Our results show that HKq works, even when some of its vertices are looped. Generalizing this case, we conjecture that all antiferromagnetic models H have the same property (though we know that this would not be the complete class, even if true).

# The number of independent sets in an irregular graph

I am excited to announce our new paper, The number of independent sets in an irregular graph, coauthored with these three amazing collaborators:

Ashwin is a freshman at MIT, Mehtaab is a sophomore at MIT, and David is a junior at Harvard.

The paper solves a conjecture made by Jeff Kahn in 2001 concerning the number of independent sets in a graph.

An independent set of a graph is a subset of vertices with no two adjacent. For example, here is the complete list of independent sets of a cycle of length 4: Since many problems in combinatorics can be naturally phrased in terms of independent sets in a graph or hypergraph, getting good bounds on the number of independent sets is a problem of central importance.

Instead of giving the exact statement of the conjecture (now theorem), which you can find in the abstract of our paper, let me highlight a specific instance of a problem addressed by the theorem:

Consider the family of graphs with no isolated vertices and

• exactly a third of the edges have degree 3 on both endpoints, and
• a third of the edges have degree 4 on both endpoints,
• the remaining third of the edges have degree 3 on one endpoint and degree 4 on the other endpoint.

What is the smallest constant ${c}$ such that every ${n}$-vertex graph satisfying the above properties has at most ${c^n}$ independent sets?

In other words, letting ${i(G)}$ denote the number of independent sets and ${v(G)}$ the number of vertices of ${G}$, maximize the quantity ${i(G)^{1/v(G)}}$ over all graphs ${G}$ in the above family.

(See the end of this post for the answer)

In summer 2009, as an undergraduate participating in the wonderful Research Experience for Undergraduates (REU) run by Joe Gallian in Duluth, MN, I learned about Kahn’s conjecture (somewhat accidentally actually, as I was working on a different problem that eventually needed some bounds on the number of independent sets, and so I looked up the literature and learned, slightly frustratingly at the time, that it was an open problem). It was on this problem that I had written one of my very first math research papers.

I had been thinking about this problem on and off since then. A couple years ago, Joe Gallian invited me to write an article for a special issue of the American Mathematical Monthly dedicated to undergraduate research (see my previous blog post on this article), where I described old and new developments on the problem and collected a long list of open problems and conjectures on the topic (one of them being Kahn’s conjecture).

This spring, I had the privilege with working with Ashwin, Mehtaab, and David, three energetic and fearless undergraduate students, finally turning Kahn’s conjecture into a theorem. Fearless indeed, as our proof ended up involving quite a formidable amount of computation (especially for such an innocent looking problem), and my three coauthors deserve credit for doing the heavy-lifting. I’ve been told that there had been many late night marathon sessions in an MIT Building 2 classroom where they tore apart one inequality after another.

This is certainly not the end of the story, as many more interesting problems on the subject remain unsolved—my favorite one being the analogous problem for colorings, e.g., instead of counting the number of independent sets, how about we count the number of ways to color the vertices of the graph with 3 colors so that no two adjacent vertices receive the same color? (See my previous blog post for some more discussion.)

Anyway, here is the the answer to the question above. The number of independent sets in an ${n}$-vertex graph satisfying the above properties is at most ${c^n}$, where the optimal constant for ${c}$ is ${15^{4/63}\times 23^{1/21} \times 31^{1/28}=1.558\dots}$, or, more helpfully, the maximum is attained by the following graph (in general, the theorem says that the maximizer is always a disjoint union of complete bipartite graphs): # Extremal regular graphs

This post is adapted from my new expository survey Extremal regular graphs: independent sets and graph homomorphisms.

The earliest result in extremal graph theory is usually credited to Mantel, who proved, in 1907, that a graph on ${n}$ vertices with no triangles contains at most ${n^2/4}$ edges, where the maximum is achieved for a complete bipartite graph with half of the vertices on one side and half on the other side. Much more is now known about the subject. While I initially encountered Mantel’s theorem as a high school student preparing for math contests, my first in-depth exposure to extremal graph theory was from taking a course by David Conlon during my year reading Part III at Cambridge (one can find excellent course notes on his website).

We seem to know less about sparse graphs (a general mantra in combinatorics, it seems). Let us focus on ${d}$-regular graphs, which are graphs where every vertex has degree ${d}$. The cycle of length 4 has a total of 7 independent sets.

An independent set in a graph is a subset of vertices with no two adjacent. Many combinatorial problems can be reformulated in terms of independent sets by setting up a graph where edges represent forbidden relations.

Question. In the family of ${d}$-regular graph of the same size, which graph has the most number of independent sets?

This question was raised by Andrew Granville in the 1988 Number Theory Conference at Banff, in an effort to resolve a problem in combinatorial number theory, namely the Cameron–-Erdős conjecture on the number of sum-free sets. The question appeared first in print in a paper by Noga Alon, who proved an asymptotic upper bound and speculated that, at least when ${n}$ is divisible by ${2d}$, the maximum should be attained by a disjoint union of complete bipartite graphs ${K_{d,d}}$.

Some ten years later, Jeff Kahn arrived at the same conjecture while studying a problem arising from statistical physics. Using a beautiful entropy argument, Kahn proved the conjecture under the additional assumption that the graph is already bipartite.

Fast forward another nearly ten years. In the summer of 2009, during my last summer as an undergraduate, I spent a fun and productive summer attending Joe Gallian’s REU in Duluth, MN (a fantastic program, by the way!), and there I showed that Kahn’s theorem can be extended to all regular graphs, not just bipartite ones.

Here is the theorem statement. We write ${I(G)}$ to denote the set of independent sets in ${G}$, and ${i(G) := |I(G)|}$ the number of independent sets in ${G}$.

Theorem (Kahn, Z.) If ${G}$ is an ${n}$-vertex ${d}$-regular graph, then $\displaystyle i(G) \le i(K_{d,d})^{n/(2d)} = (2^{d+1} - 1)^{n/(2d)}$.

In the survey, I provide an exposition of the proofs of these two theorems as well as a discussion of subsequent developments. Notably, Davies, Jenssen, Perkins, and Roberts recently gave a brand new proof of the above theorems by introducing a powerful new technique, called the occupancy method, inspired by ideas in statistical physics, and it already has a number of surprising new consequences.

On a personal level, I am pleased to see this topic gaining renewed interest. (Also, somewhat to my chagrin, my undergraduate paper, according to Google Scholar, still remains my most cited paper to date.)

I shall close this blog post with one of my favorite open problems in this area.

Let ${c_q(G)}$ denote the number of proper ${q}$-colorings of ${G}$, i.e., coloring the vertices of ${G}$ with ${q}$ colors, so that no two adjacent vertices receive the same color.

Conjecture. If ${G}$ is an ${n}$-vertex ${d}$-regular graph, and ${q \ge 3}$, then $\displaystyle c_q(G) \le c_q(K_{d,d})^{n/(2d)}$.

I was pleased to learn from Will Perkins, who gave a talk at Oxford last week, that he, along with Davies, Jenssen, and Roberts, recently proved the conjecture for 3-regular graphs. The proof uses the occupancy method that they developed earlier. The method is reminiscent of the flag algebra machinery developed by Razborov some ten years ago for solving extremal problems in dense graphs. The new method can be seen as some kind of “flag algebra for sparse graphs”. I find this development quite exciting, and I expect that more news will come. Graph homomorphisms from G to Kq correspond to proper colorings of vertices of G with q colors.

# Upper tails for triangles in sparse random graphs

Eyal Lubetzky and I just finished and uploaded to the arXiv our new paper On the variational problem for upper tails of triangle counts in sparse random graphs. This paper concerns the following question:

The upper tail problem for triangles. What is the probability that the number of triangles in an Erdős-Rényi graph graph ${\mathcal{G}_{n,p}}$ is at least twice its mean, or more generally, larger than the mean by a factor of ${1 + \delta}$?

This problem has a fairly rich history, and it is considered a difficult problem in probabilistic combinatorics. In a 2002 paper titled The infamous upper tail, Janson and Ruciński surveyed the progress on the problem and described its challenges (they also considered the upper tail problem more generally for any subgraph ${H}$, but we focus on triangles here). Research towards the solution of this problem has led to new techniques for bounding probabilities of rare events. Note that in contrast, the lower tail problem — finding the probability of getting too few triangles — is comparatively easier.

Here we consider the case when p tends to zero as n grows (the dense case, where ${p}$ is fixed, leads to an interesting variational problem involving graph limits, as shown by a seminal work of Chatterjee and Varadhan — see my previous blog post). It is not too hard to describe what the answer should be in the sparse setting. Suppose we arbitrarily select a set of ${k = \delta^{1/3}np}$ vertices and force it to be a clique, that is, we force all edges between these k vertices to be present in the random graph — the probability “cost” of this constraint is ${p^{\binom{k}{2}} = p^{(\delta^{2/3}/2 + o(1))n^2p^2}}$ — the cliques gives us roughly an additional ${\binom{k}{3} = (\delta + o(1))\binom{n}{3} p^3}$ triangles, thereby boosting the total number of triangles in the graph by a factor of ${1 + \delta}$ from the mean, which is ${\binom{n}{3}p^3}$.

Let t(G) denote the triangle density in a graph G, i.e., the number of triangles in G as a fraction of the maximum possible number ${\binom{n}{3}}$ of triangles. The above argument shows that the upper tail probability satisfies $\displaystyle \mathbb{P}(t(\mathcal{G}_{n,p}) \geq (1 + \delta)p^3) \geq \exp\Big(-(\tfrac12 \delta^{2/3} +o(1))n^2 p^2 \log(1/p)\Big).$

Is this lower bound tight? That is, can we find a matching upper bound for the upper tail probability? This is precisely the infamous upper tail problem mentioned earlier. For a long time there was no satisfactory upper bound anywhere close to the lower bound. A breakthrough by Kim and Vu in 2004 gave an upper bound of the form ${\exp(-c n^2p^2)}$. However, this still leaves a missing factor of log(1/p) in the exponent. This problem was finally settled in 2012 by Chatterjee and independently by DeMarco and Kahn. They showed that the exponent in the probability has order ${n^2p^2 \log(1/p)}$, thereby filling in the “missing log.”

Now we know the correct order in the exponent, what remains unknown is the constant in front of the ${n^2p^2 \log(1/p)}$. In a very recent breakthrough by Chatterjee and Dembo (the preprint was released just January this year), they provided a framework that reduces this large deviation problem to a certain variational problem, at least in the range when ${p \geq n^{-\alpha}}$ for some explicit (though small) ${\alpha > 0}$. The variational problem is the natural one associated to this problem, and it is expected to hold for much sparser random graphs as well.

Eyal and I have been working on this variational problem for quite some time, starting with our previous paper where we studied the problem in the dense setting (constant ${p}$) and determined the phase diagram for replica symmetry. In our new paper, we solve this variational problem in the sparse regime. Combining the solution of this variational problem with the new results of Chatterjee and Dembo, this determines the correct asymptotic in the exponent of the upper tail probabilities, at least when ${n^{-\alpha} \ll p \ll 1}$. For fixed ${\delta > 0}$, we can now prove that $\displaystyle \mathbb{P}(t(\mathcal{G}_{n,p}) \geq 1 + \delta) = \exp\Big(-(C_\delta+o(1))n^2 p^2 \log(1/p)\Big).$

where we determine the constant in the exponent to be $\displaystyle C_\delta = \min\Big\{\tfrac12 \delta^{2/3}, \tfrac13 \delta\Big\}.$

We described earlier the story behind the ${\tfrac12 \delta^{2/3}}$ term (by forcing a clique of size ${\delta^{1/3}np}$). Where does the other term, ${\tfrac13 \delta}$, come from? It turns out there is another way to get a lots of triangles relatively cheaply, at least when ${p \gg n^{-1/2}}$: forcing a set of ${\ell = \frac13 \delta np^2}$ vertices to be connected to all other vertices. This has probability ${p^{\ell(n - \ell)} = p^{(\delta/3 + o(1))n^2p^2}}$. The first construction (forcing a clique) competes with the second construction (forcing a complete bipartite graph): the former is preferable when ${\delta > 27/8}$ and the latter is preferable when ${\delta < 27/8}$. It turns out, as we show in our paper, that these are essentially the only constructions.

# Recent developments on the Green-Tao theorem

There has quite a bit of activities around the Green-Tao theorem recently. In this blog post, I want to highlight some of these developments, focusing on the following papers, which were all posted on the arXiv in the past couple of months.

Relative Szemerédi theorem

Multidimensional Szemerédi theorem in the primes

——–

We start the story with Szemerédi’s famous result.

Szemerédi’s theorem. Every subset of integers with positive density contains arbitrarily long arithmetic progressions.

Green and Tao proved their famous theorem extending Szemerédi’s theorem to the primes.

Green-Tao theorem. The primes contain arbitrarily long arithmetic progressions. In fact, any subset of the primes with positive relative density contains arbitrarily long arithmetic progressions.

An important idea in Green and Tao’s work is the transference principle. They transfer Szemerédi’s theorem as a black box to the sparse setting, so that it can be applied to subsets of a sparse pseudorandom set of integers (in this case, some carefully designed enveloping set for the primes). Jacob Fox, David Conlon, and me at the Erdős Centennial conference in Budapest, Hungary, July 2013.

In my recent paper with David Conlon and Jacob Fox, we gave a new simplified approach to proving the Green-Tao theorem. In particular, we established a new relative Szemerédi theorem, which required simpler pseudorandomness hypotheses compared to Green and Tao’s original proof. Roughly speaking, a relative Szemerédi theorem is a result of the following form.

Relative Szemerédi theorem (roughly speaking). Let S be a pseudorandom subset of integers. Then any subset of S with positive relative density contains long arithmetic progressions.

The original proof in our paper followed the hypergraph approach, and in particular used the hypergraph removal lemma, a deep combinatorial result, as a black box. Subsequently, I wrote up a short six-page note showing how to prove the same result by directly transferring Szemerédi’s theorem, without going through hypergraph removal lemma. The former approach is more powerful and more general, while the latter approach is more direct and gives better quantitative bounds.

Next we shift our attention to higher dimensions. Furstenberg and Katznelson proved, using ergodic-theoretic techniques, a multidimensional generalization of Szemerédi’s theorem.

Multidimensional Szemerédi theorem (Furstenberg and Katznelson). Any subset of Zd with positive density contains arbitrary constellations.

Here a constellation means some finite set R of lattice points, and the theorem says that the subset of Zd contains some translation of a dilation of R.

(This result always reminds me of a lovely scene in the movie A Beautiful Mind where the John Nash character traces out shapes among the stars.)

Tao proved a beautiful extension for the Gaussian primes.

Theorem (Tao). The Gaussian primes contain arbitrary constellations.

In that paper, Tao also made the following interesting conjecture: let P denote the primes. Then any subset of P × P of positive relative density contains arbitrary constellations. This statement can be viewed as a hybrid of the Green-Tao theorem and the multidimensional Szemerédi theorem. Recently this conjecture was resolved by Tao and Ziegler, and independently by Cook, Magyar, and Titichetrakun.

Multidimensional Szemerédi theorem in the primes. Let P denote the primes. Then any subset of Pd with positive density contains arbitrary constellations.

Terry Tao has written a blog post about this new result where he describes the ideas in the proofs (so I won’t repeat too much). Tao and Ziegler proved their result via ergodic theory. Their proof is about 19 pages long, and they assume as black boxes two powerful results: (1) Furstenberg and Katznelson’s multidimensional Szemerédi theorem (more precisely their equivalent ergodic-theoretic formulation) and (2) the landmark results of Green, Tao, and Ziegler on linear equations in primes (and related work on the Mobius-nilsequences conjecture and the inverse conjecture on the Gowers norm). Both these results are deep and powerful hammers.

In contrast, Cook, Magyar, and Titichetrakun proceeded differently as they develop a sparse extension of hypergraph regularity method from scratch, without assuming previous deep results. Though their paper is much longer, at 44 pages.

In a recent paper by Jacob Fox and myself, we give a new and very short proof of the same result, assuming the same tools as the Tao-Ziegler proof. Our paper is only 4 pages long, and it uses a very simple sampling argument described in two paragraphs on the first page of our paper (all the ideas are on the first page; the rest of the paper just contains the technical details spelled out). I invite you to read the first page of our paper to learn the very short proof of the theorem.

# The Green-Tao theorem and a relative Szemerédi theorem

David Conlon, Jacob Fox, and I just uploaded to the arXiv our second joint paper, titled “A relative Szemerédi theorem.”

Before describing our work, let me to take a detour to reflect on some recent news in number theory.

The past couple weeks were filled with exciting developments on prime numbers. Yitang Zhang, in a breakthrough that caught the mathematical community by complete surprise, proved that there exists infinitely many pairs of primes with bounded gaps (specifically, less than 70 million). This is a giant leap of progress towards the famous twin primes conjecture, which claims that there exist infinitely pairs of primes differing by two.

By an amazing coincidence, in the same day that Zhang’s news became public, Harald Helfgott posted on the arXiv his paper which claims to prove the odd Goldbach conjecture, that every odd integer greater than 5 can be written as a sum of three primes. Previously this was known to be true for sufficiently large odd numbers, specifically those with at least about a thousand digits. It is possible to check the conjecture by computer for “small” cases, but 101000 is far from small. Helfgott’s work brought the “sufficiently large” down to a reasonable threshold, so that all the remaining small cases can indeed be verified by computer search.

Both results are exciting developments. However, we still seem far away from resolving two of the oldest problems about prime numbers. Zhang’s bound of 70 million probably could be brought down by more careful analysis, although getting it all the way down to 2 will probably require some really new ideas. As for Goldbach’s conjecture, there’s significant obstacle in getting down to two primes (the best result in this direction is due to Jingrun Chen), as all existing methods have severe limitations. But then again, the same could have been said about bounded gaps between primes before Zhang’s surprising work. Perhaps one day, we’ll be shocked again with a breakthrough on Goldbach, maybe even using techniques right in front of our eyes.

~~~~~~ Ben Green and Terry Tao

Back in 2004, the mathematical community received a surprise on another long-standing open problem on prime numbers: Ben Green and Terry Tao proved that the primes contain arbitrarily long arithmetic progressions.

An arithmetic progression is a sequence of equally spaced numbers. For example, 3, 5, 7 is a 3-term arithmetic progression of prime numbers. To find one with four terms, you need to look a bit further: 5, 11, 17, 23. At the time of Green and Tao’s proof, the longest such progression known was a sequence of 22 numbers, starting with 11410337850553 and with step size 4609098694200. This record has since been improved to 26. Here’s the description from Wikipedia:

As of April 2010, the longest known AP-k is an AP-26, found on April 12, 2010 by Benoãt Perichon on a PlayStation 3 with software by Jaroslaw Wroblewski and Geoff Reynolds, ported to the PlayStation 3 by Bryan Little, in a distributed PrimeGrid project.

There is a webpage with current records on primes in arithmetic progressions.

It was a long standing open conjecture that the primes should contain arithmetic progressions of every length. This was a folklore conjecture, with the first recorded instance in history dating back to 1770 by Lagrange and Waring. Green and Tao proved this conjecture, and their breakthrough is considered one of the greatest mathematical achievements of the twenty-first century. This work was an important part of Tao’s 2006 Fields Medal award.

~~~~~~

I was still in high school when the Green-Tao theorem was announced. The news spread quickly online, and I soon heard of it through my math competition online community. I remember being quite excited about the news. It was a quintessential mathematical breakthrough. The statement of the problem could be easily understood, yet the solution involved very deep mathematics. I fell in love with the statement of the Green-Tao theorem. It became one of my favorite mathematical results, and I aspired to one day understand the mathematics behind it.

Now, nine years later, as a graduate student, I find it deeply personally fulfilling to be working on a problem central to the Green-Tao theorem. Our latest paper (joint with Conlon and Fox) strengthens the main technical result in the work of Green and Tao. Endre Szemerédi

To describe this result, I need to first tell you about another important mathematical breakthrough by Endre Szemerédi dating back to the early 1970’s. Last year, Szemerédi received the Abel Prize, one of the highest lifetime achievement awards in mathematics. Szemerédi is perhaps most famous for his result, commonly referred to as Szemerédi’s theorem, which says that every subset of integers with positive density contains arbitrarily long arithmetic progressions. So, if S is a sufficiently large subset of the integers, “large” meaning that it contains, say, at least 0.1% of the first N positive integers for sufficiently large N, then S necessarily contains an arithmetic progression of every length.

Szemerédi’s theorem is a very deep result, albeit again with a seemingly very innocent statement. It was conjectured by Erdős and Turán in the 1930’s, and remained open for decades. Since Szemerédi’s breakthrough, several other proofs have been discovered. None of the proofs are easy but all of them have deep insights and have spawned into very rich and active areas of mathematical research.

I was personally exposed to Szemerédi’s theorem while at Cambridge University. I spent a year there right after finishing undergrad and took part in what is colloquially known as Part III of the Maths Tripos. One of the components of the program was writing an extended expository essay, and I wrote mine about Szemerédi’s theorem under the supervision of Ben Green. Ben gave me a very high score for the essay. I’ve put the essay on my website, and several people have told me that they found it to be helpful (including one who was preparing a popular article on Szemerédi after his Abel Prize award). Though, to be honest, looking back, perhaps now I would be a bit embarrassed to read that essay again myself, since I wonder how much I actually understood while I was writing it up at the time.

While Szemerédi’s theorem is a powerful result, it is not enough to draw any conclusions about prime numbers. Szemerédi’s theorem only works for sets of integers with positive density. The primes, on the other hand, have density diminishing to zero. Indeed, the Prime Number Theorem tells us that between 1 and N, approximately 1 in ln N fraction of the numbers are prime. This ratio, 1/ln N, diminishes to zero as N grows to infinity. So Szemerédi’s theorem doesn’t work here.

The primary innovation of Green and Tao is that they came up with a relative version of Szemerédi’s theorem. To overcome the problem that the primes have zero density, they find a slightly larger set of integers where the primes can sit inside as a subset of positive relative density. This larger host set, roughly speaking, is the set of “almost primes,” which consists of numbers with few prime divisors. They found a way to transfer Szemerédi’s theorem to this relative setting, showing that if we start with a set with some random-like characteristics (in this case, the almost primes), then any subset of it with positive density relative to the host set must necessarily contain long arithmetic progressions.

The Green-Tao paper splits into two parts. In the first part, which is their main technical contribution, they establish a relative Szemerédi theorem for subsets of pseudorandom sets of integers. Their method was heavily influenced by the work of Fields Medalist Timothy Gowers, who revolutionized the field of additive combinatorics by inventing a far-fetching extension of Fourier analysis (also known in this context as the Hardy-Littlewood circle method) to give a novel proof of Szemerédi’s theorem. The second part of Green and Tao’s paper shows that the almost primes act as a suitable host set by verifying the required pseudorandomness conditions. Most of the number theoretic input to their work were credited to the works of Goldston and Yıldırım, which later led to a spectacular breakthrough in the problem of small gaps in primes by Goldston, Pintz, and Yıldırım (which relates back to Zhang’s twin primes breakthrough mentioned at the beginning of this blog post).

The pseudorandomness conditions required in the Green-Tao method are rather involved. It assumes that the host pseudorandom set satisfies a “linear forms condition” as well as a “correlations condition.” Both conditions are essential to Green and Tao’s method of establishing their relative Szemerédi’s theorem. They show that the almost primes satisfy these pseudorandomness conditions, thereby proving the old conjecture about progressions in primes. However, the complicated pseudorandomness hypotheses, while adequate for this application, seem rather contrived and somewhat unsatisfying. This leads to the next question, which has been repeatedly asked since the Green-Tao work: does a relative Szemerédi theorem hold under more natural pseudorandomness hypotheses?

In our new paper, we show that the answer is yes! We prove a relative Szemerédi theorem under a very simple and natural linear forms condition. What we need to assume is a small subset of what Green and Tao assume in their work. This new result provides not only a brand new (and simpler, as we believe) alternative approach to the proof of the Green-Tao theorem, but also, more broadly speaking, a new method for understanding sparse pseudorandom structures. The Green-Tao method has had a large number of applications since its inception almost a decade ago. With our new perspective, perhaps one can go even further.

# Sphere packing bounds via spherical codes

Henry Cohn and I just uploaded to the arXiv our paper “Sphere packing bounds via spherical codes.” [Update: Henry gave a wonderful talk about our paper at the IAS. A video of the talk is available here.] What’s the most space-efficient way to arrange a collection of identical balls? This is known as the sphere packing problem. It is a very difficult problem with a long and interesting history. This problem in 3-dimensions is known as Kepler conjecture, which says that the the face-centered cubic formation does best. This is basically how grocers stack oranges. The seemingly innocent Kepler conjecture turned out to be extremely difficult, and it was only solved in the late 1990’s by Thomas Hales who gave a very complex proof involving massive computer-aided calculations. I’ve included a few article links at the end of this blog post on the history and background of the sphere packing problem.

Now, what about sphere packing in higher dimensions? Unfortunately, we know very little about what happens beyond three dimensions. No proof of optimality is known in any higher dimension, and there are only a few dozen dimensions in which there are even plausible conjectures for the densest packing. In dimensions 8 and 24 there are upper bounds that are extremely close to the conjectured optima, thanks to the works of Cohn, Elkies, and Kumar [1,2,3] (dimensions 8 and 24 are somehow special because of the existence of highly symmetric lattices known as the ${E_8}$ lattice in dimension 8 and the Leech lattice in dimension 24). However, in most dimensions we must be content with much cruder bounds.

The current state of art for sphere packing density upper bounds is more or less as follows:

• In dimensions 1, 2, 3, the exact upper bound is known. The result for dimension 3 is due to Hales.
• In low dimensions, namely 4 to 42, Cohn and Elkies improved previous record by Rogers, although there were some recent improvements in dimensions 4,5,6,7,9 by de Laat, Filho, and Vallentin using techniques of semidefinite programming.
• In all high dimensions, namely 43 and above, the best bounds are due to Kabatiansky and Levenshtein in 1978 and have not been improved since then.

The purpose of our of paper is fourfold:

1. We give a small improvement over the 1978 bounds of Kabatiansky and Levenshtein in high dimensions by giving a simple modification of their geometric argument relating spherical codes to sphere packings.
2. Kabatiansky and Levenshtein derived their bounds by first formulating a linear program for proving upper bounds on spherical codes. Cohn and Elkies found a more direct approach to bounding sphere packing densities, with no need to consider spherical codes. However, despite the excellent performance in low dimensions, the asymptotic behavior of the Cohn-Elkies bound is far from obvious and it has been unclear whether it improves on, or even matches, the Kabatiansky-Levenshtein bound asymptotically. In our paper, we show that in every dimension ${n}$, the Cohn-Elkies linear program can always match the Kabatiansky-Levenshtein approach. This further demonstrates the power of the linear programming bound for sphere packing.
3. We prove an analogue of the Kabatiansky-Levenshtein bound in hyperbolic space. The resulting bound is exponentially better than the best bound previously known in hyperbolic space.
4. We develop the theory of hyperbolic linear programming bounds and prove that they too subsume the Kabatiansky-Levenshtein approach. Packing in hyperbolic space is much more difficult to handle than in Euclidean space, primarily because the volume of an expanding ball grows exponentially with its radius (instead of polynomially as in the case of Euclidean space), so we that cannot neglect boundary fluctuations. In fact, it is a non-trivial matter to even define the density of a packing (there are examples of packings for which any reasonable definition of density should yield two different answers).