# ARV on Abelian Cayley Graphs

Continuing from the previous post, we are going to prove the following result: let ${G}$ be a ${d}$-regular Cayley graph of an Abelian group, ${\phi(G)}$ be the normalized edge expansion of ${G}$, ${ARV(G)}$ be the value of the ARV semidefinite programming relaxation of sparsest cut on ${G}$ (we will define it below), and ${\lambda_2(G)}$ be the second smallest normalized Laplacian eigenvalue of ${G}$. Then we have

$\displaystyle \lambda_2 (G) \leq O(d) \cdot (ARV (G))^2 \ \ \ \ \ (1)$

which, together with the fact that ${ARV(G) \leq 2 \phi(G)}$ and ${\phi(G) \leq \sqrt{2 \lambda_2}}$, implies the Buser inequality

$\displaystyle \lambda_2 (G) \leq O(d) \cdot \phi^2 (G) \ \ \ \ \ (2)$

and the approximation bound

$\displaystyle \phi(G) \leq O(\sqrt d) \cdot ARV(G) \ \ \ \ \ (3)$

The proof of (1), due to Shayan Oveis Gharan and myself, is very similar to the proof by Bauer et al. of (2).

# Buser Inequalities in Graphs

As life is tentatively returning to normal, I would like to once again post technical material here. Before returning to online optimization, I would like to start with something from 2015 that we never wrote up properly, that has to do with graph curvature and with Buser inequalities in graphs.

# Finally, a joy

In Rome we have an expression, mai una gioia (literally, “never (a moment of) joy”) that applies well to the present times. Yesterday, there was, finally, something to be joyous about: the announcement that two of my heroes, Laszlo Lovasz and Avi Wigderson, will share the 2021 Abel Prize, one of the highest honors of mathematics.

The reader can find a very good article about them on Quanta Magazine.

Instead of talking about their greatest accomplishment, here I would like to recall two beautiful and somewhat related results, that admit a short treatment.

# Keith Ball on Bourgain’s Legacy in Geometric Functional Analysis

The Bulletin of the AMS has just posted an article by Keith Ball on the legacy of Bourgain’s work on geometric functional analysis.

This beautifully written article talks about results and conjectures that are probably familiar to readers of in theory, but from the perspective of their mathematical motivations and of the bigger picture in which they fit.

# Talagrand’s Generic Chaining

Welcome to phase two of in theory, in which we again talk about math. I spent last Fall teaching two courses and getting settled, I mostly traveled in January and February, and I have spent the last two months on my sofa catching up on TV series. Hence I will reach back to last Spring, when I learned about Talagrand’s machinery of generic chaining and majorizing measures from Nikhil Bansal, in the context of our work with Ola Svensson on graph and hypergraph sparsification. Here I would like to record what I understood about the machinery, and in a follow-up post I plan to explain the application to hypergraph sparsification.

# Lies, Damns Lies, and Herbert London

I am grading the final projects of my class, I am trying the clear the backlog of publishing all the class notes, I am way behind on my STOC reviews, and in two days I am taking off for a complicated two-week trips involving planes, trains and a rented automobile, as well as an ambitious plan of doing no work whatsoever from December 20 to December 31.

So, today I was browsing Facebook, and when I saw a post containing an incredibly blatant arithmetic mistake (which none of the several comments seemed to notice) I spent the rest of the morning looking up where it came from.

The goal of the post was to make the wrong claim that people have been paying more than enough money into social security (through payroll taxes) to support the current level of benefits. Indeed, since the beginning, social security has been paying individuals more than they put in, and now that population and salaries have stop growing, social security is also paying out retired people more than it gets from working people, so that the “trust fund” (whether one believes it is a real thing or an accounting fiction) will run out in the 2030s unless some change is made.

This is a complicated matter, but the post included a sentence to the extent that $4,500 a year, with an interest of 1% per year “compounded monthly”, would add up to$1,3 million after 40 years. This is not even in the right order of magnitude (it adds up to about $220k) and it should be obvious without making the calculation. Who would write such a thing, and why? My first stop was a July 2012 post on snopes, which commented on a very similar viral email. Snopes points out various mistakes (including the rate of social security payroll taxes), but the calculation in the snopes email, while based on wrong assumptions, has correct arithmetic: it says that$4,500 a year, with a 5% interest, become about $890k after 49 years. So how did the viral email with the wrong assumptions and correct arithmetic morph into the Facebook post with the same wrong assumptions but also the wrong arithmetic? I don’t know, but here is an August 2012 post on, you can’t make this stuff up, Accuracy in Media, which wikipedia describes as a “media watchdog.” The post is attributed to Herbert London, who has PhD from Columbia, is a member of the Council on Foreign Relation and used to be the president of a conservative think-tank. Currently, he has an affiliation with King’s College in New York. London’s post has the sentence I saw in the Facebook post: (…) an employer’s contribution of$375 per month at a modest one percent rate compounded over a 40 year work experience the total would be $1.3 million. The rest of the post is almost identical to the July 2012 message reported by Snopes. Where did Dr. London get his numbers? Maybe he compounded this hypothetical saving as 1% per month? No, because that would give more than$4 million. One does get about $1.3 million if one saves$375 a month for thirty years with a return of 1% per month, though.

Perhaps a more interesting question is why this “fake math” is coming back after five years. In 2012, Paul Ryan put forward a plan to “privatize” Social Security, and such a plan is now being revived. The only way to sell such a plan is to convince people that if they saved in a private account the amount of payroll taxes that “goes into” Social Security, they would get better benefits. This may be factually wrong, but that’s hardly the point.

# Ellenberg’s announcement of a solution to the cap-set problem

Jordan Ellenberg has just announced a resolution of the “cap problem” using techniques of Croot, Lev and Pach, in a self-contained three-page paper. This is a quite unexpected development for a long-standing open problem in the core of additive combinatorics.

Perhaps the right starting point for this story is 1936, when Erdos and Turan conjectured that, for every ${k}$, if ${A}$ is a subset of ${\{1,\ldots, N\}}$ without ${k}$-terms arithmetic progressions, then ${|A|= o_k(n)}$, or, equivalently, that if ${A}$ is a subset of the integers of positive density, then it must have arbitrarily long arithmetic progressions. Their goal in stating this conjecture was that resolving it would be a stepping stone to proving that the prime numbers have arbitrarily long arithmetic progressions. This vision came true several decades later. Szemeredi proved the conjecture in 1975, and Green and Tao proved that the primes contain arbitrarily long arithmetic progressions in 2004, with Szemeredi’s theorem being a key ingredient in their proof.

Rewinding a bit, the first progress on the Erdos-Turan conjecture came from Roth, who proved the ${k=3}$ case In 1955. Roth’s proof establishes that if ${A \subseteq \{ 1,\ldots, N\}}$ does not have length-3 arithmetic progressions, then ${|A|}$ is at most, roughly ${N/\log\log N}$. Erdos also conjectured that the bound should be ${o(N/\log N)}$, and if this were true it would imply that the primes have infinitely many length-3 arithmetic progressions simply because of their density.

Roth’s proof uses Fourier analysis, and Meshulam, in 1995, noted that the proof becomes much cleaner, and it leads to better bounds, if one looks at the analog problem in ${{\mathbb F}_p^n}$, where ${{\mathbb F}_p}$ is a finite field (of characteristic different from 2). In this case, the question is how big can ${A\subseteq {\mathbb F}_p^n}$ be if it does not have three points on a line. An adaptation of Roth’s techniques gives an upper bound of the order of ${p^n/n}$, which, for constant ${p}$, is of the order of ${N/\log N}$ if ${N}$ is the size of the universe of which ${A}$ is a subset.

Bourgain introduced a technique to work on ${{\mathbb Z}/N{\mathbb Z}}$ “as if” it where a vector space over a finite field, and proved upper bounds of the order of ${N/\sqrt {\log N}}$ and then ${N/(\log N)^{3/4}}$ to the size of a subset of ${\{ 1,\ldots , N\}}$ without length-3 arithmetic progressions. The latest result in this line is by Sanders, who proved a bound of ${(N poly\log\log N)/\log N}$, very close to Erdos’s stronger conjecture.

How far can these results be pushed? A construction of Behrend’s shows that there is a set ${A\subseteq \{ 1,\ldots, N\}}$ with no length-3 arithmetic progression and size roughly ${N/2^{\sqrt {\log N}}}$. The construction is simple (it is a discretization of a sphere in ${\sqrt {\log N}}$ dimensions) and it has some unexpected other applications. This means that the right bound in Roth’s theorem is of the form ${N^{1-o(1)}}$ and that the “only” question is what is the ${N^{-o(1)}}$ term.

In the finite vector space case, there is no analog of Behrend’s construction, and so the size of say, the largest subset of ${{\mathbb F}_3^n}$ without three points on a line, was completely open, with an upper bound of the order of ${3^n/n}$ and lower bounds of the order of ${c^n}$ for some constant ${c<3}$. The cap problem was the question of whether the right bound is of the form ${3^{(1-o(1)) }}$ or not.

Two weeks ago, Croot, Lev and Pach proved that if ${A}$ is a subset of ${({\mathbb Z}/4{\mathbb Z})^n}$ without length-3 arithmetic progressions, then ${|A|}$ is at most of the order of ${4^{.926 \cdot n}}$. This was a strong indication that the right bound in the cap problem should be sub-exponential.

This was done a couple of days ago by Ellenberg, who proved an upper bound of the form ${(2.756)^n}$ holds in ${{\mathbb F}_3^n}$. The proof is not specific to ${{\mathbb F}_3}$ and generalizes to all finite fields.

Both proofs use the polynomial method. Roughly speaking, the method is to associate a polynomial to a set of interest (for example, by finding a non-zero low-degree polynomial that is zero for all points in the set), and then to proceed with the use of simple properties of polynomials (such as the fact that the space of polynomials of a certain degree has a bounded dimension, or that the set of zeroes of a univariate non-zero polynomial is at most the degree) applied either to the polynomial that we constructed or to the terms of its factorization.

Let ${P_d}$ be the vector space of ${n}$-variate polynomials over ${{\mathbb F}_3}$ of total degree ${d}$ that are cube-free (that is, such that all variables occur in monomials with degree 0, 1, or 2), and let ${m_d}$ be its dimension.

If ${A\subseteq {\mathbb F}_3^n}$ is a set such that there are no distinct ${a,b,c}$ such that ${a+b+c=0}$ (a different property from being on a line, but the draft claims that the same argument works for the property of not having three points on a line as well), then Ellenberg shows that

$\displaystyle m_d - 3^n + |A| \leq 3 m_{d/2}$

then the bound follows from computing that ${m_{2n/3} \geq 3^n - c^n}$ and ${m_{n/3} \leq c^n}$ for ${c \approx 2.756\cdots}$.

The finite field Kakeya problem is another example of a problem that had resisted attacks from powerful Fourier-analytic proofs, and was solved by Zeev Dvir with a relatively simple application of the polynomial method. One may hope that the method has not yet exhausted its applicability.

Gil Kalai has posted about further consequence of the results of Croot, Lev, Pach and Ellenberg.

# Paul Erdös’s 102-ennial

Paul Erdös would be 102 year old this year, and in celebration of this the Notices of the AMS have published a two-part series of essays on his life and his work: [part 1] and [part 2].

Of particular interest to me is the story of the problem of finding large gaps between primes; recently Maynard, Ford, Green, Konyagin, and Tao solved an Erdös $10,000 question in this direction. It is probably the Erdös open question with the highest associated reward ever solved (I don’t know where to look up this information — for comparison, Szemeredi’s theorem was a$1,000 question), and it is certainly the question whose statement involves the most occurrences of “$\log$“.

# Harald Helfgott on Growth in Groups

The Bulletin of the AMS is going to publish a 57-page survey on growth in groups, which is already online, and which touches several topics of interest to readers of in theory, including the recent work of Bourgain and Gamburd on expander Cayley graphs of $SL_2(p)$ and the work of Helfgott and Seress on the diameter of permutation groups.