{"id":"a171f986-1f26-4613-a113-184ffc7bcf96","arxiv_id":"2607.21565","paper_version":1,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"With t random integers revealed, buying Θ((n/t)^((k−2)/2)) of them is necessary and sufficient to guarantee a k-term arithmetic progression when t ≫ n^(1−2/k).","lead":"This paper finds the exact budget a builder needs to secure a k-term arithmetic progression when integers are revealed one by one at random. The result gives the same simple formula for every length k, matching the point where random sets first contain such progressions.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified.","rationale":"The paper proves a clean threshold with standard first/second moment and online first-moment arguments. I checked the three load-bearing estimates: (1) Proposition 2.4's variance computation; (2) the positive-part coupling and budget control; (3) the iid reduction and template induction. All are consistent. The theorem's o/ω threshold leaves the boundary case t=Θ(n^{1-2/k}) untreated, but this is normal for such statements and not a correctness issue since at that scale even buying all t elements succeeds only with O(1) probability. The reader's ACCEPT verdict is supported; no adjustment is needed.","tokens_in":7569,"tokens_out":20690,"duration_ms":178822,"concrete_test":"Enumerate all pairs {x,y} in [n] for n=100 and k=3,4,5 and count the number of k-APs in [n] containing both; verify the maximum is at most binom(k,2). If any pair exceeds this, the base case |T_2| ≤ k^2 b^2 of Claim 3.1 fails and the lower-bound threshold would need revisiting; if not, the key structural assumption is confirmed.","verdict_should_be":"UNCHANGED","load_bearing_attack":"I read the full argument in good faith and found no load-bearing flaw. The reader's flagged weakest assumption — that any pair of elements lies in at most binom(k,2) k-APs — is correct: for each ordered choice of positions i<j within a k-AP, the common difference is forced to (y-x)/(j-i), so at most one AP per position pair. This validates both the variance bound in Proposition 2.4 (pairs of APs sharing ≥2 elements are O(n^2)) and the deterministic base |T_2| ≤ k^2 b^2 in Claim 3.1. The induction step in Claim 3.1 is sound: a template becomes access-l only by receiving one of at most k remaining elements, and T_{l-1}(s-1) ⊆ T_{l-1} justifies the summation. The exponents match: with b=o((n/t)^{(k-2)/2}) and T=2t, E|T_k| ≤ k^k b^2 (T/n)^{k-2} = o(1). The iid reduction is justified because b≥1 together with b=o((n/t)^{(k-2)/2}) forces t=o(n), making EY ≥ 3t/2 and P(Y<t)=exp(-t/4)=o(1). The positive part's coupling is exact: t = 2pn, so Lemma 2.5(a) applies to the increasing property 'contains a k-AP inside [m]'. No hidden circularity or unsupported parameter was found.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","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).","tokens_in":7924,"tokens_out":29689,"duration_ms":269076,"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.","major_comments":[],"minor_comments":[{"comment":"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.","section":"Abstract and Definition 1.1"},{"comment":"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.","section":"Theorem 1.2"},{"comment":"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.","section":"§3, proof of the 1-statement"},{"comment":"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.","section":"§3, proof of the 0-statement"}],"recommendation":"accept","confidential_remarks":"I agree with the reader's report. After checking the central second-moment and template-counting arguments, I found no load-bearing flaw. The minor wording issues can be fixed without another round of external review; I recommend acceptance."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Punchline: this is a clean, self-contained threshold theorem for a new budgeted online selection problem, and it holds up under scrutiny. The reader's verdict is right: both directions of Theorem 1.2 are proved correctly, the key structural fact (a pair of points lies in O_k(1) k-APs) is used exactly where needed, and there is no circularity or hidden parameter fitting.\n\nWhat's new: the paper transfers Frieze–Krivelevich–Michaeli's restricted-budget framework from graphs to arithmetic progressions, and pins down the optimal budget scale b ≈ (n/t)^((k-2)/2) for t above the single-AP threshold n^{1-2/k}. The proof is short and to the point: the 1-statement uses a simple buy-from-[m] strategy with Chernoff/Chebyshev and a binomial-to-uniform comparison; the 0-statement uses a first-moment count over partial AP templates, with an inductive claim that propagates the expectation bound from pairs up to full APs. The iid reduction in the lower bound is handled carefully with McDiarmid.\n\nThe soft spots are minor. The abstract says b = Θ(...) while the theorem is stated as ω/o; that's fine, but a reader might want the abstract to say 'critical scale' rather than using Θ loosely. The notation T for the total steps and T_l for template sets is a bit overused. Proposition 2.4's variance proof is standard and slightly terse—an extra line on why the overlap counts are O(n^3) and O(n^2) would help. None of this affects correctness.\n\nThe weakest assumption flagged by the reader is actually solid: for each ordered position pair in a k-AP, the common difference is forced, so any pair of purchased elements seeds at most binom(k,2) templates. The stress-test confirms this, and the induction step in Claim 3.1 is sound.\n\nWho it's for: anyone working on budget-constrained random processes or additive combinatorics in random sets. It's a niche but useful result, a natural extension rather than a paradigm shift. The citation pattern looks honest, and the paper is self-contained. I would send it to a competent referee; it will likely be accepted after minor revision.","headline":"Clean, self-contained threshold theorem for a new budgeted online AP game; both directions hold up and it deserves a real refereeing.","tokens_in":8402,"tokens_out":3157,"would_cite":true,"duration_ms":29376,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05D40","11B25","60C05"],"pacs":[],"model":"deepseek-v4-flash","headline":"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}.","keywords":["arithmetic progressions","random subsets","online algorithm","budget-constrained process","threshold","first moment method","templates","additive combinatorics"],"falsifier":"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.","tokens_in":7506,"feed_emoji":"🔢","tokens_out":13063,"duration_ms":106582,"temperature":0.7,"pith_summary":"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.","feed_headline":"Force a k-term progression with b ~ (n/t)^((k-2)/2) picks","feed_subtitle":"Asymptotically, an online buyer needs roughly this many picks to force a k-term progression from t random numbers.","key_machinery":"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","core_discovery":"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","pith_inferences":["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."],"forward_implications":["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."],"fun_headline_variants":["Forcing k-APs costs ~ (n/t)^((k-2)/2) picks","Budget for forcing k-AP: ~ (n/t)^((k-2)/2) picks","To force a k-AP, buy only ~ (n/t)^((k-2)/2) numbers","Optimal budget for forcing k-term APs from random numbers"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Forcing k-APs costs ~ (n/t)^((k-2)/2) picks","Budget for forcing k-AP: ~ (n/t)^((k-2)/2) picks","To force a k-AP, buy only ~ (n/t)^((k-2)/2) numbers","Optimal budget for forcing k-term APs from random numbers"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001686,"raw_usage":{"total_tokens":6535,"prompt_tokens":777,"completion_tokens":5758,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":521,"completion_tokens_details":{"reasoning_tokens":5661}},"tokens_in":521,"tokens_out":5758,"duration_ms":39731,"temperature":1.0,"reasoning_tokens":5661,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-01T07:03:05.064819+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[],"review_version":1}