Skip to content
DraconiticResearch
Search Sources API
226,742 studies31 sourcesUpdated 47 min ago
PreprintarXiv licencearXiv

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

  1. A Complete Solution to the Conjecture on the Inverse Collatz–Sinogowitz Irregularity Problem
    Xue Ji, Zhiwen Wang, Ji-Ming Guo
    Discrete Mathematics LettersPeer-reviewedCC BYFull textGeometry & topologyDOAJ
  2. Applying the convolution theorem to the two-dimensional magnetic inverse problem
    Michael T. M. Woodley
    arXivPreprintarXiv licenceFull textMathematical physicsarXiv
  3. Analytic Combinatorics of Lattice Paths with Forbidden Patterns: Asymptotics Aspects and Borges's Theorem
    Andrei Asinowski, Axel Bacher, Cyril Banderier +1
    Leibniz International Proceedings in InformaticsPeer-reviewedCC BY 4.0Full textAnalysis & PDEsCombinatorics & discrete mathematicsHAL
  4. Linear dependencies, polynomial factors in the Duke–Erdős forbidden sunflower problem – CORRIGENDUM
    Andrey Kupavskii, Fedor Noskov
    Forum of Mathematics, SigmaPeer-reviewedCC BY 4.0General mathematicsCrossref
  5. New approaches to the Erdős Distinct Subset Sums Problem
    Aren Hasratyan, Miklós Ruszinkó
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
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  -