Erdős Problem #148

Erdős Problem #148 (Round 2): a self-contained lower bound of size $\exp(\Omega(k^2))$

1) ROUND-2 OBJECTIVE

For Problem #148, the original task is not a single true/false statement but an estimation problem. So paths (A) and (B) from the generic Round-2 template do not literally apply. I therefore pursue the Round-2 analogue of path (C): I keep the statement as an asymptotic estimation problem and strengthen the lower-bound side of the estimate.

Concretely, Round 1 produced the fully self-contained bound \[ F(k)\ge 3^{k-3}. \] The exact Round-2 goal is to prove a substantially stronger self-contained lower bound.

2) Round-1 FOUNDATION USED

I use the following Round-1 ingredients and do not reprove them from scratch.

1. The Round-1 splitting identity: \[ \frac1N=\frac1{N+m}+\frac1{N(N+m)/m} \qquad\mbox{whenever }m\mid N,\ 1\le m<N. \]
2. The Round-1 strategy of always splitting the current largest denominator.
3. The Round-1 observation that if one always splits the current largest denominator, then all smaller denominators created in earlier steps remain untouched forever.

3) NEW INSIGHT / TOOL (ROUND 2)

The new ingredient is a two-phase branching scheme.

1. Divisor-amplification phase. Repeatedly use the choice $m=1$ to force the current largest denominator to acquire many divisors.
2. Frozen-divisor branching phase. Once a divisor-rich denominator $M$ has been created, use every proper divisor of $M$ as a branching choice at every later step. Because every later largest denominator remains a multiple of $M$, all these choices remain valid forever.

This replaces the Round-1 fixed three-choice branching argument by a branching factor that grows exponentially during the build-up phase.

4) ATTACK PLAN (ROUND 2)

The exact gap after Round 1 was this: the lower bound came from keeping only the three divisors $1,2,3$ of the initial largest denominator $6$. That leaves a lot of unused structure, because the current largest denominator typically acquires many more divisors after repeated splittings.

So I will prove the following claims.

1. After $r$ repeated uses of $m=1$, the largest denominator $M_r$ has at least $2^{r+2}$ positive divisors.
2. Once the current largest denominator is divisible by $M_r$, every proper divisor of $M_r$ yields a valid next split, and this divisibility by $M_r$ is preserved forever.
3. Distinct branching sequences in the second phase yield distinct final Egyptian-fraction representations.

From these claims one gets a family of lower bounds \[ F(3+r+s)\ge (\tau(M_r)-1)^s, \] where $\tau(n)$ denotes the number of positive divisors of $n$. Optimising over $r+s=k-3$ will then give the explicit estimate \[ F(k)\ge 2^{\lfloor (k-3)^2/4\rfloor}. \]

5) WORK (ROUND 2)

Step 1: build-up by repeated choice $m=1$.

Start from the Round-1 base representation \[ 1=\frac12+\frac13+\frac16. \] Let $M_0:=6$. For $j\ge 0$, define recursively \[ M_{j+1}:=M_j(M_j+1), \] which is exactly the new largest denominator obtained from $M_j$ by the Round-1 splitting identity with $m=1$: \[ \frac1{M_j}=\frac1{M_j+1}+\frac1{M_j(M_j+1)}. \]

Thus, after $r$ such steps we obtain a valid representation of $1$ with $3+r$ terms whose largest denominator is $M_r$.

Step 2: divisor count grows at least exponentially.

Let $\tau(n)$ denote the number of positive divisors of $n$. Since consecutive integers are coprime, \[ \gcd(M_j,M_j+1)=1, \] hence \[ \tau(M_{j+1})=\tau(M_j)\tau(M_j+1)\ge 2\tau(M_j) \] because $M_j+1>1$ and therefore $\tau(M_j+1)\ge 2$.

Since $\tau(M_0)=\tau(6)=4$, induction gives \[ \tau(M_r)\ge 4\cdot 2^r=2^{r+2}. \]

Step 3: all proper divisors of $M_r$ stay available forever.

Fix $r\ge 0$, and suppose we are at some later stage of the process where the current largest denominator is $L$ and $M_r\mid L$.

Let $d$ be any proper divisor of $M_r$. Then $d\mid L$ as well, so the Round-1 splitting identity gives \[ \frac1L=\frac1{L+d}+\frac1{L(L+d)/d}. \] The new largest denominator is \[ L':=\frac{L(L+d)}{d}=L\left(\frac{L}{d}+1\right). \] Since $M_r\mid L$, it follows immediately that $M_r\mid L'$. Therefore the property \[ M_r \mid \mbox{(current largest denominator)} \] is preserved after every such split.

Consequently, once the process reaches $M_r$, there are always at least \[ \tau(M_r)-1 \] available branching choices at every later step, namely all proper divisors of $M_r$.

Step 4: injectivity of the branching phase.

Now fix $r\ge 0$. After the build-up phase we have a representation whose current largest denominator is $M_r$.

Run a second phase of length $s\ge 0$. At each of the $s$ steps, choose an arbitrary proper divisor $d_i$ of $M_r$ and split the current largest denominator $L_i$ using $d_i$: \[ \frac1{L_i}=\frac1{L_i+d_i}+\frac1{L_{i+1}}, \qquad L_{i+1}=\frac{L_i(L_i+d_i)}{d_i}. \]

I claim that distinct sequences $(d_1,\dots,d_s)$ produce distinct final Egyptian-fraction representations.

Indeed, at step $i$ the split creates the denominator \[ a_i:=L_i+d_i. \] Because $d_i<L_i$, one has \[ a_i=L_i+d_i < \frac{L_i(L_i+d_i)}{d_i}=L_{i+1}. \] So $a_i$ is not the new largest denominator. Since all later steps split only the current largest denominator, the denominator $a_i$ is never altered again. In particular, each $a_i$ survives to the final representation.

Now suppose two branching sequences first differ at time $t$. Up to step $t-1$ they have the same current largest denominator $L_t$, but then choose different proper divisors $d_t\neq d'_t$. Hence they create different surviving denominators \[ a_t=L_t+d_t \neq L_t+d'_t=a'_t. \] Since both $a_t$ and $a'_t$ persist to the end, the two final representations are different.

Therefore the number of distinct final representations produced by an $s$-step branching phase is at least \[ (\tau(M_r)-1)^s. \]

Step 5: the general lower bound.

Combining the previous steps, we have proved:

Theorem. For every pair of integers $r,s\ge 0$, \[ F(3+r+s)\ge (\tau(M_r)-1)^s, \] where \[ M_0=6,\qquad M_{j+1}=M_j(M_j+1). \] In particular, since $\tau(M_r)\ge 2^{r+2}$, \[ F(3+r+s)\ge (2^{r+2}-1)^s. \]

Now set \[ r:=\lfloor \frac{k-3}{2}\rfloor, \qquad s:=k-3-r=\lceil \frac{k-3}{2}\rceil. \] Then \[ F(k)\ge (2^{r+2}-1)^s \ge (2^r)^s = 2^{rs}. \] Since \[ rs=\lfloor \frac{(k-3)^2}{4}\rfloor, \] we obtain the explicit Round-2 lower bound \[ F(k)\ge 2^{\lfloor (k-3)^2/4\rfloor}. \]

Conclusion for Problem #148.

Round 2 therefore upgrades the Round-1 self-contained lower bound from \[ F(k)\ge 3^{k-3} \] to the much stronger estimate \[ F(k)\ge 2^{\lfloor (k-3)^2/4\rfloor}. \] This is a genuine quantitative improvement from merely exponential growth in $k$ to growth of order $\exp(\Omega(k^2))$.

6) ADVERSARIAL VERIFICATION

I check the main possible failure modes.

1. Could a chosen divisor fail to remain valid later? No. Every branching divisor $d$ is chosen from the fixed divisor set of $M_r$, and every later largest denominator remains a multiple of $M_r$, hence also a multiple of $d$.
2. Could two different branching sequences merge later? The revised injectivity argument avoids this issue entirely. It does not rely on the final largest denominator. Instead it uses the permanently surviving denominators $a_i=L_i+d_i$, which encode the first place where two sequences differ.
3. Could one of the survivor denominators be altered later? No. At the moment it is created, it is smaller than the new largest denominator $L_{i+1}$, and every later operation only replaces the current largest denominator.
4. Are the resulting denominators still distinct and increasing? Yes. Every newly created denominator is strictly larger than the previous largest denominator, hence larger than all pre-existing denominators.

7) FINAL

UNRESOLVED (BUT STRICTLY ADVANCED).

Round 2 does not settle the full asymptotic growth problem, but it makes a real mathematical advance over Round 1: it proves the self-contained bound \[ F(k)\ge 2^{\lfloor (k-3)^2/4\rfloor}, \] which is much stronger than the Round-1 bound $3^{k-3}$.

The remaining gap is still enormous compared with the best known lower bound recorded on the Erdős Problems site, but the internal branching method is now meaningfully sharper.

8) COMPLETION ESTIMATE

COMPLETION: 55%

9) REFERENCES

1. Erdős Problems, Problem #148, "For each $k$, let $F(k)$ be the number of representations of $1$ as a sum of $k$ distinct unit fractions...", checked on 7 March 2026.

Problem 148: decoding the splitting tree and retaining the lower-order gain

1) OBJECTIVE AND SOURCE REVIEW

Attempt dated 2026-09-23. The target is the growth of $F(k)$, the number of representations of 1 by $k$ distinct positive unit fractions. I read gpt_pro_5.4/148.tex fully. Its two-phase splitting construction is useful, but the assertion that two different persistent denominators force different final sets needs their positions in the ordered list to be specified. I supply that decoding and optimize the quantitative bound without discarding two powers of 2 at every branching step.

2) WORK

Start with $(2,3,6)$ and replace a largest denominator $L$, using $d\mid L$ and $d<L$, by \[ L+d,\qquad L'=L(L+d)/d. \] Both exceed $L$ and $L+d<L'$. Thus every frozen denominator is smaller than every denominator created later. In the final increasing list the frozen denominators occur in chronological order. Given the fixed initial list and a final list, the first newly frozen entry recovers $d=(L+d)-L$; it also recovers $L'$. Induction recovers the entire sequence of choices. This is a full injectivity proof, not just persistence of individual entries.

After $r$ forced choices $d=1$, the largest denominator $M_r$ satisfies $M_0=6$, $M_{j+1}=M_j(M_j+1)$. Coprimality of the factors gives $\tau(M_r)\ge2^{r+2}$. All proper divisors of $M_r$ remain valid in each later step, since the current largest denominator remains a multiple of $M_r$. The decoded branching tree therefore proves \[ F(3+r+s)\ge(2^{r+2}-1)^s. \] Put $u=\lfloor(k-1)/2\rfloor$, $r=u-2$, and $s=k-1-u$. For $k\ge7$ these are nonnegative, $u\ge3$, and $s\le u+1$. Consequently \[ (1-2^{-u})^s\ge1-s2^{-u}\ge\frac12 \] by Bernoulli's inequality. Since $us=\lfloor(k-1)^2/4\rfloor$, we obtain the explicit refinement \[ F(k)\ge2^{\lfloor(k-1)^2/4\rfloor-1}\qquad(k\ge7). \] The leading quadratic exponent agrees with the supplied construction; the gain is a rigorously retained linear-order term, not a new growth scale.

3) ADVERSARIAL VERIFICATION

Different branches might contain some of the same numbers later, so persistence alone is insufficient; their ordered ranks are what ensure injectivity. All fractions remain distinct because both children exceed the replaced maximum. The estimate concerns a subset of all representations and gives no matching upper bound.

4) FINAL

UNRESOLVED. The splitting family has been rigorously decoded and its bound modestly sharpened. Determining the asymptotic growth of all representations remains open in this attempt; no improvement over the strongest literature bounds is claimed.

5) SOURCES CHECKED

Complete supplied file, read 2026-09-23. The splitting, divisor count, and optimization are proved directly without importing an external asymptotic estimate.

6) COMPLETION ESTIMATE

Subjective progress toward the estimation problem. COMPLETION: 12%

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").

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

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)$.

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%