Sums of integers with many divisors at the sharp threshold: pairwise-coprime summands and asymptotic representation counts (Erdős-Montgomery, 1999)

A 1999 paper of Erdős and Montgomery determined the sharp threshold for representing every large integer $n$ as a sum $n=m_1+\cdots+m_k$ of $k$ integers each having many divisors: for every fixed $k\ge2$ and every $\alpha<1-1/k$, one can guarantee $d(m_i)>D(n)^\alpha$ for every summand, where $d$ is the divisor function and $D(x)=\exp((\log 2)(\log x)/\log\log x)$ is its maximal-order scale, while for $\alpha>1-1/k$ infinitely many $n$ admit no such representation. The paper leaves open: (A) whether, for $k\ge3$, the summands can additionally be required to be pairwise coprime - the paper's construction achieves only $\gcd(m_1,\ldots,m_k)=1$, and for $k=2$ the two conditions coincide; (B) an asymptotic formula for the number of such representations, where the circle method applies only for sufficiently small $\alpha$ and the intermediate range up to the threshold is open; and (C) a secondary small-prime refinement of the counting law $\mathrm{card}\{m\le x: d(m)>D(x)^\alpha\}=x^{1-\alpha+o(1)}$ on which the threshold argument rests. Of these, (A) and (B) are the substantive core of the problem.

Background

For a positive integer $m$, let $d(m)$ denote the number of positive divisors of $m$ (the divisor function). A classical theorem of Wigert (1907) determines the maximal order of $d$: $\limsup_{m\to\infty}\log d(m)\,\log\log m/\log m=\log 2$, so the most divisor-rich integers up to $x$ have about $D(x)=\exp((\log 2)(\log x)/\log\log x)$ divisors, and $D(x)$ is the natural scale on which to measure how many divisors a number near $x$ can have. Erdős and Montgomery (1999) studied an additive counterpart of this multiplicative extremal question, a question the authors attribute to F. Göbel: if a large integer $n$ is written as a sum of $k$ positive integers, $n=m_1+\cdots+m_k$, how large can the least divisor count $\min_i d(m_i)$ be guaranteed to be? Measuring against the maximal-order scale, one fixes $0\le\alpha<1$ and asks when every sufficiently large $n$ admits such a representation with $d(m_i)>D(n)^\alpha$ for all $i$. Their answer is sharp in $\alpha$: for every fixed $k\ge2$ and every $\alpha<1-1/k$, every sufficiently large $n$ is representable, while for $\alpha>1-1/k$ infinitely many $n$ are not. (In the paper's own formulation, $d(m_i)>n^{(\log 2-\varepsilon)(1-1/k)/\log\log n}$ for any $\varepsilon>0$, and the constant $\log 2$ cannot be increased; the two formulations are equivalent since $\log D(n)=(\log 2)(\log n)/\log\log n$.) Both halves rest on the supply-side counting law $\mathrm{card}\{m\le x: d(m)>D(x)^\alpha\}=x^{1-\alpha+o(1)}$, uniform in $0\le\alpha\le1$ (where $o(1)$ denotes a quantity tending to $0$): the eligible summands form a set of density $x^{-\alpha+o(1)}$, so the expected size of the $k$-fold sumset (the set of all sums of $k$ eligible integers) is $x^{k(1-\alpha)+o(1)}$, which first reaches all integers exactly at the threshold $k(1-\alpha)=1$. The existence half is proved by explicit construction: each summand is built to contain a large block of consecutive small primes (which forces many divisors), and the blocks are positioned so that suitable multiples can be combined to sum to $n$ via the Chinese remainder theorem (the solvability of simultaneous congruences modulo pairwise coprime moduli). Two features of this construction drive the open questions. First, the summands are designed around large shared factors; the authors achieve only that the summands have no common factor all together ($\gcd(m_1,\ldots,m_k)=1$), not that they are pairwise coprime ($\gcd(m_i,m_j)=1$ for $i\ne j$) - and for $k=2$ the two conditions coincide, so the gap concerns $k\ge3$. Second, the theorem is one of existence, not of counting: the circle method (the Hardy-Littlewood technique that converts the counting of additive representations into analysis of the associated generating function on the unit circle) would yield an asymptotic formula for the number of representations, but as the authors note it applies only when $\alpha$ is sufficiently small depending on $k$, and they see no hope of reaching the full range $\alpha<1-1/k$. Finally, the obstruction half of the counting law is obtained from a moment estimate for $d(m)^\beta$ proved by comparing Dirichlet-series coefficients coefficient by coefficient, a comparison that is sharp only at large primes; the authors indicate that for small primes a Poisson-summation identity (an exact series/integral identity permitting estimation of such sums by integral means) gives better bounds, a refinement they left unworked.

Problem Statement

Throughout, $d(m)$ is the number of positive divisors of $m$, $D(x)=\exp((\log 2)(\log x)/\log\log x)$ is the maximal-order scale of the divisor function, $k\ge2$ is a fixed integer, and $\alpha$ is a fixed real parameter. Call a representation $n=m_1+\cdots+m_k$ of a positive integer $n$ by positive integers admissible at level $\alpha$ if $d(m_i)>D(n)^\alpha$ for every $i$. Erdős and Montgomery proved that for every fixed $k\ge2$ and every $\alpha<1-1/k$, every sufficiently large $n$ has an admissible representation; that the range $\alpha<1-1/k$ is best possible (for $\alpha>1-1/k$, infinitely many $n$ have no admissible representation); and that the summands can additionally be required to satisfy $\gcd(m_1,\ldots,m_k)=1$. The open questions:

(A) Pairwise-coprime summands. For fixed $k\ge3$ and fixed $\alpha<1-1/k$, is every sufficiently large $n$ representable as $n=m_1+\cdots+m_k$ with $d(m_i)>D(n)^\alpha$ for all $i$ and $\gcd(m_i,m_j)=1$ for all $i\ne j$? (For $k=2$ this is exactly the proven gcd-one statement; the question is open for every $k\ge3$.)

(B) Asymptotic enumeration. For fixed $k\ge2$ and $\alpha<1-1/k$, let $r_{k,\alpha}(n)$ denote the number of admissible representations of $n$ at level $\alpha$. Obtain an asymptotic formula for $r_{k,\alpha}(n)$ as $n\to\infty$ - an explicit main term, possibly depending on $n$ through local congruence densities, valid for all sufficiently large $n$, in the standard sense of Waring-type problems; in particular, determine, as a function of $k$, the largest range of $\alpha$ below the threshold $1-1/k$ in which such a formula holds. (The circle method is expected to handle sufficiently small $\alpha$; the intermediate range is open, and the authors state there appears to be no hope at the full range.)

(C) Small-prime refinement of the counting law. The counting law $\mathrm{card}\{m\le x: d(m)>D(x)^\alpha\}=x^{1-\alpha+o(1)}$ is obtained by a coefficientwise comparison that loses precision at small primes. Can the counting law, or its uniformity in $\alpha$, be sharpened quantitatively at small primes?

Equivalently, (A) asks for a positive construction for all $k\ge3$ and all $\alpha<1-1/k$, or a disproof, and (B) asks for an asymptotic formula for $r_{k,\alpha}(n)$ valid for all sufficiently large $n$ throughout the largest range $\alpha<\alpha_0(k)$ below the threshold $1-1/k$, with $\alpha_0(k)$ identified as a function of $k$.

References

1. Paul Erdős and Hugh L. Montgomery, 'Sums of Numbers with Many Divisors', Journal of Number Theory 75(1) (1999) 1-6. DOI: 10.1006/jnth.1998.2323, https://doi.org/10.1006/jnth.1998.2323.
2. Peter Shiu, review of 'Sums of Numbers with Many Divisors' by P. Erdős and H. L. Montgomery, zbMATH Open, Zbl 0922.11075 (1999), https://zbmath.org/?q=an%3A0922.11075.
3. Richard K. Guy, 'Divisibility', in Unsolved Problems in Number Theory, 3rd edition, Problem Books in Mathematics, Springer, New York (2004), pp. 71-158. DOI: 10.1007/978-0-387-26677-0_3, https://doi.org/10.1007/978-0-387-26677-0_3.
4. S. Wigert, 'Sur l'ordre de grandeur du nombre des diviseurs d'un entier', Arkiv för Matematik, Astronomi och Fysik 3, No. 18 (1907), 9 pp. JFM 38.0249.01, https://zbmath.org/?q=an%3A38.0249.01.
5. Andreas Weingartner, 'Practical numbers and the distribution of divisors', The Quarterly Journal of Mathematics 66(2) (2015) 743-758. DOI: 10.1093/qmath/hav006, https://doi.org/10.1093/qmath/hav006.
6. Carl Pomerance and Andreas Weingartner, 'On primes and practical numbers', The Ramanujan Journal 57(3) (2022) 981-1000. DOI: 10.1007/s11139-020-00354-y, https://doi.org/10.1007/s11139-020-00354-y.