Skip to content
DraconiticResearch
Search Sources API
186,546 studies31 sourcesUpdated 19 min ago
PreprintarXiv licencearXiv

A near-quadratic lower bound for sets with no unique sums

  • Jianfeng Hou
  • Kai Yang
Open at sourcePDFDOICite

Abstract

Let m(p) be the least size of a subset of Fp with at least two elements for which every sum has two distinct representations as unordered pairs, allowing repetition. We prove that, for every prime p≥64, m(p)≥2−80((log p)/(loglog p))2. The argument compresses the full integer collision lattice by unit-pivot elimination. A shared random sample and forests of bounded diameter give O(√n+n/log p) surviving coordinates of polynomial height for a minimal set of size n. A nonzero minor divisible by p then gives the lower bound. We also construct weakly ternary-balanced seeds yielding m(p)≤((log p)2)/2(log3)2 +(1/4log3+o(1)) ((log p)2)/(loglog p). Consequently m(p)=(log p)2+o(1) as p tends to infinity through the primes. The constant-factor order of m(p) remains undetermined.

Related

  1. A near-quadratic lower bound for the Brown--Erdős--Sós (9,6)-problem
    Xiangliang Kong, Chong Shangguan, Xin Wang
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  2. A Nearly Quadratic Lower Bound for Linear Optimization over Convex Bodies in the Membership Oracle Model
    Santosh S. Vempala
    arXivPreprintarXiv licenceFull textAnalysis & PDEsOptimisation & controlarXiv
  3. A Quadratic Lower Bound on Determinantal Complexity
    Mrinal Kumar, Ben Lee Volk
    arXivPreprintarXiv licenceFull textAlgebra & number theoryarXiv
  4. A Quadratic Lower Bound for the Shield Number of the Stable Marriage Problem: Rearrangement, Extremal Construction, and Biclique Realizability
    Yoshiteru Ishida
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  5. A short proof of a quadratic lower bound on the border determinantal complexity of x1n+⋯+xnn over ℂ: A simple human exposition
    Karthik Sheshadri
    arXivPreprintCC BY 4.0Full textAlgebra & number theoryarXiv

Cite

BibTeXRIS
BibTeX
@misc{hou2026nearquadratic,
  title = {{A near-quadratic lower bound for sets with no unique sums}},
  author = {Jianfeng Hou and Kai Yang},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.09349},
  eprint = {2610.09349},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.09349},
}
RIS
TY  - UNPB
TI  - A near-quadratic lower bound for sets with no unique sums
AU  - Jianfeng Hou
AU  - Kai Yang
PY  - 2026
DA  - 2026/10/07
PB  - arXiv
DO  - 10.48550/arxiv.2610.09349
UR  - https://arxiv.org/abs/2610.09349
AB  - Let m(p) be the least size of a subset of F_p with at least two elements for which every sum has two distinct representations as unordered pairs, allowing repetition. We prove that, for every prime p≥64, m(p)≥2^−80((log p)/(loglog p))^2. The argument compresses the full integer collision lattice by unit-pivot elimination. A shared random sample and forests of bounded diameter give O(√n+n/log p) surviving coordinates of polynomial height for a minimal set of size n. A nonzero minor divisible by p then gives the lower bound. We also construct weakly ternary-balanced seeds yielding m(p)≤((log p)^2)/2(log3)^2 +(1/4log3+o(1)) ((log p)^2)/(loglog p). Consequently m(p)=(log p)^2+o(1) as p tends to infinity through the primes. The constant-factor order of m(p) remains undetermined.
ER  -