Forbidden subset sums in a linear range: an inverse theorem and the Erdős-Graham irregularity problem
Mateo Matijasevick
math.CO
Nov 12, 2026 · v1
math.NT
TL;DR
Main results on Erdős Problem #361, including Freiman's 3k-4 theorem and an inverse theorem for q in {2,3}, are formalized in Lean 4 with Mathlib (about 5000 lines).
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ős and Graham asked whether $f_c(n)$ depends on $n$ in an irregular way (Erdő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.
Problem
Erdős Problem #361 asks for the largest size f_c(n) of a set A ⊆ {1,…,⌊cn⌋} for which n is not a sum of distinct elements of A. It also asks whether f_c(n) depends on n irregularly.
Approach
The upper bounds come from an inverse theorem: a large subset of {1,…,E} must contain a subset summing to sT, where q is the least non-divisor of s. Its proof uses Roth's theorem, Freiman's 3k-4 theorem and a normalization by the gcd. A second, independent non-convergence proof uses zero-sums via Alon's theorem and the Dias da Silva–Hamidoune theorem. The main results are formalized in Lean 4 with Mathlib, using a trusted Challenge/Solution statement layer that is checked with the Comparator tool.
Results
For c ≥ 1, f_c(n) = ⌊cn⌋ − ⌈n/2⌉. For 0 < c < 1, f_c(n)/n has limsup c/2 and has explicit limits along n with a given least non-divisor q, so it does not converge; for c = 1/2 the limit points are exactly {1/6, 1/4}. Eleven Lean statements are machine-checked, depending only on the standard axioms.
| q | n with snd(n)=q | φ_q(c), c ≤ 1/2 | φ_q(c), c ≥ 1/2 |
|---|
| 2 | n odd | c/2 | c/2 |
| 3 | n ≡ 2,4 (mod 6) | c/3 | 2c/3 − 1/6 |
| 4 | n ≡ 6 (mod 12) | c/4 | 3c/4 − 1/4 |
| 5 | n ≡ 12,24,36,48 (mod 60) | c/5 | 4c/5 − 3/10 |
Limits of f_c(n)/n along n with least non-divisor q (excerpt)