Exponents in the local properties problem for difference sets have a gap at 2
Fuente:
arXiv
Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866909461089615872 |
|---|---|
| author | Das, Sanjana |
| author_facet | Das, Sanjana |
| contents | We study the local properties problem for difference sets: If we have a large set of real numbers and know that every small subset has many distinct differences, to what extent must the entire set have many distinct differences? More precisely, we define $g(n, k, \ell)$ to be the minimum number of differences in an $n$-element set with the `local property' that every $k$-element subset has at least $\ell$ differences; we study the asymptotic behavior of $g(n, k, \ell)$ as $k$ and $\ell$ are fixed and $n \to \infty$.
The quadratic threshold is the smallest $\ell$ (as a function of $k$) for which $g(n, k, \ell) = Ω(n^2)$; its value is known when $k$ is even. In this paper, we show that for $k$ even, when $\ell$ is one below the quadratic threshold, we have $g(n, k, \ell) = O(n^c)$ for an absolute constant $c < 2$ -- i.e., at the quadratic threshold, the `exponent of $n$ in $g(n, k, \ell)$' jumps by a constant independent of $k$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_11148 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Exponents in the local properties problem for difference sets have a gap at 2 Das, Sanjana Combinatorics 05D40 We study the local properties problem for difference sets: If we have a large set of real numbers and know that every small subset has many distinct differences, to what extent must the entire set have many distinct differences? More precisely, we define $g(n, k, \ell)$ to be the minimum number of differences in an $n$-element set with the `local property' that every $k$-element subset has at least $\ell$ differences; we study the asymptotic behavior of $g(n, k, \ell)$ as $k$ and $\ell$ are fixed and $n \to \infty$. The quadratic threshold is the smallest $\ell$ (as a function of $k$) for which $g(n, k, \ell) = Ω(n^2)$; its value is known when $k$ is even. In this paper, we show that for $k$ even, when $\ell$ is one below the quadratic threshold, we have $g(n, k, \ell) = O(n^c)$ for an absolute constant $c < 2$ -- i.e., at the quadratic threshold, the `exponent of $n$ in $g(n, k, \ell)$' jumps by a constant independent of $k$. |
| title | Exponents in the local properties problem for difference sets have a gap at 2 |
| topic | Combinatorics 05D40 |
| url | https://arxiv.org/abs/2501.11148 |