16
$\begingroup$

The corners theorem of Ajtai and Szemerédi states that if $A\subseteq[N]^2$ is corner-free, i.e. there are no $x,y,h\in\mathbb{N}$ with all of $(x,y),(x+h,y),(x,y+h)$ in $A$, then $|A|=o(N^2)$. The standard proof of this theorem is to apply the triangle removal lemma that follows from Szemerédi's graph regularity lemma. The theorem is particularly useful because it implies Roth's theorem, which can also be proven directly using the regularity lemma.

If we let $r_3(S)$ be the maximum size of a subset of $S$ that is $3$-AP free, and $r_\angle(S)$ be the same except for corner-free, then Roth's theorem becomes $r_3([N])=o(N)$ and the corners theorem becomes $r_\angle([N])=o(N^2)$. The inequality $r_3([N])\leq\frac{r_\angle([N])}{N}$ shows that the corners theorem implies Roth's theorem.

The finite field setting $\mathbb{F}_p^n$ (with size $N=p^n$) is often used as a "sandbox" for applying methods to integers before applying them directly on the integers. For example, we have a similar theorem that $r_3(\mathbb{F}_p^n)=O(\frac{N}{\log N})$, which can be proven using Fourier analysis. This Fourier proof of Roth's theorem for finite fields can be modified to prove Roth's theorem over $\mathbb{N}$.

The inequality $r_3(\mathbb{F}_p^n)\leq\frac{r_\angle(\mathbb{F}_p^n)}{N}$ still holds, so a corners theorem for finite fields of the form $r_\angle(\mathbb{F}_p^n)=O(\frac{N^2}{\log N})$ would imply Roth's theorem for finite fields. Is there a known result of this form? I might expect such a proof to come in a Fourier form, similar to how the stronger version of Roth's theorem can be proven in a similar method. Perhaps such a Fourier proof would also produce a Fourier proof of the corners theorem over $\mathbb{N}$.

Even stronger, is there a known result of the form $r_\angle(\mathbb{F}_p^n)=O(c^{2n})$ for some $c<p$? This would, for the same reasons, imply that $r_3(\mathbb{F}_p^n)=O(c^n)$ for some $c<p$ (which is the subject of the cap set problem, resolved via the Croot-Lev-Pach polynomial method).

$\endgroup$
1
  • 3
    $\begingroup$ The question in your last paragraph attracts a lot of attention but is still open, as far as I know. $\endgroup$ Commented Dec 15, 2019 at 3:46

1 Answer 1

10
$\begingroup$

Concerning your second question

...is there a known result of the form $r_\angle(\mathbb{F}_p^n)=O(c^{2n})$ for some $c<p$? This would, for the same reasons, imply that $r_3(\mathbb{F}_p^n)=O(c^n)$ for some $c<p$ (which is the subject of the cap set problem, resolved via the Croot-Lev-Pach polynomial method).

Not only is this not known, it is known that the methods that work for the cap set problem do not work for the corner-free problem. That is, a slice-rank based proof is impossible. The reason is that the slice-rank applies generally to upper bound induced matchings, and there are large induced matchings in this graph.

Indeed, see Theorem 8 of this paper by Christandl, Fawzi, Ta, and Zuiddam:

Theorem: For any abelian group $G$, the hypergraph $H^{\boxtimes n}_{\text{corner},G}$ has an induced matching of size $|G|^{2n-o(n)}$.

This implies that the slice-rank of any tensor that "fits" the corner problem over $\mathbb{F}_p$ is always maximal, so no direct slice-rank proof is possible.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .