Hitting Arithmetic Progressions at the Square-Root Scale

For positive integers $N$ and $k$, let $f(N,k)$ be the minimum size of a set $A\subseteq \{0,1,\dots ,N-1\}$ which intersects every $k$-term arithmetic progression contained in $\{0,1,\dots ,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+\frac{1}{2}{n}^{1\mathrm{/}2}-2.$$ We improve the leading constant in the second-order term, proving $$f(n^2,n)\ge n+(\frac{1}{\sqrt{2}}+o(1))n^{1\mathrm{/}2}\mathrm{.}$$ 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-(\sqrt{\frac{2}{3}}-o(1))\sqrt{\frac{p}{\log p}}$$ for sufficiently large prime $p$. The upper bound is obtained by a randomized front construction with an alteration step.