Forbidden subset sums in a linear range: an inverse theorem and the Erdős-Graham irregularity problem
Abstract
For c>0 let fc(n) be the largest size of a set A⊆{1,…,⌊ cn⌋} such that n is not a sum of distinct elements of A. Erdős and Graham asked whether fc(n) depends on n in an irregular way (Erdős Problem \#361). We prove that fc(n)=⌊ cn⌋−⌈ n/2⌉ for c≥ 1, while for 0<c<1 the ratio fc(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{c/q, c−1/2+(1−c)/q} whenever 2q−2min{c,1−c}≤ 1 . Consequently fc(n)/n converges if and only if c≥1; for 0<c<1 it has at least two limit points, and arbitrarily many as c→0+ or c→1-. 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≥1, q is the least positive integer not dividing s, and ε>0, then every A⊆{1,…,E} with |A|≥ E/q+ε T has a subset summing to sT, uniformly for all sufficiently large T and all E≤ sT/2q−2. For s=2, this extends Alon's theorem on subsets of {1,…,N} with no subset sum equal to 2N. The results for c≥1 and the limsup, as well as the limits and the inverse theorem for q∈{2,3}, have been formalized and machine-checked in the Lean~4 proof assistant.
Related
- A Complete Solution to the Conjecture on the Inverse Collatz–Sinogowitz Irregularity Problem
- Applying the convolution theorem to the two-dimensional magnetic inverse problem
- Analytic Combinatorics of Lattice Paths with Forbidden Patterns: Asymptotics Aspects and Borges's Theorem
- Linear dependencies, polynomial factors in the Duke–Erdős forbidden sunflower problem – CORRIGENDUM
- New approaches to the Erdős Distinct Subset Sums Problem
BibTeX
@misc{matijasevick2026forbidden,
title = {{Forbidden subset sums in a linear range: an inverse theorem and the Erdős-Graham irregularity problem}},
author = {Mateo Matijasevick},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.17205},
eprint = {2611.17205},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.17205},
}
RIS
TY - UNPB
TI - Forbidden subset sums in a linear range: an inverse theorem and the Erdős-Graham irregularity problem
AU - Mateo Matijasevick
PY - 2026
DA - 2026/11/12
PB - arXiv
DO - 10.48550/arxiv.2611.17205
UR - https://arxiv.org/abs/2611.17205
AB - For c>0 let f_c(n) be the largest size of a set A⊆{1,…,⌊ cn⌋} 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)=⌊ cn⌋−⌈ n/2⌉ for c≥ 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{c/q, c−1/2+(1−c)/q} whenever 2^q−2min{c,1−c}≤ 1 . Consequently f_c(n)/n converges if and only if c≥1; for 0<c<1 it has at least two limit points, and arbitrarily many as c→0^+ or c→1^-. 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≥1, q is the least positive integer not dividing s, and ε>0, then every A⊆{1,…,E} with |A|≥ E/q+ε T has a subset summing to sT, uniformly for all sufficiently large T and all E≤ sT/2^q−2. For s=2, this extends Alon's theorem on subsets of {1,…,N} with no subset sum equal to 2N. The results for c≥1 and the limsup, as well as the limits and the inverse theorem for q∈{2,3}, have been formalized and machine-checked in the Lean~4 proof assistant.
ER -