You are currently browsing the tag archive for the ‘Erdos-Straus conjecture’ tag.

Christian Elsholtz and I have recently finished our joint paper “Counting the number of solutions to the Erdös-Straus equation on unit fractions“, submitted to the Journal of the Australian Mathematical Society. This supercedes my previous paper on the subject, by obtaining stronger and more general results. (The paper is currently in the process of being resubmitted to the arXiv, and should appear at this link within a few days.)

As with the previous paper, the main object of study is the number {f(n)} of solutions to the Diophantine equation

\displaystyle  \frac{4}{n} = \frac{1}{x} + \frac{1}{y} + \frac{1}{z} \ \ \ \ \ (1)

with {x,y,z} positive integers. The Erdös-Straus conjecture asserts that {f(n)>0} for all {n>1}. Since {f(nm) \geq f(n)} for all positive integers {n,m}, it suffices to show that {f(p)>0} for all primes {p}.

We single out two special types of solutions: Type I solutions, in which {x} is divisible by {n} and {y,z} are coprime to {n}, and Type II solutions, in which {x} is coprime to {n} and {y,z} are divisible by {n}. Let {f_I(n), f_{II}(n)} denote the number of Type I and Type II solutions respectively. For any {n}, one has

\displaystyle  f(n) \geq 3 f_I(n) + 3 f_{II}(n),

with equality when {n} is an odd primes {p}. Thus, to prove the Erdös-Strauss conjecture, it suffices to show that at least one of {f_I(p)}, {f_{II}(p)} is positive whenever {p} is an odd prime.

Our first main results are the asymptotics

\displaystyle  N \log^3 N \ll \sum_{n \leq N} f_I(n) \ll N \log^3 N

\displaystyle  N \log^3 N \ll \sum_{n \leq N} f_{II}(n) \ll N \log^3 N

\displaystyle  N \log^2 N \ll \sum_{p \leq N} f_I(p) \ll N \log^2 N \log\log N

\displaystyle  N \log^2 N \ll \sum_{p \leq N} f_{II}(p) \ll N \log^2 N.

This improves upon the results in the previous paper, which only established

\displaystyle  N \log^2 N \ll \sum_{p \leq N} f_I(p) \ll N \exp(O( \frac{\log x}{\log\log x} ))


\displaystyle  N \log^2 N \ll \sum_{p \leq N} f_{II}(p) \ll N \log^2 N \log \log N.

The double logarithmic factor in the upper bound for {\sum_{p \leq N} f_I(p)} is artificial (arising from the inefficiency in the Brun-Titchmarsh inequality on very short progressions) but we do not know how to remove it.

The methods are similar to those in the previous paper (which were also independently discovered in unpublished work of Elsholtz and Heath-Brown), but with the additional input of the Erdös divisor bound on expressions of the form {\sum_{n \leq N} \tau(P(n))} for polynomials {P}, discussed in this recent blog post. (Actually, we need to tighten Erdös’ bound somewhat, to obtain some uniformity in the bounds even as the coefficients of {P} become large, but this turns out to be achievable by going through the original arguments of Erdös more carefully.)

We also note an observation of Heath-Brown, that in our notation gives the lower bound

\displaystyle  N \log^6 N \ll \sum_{n \leq N} f(n);

thus, we see that for typical {n}, that most solutions to the Erdös-Straus equation are not of Type I or Type II, in contrast to the case when {n} is prime.

We also have a number other new results. We find a way to systematically unify all the previously known parameterisations of solutions to the Erdös-Straus equation, by lifting the Cayley-type surface {\{ (x,y,z): \frac{4}{n} = \frac{1}{x} + \frac{1}{y} + \frac{1}{z} \}} to a certain three-dimensional variety in six-dimensional affine space, in such a way that integer points in the former arise from integer points in the latter. Each of the previously known characterisations of solutions then corresponds to a different choice of coordinates on this variety. (This point of view was also adopted in a paper of Heath-Brown, who interprets this lifted variety as the universal torsor of the Cayley surface.) By optimising between these parameterisations and exploiting the divisor bound, we obtain some bounds on the worst-case behaviour of {f_I(n)} and {f_{II}(n)}, namely

\displaystyle  f_I(n) \ll n^{3/5 + O(1/\log \log n)}


\displaystyle  f_{II}(n) \ll n^{2/5 + O(1/\log \log n)},

which should be compared to a recent previous bound {f(n) \ll n^{2/3 + O(1/\log \log n)}} of Browning and Elsholtz. In the other direction, we show that {f(n) \gg n^{(3+o(1))/\log\log n}} for infinitely many {n}, and {f(p) \gg \log^{\frac{\log 3}{2}-o(1)} p} for almost all primes {p}. Here, the main tools are some bounds for the representation of a rational as a sum of two unit fractions in the above-mentioned work of Browning and Elsholtz, and also the Turán-Kubilius inequality.

We also completely classify all the congruence classes that can be solved by polynomials, completing the partial list discussed in the previous post. Specifically, the Erdös-Straus conjecture is true for {n} whenever one of the following congruence-type conditions is satisfied:

  1. {n = -f \mod 4ad}, where {a,d,f \in {\bf N}} are such that {f|4a^2 d+1}.
  2. {n = -f \mod 4ac} and {n = -\frac{c}{a} \mod f}, where {a,c,f \in {\bf N}} are such that {(4ac,f)=1}.
  3. {n = -f \mod 4cd} and {n^2 = -4c^2d \mod f}, where {c,d,f \in {\bf N}} are such that {(4cd,f)=1}.
  4. {n = -\frac{1}{e} \mod 4ab} or {n = -e \mod 4ab}, where {a,b,e \in {\bf N}} are such that {e|a+b} and {(e,4ab)=1}.
  5. {n = -4a^2d \mod f}, where {a,d,f \in {\bf N}} are such that {4ad|f+1}.
  6. {n = -4a^2d-e \mod 4ade}, where {a,d,e \in {\bf N}} are such that {(4ad,e)=1}.

In principle, this suggests a way to extend the existing verification of the Erdös-Straus conjecture beyond the current range of {10^{14}} by collecting all congruences to small moduli (e.g. up to {10^6}), and then using this to sieve out the primes up to a given size.

Finally, we begin a study of the more general equation

\displaystyle  \frac{m}{n} = \frac{1}{n_1}+\ldots+\frac{1}{n_k} \ \ \ \ \ (2)

where {m > k \geq 3} are fixed. We can obtain a partial analogue of our main bounds for the {m=4,k=3} case, namely that

\displaystyle  \sum_{n \leq N} f_{m,k,II}(n) \gg N \log^{2^{k-1}-1} N


\displaystyle  \sum_{p \leq N} f_{m,k,II}(p) \gg N \log^{2^{k-1}-2} N / \log\log N

were {f_{m,k,II}(n)} denotes the number of solutions to (2) which are of “Type II” in the sense that {n_2,\ldots,n_k} are all divisible by {n}. However, we do not believe our bounds to be sharp in the large {k} regime, though it does show that the expected number of solutions to (2) should grow rapidly in {k}.

I have just uploaded to the arXiv my paper “On the number of solutions to {\frac{4}{p}=\frac{1}{n_1}+\frac{1}{n_2}+\frac{1}{n_3}}“, submitted to the Journal of the Australian Mathematical Society.

For any positive integer {n}, let {f(n)} denote the number of solutions to the Diophantine equation

\displaystyle  \frac{4}{n} = \frac{1}{n_1} + \frac{1}{n_2} + \frac{1}{n_3}

where {n_1,n_2,n_3} are positive integers (we allow repetitions, and do not require the {n_i} to be increasing). The Erdös-Straus conjecture asserts that {f(n)>0} for all {n \geq 2}. By dividing through by any positive integer {m} we see that {f(nm) \geq f(n)}, so it suffices to verify this conjecture for primes {n=p}, i.e. to solve the Diophantine equation

\displaystyle  \frac{4}{p} = \frac{1}{n_1} + \frac{1}{n_2} + \frac{1}{n_3} \ \ \ \ \ (1)

for each prime {p}. As the case {p=2} is easily solved, we may of course restrict attention to odd primes.

This conjecture remains open, although there is a reasonable amount of evidence towards its truth. For instance, it was shown by Vaughan that for any large {x}, the number of exceptions {f(n)=0} to the Erdös-Straus conjecture with {n<x} is at most {x \exp( - c \log^{2/3} x)} for some absolute constant {c>0}. The Erdös-Straus conjecture is also verified in several congruence classes of primes; for instance, from the identity

\displaystyle  \frac{4}{p} = \frac{1}{\frac{p+1}{4}} + \frac{1}{\frac{p+1}{2}p} + \frac{1}{\frac{p+1}{2}p}

we see that the conjecture holds when {p = 3 \hbox{ mod } 4}. Further identities of this type can be used to resolve the conjecture unless {p} is a quadratic residue mod {840}, which leaves only six residue classes in that modulus to check (namely, {1, 121, 169, 289, 361}, and {529}). However, there is a significant obstruction to eliminating the quadratic residue classes, as we will discuss later.

By combining these reductions with extensive numerical calculations, the Erdös-Straus conjecture was verified for all {n \leq 10^{14}} by Swett.

One approach to solving Diophantine equations such as (1) is to use methods of analytic number theory, such as the circle method, to obtain asymptotics (or at least lower bounds) for the number {f(p)} of solutions (or some proxy for this number); if one obtains a lower bound which is nontrivial for every {p}, one has solved the problem. (One can alternatively view such methods as a variant of the probabilistic method; in this interpretation, one chooses the unknowns {n_1,n_2,n_3} according to some suitable probability distribution and then tries to show that the probability of solving the equation is positive.) Such techniques can be effective for instance for certain instances of the Waring problem. However, as a general rule, these methods only work when there are a lot of solutions, and specifically when the number {f(p)} of solutions grows at a polynomial rate with the parameter {p}.

The first main result of my paper is that the number of solutions {f(p)} is essentially logarithmic in nature, thus providing a serious obstruction to solution by analytic methods, as there is almost no margin of error available. More precisely, I show that for almost all primes {p} (i.e. in a subset of primes of relative density {1}), one has {f(p) \leq p^{o(1)}}, or more precisely that

\displaystyle  f(p) \leq \exp( O( \frac{\log p}{\log\log p} ) ).

Readers familiar with analytic number theory will recognise the right-hand side from the divisor bound, which indeed plays a role in the proof.

Actually, there are more precise estimates which suggest (though do not quite prove) that the mean value of {f(p)} is comparable to {\log^3 p}. To state these results properly, I need some more notation. It is not difficult to show that if {p} is an odd prime and {n_1,n_2,n_3} obey (1), then at least one, but not all, of the {n_1,n_2,n_3} must be a multiple of {p}. Thus we can split {f(p) = f_1(p) + f_2(p)}, where {f_i(p)} is the number of solutions to (1) where exactly {i} of the {n_1,n_2,n_3} are divisible by {p}. The sharpest estimates I can prove are then

Theorem 1 For all sufficiently large {x}, one has

\displaystyle  x \log^2 x \ll \sum_{p < x} f_1(p) \ll x \exp( O( \frac{\log x}{\log \log x} ) )


\displaystyle  x \log^2 x \ll \sum_{p < x} f_2(p) \ll x \log^2 x \log\log x.

Since the number of primes less than {x} is comparable to {x/\log x} by the prime number theorem, this shows that the mean value of {f_2(p)} in this range is between {\log^3 x} and {\log^3 \log\log x}, and the mean value of {f_1(p)} is between {\log^3 x} and {\exp( O( \frac{\log x}{\log \log x}) )}, which gives the previous result as a corollary (thanks to a Markov inequality argument). A naive Poisson process heuristic then suggests that each prime {p} has a “probability” {1 - O( \exp( - c \log^3 p ) )} of having a solution to (1), which by the Borel-Cantelli lemma heuristically suggests that there are only finitely many {p} for which (1) fails. Of course, this is far from a rigorous proof (though the result of Vaughan mentioned earlier, which is based on the large sieve, can be viewed as a partial formalisation of the argument).

The first step in obtaining these results is an elementary description of {f_1(p), f_2(p)} in terms of some divisibility constraints. More precisely, we have

Lemma 2 Let {p} be an odd prime. Then {f_1(p)} is equal to three times the number of triples {(a,b,c)} of positive integers, with {a, b} coprime, {c} dividing {a+b}, and {4ab} dividing {cp+1}. Similarly, {f_2(p)} is equal to three times the number of triples {(a,b,c)} of positive integers, with {a, b} coprime, {c} dividing {a+b}, and {4ab} dividing {p+c}.

One direction of this lemma is very easy: if {c} divides {a+b} and {4ab} divides {cp+1} then the identity

\displaystyle  \frac{4}{p} = \frac{1}{\frac{pc+1}{4}p} + \frac{1}{\frac{pc+1}{4a} \frac{a+b}{c}} + \frac{1}{\frac{pc+1}{4b} \frac{a+b}{c}}

and its cyclic permutations give three contributions to {f_1(p)}, and similarly if {4ab} divides {p+c} instead then the identity

\displaystyle  \frac{4}{p} = \frac{1}{\frac{p+c}{4}} + \frac{1}{\frac{p+c}{4a} \frac{a+b}{c} p} + \frac{1}{\frac{p+c}{4b} \frac{a+b}{c} p}

and its cyclic permutations give three contributions to {f_2(p)}. Conversely, some elementary number theory can be used to show that all solutions contributing to either {f_1(p)} or {f_2(p)} are of these forms. (Similar criteria have been used in prior literature, for instance in the previously mentioned paper of Vaughan.)

This lemma, incidentally, provides a way to quickly generate a large number of congruences of primes {p} for which the Erdös-Straus conjecture can be verified. Indeed, from the above lemma we see that if {a, b} are coprime and {c} is any odd factor of {a+b} (and hence coprime to {4ab}), then the Erdös-Straus conjecture is true whenever {p=-c \hbox{ mod } 4ab} or {p = -c^{-1} \hbox{ mod } 4ab}. For instance,

  • Taking {(a,b,c)=(1,1,1)}, we see that the conjecture holds whenever {p=3 \hbox{ mod } 4} (leaving only those primes {p=1 \hbox{ mod } 4});
  • Taking {(a,b,c)=(1,2,3)} we see that the conjecture holds whenever {p=5 \hbox{ mod } 8} (leaving only those primes {p=1 \hbox{ mod } 8});
  • Taking {(a,b,c)=(3,4,7)}, we see that the conjecture holds whenever {p=5 \hbox{ mod } 12} ((leaving only those primes {p=1 \hbox{ mod } 24});
  • Taking {(a,b,c)=(1,5,3)}, we see that the conjecture holds whenever {p=17, 13 \hbox{ mod } 20} (leaving only those primes {p=1,49 \hbox{ mod } 120});
  • Taking {(a,b,c)=(1,14,15)}, we see that the conjecture holds whenever {p= 41 \hbox{ mod } 56}; taking instead {(a,b,c)=(2,21,23)}, we see that the conjecture holds whenever {p = 73, 145 \hbox{ mod } 168}. (This leaves only the primes {p} that are equal to one of the six quadratic residues {1, 121, 169, 289, 361, 529 \hbox{ mod } 840}, an observation first made by Mordell.)
  • etc.

If we let {g_1(n)} (resp. {g_2(n)}) be the number of triples {(a,b,c)} with {a,b} coprime, {c} dividing {a+b}, and {n} congruent to {-c^{-1}} (resp. {-c}) mod {4ab}, the above lemma tells us that {f_i(p) = 3g_i(p)} for all odd primes {p}, so it suffices to show that {g_1(p), g_2(p)} are non-zero for all {p}. One might hope that there are enough congruence relations provided by the previous observation to obtain a covering system of congruences which would resolve the conjecture. Unfortunately, as was also observed by Mordell, an application of the quadratic reciprocity law shows that these congruence relations cannot eliminate quadratic residues, only quadratic non-residues. More precisely, one can show that if {a,b,c,p} are as above (restricting to the case p=1 \hbox{ mod } 8amp;fg000000, which contains all the unsolved cases of the conjecture) and {q} is the largest odd factor of {4ab}, then the Jacobi symbols {\left(\frac{-c}{q}\right)} and {\left(\frac{-c^{-1}}{q}\right)} are always equal to {-1}. One consequence of this is that {g_1(n)=g_2(n)=0} whenever {n} is an odd perfect square. This makes it quite hard to resolve the conjecture for odd primes {p} which resemble a perfect square in that they lie in quadratic residue classes to small moduli (and, from Dirichlet’s theorem on primes in arithmetic progressions, one can find many primes of this type). The same argument also shows that for an odd prime {p}, there are no solutions to

\displaystyle  \frac{4}{p^2} = \frac{1}{n_1} + \frac{1}{n_2} + \frac{1}{n_3}

in which one or two of the {n_1,n_2,n_3} are divisible by {p^2}, with the other denominators being coprime to {p}. (Of course, one can still get representations of {\frac{4}{p^2}} by starting with a representation of {\frac{4}{p}} and dividing by {p}, but such representations are is not of the above form.) This shows that any attempt to establish the Erdös-Straus conjecture by manually constructing {n_1,n_2,n_3} as a function of {p} must involve a technique which breaks down if {p} is replaced by {p^2} (for instance, this rules out any approach based on using polynomial combinations of {p} and dividing into cases based on residue classes of {p} in small moduli). Part of the problem here is that we do not have good bounds that prevent a prime {p} from “spoofing” a perfect square to all small moduli (say, to all moduli less than a small power of {p}); this problem is closely related (via quadratic reciprocity) to Vinogradov’s conjecture on the least quadratic nonresidue, discussed in this previous blog post.

It remains to control the sums {\sum_{p<x} g_i(p)} for {i=1,2}. The lower bounds {\sum_{p<x} g_i(p) \gg x \log^2 x} are relatively routine to establish, arising from counting the contribution of those {a,b,c} that are somewhat small (e.g. less than {x^{0.2}}), and use only standard asymptotics of arithmetic functions and the Bombieri-Vinogradov inequality (to handle the restriction of the summation to primes). To obtain (nearly) matching upper bounds, one needs to prevent {a,b,c} from getting too large. In the case of {g_2(p)}, the fact that {c} divides {a+b} and {4ab} divides {c+p} soon leads one to the bounds {ab \ll x}, at which point one can count primes in residue classes modulo {4ab} with reasonable efficiency via the Brun-Titchmarsh inequality. This inequality unfortunately introduces a factor of {\frac{4ab}{\phi(4ab)}}, which we were only able to handle by bounding it crudely by {O(\log \log x)}, leading to the double logarithmic loss in the {f_2} sum.

For {g_1(p)}, these arguments do not give good bounds, because it is possible for {ab} to be much larger than {x}, and one can no longer easily count solutions to {p = -c^{-1} \hbox{ mod } 4ab}. However, an elementary change of variables resolves this problem. It turns out that if one lets {l,m} be the positive integers

\displaystyle  l := \frac{pc+1}{4ab}

\displaystyle  m := \frac{4la^2+1}{c}

then one can convert the triple {(a,b,c)} to a triple {(a,l,m)} obeying the constraints

\displaystyle  al \leq p

\displaystyle  m | 4la^2+1

\displaystyle  p = -m \hbox{ mod } 4al.

Conversely, every such triple {(a,l,m)} determines {(a,b,c)} by the formulae

\displaystyle  c = \frac{4la^2+1}{m}; b = c \frac{p+m}{4al} - a = \frac{4la^2 p + m + p}{4alm}. \ \ \ \ \ (2)

The point is that this transformation now places {p} in a residue class modulo {4al} rather than {4ab}, and with {al = O(x)}, this allows one to count the number of solutions reasonably efficiently. The main loss now comes from counting the number of divisors {m} of {4la^2+1}; in particular, one becomes interested in estimating sums such as

\displaystyle  \sum_{a \sim A} \sum_{l \sim L} d( 4la^2+1 )

where {A, L} are less than {x} and {d(n)} is the number of divisors of {n}. In principle, because {d(n)} behaves like {\log n} on the average (as can be seen from the Dirichlet hyperbola method), we expect this sum to be of order {AL \log x}, but I was unable to show this, instead using the far cruder divisor bound

\displaystyle  d(n) \ll \exp( O(\frac{\log n}{\log\log n}) )

to obtain an upper bound of {AL \exp( O(\frac{\log x}{\log\log x}) )}. Any improvement upon this bound would lead to a corresponding improvement in the upper bound for {\sum_{p<x} f_1(p)}. While improvement is possible in some ranges (particularly when {L} is large) using various bounds on Kloosterman-type exponential sums, I was not able to adequately control these sums when {L} was fairly small (e.g. polylogarithmic size in {x}), as one could no longer extract much of an averaging effect from the {l} summation in that case. Part of the difficulty is that in that case one must somehow exploit the fact that {4la^2+1} is irreducible as a polynomial in {a} for any fixed {l}, otherwise there will be too many divisors.

Read the rest of this entry »