Strong Bounds for Skew-Corner-Free Sets
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866908562274385920 |
|---|---|
| author | Jaber, Michael Lovett, Shachar Ostuni, Anthony |
| author_facet | Jaber, Michael Lovett, Shachar Ostuni, Anthony |
| contents | 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(-Ω(\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ćević (arXiv'24). |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_07380 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Strong Bounds for Skew-Corner-Free Sets Jaber, Michael Lovett, Shachar Ostuni, Anthony Combinatorics Number Theory 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(-Ω(\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ćević (arXiv'24). |
| title | Strong Bounds for Skew-Corner-Free Sets |
| topic | Combinatorics Number Theory |
| url | https://arxiv.org/abs/2404.07380 |