Hitting Arithmetic Progressions at the Square-Root Scale
Fuente:
arXiv
Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866913178125860864 |
|---|---|
| author | Korsky, Samuel |
| author_facet | Korsky, Samuel |
| contents | For positive integers $N$ and $k$, let $f(N,k)$ be the minimum size of a set $A\subseteq\{0,1,\ldots,N-1\}$ which intersects every $k$-term arithmetic progression contained in $\{0,1,\ldots,N-1\}$. Brown and Freedman introduced this hitting problem for arithmetic progressions and studied it for growing $k$. The square-root scale $k=\sqrt N$ is a natural transition point. Truss proved \[
f(n^2,n)>n+\frac12 n^{1/2}-2. \] We improve the leading constant in the second-order term, proving \[
f(n^2,n)\ge n+\left(\frac1{\sqrt2}+o(1)\right)n^{1/2}. \] On the upper-bound side, Brown and Freedman proved $f(p^2,p)\le 2p-2$ for odd primes $p$, and subsequent Szekeres-type constructions give logarithmic savings. We prove the stronger asymptotic upper bound \[
f(p^2,p)
\le
2p-\left(\sqrt{\frac23}-o(1)\right)\sqrt{\frac p{\log p}} \] for sufficiently large prime $p$. The upper bound is obtained by a randomized front construction with an alteration step. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2606_01780 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Hitting Arithmetic Progressions at the Square-Root Scale Korsky, Samuel Combinatorics Number Theory For positive integers $N$ and $k$, let $f(N,k)$ be the minimum size of a set $A\subseteq\{0,1,\ldots,N-1\}$ which intersects every $k$-term arithmetic progression contained in $\{0,1,\ldots,N-1\}$. Brown and Freedman introduced this hitting problem for arithmetic progressions and studied it for growing $k$. The square-root scale $k=\sqrt N$ is a natural transition point. Truss proved \[ f(n^2,n)>n+\frac12 n^{1/2}-2. \] We improve the leading constant in the second-order term, proving \[ f(n^2,n)\ge n+\left(\frac1{\sqrt2}+o(1)\right)n^{1/2}. \] On the upper-bound side, Brown and Freedman proved $f(p^2,p)\le 2p-2$ for odd primes $p$, and subsequent Szekeres-type constructions give logarithmic savings. We prove the stronger asymptotic upper bound \[ f(p^2,p) \le 2p-\left(\sqrt{\frac23}-o(1)\right)\sqrt{\frac p{\log p}} \] for sufficiently large prime $p$. The upper bound is obtained by a randomized front construction with an alteration step. |
| title | Hitting Arithmetic Progressions at the Square-Root Scale |
| topic | Combinatorics Number Theory |
| url | https://arxiv.org/abs/2606.01780 |