{"id":"048ce559-d55c-4abd-9c08-072e05c0120b","arxiv_id":"2611.17205","paper_version":1,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":8.0,"correctness_risk":"low","formal_verification":"partial","parameter_count":0,"one_line_summary":"For c>=1, f_c(n)=floor(cn)-ceil(n/2); for 0<c<1, the ratio f_c(n)/n has at least two limit points, with exact limits along n whose least non-divisor is a small prime power.","lead":"The paper resolves an old question of Erdős and Graham about the largest set of small numbers that can still avoid a target sum. It shows the answer is completely regular when the allowed range is large enough, and genuinely irregular when it is not.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek/deepseek-v4-flash","headline":"No significant objection identified: the central irregularity claim (non-convergence for 0<c<1) is already proved via q=2,3, which are formally verified; the q≥4 results are conditional but acknowledged as open.","rationale":"The reader's weakest_assumption identified Lemma 2.5 (bounded additive basis) as the most fragile premise, and noted that the formal verification covers only q=2,3. That is accurate. However, the reader's verdict of ACCEPT with high confidence is appropriate because the central irregularity claim does not depend on q≥4. The stress-test confirms that the core result is securely established. The partial agreement reflects that while the reader correctly identified a fragile point, that point is not load-bearing for the main conclusion; the main conclusion is already supported by the verified q=2,3 cases. The paper's own limitations are transparent, and the formal verification provides strong evidence for the essential part of the claim.","tokens_in":25577,"tokens_out":536,"duration_ms":27423,"concrete_test":"Re-run the formal verification for the q=2,3 cases (already done) and confirm that the statement erdos361_irregular (non-convergence for 0<c<1) is indeed proved. This is already recorded in the paper. No further test is needed to settle the central claim.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The paper's main conclusion—that fc(n)/n does not converge for any 0<c<1—is already established by Theorem 1.5 using only the q=2 and q=3 cases of Theorem 1.4(ii). Those cases are covered by the formal verification in Lean (Section 8, Table 3). The additional results for q≥4 (more limit points, exact limits along specific subsequences) depend on the condition 2^{q-2} min{c,1-c} ≤ 1, which the authors explicitly note is not known to be optimal (Problem 9.2, Remark 3.2). The formal verification does not cover q≥4, and the optimal range constant θ_q is open. However, the central claim of the paper—the irregularity answer to the Erdős–Graham problem—does not require those q≥4 results; it is already fully supported by the q=2,3 cases. Therefore, no load-bearing concern about the central claim remains unresolved. The paper's own limitations are clearly stated, and the core argument is machine-checked.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek/deepseek-v4-flash","summary":"The paper studies the Erdős–Graham function fc(n), the largest size of a set A⊆[1,⌊cn⌋] with no subset summing to n. The main results are: an exact formula fc(n)=⌊cn⌋−⌈n/2⌉ for c≥1; for 0<c<1, an asymptotic limsup equal to c/2 attained along odd n; and, along the subsequence snd(n)=q for prime powers q satisfying 2^{q−2}min{c,1−c}≤1, the limit φq(c)=max{c/q, c−1/2+(1−c)/q}. It follows that fc(n)/n converges if and only if c≥1, that for 0<c<1 there are at least two limit points, and that for c=1/2 the exact set of limit points is {1/6,1/4}. The upper bounds are uniform consequences of an inverse theorem (Theorem 1.2): for s≥1, q=snd(s), and ε>0, any A⊆[1,E] with |A|≥E/q+εT contains a subset summing to sT, provided 2^{q−2}E≤sT and T is sufficiently large. A substantial part of the argument, including the c≥1 results, the limsup statement, the q∈{2,3} cases of the inverse theorem and limits, and the resulting non-convergence for every 0<c<1, is formalized in Lean 4.","tokens_in":24045,"tokens_out":25962,"duration_ms":146600,"significance":"If accepted, this resolves the irregularity question of Erdős and Graham (Problem #361) in a strong form: for linear ranges, the ratio fc(n)/n is regular exactly for c≥1 and irregular for every 0<c<1. The inverse theorem is of independent interest and extends Alon's theorem on subsets of [1,N] with no subset sum equal to 2N. The paper's main claims rest on a carefully structured proof: elementary lower constructions, a distinctification lemma, a central interval lemma, and a dyadic iteration of Freiman's 3k−4 theorem. The formal verification covers precisely the decisive cases q=2 and q=3, so the central convergence/non-convergence dichotomy is machine-checked. The q≥4 results inherit the possibly non-optimal range constant 2^{q−2}; this is explicitly acknowledged in Remark 3.2 and Problem 9.2, and it does not affect the main irregularity theorem, which only needs q=2 and q=3. I found no fitted parameters, no post-hoc selection of constants, and no circularity in the derivations.","major_comments":[],"minor_comments":[{"comment":"Cross-references to 'Theorem 5.5' and 'Theorem 5.1' do not match the numbering in the text, where the statements appear as Remark 5.5 and Lemma 5.1; these labels should be made uniform.","section":"Sections 1.2 and 5.4","authors_acknowledge":null,"authors_acknowledge_p":null},{"comment":"For c≤1/2 the table caption correctly notes that n≤127 is below the asymptotic regime, but Figure 1 shows only c=2/3 and c=3/4; adding an explicit sentence to the figure caption that small-c numerical values are not asymptotic evidence would prevent overreading of Table 2.","section":"Section 7, Table 2 and Figure 1","authors_acknowledge":null,"authors_acknowledge_p":null},{"comment":"The sentence that the Comparator configurations were not run is a useful limitation and should remain in the verification record; I suggest moving it into the main verification paragraph so that the kernel-checked status of the eleven statements is not confused with the weaker comparator check.","section":"Section 8","authors_acknowledge":null,"authors_acknowledge_p":null}],"recommendation":"accept"},"author_rebuttal":null,"desk_editor":{"model":"deepseek/deepseek-v4-flash","letter":"Bottom line: this is the real thing. The paper gives the first inverse theorem for forbidden subset sums in the linear range and uses it to answer Erdős–Graham #361. The c≥1 formula is elementary and was already floating around the problem discussion; the actual content is the 0<c<1 regime, where the paper proves non-convergence and identifies limit points along the snd(n)=q classes. The small-c and c-near-1 consequences are a nice bonus, and the c=1/2 exact limit set is a clean corollary.\n\nThe proof chain holds together. The distinctification lemma, the central interval lemma, and the dyadic Freiman iteration line up, and the inverse theorem is genuinely independent of the lower constructions. There is no fitted constant anywhere, and the forum values reproduced in Section 7 are treated as a sanity check, not as a source of parameters. The Lean formalization is also real evidence, not decoration. It covers c≥1, the limsup, non-convergence, and the inverse theorem for q=2,3; the statement/Challenge.lean separation and the axiom reports are clean. Since the main non-convergence claim needs only q=2 and q=3, the machine-checked part is load-bearing for the central answer.\n\nSoft spots are real but mostly acknowledged. The full inverse theorem for q≥4 depends on the range constant θ_q, which is only known between max{2,q−2+1/q} and 2^{q−2}. That makes the q≥4 limit results conditional, and the authors say so. It does not undermine the main irregularity theorem, but anyone citing the inverse theorem in full generality needs to know the q≥4 part is not yet unconditional. The exact set of limit points for c≠1/2 is also left open. On the formalization side, the short deduction from the formalized inverse form to the full Theorem 1.2 for q=2,3 is not machine-checked, and the Comparator configurations were not run; both are minor. The C program from Section 7 is not in the repository, which is a small reproducibility annoyance but not a correctness issue.\n\nWho should read this? Anyone working in additive combinatorics, subset sums, or inverse problems in the linear regime. It deserves a serious referee and will likely survive contact with one. I would send it out without hesitation, with the q≥4 and repository points as minor revision requests.","headline":"This paper actually settles Erdős–Graham #361 in the linear range, and the main irregularity claim already rests on the machine-checked q=2,3 cases.","tokens_in":24609,"tokens_out":1844,"duration_ms":20088},"pith_extraction":{"msc":["11B13","11B30","11P70","68V20"],"pacs":[],"model":"deepseek/deepseek-v4-flash","headline":"The Erdős–Graham subset-sum function has the exact value ⌊cn⌋−⌈n/2⌉ for c≥1, and for 0<c<1 the ratio f_c(n)/n never converges, accumulating at distinct limits indexed by the least non-divisor of n.","keywords":["subset sums","Erdős–Graham problem","least non-divisor","inverse additive combinatorics","Freiman 3k−4 theorem","Roth's theorem","limit points","Lean 4 formal verification"],"falsifier":"The cleanest test is exact computation, since the paper's own branch-and-bound search covered only $40\\le n\\le127$. For $c=1/2$ the theorem forces $f_{1/2}(n)/n\\to1/4$ along odd $n$ and $\\to1/6$ along even $n$; exhibiting infinitely many odd $n$ with $f_{1/2}(n)\\ge(1/4+\\delta)n$, or even $n$ with $f_{1/2}(n)\\ge(1/6+\\delta)n$, for a fixed $\\delta>0$ would falsify this dichotomy. The author's own open case is $q=4$ with $1/4<c<3/4$: computing whether $f_c(n)/n$ settles near $\\varphi_4(c)$ or near the interval-construction value $1/4$ along $n\\equiv6\\pmod{12}$ would decide whether the $Q(c)$ hypothesis is necessary.","tokens_in":25196,"feed_emoji":"🔢","tokens_out":23692,"duration_ms":119830,"temperature":0.7,"pith_summary":"The paper answers Erdős–Graham Problem #361 in the linear range: for $c>0$, how large can a set $A\\subseteq\\{1,\\ldots,\\lfloor cn\\rfloor\\}$ be while no subset of $A$ sums to $n$? For $c\\ge 1$ the answer is exact and regular: $f_c(n)=\\lfloor cn\\rfloor-\\lceil n/2\\rceil$ for every $n$, so $f_c(n)/n\\to c-1/2$. For $0<c<1$ the answer is genuinely irregular: the ratio has $\\limsup$ equal to $c/2$, attained along the odd integers, and along the classes of $n$ with the same least non-divisor $q$ it tends to $\\varphi_q(c)=\\max\\{c/q,\\;c-\\tfrac12+\\tfrac{1-c}{q}\\}$ for every prime power $q$ with $2^{q-2}\\min\\{c,1-c\\}\\le 1$. Consequently $f_c(n)/n$ converges if and only if $c\\ge 1$, it has at least two limit points for every $0<c<1$, and at $c=1/2$ the limit set is exactly $\\{1/6,1/4\\}$. The upper bounds rest on a new inverse theorem — dense sets in a short interval must already represent the target as a subset sum — proved by iterating Freiman's $3k-4$ theorem along dyadic sumsets; the author also shows the hypothesis $q\\in Q(c)$ cannot simply be dropped.","feed_headline":"Erdős problem #361: subset-sum ratios converge exactly for c ≥ 1","feed_subtitle":"For smaller windows the ratio keeps at least two distinct limits, indexed by the smallest divisor missing from n.","key_machinery":"The object that carries the argument is the inverse theorem (Theorem 1.2): if $q=\\operatorname{snd}(s)$ is the least positive integer not dividing $s$ (always a prime power, with $\\operatorname{lcm}(1,\\ldots,q-1)\\mid s$), then for every $\\varepsilon>0$ and all sufficiently large $T$, every $A\\subseteq[1,E]$ with $|A|\\ge E/q+\\varepsilon T$ and $E\\le sT/2^{q-2}$ has a subset summing to $sT$, using at most $2^{q-2}(\\lceil 2s/\\varepsilon\\rceil+1)$ distinct elements. Setting $s=2$ and $E=T$ recovers the upper bound in Alon's theorem that a subset of $[1,N]$ with no subset sum $2N$ has at most $(1/3+o(1))N$ elements. The proof passes through three devices: a 'distinctification' lemma that converts sums with repetitions into subset sums using Roth's theorem; a normalization to a set $B\\subseteq[0,L]$ of density at least $1/q+\\eta$ with $\\gcd(B)=1$; and the bounded additive basis lemma (Lemma 2.5), which iterates Freiman's $3k-4$ theorem on the dyadic sumsets $2^jB$ to show that every $y\\in[2^{q-2}L,KL]$ is a sum of at most $2^{q-2}(\\lceil K\\rceil+1)$ elements of $B$. The multiples of $q$ supply the matching lower bound of density $1/q$ whenever $q\\nmid sT$, while the exponential range constant $2^{q-2}$ is proved sharp only for $q\\in\\{2,3\\}$.","core_discovery":"The central claim is a dichotomy between regular and irregular behaviour of the extremal size $f_c(n)$. For $c\\ge 1$, an injection argument gives the exact value $f_c(n)=\\lfloor cn\\rfloor-\\lceil n/2\\rceil$: a set avoiding $n$ holds at most one element from each pair $\\{x,n-x\\}$, and the interval $[\\lceil n/2\\rceil,n-1]\\cup[n+1,\\lfloor cn\\rfloor]$ achieves the bound. For $0<c<1$ the paper proves that $f_c(n)/n$ has $\\limsup\\, c/2$, achieved along odd $n$ by the multiples of $2$, and that along every class $\\{n:\\operatorname{snd}(n)=q\\}$ with $q$ a prime power and $2^{q-2}\\min\\{c,1-c\\}\\le 1$, the ratio tends to $\\varphi_q(c)=\\max\\{c/q,\\;c-\\tfrac12+\\tfrac{1-c}{q}\\}$, the larger of two competing behaviours: the multiples of $q$ (density $c/q$) versus a mixed set of multiples of $q$ together with one residue class above $n/2$ (density $c-\\tfrac12+\\tfrac{1-c}{q}$). Since the values $\\varphi_q(c)$ are pairwise distinct and $\\{2,3\\}\\subseteq Q(c)$, the sequence has at least two limit points always, and arbitrarily many as $c\\to 0^+$ or $c\\to 1^-$, so $f_c(n)/n$ converges exactly when $c\\ge 1$. At $c=1/2$ the description is complete: odd $n$ give $1/4$ and even $n$ give $1/6$, so the limit set is exactly $\\{1/6,1/4\\}$; the even case reproduces Alon's $f(N,2N)=(1/3+o(1))N$. The paper frames its contribution as the matching upper bounds: the lower-bound constructions were largely known from the problem's discussion, while the arithmetic-sensitive upper bounds are new (Theorem 1.2 and its consequences).","pith_inferences":["If the true range constant $\\theta_q$ in Theorem 1.2 were linear in $q$ — a route the author explicitly leaves open via structure theorems for $h$-fold sumsets — then Theorem 1.4(ii) would extend to far more classes $\\mathrm{snd}(n)=q$ for each fixed $c$, the number of limit points would grow like $1/\\min\\{c,1-c\\}$ instead of logarithmically, and the open case $q=4$ with $1/4<c<3/4$ would likely f","The complete picture at $c=1/2$ suggests a general conjecture the paper does not state: that for every $0<c<1$ the full set of limit points of $f_c(n)/n$ is $\\{\\varphi_q(c):q\\in Q(c)\\}$ together with the values forced by interval constructions where those exceed $\\varphi_q(c)$ (such as $1/4$ for $2/3\\le c<3/4$); the author's Conjecture 9.4, asserting $f_c(n)=\\lfloor\\lfloor cn\\rfloor/2\\rfloor$ for ","Because the Section 6 zero-sum proof derives non-convergence from bounded zero-sum estimates alone, the qualitative irregularity does not depend on the sharp inverse theorem, and this is the route the Lean formalization takes; the author notes that the short deduction of Theorem 1.2's final form and the bound on the number of summands are not part of that formalization, so the machine-checked stat"],"forward_implications":["At $c=1/2$ the irregularity is completely described: the set of limit points of $f_{1/2}(n)/n$ is exactly $\\{1/6,1/4\\}$, with $1/4$ along odd $n$ and $1/6$ along even $n$ (Corollary 1.6).","For every $0<c<1$, $f_c(n)/n$ has at least as many limit points as there are prime powers $q\\le 2+\\log_2(1/\\min\\{c,1-c\\})$, and this number grows without bound as $c\\to 0^+$ or $c\\to 1^-$; the ratio never converges unless $c\\ge 1$ (Corollary 1.5).","Outside the regular range the extremal sets change shape: for $c>1/2$ and $q\\ge 3$ the maximizing sets are mixed — multiples of $q$ together with one residue class above $n/2$ — rather than the plain multiples of the least non-divisor (Theorem 5.3(b)).","The inverse theorem converts density into representation uniformly: every $A\\subseteq[1,\\lfloor xT\\rfloor]$ with $|A|>(x/q+\\varepsilon)T$ contains a subset summing to $sT$ whenever $x\\le s/2^{q-2}$, and then $F(\\lfloor xT\\rfloor,sT)=(x/q+o(1))T$ along $T$ with $p\\nmid T$ (Corollary 1.3).","The hypothesis $q\\in Q(c)$ is necessary, not cosmetic: for $2/3\\le c<3/4$ an interval construction gives $f_c(n)\\ge n/4-1$ for every $n$, which beats every $\\varphi_q(c)$ for all large $q$ (Remark 5.5)."],"supporting_citations":[{"why":"Erdős and Graham's monograph posing Problem #361, the question the paper resolves in the linear range.","marker":"[10]"},{"why":"Alon's subset-sum paper: supplies the least-non-divisor lower bound, the bounded zero-sum theorem used in Section 6, and the target f(N,2N)=(1/3+o(1))N that the new inverse theorem extends.","marker":"[1]"},{"why":"Freiman's 3k-4 theorem, iterated on dyadic sumsets inside the bounded additive basis lemma to force dense sets to represent every integer in the exponential window.","marker":"[12]"},{"why":"Roth's theorem, used in the distinctification lemma to pass from sums with repetitions to sums of distinct elements.","marker":"[24]"},{"why":"Dias da Silva–Hamidoune bound on k-fold restricted sums, the prime-modulus zero-sum route of Section 6.","marker":"[8]"},{"why":"Alon–Nathanson–Ruzsa polynomial method, used to derive the prime-modulus restricted-sum bound inside the formal proof.","marker":"[4]"},{"why":"Nathanson's additive number theory text, whose large-diameter induction proof of Freiman's theorem is formalized from scratch in the Lean development.","marker":"[22]"},{"why":"Bloom's Erdős problem database where #361 is quoted as open and whose discussion contains the constructions and numerical values reproduced in Section 7.","marker":"[5]"}],"fun_headline_variants":[],"cache_read_input_tokens":0,"weakest_assumption_plain":"Every upper bound for $0<c<1$ passes through the bounded additive basis lemma, which asserts that a set of density at least $1/q+\\eta$ in $[0,L]$ represents every integer in the dyadic window $[2^{q-2}L,KL]$ with $2^{q-2}(\\lceil K\\rceil+1)$ summands; the exponential window comes from iterating Freiman's $3k-4$ theorem and is proved optimal only for $q=2,3$, so if the true window for $q\\ge4$ were smaller the theorem's scope would only widen, whereas if this growth estimate failed the $c<1$ upper bounds would collapse.","fun_headline_variants_meta":{"raw":{"variants":[]},"model":"deepseek/deepseek-v4-flash","effort":"low","cost_usd":0.000141,"raw_usage":{"cost":0.0001405222,"is_byok":false,"cost_details":{"upstream_inference_cost":0.0001405222,"upstream_inference_prompt_cost":0.0001230502,"upstream_inference_completions_cost":1.7472e-05},"total_tokens":1653,"prompt_tokens":1557,"completion_tokens":96,"prompt_tokens_details":{"audio_tokens":0,"video_tokens":0,"cached_tokens":256,"cache_write_tokens":0},"completion_tokens_details":{"audio_tokens":0,"image_tokens":0,"reasoning_tokens":0}},"tokens_in":1557,"tokens_out":96,"cost_source":"openrouter_usage","duration_ms":9581,"image_pages":[],"temperature":1.0,"billed_attempts":1,"reasoning_tokens":0,"transport_provider":"openrouter","cache_read_input_tokens":0,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-11-13T09:16:43.771203+00:00","model_set":{"reader":"deepseek/deepseek-v4-flash"},"pipeline_version":"pith-pipeline@v1.4.1-daily-deepseek-or-medium","input_kind":null,"input_chars":null,"input_total_chars":null,"passes_missing":null,"published_standing":null,"published_confidence":null,"objection_audit":null,"run_record":null,"basis":{"kind":"not_recorded","source":null,"chars_given":null,"chars_total":null},"receipt":null,"falsifier":"The cleanest test is exact computation, since the paper's own branch-and-bound search covered only $40\\le n\\le127$. For $c=1/2$ the theorem forces $f_{1/2}(n)/n\\to1/4$ along odd $n$ and $\\to1/6$ along even $n$; exhibiting infinitely many odd $n$ with $f_{1/2}(n)\\ge(1/4+\\delta)n$, or even $n$ with $f_{1/2}(n)\\ge(1/6+\\delta)n$, for a fixed $\\delta>0$ would falsify this dichotomy. The author's own open case is $q=4$ with $1/4<c<3/4$: computing whether $f_c(n)/n$ settles near $\\varphi_4(c)$ or near the interval-construction value $1/4$ along $n\\equiv6\\pmod{12}$ would decide whether the $Q(c)$ hypothesis is necessary.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Erdős and Graham's monograph posing Problem #361, the question the paper resolves in the linear range."},{"cited_title":"Alon,Subset sums, J","cited_arxiv_id":null,"evidence_quote":"Alon's subset-sum paper: supplies the least-non-divisor lower bound, the bounded zero-sum theorem used in Section 6, and the target f(N,2N)=(1/3+o(1))N that the new inverse theorem extends."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Freiman's 3k-4 theorem, iterated on dyadic sumsets inside the bounded additive basis lemma to force dense sets to represent every integer in the exponential window."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Roth's theorem, used in the distinctification lemma to pass from sums with repetitions to sums of distinct elements."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Dias da Silva–Hamidoune bound on k-fold restricted sums, the prime-modulus zero-sum route of Section 6."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Alon–Nathanson–Ruzsa polynomial method, used to derive the prime-modulus restricted-sum bound inside the formal proof."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Nathanson's additive number theory text, whose large-diameter induction proof of Freiman's theorem is formalized from scratch in the Lean development."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Bloom's Erdős problem database where #361 is quoted as open and whose discussion contains the constructions and numerical values reproduced in Section 7."}],"lane_accuracy":{"status":"not yet measured","lane":{"model":"deepseek/deepseek-v4-flash","input_kind":null},"url":"https://pith.science/accuracy"},"review_version":1}