🔢 mathematics

A Stretched-Exponential Bound for an Erdos--Graham Unit-Fraction Problem

This paper proves a stretched-exponential bound, $\varepsilon(A)\leq \exp\bigl(-c\sqrt{K\log K}\bigr)$ , for the distance from 1 to the largest reciprocal subsum of a finite multiset of positive integers with total reciprocal sum exceeding $K$ , thereby improving upon the quadratic bound established by Erdős and Graham and providing significant progress toward their conjecture of a pure exponential decay.

Original authors: Samuel Korsky

Published 2026-07-07

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Samuel Korsky

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Picture: The "Perfect 1" Puzzle

Imagine you have a giant bag of different-sized Lego bricks. Each brick has a number on it, like 2, 3, 5, or 100. The rule of the game is that the "value" of a brick is 1 divided by its number.

A brick labeled "2" has a value of 1/2.
A brick labeled "3" has a value of 1/3.
A brick labeled "100" has a value of 1/100.

The Goal: You want to pick a handful of these bricks and stack them together so their total value is exactly 1.

The Problem: Sometimes, no matter how many bricks you have, you can't get the stack to equal exactly 1. You might get very close—like 0.999—but you miss the mark. The paper asks: If you have a huge pile of bricks (a lot of "mass"), how close can you get to 1 without hitting it exactly?

The Old Guess vs. The New Discovery

Mathematicians Paul Erdős and Ronald Graham looked at this problem years ago. They proved that if your pile of bricks is big enough, you can't miss the target by much. They showed the gap (the distance between your stack and 1) gets smaller as the pile gets bigger, but they thought it might shrink very fast—like an exponential curve (think of a ball dropping and bouncing, getting smaller and smaller very quickly).

They asked: Is it true that the gap shrinks super-fast, like $e^{-K}$ ?

The Answer in this Paper:
The author, Samuel Korsky, says: "Not quite that fast, but still incredibly fast."
He proves that the gap shrinks at a "stretched-exponential" rate.

The Analogy: Imagine the "perfect 1" is a target on a wall.
- The old guess was that if you double your number of bricks, your aim gets exponentially better (you get infinitely closer).
- Korsky proves that your aim gets better at a rate that is almost exponential, but slightly "stretched" out. It's like running a race where you get faster and faster, but you have to run a slightly longer distance to reach that top speed.
- Mathematically, the gap is roughly $e^{-\sqrt{K \log K}}$ . This is still a tiny, tiny number for large piles, meaning you are almost guaranteed to hit 1 if you have enough bricks.

How Did He Solve It? (The Three-Step Strategy)

To prove this, the author had to deal with a chaotic mess of numbers. He used a clever three-step process to organize the chaos.

1. The "Compression" (Folding the Map)

Imagine you have a messy pile of bricks where you have 100 copies of the "1/100" brick.

The Trick: The author realized that 100 copies of "1/100" is the same as 10 copies of "1/10". And 10 copies of "1/10" is the same as 1 copy of "1/1".
The Action: He systematically "compressed" the pile. If he saw enough small bricks to make a bigger one, he swapped them out for the bigger one.
The Result: He turned a messy, huge pile into a "stable" pile where no number appears too many times. This made the math much easier to handle, like folding a giant map into a small pocket size.

2. The "Random Activation" (The Dice Roll)

Now, he needed to show that in this "stable" pile, there must be a combination that hits 1.

The Analogy: Imagine you are trying to find a specific combination of ingredients to bake a cake. Instead of checking every single recipe, you decide to randomly pick ingredients.
The Method: He used a mathematical "dice roll" (probability). He asked: "If I randomly pick a subset of these compressed bricks, what is the chance the total is close to 1?"
The Insight: He proved that if the pile is big enough, the "random picks" will inevitably land in the "danger zone" (the tiny gap just below 1). If they land there, it means a perfect combination must exist.

3. The "Divisor Sorting" (Organizing the Chaos)

The hardest part was dealing with "composite" numbers (numbers made of smaller numbers, like 6, 12, 15). These are tricky because they share factors with other numbers.

The Analogy: Imagine trying to sort a pile of mixed-up keys. Some keys open many doors; some open only one.
The Method: He created a system to sort these "keys" (numbers) based on how many other numbers they divide. He separated the "easy" numbers (primes) from the "hard" numbers (composites).
The Result: By sorting them, he could prove that the "hard" numbers didn't mess up the math enough to prevent the "random pick" from hitting the target.

The "AI" Twist

At the very end of the paper, the author includes a unique note: He used AI (GPT-5.5 Pro) to help write the proof.

What the AI did: The author came up with the big ideas (the compression, the random strategy, the main logic). The AI helped fill in the boring, difficult technical details, checked the math constants, and helped write the code to verify the complex steps.
The Human Role: The author took full responsibility for the final result, verifying that the AI didn't make any mistakes. It's like an architect designing a building and using a robot to help lay the bricks and check the measurements.

Summary

The paper solves a 50-year-old puzzle about adding fractions. It proves that if you have a large enough collection of unit fractions, you can get extremely close to a sum of 1. The gap between your sum and 1 shrinks incredibly fast (a "stretched exponential" rate). The author solved this by compressing the numbers, using probability to find the solution, and sorting the difficult numbers, with significant help from AI to handle the heavy mathematical lifting.

Technical Summary: A Stretched-Exponential Bound for an Erdős–Graham Unit-Fraction Problem

Problem Statement
The paper addresses a question posed by Erdős and Graham regarding the distribution of reciprocal sums of finite multisets of positive integers. For a finite multiset $A$ , let $R(A) = \sum_{a \in A} a^{-1}$ be the total reciprocal sum, and let $\varepsilon(A)$ denote the distance from 1 to the largest reciprocal subsum of $A$ that does not exceed 1. Specifically, $\varepsilon(A) = 1 - \max \{ R(S) : S \subseteq A, R(S) \le 1 \}$ .

Erdős and Graham established that if $R(A) > K$ , then $\varepsilon(A) \ll K^{-2}$ . They asked whether a significantly stronger exponential bound holds: whether there exists an absolute constant $c > 0$ such that $R(A) > K$ implies $\varepsilon(A) \le e^{-cK}$ for all sufficiently large $K$ . This exponential conjecture remains open. The current work proves a "stretched-exponential" intermediate bound.

Methodology
The proof employs a combination of deterministic compression, probabilistic activation, and analytic number theory techniques.

Compression and Reduction:
The authors begin by selecting a maximal submultiset $S$ with $R(S) \le 1$ and defining the remainder $B = A \setminus S$ . They apply a deterministic "stable compression" procedure to $B$ . This process repeatedly replaces $p$ copies of $1/n$ (where $p$ is a prime divisor of $n$ ) with a single formal copy of $1/(n/p)$ . This yields a stable multiset $C$ with the same total reciprocal mass as $B$ , where multiplicities $m_n$ satisfy $m_n < P^-(n)$ (the least prime factor of $n$ ). Crucially, no submultiset of $C$ has a reciprocal sum in the interval $(1 - N^{-2}, 1)$ , where $N = \varepsilon(A)^{-1}$ .
The Activation Package:
The core analytic tool is a "sparse activation" lemma. The authors construct a random reciprocal subsum by activating a sparse random set of denominator types and choosing uniform coefficients within allowed ranges.
- Divisor Sorting: A high-frequency analysis controls the characteristic function of the sum, bounding the number of divisors of integers in specific ranges.
- One-Sided Local Limit Theorem: A smoothed local limit lemma is used to force the random sum to fall into the forbidden interval $(1 - N^{-2}, 1)$ unless the total mass of the set is small.
- Ratio Classes: The estimates are split based on the ratio $\alpha \approx m_n/n$ . For small $\alpha x$ (where $x = \log N$ ), a bound involving $\sqrt{\alpha x}$ is derived. For prime denominators with large $\alpha x$ , a linear bound in $\alpha x$ is established.
Mass Estimation:
The total mass $R(C)$ is decomposed into three parts:
- Prime Denominators: Controlled using the divisor-count bound $\omega(q) \ll x/\log x$ and the activation package.
- Small Composite Denominators: Bounded using a "rough-number" sieve estimate (Lemma 4.1), which limits the sum of reciprocals of composites with restricted multiplicities.
- Large Composite Denominators: Controlled via a dyadic decomposition of denominators and multiplicities. Stability conditions ensure that prime factors are large relative to multiplicities, allowing for divisor-incidence bounds. An exponential crossing sum lemma is used to optimize the summation over dyadic scales.

Key Results
The paper establishes the following theorem:

Theorem 1.1: There exist absolute constants $c > 0$ and $K_0$ such that for every finite multiset $A$ of positive integers satisfying $R(A) > K \ge K_0$ ,
$\varepsilon(A) \le \exp\left(-c \sqrt{K \log K}\right).$

This result improves upon the previously known polynomial bound $\varepsilon(A) \ll K^{-2}$ but falls short of the full exponential conjecture $\varepsilon(A) \le e^{-cK}$ . The authors note that a standard lower-bound construction (using copies of primes up to $z$ ) yields $\varepsilon(A_z) \ge \exp(-(1+o(1)) R(A_z) \log R(A_z))$ , suggesting that the true behavior lies between the polynomial and full exponential regimes, and that the problem cannot be resolved solely by lattice arguments.

Significance and Claims
The paper claims to provide the first significant improvement over the polynomial bound for the Erdős–Graham unit-fraction problem, moving the field toward the conjectured exponential decay. The significance lies in:

Quantitative Progress: Establishing a stretched-exponential bound $\exp(-c\sqrt{K \log K})$ .
Methodological Innovation: Introducing a "stable compression" framework combined with a "sparse activation" probabilistic method to handle multisets with arbitrary multiplicities.
Analytic Rigor: Providing a detailed proof involving divisor sorting, one-sided local limit theorems, and precise arithmetic estimates for composite numbers with restricted prime factors.

The authors explicitly state that their results do not resolve the full exponential conjecture and that the problem remains open. The work is presented as a step toward understanding the density of reciprocal sums near 1, distinguishing between the behavior of sets with distinct denominators (where stronger results exist) and general multisets.