Pith. sign in

REVIEW 4 minor 20 references

Arithmetic progressions in a random set on a budget

T0 review · 0 major / 4 minor · reviewed 2026-08-01 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read An online player who sees t random integers and may keep at most b can force a k-term arithmetic progression with high probability precisely when t grows faster than n^{1-2/k} and b grows faster than (n/t)^{(k-2)/2}.

desk verdict Clean, self-contained threshold theorem for a new budgeted online AP game; both directions hold up and it deserves a real refereeing. read the letter →

arxiv 2607.21565 v1 pith:KXCEMGZW submitted 2026-07-23 math.CO math.NT

Jan Hladký , Daniel Iľkovič , Jared León , Xichao Shu This is my paper · ORCID
classification math.COmath.NT MSC 05D4011B2560C05
keywords arithmeticprogressionsrandomsubsetsonlinealgorithmbudget-constrainedprocessthresholdfirstmomentmethodtemplatesadditivecombinatorics
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

An online player who is shown t random integers from {1,...,n} and may keep at most b of them, deciding instantly whether to keep each one, wants the kept set to contain a k-term arithmetic progression. This paper proves the exact threshold: if t = ω(n^{1-2/k}), then a budget of order (n/t)^{(k-2)/2} is both necessary and sufficient. Above this budget, a simple strategy — buy every exposed number from a short initial interval — succeeds with high probability. Below it, the expected number of progressions that can be completed from the purchased elements is o(1), so every strategy fails with high probability. The result transfers the recent 'random graph on a budget' framework to integers and establishes a sharp budget threshold for an additive structure.

What carries the argument

The template induction of Claim 3.1, together with the base bound |T_2| ≤ binom(b,2)·binom(k,2) < k²b². The induction step uses the fact that, conditional on the history, a new random element can turn an access-(l-1) template into an access-l template in at most k ways, so the expected increase of |T_l| is at most k E|T_{l-1}|/n per step; summing over T = 2t steps gives E|T_l| ≤ k(T/n) E|T_{l-1}|. Iterating k-2 times yields the first-moment bound that drives the lower bound. For the upper bound, the key object is the initial interval [m] with m = bn/(2t); the strategy buys all exposed elements there, and the binomial-threshold Proposition 2.4 plus a hypergeometric budget check shows this wor

What would settle it

Compute the success probability of the best known strategy for k=3 at n=10^12, t=10^6, b=100. The theorem predicts it should be close to 0 (since b is below the predicted threshold 10^3); a success probability bounded away from 0 would indicate the converse is false, and repeating at n=10^15, t=10^7 with b=10^3 would confirm the trend.

Watch

Extended reading notes

Core claim

The central claim is Theorem 1.2: for every fixed k ≥ 3, Builder can whp construct a k-AP if and only if t = ω(n^{1-2/k}) and b = ω((n/t)^{(k-2)/2}). The sufficiency direction uses the interval strategy: set m = bn/(2t) and purchase every exposed element of [m]; whp the number purchased is below budget and the set [m]∩[n]_t contains a k-AP, by the classical threshold for binomial random subsets (Proposition 2.4). The necessity direction is a first-moment argument over 'templates'. A template is a k-AP; T_l is the set of templates with at least l purchased elements. Claim 3.1 shows E|T_l| ≤ k E|T_{l-1}| · (T/n), and since each pair of purchased elements lies in at most binom(k,2) templates, i

Load-bearing premise

The lower-bound proof assumes that any two purchased elements lie together in at most a constant (depending only on k) number of k-term arithmetic progressions; if a pair could seed many more progressions, the first-moment bound would break and a smaller budget might suffice.

Editorial extensions

If this is right

  • The threshold b ≍ (n/t)^{(k-2)/2} is necessary and sufficient for every fixed k ≥ 3, so the problem is completely settled in the o/ω sense.
  • The time constraint t = ω(n^{1-2/k}) is also necessary: below it, the exposed set itself whp contains no k-AP, regardless of budget.
  • A constructive strategy exists at the threshold: set m = bn/(2t) and purchase every exposed element in [m]; whp this stays within budget and contains a k-AP.
  • The required budget shrinks as more elements are exposed: for k=3 it is sqrt(n/t), for k=4 it is n/t, and in general the exponent (k-2)/2 grows with k.
  • The result confirms a pair-seeding heuristic: since each pair of purchased elements lies in O(1) progressions, the expected number of completable progressions is O(b²(t/n)^{k-2}), which is exactly the scale that makes the threshold non-trivial.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The template induction is pattern-agnostic: for any fixed configuration P on r points in which each pair of points lies in O(1) copies of P, the same proof would give a budget threshold b ~ (n/t)^{(r-2)/2} whenever t is above the appearance threshold for P. This is an extrapolation, not a claim of the paper.
  • The reduction from sampling without replacement to iid sampling via concentration of the number of distinct values is a reusable technique; it shows that for t = o(n), online strategies can be analysed in the simpler iid model.
  • The optimality of the simple interval strategy hints at a general principle for budgeted online construction: when the target structure is abundant in a small window, concentrating all purchases there is asymptotically optimal.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

0 major / 4 minor

Summary. The paper studies a budget-constrained online process for finding arithmetic progressions in random subsets of [n]. Builder is shown the first t elements of a uniformly random permutation of [n] and must decide immediately and irrevocably whether to purchase each element, with at most b purchases total; success means the purchased set contains a fixed-length k-AP. Theorem 1.2 states a sharp joint threshold: for k≥3, if t=ω(n^{1−2/k}) and b=ω((n/t)^{(k−2)/2}) there is a strategy that whp constructs a k-AP, while if t=o(n^{1−2/k}) or b=o((n/t)^{(k−2)/2}) every strategy whp fails. The positive direction is a simple 'buy all elements in a short initial interval' strategy analyzed with the binomial-to-uniform comparison. The negative direction first disposes of the too-few-exposed-elements case by Markov, then reduces the without-replacement process to an i.i.d. sequence of 2t draws, and bounds the expected number of 'access-k templates' in any strategy's purchased set by k^k b^2 (2t/n)^{k−2}=o(1).

Significance. The result transfers the restricted-budget random-process framework of Frieze–Krivelevich–Michaeli from graphs to additive combinatorics and determines the optimal joint scaling in the o/ω sense. The proof is self-contained: Proposition 2.4 gives the required threshold for single APs in binomial sets, and Lemma 2.5 supplies the model comparison; no hidden parameter fitting or external threshold is assumed. The structural fact the argument relies on, that any pair of elements lies in at most binom(k,2) k-APs, is correct and is used exactly where needed. The paper is concise, well written, and a clean contribution; if anything, it could be a model for future restricted-budget problems in additive combinatorics.

minor comments (4)
  1. [Abstract and Definition 1.1] The abstract says Builder is presented with 'a sequence of t integers drawn uniformly at random from [n]', which can be read as sampling with replacement. Since the process is the first t elements of a uniformly random permutation, I suggest wording such as 'the first t elements of a uniformly random permutation of [n]' to match Definition 1.1.
  2. [Theorem 1.2] The theorem states only t,b≤n, whereas Definition 1.1 has 0≤b≤t≤n. The upper-bound proof uses b≤t when setting m=bn/(2t)≤n/2, so it is worth restating the full range in the theorem for self-containedness.
  3. [§3, proof of the 1-statement] When Lemma 2.5(a) is invoked, the property used is not merely 'contains a k-AP' but 'contains a k-AP entirely inside [m]'; otherwise the AP guaranteed in [n]_t might lie outside the interval the strategy purchases. The intended property is increasing, but the sentence should say this explicitly.
  4. [§3, proof of the 0-statement] The 'subsequence principle' argument is terse. One sentence explaining that proving the failure probability is o(1) along every subsequence (after possibly passing to a further subsequence) implies the original sequence is o(1) would improve readability.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the threshold theorem is proved from self-contained first-moment and template-counting arguments, with only contextual self-citations.

full rationale

The derivation is self-contained. The 1-statement is proved by an explicit strategy: purchase all exposed elements in an initial interval [m] with m = bn/(2t). The proof that this interval contains a k-AP relies on Proposition 2.4, whose full proof is included in the paper via a Chebyshev second-moment calculation over k-APs, and on Lemma 2.5(a), also proved in the paper. The budget is checked with a hypergeometric variance bound. None of these steps assume the theorem. The 0-statement is a direct first-moment computation when t = o(n^{1-2/k}); in the budget case, the iid reduction is justified by McDiarmid's inequality, and the template-counting Claim 3.1 is an explicit induction with deterministic base |T_2| ≤ k^2 b^2. The only structural fact used, that any pair of elements lies in at most binom(k,2) k-APs, is elementary and is proved implicitly by the position-pair argument; it is not an imported result. The final bound E|T_k| = o(1) is obtained by substituting b = o((n/t)^{(k-2)/2}) into the proved inequalities. Self-citations [12], [13], and [3] concern background or related problems and are not load-bearing for Theorem 1.2. There is no fitted parameter renamed as a prediction, no uniqueness theorem imported from the authors' prior work, and no ansatz smuggled in by citation. The result can be checked entirely from the equations in the paper, so the central claim is not circular.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

The central claim rests only on standard probabilistic inequalities, the standard binomial-to-uniform comparison for increasing properties, and elementary structural facts about k-APs in [n] (Θ(n^2) progressions; a pair of elements lies in at most binom(k,2) progressions). No numbers are fitted, no entities are invented.

assumptions (4)
  • standard math Standard concentration inequalities (Chebyshev, Chernoff, McDiarmid) and hypergeometric variance bound
    Used throughout Section 3; Lemmas 2.1–2.3 and hypergeometric expectation/variance formulas.
  • standard math Number of k-APs in [n] is Θ_k(n^2); pairs of APs intersecting in one element number O_k(n^3) and in at least two elements O_k(n^2)
    Used in Proposition 2.4's second moment and in the 0-statement's first moment.
  • standard math Binomial-to-uniform comparison for increasing properties when pn→∞ (Lemma 2.5)
    Used in the 1-statement to transfer whp containment of a k-AP from [n]_p to [n]_t.
  • standard math A pair of elements of [n] is contained in at most binom(k,2) k-APs
    Base case |T_2| ≤ k²b² in Claim 3.1; load-bearing for the template-counting lower bound.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Arithmetic progressions in a random set on a budget." pith.science (2026). https://pith.science/paper/KXCEMGZW

@misc{pith2026260721565,
  author       = {Pith},
  title        = {Pith review of: Arithmetic progressions in a random set on a budget},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/KXCEMGZW}},
  note         = {Machine review of arXiv:2607.21565}
}
abstract

A restricted-budget version of the random graph process, introduced by Frieze, Krivelevich, and Michaeli in 2025, studies the construction of structures by an online player who can purchase only a limited number of random edges. In this paper, we transfer this framework from random graphs to random subsets of integers, focusing on the construction of $k$-term arithmetic progressions. A player, Builder, is presented with a sequence of $t$ integers drawn uniformly at random from $[n]$. As the elements are revealed one by one, Builder must immediately and irrevocably decide whether to select the current integer, subject to a maximum budget of $b$ selected elements in total. We establish the optimal thresholds for this process, proving that for $t = \omega(n^{1-2/k})$, a budget of $b = \Theta((n/t)^{\frac{k-2}{2}})$ is both necessary and sufficient for Builder to successfully construct a $k$-term arithmetic progression with high probability.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

20 extracted references · 12 canonical work pages

  1. [1]

    Ajtai, J

    M. Ajtai, J. Komlós, and E. Szemerédi. First occurrence of hamilton cycles in random graphs. Cycles in graphs, Workshop Simon Fraser Univ., Burnaby/Can. 1982, Ann. Discrete Math. 27, 173-178, 1985. doi:10.1016/S0304-0208(08)73007-X

    work page doi:10.1016/s0304-0208(08)73007-x 1982

  2. [2]

    M. Anastos. Constructing hamilton cycles and perfect matchings efficiently (extended abstract). InPro- ceedings of the 12th European conference on combinatorics, graph theory and applications. EUROCOMB’23, Prague, August 28 – September 1, pages 36–41. Brno: Masaryk University, 2023.doi:10.5817/CZ.MUNI. EUROCOMB23-005

    doi:10.5817/cz.muni 2023

  3. [3]

    Antoniuk, A

    S. Antoniuk, A. E. Díaz, K. Petrova, and M. Stojaković. On constructing small subgraphs in the budget- constrained random graph process. Preprint, arXiv:2602.18325 [math.CO], 2026.doi:10.48550/arXiv. 2602.18325

    work page doi:10.48550/arxiv.2602.18325 2026

  4. [4]

    Bollobás

    B. Bollobás. The evolution of sparse graphs. Graph theory and combinatorics, Proc. Conf. Hon. P. Erdős, Cambridge 1983, 35-37, 1984

    1983

  5. [5]

    Random graphs., volume 73 ofCamb. Stud. Adv. Math.Cambridge: Cambridge University Press, 2001.doi:10.1017/CBO9780511814068

    doi:10.1017/cbo9780511814068 2001

  6. [6]

    Bollobás and A

    B. Bollobás and A. Thomason. Random graphs of small order. Random graphs ’83, Lect. 1st Semin., Poz- nań/Pol. 1983, Ann. Discrete Math. 28, 47-97, 1985.doi:10.1016/S0304-0208(08)73612-0. ARITHMETIC PROGRESSIONS IN A RANDOM SET ON A BUDGET 7

    doi:10.1016/s0304-0208(08)73612-0 1983

  7. [7]

    Conlon and W

    D. Conlon and W. T. Gowers. Combinatorial theorems in sparse random sets.Ann. Math. (2), 184:367–454, 2016.doi:10.4007/annals.2016.184.2.2

    work page doi:10.4007/annals.2016.184.2.2 2016

  8. [8]

    Erdős and A

    P. Erdős and A. Rényi. On the evolution of random graphs.Publ. Math. Inst. Hung. Acad. Sci., Ser. A, 5:17–61, 1960. URL:https://users.renyi.hu/~p_erdos/1960-10.pdf

    1960

Show all 20 references
  1. [9]

    On the existence of a factor of degree one of a connected random graph.Acta Math. Acad. Sci. Hung., 17:359–368, 1966.doi:10.1007/BF01894879

    1966 doi

  2. [10]

    Espuni Díaz, F

    A. Espuni Díaz, F. Garbe, T. Naia, and Z. Smith. Graph factors and powers of hamilton cycles in the budget-constrained random graph process. Preprint, arXiv:2502.20870 [math.CO], 2026.doi:10.48550/ arXiv.2502.20870

    2026 doi arXiv

  3. [11]

    Frieze and M

    A. Frieze and M. Karoński.Introduction to random graphs. Cambridge: Cambridge University Press, 2016. doi:10.1017/CBO9781316339831

    2016 doi

  4. [12]

    Frieze, M

    A. Frieze, M. Krivelevich, and P. Michaeli. Fast construction on a restricted budget.Random Struct. Algo- rithms, 67:article id e70031, 26 p., 2025.doi:10.1002/rsa.70031

    2025 doi

  5. [13]

    Iľkovič, J

    D. Iľkovič, J. León, and X. Shu. Multi-cyclic graphs in the random graph process with restricted budget. Preprint, arXiv:2412.17620 [math.CO], 2024.doi:10.48550/arXiv.2412.17620

    2024 doi arXiv

  6. [14]

    Janson, T

    S. Janson, T. Łuczak, and A. Ruciński.Random graphs. Wiley-Intersci. Ser. Discrete Math. Optim. New York, NY: Wiley, 2000.doi:10.1002/9781118032718

    doi

  7. [15]

    Katsamaktsis and S

    K. Katsamaktsis and S. Letzter. Building graphs with high minimum degree on a budget.Eur. J. Comb., 129:article id 104119, 14 p., 2025.doi:10.1016/j.ejc.2025.104119

    2025

  8. [16]

    Kohayakawa, T

    Y. Kohayakawa, T. Łuczak, and V. Rödl. Arithmetic progressions of length three in subsets of a random set. Acta Arith., 75:133–163, 1996.doi:10.4064/aa-75-2-133-163

    1996 doi

  9. [17]

    Lichev.d-connectivity of the random graph with restricted budget.J

    L. Lichev.d-connectivity of the random graph with restricted budget.J. Graph Theory, 108:293–312, 2025. doi:10.1002/jgt.23180

    2025 doi

  10. [18]

    K. F. Roth. On certain sets of integers.J. Lond. Math. Soc., 28:104–109, 1953.doi:10.1112/jlms/s1-28. 1.104

    1953 doi

  11. [19]

    M. Schacht. Extremal results for random discrete structures.Ann. Math. (2), 184:333–365, 2016.doi: 10.4007/annals.2016.184.2.1

    2016 doi

  12. [20]

    Szemerédi

    E. Szemerédi. On sets of integers containing nokelements in arithmetic progression.Acta Arith., 27:199–245, 1975.doi:10.4064/aa-27-1-199-245

    1975 doi

Pith tools

Reviewed August 1, 2026 · model on record in the stance chip above.