pith. sign in

arxiv: 2606.01780 · v1 · pith:WR533EHUnew · submitted 2026-06-01 · 🧮 math.CO · math.NT

Hitting Arithmetic Progressions at the Square-Root Scale

Samuel Korsky This is my paper

Pith reviewed 2026-06-28 14:13 UTC · model grok-4.3

classification 🧮 math.CO math.NT
keywords arithmetic progressionshitting setsf(N,k)square-root scalerandomized constructionalteration methodlower boundsupper bounds
0
0 comments X

The pith

f(n²,n) ≥ n + (1/√2 + o(1)) n^{1/2} and f(p²,p) ≤ 2p - (√(2/3) - o(1)) √(p/log p) for large primes p

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper studies the smallest set A that intersects every k-term arithmetic progression inside the interval from 0 to N-1, with focus on the transition regime k ≈ √N. It improves the known lower bound on this minimal size f(n²,n) by lifting the second-order coefficient from 1/2 to 1/√2. For upper bounds it shows that when N is a prime square the minimal size can be reduced below the previous 2p-2 by a term of order √(p/log p) rather than a logarithmic term. A reader would care because the square-root scale is where earlier deterministic constructions stop giving sharp second-order information.

Core claim

Truss proved f(n²,n) > n + (1/2)n^{1/2} - 2. The paper raises the leading constant in the second term to 1/√2 + o(1). Brown and Freedman showed f(p²,p) ≤ 2p - 2; later Szekeres-type constructions gave only logarithmic savings. The paper obtains the stronger upper bound f(p²,p) ≤ 2p - (√(2/3) - o(1)) √(p/log p) for large primes p by a randomized front construction followed by an alteration step.

What carries the argument

The minimal hitting-set size f(N,k) for k-term arithmetic progressions inside [0,N), with the lower bound obtained by direct counting and the upper bound obtained by randomized front construction plus alteration

If this is right

  • Any hitting set for n-term APs inside [0,n²) must have size at least n + (1/√2)√n asymptotically.
  • Hitting sets for p-term APs inside [0,p²) exist whose size is 2p minus nearly √(2/3) √(p/log p).
  • The square-root scale admits both a linear leading term and a non-trivial second-order correction in both directions.
  • The alteration step removes conflicting elements while retaining most of the size reduction produced by the random front.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The numerical constants 1/√2 and √(2/3) may be improvable by refined counting or different random models.
  • The randomized-front method could extend to composite N if analogous 'fronts' can be defined without primality.
  • The persistent factor-of-two gap between the √N-scale lower bound and the 2√N-scale upper bound suggests examining whether the true order of f(N,√N) lies closer to one or the other.

Load-bearing premise

The probabilistic analysis of the randomized front construction with alteration step produces a positive-probability outcome that yields the stated savings.

What would settle it

Explicit computation or estimation of f(p²,p) for a sequence of large primes p to check whether 2p - f(p²,p) grows like √(2/3) √(p/log p).

read the original abstract

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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 0 minor

Summary. The manuscript defines f(N,k) as the minimal size of a hitting set for all k-term arithmetic progressions inside {0,…,N−1}. It proves the improved lower bound f(n²,n) ≥ n + (1/√2 + o(1))n^{1/2} (strengthening Truss) via a direct counting argument and the upper bound f(p²,p) ≤ 2p − (√(2/3)−o(1))√(p/log p) for large primes p, obtained from a randomized front construction followed by an alteration step that removes one element per surviving AP.

Significance. If the upper-bound construction succeeds, the result supplies a super-logarithmic saving of order √(p/log p) over the trivial 2p construction, improving on prior Szekeres-type logarithmic savings; the lower bound improves the leading constant in the second-order term from 1/2 to 1/√2. The lower bound is a direct counting argument with no circularity and the upper bound employs an independent randomized procedure; both features strengthen the contribution if the probabilistic estimates are verified.

major comments (1)
  1. [upper-bound method] Upper-bound construction (abstract and the section describing the randomized front + alteration method): the claim that the procedure yields a positive-probability outcome with net saving (√(2/3)−o(1))√(p/log p) after alteration rests on the initial random savings exceeding the expected alteration cost by the full term; the manuscript provides no explicit error-term controls, dependence analysis between the random choices and the surviving APs, or verification that the number of surviving APs is not underestimated. This calculation is load-bearing for the stated asymptotic upper bound.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the detailed report and for identifying the need for stronger probabilistic controls in the upper-bound argument. We address the single major comment below and will revise the manuscript to incorporate the requested clarifications.

read point-by-point responses

  1. Referee: [upper-bound method] Upper-bound construction (abstract and the section describing the randomized front + alteration method): the claim that the procedure yields a positive-probability outcome with net saving (√(2/3)−o(1))√(p/log p) after alteration rests on the initial random savings exceeding the expected alteration cost by the full term; the manuscript provides no explicit error-term controls, dependence analysis between the random choices and the surviving APs, or verification that the number of surviving APs is not underestimated. This calculation is load-bearing for the stated asymptotic upper bound.

    Authors: We agree that the current write-up of the randomized front construction and alteration step lacks sufficiently explicit error-term controls and a full dependence analysis. In the revised manuscript we will expand the relevant section to include: (i) explicit bounds on the variance and concentration of the initial random savings, (ii) a careful accounting of the dependence between the random front choices and the set of surviving APs (via a suitable martingale or limited-dependence argument), and (iii) a rigorous upper bound on the number of surviving APs that does not rely on underestimation. These additions will verify that the net saving of (√(2/3)−o(1))√(p/log p) occurs with positive probability for large primes p. We view this as a clarification rather than a change in the underlying argument. revision: yes

Circularity Check

0 steps flagged

No circularity; lower bound by direct counting, upper bound by independent randomized construction

full rationale

The claimed lower bound improves Truss's earlier result via a direct counting argument on the size of a hitting set. The upper bound is an existence result obtained from a randomized front construction followed by an alteration step; the probabilistic analysis is an independent calculation that does not reduce the final bound to a quantity defined in terms of itself. No self-citations are load-bearing for the main claims, no parameters are fitted and then renamed as predictions, and no ansatz or uniqueness theorem is smuggled in via prior work by the same author. The derivation chain is self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The paper relies on standard facts from combinatorics and the probabilistic method; no free parameters, ad-hoc axioms, or new entities are introduced.

axioms (2)
  • standard math Standard counting and union-bound arguments apply to arithmetic progressions
    Invoked implicitly in both the lower-bound counting and the upper-bound probabilistic construction.
  • standard math The probabilistic method guarantees existence when a random object has positive probability of satisfying the desired property
    Used to establish the upper bound via the randomized front construction.

pith-pipeline@v0.9.1-grok · 5768 in / 1263 out tokens · 28788 ms · 2026-06-28T14:13:46.408303+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

11 extracted references · 8 canonical work pages · 1 internal anchor

  1. [1]

    F. A. Behrend,On sequences of integers containing no arithmetic progression, ˇCasopis Pˇ est. Mat. Fys.67(1938), 235–239. EuDML

    1938

  2. [2]

    T. F. Bloom and O. Sisask,An improvement to the Kelley–Meka bounds on three-term arith- metic progressions, arXiv:2309.02353. 14

    work page arXiv

  3. [3]

    T. C. Brown and A. R. Freedman,Small sets which meet all thek(n)-term arithmetic progres- sions in the interval[1, n], J. Combin. Theory Ser. A51(1989), 244–249. doi:10.1016/0097- 3165(89)90049-6; author PDF

    work page doi:10.1016/0097- 1989

  4. [4]

    W. T. Gowers,A new proof of Szemer´ edi’s theorem, Geom. Funct. Anal.11(2001), 465–588. doi:10.1007/s00039-001-0332-9

    work page doi:10.1007/s00039-001-0332-9 2001

  5. [5]

    Kelley and R

    Z. Kelley and R. Meka,Strong bounds for3-progressions, Proceedings of the 64th IEEE Sym- posium on Foundations of Computer Science, 2023, 933–973; arXiv:2302.05537

    work page arXiv 2023

  6. [6]

    J. Leng, A. Sah, and M. Sawhney,Improved bounds for Szemer´ edi’s theorem, arXiv:2402.17995

    work page arXiv

  7. [7]

    Sets of integers that do not contain long arithmetic progressions

    K. O’Bryant,Sets of integers that do not contain long arithmetic progressions, Electron. J. Combin.18(2011), no. 1, Paper 59. doi:10.37236/546; arXiv:0811.3057

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.37236/546 2011

  8. [8]

    R. A. Rankin,Sets of integers containing not more than a given number of terms in arithmetical progression, Proc. Roy. Soc. Edinburgh Sect. A65(1960), 332–344. Cambridge Core

    1960

  9. [9]

    Szemer´ edi,On sets of integers containing nokelements in arithmetic progression, Acta Arith.27(1975), 199–245

    E. Szemer´ edi,On sets of integers containing nokelements in arithmetic progression, Acta Arith.27(1975), 199–245. EuDML

    1975

  10. [10]

    J. K. Truss,Small sets which meet all then-term arithmetic progressions in the interval[1, n 2], Bull. London Math. Soc.23(1991), 123–127. doi:10.1112/blms/23.2.123

    work page doi:10.1112/blms/23.2.123 1991

  11. [11]

    Xu,A generalization of sets without long arithmetic progressions based on Szekeres algo- rithm, J

    X. Xu,A generalization of sets without long arithmetic progressions based on Szekeres algo- rithm, J. Number Theory133(2013), 3670–3677. doi:10.1016/j.jnt.2013.05.008. 15

    work page doi:10.1016/j.jnt.2013.05.008 2013