Corner-free Subsets of Groups

Let $G$ be an abelian group. By a (non-trivial) corner in a set $A ⊆ G × G$ we mean a choice of $x, y$, and $d \ne 0$ in $G$ such that $(x, y)$, $(x + d, y)$, and $(x, y + d)$ all lie in $A$. The existence of corners in subsets $A$ of $[N]×[N]$ of positive density was first proved by Ajtai and Szemerédi in 1974, and also follows–at least qualitatively–straight from the multidimensional Szemerédi theorem.

This essay surveys the existing literature on the quantitative aspects of the problem and gives a detailed exposition of Shkredov’s upper bound on the density of corner-free sets of $\mathbb F_p^n × \mathbb F_p^n$ as set out by Green in his expository survey, as well as recent lower-bound constructions in that setting motivated by links between this problem and questions in communication complexity. In addition, the essay explains how to adapt Shkredov’s argument to prove a quantitative version of the Ajtai-Szemerédi result.