{"arxiv_id":"2611.17205","title":"Forbidden subset sums in a linear range: an inverse theorem and the Erd\\H{o}s-Graham irregularity problem","abstract":"For $c>0$ let $f_c(n)$ be the largest size of a set $A\\subseteq\\{1,\\dots,\\lfloor cn\\rfloor\\}$ such that $n$ is not a sum of distinct elements of $A$. Erd\\H{o}s and Graham asked whether $f_c(n)$ depends on $n$ in an irregular way (Erd\\H{o}s Problem \\#361). We prove that $f_c(n)=\\lfloor cn\\rfloor-\\lceil n/2\\rceil$ for $c\\ge 1$, while for $0<c<1$ the ratio $f_c(n)/n$ has $\\limsup$ equal to $c/2$, attained along odd $n$, and, along the integers $n$ whose least non-divisor equals a prime power $q$, tends to \\[ \\max\\Bigl\\{\\frac cq,\\; c-\\frac12+\\frac{1-c}{q}\\Bigr\\} \\qquad\\text{whenever } 2^{q-2}\\min\\{c,1-c\\}\\le 1 . \\] Consequently $f_c(n)/n$ converges if and only if $c\\ge1$; for $0<c<1$ it has at least two limit points, and arbitrarily many as $c\\to0^+$ or $c\\to1^-$. For $c=1/2$ the set of limit points is exactly $\\{1/6,1/4\\}$. The upper bounds follow from an inverse theorem of independent interest: if $s\\ge1$, $q$ is the least positive integer not dividing $s$, and $\\varepsilon>0$, then every $A\\subseteq\\{1,\\dots,E\\}$ with $|A|\\ge E/q+\\varepsilon T$ has a subset summing to $sT$, uniformly for all sufficiently large $T$ and all $E\\le sT/2^{q-2}$. For $s=2$, this extends Alon's theorem on subsets of $\\{1,\\dots,N\\}$ with no subset sum equal to $2N$. The results for $c\\ge1$ and the $\\limsup$, as well as the limits and the inverse theorem for $q\\in\\{2,3\\}$, have been formalized and machine-checked in the Lean~4 proof assistant.","primary_cat":"math.CO","cross_cats":["math.NT"],"submitted_at":"2026-11-12T18:05:45+00:00","latest_version":1,"source":"arxiv","source_label":"arXiv","source_url":null,"has_pdf":true,"has_source":false,"verdict":"ACCEPT","confidence":"HIGH","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.","novelty_score":8.0,"correctness_risk":"low","formal_verification":"partial","upvotes":0,"downvotes":0,"pith_score":0,"inbound_count":0,"_links":{"html":"https://pith.science/paper/2611.17205","verdict":"/api/v1/verdicts/2611.17205"}}