Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2310.13999 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
Table of Contents:
- We consider the local properties problem for difference sets: we define $g(n, k, \ell)$ to be the minimum value of $\lvert A - A\rvert$ over all $n$-element sets $A \subseteq \mathbb{R}$ with the `local property' that $\lvert A' - A'\rvert \geq \ell$ for all $k$-element subsets $A' \subseteq A$. We view $k$ and $\ell$ as fixed, and study the asymptotic behavior of $g(n, k, \ell)$ as $n \to \infty$. One of our main results concerns the quadratic threshold, i.e., the minimum value of $\ell$ such that $g(n, k, \ell) = Ω(n^2)$; we determine this value exactly for even $k$, and we determine it up to an additive constant for odd $k$. We also show that for all $1 < c \leq 2$, the `threshold' for $g(n, k, \ell) = Ω(n^c)$ is quadratic in $k$; conversely, for $\ell$ quadratic in $k$, we obtain upper and lower bounds of the form $n^c$ for (not necessarily equal) constants $c > 1$. In particular, this provides the first nontrivial upper bounds in the regime where $\ell$ is quadratic in $k$.