Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2405.09402 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913351583399936 |
|---|---|
| author | Shapira, Asaf |
| author_facet | Shapira, Asaf |
| contents | A linear equation $E$ is said to be sparse if there is $c>0$ so that every subset of $[n]$ of size $n^{1-c}$ contains a solution of $E$ in distinct integers. The problem of characterizing the sparse equations, first raised by Ruzsa in the 90's, is one of the most important open problems in additive combinatorics. We say that $E$ in $k$ variables is abundant if every subset of $[n]$ of size $\varepsilon n$ contains at least poly$(\varepsilon)\cdot n^{k-1}$ solutions of $E$. It is clear that every abundant $E$ is sparse, and Girão, Hurley, Illingworth and Michel asked if the converse implication also holds. In this note we show that this is the case for every $E$ in $4$ variables. We further discuss a generalization of this problem which applies to all linear equations. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_09402 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A Generalization of Varnavides's Theorem Shapira, Asaf Combinatorics A linear equation $E$ is said to be sparse if there is $c>0$ so that every subset of $[n]$ of size $n^{1-c}$ contains a solution of $E$ in distinct integers. The problem of characterizing the sparse equations, first raised by Ruzsa in the 90's, is one of the most important open problems in additive combinatorics. We say that $E$ in $k$ variables is abundant if every subset of $[n]$ of size $\varepsilon n$ contains at least poly$(\varepsilon)\cdot n^{k-1}$ solutions of $E$. It is clear that every abundant $E$ is sparse, and Girão, Hurley, Illingworth and Michel asked if the converse implication also holds. In this note we show that this is the case for every $E$ in $4$ variables. We further discuss a generalization of this problem which applies to all linear equations. |
| title | A Generalization of Varnavides's Theorem |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2405.09402 |