Short Egyptian fractions

Proof. We use Takenouchi’s argument [20, Sections II–III, pp. 79–80]. For fixed x>0 and k, there are only finitely many nondecreasing lists of k denominators with reciprocal sum x. Indeed, the first denominator is at most k/x. Once it is chosen, induction applies to the remaining positive sum and the remaining k-1 terms; when no terms remain the sum must be zero.

If a denominator occurs twice, apply one of the identities

Because the total is less than 1, a denominator 1, or a repeated denominator 2, is impossible. Thus p\ge2 in the first identity and p\ge1 in the second. Each replacement preserves the number of terms and increases the sum of their denominators: the increases are (p-1)^2 and 2p^2, respectively. Finiteness of the set of lists therefore forces termination, at which point all denominators are distinct. Positivity and the unchanged total exclude a denominator 1 throughout.□

Proof. For a positive remainder A/C<1, set

Subtracting 1/z leaves A'/C'. The ceiling inequality gives 0\le A'<A, while integrality of A gives z\le C and hence C'\le C^2. Thus the numerator never exceeds a. Stop at zero or at the first positive remainder whose denominator is at least T. At such a first crossing, the preceding denominator was less than T, so the new one is less than T^2.

To bound the number of steps, write x=A/C. Since \lceil1/x\rceil\le 1+1/x,

The first positive remainder is less than 1/2, and subsequent remainders decrease at least by squaring. After j\ge1 positive steps their values therefore satisfy

If the procedure has not yet stopped, its positive integer numerator gives x_j\ge 1/C_j>1/T. This is impossible when 2^{j-1}\log2\ge\log T, proving the stated bound. Every current positive value is less than 1, so z\ge2.□

Proof of Theorem 1.1, assuming Proposition 2.1. For the upper bound, fix 1\le a<b, put S=\log b, and assume that S is sufficiently large. Apply Lemma 2.3 with T=e^{D_CS}. This uses O(\log S) terms. If the procedure terminates, Lemma 2.2 gives the required upper bound. Otherwise its remainder A/C satisfies

Choose M,G,X from Proposition 2.1 for this S,C. Since D_X=D_M+2,

Let g=\lfloor X/(AM)\rfloor and n=gAM. These are positive integers, and the inequality \lfloor t\rfloor\ge t/2 for t\ge1 gives

Write H=\{1,\ldots,\lfloor X\rfloor\}\setminus G. Among the n-1 positive splits n=u+(n-u), at most 2|H|\le X/4 have an entry outside G. Since n-1\ge X/2-1>X/4 for large S, some split has both entries in G. Their expansions together express

using at most 2L\log S unit fractions. Multiplying every denominator by the integer g gives an expansion of A/C of the same length. Adjoin the greedy prefix and apply Lemma 2.2 to the total a/b<1. The resulting distinct expansion has O(\log S) terms, uniformly in a. No reduction of a/b, or restriction on the final denominator sizes, has been used.

For the lower bound, consider an expansion of (b-1)/b with k terms and append 1/b. Sort the resulting s=k+1 denominators as d_1\le\cdots\le d_s; repetitions are harmless here. Put L_0=1 and L_j=d_1\cdots d_j. For each 1\le j\le s, the amount remaining after the first j-1 terms is positive and has denominator dividing L_{j-1}. Consequently

It follows that d_j\le sL_{j-1} and L_j\le sL_{j-1}^2. Induction gives L_j\le s^{2^j-1} and d_j\le s^{2^{j-1}}. As b is one of these denominators,

Hence \log\log b\le k\log2+\log\log(k+1)\le(1+\log2)k. The numerator b-1 therefore supplies the required lower bound for N(b).□

Proof. Write v=\log X, E=D+1, and

Every integer n=N+h under consideration satisfies 1\le n\le2e^{DS}\le e^{ES} for sufficiently large S. Moreover,

All estimates below are uniform in X,Y,N in the stated ranges.

Two elementary estimates. First, consider divisors of n formed from primes at least z\ge2. List these prime factors with multiplicity, giving distinct labels to repeated occurrences. There are at most L=\lfloor ES/\log z\rfloor occurrences, and a divisor at most X uses at most v/\log z of them. Counting subsets can only overcount divisors. With q=v/(ES)\in(0,1), their number is therefore at most

Here the middle inequality follows by inserting the weights q^j; the last uses Lq\le v/\log z.

Split the prime factors at S^{1/2}. For each smaller prime there are at most 1+ES/\log2 possible exponents in a divisor of n. Applying (3.3) to the remaining primes gives

Since v\ge S/(2\log S), there is a function \varepsilon_D(S)\to0, independent of X,Y,N,h, such that

Second, write \tau(d) for the number of positive divisors of d. For fixed r and 3/4\le\sigma\le1,

for every prime p. Indeed, the power series \sum_{j\ge1}(j+1)^r x^{j-1} is bounded on 0\le x\le2^{-3/4}<1. We will also use the elementary estimate

To prove it, set s=1+1/\log T and \zeta(s)=\sum_{a\ge1}a^{-s}. Euler’s absolutely convergent product and the integral bound \zeta(s)\le1+1/(s-1) give

In particular, multiplicativity and (3.5) imply

A prefix of the prime factorization. For n>\sqrt Y, order its prime factors with multiplicity and let d be the longest initial product at most \sqrt Y, allowing d=1. Let p be the next prime. Then

all prime factors of d are at most p, and all those of n/d are at least p. The inequality

does not require d and n/d to be coprime: a divisor a\le X of n determines

Then b\mid d, c\mid n/d, c\le X, and the pair (b,c) determines a. Thus (3.3) gives

For any fixed d\le\sqrt Y, the number of its multiples in (N,N+Y] is at most

We now sum according to the size of the next prime p. If p is large, the remaining factor n/d has few small divisors. If p is smaller, the condition dp>\sqrt Y forces d to be a large product of small primes. The total reciprocal weight of such prefixes is small, so (3.9) limits their occurrence in every shifted interval.

If \log p\ge v^{15/16}, the exponential factor in (3.8) is at most e^{rBv^{1/16}}. For n\le\sqrt Y, instead take d=n and use d_X(n)\le\tau(d). By (3.9) and (3.7), these two cases together contribute at most

For the remaining integers, \log p<v^{15/16}, so

once S is sufficiently large. This large prefix makes integers with small next prime rare. We estimate the ensuing smooth-prefix sums by Rankin’s exponential weighting method; see [13, p. 414, (1.3)].

If p<S^4, every prime factor of d is smaller than S^4. Multiplying each summand by (d/e^{v/5})^{1/10}>1 gives

The logarithm of this product is O(S^{2/5}), since

Counting multiples by (3.9) and bounding the entire summand by (3.4), we obtain a contribution at most

Here S^{2/5}=o(v), uniformly in the allowed range.

The intermediate primes. It remains to treat 4\log S\le\log p<v^{15/16}. Partition this range into intervals [t,2t), where t=2^j4\log S\le v^{15/16}. There are O_D(\log S) such intervals; the last may extend beyond the upper endpoint. For one interval put

Then Q\ge v^{1/16}, and

for sufficiently large S. Equations (3.8), (3.9), and (3.11) bound the contribution of this interval by

The last sum is at most

By (3.5) and (3.6), the logarithm of this product is bounded by

The contribution of the interval is consequently at most

Both positive terms in this exponent are uniformly negligible compared with Q\log Q. Indeed, (3.2) and Q\ge v^{1/16} give

Thus (3.13) is at most 2Y\exp(-Q\log Q/100)\le2Y, after increasing S_0(D,r). Summing the intervals costs O_D(Y\log S).

Combining this bound with (3.10) and (3.12) gives

The logarithmic loss is o(S^{1/4}), proving (3.1). Every enlargement of the threshold depended only on the fixed D,r; this completes the required uniformity check.□

Proof. Apply (4.8) to x_t=-Qt/u and J=[0,e^{-\eta w}). Conjugation leaves the Fourier bounds unchanged. The discrepancy is

It is therefore at most e^{-\eta w}/2 eventually. Finally, \{-Qt/u\}=(u\lceil Qt/u\rceil-Qt)/u, including when the residue is zero.□

Proof. We give the derivative argument, including the elementary estimates it uses. This is the classical differencing method of van der Corput; see [12, Lemma 2.5] for differencing and [12, Theorem 2.2] for the second-derivative estimate.

First, if |a_n|\le1 is supported on an interval of length at most U, then for 2\le L\le U,

To see this, express the sum as L^{-1}\sum_n\sum_{h=1}^L a_{n+h}, apply Cauchy–Schwarz in n, and expand the square. The outer support has length at most U+L+2, the diagonal contributes O(LU), and the off-diagonal terms give (4.9).

We also need the second derivative bound

on an interval J of length at most U, for g\in C^2(J). Here is an elementary proof. For \lambda above a fixed positive constant the trivial bound suffices. Otherwise put \beta=\sqrt\lambda<1/4. The derivative g' is monotone and traverses a range of length O_A(U\lambda). The portions where g' is within \beta of an integer have O_A(U\lambda+1) components and total length O_A(U\beta+\beta/\lambda), since |g''|\ge\lambda. Their integer points contribute the same bound after adding the number of components.

On each remaining interval g' is monotone and stays between q+\beta and q+1-\beta for some integer q. The corresponding sum is O(\beta^{-1}). Indeed the increments g(n+1)-g(n) are monotone in that same interval, and summation by parts in

gives this bound: the reciprocal denominator has supremum and total variation O(\beta^{-1}). Boundary terms add at most a constant per interval. Summing over the O_A(U\lambda+1) intervals proves (4.10).

Now let k be a nearest integer to \log|Z|/\log U, and set

There are only finitely many possible orders:

Apply (4.9) r times to a_n=\mathbf1_I(n)\e(f(n)), where f(x)=Z/x, extending the sequence by zero outside I. For positive shifts h_1,\ldots,h_r<L, the last phase is

Its support is the interval on which both x and x+h_1+\cdots+h_r belong to I. All intermediate points x+t_1+\cdots+t_r, 0\le t_i\le h_i, therefore remain in [U,2U]. Empty supports contribute zero.

The fundamental theorem of calculus gives

Since f^{(k)}(x)=(-1)^k k!Zx^{-k-1} has constant sign,

By (4.11) and the choice of L,

Thus (4.10) bounds each last correlation by O_k(U^{4/5}+U^{3/4}+1)=O_k(U^{4/5}).

For clarity, normalize every correlation by U, and let \sigma_j be their maximum after j shifts. Then

Induction, using L\ge U^{1/(10k)}/2 for large U, yields

Taking the largest implied constant over 4\le k\le Q_B and, for example, \delta_B=(10Q_B2^{Q_B})^{-1} proves the lemma. In particular, although k depends on Z,U, the final constants depend only on B.□

Proof. Write Y=X_{j+1}=\rho X; then Y>e^{S-\eta m}\ge e^{0.9S}. Expanding the square, the diagonal contributes at most 2^{-m} because the 2^m subset products are distinct. For an off-diagonal pair put Z=\ell C(t-t'). The difference t-t' is a nonzero integer, and (4.3) and (4.6) give

Split (Y,X] into intersections with dyadic intervals [U,2U]. We may take Y/2\le U\le X, so for large S,

Lemma 4.3, with the fixed value B=3D_C, bounds the sum over each piece by O(Ue^{-0.8\delta_BS}). The sum of the dyadic U’s is O(X). Thus

for an absolute c>0. Averaging over all off-diagonal pairs cancels their number against |T_0|^2. The left side of (4.12) is consequently at most

eventually, since S/m\to\infty.□

Proof. Expanding the square gives

For uniformly counted pairs I,J, their Hamming distance B has distribution \operatorname{Bin}(m,1/2). The exponential Markov inequality gives

We bound these pairs trivially. Fix any remaining pair, and set

Since V/(K\log S)\ge1000, and V\le S, we have

for sufficiently large S.

Select the first 2s differing coordinates in increasing order, and divide them into two sets of s coordinates each. This choice depends only on I,J, not on the sampled primes. Expose every labelled prime sample except the I-selected sample at these 2s coordinates. Then t_J is fixed and

where U_0 is fixed by the exposure and U_1,U_2 are independent products of s fresh uniform samples each. Equal prime values cause no difficulty: the I-selected and J-selected variables at a differing coordinate are distinct independent samples.

Write

The coefficient lU_0/u reduces to a fraction with denominator q. We will show that q is usually large enough for distinct integer values of each fresh product to remain distinct modulo q. Their small point probabilities will then give cancellation by additive-character orthogonality.

We first bound the probability, over the exposed variables, that q<u^{0.9}. Since l\le u^{0.005} and \gcd(lU_0,u)\le l\gcd(U_0,u), this event implies \gcd(U_0,u)>u^{0.095}. Call a sample contributing to U_0 a hit if its prime value divides u, and count hits with their sample multiplicities. If their number is B_0, then

Thus failure requires at least

hits. At most S primes in the sampling interval divide u, so each sample has hit probability at most S/P\le S^{-(K-2)}. There are at most m\le S independent samples in U_0. A union bound over sets of k_0 positions yields

If k_0>m-2s, the event is empty. This argument allows prime powers in u and repeated sampled primes.

Now fix an exposure with q\ge u^{0.9}. Every possible value of either fresh product is at most

By unique factorization, an integer can arise as the product of at most s! ordered s-tuples of primes. Consequently each atom in the distribution of U_i, for i=1,2, has probability at most

Reduction modulo q is injective on these integer values. The probability vectors \alpha,\beta of U_1,U_2 on \Z/q\Z therefore satisfy

The reduced fraction lU_0/u=c/q has \gcd(c,q)=1. Complete additive-character orthogonality gives

Indeed the inner sum over x vanishes unless q\mid c(y-y'), equivalently y=y' modulo q. This identity holds for composite q as well. Cauchy–Schwarz gives

The factor \e(-lt_J/u) is fixed under the exposure. Averaging this conditional estimate and using (4.15) bounds the contribution of our fixed pair I,J in absolute value by u^{-0.05}+u^{-0.2}.

Combining this with the Hamming exception, we obtain

The final inequality is uniform because \min(m,D_0\log S) tends to infinity with S.□

Proof of Lemma 4.1. The construction already gives the required size of M, its power of two, and divisibility of every list entry, for every realization of the samples. We prove the two residue properties.

Put H=\lfloor e^{4\eta m}\rfloor. At a level with X_j>e^S, Lemma 4.4 and Markov’s inequality show that the number of integers u\in(X_{j+1},X_j] for which

at some 1\le l\le H is at most

Conjugation changes the Fourier sign without changing the absolute value. Lemma 4.2, with scale m, therefore gives at least \rho|T_0|/2 entries with

outside that exceptional set. This holds separately at every such level and requires no probabilistic selection.

Next suppose j<d and X_j\le e^S. Then X_j>e^m, and every u\in(X_{j+1},X_j] satisfies

For sufficiently large S, these integers satisfy the lower bound in Lemma 4.5. Moreover 4\eta m\le0.005w, so that Lemma applies to all 1\le l\le H. In block 1, Markov’s inequality followed by the frequency union bound shows that

Let B_j count integers in this level that fail this Fourier bound. Linearity of expectation and another application of Markov give

As d=O(\log S), with probability 1-o(1) these bounds hold at every level under consideration. No independence between different integers or levels is needed. Here C_j=1, so Lemma 4.2 again gives the required \rho|T_1|/2 entries outside the exceptional sets.

Finally fix an integer S^{D_0}<u\le e^m. Now w=\log u, and Lemma 4.5, Markov’s inequality and the union over 1\le l\le\lfloor u^{4\eta}\rfloor give

in each block i. On success, Lemma 4.2, with scale \log u, supplies a list entry for which

The R=1000 blocks are independent for this fixed u. The probability that every block fails is therefore at most u^{-5}. A union bound over all terminal integers shows that

Thus every terminal integer has a suitable divisor, simultaneously, with probability tending to one.

The sum of this failure probability and the middle-level failure probability is o(1). Hence a realization satisfying both sets of requirements exists. Fix it and the resulting M. Since e^{-0.009m}\le e^{-0.001m}, the same c_*=0.001 is valid at every level. This proves both properties for one common M, for the fixed S and C.□

Proof of Proposition 2.1. Use the absolute constants and levels of Lemma 4.1. Before choosing S, fix

All subsequent lower bounds on S may depend on these fixed constants. In particular, the moment order r is independent of S. For sufficiently large S,

Fix an integer C in the range of Proposition 2.1, and choose the common integer M supplied by Lemma 4.1.

Every fraction u/(MC_j) with 1\le u\le X_j is less than one. Indeed, if C_j=C, then u\le X_0=e^{D_XS}<MC; if C_j=1, then u\le e^S<M. Moreover C_d=1, since X_d\le e^m<e^S. We first produce expansions at this last level, and then work backwards.

The last level. The power of two dividing M is at least S^{D_0}. For any integer 1\le u\le S^{D_0}, write u in binary. Every power 2^k that occurs divides M, and

This gives an expansion of u/M with at most 1+D_0\log S/\log 2 terms.

If S^{D_0}<u\le e^m, the last part of Lemma 4.1 gives a divisor t\mid M for which

The identity

adds one unit fraction. If h=0, the expansion ends; otherwise an expansion of h/M can be divided by the positive integer z. As long as the numerator remains above S^{D_0}, its logarithm decreases by a factor at most 1-\eta at each step. It starts at most m\le S, so after at most

steps it has either vanished or entered the binary range. Thus an absolute constant B_0 bounds the length of every terminal expansion by B_0\log S. All denominators are integers. Since every term is positive and the total is less than one, every denominator is at least two.

Working backwards. Set

At a level j<d, write the list prescribed by Lemma 4.1 as (t_{j,i})_{i\in I_j}: it is the deterministic list when X_j>e^S, and the first random list otherwise. Its entries may coincide; their indices are always retained. Having defined G_{j+1}, let

These sets have the asserted expansions. For membership inherited directly from G_{j+1}, divide the known expansion by the integer C_j/C_{j+1}. For membership obtained from a residue, put

Then

Both M/t_{j,i} and zC_j/C_{j+1} are positive integers. This includes the possible transition from C_j=C to C_{j+1}=1, where the second scaling factor is zC. If h=0, the second term is absent. Otherwise it uses the known expansion for h\in G_{j+1}. Consequently every member of G_j has an expansion of length at most

It remains to prove that almost all integers up to X_0 belong to G_0. We have built expansions whenever a residue reaches a previously treated numerator; the following count controls all other numerators.

Counting unsuccessful numerators. Define

Thus 0\le\delta_j\le1 and \delta_d=0. Fix j<d, and abbreviate X=X_j, Y=X_{j+1}=\rho X. The inclusion G_{j+1}\subseteq G_j gives

Apart from at most Xe^{-c_*m} exceptional integers, every u\in H_j\cap(Y,X] has at least \rho|I_j|/2 indices i with h_{j,t_{j,i}}(u)\le Y. Each such residue lies in H_{j+1}: a residue in G_{j+1}\cup\{0\} would place u in G_j.

For a fixed pair (h,i), every predecessor u satisfies

There are at most d_X(C_jt_{j,i}+h) such predecessors. Counting pairs with their list indices therefore yields

Repeated values of t_{j,i} create repeated summands on both sides of this count and require no adjustment. Figure 1 shows why the index must be retained in this double count.

We check the hypotheses of Lemma 3.1 before applying it. Since j<d, one has

Also

Finally, each shift N=C_jt_{j,i} is a positive integer and satisfies

Thus Lemma 3.1, with the fixed parameters D_*,r, applies uniformly at every level and to every list entry. Hölder’s inequality gives

This also holds when H_{j+1} is empty. Substitution in (5.6), followed by division by X, uses Y=\rho X to cancel the factor 1/\rho:

Since \delta_{j+1}\le\delta_{j+1}^{\alpha}, for sufficiently large S we obtain the uniform recurrence

Iterating the recurrence. Our fixed choice of r ensures

where we used -\log(1-1/r)\le2/r and (5.1). For nonnegative a,b, the inequality (a+b)^\alpha\le a^\alpha+b^\alpha permits us to unroll (5.8) from \delta_d=0:

Indeed, the exponent of A is at most r, and \alpha^i\ge\alpha^d\ge S^{-1/4}. The right-hand side tends to zero: the negative term has size at least c_*S^{3/4}/(2\log S), which dominates the fixed multiple 2rS^{1/4} and \log d.

For all sufficiently large S, we therefore have

Take G=G_0 and X=X_0. By (5.1) and (5.5), every u\in G has an expansion of u/(MC) with at most (B_0+K_d)\log S terms. The size bounds on M come from Lemma 4.1. Every estimate above is uniform in the allowed integer C, and all thresholds depend only on fixed absolute constants. Choosing L=B_0+K_d and then one sufficiently large absolute S_0 proves Proposition 2.1.□

Proof. Whenever a denominator m occurs twice, replace those two terms by

The sum stays equal to one and the length does not increase. There remains a denominator divisible by Q: if no such denominator is removed it persists, while if Q\mid m, the even replacement m/2 is a multiple of Q because Q is odd, and the larger odd replacement is a multiple of m.

This invariant excludes a denominator one, since that would force the singleton list (1). It also excludes a repeated denominator two, since two halves exhaust the sum and neither denominator is divisible by Q. Thus an odd repeated denominator is at least three. In an odd replacement the smaller new denominator is strictly below m and the larger is strictly above m. The sorted denominator tuple therefore strictly decreases lexicographically: all entries below (m+1)/2 are unchanged, and one extra copy of (m+1)/2 is inserted. At a fixed length such a descent in positive integer tuples terminates. Indeed, the first coordinate can decrease only finitely often, and after it stabilizes the same argument applies successively to the other coordinates. Even replacements strictly reduce length, so only finitely many occur. The procedure consequently terminates with distinct denominators and preserves the required multiple of Q.□

Proof of Corollary 1.2. A short initial expansion. Let r be a sufficiently large integer and let Q be the product of the first r odd primes. The prime number theorem, already used in Section 4, gives

Apply Theorem 1.1 to (Q-1)/Q and append 1/Q. Lemma 6.1 produces a distinct expansion of one whose denominator set S has size s=O(\log r) and contains a multiple n of Q. Fix this one set S and this one n. Writing \tau(n) for the number of positive divisors of n, we have \tau(n)\ge 2^r.

Branching over divisors. For every positive proper divisor d of n, the identity

gives two distinct integer denominators, with

For each unchanged denominator in S\setminus\{n\}, at most one choice of d makes it equal to n+d, and at most one makes it equal to n+n^2/d. Thus at least

choices give distinct-denominator expansions of one, all of the same length \ell=s+1. They give different expansions: from any resulting denominator set, remove the fixed set S\setminus\{n\}; the smaller of the two remaining denominators is n+d, which recovers d. Sorting each set therefore gives a different tuple counted by F(\ell).

Every sufficiently large length. For any distinct expansion of one with at least two terms, its largest denominator v exceeds one. Replace v by v+1 and v(v+1), using

These are the two largest denominators of the new expansion. The operation is injective: delete those two denominators and reinsert the second largest minus one. Iterating a fixed number of times is therefore injective. Our initial set contains a multiple of Q>1, so it is not the singleton \{1\}; the operation applies to all the expansions just constructed.

Choose an absolute constant B\ge1 such that \ell\le B\log r for all sufficiently large r. For each sufficiently large integer k, take r=\lfloor\exp(k/(2B))\rfloor. Then \ell\le k, and applying (6.2) exactly k-\ell times to each of our common-length expansions gives

Since r\ge\tfrac12\exp(k/(2B)) for large k, this proves \log\log F(k)\ge k/(2B)+O(1), hence the desired lower bound for every sufficiently large integer k.

The upper bound. Fix a tuple counted by F(k) and put P_0=1 and P_i=n_1\cdots n_i. Before the ith term, the positive remainder

is a rational number with a positive integer numerator over P_{i-1}. Ordering therefore gives

Inductively P_i\le k^{2^i-1} and n_i\le k^{2^{i-1}}. Counting all integer choices in this larger box shows that F(k) is finite and

Together with the lower bound, this yields \log\log F(k)\le k\log2+\log\log k=O(k) for sufficiently large k, as required.□

Proof. Start with (R_0,q_0)=(m-1,m) and x_0=R_0/q_0. Whenever R_i>0 and q_i<T, set

Do not cancel common factors in this pair. Thus x_{i+1}=R_{i+1}/q_{i+1}=x_i-1/n_{i+1}.

For an ordinary step, writing n=n_{i+1}=a gives

Moreover n<1/x_i+1, so

In the exceptional step a=m, we have (m-1)R_i<q_i\le mR_i. Consequently

where the last inequality uses m\ge4. Every step therefore leaves a remainder smaller than the term just subtracted. The next denominator, if there is one, is strictly larger. After the exceptional step all later denominators exceed m+1, so that step can occur at most once. Before it, R_i\le m-1; after it, the numerator is less than 2(m-1) and decreases at every subsequent step. Thus 0\le R_i<2m throughout. Since R_i\ge1 in an active step, a\le q_i and hence n_{i+1}\le q_i+1.

All selected denominators are at least 2, so q_i at least doubles at each step. The procedure thus stops after finitely many steps. Its first denominator is 2, and x_1=(m-2)/(2m)<1/2. All later steps square the upper bound for the remainder, apart from at most one step that still decreases it. Therefore, whenever i\ge2 and the remainder is positive,

If the final step has index j\ge3, its preceding state is active, and hence

This gives the asserted bound for j; it is immediate when j\le2. The same preceding state satisfies q_j\le q_{j-1}(q_{j-1}+1)<T^2, since T is an integer.

The displayed decomposition and product formula follow by telescoping. If R_j=0, the decomposition is complete. Otherwise the stopping rule gives q_j\ge T and R_j<2m, whence R_j/q_j<2m/T\le1/m. At each earlier step the new remainder was smaller than 1/n_i, and subsequent steps only decrease it. This proves all the claimed strict inequalities.□

Proof. This is the padding lemma of van Doorn and Tang [22, Lemma 2.1]; we include a proof. Every denominator is at least two, since a term with denominator one would already exhaust the sum. The identity

replaces one term by two with distinct denominators larger than b. If m\ne n_r, apply it to n_r; the new denominators exceed all the unchanged ones, and m remains.

Suppose that m=v=n_r, and let s=n_{r-1}. The same split of s works unless v=s+1 or v=s(s+1), since every other unchanged denominator is smaller than s. In either exceptional case, if s=ab with integers a,b\ge2, use instead

The inequalities

show that both new denominators avoid either exceptional value of v and all the unchanged denominators below s.

Finally, neither exceptional case can occur when s=p is prime. There are at least three original terms, so p>n_{r-2}\ge2 and in particular p is odd. All denominators other than p and v are below p; write the sum of their reciprocals as A/B with p\nmid B. The two exceptional choices give respectively

After clearing denominators and reducing modulo p, these equations give respectively 0\equiv B\pmod p and 0\equiv2B\pmod p, both impossible. Thus in every valid case an unmarked term can be replaced by two distinct terms, preserving m and increasing the length by exactly one.□

Proof. The prime number theorem [19, p. 305, (1.1)] gives

Since \ell(Y)=16\log m/\log 2+O(1), and \log(\lfloor L\rfloor!)=O(L\log L), this proves (8.1). Also P(Y)\geq2^{\ell(Y)}\geq Y^4, so K_m>m for large m.

We next prove an assertion whose threshold is independent of m. Fix a sufficiently large odd integer u, and let A be the set of positive divisors of P(u). Write N=|A|=2^{\ell(u)}\geq u^4. We estimate exceptional primes by counting congruent pairs, the mechanism underlying Gallagher’s larger sieve [10]. The coarse count below suffices. For each prime p\leq u, let A_p be the image of A in \mathbb F_p. Call p exceptional when |A_p|\leq p^{3/4}. If c_a is the number of members of A in residue class a, then Cauchy–Schwarz shows that the number of ordered pairs of distinct members of A congruent modulo an exceptional prime is at least

For any two distinct members a,b\in A, the nonzero integer |a-b|<P(u) has at most \log P(u)/\log 2 distinct prime divisors. Counting the same pairs prime by prime therefore bounds the number B(u) of exceptional primes by

We use the quantitative form of Vinogradov’s three-prime theorem: there is an absolute c>0 such that every sufficiently large odd integer u has at least cu^2/(\log u)^3 ordered representations as a sum of three primes; see the statement in [15, (1)–(2)] and the exposition in [16, Theorem 1 and Section 3.1]. To make the uniformity in odd u explicit, its singular series is

For odd u its factor at 2 is 2, and

The infinite product is positive because the sum of the subtracted quantities converges. Thus the asymptotic formula supplies an absolute lower bound with an absolute threshold, with no dependence on the factorization of u.

At most 3uB(u) ordered prime triples summing to u contain an exceptional prime: choose its position, its value, and one further entry; the last entry is then fixed. By (8.3),

Consequently every sufficiently large odd u is the sum of three primes that are not exceptional for this same set A.

It remains to represent each such prime using divisors of P(u)^2. Fix one of them, say p, and put H=A_p and h=|H|>p^{3/4}. Let U be the product of two independent uniformly chosen members of H, and write \mathrm e_p(z)=\exp(2\pi i z/p). The following classical bilinear estimate is recorded in [11, Proposition 1.1]; we give its short proof and the five-product consequence needed here. For every nonzero r\in\mathbb F_p, orthogonality and Cauchy–Schwarz give

After division by h^4, this says

For five independent copies U_1,\ldots,U_5, Fourier inversion now yields

Here the lower bound follows by bounding the absolute value of the sum of the nonzero Fourier coefficients.

Choose pairs of residues witnessing this positive probability and lift each residue to any positive member of A representing it. The five integer products e_1,\ldots,e_5 are positive divisors of P(u)^2, and their sum is divisible by p. Hence

The three chosen primes thus represent u in fifteen summands of the required kind.

For a sufficiently large integer s, use u=s if s is odd and u=s-1 otherwise. In the even case append the summand 1=1/1. This uses at most sixteen summands. If s\leq Y, monotonicity of \ell implies P(u)\mid P(Y), so every numerator constructed above divides K_m.

Finally, all preceding thresholds concern s alone and are absolute. Choose an integer S_0 above them. For all sufficiently large m we have \lfloor L\rfloor\geq S_0. Each remaining integer 1\leq s\leq S_0 then divides \lfloor L\rfloor! and hence K_m, so it has the one-summand representation s=s/1. This proves the assertion simultaneously for every 1\leq s\leq Y.□

Proof. For the initial value q=m, the divisor 1 works throughout [1,m]. Suppose the property holds for q, and put q'=nq. If 1\le w\le q, use a divisor of q, which is also a divisor of q'. If n\le w\le nq, apply the property at w/n and multiply the resulting divisor by n. These two cases cover [1,nq] unless q<n and q<w<n. In that gap the divisor q itself works: q<w and

This proves the induction, including the real points between consecutive integers.□

Proof. Write X_0=X, and repeatedly remove groups from the remaining integer. If the current integer X_i exceeds m^4, then w=X_i/m^2 lies in [1,q]. Choose d_i\mid q with

Thus m^2\le s_i\le m^3\le m^4, and the integer remaining after the group d_i s_i is removed satisfies

If instead 0<X_i\le m^4, remove the final group with d_i=1 and s_i=X_i. Stop immediately if the remaining integer is zero.

Every grouping step with X_i>m^4 decreases the remainder by a factor strictly greater than m^2. There are therefore at most \lceil\log X/(2\log m)\rceil such steps, followed by at most one final group. The number G of groups satisfies

This bound also covers X=1 and a zero remainder before the final group.

For each group, use the assumed representation s_i=\sum_{a=1}^{b_i}e_{i,a}/t_{i,a}, with b_i\le B. Dividing X=\sum_i d_i s_i by qK_m gives

Each displayed denominator is a positive integer. This uses the two divisibilities d_i\mid q and e_{i,a}\mid K_m; no divisibility between t_{i,a} and e_{i,a}, or coprimality assumption, is needed. The total number of terms is at most BG.□

Proof of Proposition 8.1. Fix a sufficiently large integer m, put L=\log\log m, and take K_m from Lemma 8.2. Apply Lemma 7.1 with T=2mK_m, which is an integer at least 2m^2. It gives

The prefix is distinct and avoids m. By (8.1),

If R=0, the expansion is complete and already satisfies the asserted length bound. Suppose henceforth that R>0.

The denominator q is retained without cancellation, beginning at m and using multipliers at most the preceding denominator plus one. Lemma 8.3 therefore applies to this q. Moreover q\ge2mK_m and R<2m, so the integer X=RK_m satisfies 1\le X<q. Lemma 8.4, with B=16 and the supply from Lemma 8.2, represents X/(qK_m)=R/q as a sum of at most 16G unit fractions, where

This count depends on RK_m, not on the potentially much larger q.

Apply Lemma 2.2 only to this tail. It makes its denominators distinct without changing its number of terms. The tail sum is strictly below 1/m and every 1/n_i by Lemma 7.1. Every reciprocal in any positive expansion of that sum is at most the sum itself. Thus all denominators of the distinct tail exceed m and every n_i, so adjoining it to the reserved term and prefix produces a distinct expansion of 1. There is one reserved term, j prefix terms, and at most sixteen terms for each of the G groups. Its total length is therefore at most

All errors here tend to zero as m tends to infinity through all integers: the bound on R removed any dependence on the chosen stopping numerator, and the supply covers both parities. Absorbing the error into any prescribed \varepsilon>0 proves the proposition.□

Proof of Corollary 1.3. Set A=257/\log2. Fix a real number c with 0<c<1/A, and choose \varepsilon>0 such that c(A+\varepsilon)<1. Proposition 8.1 supplies an integer M\ge4 such that every integer m\ge M has a distinct marked expansion with at most (A+\varepsilon)\log\log m terms. The construction in Section 7 also gives a finite distinct marked expansion for each 2\le m<M. Fix one for each such m, and let k_* be the maximum of their finitely many lengths.

For every integer k\ge k_* and every integer 2\le m\le\exp(\exp(ck)), the chosen expansion has at most k terms. This is immediate for m<M; for m\ge M its length is at most

A distinct expansion of 1 containing a denominator m\ge2 has at least three terms: denominator one would exhaust the sum, and two distinct denominators at least two contribute at most 1/2+1/3<1. Thus Lemma 7.2 may be iterated until the length is exactly k, retaining the exact integer m. We have proved

The first missing integer exceeds the real right endpoint, and hence v(k)\ge\exp(\exp(ck)) for every sufficiently large integer k. Because this holds for each fixed c<\log2/257, it gives

In particular 257/\log2<600, so taking c=1/600 gives the stated eventual lower bound v(k)\ge\exp(\exp(k/600)).

For the upper bound, the product recurrence in the proof of Corollary 1.2 gives n_i\le k^{2^{i-1}} in every distinct exact-k expansion of 1. Every denominator in such an expansion is therefore at most k^{2^{k-1}}. Consequently D_k is finite for every k\ge1, its complement in \{2,3,\ldots\} is nonempty, and

For k\ge2 this yields \log\log v(k)\le k\log2+\log\log k, and therefore

Together the two bounds imply \log\log v(k)=\Theta(k).□