Forbidden subset sums in a linear range: an inverse theorem and the Erdős-Graham irregularity problem

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 $00$, 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.

Authors

Publication Details

Journal
arXiv (Cornell University)
Published
2026-11-12
DOI
https://doi.org/10.48550/arxiv.2611.17205
Primary Topic
Limits and Structures in Graph Theory
Type
preprint
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
preprint

Forbidden subset sums in a linear range: an inverse theorem and the Erdős-Graham irregularity problem

Mateo Matijasevick
arXiv (Cornell University)
Limits and Structures in Graph Theory
preprint

Forbidden subset sums in a linear range: an inverse theorem and the Erdős-Graham irregularity problem

Mateo Matijasevick
preprint en

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 $00$, 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.

arXiv (Cornell University)
Limits and Structures in Graph Theory
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon