Hostname: page-component-8448b6f56d-wq2xx Total loading time: 0 Render date: 2024-04-18T05:41:52.874Z Has data issue: false hasContentIssue false
  • English
  • Français

COUNTING THE NUMBER OF SOLUTIONS TO THE ERDŐS–STRAUS EQUATION ON UNIT FRACTIONS

Part of: Multiplicative number theory Diophantine equations

Published online by Cambridge University Press:  15 May 2013

CHRISTIAN ELSHOLTZ  and
TERENCE TAO
CHRISTIAN ELSHOLTZ*
Affiliation:
Institut für Mathematik A, Steyrergasse 30/II, Technische Universität Graz, A-8010 Graz, Austria
TERENCE TAO
Affiliation:
Department of Mathematics, UCLA, Los Angeles CA 90095-1555, USA email tao@math.ucla.edu
*
✉elsholtz@math.tugraz.at
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

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

$$\begin{eqnarray*}\frac{4}{n} = \frac{1}{x} + \frac{1}{y} + \frac{1}{z}\end{eqnarray*}$$
with $x, y, z$ positive integers. The Erdős–Straus conjecture asserts that $f(n)\gt 0$ for every $n\geq 2$. In this paper we obtain a number of upper and lower bounds for $f(n)$ or $f(p)$ for typical values of natural numbers $n$ and primes $p$. For instance, we establish that
$$\begin{eqnarray*}N\hspace{0.167em} {\mathop{\log }\nolimits }^{2} N\ll \displaystyle \sum _{p\leq N}f(p)\ll N\hspace{0.167em} {\mathop{\log }\nolimits }^{2} N\log \log N.\end{eqnarray*}$$
 These upper and lower bounds show that a typical prime has a small number of solutions to the Erdős–Straus Diophantine equation; small, when compared with other additive problems, like Waring’s problem.

Keywords

number of solutions of diophantine equationErdős–Straus conjecture

MSC classification

Secondary: 11D68: Rational numbers as sums of fractions 11N37: Asymptotic results on arithmetic functions 11D72: Equations in many variables 11N56: Rate of growth of arithmetic functions
Type
Research Article
Information
Journal of the Australian Mathematical Society , Volume 94 , Issue 1 , February 2013 , pp. 50 - 105
Copyright
Copyright ©2012 Australian Mathematical Publishing Association Inc. 

References

Aigner, A., ‘Brüche als Summe von Stammbrüchen’, J. reine angew. Math. 214/215 (1964), 174–179.CrossRefGoogle Scholar
Barban, M. B. and Vehov, P. P., ‘Summation of multiplicative functions of polynomials’, Mat. Zametki 5 (1969), 669–680.Google Scholar
Bartoš, P. and Pehatzová-Bošanká, K., ‘K Riešeniu Diofantickej Rovnice $1/ x+ 1/ y+ 1/ z= a/ b$’, Časopis pro pěstování matematiky 96 (1971), 294–299.CrossRefGoogle Scholar
Bartoš, P., ‘K Riešitel’nosti Diofantickej Rovnice ${ \mathop{\sum }\nolimits}_{j= 1}^{n} 1/ {x}_{j} = a/ b$’, Časopis pro pěstování matematiky 98 (1973), 261–264.CrossRefGoogle Scholar
Bello-Hernández, M., Benito, M. and Fernández, E., 2012 On egyptian fractions. arXiv:1010.2035.Google Scholar
Bernstein, L., ‘Zur Lösung der diophantischen Gleichung $\frac{m}{n} = \frac{1}{x} + \frac{1}{y} + \frac{1}{z} $, insbesondere im Fall $m= 4$’, J. reine angew. Math. 211 (1962), 1–10.CrossRefGoogle Scholar
de la Bretéche, R. and Browning, T., ‘Sums of arithmetic functions over values of binary forms’, Acta Arith. 125 (2006), 291–304.CrossRefGoogle Scholar
Browning, T. and Elsholtz, C., ‘The number of representations of rationals as a sum of unit fractions’, Illinois J. Math., to appear.Google Scholar
Brüdern, J., Einführung in die analytische Zahlentheorie (Springer, Berlin, Heidelberg, 1995).CrossRefGoogle Scholar
Chen, Y.-G., Elsholtz, C. and Jiang, L.-L., ‘Egyptian fractions with restrictions’, Acta Arith. 154 (2012), 109–123.CrossRefGoogle Scholar
Colliot-Théelène, J.-L. and Sansuc, J.-J., ‘Torseurs sous des groupes de type multiplicatif; applications á l’étude des points rationnels de certaines variétés algébriques’, C. R. Acad. Sci. Paris Sér. A–B 282 (18) (1976), Aii, A1113–A1116.Google Scholar
Croot, E. S., Dobbs, D. E., Friedlander, J. B., Hetzel, A. J. and Pappalardi, F., ‘Binary Egyptian fractions’, J. Number Theory 84 (1) (2000), 63–79.CrossRefGoogle Scholar
Elliott, P. D. T. A., ‘Probabilistic number theory. II’, in: Central Limit Theorems, Grundlehren der Mathematischen Wissenschaften, 240 (Springer, Berlin-New York, 1980).Google Scholar
Elsholtz, C., ‘Sums of $k$ unit fractions’, PhD Thesis, Technische Universität Darmstadt, 1998.Google Scholar
Elsholtz, C., ‘Sums of $k$ unit fractions’, Trans. Amer. Math. Soc. 353 (2001), 3209–3227.CrossRefGoogle Scholar
Elsholtz, C, Heuberger, C. and Prodinger, H., ‘The number of Huffman codes, compact trees, and sums of unit fractions’, IEEE Trans. Inform. Theory., to appear.Google Scholar
Erdős, P., ‘Az $1/ {x}_{1} + 1/ {x}_{2} + \cdots + 1/ {x}_{n} = a/ b$ egyenlet egész számú megoldásairól’, Mat. Lapok 1 (1950), 192–210.Google Scholar
Erdős, P., ‘On the sum ${ \mathop{\sum }\nolimits}_{k= 1}^{x} d(f(k))$’, J. Lond. Math. Soc. 27 (1952), 7–15.Google Scholar
Erdős, P. and Graham, R. L., Old and New Problems and Results in Combinatorial Number Theory, Monographies de L’Enseignement Mathématique, 28 (L’Enseignement Mathématique, Geneva, 1980).Google Scholar
Fouvry, É., ‘Sur le probléme des diviseurs de Titchmarsh’, J. reine angew. Math. 357 (1985), 51–76.Google Scholar
Fouvry, É. and Iwaniec, H., ‘The divisor function over arithmetic progressions’, Acta Arith. 61 (3) (1992), 271–287; With an appendix by Nicholas Katz.CrossRefGoogle Scholar
Gallagher, P. X., ‘Primes and powers of two’, Invent. Math. 29 (1975), 125–142.CrossRefGoogle Scholar
Gupta, H., Selected Topics in Number Theory (Abacus Press, Tunbridge Wells, 1980).Google Scholar
Guy, R., Unsolved Problems in Number Theory, 2nd edn (Springer, New York, 1994), 158–166.CrossRefGoogle Scholar
Halberstam, H. and Richert, H.-E., ‘On a result of R. R. Hall’, J. Number Theory 11 (1) (1979), 76–89.CrossRefGoogle Scholar
Hall, R. R., Sets of Multiples (Cambridge University Press, Cambridge, 1996).CrossRefGoogle Scholar
Heath-Brown, D. R., ‘The density of rational points on Cayley’s cubic surface’, in: Proceedings of the Session in Analytic Number Theory and Diophantine Equations, Bonner Mathematische Schriften, 360 (Univ. Bonn, Bonn, 2003).Google Scholar
Henriot, K., ‘Nair–Tenenbaum bounds uniform with respect to the discriminant’, Math. Proc. Camb. Phil. Soc. 152 (3) (2012), 405–424.CrossRefGoogle Scholar
Hooley, C., ‘On the number of divisors of quadratic polynomials’, Acta Math. 110 (1963), 97–114.CrossRefGoogle Scholar
Huang, J. and Vaughan, R. C., ‘Mean value theorems for binary Egyptian fractions’, J. Number Theory 131 (2011), 1641–1656.CrossRefGoogle Scholar
Huxley, M. N., ‘A note on polynomial congruences’, in: Recent Progress in Analytic Number Theory, Vol. I (eds. Halberstam, H. and Hooley, C.) (Academic Press, London, 1981), 193–196.Google Scholar
Iwaniec, H. and Kowalski, E., Analytic Number Theory, American Mathematical Society Colloquium Publications, 53 (American Mathematical Society, Providence, RI, 2004).Google Scholar
Jia, C., 2011 ‘A note on Terence Tao’s Paper ‘on the number of solutions to $4/ p= 1/ {n}_{1} + 1/ {n}_{2} + 1/ {n}_{3} $”. arXiv:1107.5394.Google Scholar
Jia, C., ‘The estimate for mean values on prime numbers relative to $4/ p= 1/ {n}_{1} + 1/ {n}_{2} + 1/ {n}_{3} $’, Sci. China Math. 55 (3) (2012), 465–474.CrossRefGoogle Scholar
Jollensten, R. W., ‘‘A note on the Egyptian problem’’, in: Congressus Numerantium 17: Proceedings of the Seventh Southeastern Conference on Combinatorics, Graph Theory, and Computing, Louisiana State University, Baton Rouge, LA, 9–12 February 1976 (Utilitas Math., Winnipeg, Man., 1976), 351–364.Google Scholar
Kotsireas, I., ‘The Erdős–Straus conjecture on Egyptian fractions’, in: Paul Erdős and his Mathematics, Budapest, 4–11 July 1999 (János Bolyai Math. Soc., Budapest, 1999), 140–144.Google Scholar
Landreau, B., ‘A new proof of a theorem of van der Corput’, Bull. Lond. Math. Soc. 21 (4) (1989), 366–368.CrossRefGoogle Scholar
Li, D., ‘On the equation $4/ n= 1/ x+ 1/ y+ 1/ z$’, J. Number Theory 13 (1981), 485–494.Google Scholar
Mardjanichvili, C., ‘Estimation d’une somme arithmetique’, Comptes Rendus (Doklady) de l’Académie des Sciences de l’URSS 22 (1939), 387–389.Google Scholar
McKee, J., ‘On the average number of divisors of quadratic polynomials’, Math. Proc. Cambridge Philos. Soc. 117 (3) (1995), 389–392.CrossRefGoogle Scholar
McKee, J., ‘A note on the number of divisors of quadratic polynomials’, in: Sieve methods, exponential sums, and their applications in number theory, Cardiff, 17–21 July 1995, London Mathematical Society Lecture Note Series, 237 (Cambridge University Press, Cambridge, 1997), 275–281.CrossRefGoogle Scholar
McKee, J., ‘The average number of divisors of an irreducible quadratic polynomial’, Math. Proc. Cambridge Philos. Soc. 126 (1) (1999), 17–22.CrossRefGoogle Scholar
Mordell, L. J., Diophantine Equations, Pure and Applied Mathematics, 30 (Academic Press, 1969).Google Scholar
Nagell, T., ‘Généralisation d’un theórème de Tchebycheff’, J. Math. Pures Appl. (9) 8 (1921), 343–356.Google Scholar
Nair, M., ‘Multiplicative functions of polynomial values in short intervals’, Acta Arith. 62 (3) (1992), 257–269.CrossRefGoogle Scholar
Nair, M. and Tenenbaum, G., ‘Short sums of certain arithmetic functions’, Acta Math. 180 (1998), 119–144.CrossRefGoogle Scholar
Nakayama, M., ‘On the decomposition of a rational number into ‘Stammbrüche’’, Tôhoku Math. J. 46 (1939), 1–21.Google Scholar
Obláth, M. R., ‘Sur l’ équation diophantienne $4/ n= 1/ {x}_{1} + 1/ {x}_{2} + 1/ {x}_{3} $’, Mathesis 59 (1950), 308–316.Google Scholar
Ore, O., ‘Anzahl der Wurzeln höherer Kongruenzen’, in: Norsk Matematisk Tidsskrift, 3 Aagang (Kristiana, 1921), 63–66.Google Scholar
Palamà, G., ‘Su di una congettura di Sierpiński relativa alla possibilità in numeri naturali della $5/ n= 1/ {x}_{1} + 1/ {x}_{2} + 1/ {x}_{3} $’, Boll. Unione Mat. Ital. (3) 13 (1958), 65–72.Google Scholar
Palamà, G., ‘Su di una congettura di Schinzel’, Boll. Unione Mat. Ital. (3) 14 (1959), 82–94.Google Scholar
Pomerance, C., ‘Analysis and comparison of some integer factoring algorithms’, in: Computational Methods in Number Theory, Part I, Math. Centre Tract, 154 (eds. Lenstra, H. W. Jr. and Tijdeman, R.) (Math. Centrum, Amsterdam, 1982), 89–139.Google Scholar
Pomerance, C., ‘Ruth–Aaron numbers revisited’, in: Paul Erdős and his Mathematics, I Budapest, 4–11 July 1999, Bolyai Society Mathematical Studies, 11 (János Bolyai Math. Soc., Budapest, 2002), 567–579.Google Scholar
Popovici, C. P., ‘On the diophantine equation $a/ b= 1/ {x}_{1} + 1/ {x}_{2} + 1/ {x}_{3} $’, Analele Universitătii Bucureṣti. Seria Ṣtiinṭele Naturii. Matematică-Fizikă 10 (1961), 29–44.Google Scholar
Ramanujan, S., ‘Highly composite numbers’, Proc. Lond. Math. Soc. 14 (1915), 347–409.CrossRefGoogle Scholar
Rav, Y., ‘On the representation of rational numbers as a sum of a fixed number of unit fractions’, J. reine angew. Math. 222 (1966), 207–213.Google Scholar
Rosati, L., ‘Sull’equazione diofantea $4/ n= 1/ {x}_{1} + 1/ {x}_{2} + 1/ {x}_{3} $’, Boll. Unione. Mat. Ital. 9 (3) (1954), 59–63.Google Scholar
Rosser, J. and Schoenfeld, L., ‘Approximate formulas for some functions of prime numbers’, Illinois J. Math. 6 (1962), 64–94.CrossRefGoogle Scholar
Ruzsa, I. Z., ‘On an additive property of squares and primes’, Acta Arithmetica 49 (1988), 281–289.CrossRefGoogle Scholar
Sander, J. W., ‘On $4/ n= 1/ x+ 1/ y+ 1/ z$ and Rosser’s sieve’, Acta Arithmetica 59 (1991), 183–204.CrossRefGoogle Scholar
Sander, J. W., ‘On $4/ n= 1/ x+ 1/ y+ 1/ z$ and Iwaniec’ Half Dimensional Sieve’, J. Number Theory 46 (1994), 123–136.CrossRefGoogle Scholar
Sander, J. W., ‘Egyptian fractions and the Erdős–Straus conjecture’, Nieuw Arch. Wiskd. (4) 15 (1997), 43–50.Google Scholar
Sándor, G., ‘Über die Anzahl der Lösungen einer Kongruenz’, Acta. Math. 87 (1952), 13–17.CrossRefGoogle Scholar
Sándor, C., ‘On the number of solutions of the Diophantine equation ${ \mathop{\sum }\nolimits}_{i= 1}^{n} \frac{1}{{x}_{i} } = 1$’, Period. Math. Hungar. 47 (1–2) (2003), 215–219.CrossRefGoogle Scholar
Schinzel, A., ‘Sur quelques propriétés des nombres $3/ n$ et $4/ n$, où $n$ est un nombre impair’, Mathesis 65 (1956), 219–222.Google Scholar
Schinzel, A., ‘On sums of three unit fractions with polynomial denominators’, Funct. Approx. Comment. Math. 28 (2000), 187–194.CrossRefGoogle Scholar
Schwarz, W. and Spilker, J., Arithmetical Functions, London Mathematical Society Lecture Note Series, 184 (Cambridge University Press, Cambridge, 1994).CrossRefGoogle Scholar
Scourfield, E. J., ‘The divisors of a quadratic polynomial’, Proc. Glasgow Math. Assoc. 5 (1961), 8–20.CrossRefGoogle Scholar
Shen, Z., ‘On the diophantine equation ${ \mathop{\sum }\nolimits}_{i= 0}^{k} 1/ {x}_{i} = a/ n$’, Chinese Ann. Math. Ser. B 7 (1986), 213–220.Google Scholar
Shiu, P., ‘A Brun–Titchmarsh theorem for multiplicative functions’, J. reine angew. Math. 313 (1980), 161–170.Google Scholar
Sierpiński, W., ‘Sur les décompositions de nombres rationnels en fractions primaires’, Mathesis 65 (1956), 16–32.Google Scholar
Sierpiński, W., ‘On the decomposition of rational numbers into unit fractions’, Monografie Popularnonaukow Matematyka (Pánstwowe Wydawnictwo Naukowe, Warsaw, 1957).Google Scholar
Sós, E., ‘Die diophantische Gleichung $1/ x= 1/ {x}_{1} + 1/ {x}_{2} + \cdots + 1/ {x}_{n} $’, Zeitschrift für Mathematischen und Naturwissenschaftlichen Unterricht 36 (1905), 97–102.Google Scholar
Stewart, B. M., Theory of Numbers, 2nd edn (The Macmillan Company, New York, 1964), London: Collier-Macmillan.Google Scholar
Stewart, C. L., ‘On the number of solutions of polynomial congruences and Thue equations’, J. Amer. Math. Soc. 4 (4) (1991), 793–835.CrossRefGoogle Scholar
Swett, A., http://math.uindy.edu/swett/esc.htm accessed on 27 July 2011.Google Scholar
Tenenbaum, G., Introduction to Analytic and Probabilistic Number Theory, Cambridge Studies in Advanced Mathematics, 46 (Cambridge University Press, Cambridge, 1995).Google Scholar
Terzi, D. G., ‘On a conjecture by Erdős–Straus’, Nordisk Tidskr. Informations-Behandling (BIT) 11 (1971), 212–216.Google Scholar
Vaughan, R., ‘On a problem of Erdős, Straus and Schinzel’, Mathematika 17 (1970), 193–198.CrossRefGoogle Scholar
Viola, C., ‘On the diophantine equations ${ \mathop{\prod }\nolimits}_{0}^{k} {x}_{i} - { \mathop{\sum }\nolimits}_{0}^{k} {x}_{i} = n$ and ${ \mathop{\sum }\nolimits}_{0}^{k} 1/ {x}_{i} = a/ n$’, Acta Arith. 22 (1973), 339–352.CrossRefGoogle Scholar
Webb, W., ‘On $4/ n= 1/ x+ 1/ y+ 1/ z$’, Proc. Amer. Math. Soc. 25 (1970), 578–584.Google Scholar
Webb, W., ‘On a theorem of Rav concerning Egyptian fractions’, Canad. Math. Bull. 18 (1) (1975), 155–156.CrossRefGoogle Scholar
Webb, W., ‘On the Diophantine equation $k/ n= {a}_{1} / {x}_{1} + {a}_{2} / {x}_{2} + {a}_{3} / {x}_{3} $’, Časopis pro pěstováni matematiky, roč 101 (1976), 360–365.CrossRefGoogle Scholar
Wintner, A., Eratosthenian Averages (Waverly Press, Baltimore, Md, 1943).Google Scholar
Yamamoto, K., ‘On the Diophantine Equation $4/ n= 1/ x+ 1/ y+ 1/ z$’, Mem Fac. Sci. Kyushu Univ. Ser. A, V. 19 (1965), 37–47.Google Scholar
Yang, X. Q., ‘A note on $4/ n= 1/ x+ 1/ y+ 1/ z$’, Proc. Amer. Math. Soc. 85 (1982), 496–498.Google Scholar