Power saving for the Brown-Erdős-Sós problem

Power saving for the Brown-Erdős-Sós problem, Discrete Analysis 2025:5, 16 pp.

It has long been known that there are important connections between extremal questions concerning hypergraphs and extremal questions in additive combinatorics. This realization dates back at least as far as the famous $(6,3)$-theorem of Ruzsa and Szemerédi, which has several equivalent formulations, including the equally famous triangle removal lemma.

In its hypergraph formulation, the theorem states that if a 3-uniform hypergraph has $n$ vertices and no six of those vertices span three edges, then there are $o(n^2)$ edges. (Here an “edge” means a triple of vertices that belongs to the hypergraph.) A moment’s reflection shows that if the hypergraph is linear – that is, no two edges overlap in more than one vertex – then the only way that six vertices can span three edges is for those three edges to form what is sometimes called a “triforce”, which is a configuration of the form $xyu, yzv, xzw$. Thus, another way to state the theorem is to say that for every $\delta>0$ there exists $n$ such that every linear hypergraph with $n$ vertices and at least $\delta n^2$ edges (note that the number of edges of a linear hypergraph is trivially at most $\binom n2$) contains a triforce.

To see how this is relevant to additive combinatorics, let $G$ be an Abelian group of odd order $n$ and let $A$ be a subset of $G$ of density $\delta$. Form a 6-partite linear hypergraph $H$ with vertex sets $X,Y,Z,U,V,W$ that are each copies of $G$, and let $xyu$ be an edge if $y-x=u$ and $u\in A$, let $yzv$ be an edge if $z-y=v$ and $v\in A$, and let $xzw$ be an edge if $z-x=2w$ and $w\in A$. Then $H$ has positive density (independent of $n$) so for large enough $n$ it must contain a triforce. It is a small exercise to check that that triforce must contain exactly one vertex in each vertex set, which therefore gives us three elements $x,y,z$ of $G$ such that $y-x$ and $z-y$ belong to $A$ and $z-x$ belongs to $2.A$ (the dilate of $A$ by a factor of 2). From this we obtain $u,v,w\in A$ with $2w=u+v$ – that is, an arithmetic progression. This is not quite a proof, because the arithmetic progression can be degenerate, but a slightly more careful version of the argument yields that the number of triforces exceeds the number of degenerate arithmetic progressions.

Motivated by this result, it is natural to formulate the following general problem: how many edges can a 3-uniform hypergraph on $n$ vertices have if no $v$ vertices span $e$ or more edges? In particular, the well-known Brown-Erdős-Sós question asks whether if $e$ is fixed and $v=e+3$, then this number is $o(n^2)$.

A well-known result in this direction, due to Sárközy and Selkow in 2004, is that the number of edges is $o(n^2)$ if $v=e+\lfloor \log_2 e\rfloor+2$. Note that when $e=3$, $\lfloor\log_2e\rfloor=1$, so this result generalizes the Ruzsa-Szemerédi $(6,3)$-theorem. This result has been improved more recently: in 2017 Solymosi and Solymosi obtained the conclusion if $e=10$ and $v=14$, instead of the 15 that would be given by the Sárközy-Selkow theorem, and Conlon, Gishboliner, Levanzov and Shapira obtained the first asymptotic improvement by showing that the conclusion holds if $v=e+\lceil 26\log e/\log\log e\rceil$.

This paper concerns a related question: how large does $v$ have to be (as a function of $e$) for the bound to be not just $o(n^2)$ but $O(n^{2-c})$ for some positive constant $c$ (depending on $e$)? The main result is that it suffices if $v=\lfloor \log_2 e\rfloor +38$. Thus, their bound matches the Sárközy-Selkow bound (but not the Conlon-Gishboliner-Levanzov-Shapira bound) up to an additive constant. A bound of $e+2\log_2e+C$ was previously known, but quite a lot easier to prove and therefore not formally published anywhere – it could perhaps be described as folklore – but to remove the factor of 2 the authors use tools such as the sunflower lemma that had not previously made an appearance in this circle of ideas.

One reason to be interested in power savings in the Brown-Erdős-Sós problem is an observation of Gowers and Long that a power saving for the $(9,5)$ problem would yield a positive solution to the following stubbornly open problem in additive combinatorics.

Problem. Do there exist constants $c, C>0$ such that for every $n$, every subset of $\{1,2,\dots,n\}$ of size at least $Cn^{1-c}$ contains distinct elements $x,y,z,w$ such that $2(x+y)=z+3w$?

A straightforward modification of the proof of Roth’s theorem yields a bound of $o(n^2)$ for this problem, but what makes the question interesting is that in the other direction it is not possible to modify the Behrend construction to give a lower bound of the form $n^{1-o(1)}$.