we-solve (beta)

Math-692-A2 · revision r1 · on Math-692

gpt pro 5.2 attempt on Math-692

No claim recorded · LLM-generated · gpt pro 5.2 ·

Unverified LLM-generated attempt. Automated screening checks form, honesty and scope, not correctness. Status at erdosproblems.com: open. Claims here do not change the source status.

Manuscript

Contents
  1. Erdős Problem #148: Counting Egyptian fraction representations
  2. FORMAL RESTATEMENT
  3. QUICK LITERATURE/CONTEXT CHECK
  4. DEFINITIONS / SETUP
  5. KNOWN RESULTS I WILL USE
  6. MAIN ATTEMPT
  7. 1) Exact values for small $k$
  8. 2) A fully self-contained exponential lower bound
  9. 3) A fully self-contained double-exponential upper bound via Sylvester
  10. ADVERSARIAL CHECK
  11. FINAL

Erdős Problem #148: Counting Egyptian fraction representations

FORMAL RESTATEMENT

For each integer $k\ge 1$, let $F(k)$ be the number of strictly increasing $k$-tuples $(n_1,\dots,n_k)\in \mathbb{N}^k$ with \[ 1 \;=\; \frac{1}{n_1}+\cdots+\frac{1}{n_k} \quad\text{and}\quad 1\le n_1<\cdots<n_k. \] The problem asks for good estimates for $F(k)$ as $k\to\infty$.

Ambiguity note. The prompt is open-ended (not a single proposition to prove/disprove). I interpret "good estimates" as: find explicit functions $L(k),U(k)$ with $L(k)\le F(k)\le U(k)$ and with $L,U$ as close as possible on a double-exponential scale (e.g. matching the correct order of magnitude of $\log\log F(k)$).

QUICK LITERATURE/CONTEXT CHECK

The Erdős Problems database currently records the best known general bounds as \[ 2^{c^{k/\log k}} \;\le\; F(k)\;\le\; c_0^{(\frac15+o(1))2^k}, \] where $c>0$ is an absolute constant and $c_0\approx 1.26408\ldots$ is the Vardi constant. The lower bound is attributed to Konyagin (with later errata/clarifications noted on the problem discussion page), and the upper bound to Elsholtz--Planitzer.

What I do here. I do not reprove these deep best-known bounds. Instead I:

  • compute $F(k)$ exactly for $k\le 6$ via exhaustive backtracking, as a consistency check;
  • give a clean, fully self-contained exponential lower bound $F(k)\ge 3^{k-3}$;
  • give a clean, fully self-contained double-exponential upper bound of the form $F(k)\le k^k \prod_{i=1}^k u_i$, where $(u_i)$ is the Sylvester sequence, implying $F(k)\le (c_0+o(1))^{2^{k+1}}$.

DEFINITIONS / SETUP

  • A unit fraction is a rational number of the form $1/n$ with $n\in\mathbb{N}$.
  • An Egyptian fraction representation of $1$ with $k$ terms is a strictly increasing sequence $1\le n_1<\cdots<n_k$ such that $1=\sum_{i=1}^k 1/n_i$.
  • The Sylvester sequence $(u_i)_{i\ge 1}$ is defined by \[ u_1=1,\qquad u_{i+1}=u_i(u_i+1)\ \ (i\ge 1). \] It is classical that $u_i$ grows doubly exponentially; one defines \[ c_0 := \lim_{i\to\infty} u_i^{2^{-i}}, \] the so-called Vardi constant ($c_0\approx 1.26408\ldots$).

KNOWN RESULTS I WILL USE

All items below are proved in-line (so "known" means "standard and I will verify it").
Lemma (Two-term splitting identity): Let $n\in\mathbb{N}$ and let $m$ be a proper divisor of $n$ (i.e. $m\mid n$ and $1\le m<n$). Then \[ \frac{1}{n} \;=\; \frac{1}{n+m} + \frac{1}{\frac{n(n+m)}{m}}, \] and the two denominators $n+m$ and $\frac{n(n+m)}{m}$ are distinct integers exceeding $n$.
Proof: Compute \[ \frac{1}{n+m} + \frac{1}{n(n+m)/m} = \frac{1}{n+m} + \frac{m}{n(n+m)} = \frac{n}{n(n+m)}+\frac{m}{n(n+m)} = \frac{n+m}{n(n+m)} = \frac{1}{n}. \] Since $m\mid n$, the quantity $n(n+m)/m$ is an integer. Also $n+m>n$ and $n(n+m)/m\ge n(n+1)/m>n$. Finally, if $n+m = n(n+m)/m$ then $m=n$, contradicting $m<n$. ∎
Lemma (A standard independent-set lower bound): If $G$ is a graph on $N$ vertices with maximum degree at most $\Delta$, then $\alpha(G)\ge \frac{N}{\Delta+1}$.
Proof: Greedy algorithm: iteratively pick a vertex, add it to an independent set, and delete it together with its (at most $\Delta$) neighbors. Each chosen vertex removes at most $\Delta+1$ vertices, so we choose at least $N/(\Delta+1)$ vertices. ∎

MAIN ATTEMPT

1) Exact values for small $k$

Using backtracking with the elementary bounds \[ n_i \ge \left\lceil \frac{1}{\text{(remaining sum)}}\right\rceil, \qquad n_i \le \left\lfloor \frac{\text{(\# remaining terms)}}{\text{(remaining sum)}} \right\rfloor, \] I enumerated all solutions for $k\le 6$. The results are: \[ F(1)=1,\quad F(2)=0,\quad F(3)=1,\quad F(4)=6,\quad F(5)=72,\quad F(6)=2320. \] For instance, the $k=4$ solutions are \[ (2,3,7,42),\ (2,3,8,24),\ (2,3,9,18),\ (2,3,10,15),\ (2,4,5,20),\ (2,4,6,12). \] These values agree with the rapid growth expected from the literature.

2) A fully self-contained exponential lower bound

Proposition (Elementary exponential growth): For every $k\ge 3$ one has \[ F(k)\ \ge\ 3^{k-3}. \]
Proof: Start from the valid $3$-term representation \[ 1=\frac12+\frac13+\frac16, \] whose largest denominator is $6$, divisible by $6$.

We define an operation that increases the number of terms by one: given a representation with largest denominator $N$ (necessarily $N\ge 6$ and divisible by $6$), replace the term $1/N$ using Lemma Lemma (Two-term splitting identity) with one of the three choices $m\in\{1,2,3\}$: \[ \frac1N = \frac{1}{N+m} + \frac{1}{\frac{N(N+m)}{m}} \qquad (m=1,2,3). \] Since $m\mid N$ for $m=1,2,3$, this is always valid, and it replaces one term by two distinct terms with denominators $>N$. Therefore, the resulting list of denominators remains distinct, and after sorting we again have a strictly increasing representation of $1$.

Let $N'$ denote the new largest denominator; it is \[ N'=\frac{N(N+m)}{m}. \] We claim $N'$ is again divisible by $6$:

  • For $m=1$, $N'=N(N+1)$ is divisible by $6$ because it is a product of two consecutive integers and $N$ is divisible by $6$.
  • For $m=2$, since $N$ is divisible by $6$, $N/2$ is divisible by $3$, and $N+2$ is even, so $N'=(N/2)(N+2)$ is divisible by $6$.
  • For $m=3$, $N'=(N/3)(N+3)$ with $N/3$ even and $N+3$ divisible by $3$, hence divisible by $6$.
Thus the operation can be iterated indefinitely while always keeping three available choices.

Finally, different choices of $m$ at the first step already yield different new largest denominators $N'$, hence different resulting $k$-tuples. By induction on the first index where two choice-sequences differ, we see that distinct sequences of $m$'s produce distinct final representations. Therefore after $t=k-3$ iterations we obtain at least $3^t=3^{k-3}$ distinct representations of length $k$. ∎

3) A fully self-contained double-exponential upper bound via Sylvester

The following is a standard "Sylvester sequence" argument giving an explicit upper bound on the sizes of denominators in any solution, hence also an explicit (although crude) upper bound on $F(k)$.
Lemma (Sylvester-type control of partial remainders): Let $k\ge 1$ and let $x_1\le x_2\le \cdots\le x_k$ be integers such that $1=\sum_{i=1}^k \frac1{x_i}$. For $0\le m\le k$ define $y_m\in \mathbb{Q}_{>0}\cup\{\infty\}$ by \[ 1-\sum_{i=1}^m \frac1{x_i}=\frac1{y_m} \quad\text{(so $y_0=1$ and $y_k=\infty$)}. \] Then for $0\le m\le k-1$ we have the recurrence bound \[ y_{m+1}\ \le\ y_m(y_m+1), \] and hence $y_m\le u_{m+1}$ for all $0\le m\le k-1$.
Proof: Fix $0\le m\le k-1$. Since the remaining sum after $m$ terms is \[ \frac1{y_m} = \frac{1}{x_{m+1}}+\cdots+\frac{1}{x_k}, \] we have $x_{m+1}\ge y_m+1$ (because $x_{m+1}>y_m$; if $x_{m+1}\le y_m$ then $1/x_{m+1}\ge 1/y_m$, forcing the remaining sum to be $\ge 1/y_m$ with equality only if all other terms vanish, impossible unless $m=k-1$). Compute \[ \frac1{y_{m+1}}=\frac1{y_m}-\frac1{x_{m+1}}=\frac{x_{m+1}-y_m}{y_m x_{m+1}}. \] Since $x_{m+1}-y_m\ge 1$, we obtain \[ \frac1{y_{m+1}} \ge \frac{1}{y_m x_{m+1}} \ge \frac{1}{y_m(y_m+1)}. \] Taking reciprocals gives $y_{m+1}\le y_m(y_m+1)$.

Now compare to Sylvester: $u_1=1$ and $u_{i+1}=u_i(u_i+1)$, so by induction $y_m\le u_{m+1}$. ∎

Proposition (Crude double-exponential upper bound): For every $k\ge 1$, \[ F(k) \ \le\ k^k \prod_{i=1}^k u_i, \] where $(u_i)$ is the Sylvester sequence. In particular, since $u_i \le (c_0+o(1))^{2^i}$, \[ F(k) \ \le\ (c_0+o(1))^{2^{k+1}} \qquad\text{as }k\to\infty. \]
Proof: Let $(x_1,\dots,x_k)$ be a solution with $x_1<\cdots<x_k$. From Lemma Lemma (Sylvester-type control of partial remainders), for each $1\le i\le k$ the remainder after $i-1$ terms satisfies $y_{i-1}\le u_i$ and \[ \frac1{y_{i-1}} = \frac{1}{x_i}+\cdots+\frac{1}{x_k} \le \frac{k}{x_i}. \] Hence $x_i \le k y_{i-1} \le k u_i$. Therefore each coordinate $x_i$ lies in $\{1,2,\dots, k u_i\}$, and the number of possible $k$-tuples is at most $\prod_{i=1}^k (k u_i)=k^k\prod_{i=1}^k u_i$, giving the claimed bound on $F(k)$.

Finally, the definition of $c_0$ implies $u_i=(c_0+o(1))^{2^i}$, so $\prod_{i=1}^k u_i = (c_0+o(1))^{\sum_{i=1}^k 2^i}=(c_0+o(1))^{2^{k+1}}$. ∎

ADVERSARIAL CHECK

  • Lower bound injectivity. The proof of Proposition Proposition (Elementary exponential growth) relies on the fact that distinct sequences of choices $m\in\{1,2,3\}$ yield distinct final representations. This is ensured because the largest denominator evolves deterministically via $N\mapsto N(N+m)/m$; two sequences that first differ at step $j$ produce different $N_{j+1}$ at that step, and subsequent operations only increase denominators, so final multisets differ.
  • Upper bound correctness. Proposition Proposition (Crude double-exponential upper bound) counts all integer $k$-tuples bounded coordinate-wise; it does not attempt to enforce strict increase when counting, so it is indeed an upper bound.
  • Growth scale. The upper bound is doubly exponential and very crude compared to the best known $c_0^{(\frac15+o(1))2^k}$; however it is completely self-contained and captures the correct "double-exponential in $k$" phenomenon.

FINAL

UNRESOLVED --- PARTIAL PROGRESS.
  • Farthest point reached. I proved an explicit elementary exponential lower bound $F(k)\ge 3^{k-3}$ and a fully self-contained double-exponential upper bound $F(k)\le k^k\prod_{i\le k}u_i \le (c_0+o(1))^{2^{k+1}}$. I also computed exact values $F(k)$ for $k\le 6$.
  • Remaining gap. The true growth is known to be doubly exponential, but tightening the exponent from the crude constant "$\approx 1$" down to the best known $(1/5+o(1))$ (and improving the lower bound to match on the $\log\log$ scale) requires substantially deeper arguments.
  • Promising next steps. (i) Implement Konyagin-type constructions carefully (taking into account the published errata) to recover a lower bound of the form $2^{c^{k/\log k}}$ in a fully verified way. (ii) Improve the crude Sylvester counting by using sharp upper bounds on the number of representations of a fixed rational as a sum of $3$ or $4$ unit fractions (the Elsholtz--Planitzer strategy).

COMPLETION: 35%