Proof. Let m be an element of $D_k$ and let $(n_1, \ldots, n_k) \in S_k$ contain m. We then aim to construct a $(k+1)$ -tuple in $S_{k+1}$ that also contains m. As one can verify

\begin{align*}D_2 = \emptyset \subseteq D_3 = \{2, 3, 6\} \subseteq \{2, 3, 7, 42\} \cup \{2, 4, 6, 12\} \subseteq D_4,\end{align*}

we may assume $k\ge 4$ .

In analogy with the proof of $F(k) \leq F(k+1)$ , if $m \neq n_k$ , then we first of all remark

\begin{align*}m \in (n_1,\dots,n_{k-1},n_k+1,n_k(n_k+1)) \in S_{k+1}\end{align*}

by (2·1). Secondly, if $m = n_k \notin \{n_{k-1}+1,\;n_{k-1}(n_{k-1}+1)\}$ , then we haveFootnote ²

\begin{align*}m \in (n_1,\dots,n_{k-2}, n_k, n_{k-1}+1,n_{k-1}(n_{k-1}+1)) \in S_{k+1},\end{align*}

once again by (2·1). We may therefore further assume $m = n_k \in \{n_{k-1}+1,\;n_{k-1}(n_{k-1}+1)\}$ from now on.

If $n_{k-1}$ is composite, write $n_{k-1} = ab$ with a and b integers larger than 1. Generalising (2·1), we have the identity

\begin{align*}\frac{1}{n_{k-1}}=\frac{1}{n_{k-1}+a}+\frac{1}{b(n_{k-1}+a)},\end{align*}

while

\begin{align*}n_{k-1}+1 \lt n_{k-1}+a \lt b(n_{k-1}+a) \lt n_{k-1}(n_{k-1}+1).\end{align*}

We therefore deduce

\begin{align*}m \in (n_1,\dots,n_{k-2}, n_k, n_{k-1}+a, b(n_{k-1}+a)) \in S_{k+1}.\end{align*}

On the other hand, if $n_{k-1} = p$ is prime, we claim that $m = n_k \in \{n_{k-1}+1,\;n_{k-1}(n_{k-1}+1)\}$ implies $n_k = n_{k-1}(n_{k-1}+1)$ . To see this, assume by contradiction that $m = n_k$ is equal to $n_{k-1}+1$ instead. We then write

\[\sum_{i=1}^k \frac{1}{n_i}=\frac{1}{p}+\sum_{\substack{1\leq i\leq k\\ i\neq k-1}}\frac{1}{n_i}=\frac{1}{p}+\frac{A}{B}=\frac{Ap+B}{Bp},\]

where ${A}/{B}$ is the reduced form of the remaining sum. Now, by the assumption $n_k = n_{k-1}+1$ , we see that none of the denominators $n_i$ with $i\neq k-1$ are divisible by p, hence $\gcd\!(B,p)=1$ . Thus, for the numerator we have $Ap+B\equiv B\not\equiv 0\pmod p$ , implying that the fraction $(Ap+B)/(Bp)$ cannot simplify to a fraction with denominator not divisible by p. In particular, this fraction is not equal to the integer 1, contradicting the assumption $(n_1,\ldots,n_k)\in S_k$ .

With the assumption that $n_{k-1}$ is prime and the equality $n_k = n_{k-1}(n_{k-1}+1)$ in mind, there are now two final cases to consider.

If $n_{k-1} \neq n_{k-2} + 1$ , then we claim that

\begin{align*}m \in (n_1,\dots,n_{k-3},n_{k-1},n_k,n_{k-2}+1,n_{k-2}(n_{k-2}+1)) \in S_{k+1}.\end{align*}

The sum of reciprocals of this latter tuple is equal to 1 by (2·1), so it suffices to prove that all integers in the tuple are distinct. In other words, we need to show that

\begin{align*}\{n_{k-1}, n_k\} \cap \{n_{k-2}+1,n_{k-2}(n_{k-2}+1) \} = \emptyset.\end{align*}

One sees this by the assumption $n_{k-1} \neq n_{k-2} + 1$ , the assumption that $n_{k-1}$ is prime (hence not equal to $n_{k-2}(n_{k-2}+1)$ ), and the fact that $n_{k} = n_{k-1}(n_{k-1}+1) \gt n_{k-2}(n_{k-2}+1)$ .

If $n_{k-1} = n_{k-2} + 1$ , then $n_{k-2}$ is even and, by the assumption $k \ge 4$ , larger than $n_1 \ge 2$ . Hence, $n_{k-2}$ is composite and we can write $n_{k-2} = ab$ with a and b integers larger than 1. We then see

\begin{align*}m \in (n_1,\dots,n_{k-3},n_{k-1}, n_k, n_{k-2}+a, b(n_{k-2}+a)) \in S_{k+1},\end{align*}

where

\begin{align*}\{n_{k-1}, n_k\} \cap \{n_{k-2}+a,b(n_{k-2}+a) \} = \emptyset\end{align*}

follows similarly as before, in this case using the assumption $n_{k-1} = n_{k-2} + 1 \neq n_{k-2} + a$ .

Proof of Theorem 1·1. By iterating Lemma 2·1 it is sufficient to show that there exists an absolute constant $c \gt 0$ such that for all integers $k \geq 1$ and all integers m with $1 \lt m \lt e^{ck^2}$ we have $m \in D_{k'}$ for some $k' \leq k$ . That is, we need to prove that there exists a unit fraction decomposition of 1 with at most k terms that contains m as one of the denominators.

With C as in Lemma 2·2 we choose

\[c \;:\!=\; \min\!\left(\frac{\log 2}{432^2}, \frac{1}{(433C)^2}\right)\!.\]

Now let m be any integer with $1 \lt m \lt e^{ck^2}$ , and note that we may assume $k\ge 433$ , as for $k\leq 432$ there are no integers m with $1 \lt m \lt e^{ck^2}$ by the definition of c.

We then first consider $m \leq 432$ , in which case it is by the assumption $k \ge 433$ sufficient to show that the denominator m occurs in a unit fraction decomposition of 1 with at most $m+1$ terms. If $m \leq 432$ is not of the form $q(q+1)$ with $q \in \mathbb{N}$ , then we have the decomposition

\[1=\frac1m+\sum_{i=1}^{m-1}\frac{1}{i(i+1)}.\]

The denominators in this decomposition are distinct, since the products $i(i+1)$ are strictly increasing and none of them are equal to m.

On the other hand, if $m=q(q+1)$ for some positive integer q, then we use

\[1=\frac1m+\frac{1}{m+1}+\frac{1}{m(m+1)} +\sum_{\substack{1\leq i\leq m-1\\ i\ne q}}\frac{1}{i(i+1)}.\]

We claim that this is again a decomposition into distinct unit fractions. Indeed, the products $i(i+1)$ are strictly increasing, the product $q(q+1)=m$ has been omitted, and neither $m+1$ nor $m(m+1)$ is equal to one of the remaining products, since

\[q(q+1)\lt m+1\lt(q+1)(q+2),\]

while $i(i+1)\lt m(m+1)$ for all $1\leq i\leq m-1$ . Hence, for every $2\leq m\leq 432$ , there is such a decomposition with at most $m+1 \leq 433$ terms. For the remainder of the proof, we may therefore assume both $k\ge 433$ and $m \ge 433$ . We then apply Lemma 2·2 to the fraction ${a}/{b} = ({m-1})/{m}$ , and there are two different cases to consider.

If m does not occur among the $u_i$ and $v_j$ , then

\begin{align*}\frac{1}{u_1} + \cdots + \frac{1}{u_r} + \frac{1}{v_1} + \cdots + \frac{1}{v_s} + \frac{1}{m}\end{align*}

is a unit fraction decomposition of 1 containing m as a denominator. Moreover, the number of terms is

\begin{align*}r+s+1 &\leq C \sqrt{\log m} +1 \\[5pt] &\lt C\sqrt{c}k + 1 \\[5pt] &\leq \frac{k}{433} + 1 \\[5pt] &\lt k.\end{align*}

On the other hand, if m does occur as one of the denominators $u_i$ or $v_j$ , then let $t \in \{1, 2, 3\}$ be such that $m+t$ is divisible by 3 and define

\begin{align*}D \;:\!=\; \{3, 6, 9, 12, 15, 18, 24, 27, 30, 45, 54, 60, 72\}.\end{align*}

We note that all $d \in D$ are divisible by 3 and one can verify that $\sum_{d \in D} ({1}/{d}) = 1$ . We now consider

(2·2) \begin{equation} \frac{1}{u_1} + \cdots + \frac{1}{u_r} + \frac{1}{v_1} + \cdots + \frac{1}{v_s} + \frac{1}{m+t} + \sum_{i=0}^{t-1} \sum_{d \in D} \frac{1}{d(m+i)(m+i+1)}.\end{equation}

Since $\sum_{d \in D} \frac{1}{d} = 1$ , we first note that

\begin{align*}\frac{1}{m+t} + \sum_{i=0}^{t-1} \sum_{d \in D} \frac{1}{d(m+i)(m+i+1)}&= \frac{1}{m+t} + \sum_{i=0}^{t-1} \frac{1}{(m+i)(m+i+1)} \\ &= \frac{1}{m+t} + \sum_{i=0}^{t-1} \left(\frac{1}{m+i} - \frac{1}{m+i+1} \right) \\ &= \frac{1}{m},\end{align*}

as the sum telescopes. We therefore deduce that the total sum in (2·2) is equal to 1. As before, the number of terms in (2·2) satisfies

\begin{align*}r+s+1+t|D| &\leq r+s+40 \\ &\lt C\sqrt{c}k + 40 \\ &\leq \frac{k}{433} + 40 \\ &\leq k,\end{align*}

by our choice of c and the fact that $k\ge 433$ . Therefore, to complete the proof it suffices to show that all denominators in (2·2) are distinct.

To see this, observe that every denominator in (2·2) other than the $u_i$ and $v_j$ is a multiple of 3. On the other hand, recall that $N_K=4^{\alpha K^2}(p_1p_2\cdots p_K)^2$ with $p_i \ge 5$ for all i, so that $3\nmid N_K$ . Hence, none of these new denominators can divide $N_K$ , and in particular none of them can coincide with any $u_i$ . Therefore, it remains to check that the denominators $m+t$ and $d(m+i)(m+i+1)$ are all distinct from the $v_j$ (or equivalently, that none of them are equal to m times a divisor of $N_K$ ), and also distinct from one another.

Now, $m+t \in \{m+1,m+2,m+3 \}$ is not a multiple of m if $m \ge 4$ , while $m+t$ is smaller than all the other terms $d(m+i)(m+i+1)$ , so the denominator $m+t$ in (2·2) is certainly unique.

If $i=0$ , then $d(m+i)(m+i+1)=dm(m+1)$ cannot be equal to m times a divisor of $N_K$ , as $d(m+1)$ is divisible by 3, whereas $3\nmid N_K$ .

To see why $d(m+i)(m+i+1)$ is, for $1 \leq i \leq t-1$ , not a multiple of m and therefore not equal to any $v_j$ , note that

\begin{align*}\gcd\!(m, d(m+i)(m+i+1)) &\leq \gcd\!(m, d)\gcd\!(m, m+i)\gcd\!(m, m+i+1) \\ &= \gcd\!(m, d)\gcd\!(m, i)\gcd\!(m, i+1)\\ &\leq d(t-1)t\\ &\leq 432 \\ &\lt m.\end{align*}

We conclude that none of the $d(m+i)(m+i+1)$ are equal to a $v_j$ .

Finally, we need to check that

\[d(m+i)(m+i+1)\neq d'(m+j)(m+j+1)\]

for all $d,d'\in D$ and all integers $0\leq i,j \leq t-1$ , unless $d=d'$ and $i=j$ . Suppose, for a contradiction, that

(2·3) \begin{equation}d(m+i)(m+i+1)=d'(m+j)(m+j+1)\end{equation}

does hold for some $d,d'\in D$ and $0\leq i,j \leq t-1$ . By symmetry we may assume $d\ge d'$ . In fact, if $d=d'$ , then equation (2·3) simplifies to

\[(m+i)(m+i+1)=(m+j)(m+j+1).\]

As the function $x\mapsto (m+x)(m+x+1)$ is strictly increasing for $x\ge 0$ , this would imply $i=j$ . Hence, we will further assume the strict inequality $d \gt d'$ .

Inspecting the set D, one can verify that for any distinct $d\gt d'$ in D we actually have

(2·4) \begin{equation} \frac{d}{d'}\ge \frac{10}{9}.\end{equation}

Since $t\in\{1,2,3\}$ , we have $i,j\in\{0,1,2\}$ , hence

(2·5) \begin{equation} d(m+i)(m+i+1)\ge dm(m+1)\end{equation}

and

(2·6) \begin{equation} d'(m+j)(m+j+1)\leq d'(m+2)(m+3).\end{equation}

By combining (2·3), (2·4), (2·5) and (2·6), we then obtain

\[\frac{10}{9}m(m+1) \leq (m+2)(m+3),\]

contradicting $m \gt 432$ . This completes the proof.