TRANSACTIONS OF THE AMERICAN MATHEMATICAL SOCIETY Volume 353, Number 8, Pages 3209–3227 S 0002-9947(01)02782-9 Article electronically published on April 12, 2001

SUMS OF k UNIT FRACTIONS

CHRISTIAN ELSHOLTZ

Abstract. Erdős and Straus conjectured that for any positive integer n ≥ 2 the equation \frac{4}{n} = \frac{1}{x} + \frac{1}{y} + \frac{1}{z} has a solution in positive integers x, y, and z. Let m > k ≥ 3 and

E_{m,k}(N) = | \{n ≤ N | \frac{m}{n} = \frac{1}{t_{1}} + … + \frac{1}{t_{k}} has no solution with t_{i} ∈ ℕ\} | .

We show that parametric solutions can be used to find upper bounds on E_{m,k}(N) where the number of parameters increases exponentially with k. This enables us to prove

E_{m,k}(N) ≪ N exp (−c_{m,k}(log N)^{1− \frac{1}{2k−1−1}} ) with c_{m,k} > 0.

This improves upon earlier work by Viola (1973) and Shen (1986), and is an “exponential generalization” of the work of Vaughan (1970), who considered the case k = 3.

1. Introduction

In the theory of diophantine equations one often chooses the variables to be coprime. For many equations, for example x^{n}+y^{n} = z^{n}, this is no loss of generality. For other equations, however, this may be a considerable loss of generality. In fact, if the variables are chosen coprime in pairs then one makes use of k instead of conceivably 2^{k} − 1 independent parameters only.

The multiplicative structure amongst k integers can be expressed by means of 2^{k} − 1 parameters. One parameter corresponds to each of the 2^{k} − 1 nonempty subsets of the set of k integers.

If one deals with a diophantine equation in many variables which are highly composite and have many nontrivial common divisors, then one ought to start off from the most general starting point using all parameters.

In this paper we apply this idea to the diophantine equation

\frac{m}{n} = \frac{1}{t_{1}} + \frac{1}{t_{2}} + … + \frac{1}{t_{k}} . (1.1)

One of the outstanding problems in the theory of unit fractions is the famous Erdős-Straus conjecture on \frac{4}{n} = \frac{1}{x} + \frac{1}{y} + \frac{1}{z} and its generalizations.

Conjecture 1.1 (Erdős & Straus, 1948, [Erd50]). For all integers n ≥ 2, there exists a solution of the equation \frac{4}{n} = \frac{1}{x} + \frac{1}{y} + \frac{1}{z} in positive integers x, y and z.

\begin{matrix}c \\ ◯ \end{matrix}2001 American Mathematical Society

Received by the editors May 23, 2000 and, in revised form, August 28, 2000.

2000 Mathematics Subject Classification. Primary 11D68; Secondary 11D72, 11N36.

The research for this paper was supported by a Ph.D. grant from the German National Merit Foundation.

Conjecture 1.2 (Schinzel, [Sie56]). For all integers m ≥ 4 there exists N_{m} such that for all integers n ≥ N_{m} there exists a solution of \frac{m}{n} = \frac{1}{x} + \frac{1}{y} + \frac{1}{z} in positive integers x, y and z.

It is not even known whether there is any m such that \frac{m}{n} can be written as a sum of k = m − 1 unit fractions if n ≥ N_{m,k}. Note that, for m ≤ k there are, trivially, solutions of (1.1).

Partial answers to these conjectures concentrated on the exceptional set of denominators, for fixed m and k. Let E_{m,k}(N) denote the number of those integers n ≤ N for which (1.1) has no solution in positive integers t_{1}, t_{2}, …, t_{k}.

Upper bounds on E_{m,k}(N) can be obtained by means of sieve methods, since parametric solutions of equation (1.1) solve this equation for denominators n lying in certain residue classes. It can be expected to yield good upper bounds on E_{m,k}(N), if the parametric solution uses many independent parameters.

The question of finding upper bounds on E_{m,k}(N) has attracted considerable attention (see [Nak39], [Web70], [Vau70], [Vio73], [Li81], [Yan82], [She86], and [AB98]; the strongest of these results are those of Vaughan and Shen). Previous work started off from parametric solutions where the number of parameters grows linearly with k. In this paper we shall show that the number of parameters that can be used in the sieve process may increase exponentially with k. We prove the following theorem:

Theorem 1.3. For any fixed k ≥ 3 and m > k the following upper bound holds, with a positive constant c_{m,k},

E_{m,k}(N) ≪ \frac{N}{exp (c_{m,k}(log N)^{1− \frac{1}{2^{k−1}−1}} )}.

This improves upon the work of Viola (see [Vio73]) and Shen (see [She86]) who proved an upper bound with the exponent 1 − \frac{1}{k−1} and 1 − \frac{1}{k}, respectively, instead of our new exponent 1 − \frac{1}{2^{k−1}−1}. For k = 3, this result had been found before by Vaughan, (see [Vau70]). Proofs of Vaughan’s result can also be found in the books by Narkiewicz (see [Nar86]) and Schwarz (see [Sch74]). Our work can be understood as an “exponential generalization” of the work of Vaughan. We use 2^{k−1} parameters, while Vaughan used 4 parameters for k = 3.

Whereas this work concentrates on sums of a fixed number of unit fractions there has recently been considerable progress on questions involving an unlimited number of unit fractions. For this I would like to refer the reader to the work of E. Croot (see [Cro00]) and G. Martin (see [Mar99] and [Mar00]). A. Schinzel wrote a recent survey on various aspects of unit fractions, (see [Scha] and [Sch00]).

I would like to express my gratitude to all of those who have contributed to the research on this work. I am greatly indebted to D.R. Heath-Brown (Oxford), who introduced me to the subject of the Erdős-Straus conjecture and the relevant methods of elementary and analytic number theory. I would also like to express my gratitude to W. Schwarz (Frankfurt), D. Laugwitz (Darmstadt), J. Brüdern (Stuttgart), A. Schinzel (Warsaw), C. List (Oxford), S. Daniel (Cardiff), an anonymous referee, and many others, for useful suggestions.

This paper is part of the author’s Ph.D. thesis. An unabbreviated version can be obtained from the author upon request.

SUMS OF k UNIT FRACTIONS 3211

2. Notation

It turned out to be suitable to denote the parameters by their rôle. That is to say, a parameter that occurs in the i_{1}-th, i_{2}-th, …, i_{r}-th fraction but not in the other fractions will be denoted as x_{i_{1}i_{2}...i_{r}}.

It is convenient to have a common name for certain products of parameters. The product of all parameters occurring in the i-th fraction is denoted by [i]. The product of all parameters that occur in the i_{1}-th, i_{2}-th, …, i_{r}-th fraction will be called

[i_{1} ⊕ i_{2} ⊕ … ⊕ i_{r}].

Similarly, the product of all parameters that occur in the i_{1}-th, i_{2}-th, …, i_{r}-th fraction, but not in the j_{1}-th, j_{2}-th, …, j_{s}-th fraction will be denoted by

[i_{1} ⊕ i_{2} ⊕ … ⊕ i_{r} ⊖ j_{1} ⊖ j_{2} ⊖ … ⊖ j_{s}].

The product [1 ⊕ 2], for example, has different meanings for different k:

\begin{matrix}k = 2 : & [1 ⊕ 2] = x_{12}, \\ k = 3 : & [1 ⊕ 2] = x_{12}x_{123}, \\ k = 4 : & [1 ⊕ 2] = x_{12}x_{123}x_{124}x_{1234}, \\ k = 5 : & [1 ⊕ 2] = x_{12}x_{123}x_{124}x_{125}x_{1234}x_{1235}x_{1245}x_{12345}, \end{matrix}

etc. While the length of the right hand side grows exponentially with k, the length of the left hand side is as compact for large k as it is for small k.

To denote individual parameters, it is more convenient to refer to them by their name x_{i_{1}i_{2}...i_{r}}. Nevertheless, it is important to keep in mind that any individual parameter x_{i_{1}i_{2}...i_{r}} can also be expressed as

x_{i_{1}i_{2}...i_{r}} = [i_{1} ⊕ i_{2} ⊕ … ⊕ i_{r} ⊖ i_{r+1} ⊖ i_{r+2} ⊖ … ⊖ i_{k}],

where the i_{1}, …, i_{r}, i_{r+1}, i_{r+2}, …, i_{k} are a permutation of {1, 2, …, k}.

We often need to specify those parameters that occur in the second fraction. For this purpose, we make the following convention: If x_{I} is a parameter such that I is a subset of {1, 2, …, k}, with 2 ∈ I and |I| ≥ 2, then we say that I is an admissible index set or that x_{I} is an admissible parameter. We introduce the abbreviation K := 2^{k−1}.

We also need a particular enumeration of the parameters x_{I}. We denote the i-th parameter by y_{i}. Any such parameter y_{i} (for i = 1, …, K − 1) is identical to some x_{I} for some admissible index set I. With each parameter y_{i} we associate a suitable constant ϑ_{i}, to be defined later.

3. Survey of the Proof

The structure of the proofs of Vaughan, Viola, Shen, and myself is the same. I will give a short survey of this proof, particularly in the case k = 4, and compare the new approach with previous work.

Step 1: Starting point. We explain the previous work in our new notation which makes it easier to compare the various results. For k = 3, Vaughan used the following starting point:

\frac{m}{n} = \frac{1}{x_{12}x_{13}x_{123}} + \frac{1}{nx_{12}x_{23}x_{123}} + \frac{1}{nx_{13}x_{23}x_{123}} .

For k = 4, we use the following starting point.

\begin{aligned}\frac{m}{n} = & \frac{1}{x_{12}x_{123}x_{124}x_{134}x_{1234}} + \frac{1}{nx_{12}x_{23}x_{24}x_{123}x_{124}x_{234}x_{1234}} \\ & + \frac{1}{nx_{23}x_{123}x_{134}x_{234}x_{1234}} + \frac{1}{nx_{24}x_{124}x_{134}x_{234}x_{1234}} . \end{aligned} (3.1)

More generally, we use all 2^{k−1} −1 parameters occurring in the second fraction, and x_{134...k}, i.e. the only parameter not occurring in the second fraction. Note that this is a slight simplification of the most general starting point which would allow for 2^{k} − 1 instead of 2^{k−1} parameters. The idea that in principle 2^{k} − 1 parameters can be used to decompose integers can be traced back to the work of Dedekind (see his paper of 1897, [Ded31]), and Sós (see [Sos05] and [Sos06]). For prime denominator n = p the number of parameters that could be used in principle is 2^{k} − k − 1, since here there are restrictions on k of the parameters, (for details see [Els98]). It is thus conceivable to prove a slightly better sieve bound, using the methods of this paper.

Viola made use of k, and Shen made use of k + 1 parameters. Shen used one parameter that occurs in all fractions and k parameters that occur in all but one fraction. For k = 4, their approach starts with

Viola: \frac{m}{n} = \frac{1}{x_{123}x_{124}x_{134}x_{1234}} + \frac{1}{nx_{123}x_{124}x_{1234}}

+ \frac{1}{nx_{123}x_{134}x_{1234}} + \frac{1}{nx_{124}x_{134}x_{1234}} .

Shen: \frac{m}{n} = \frac{1}{x_{123}x_{124}x_{134}x_{1234}} + \frac{1}{nx_{123}x_{124}x_{234}x_{1234}}

+ \frac{1}{nx_{123}x_{134}x_{234}x_{1234}} + \frac{1}{nx_{124}x_{134}x_{234}x_{1234}} .

From our starting point (3.1) we proceed to solve certain residue classes:

with x_{134} + x_{12}x_{24}x_{124} + x_{12}x_{23}x_{123} = rx_{23}x_{24}x_{234} (say)

we find that

\begin{aligned}n & = (mx_{12}x_{23}x_{24}x_{123}x_{124}x_{234}x_{1234} − 1) r \\ & − mx_{12}x_{123}x_{124}x_{1234} (x_{12}x_{23}x_{123} + x_{12}x_{24}x_{124}) \end{aligned}

is soluble. We see that we can solve the equation for certain residue classes. This means for all n in certain residue classes one can find a solution.

Step 2: Uniqueness of the residue classes. In order to apply an upper bound sieve we have to count the number of residue classes which can be treated as above. We must ensure that each sifted class is counted at most once. We shall show that suitable conditions on the size of the parameters and a square-free condition entails that two distinct factorizations of x_{12}x_{23}x_{24}x_{123}x_{124}x_{234}x_{1234} lead to distinct residue classes such that each counted class is counted at most once.

Step 3: Counting the number of eliminable residue classes. It turns out that the number ω(q) of residue classes to be counted can be written as ω(q) ≈ d_{2^{k−1}−1} (\frac{q+1}{m}), where d_{2^{k−1}−1} is the divisor function counting the number of ways in which a number can be written as a product of 2^{k−1} − 1 factors. We shall prove that

(log x)^{2^{k−1}−2} ≪ ∑_{\begin{matrix}q≤x \\ q prime \end{matrix}} \frac{ω(q)}{q}.

Step 4: The large sieve argument. A general large sieve device due to Vaughan immediately implies the theorem.

4. The Starting Point

Our starting point is as follows:

\frac{m}{p} = \frac{1}{[1 ⊕ 2]x_{134...k}} + \frac{1}{p[2]} + \frac{1}{p[2 ⊕ 3]x_{134...k}} + … + \frac{1}{p[2 ⊕ k]x_{134...k}} .

This implies that

m[2]x_{134...k} = p[2 ⊖ 1] + x_{134...k} + [2 ⊖ 3] + … + [2 ⊖ k].

The left hand side is divisible by [2 ⊖ 1] hence the right hand side must also be divisible by [2 ⊖ 1]. So, for some positive integer r:

[2 ⊖ 1]r = x_{134...k} + [2 ⊖ 3] + … + [2 ⊖ k].

We then divide by [2 ⊖ 1] and get

m[2 ⊕ 1]x_{134...k} = p + r.

We re-substitute x_{134...k} = [2 ⊖ 1]r − [2 ⊖ 3] − … − [2 ⊖ k], and obtain

m[2 ⊕ 1] ([2 ⊖ 1]r − [2 ⊖ 3] − … − [2 ⊖ k]) = p + r.

Hence,

p = (m[2 ⊕ 1][2 ⊖ 1] − 1) r − m[2 ⊕ 1] ([2 ⊖ 3] + … + [2 ⊖ k])
= (m[2] − 1) r − m[1 ⊕ 2] ([2 ⊖ 3] + … + [2 ⊖ k]) .

In particular, we can solve the equation (1.1) for all integers n in the residue class

−m[1 ⊕ 2] ([2 ⊖ 3] + … + [2 ⊖ k]) mod q = m[2] − 1.

5. Uniqueness of the Residue Classes

5.1. Introduction. In this section we shall show how to ensure that each eliminable residue class is counted not more than once. For this purpose we introduce certain restrictions on the parameters. On the one hand, these restrictions are sufficiently strong to ensure that each class we count is counted once. On the other hand, they are sufficiently weak to ensure that the number of counted classes is on average of the same order as the number of those classes for which the equation is generally soluble.

Following the ideas of Vaughan, Viola, and Shen, it seemed to be suitable to restrict the size of the parameters, to take some of the parameters to be squarefree, and to omit small primes q. Using combinatorial ideas that go beyond the work of Vaughan, Viola, and Shen, it turns out that these restrictions suffice to ensure the uniqueness of the residue classes:

Theorem 5.1 (Uniqueness of the residue class). Let q be prime with q > q_{m,k}. We use the enumeration of the parameters as specified in section 5.2.1 below. Let the size of the parameters be restricted as follows: For the i-th parameter y_{i}, we have [2]^{ϑ_{i}} ≤ y_{i}, where ϑ_{i} = \frac{3}{4^{i}} . Let \frac{[2]}{x_{12}x_{234...k}} be square-free. Suppose that we have two factorizations of \frac{q+1}{m} with the above restrictions on the parameters.

\frac{q + 1}{m} = [2] = x_{12}x_{123} ⋯ = x̃_{12}x̃_{123} ⋯ = ˜[2].

Suppose that the corresponding eliminable classes of these two factorizations are congruent modulo q

[1 ⊕ 2]([2 ⊖ 3] + … + [2 ⊖ k]) ≡ ˜ [1 ⊕ 2]( ˜ [2 ⊖ 3] + … + ˜ [2 ⊖ k]) mod q.

Then, for any pair (x_{I}, x̃_{I}) of corresponding parameters with an admissible index set I, pairwise identity holds:

x_{I} = x̃_{I}.

This means that the factorization of \frac{q+1}{m} with the above restrictions is unique.

The proof of this result requires several steps and lemmas.

Part 1. Firstly, we give the details of the suitable order of the parameters and the restriction on the size of the parameters.

Part 2. Suppose that we have two factorisations of \frac{q+1}{m} = [2] = ˜[2].

Suppose that the eliminable classes

[1 ⊕ 2]([2 ⊖ 3] + … + [2 ⊖ k]) and ˜ [1 ⊕ 2]( ˜ [2 ⊖ 3] + … + ˜ [2 ⊖ k])

that correspond to the factorizations [2] = ˜[2] are congruent modulo q, where q is prime. We will show that suitable restrictions on the size of the parameters ensure that [1 ⊕ 2]([2 ⊖ 3] + … + [2 ⊖ k]) = ˜ [1 ⊕ 2]( ˜ [2 ⊖ 3] + … + ˜ [2 ⊖ k]).

Part 3. Using the size of the parameters and omitting small primes, we shall subsequently show that [1 ⊕ 2][2 ⊖ r] = ˜ [1 ⊕ 2] ˜ [2 ⊖ r] for r = k, k − 1, ⋯, 3.

Part 4. Given the identity of a pair of ‘long’ products of corresponding parameters (see part 3) our next step is to deduce the identity of suitable pairs of ‘shorter subproducts’, and finally for all pairs of admissible parameters x_{I} = x̃_{I}.

5.2. The details. Since some of the details are somewhat involved we invite the reader first to work through the proof in the case k = 4. We give some details for this case in section 5.3. Parts 1-3 closely follow the arguments of Viola. In part 4 however, we need to split long products into short ones, a problem that did not occur in Viola’s or Shen’s presentation.

5.2.1. Part 1. We enumerate the K − 1 admissible parameters as follows: The first k − 1 parameters are

y_{1} = x_{12}, y_{2} = x_{123}, y_{3} = x_{1234}, …, y_{k−1} = x_{123...k}.

Then we continue with y_{k} = x_{124}, …, y_{2k−4} = x_{12k} and y_{2k−3} = x_{1235}, y_{2k−2} = x_{1236}, …, y_{(k^{2}−k−4)/2} = x_{12(k−1)k} etc. up to

y_{2^{k−2}−k+4} = x_{1234...(k−2)k}, …, y_{2^{k−2}} = x_{124...(k−1)k}.

Similarly, y_{2^{k−2}+1} = x_{23}, …, y_{2^{k−2}+k−2} = x_{2k}, then x_{234}, x_{235}, …, x_{2(k−1)k} etc. up to x_{234...(k−2)(k−1)}, …, x_{24...(k−1)k}, and finally y_{K−1} = x_{234...(k−2)(k−1)k}.

Put ϑ_{i} = \frac{3}{4^{i}}. In particular, we find that

[1 ⊕ 2] ≥ x_{12}x_{123} ⋯ x_{123...k} ≥ [2]^{1− \frac{1}{4^{k−1}}} ,
[2 ⊕ k] ≥ x_{123...k} = [2]^{\frac{3}{4^{k−1}}} ,
For r ≥ 3: [2 ⊖ r] ≥ x_{12}x_{123} ⋯ x_{123...(r−1)} ≥ [2]^{1− \frac{1}{4^{r−2}}} ,
[2 ⊕ (r − 1)] ≥ x_{123...(r−1)} ≥ [2]^{\frac{3}{4^{r−2}}} .

We also put an upper bound on the parameters

[2]^{ϑ_{i}} ≤ y_{i} ≤ [2]^{ϑ_{i}+η} (i = 2, …, K − 1) with η = \frac{1}{K4^{K−1}} .

Note that ∑_{i=2}^{K−1} (ϑ_{i} + η) < \frac{1}{4}. It is important that we do not impose such an upper bound on the parameter y_{1} = x_{12}. We observe that

[2 ⊖ 3] ≤ [2 ⊖ 4] ≤ … ≤ [2 ⊖ k].

5.2.2. Part 2.

Lemma 5.2 (Compare [Vio73]). Suppose that we have two factorizations of \frac{q+1}{m},

\frac{q + 1}{m} = [2] = ˜[2],

with the above restrictions on the parameters. Suppose that

[1 ⊕ 2]([2 ⊖ 3] + … + [2 ⊖ k]) ≡ ˜ [1 ⊕ 2]( ˜ [2 ⊖ 3] + … + ˜ [2 ⊖ k]) mod q. (5.1)

We then have

[1 ⊕ 2]([2 ⊖ 3] + … + [2 ⊖ k]) = ˜ [1 ⊕ 2]( ˜ [2 ⊖ 3] + … + ˜ [2 ⊖ k]). (5.2)

Proof. Note that ([2], q)=1.

[1 ⊕ 2]([2 ⊖ 3] + … + [2 ⊖ k]) ≡ ˜ [1 ⊕ 2]( ˜ [2 ⊖ 3] + … + ˜ [2 ⊖ k]) mod q,
\frac{[2]}{[2 ⊖ 1]}([2 ⊖ 3] + … + [2 ⊖ k]) ≡ \frac{[2]}{˜ [2 ⊖ 1]}( ˜ [2 ⊖ 3] + … + ˜ [2 ⊖ k]) mod q,
˜ [2 ⊖ 1]([2 ⊖ 3] + … + [2 ⊖ k]) ≡ [2 ⊖ 1]( ˜ [2 ⊖ 3] + … + ˜ [2 ⊖ k]) mod q.

Therefore

0 ≤ ˜ [2 ⊖ 1]([2 ⊖ 3] + … + [2 ⊖ k]) ≤ (k − 2) ˜ [2 ⊖ 1][2 ⊖ k]
≤ (k − 2)\frac{[2]  [2]}{˜ [1 ⊕ 2][2 ⊕ k]}
≤ (k − 2)[2]^{1− \frac{2}{4^{k−1}}} < m[2] − 1 = q.

Analogously

0 ≤ [2 ⊖ 1]( ˜ [2 ⊖ 3] + … + ˜ [2 ⊖ k]) < q.

Therefore (5.1) implies that

˜ [2 ⊖ 1]([2 ⊖ 3] + … + [2 ⊖ k]) = [2 ⊖ 1]( ˜ [2 ⊖ 3] + … + ˜ [2 ⊖ k]).

Hence the asserted identity (5.2) must also hold.

5.2.3. Part 3.

Lemma 5.3 (Compare [Vio73]). Suppose, as in the previous lemma, that we have two factorizations of \frac{q+1}{m} = [2] = [˜2] with the restrictions on the parameters mentioned above. Let us further suppose that q > q_{m,k} and that

[1 ⊕ 2]([2 ⊖ 3] + … + [2 ⊖ k]) = ˜ [1 ⊕ 2]( ˜ [2 ⊖ 3] + … + ˜ [2 ⊖ k]).

Then

[1 ⊕ 2][2 ⊖ r] = ˜ [1 ⊕ 2] ˜ [2 ⊖ r] for r = 3, ⋯, k.

Proof. We first prove [1 ⊕ 2][2 ⊖ r] = ˜ [1 ⊕ 2] ˜ [2 ⊖ r] for r = k and then, successively, for r = k − 1, k − 2, …, 3. For r = k we have that

\begin{aligned}& |[1 ⊕ 2][2 ⊖ r] − ˜ [1 ⊕ 2] ˜ [2 ⊖ r]| \\ = & | ˜ [1 ⊕ 2]( ˜ [2 ⊖ 3] + … + ˜ [2 ⊖ r − 1]) − [1 ⊕ 2]([2 ⊖ 3] + … + [2 ⊖ r − 1])| . \end{aligned}

Suppose, for a contradiction, that [1 ⊕ 2][2 ⊖ r] ≠ ˜ [1 ⊕ 2] ˜ [2 ⊖ r]. The idea is to deduce contradicting upper and lower bounds for

| ˜ [2 ⊖ 1][2 ⊖ r] − [2 ⊖ 1] ˜ [2 ⊖ r]|.

The upper bound:

| ˜ [2 ⊖ 1][2 ⊖ r] − [2 ⊖ 1] ˜ [2 ⊖ r]|
= \frac{[2 ⊖ 1] ˜ [2 ⊖ 1]}{[2]}|[1 ⊕ 2][2 ⊖ r] − ˜ [1 ⊕ 2] ˜ [2 ⊖ r]|
= \frac{[2 ⊖ 1] ˜ [2 ⊖ 1]}{[2]}| ˜ [1 ⊕ 2]( ˜ [2 ⊖ 3] + … + ˜ [2 ⊖ (r − 1)])

−[1 ⊕ 2]([2 ⊖ 3] + … + [2 ⊖ (r − 1)])|

= \frac{[2 ⊖ 1] ˜ [2 ⊖ 1]}{[2]}|\frac{[2]}{˜ [2 ⊖ 1]}( ˜ [2 ⊖ 3] + … + ˜ [2 ⊖ (r − 1)])

−\frac{[2]}{[2 ⊖ 1]}([2 ⊖ 3] + … + [2 ⊖ (r − 1)])|

= |[2 ⊖ 1]( ˜ [2 ⊖ 3] + … + ˜ [2 ⊖ (r − 1)])
− ˜ [2 ⊖ 1]([2 ⊖ 3] + … + [2 ⊖ (r − 1)])|
< max((r − 3)[2 ⊖ 1]  ˜ [2 ⊖ (r − 1)], (r − 3) ˜ [2 ⊖ 1][2 ⊖ (r − 1)])
≤ (r − 3) max(\frac{[2]^{2}}{[1 ⊕ 2]  ˜ [2 ⊕ (r − 1)]}, \frac{[2]^{2}}{˜ [1 ⊕ 2][2 ⊕ (r − 1)]})
≤ (r − 3)[2]^{2−(1− \frac{1}{4^{k−1}} )− \frac{3}{4^{r−2}}} .

The lower bound:

| ˜ [2 ⊖ 1] ˜ [2 ⊕ r] − [2 ⊖ 1][2 ⊕ r]| is an integer ≥ 0. By our assumption,

[1 ⊕ 2][2 ⊖ r]  ≠ ˜ [1 ⊕ 2] ˜ [2 ⊖ r]
⇔  \frac{[2]}{[2 ⊖ 1]} \frac{[2]}{[2 ⊕ r]}  ≠ \frac{[2]}{˜ [2 ⊖ 1]} \frac{[2]}{˜ [2 ⊕ r]}
⇒  | ˜ [2 ⊖ 1] ˜ [2 ⊕ r] − [2 ⊖ 1][2 ⊕ r]| ≠ 0
Hence | ˜ [2 ⊖ 1] ˜ [2 ⊕ r] − [2 ⊖ 1][2 ⊕ r]| ≥ 1.

| ˜ [2 ⊖ 1][2 ⊖ r] − [2 ⊖ 1] ˜ [2 ⊖ r]| = \frac{[2]}{[2 ⊕ r] ˜ [2 ⊕ r]}| ˜ [2 ⊖ 1] ˜ [2 ⊕ r] − [2 ⊖ 1][2 ⊕ r]|
≥ \frac{[2]}{[2 ⊕ r] ˜ [2 ⊕ r]} = \frac{[2 ⊖ r] ˜ [2 ⊖ r]}{[2]}
≥ [2]^{2(1− \frac{1}{4^{r−2}} )−1}.

Combining the lower and upper bound, yields

[2]^{2(1− \frac{1}{4^{r−2}} )−1} ≤ (r − 3)[2]^{2−(1− \frac{1}{4^{k−1}} )− \frac{3}{4^{r−2}}}

which leads to [2]^{\frac{3}{4^{r−1}}} ≤ (r − 3).

Hence we find for sufficiently large q a contradiction for r = k and can inductively assume that the lemma has been proven for k, ⋯, r+1. The same argument proves the lemma for any r ≥ 3.

5.2.4. Part 4. It will be our aim now to split ‘long’ products like [1 ⊕ 2][2 ⊖ r] into ‘short’ ones such that we finally get the identity of the single parameters x_{I} = x̃_{I}. In this part we also make use of a restriction on the multiplicative structure of [2].

We assume that \frac{[2]}{x_{12}x_{234···k}} is square-free. In particular, we do not assume that x_{12} is square-free.

We know that

\begin{aligned}[1 ⊕ 2][2 ⊖ 3] & = & ˜ [1 ⊕ 2] ˜ [2 ⊖ 3] \\ [1 ⊕ 2][2 ⊖ 4] & = & ˜ [1 ⊕ 2] ˜ [2 ⊖ 4] \\ ⋮ & ⋮ & ⋮ \\ [1 ⊕ 2][2 ⊖ k] & = & ˜ [1 ⊕ 2] ˜ [2 ⊖ k]. \end{aligned}

Multiplying these equations leads to

[1 ⊕ 2]^{k−2}[2 ⊖ 3][2 ⊖ 4] … [2 ⊖ k] = ˜ [1 ⊕ 2]^{k−2} ˜ [2 ⊖ 3] ˜ [2 ⊖ 4] … ˜ [2 ⊖ k].

Writing this equation in terms of the single parameters, in decreasing order of their exponents, leads to

(x_{12})^{2k−4}(x_{123}x_{124} … x_{12k})^{2k−5}(x_{1234}x_{1235} … x_{12(k−1)k})^{2k−6} … (x_{123...k})^{k−2}

× (x_{23}x_{24} … x_{2k})^{k−3}(x_{234}x_{235} … x_{2(k−1)k})^{k−4} … (x_{234...k})^{0}

=(x̃_{12})^{2k−4}(x̃_{123}x̃_{124} … x̃_{12k})^{2k−5}(x̃_{1234}x̃_{1235} … x̃_{12(k−1)k})^{2k−6} … (x̃_{123...k})^{k−2}

× (x̃_{23}x̃_{24} … x̃_{2k})^{k−3}(x̃_{234}x̃_{235} … x̃_{2(k−1)k})^{k−4} … (x̃_{234...k})^{0}.

Any divisor of the left hand side taken to the r-th (say) power must also be taken to the r-th power on the right hand side. By the uniqueness of the prime factorization and since \frac{[2]}{x_{12}x_{234...k}} and \frac{[2]}{x̃_{12}x̃_{234...k}} are square-free, we can see that

\begin{aligned}x_{12} & = & x̃_{12} \\ x_{123}x_{124} … x_{12k} & = & x̃_{123}x̃_{124} … x̃_{12k} \\ x_{1234}x_{1235} … x_{12(k−1)k} & = & x̃_{1234}x̃_{1235} … x̃_{12(k−1)k} \\ ⋮ & ⋮ & ⋮ \\ x_{123...k} & = & x̃_{123...k} \end{aligned}

and

\begin{aligned}x_{23}x_{24} … x_{2k} & = & x̃_{23}x̃_{24} … x̃_{2k} \\ x_{234}x_{235} … x_{2(k−1)k} & = & x̃_{234}x̃_{235} … x̃_{2(k−1)k} \\ ⋮ & ⋮ & ⋮ \\ x_{234...k} & = & x̃_{234...k}. \end{aligned}

One can first prove the first line. For the following lines we can use the principle: Suppose that pr_{1}^{a}pr_{2}^{b} = p̃r_{1}^{a}p̃r_{2}^{b}, where the pr_{i} stand for any product of parameters and where a ≠ b. Then gcd(pr_{1}, pr_{2}) = 1 and gcd(p̃r_{1}, p̃r_{2}) = 1 implies that pr_{1} = p̃r_{1} and pr_{2} = p̃r_{2}. The very last of these equations, x_{234...k} = x̃_{234...k}, requires a further explanation. Let I run through the admissible index sets. We know that [2] = ∏_{I} x_{I} = ∏_{I} x̃_{I} = ˜[2]. Hence the identity x_{234...k} = x̃_{234...k} follows, since these are the only parameters that do not occur in any of the above equations.

Note that

\begin{aligned}x_{12}(x_{123}x_{124} … x_{12k}) … x_{123...k} & = x̃_{12}(x̃_{123}x̃_{124} … x̃_{12k}) … x̃_{123...k}, \\ i.e. [1 ⊕ 2] & = ˜ [1 ⊕ 2]. \end{aligned} (5.3)

This implies

[2 ⊖ a] = ˜ [2 ⊖ a], (a = 3, …, k).

We now aim to prove that x_{I} = x̃_{I}, for any pair x_{I} and x̃_{I} of corresponding parameters with admissible index set I. Let J = {i_{1}, i_{2}, ⋯, i_{r}} ⊆ {3, 4, …, k}. We will show that x_{12J} = x̃_{12J} and x_{2J} = x̃_{2J}.

We can express the product x_{12J}x_{2J} as follows:

[2 ⊕ i_{1} ⊕ i_{2} ⊕ … ⊕ i_{r} ⊖ i_{r+1} ⊖ … ⊖ i_{k−2}].

Then consider the product

∏_{b≠i_{1},i_{2},... ,i_{r}}[2 ⊖ b] = \frac{[2 ⊖ 3][2 ⊖ 4][2 ⊖ 5] … [2 ⊖ k]}{[2 ⊖ i_{1}][2 ⊖ i_{2}] … [2 ⊖ i_{r}]} = ∏_{b≠i_{1},i_{2},... ,i_{r}} ˜ [2 ⊖ b].

The greatest exponent that occurs in this product is k − r − 2. The parameters that occur with exponent k − r − 2 are x_{12}, x_{12i_{1}i_{2}...i_{r}} and x_{2i_{1}i_{2}...i_{r}}. We already know that x_{12} = x̃_{12}, and hence we can deduce that

x_{12i_{1}i_{2}...i_{r}}x_{2i_{1}i_{2}...i_{r}} = x̃_{12i_{1}i_{2}...i_{r}} x̃_{2i_{1}i_{2}...i_{r}}.

This implies with (5.3) that

∏_{3≤j_{1}<j_{2}<...<j_{r}} ; x̃_{12j_{1}j_{2}...j_{r}} = \frac{x̃_{12i_{1}i_{2}...i_{r}} x̃_{2i_{1}i_{2}...i_{r}}}{x_{2i_{1}i_{2}...i_{r}}} \frac{∏_{3≤j_{1}<j_{2}<...<j_{r}} x_{12j_{1}j_{2}...j_{r}}}{x_{12i_{1}i_{2}...i_{r}}} ,

x̃_{2i_{1}i_{2}...i_{r}} ∏_{\begin{matrix}3≤j_{1}<j_{2}<...<j_{r}, \\ but not (j_{1}=i_{1},... ,j_{r}=i_{r}) \end{matrix}} x_{12j_{1}j_{2}...j_{r}} = x_{2i_{1}i_{2}...i_{r}} ∏_{\begin{matrix}3≤j_{1}<j_{2}<...<j_{r}, \\ but not (j_{1}=i_{1},... ,j_{r}=i_{r}) \end{matrix}} x̃_{12j_{1}j_{2}...j_{r}}.

The square-free condition implies that

x_{2i_{1}i_{2}...i_{r}} = x̃_{2i_{1}i_{2}...i_{r}}.

It immediately follows that

x_{12i_{1}i_{2}...i_{r}} = x̃_{12i_{1}i_{2}...i_{r}}.

5.3. The case k = 4. In this section we give some further details for the case k = 4, so that the reader can more easily work through the last section. We take y_{1} = x_{12}, y_{2} = x_{123}, y_{3} = x_{1234}, y_{4} = x_{124}, y_{5} = x_{23}, y_{6} = x_{24}, y_{7} = x_{234}.

[2] = x_{12}x_{123}x_{124}x_{1234}x_{23}x_{24}x_{234} and for example [2]^{3/4} ≤ y_{1} ≤ [2]^{3/4+1/(7·4^{7})}. The soluble residue class is x_{12}x_{123}x_{124}x_{1234}(x_{12}x_{124}x_{24} + x_{12}x_{123}x_{23}) modulo m[2] − 1.

Suppose there are two factorizations of [2], namely

x_{12}x_{123}x_{124}x_{1234}x_{23}x_{24}x_{234} = x̃_{12}x̃_{123}x̃_{124}x̃_{1234}x̃_{23}x̃_{24}x̃_{234}

and suppose that x_{123}x_{124}x_{1234}x_{23}x_{24} and x̃_{123}x̃_{124}x̃_{1234}x̃_{23}x̃_{24} are square-free. We know that

x_{12}x_{123}x_{124}x_{1234}x_{12}x_{123}x_{23} = x̃_{12}x̃_{123}x̃_{124}x̃_{1234}x̃_{12}x̃_{123}x̃_{23}, (5.4)

x_{12}x_{123}x_{124}x_{1234}x_{12}x_{124}x_{24} = x̃_{12}x̃_{123}x̃_{124}x̃_{1234}x̃_{12}x̃_{124}x̃_{24}. (5.5)

Multiplying both equations gives the equality

x_{12}^{4}x_{123}^{3}x_{124}^{3}x_{1234}^{2}x_{23}^{1}x_{24}^{1}x_{234}^{0} = x̃_{12}^{4}x̃_{123}^{3}x̃_{124}^{3}x̃_{1234}^{2}x̃_{23}^{1}x̃_{24}^{1}x̃_{234}^{0}.

The square-freeness implies that

x_{12} = x̃_{12},
x_{123}x_{124} = x̃_{123}x̃_{124},
x_{1234} = x̃_{1234},
x_{23}x_{24} = x_{123}x_{124},
x_{234} = x̃_{234}.

Combining this with (5.4) gives

x_{23}x_{123} = x̃_{23}x̃_{123}.

Combining this with x_{123}x_{124} = x̃_{123}x̃_{124} gives

x_{23}x̃_{123}x̃_{124} = x̃_{23}x̃_{123}x_{124}.

Any factor in x_{23} must (because of the square-free condition) occur in x̃_{23} and vice versa. This implies x_{23} = x̃_{23}. The arguments for the other parameters are similar.

6. The Number of Eliminable Classes

6.1. Lower bound estimate of ∑_{q≤x} ω(q). We now count the number ω_{m,k}(q) of

residue classes modulo q for which we can solve the equation. As before, q denotes a prime. In view of theorem 7.2, we aim to find a lower bound on ∑_{q≤x} \frac{ω_{m,k}(q)}{q}.

Let d_{K−1,[2]}(n) := ∑_{\begin{matrix}y_{1}y_{2}...y_{K−1}=n \\ y_{i}≥[2]^{ϑ_{i}} \end{matrix}} 1 and d′_{K−2,[2]}(n) = ∑_{\begin{matrix}y_{2}...y_{K−1}=n \\ y_{i}≥[2]^{ϑ_{i}} \end{matrix}} 1.

Note that

d_{K−1,[2]}(n) = ∑_{\begin{matrix}[2]^{ϑ_{1}} ≤x_{12} \\ x_{12}|n \end{matrix}} d′_{K−2,[2]}(\frac{n}{x_{12}} )

and that for [2] ≤ x

d′_{K−2,[2]}(n) ≥ d′_{K−2,x}(n).

By the above considerations concerning the ‘uniqueness of the residue class’, we can eliminate the following number of residue classes modulo q:

ω_{m,k}(q) = \{ \begin{matrix}∑_{\begin{matrix}[2]^{ϑ_{1}} ≤x_{12} \\ x_{12}| \frac{q+1}{m} \end{matrix}} μ^{2} (\frac{q+1}{mx_{12}} ) d′_{K−2,[2]} (\frac{q+1}{mx_{12}} ) & if q ≡ −1 mod m and q > q_{m,k}, \\ 0 & otherwise. \end{matrix}

Theorem 6.1 (Compare [Vau70] for the case k = 3). We have the following lower bound:

∑_{q≤x} ω_{m,k}(q) ≫_{m,k} x(log x)^{K−3}.

By partial summation this implies the following corollary:

SUMS OF k UNIT FRACTIONS 3221

Corollary 6.2.

∑_{q≤x} \frac{ω_{m,k}(q)}{q} ≫_{m,k} (log x)^{K−2}.

Proof of the theorem.

∑_{\frac{q+1}{m} ≤x} ω_{m,k}(q) = ∑_{\frac{q+1}{m} =[2]≤x} ∑_{\begin{matrix}x_{12}| \frac{q+1}{m} \\ [2]^{3/4}≤x_{12} \end{matrix}} d′_{K−2,[2]} (\frac{q + 1}{mx_{12}} ) μ^{2} (\frac{q + 1}{mx_{12}} )
≥ ∑_{\frac{x}{2} < \frac{q+1}{m} ≤x} ∑_{\begin{matrix}x_{12}| \frac{q+1}{m} \\ x^{3/4}≤x_{12} \end{matrix}} d′_{K−2,x} (\frac{q + 1}{mx_{12}} ) μ^{2} (\frac{q + 1}{mx_{12}} )
= ∑_{\frac{x}{2} < \frac{q+1}{m} ≤x} ∑_{\begin{matrix}r| \frac{q+1}{m} \\ r≤x^{1/4} \end{matrix}} d′_{K−2,x}(r)μ^{2}(r)
= ∑_{r≤x^{1/4}} μ^{2}(r)d′_{K−2,x}(r) (π(x; mr, −1) − π(\frac{x}{2}; mr, −1))
≥ ∑_{r≤x^{1/4}} μ^{2}(r)d′_{K−2,x}(r) (\frac{li(x) − li(\frac{x}{2})}{φ(mr)})

+ ∑_{r≤x^{1/4}} μ^{2}(r)d′_{K−2,x}(r) ((π(x; mr, −1) − π(\frac{x}{2}; mr, −1)) − (\frac{li(x) − li(\frac{x}{2})}{φ(mr)}))

≥ ∑_{r≤x^{1/4}} μ^{2}(r)d′_{K−2,x}(r) (\frac{li(x) − li(\frac{x}{2})}{φ(mr)}) + R(x) (say)
≫ \frac{1}{m} \frac{x}{log x} ∑_{r≤x^{1/4}} \frac{μ^{2}(r)}{φ(r)}d′_{K−2,x}(r) + R(x)
≫ \frac{x}{log x} ∑_{\begin{matrix}y_{2}y_{2}...y_{K−1}≤x^{1/4} \\ y_{i}≥x^{ϑ_{i}} \end{matrix}} \frac{μ^{2}(y_{2} … y_{K−1})}{φ(y_{2} … y_{K−1})} + R(x)
≫ \frac{x}{log x} ∑_{x^{ϑ_{i}} ≤y_{i}≤x^{ϑ_{i}+η}} \frac{μ^{2}(y_{2} … y_{K−1})}{φ(y_{2} … y_{K−1})} + R(x)
≫ \frac{x}{log x} (log x)^{K−2} + R(x) by theorem 6.4 below
≫ x(log x)^{K−3} + R(x).

The error term is

R(x)= ∑_{r≤x^{1/4}} μ^{2}(r)d′_{K−2,x}(r) ((π(x; mr, −1) − π(\frac{x}{2}; mr, −1))−(\frac{li(x) − li(\frac{x}{2})}{φ(mr)})) .

3222 CHRISTIAN ELSHOLTZ

For the estimate of the error term note that d′_{K−2,x}(r) ≤ d_{K−2}(r).

|R(x)| ≤ | ∑_{r≤x^{1/4}} \frac{μ^{2}(r)d′_{K−2,x}(r)}{\sqrt{φ(r)}}\sqrt{φ(mr)} ((π(x; mr, −1) − π(\frac{x}{2}; mr, −1))
− (\frac{li(x) − li(\frac{x}{2})}{φ(mr)})) |

by the Cauchy-Schwarz inequality

≪ ( ∑_{r≤x^{1/4}} \frac{μ^{2}(r) (d_{K−2}(r))^{2}}{φ(r)} )^{1/2}

×( ∑_{r≤x^{1/4}} φ(mr) ((π(x; mr,−1)−π(\frac{x}{2}; mr,−1))−(\frac{li(x)−li(\frac{x}{2})}{φ(mr)}))^{2})^{1/2}

by the Brun-Titchmarsh theorem:

φ(mr) |(π(x; mr, −1) − π(\frac{x}{2}; mr, −1)) − (\frac{li(x) − li(\frac{x}{2})}{φ(mr)})| ≪ \frac{x}{log x}

and by lemma 6.3 below

≪ ((log x)^{(K−2)^{2}})^{1/2} (\frac{x}{log x} ∑_{r≤x^{1/4}} |(π(x; mr, −1) − π(\frac{x}{2}; mr, −1))

− (\frac{li(x) − li(\frac{x}{2})}{φ(mr)})| )^{1/2}

by the Bombieri-Vinogradov theorem for an arbitrary constant A, ≪ \frac{x}{(log x)^{A}} for an arbitrary constant A.

Lemma 6.3 (This is lemma 4 of [Vio73]).

∑_{n≤x} μ^{2}(n)\frac{d_{k}^{l}(n)}{φ(n)} ≪ (log x)^{k^{l}}.

6.2. An estimate on ∑_{x^{α_{i}} ≤n_{i}≤x^{β_{i}}} \frac{μ^{2}(n_{1}...n_{s})}{n_{1}...n_{s}}. Recall that in corollary 6.2 for establishing the lower bound of the main term, we have used

∑_{x^{ϑ_{i}} ≤y_{i}≤x^{ϑ_{i}+η}} \frac{μ^{2}(y_{2} … y_{K−1})}{φ(y_{2} … y_{K−1})} ≫ (log x)^{K−2}.

This follows immediately from the following theorem:

Theorem 6.4. Let 0 < α_{i} < β_{i} < 1, for i = 1, ⋯, s. Then the following inequality holds:

∑_{\begin{matrix}x^{α_{i}} ≤n_{i}≤x^{β_{i}} \\ i=1,... ,s \end{matrix}} \frac{μ^{2}(n_{1}n_{2} … n_{s})}{n_{1}n_{2} … n_{s}} ≫_{s} (log x)^{s} ∏_{i=1}^{s}(β_{i} − α_{i}).

The proof below was suggested to me by Roger Heath-Brown. It simplified my own proof considerably.

We put α_{min} = min_{1≤i≤s} α_{i}. Let p stand for a prime and let w be an integer

parameter that may increase with x, whereas R is a fixed positive integer. Let r be an integer 0 < r ≤ R. Let also be 0 < α_{i} < β_{i} < 1, for i = 1, ⋯, s.

Lemma 6.5. For x > 0 we have that

∑_{1≤n≤x} \frac{1}{n} = log x + γ + O (\frac{1}{x^{1/4}} ) .

For x ≥ 1 this follows from ∑_{1≤n≤x} \frac{1}{n} = log x+γ +O (\frac{1}{x}) . For x < 1 this follows from | log x + γ| = O_{ε}(\frac{1}{x^{ε}}) for any positive ε.

The easy proof of the following lemma is left to the reader.

Lemma 6.6. Suppose that (w, R) = 1.

∑_{\begin{matrix}x^{α}<n≤x^{β} \\ w|n \\ n≡rmodR \end{matrix}} \frac{1}{n} = \frac{(β − α) log x}{wR} + O (\frac{1}{x^{α/4} w^{3/4}} ) .

If p^{2}|n_{1} ⋯ n_{s}, where p is a prime, then either for some n_{u} we have that p^{2}|n_{u} or for some n_{u} and n_{v} (with u ≠ v) we have that p|n_{u} and p|n_{v}. Thus it is enough to consider the case that p^{2} divides a product of two of the parameters. Let ∑′ denote that the sum is taken over the n_{u} and n_{v} satisfying the following conditions.

x^{α_{u}} < n_{u} ≤ x^{β_{u}}, x^{α_{v}} < n_{v} ≤ x^{β_{v}}, n_{u} ≡ r_{u} mod R, n_{v} ≡ r_{v} mod R.

Lemma 6.7.

\begin{matrix}∑ & ′ \\ p^{2}|n_{u}n_{v} \end{matrix} \frac{1}{n_{u}n_{v}} = (3 − \frac{2}{p}) \frac{(β_{u} − α_{u})(β_{v} − α_{v})}{R^{2} p^{2}}(log x)^{2} + O (\frac{log x}{x^{min(α_{u},α_{v})/4} p^{3/2}} ) .

Proof of the lemma.

\begin{matrix}∑ & ′ \\ p^{2}|n_{u}n_{v} \end{matrix} \frac{1}{n_{u}n_{v}} = \begin{matrix}∑ & ′ \\ p^{2}|n_{u} \end{matrix} \frac{1}{n_{u}n_{v}} +\begin{matrix}∑ & ′ \\ p^{2}|n_{v} \end{matrix} \frac{1}{n_{u}n_{v}} +\begin{matrix}∑ & ′ \\ p|n_{u}, p|n_{v} \end{matrix} \frac{1}{n_{u}n_{v}}

−\begin{matrix}∑ & ′ \\ p^{2}|n_{u},p|n_{v} \end{matrix} \frac{1}{n_{u}n_{v}} −\begin{matrix}∑ & ′ \\ p|n_{u},p^{2}|n_{v} \end{matrix} \frac{1}{n_{u}n_{v}}

= S_{1} + S_{2} + S_{3} − S_{4} − S_{5} (say).

The lemma follows with

S_{1,2,3} = \frac{(β_{u} − α_{u})(β_{v} − α_{v})}{p^{2} R^{2}}(log x)^{2} + O (\frac{log x}{x^{min(α_{u},α_{v})/4} p^{3/2}} ) .

S_{4,5} = \frac{(β_{u} − α_{u})(β_{v} − α_{v})}{p^{3} R^{2}}(log x)^{2} + O (\frac{log x}{x^{min(α_{u},α_{v})/4} p^{9/4}} ) .

Proposition 6.8. Let p denote a prime and suppose that (p, R) = 1. Then we have that

∑_{\begin{matrix}x^{α_{i}} <n_{i}≤x^{β_{i}} \\ p^{2}|n_{1}···n_{s} \\ n_{i}≡r_{i} modR \end{matrix}} \frac{1}{n_{1} ⋯ n_{s}} = \frac{1}{R^{s}} (\frac{s(s + 1)}{2p^{2}} + O_{s}(\frac{1}{p^{3}} )) (∏_{i=1}^{s}(β_{i} − α_{i})) (log x)^{s}

+O_{s} (\frac{(log x)^{s−1}}{x^{α_{min}/4} p^{3/2}} ) .

Proof of the proposition. To prove the proposition one applies the above lemma to all s cases with p^{2}|n_{u} and all \frac{s(s−1)}{2} cases with p|n_{u}, p|n_{v}. This explains the \frac{s(s+1)}{2p^{2}} part. Other cases like p^{2}|n_{u}, p|n_{v} give the O_{s}(\frac{1}{p^{3}} ) part. The other factors are of

the type (\frac{(β_{i}−α_{i})}{R} log x + O (\frac{1}{x^{α_{i}/4}} )). Thus multiplying and collecting error terms proves the proposition.

The proposition implies the following corollary:

Corollary 6.9. Let p denote a prime and suppose that (p, R) = 1. Then there exists a constant C_{s} such that the following inequality holds:

∑_{\begin{matrix}x^{α_{i}} <n_{i}≤x^{β_{i}} \\ p^{2}|n_{1}···n_{s} \\ n_{i}≡r_{i} modR \end{matrix}} \frac{1}{n_{1} ⋯ n_{s}} ≤ \frac{C_{s}}{p^{2} R^{s}} (log x)^{s}.

Proof of theorem 6.4. Let Q_{s} denote a fixed integer to be determined below.

If (n, ∏_{p≤Q_{s}} p^{2}) = 1, then n is trivially square-free with regard to primes p ≤ Q_{s}. For such n we see that μ^{2}(n) ≥ 1 − ∑\begin{matrix}p>Q_{s} \\ p^{2}|n \end{matrix} 1.

Let us choose R = ∏_{p≤Q_{s}} p^{2}. To ensure that n_{1}n_{2} ⋯ n_{s} is square-free with regard to primes p ≤ Q_{s} it is enough to choose n_{i} ≡ 1 mod R for all i = 1, ⋯, s. Hence

∑_{\begin{matrix}x^{α_{i}} <n_{i}≤x^{β_{i}} \\ n_{i}≡1modR \end{matrix}} \frac{μ^{2}(n_{1} ⋯ n_{s})}{n_{1} ⋯ n_{s}} ≥ ∑_{\begin{matrix}x^{α_{i}} <n_{i}≤x^{β_{i}} \\ n_{i}≡1modR \end{matrix}} \frac{1}{n_{1} ⋯ n_{s}} − ∑_{\begin{matrix}p>Q_{s} \\ p^{2}|n_{1}···n_{s} \end{matrix}}  ∑_{\begin{matrix}x^{α_{i}} <n_{i}≤x^{β_{i}} \\ n_{i}≡1modR \end{matrix}} \frac{1}{n_{1} ⋯ n_{s}}

≥ \frac{1}{R^{s}} ∏_{i=1}^{s}(β_{i} − α_{i})(log x)^{s} + O_{s} (\frac{(log x)^{s−1}}{x^{α_{min}/4}} )

− ∑_{p>Q_{s}} \frac{1}{p^{2}} \frac{C_{s}}{R^{s}} ∏_{i=1}^{s}(β_{i} − α_{i})(log x)^{s} + O_{s} ( ∑_{p>Q_{s}} \frac{1}{p^{3/2}} \frac{(log x)^{s−1}}{x^{α_{min}/4}} )

= (1 − C_{s} ∑_{p>Q_{s}} \frac{1}{p^{2}} ) \frac{1}{R^{s}} ∏_{i=1}^{s}(β_{i} − α_{i})(log x)^{s} + O_{s} (\frac{(log x)^{s−1}}{x^{α_{min}/4}} ) .

We now choose Q_{s} sufficiently large such that C_{s} ∑_{p>Q_{s}} \frac{1}{p^{2}} < 1. The theorem follows immediately.

7. The Final Sieve Result

We will use Montgomery’s version of the large sieve.

Theorem 7.1 (see [Mon78]). Let P denote the set of primes. Let p be a prime. Let A be a set of integers which avoids ω(p) residue classes modulo p. Here ω : P → ℕ with 0 ≤ ω(p) ≤ p − 1. Let A(x) denote the counting function A(x) = ∑_{a≤x,a∈A} 1. Then the following upper bound on the counting function holds:

A(N) ≤ \frac{2N}{L} , where L = ∑_{q≤N^{1/2}} μ^{2}(q) ∏_{p|q} \frac{ω(p)}{p − ω(p)}.

Vaughan generally proved a lower bound estimate for L, when a lower bound for

∑_{p≤x} \frac{ω(p)}{p} is known.

Theorem 7.2 (Vaughan, [Vau73]). Let α > 0, C_{1} > 0. If, for sufficiently large x, the inequality

∑_{p≤x} \frac{ω(p)}{p} > C_{1}(log x)^{α}

holds, then there is a positive constant C(α, C_{1}) such that

L > exp (C(α, C_{1}) (log N)^{\frac{α}{α+1}} ) .

Hence corollary 6.2 and theorem 7.2 immediately yield the following sieve bound, which proves our theorem 1.3:

E_{m,k}(N) ≤ 2N exp (−c_{m,k}(log N)^{1− \frac{1}{2^{k−1}−1}} ) .

Remark 7.3. For k = 3 we have worked out the following slightly more explicit version of Vaughan’s theorem:

We may observe, that for k = 3 it suffices to apply the Bombieri-Vinogradov theorem with an exponent of A = \frac{3}{2} in the upper bound ≪ \frac{x}{(log x)^{A}}. For A < 2−ε it can be shown that the ≪-constant is effective, (see [Kar93], page 140). (Vaughan’s approach was slightly different and required an A > 2.) Moreover, it is possible to compute admissible values of the constants c_{m,k}.

An admissible value for c_{m,3} is

c_{m,3} = \frac{3}{e^{\frac{2}{3}}} (\frac{1}{8m})^{\frac{1}{3}} − ε, where ε > 0.

In the case of the Erdős-Straus conjecture with m = 4 we found that c_{4,3} = 0.5645 is an admissible value, (see [Els96]). This result holds for N > N_{m}, where N_{m} is, in principle, effective. An entirely effective but very weak upper bound was recently proven, (see [AB98]).

References

[AB98] M.H. Ahmadi and M.N. Bleicher. On the conjectures of Erdős and Straus, and Sierpinski on Egyptian fractions. Int. J. Math. Stat. Sci., 7:169–185, 1998. See also Zentralblatt 990.17875. MR 99k:11049

[Cro00] E.S. Croot. Unit Fractions. PhD thesis, University of Georgia, Athens, 2000. The thesis is based on three papers: 1) On some questions of Erdős and Graham about Egyptian fractions, to appear in Mathematika, 2) On unit fractions with denominators in short intervals, to appear in Acta Arithmetica, 3) On a coloring conjecture about unit fractions.

[Ded31] R. Dedekind. Über Zerlegungen von Zahlen durch ihren größten gemeinsamen Teiler, (Festschrift der Universität Braunschweig, 1897) in Gesammelte mathematische Werke, Band 2. Braunschweig: Friedr. Vieweg & Sohn A.-G., 1931.

[EG80] P. Erdős and R.L. Graham. Old and New Problems and Results in Combinatorial Number Theory. Université de Genève, 1980. Monographie No. 28 de L’Enseignement Mathématique. MR 82j:10001

[Els96] C. Elsholtz. The Erdős-Straus conjecture on \frac{4}{n} = \frac{1}{x} + \frac{1}{y} + \frac{1}{z}. Diploma thesis, Technische Universität Darmstadt, 1996.

[Els98] C. Elsholtz. Sums of k Unit Fractions. PhD thesis, Technische Universität Darmstadt, 1998.

[Erd50] P. Erdős. Az \frac{1}{x_{1}} + \frac{1}{x_{2}} + … + \frac{1}{x_{n}} = \frac{a}{b} egyenlet egész számú megoldásairól (On a Diophantine equation). Mat. Lapok, 1:192–210, 1950. MR 13:208b

[Gra64] R.L. Graham. On finite sums of unit fractions. Proc. London Math. Soc. (3), 14:193–207, 1964. MR 28:3968

[Guy94] R.K. Guy. Unsolved Problems in Number Theory, second edition. Springer-Verlag, 1994. MR 96e:11002

[Kar93] A.A. Karatsuba. Basic Analytic Number Theory. Springer Verlag, 1993. MR 94a:11001 [Li81] Delang Li. On the Equation \frac{4}{n} = \frac{1}{x} + \frac{1}{y} + \frac{1}{z}. J. Number Theory, 13:485–494, 1981.

See also Letter to the editor, J. Number Theory 15:282, 1982. MR 83e:10026; MR 84b:10024

[Mar00] G. Martin. Denser Egyptian fractions. Acta Arith. 95:231–260, 2000.

[Mar99] G. Martin. Dense Egyptian fractions. Trans. Amer. Math. Soc., 351:3641–3657, 1999. MR 99m:11035

[Mon78] H.L. Montgomery. The analytic principle of the large sieve. Bull. Amer. Math. Soc., 84:547–567, 1978. MR 57:5931

[Mor69] L.J. Mordell. Diophantine Equations, volume 30 of Pure and Applied Mathematics. Academic Press, 1969. MR 40:2600

[Nak39] M. Nakayama. On the Decomposition of a Rational Number into “Stammbrüche”. Tôhuku Math. J., 46:1–21, 1939. MR 1:134c

[Nar86] W. Narkiewicz. Classical Problems in Number Theory, volume 62 of Mathematical Monographs. PWN, 1986. MR 90e:11002

[San91] J.W. Sander. On \frac{4}{n} = \frac{1}{x} + \frac{1}{y} + \frac{1}{z} and Rosser’s sieve. Acta Arith., 59:183–204, 1991. MR 92j:11031

[San94] J.W. Sander. On \frac{4}{n} = \frac{1}{x} + \frac{1}{y} + \frac{1}{z} and Iwaniec’ Half Dimensional Sieve. J. Number Theory, 46:123–136, 1994. MR 95e:11044

[San97] J.W. Sander. Egyptian Fractions and the Erdős-Straus Conjecture. Nieuw Arch. Wisk. (4), 15:43–50, 1997. MR 98d:11039

[Scha] A. Schinzel. Erdős’s work on finite sums of unit fractions. To appear in Paul Erdős and his Mathematics, Proceedings of the Erdős conference (Budapest 1999), (Editors: G. Hálasz, L. Lovász, M. Simonovits, V. Sós).

[Sch00] A. Schinzel. On sums of three unit fractions with polynomial denominators. Funct. Approx. Comment. Math. 28:187–194, 2000.

[Sch56] A. Schinzel. Sur quelques propriétés des nombres \frac{3}{n} et \frac{4}{n}, où n est un nombre impair. Mathesis, 65:219–222, 1956. MR 18:284a

[Sch74] W. Schwarz. Einführung in die Siebmethoden der analytischen Zahlentheorie. Bibliographisches Institut, Mannheim, 1974. MR 53:13147

[She86] Shen Zun. On the diophantine equation ∑_{i=0}^{k} \frac{1}{x_{i}} = \frac{a}{n}. Chinese Ann. Math. Ser. B, 7:213–220, 1986. MR 87j:11026 [Sie56] W. Sierpiński. Sur les décompositions de nombres rationnels en fractions primaires. Math-

esis, 65:16–32, 1956. MR 17:1185d

[Sos05] E. Sós. Die diophantische Gleichung \frac{1}{x} = \frac{1}{x_{1}} + \frac{1}{x_{2}} + … + \frac{1}{x_{n}}. Zeitschrift für mathematischen und naturwissenschaftlichen Unterricht, 36:97–102, 1905.

[Sos06] E. Sós. Zwei diophantische Gleichungen. Zeitschrift für mathematischen und naturwissenschaftlichen Unterricht, 37:186–190, 1906.

[Vau70] R.C. Vaughan. On a problem of Erdős, Straus and Schinzel. Mathematika, 17:193–198, 1970. MR 44:6600

[Vau73] R.C. Vaughan. Some Applications of Montgomery’s Sieve. J. Number Theory, 5:64–79, 1973. MR 49:7222

[Vio73] C. Viola. On the diophantine equations ∏_{0}^{k} x_{i} −∑_{0}^{k} x_{i} = n and ∑_{0}^{k} \frac{1}{x_{i}} = \frac{a}{n}. Acta Arith., 22:339–352, 1973. MR 48:234

[Web70] W.A. Webb. On \frac{4}{n} = \frac{1}{x} + \frac{1}{y} + \frac{1}{z}. Proc. Amer. Math. Soc., 25:578–584, 1970. MR 41:1639 [Yan82] Xun Qian Yang. A note on \frac{4}{n} = \frac{1}{x} + \frac{1}{y} + \frac{1}{z}. Proc. Amer. Math. Soc., 85:496–498, 1982.

MR 83j:10017

Institut für Mathematik, Technische Universität Clausthal, Erzstrasse 1, D-38678 Clausthal-Zellerfeld, Germany

   E-mail address: elsholtz@math.tu-clausthal.de