{"id":"ad89b465-b1cc-4304-bec6-796e452a3b4b","arxiv_id":"2607.26450","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"The shortest guaranteed interval for distinct multiples of the numbers 1..n is at least n·exp((1/50)log n/loglog n) and at most n^1.4031, with the prime-only version between the same lower bound and n^{7/5}/(log n)^{2/5}.","lead":"This paper narrows the known range for how long a run of consecutive integers must be to contain one distinct multiple for each number up to n. It improves four prior bounds and disproves a recent conjecture that about n log n numbers would suffice.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 4.1's size bound uses k^{-10}W where only k^{-11}W is justified; the passage to W^{t(1-ε)} needs exponent comparison, but the stronger bound repairs it.","rationale":"The reader's weakest_assumption correctly identifies the Lemma 4.1 size-bound passage as the most load-bearing gap. If |A_t| were larger than W^{t(1−ε)}, the inequality |U|<|P| in Section 4 would fail and the Hall-violation argument for Theorem 1.2 would collapse. The concern is real as a matter of exposition/rigor because the proof as written does not justify the step from k^{-10}W to W^{t(1−ε)}. But it is not a fatal flaw: the same estimates yield the stronger |S|≤k^{-11}W, which makes the desired bound true. This is exactly the kind of fixable gap that warrants conditional acceptance, not rejection. I agree with the reader's assessment; no change to the verdict is needed.","tokens_in":12644,"tokens_out":23686,"duration_ms":170909,"concrete_test":"Re-derive the bound on |S| in Lemma 4.1 tracking constants: from |S| ≤ k^2 W/2^r ∏(1+1/q_i), r=⌈20 log k⌉, ∏(1+1/q_i) ≪ log log k, obtain |S| ≤ k^{-11}W for all sufficiently large k. Then verify that k^{-11} ≤ W^{-ε} for the stated ε by comparing exponents: -ε log W ≥ -11 log k for large k. If both checks pass, replace the k^{-10} line with k^{-11}W; the lemma then justifies the lower-bound proof.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The lower bound Theorem 1.2 rests on Lemma 4.1, whose crucial quantitative claim is |A_t| ≤ W^{t(1−ε)} with ε=(1/2+o(1))/loglog k. The proof obtains |S| ≤ k^{-10}W and then writes |A_t| ≤ |S|^t ≤ (k^{-10}W)^t ≤ W^{t(1−ε)}. This last step requires k^{-10} ≤ W^{-ε}. Since log W = (20+o(1)) log k loglog k, W^{-ε} = k^{-(10+o(1))}. Whether k^{-10} ≤ k^{-(10+o(1))} depends on the sign of the o(1) in ε or in log W, which is not controlled; if the o(1) is positive, the inequality fails. However, the estimate preceding this line, |S| ≤ k^2 W/2^r ∏(1+1/q_i) with r=⌈20 log k⌉, actually gives |S| ≤ k^{-11}W (since 20 log 2 > 11 and the loglog k factor is k^{o(1)}). With the stronger bound, k^{-11} ≤ k^{-(10+o(1))} for large k, so the desired |A_t| ≤ W^{t(1−ε)} follows. Thus the proof has a genuine but easily repairable gap: the displayed inequality in Lemma 4.1 is not fully justified as written, but the lemma statement is true.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies two functions introduced by Erdős and Pomerance: F(n), the minimal interval length guaranteeing a distinct-multiple matching for all integers up to n, and h_P(n), the analogous quantity for primes up to n. Three theorems are proved. Theorem 1.1 gives F(n) ≤ n^{β+o(1)} with β ≈ 1.4031, using the Katz–Tao sum-difference theorem. Theorem 1.2 gives h_P(n) ≥ n exp((1/50) log n / log log n) for large n, based on a square-residue digit construction of Green–Ruzsa; since F(n) ≥ h_P(n), this also gives the same lower bound for F(n) and disproves Kominers's conjecture F(n) ≪ n log n. Theorem 1.4 gives h_P(n) ≪ n^{7/5}/(log n)^{2/5} by a combinatorial argument with a C4-free graph. The proofs are largely self-contained and import only standard external results: Hall's theorem, Katz–Tao, PNT/Mertens, CRT, and spectral graph inequalities.","tokens_in":13110,"tokens_out":29991,"duration_ms":267202,"significance":"If the technical gap discussed below is repaired, the lower bound is a substantial qualitative improvement over Ruzsa's h_P(n)/n → ∞ and over the polynomial-type lower bounds of van Doorn and Kominers; in particular, it settles Kominers's conjecture in the negative. The upper bounds improve the classical 1980 results of Erdős and Pomerance and combine disparate tools in a convincing way. The paper is constructive: constants and heights are tracked in the key arithmetic-Kakeya construction, which makes the argument checkable. There is no circular dependence on the target results, and the infrastructure from [6, 11] is used as an external input rather than as an unproved ad hoc assumption.","major_comments":[{"comment":"The proof contains a load-bearing step that is not justified as written. The displayed chain |A_t| ≤ |S|^t ≤ (k^{-10}W)^t ≤ W^{t(1-ε)} requires k^{-10} ≤ W^{-ε}. Together with log W = (20+o(1)) log k log log k and ε = (1/2+o(1))/log log k, this gives W^{-ε} = k^{-(10+o(1))}; the inequality k^{-10} ≤ k^{-(10+o(1))} depends on the sign of the o(1), which is not controlled. If the o(1) is positive, the inequality fails. However, the preceding estimate, namely |S| ≤ k^2 W / 2^r ∏(1+1/q_i) with r = ⌈20 log k⌉, actually yields the stronger bound |S| ≤ k^{-11}W for all sufficiently large k. Replacing k^{-10} by k^{-11} makes the chain valid, since k^{-11} ≤ k^{-(10+o(1))} eventually. This repair is necessary because Theorem 1.2 rests on this size estimate of A_t.","section":"§4, Lemma 4.1"}],"minor_comments":[{"comment":"In the 'Combining' display after (14)–(18), the term 3 tr(RC^2) is bounded by 3·2|X|^{3/2}ℓ^2 = 6|X|^{3/2}ℓ^2, so the lower bound for T_B should subtract |X|^{3/2}ℓ^2, not (1/3)|X|^{3/2}ℓ^2. The final conclusion is unaffected because this term is of lower order than |X|^2ℓ when ℓ ≫ |X|^{2/5}, so it can be absorbed by taking C_0 large, but the displayed inequality should be corrected.","section":"§5, Lemma 5.1"},{"comment":"The branching thresholds are inconsistent: the first case covers L ≤ 20C_0|P|^{2/5}, and the second case then should assume L > 20C_0|P|^{2/5}, not merely L ≥ 10C_0|P|^{2/5}. This is only a clarity issue.","section":"§5, Lemma 5.2"},{"comment":"The CRT gives an integer m; since h_P(n) is defined for intervals of positive integers, the proof should explicitly say that m is chosen in the positive residue class modulo ∏_{p∈P} p. This does not affect the argument.","section":"§4, proof of Theorem 1.2"}],"recommendation":"major_revision","confidential_remarks":"The main lower-bound theorem appears correct after the small but real repair in Lemma 4.1. The paper is otherwise mathematically coherent and the improvements are significant. The Section 6 AI-assistance disclosure is unusual but does not affect the mathematical assessment; the journal should verify that its policy on AI-assisted proofs is satisfied."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Punchline: the paper delivers real improvements — the lower bound h_P(n) ≥ n exp((1/50)log n/log log n) disproves Kominers's conjecture, and the h_P upper bound n^{7/5}/(log n)^{2/5} breaks the 1980 Erdős–Pomerance exponent. The F(n) upper bound n^{1.4031+o(1)} is a corollary of Katz–Tao but still a strict improvement.\n\nWhat's actually new and good: the Green–Ruzsa square-residue construction is adapted to the prime matching problem, and the CRT embedding that turns the arithmetic-Kakeya set into a Hall obstruction is a clean idea. The constants are tracked tightly enough to get the explicit log/loglog exponent. The upper bound proof is the strongest part: Lemmas 5.1–5.2 build a C6-counting argument that avoids Katz–Tao entirely, and the dyadic partition handles the prime distribution cleanly. The paper is honest about the provenance of the proof details (AI statement) and does not hide behind it.\n\nSoft spots, both minor:\n- Lemma 4.1 has a genuine gap: the step from |S|≤k^{-10}W to |A_t|≤W^{t(1−ε)} requires comparing k^{-10} with k^{-(10+o(1))}, and the sign of the o(1) is not controlled. The stronger bound |S|≤k^{-11}W, which follows from the same estimates, repairs the inequality. The lemma statement is true; the proof needs one line fixed.\n- Lemma 5.1 drops a factor of 3 when combining (14)–(18): the term from 3tr(RC^2) should give 6|X|^{3/2}ℓ^2, not 2. This is a constant typo; it doesn't change the final c0ℓ^6 conclusion because the negative terms are lower order for ℓ ≥ C0|X|^{2/5}. Also, the “at most L edges” claim in Lemma 5.2 should be “at most 2ℓ,” which is ≤L for L≥4, so it's fine.\n\nThe citation pattern is healthy: external theorems are used independently, and the new lemmas are proved from scratch. No circularity.\n\nWho should read it: people working on distinct-multiples problems, additive combinatorics applications to number theory, and anyone who wants to see a clean use of the arithmetic Kakeya construction. It deserves a serious referee. My recommendation: send it out, ask for the two repairs to the constants, and accept after they're done.","headline":"Genuine improvements on a niche problem; the two flagged gaps are real but repairable, so the paper should go to referees.","tokens_in":13562,"tokens_out":8253,"would_cite":true,"duration_ms":66542,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["11N05","11P70"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper proves that the shortest interval guaranteed to contain distinct multiples of every integer up to n grows faster than n log n, falsifying a conjecture that n log n would suffice.","keywords":["distinct multiples","intervals","matching","arithmetic Kakeya","lower bound","upper bound","prime distribution","additive combinatorics"],"falsifier":"Inspect Lemma 4.1 numerically: compute W, ε, and the ratio |S|/W for the specified construction, and check whether |S|^t ≤ W^{t(1−ε)} for t=2 or t=3. A direct computation showing the digit-product set exceeds W^{t(1−ε)} would falsify the lower-bound proof; confirming the stronger bound k^{-11}W would support it.","tokens_in":12592,"feed_emoji":"🔢","tokens_out":7823,"duration_ms":66922,"temperature":0.7,"pith_summary":"Two interval-length functions are studied: F(n), the smallest length such that every interval of that length contains, for each integer 1 through n, a distinct multiple of that integer, and h_P(n), the analogous quantity when only primes at most n are required. The main advance is a lower bound h_P(n) ≥ n exp((1/50) log n / log log n) for all large n, which transfers to F(n) because F(n) ≥ h_P(n). This growth is faster than n log n, so a conjecture that F(n) is at most n log n is refuted. The paper also obtains improved upper bounds, F(n) ≤ n^{β+o(1)} with β ≈ 1.4031 and h_P(n) ≪ n^{7/5}/(log n)^{2/5}, improving the 1980 bounds.","feed_headline":"Distinct-multiple intervals: lower bound beats n log n","feed_subtitle":"New proof shows the needed interval length grows like n exp((log n)/(50 log log n)), disproving an n log n conjecture.","key_machinery":"The lower bound's engine is the digit-product arithmetic-Kakeya set: a set of integers that contains, for every d up to W^t, a k-term arithmetic progression with common difference d, yet stays sparse (size ≤ W^{t(1−ε)}). This smallness, combined with the classical matching criterion for bipartite graphs and a Chinese-remainder shift, produces an interval whose prime-multiple offsets fit inside fewer offsets than there are primes, blocking any distinct multiple assignment. The upper bounds rely on a projection inequality for finite subsets of Z² and on a lemma counting C6 cycles in a C4-free bipartite graph.","core_discovery":"On the paper's own terms, the central discovery is a quantitative lower bound: for sufficiently large n, h_P(n) ≥ n exp((1/50) log n / log log n), and therefore the same inequality holds for F(n). The proof constructs, for a carefully chosen product W of small odd primes, a digit-product set A_t that contains a k-term arithmetic progression of every difference d < W^t (a (k,W^t) arithmetic-Kakeya set) while having size at most W^{t(1−ε)}. Embedding the primes in a CRT-chosen interval then makes the neighborhood of the prime set too small for a matching, so the interval must be long. A separate argument, based on a projection estimate for finite lattice sets, yields F(n) ≤ n^{1.4031+o(1)}; an","pith_inferences":["The size-bound step in Lemma 4.1 appears to require a slightly stronger estimate than the stated |S|≤k^{-10}W; the surrounding estimates seem to supply |S|≤k^{-11}W, which would close the gap, so the theorem likely survives a careful rewriting.","The same CRT-plus-sparse-set template might extend to other sets of moduli — for example, integers with at most two prime factors — wherever the corresponding arithmetic-Kakeya set can be made sparse.","The upper-bound method for h_P(n) uses only a codegree-at-most-one structure and a lower bound on C6 cycles, so it may generalize to other 'few-overlap' families of arithmetic progressions.","Numerical tests of Lemma 4.1 for moderate k would indicate whether the stated quantitative smallness is present or whether the proof needs the stronger estimate."],"forward_implications":["The lower bound F(n) ≥ n exp((1/50) log n / log log n) disproves the conjecture that F(n) ≪ n log n.","Because F(n) ≥ h_P(n), the same superlinear lower bound applies to all-integer distinct multiples, not just primes.","The upper bound F(n) ≤ n^{1.4031+o(1)} improves the long-standing n^{3/2} bound.","The upper bound h_P(n) ≪ n^{7/5}/(log n)^{2/5} improves the previous n^{3/2}/√(log n) bound for the prime-only problem.","The older conjecture that F(n) = n^{1+o(1)} remains open, but the new bounds narrow the possible range to between n exp((1/50)log n/log log n) and n^{1.4031+o(1)}."],"fun_headline_variants":["Distinct-multiple intervals: n log n conjecture false","New lower bound: n exp(log n / log log n)","Surpasses n log n: distinct multiples in intervals","Erdős–Pomerance functions: sharper bounds proved","Kominers' conjecture on distinct multiples disproved"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The load-bearing premise is the quantitative size bound on the digit-product set in Lemma 4.1. The proof derives it from |S|≤k^{-10}W, but the stated constants do not by themselves force |A_t|≤W^{t(1−ε)}; if that size bound were false the lower bound would collapse, although the surrounding estimates appear to provide the stronger |S|≤k^{-11}W needed.","fun_headline_variants_meta":{"raw":{"variants":["Distinct-multiple intervals: n log n conjecture false","New lower bound: n exp(log n / log log n)","Surpasses n log n: distinct multiples in intervals","Erdős–Pomerance functions: sharper bounds proved","Kominers' conjecture on distinct multiples disproved"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000476,"raw_usage":{"total_tokens":2309,"prompt_tokens":968,"completion_tokens":1341,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":712,"completion_tokens_details":{"reasoning_tokens":1259}},"tokens_in":712,"tokens_out":1341,"duration_ms":14043,"temperature":1.0,"reasoning_tokens":1259,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-01T15:44:43.082031+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Inspect Lemma 4.1 numerically: compute W, ε, and the ratio |S|/W for the specified construction, and check whether |S|^t ≤ W^{t(1−ε)} for t=2 or t=3. A direct computation showing the digit-product set exceeds W^{t(1−ε)} would falsify the lower-bound proof; confirming the stronger bound k^{-11}W would support it.","supporting_citations":[],"review_version":1}