## Reflections on the recent solution of the cap-set problem I

May 19, 2016

Sometimes blog posts about recent breakthroughs can be useful because they convey the main ideas of a proof without getting bogged down in the technical details. But the recent solution of the cap-set problem by Jordan Ellenberg, and independently and fractionally later by Dion Gijswijt, both making crucial use of an amazing lemma of Croot, Lev and Pach that was made public a week or so before, does not really invite that kind of post, since the papers are so short, and the ideas so transparent, that it’s hard to know how a blog post can explain them more clearly.

But as I’ve got a history with this problem, including posting about it on this blog in the past, I feel I can’t just not react. So in this post and a subsequent one (or ones) I want to do three things. The first is just to try to describe my own personal reaction to these events. The second is more mathematically interesting. As regular readers of this blog will know, I have a strong interest in the question of where mathematical ideas come from, and a strong conviction that they always result from a fairly systematic process — and that the opposite impression, that some ideas are incredible bolts from the blue that require “genius” or “sudden inspiration” to find, is an illusion that results from the way mathematicians present their proofs after they have discovered them.

From time to time an argument comes along that appears to present a stiff challenge to my view. The solution to the cap-set problem is a very good example: it’s easy to understand the proof, but the argument has a magic quality that leaves one wondering how on earth anybody thought of it. I’m referring particularly to the Croot-Lev-Pach lemma here. I don’t pretend to have a complete account of how the idea might have been discovered (if any of Ernie, Seva or Peter, or indeed anybody else, want to comment about this here, that would be extremely welcome), but I have some remarks.

The third thing I’d like to do reflects another interest of mine, which is avoiding duplication of effort. I’ve spent a little time thinking about whether there is a cheap way of getting a Behrend-type bound for Roth’s theorem out of these ideas (and I’m not the only one). Although I wasn’t expecting the answer to be yes, I think there is some value in publicizing some of the dead ends I’ve come across. Maybe it will save others from exploring them, or maybe, just maybe, it will stimulate somebody to find a way past the barriers that seem to be there.
Read the rest of this entry »

## The L-functions and modular forms database

May 10, 2016

With each passing decade, mathematics grows substantially. As it grows, mathematicians are forced to become more specialized — in the sense of knowing a smaller fraction of the whole — and the time and effort needed to get to the frontier of what is known, and perhaps to contribute to it, increases. One might think that this process will eventually mean that nobody is prepared to make the effort any more, but fortunately there are forces that work in the opposite direction. With the help of the internet, it is now far easier to find things out, and this makes research a whole lot easier in important ways.

It has long been a conviction of mine that the effort-reducing forces we have seen so far are just the beginning. One way in which the internet might be harnessed more fully is in the creation of amazing new databases, something I once asked a Mathoverflow question about. I recently had cause (while working on a research project with a student of mine, Jason Long) to use Sloane’s database in a serious way. That is, a sequence of numbers came out of some calculations we did, we found it in the OEIS, that gave us a formula, and we could prove that the formula was right. The great thing about the OEIS was that it solved an NP-ish problem for us: once the formula was given to us, it wasn’t that hard to prove that it was correct for our sequence, but finding it in the first place would have been extremely hard without the OEIS.
Read the rest of this entry »

## Should I have bet on Leicester City?

May 3, 2016

If you’re not British, or you live under a stone somewhere, then you may not have heard about one of the most extraordinary sporting stories ever. Leicester City, a football (in the British sense) team that last year only just escaped relegation from the top division, has just won the league. At the start of the season you could have bet on this happening at odds of 5000-1. Just 12 people availed themselves of this opportunity.

Ten pounds bet then would have net me 50000 pounds now, so a natural question arises: should I be kicking myself (the appropriate reaction given the sport) for not placing such a bet? In one sense the answer is obviously yes, as I’d have made a lot of money if I had. But I’m not in the habit of placing bets, and had no idea that these odds were being offered anyway, so I’m not too cut up about it.

Nevertheless, it’s still interesting to think about the question hypothetically: if I had been the betting type and had known about these odds, should I have gone for them? Or would regretting not doing so be as silly as regretting not choosing and betting on the particular set of numbers that just happened to win the national lottery last week?
Read the rest of this entry »

## Discrete Analysis launched

March 1, 2016

As you may remember from an earlier post on this blog, Discrete Analysis is a new mathematics journal that runs just like any other journal except in one respect: the articles we publish live on the arXiv. This is supposed to highlight the fact that in the internet age, and in particular in an age when it is becoming routine for mathematicians to deposit their articles on the arXiv before they submit them to journals, the only important function left for journals is organizing peer review. Since this is done through the voluntary work of academics, it should in principle be possible to run a journal for almost nothing. The legacy publishers (as they are sometimes called) frequently call people naive for suggesting this, so it is important to have actual examples to prove it, and Discrete Analysis is set up to be one such example. Its website goes live today.
Read the rest of this entry »

## FUNC4 — further variants

February 22, 2016

I’ve been in Paris for the weekend, so the number of comments on the previous post got rather large, and I also fell slightly behind. Writing this post will I hope help me catch up with what is going on.

### FUNC with symmetry

One question that has arisen is whether FUNC holds if the ground set is the cyclic group $\mathbb Z_n$ and $\mathcal A$ is rotationally invariant. This was prompted by Alec Edgington’s example showing that we cannot always find $x$ and an injection from $\mathcal A_{\overline x}$ to $\mathcal A_x$ that maps each set to a superset. Tom Eccles suggested a heuristic argument that if $\mathcal A$ is generated by all intervals of length $r$, then it should satisfy FUNC. I agree that this is almost certainly true, but I think nobody has yet given a rigorous proof. I don’t think it should be too hard.

One can ask similar questions about ground sets with other symmetry groups.

A nice question that I came across on Mathoverflow is whether the intersection version of FUNC is true if $\mathcal A$ consists of all subgroups of a finite group $G$. The answers to the question came very close to solving it, with suggestions about how to finish things off, but the fact that the question was non-trivial was quite a surprise to me.
Read the rest of this entry »

## FUNC3 — further strengthenings and variants

February 13, 2016

In the last post I concentrated on examples, so in this one I’ll concentrate on conjectures related to FUNC, though I may say a little about examples at the end, since a discussion has recently started about how we might go about trying to find a counterexample to FUNC.

### A proposal for a rather complicated averaging argument

After the failure of the average-overlap-density conjecture, I came up with a more refined conjecture along similar lines that has one or two nice properties and has not yet been shown to be false.

The basic aim is the same: to take a union-closed family $\mathcal A$ and use it to construct a probability measure on the ground set in such a way that the average abundance with respect to that measure is at least 1/2. With the failed conjecture the method was very basic: pick a random non-empty set $A\in\mathcal A$ and then a random element $x\in A$.

The trouble with picking random elements is that it gives rise to a distribution that does not behave well when you duplicate elements. (What you would want is that the probability is shared out amongst the duplicates, but in actual fact if you duplicate an element lots of times it gives an advantage to the set of duplicates that the original element did not have.) This is not just an aesthetic concern: it was at the heart of the downfall of the conjecture. What one really wants, and this is a point that Tobias Fritz has been emphasizing, is to avoid talking about the ground set altogether, something one can do by formulating the conjecture in terms of lattices, though I’m not sure what I’m about to describe does make sense for lattices.
Read the rest of this entry »

## FUNC2 — more examples

February 8, 2016

The first “official” post of this Polymath project has passed 100 comments, so I think it is time to write a second post. Again I will try to extract some of the useful information from the comments (but not all, and my choice of what to include should not be taken as some kind of judgment). A good way of organizing this post seems to be list a few more methods of construction of interesting union-closed systems that have come up since the last post — where “interesting” ideally means that the system is a counterexample to a conjecture that is not obviously false.

### Standard “algebraic” constructions

#### Quotients

If $\mathcal A$ is a union-closed family on a ground set $X$, and $Y\subset X$, then we can take the family $\mathcal A_Y=\{A\cap Y:A\in\mathcal{A}\}$. The map $\phi:A\to A\cap Y$ is a homomorphism (in the sense that $\phi(A\cup B)=\phi(A)\cup\phi(B)$, so it makes sense to regard $\mathcal A_Y$ as a quotient of $\mathcal A$.

#### Subfamilies

If instead we take an equivalence relation $R$ on $X$, we can define a set-system $\mathcal A( R)$ to be the set of all unions of equivalence classes that belong to $\mathcal{A}$.

Thus, subsets of $X$ give quotient families and quotient sets of $X$ give subfamilies.

#### Products

Possibly the most obvious product construction of two families $\mathcal A$ and $\mathcal B$ is to make their ground sets disjoint and then to take $\{A\cup B:A\in\mathcal A,B\in\mathcal B\}$. (This is the special case with disjoint ground sets of the construction $\mathcal A+\mathcal B$ that Tom Eccles discussed earlier.)

Note that we could define this product slightly differently by saying that it consists of all pairs $(A,B)\in\mathcal A\times\mathcal B$ with the “union” operation $(A,B)\sqcup(A',B')=(A\cup A',B\cup B')$. This gives an algebraic system called a join semilattice, and it is isomorphic in an obvious sense to $\mathcal A+\mathcal B$ with ordinary unions. Looked at this way, it is not so obvious how one should define abundances, because $(\mathcal A\times\mathcal B,\sqcup)$ does not have a ground set. Of course, we can define them via the isomorphism to $\mathcal A+\mathcal B$ but it would be nice to do so more intrinsically.
Read the rest of this entry »

## FUNC1 — strengthenings, variants, potential counterexamples

January 29, 2016

After my tentative Polymath proposal, there definitely seems to be enough momentum to start a discussion “officially”, so let’s see where it goes. I’ve thought about the question of whether to call it Polymath11 (the first unclaimed number) or Polymath12 (regarding the polynomial-identities project as Polymath11). In the end I’ve gone for Polymath11, since the polynomial-identities project was listed on the Polymath blog as a proposal, and I think the right way of looking at things is that the problem got solved before the proposal became a fully-fledged project. But I still think that that project should be counted as a Polymathematical success story: it shows the potential benefits of opening up a problem for consideration by anybody who might be interested.

## Frankl’s union-closed conjecture — a possible Polymath project?

January 21, 2016

Although it was from only a couple of people, I had an enthusiastic response to a very tentative suggestion that it might be rewarding to see whether a polymath project could say anything useful about Frankl’s union-closed conjecture. A potentially worrying aspect of the idea is that the problem is extremely elementary to state, does not seem to yield to any standard techniques, and is rather notorious. But, as one of the commenters said, that is not necessarily an argument against trying it. A notable feature of the polymath experiment has been that it throws up surprises, so while I wouldn’t expect a polymath project to solve Frankl’s union-closed conjecture, I also know that I need to be rather cautious about my expectations — which in this case is an argument in favour of giving it a try.

A less serious problem is what acronym one would use for the project. For the density Hales-Jewett problem we went for DHJ, and for the Erdős discrepancy problem we used EDP. That general approach runs into difficulties with Frankl’s union-closed conjecture, so I suggest FUNC. This post, if the project were to go ahead, could be FUNC0; in general I like the idea that we would be engaged in a funky line of research.
Read the rest of this entry »

## Entropy and Sidorenko’s conjecture — after Szegedy

November 18, 2015

Here is a simple but important fact about bipartite graphs. Let $G$ be a bipartite graph with (finite) vertex sets $X$ and $Y$ and edge density $\alpha$ (meaning that the number of edges is $\alpha |X||Y|$). Now choose $(x_1,x_2)$ uniformly at random from $X^2$ and $(y_1,y_2)$ uniformly at random from $Y^2$. Then the probability that all of $x_1y_1, x_1y_2, x_2y_1$ and $x_2y_2$ are edges is at least $\alpha^4$.

The proof is very simple. For each $x$, let $f_x:Y\to\{0,1\}$ be the characteristic function of the neighbourhood of $x$. That is, $f_x(y)=1$ if $xy$ is an edge and $0$ otherwise. Then $\sum_{x,y}f_x(y)$ is the sum of the degrees of the $x\in X$, which is the number of edges of $G$, which is $\alpha |X||Y|$. If we set $f=\sum_{x\in X}f_x$, then this tells us that $\sum_{y\in Y}f(y)=\alpha|X||Y|$. By the Cauchy-Schwarz inequality, it follows that $\sum_{y\in Y}f(y)^2\geq\alpha^2|X|^2|Y|$.

But by the Cauchy-Schwarz inequality again,
$(\sum_{y\in Y}f(y)^2)^2=(\sum_{y\in Y}\sum_{x_1,x_2\in X}f_{x_1}(y)f_{x_2}(y))^2$
$= (\sum_{x_1,x_2\in X}\sum_{y\in Y}f_{x_1}(y)f_{x_2}(y))^2$
$\leq |X|^2\sum_{x_1,x_2\in X}(\sum_{y\in Y}f_{x_1}(y)f_{x_2}(y))^2$
$=|X|^2\sum_{x_1,x_2\in X}\sum_{y_1,y_2\in Y}f_{x_1}(y_1)f_{x_2}(y_1)f_{x_1}(y_2)f_{x_2}(y_2).$
That last expression is $|X|^2$ times the number of quadruples $x_1,x_2,y_1,y_2$ such that all of $x_1y_1, x_1y_2, x_2y_1$ and $x_2y_2$ are edges, and our previous estimate shows that it is at least $\alpha^4|X|^4|Y|^2$. Therefore, the probability that a random such quadruple consists entirely of edges is at least $\alpha^4$, as claimed (since there are $|X|^2|Y|^2$ possible quadruples to choose from). Read the rest of this entry »