Strong bounds for skew corner-free sets
| Autor: | Jaber, Michael, Lovett, Shachar, Ostuni, Anthony |
|---|---|
| Rok vydání: | 2024 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | Motivated by applications to matrix multiplication algorithms, Pratt asked (ITCS'24) how large a subset of $[n] \times [n]$ could be without containing a skew-corner: three points $(x,y), (x,y+h),(x+h,y')$ with $h \ne 0$. We prove any skew corner-free set has size at most $\exp(-\Omega(\log^{1/12} n))\cdot n^2$, nearly matching the best known lower bound of $\exp(-O(\sqrt{\log n}))\cdot n^2$ by Beker (arXiv'24). Our techniques generalize those of Kelley and Meka's recent breakthrough on three-term arithmetic progression (FOCS'23), answering a question of Beker (arXiv'24). We note that a similar bound was obtained concurrently and independently by Mili\'cevi\'c (arXiv'24). Comment: 23 pages, comments welcome |
| Databáze: | arXiv |
| Externí odkaz: |
|