Matching order for Erdős problem 790

Primarily AI-generated textHuman understanding: no partsmath.CO — Combinatorics

Contributed by Grant Huffman, Jensen Kohlmeyer, Will Howe, Liam Kruer ↗

Version 1 / Nov 21, 2026 / CC BY 4.0

Abstract

Let ℓ(n)\ell(n) be the largest size of a subset guaranteed in every nn-element set of integers in which no element is a sum of at least two distinct other elements. We give an upper bound of order n/(log⁡n)2n/(\log n)^2 by propagating mixed averages through a layered construction and lifting repeated-summand relations to distinct summands. Together with Samuel Korsky’s lower bound, this gives matching upper and lower bounds. A linked Lean development proves the upper bound and matching order, with an independent statement bridge.

Author comments: TeX edition of the public matching-order manuscript for JSP-000649. Pinned publication and contributor credits: https://github.com/Ghuffy1/erdos790-jsp/tree/7c3d195fa10d7b52f4fa4a2165b336396d4b21c0 . Pinned proof and statement bridge: https://github.com/Ghuffy1/erdos790-jsp/tree/0a69771b18df655fe47af2d5fb78a7d125fcd5f0

Provenance statement

The manuscript and Lean development acknowledge substantial OpenAI Codex assistance. This TeX edition uses the public JSP manuscript, preserves the attribution of the lower bound to Samuel Korsky, and links the recorded build and direct target checks. An additional fresh whole-closure replay timed out.

References

No bibliography entries.

Version history

  1. v1 · 7 pagesSubmitted by Liam KruerTeX edition of the public matching-order manuscript for JSP-000649. Pinned publication and contributor credits: https://github.com/Ghuffy1/erdos790-jsp/tree/7c3d195fa10d7b52f4fa4a2165b336396d4b21c0 . Pinned proof and statement bridge: https://github.com/Ghuffy1/erdos790-jsp/tree/0a69771b18df655fe47af2d5fb78a7d125fcd5f0CurrentNov 21, 2026