Abstract
A central question in additive combinatorics is to understand how large arithmetic progression-free sets can be. In this talk, I will focus on this question for high-dimensional generalization of arithmetic progressions (AP) known as \textit{corners}. A (2-dimensional) corner is a triple of the form $(x,y),(x+d,y),(x,y+d)$ for some $d>0$ in $[N] \times [N]$. Extending this definition to higher dimensions, a $k$-dimensional corner in $[N]^k$ is a $(k+1)$-tuple defined similarly for some $d$. While it is known that corner-free sets have a vanishingly small density, the precise bounds on their size remain unknown. Until recently, the best-known corner-free sets were derived from constructions of AP-free sets: a construction of a $3$-term AP-free set by Behrend from 1946, and a generalization by Rankin for $k$-term APs in 1961. New results by Linial and Shraibman (CCC 2021) and Green (New Zealand Journal of Mathematics 2021) changed this picture; they improved the upper bound for $k=2$ by adopting a communication complexity point of view.
I will discuss our recent work where we employ the same perspective of communication complexity and obtain the first improvement on the upper bound of the size of high-dimensional ($k>2$) corner-free sets since the original construction of Rankin.
Based on joint work with Toniann Pitassi, Suhail Sherif, Morgan Shirley, and Adi Shraibman.