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 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] × [N]. Extending this definition to higher dimensions, a k-dimensional corner in [N]^k is a (k+1)-tuple defined similarly. It is known that corner-free sets have a vanishingly small density, but the precise bounds on their size are 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.
In our recent work 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.