Some problems of Erdős on the sum-of-divisors function

Pollack, Paul; Pomerance, Carl

doi:10.1090/btran/10

Some problems of Erdős on the sum-of-divisors function
HTML articles powered by AMS MathViewer

by Paul Pollack and Carl Pomerance;

Trans. Amer. Math. Soc. Ser. B 3 (2016), 1-26

DOI: https://doi.org/10.1090/btran/10

Published electronically: April 5, 2016

HTML | PDF

Abstract:

Let $\sigma (n)$ denote the sum of all of the positive divisors of $n$, and let $s(n) = \sigma (n)-n$ denote the sum of the proper divisors of $n$. The functions $\sigma (\cdot )$ and $s(\cdot )$ were favorite subjects of investigation by the late Paul Erdős. Here we revisit three themes from Erdős’s work on these functions. First, we improve the upper and lower bounds for the counting function of numbers $n$ with $n$ deficient but $s(n)$ abundant, or vice versa. Second, we describe a heuristic argument suggesting the precise asymptotic density of $n$ not in the range of the function $s(\cdot )$; these are the so-called nonaliquot numbers. Finally, we prove new results on the distribution of friendly $k$-sets, where a friendly $k$-set is a collection of $k$ distinct integers which share the same value of $\frac {\sigma (n)}{n}$.

References

J. D. Alanen, Empirical study of aliquot sequences, Ph.D. thesis, Yale University, 1972.
Aria Anavi, Paul Pollack, and Carl Pomerance, On congruences of the form $\sigma (n)\equiv a\pmod n$, Int. J. Number Theory 9 (2013), no. 1, 115–124. MR 2997493, DOI 10.1142/S1793042112501266
Michael R. Avidon, On the distribution of primitive abundant numbers, Acta Arith. 77 (1996), no. 2, 195–205. MR 1411032, DOI 10.4064/aa-77-2-195-205
R. C. Baker and G. Harman, Shifted primes without large prime factors, Acta Arith. 83 (1998), no. 4, 331–361. MR 1610553, DOI 10.4064/aa-83-4-331-361
William D. Banks and Florian Luca, Nonaliquots and Robbins numbers, Colloq. Math. 103 (2005), no. 1, 27–32. MR 2148946, DOI 10.4064/cm103-1-4
W. Bosma, Aliquot sequences with small starting values, preprint available from http://www.math.ru.nl/~bosma/.
Wieb Bosma and Ben Kane, The aliquot constant, Q. J. Math. 63 (2012), no. 2, 309–323. MR 2925292, DOI 10.1093/qmath/haq050
E. Catalan, Propositions et questions diverses, Bull. Soc. Math. France 16 (1888), 128–129 (French). MR 1504036, DOI 10.24033/bsmf.366
Yong-Gao Chen and Qing-Qing Zhao, Nonaliquot numbers, Publ. Math. Debrecen 78 (2011), no. 2, 439–442. MR 2796778, DOI 10.5486/PMD.2011.4820
N. G. de Bruijn, On the number of positive integers $\leq x$ and free of prime factors $>y$, Nederl. Akad. Wetensch. Proc. Ser. A 54 (1951), 50–60. MR 46375
N. G. de Bruijn, On the number of positive integers $\leq x$ and free prime factors $>y$. II, Indag. Math. 28 (1966), 239–247. Nederl. Akad. Wetensch. Proc. Ser. A 69. MR 205945, DOI 10.1016/S1385-7258(66)50029-4
L. E. Dickson, Theorems and tables on the sum of the divisors of a number, Q. J. Math. 44 (1913), 264–296.
P. Erdős, On primitive abundant numbers, J. London Math. Soc. 10 (1935), 49–58.
P. Erdős, On the normal number of prime factors of $p-1$ and some related problems concerning Euler’s $\varphi$-function, Q. J. Math., Oxford Ser. 6 (1935), 205–213.
P. Erdös, On amicable numbers, Publ. Math. Debrecen 4 (1955), 108–111. MR 69198, DOI 10.5486/pmd.1955.4.1-2.16
P. Erdös, On perfect and multiply perfect numbers, Ann. Mat. Pura Appl. (4) 42 (1956), 253–258. MR 82516, DOI 10.1007/BF02411879
P. Erdős, Remarks on number theory. II. Some problems on the $\sigma$ function, Acta Arith. 5 (1959), 171–177. MR 107623, DOI 10.4064/aa-5-2-171-177
P. Erdős, Über die Zahlen der Form $\sigma (n)-n$ und $n-\varphi (n)$, Elem. Math. 28 (1973), 83–86.
P. Erdős, On the distribution of numbers of the form $\sigma (n)/n$ and on some related questions, Pacific J. Math. 52 (1974), 59–65. MR 354601, DOI 10.2140/pjm.1974.52.59
P. Erdős, On asymptotic properties of aliquot sequences, Math. Comp. 30 (1976), no. 135, 641–645. MR 404115, DOI 10.1090/S0025-5718-1976-0404115-8
P. Erdős and G. J. Rieger, Ein Nachtrag über befreundete Zahlen, J. Reine Angew. Math. 273 (1975), 220 (German). MR 364157
P. Erdős, A. Granville, C. Pomerance, and C. Spiro, On the normal behavior of the iterates of some arithmetic functions, Analytic number theory (Allerton Park, IL, 1989) Progr. Math., vol. 85, Birkhäuser Boston, Boston, MA, 1990, pp. 165–204. MR 1084181, DOI 10.1007/978-1-4612-3464-7_{1}3
Paul Erdős, Florian Luca, and Carl Pomerance, On the proportion of numbers coprime to a given integer, Anatomy of integers, CRM Proc. Lecture Notes, vol. 46, Amer. Math. Soc., Providence, RI, 2008, pp. 47–64. MR 2437964, DOI 10.1090/crmp/046/03
Kevin Ford, Florian Luca, and Carl Pomerance, Common values of the arithmetic functions $\phi$ and $\sigma$, Bull. Lond. Math. Soc. 42 (2010), no. 3, 478–488. MR 2651943, DOI 10.1112/blms/bdq014
Richard K. Guy and J. L. Selfridge, What drives an aliquot sequence?, Math. Comput. 29 (1975), 101–107. MR 384669, DOI 10.1090/S0025-5718-1975-0384669-X
H. Halberstam and H.-E. Richert, Sieve methods, London Mathematical Society Monographs, No. 4, Academic Press [Harcourt Brace Jovanovich, Publishers], London-New York, 1974. MR 424730
Bernhard Hornfeck and Eduard Wirsing, Über die Häufigkeit vollkommener Zahlen, Math. Ann. 133 (1957), 431–438 (German). MR 90600, DOI 10.1007/BF01343756
Mitsuo Kobayashi, Paul Pollack, and Carl Pomerance, On the distribution of sociable numbers, J. Number Theory 129 (2009), no. 8, 1990–2009. MR 2522719, DOI 10.1016/j.jnt.2008.10.011
H. W. Lenstra, Jr., Problem 6064, Amer. Math. Monthly 82 (1975), 1016. Solution by the proposer, op. cit. 84 (1977), 580.
Florian Luca and Carl Pomerance, The range of the sum-of-proper-divisors function, Acta Arith. 168 (2015), no. 2, 187–199. MR 3339454, DOI 10.4064/aa168-2-6
Tomás Oliveira e Silva, Siegfried Herzog, and Silvio Pardi, Empirical verification of the even Goldbach conjecture and computation of prime gaps up to $4\cdot 10^{18}$, Math. Comp. 83 (2014), no. 288, 2033–2060. MR 3194140, DOI 10.1090/S0025-5718-2013-02787-1
Paul Pollack, On the greatest common divisor of a number and its sum of divisors, Michigan Math. J. 60 (2011), no. 1, 199–214. MR 2785871, DOI 10.1307/mmj/1301586311
Paul Pollack, Some arithmetic properties of the sum of proper divisors and the sum of prime divisors, Illinois J. Math. 58 (2014), no. 1, 125–147. MR 3331844
Paul Pollack, Remarks on fibers of the sum-of-divisors function, in Analytic number theory (in honor of Helmut Maier’s 60th birthday), M. Rassias and C. Pomerance, eds., Springer, Cham, Switzerland, 2015, pp. 305–320.
Paul Pollack and Carl Pomerance, Prime-perfect numbers, Integers 12 (2012), no. 6, 1417–1437. MR 3011565, DOI 10.1515/integers-2012-0044
Carl Pomerance, On the distribution of amicable numbers, J. Reine Angew. Math. 293(294) (1977), 217–222. MR 447087, DOI 10.1515/crll.1977.293-294.217
Carl Pomerance, Popular values of Euler’s function, Mathematika 27 (1980), no. 1, 84–89. MR 581999, DOI 10.1112/S0025579300009967
Carl Pomerance, On amicable numbers, in Analytic number theory (in honor of Helmut Maier’s 60th birthday), M. Rassias and C. Pomerance, eds., Springer, Cham, Switzerland, 2015, pp. 321–327.
Carl Pomerance and Hee-Sung Yang, Variant of a theorem of Erdős on the sum-of-proper-divisors function, Math. Comp. 83 (2014), no. 288, 1903–1913. MR 3194134, DOI 10.1090/S0025-5718-2013-02775-5
G. J. Rieger, Bemerkung zu einem Ergebnis von Erdős über befreundete Zahlen, J. Reine Angew. Math. 261 (1973), 157–163 (German). MR 319882, DOI 10.1515/crll.1973.261.157
J. Sesiano, Two problems of number theory in Islamic times, Arch. Hist. Exact Sci. 41 (1991), no. 3, 235–238. MR 1107382, DOI 10.1007/BF00348408
N. J. A. Sloane, On-line encyclopedia of integer sequences, http://oeis.org. Sequence A001970; gp script by Michael Marcus online at http://oeis.org/A246827/ a246827.gp.txt.
Gérald Tenenbaum, Introduction to analytic and probabilistic number theory, Cambridge Studies in Advanced Mathematics, vol. 46, Cambridge University Press, Cambridge, 1995. Translated from the second French edition (1995) by C. B. Thomas. MR 1342300
H. J. J. te Riele, A theoretical and computational study of generalized aliquot sequences, Mathematical Centre Tracts, No. 74, Mathematisch Centrum, Amsterdam, 1976. MR 556033
Vincent Toulmonde, Module de continuité de la fonction de répartition de $\phi (n)/n$, Acta Arith. 121 (2006), no. 4, 367–402 (French). MR 2224402, DOI 10.4064/aa121-4-6
R. C. Vaughan, The Hardy-Littlewood method, 2nd ed., Cambridge Tracts in Mathematics, vol. 125, Cambridge University Press, Cambridge, 1997. MR 1435742, DOI 10.1017/CBO9780511470929
Eduard Wirsing, Bemerkung zu der Arbeit über vollkommene Zahlen, Math. Ann. 137 (1959), 316–318 (German). MR 104636, DOI 10.1007/BF01360967