On a theorem of Erdős and Loxton

Noah Lebowitz-Lockard · 2025

Read On a theorem of Erdős and Loxton by Noah Lebowitz-Lockard (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-03446.txt.

Introduction

Noah Lebowitz-Lockard revisits a theorem of Erdos and Loxton on a special kind of number partition, in a 2025 note. The partitions counted are chains where each term is a proper divisor of the one before. Erdos and Loxton showed the total count up to a bound grows like a constant times a power of that bound.

The power is about 1.73, the unique value where a known zeta equation holds. Lebowitz-Lockard gives tight bounds on the constant, though no exact formula is found. He also writes an explicit upper bound for the count at a single value. The note sharpens a classic counting result.

Catalog record

CREATORNoah Lebowitz-Lockard
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE15 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2504-03446

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

On a theorem of Erdős and Loxton Noah Lebowitz-Lockard Abstract Let a ⁡ ( n ) a(n) be the number of partitions of n n of the form a 1 + a 2 + ⋯ + a k a_{1}+a_{2}+\cdots+a_{k} where a i + 1 a_{i+1} is a proper divisor of a i a_{i} for all i < k i<k . Erdős and Loxton showed that the sum of a ⁡ ( n ) a(n) over all n ≤ x n\leq x is asymptotic to a constant multiple of x ρ x^{\rho} where s = ρ ≈ 1.73 s=\rho\approx 1.73 is the unique solution to the equation ζ ⁡ ( s ) = 2 \zeta(s)=2 satisfying s > 1 s>1 . In this note, we provide tight bounds on the value of this constant, though we do not find an exact formula for it. In addition, we write an explicit upper bound for a ⁡ ( n ) a(n) . 1 Introduction In this paper we consider partitions with a specific factorization-related property. We let a(n) be the number of partitions of n into distinct parts in which every part is a multiple of the next part. For example, a(10)=4 because we have 10=9+1=8+2=6+3+1. We also define A(x) as the sum \sum_{n\leq x}a(n). It is straightforward to show that these factorizations are closely related to the number of ways one can express a number as a product of numbers greater than 1 . Though we discuss this correspondence in more detail later on, we write a few results about these products here. Definition . Let g(n) be the number of ways to express the number n as an ordered product of integers greater than 1 (with g(1)=1 for notational convenience). From here on, we refer to these products as factorizations of n . (They are also called “multiplicative partitions” in the literature.) We also let G(x) be the sum of g(n) over all n\leq x . In 1931, Kalmár [ 14 ] found an asymptotic formula for G(x) . Theorem 1 . As x\to\infty , we have G(x)\sim-\frac{1}{\rho\zeta^{\prime}(\rho)}x^{\rho}, where s=\rho\approx 1.73 is the unique real solution to the equation \zeta(s)=2 with s>1 . (Here, \zeta is the Riemann zeta function. Note that \zeta^{\prime}(\rho) is negative, cancelling out the negative sign in front.) One may also prove this result by applying the Wiener-Ikehara Theorem [ 19 , Thm. 7.1] to the Dirichlet series of g(n) . Ikehara [ 13 ] refined the error term and Hwang [ 12 ] later proved that G(x)=-\frac{1}{\rho\zeta^{\prime}(\rho)}x^{\rho}+O(x^{\rho}\exp(-c(\log\log x)^{(3/2)-\epsilon})), where \epsilon can be any positive number and c:=c(\epsilon) is a positive constant. (For the corresponding sum for unordered factorizations, see [ 18 ] .) Erdős and Loxton [ 7 , Thm. 2 ] proved the following result about A(x) . Theorem 2 . Define \rho as we did in the asymptotic formula for G(x) . Then there exists a positive constant c such that A(x)\sim cx^{\rho}. In addition, there does not exist a positive number \epsilon for which A(x)=cx^{\rho}+O(x^{\rho-\epsilon}) . Though Erdős and Loxton proved this result, they do not provide any bounds on c . In this paper we prove the following inequality on c . Theorem 3 . For every positive integer k , the value of c lies between -\frac{2}{\rho\zeta^{\prime}(\rho)}\sum_{d_{1},d_{2},\ldots,d_{k}>1}\frac{1}{(2+d_{1}+d_{1}d_{2}+\cdots+(d_{1}d_{2}\cdots d_{k}))^{\rho}} and -\frac{2}{\rho\zeta^{\prime}(\rho)}\sum_{d_{1},d_{2},\ldots,d_{k}>1}\frac{1}{(1+d_{1}+d_{1}d_{2}+\cdots+(d_{1}d_{2}\cdots d_{k}))^{\rho}}. In order to show that these sums converge, we note that \displaystyle\sum_{d_{1},d_{2},\ldots,d_{k}>1}\frac{1}{(1+d_{1}+d_{1}d_{2}+\cdots+(d_{1}d_{2}\cdots d_{k}))^{\rho}} \displaystyle< \displaystyle\sum_{d_{1},d_{2},\ldots,d_{k}>1}\frac{1}{(d_{1}d_{2}\cdots d_{k})^{\rho}} \displaystyle= \displaystyle\left(\sum_{d=2}^{\infty}\frac{1}{d^{\rho}}\right)^{k} \displaystyle= \displaystyle(\zeta(\rho)-1)^{k} \displaystyle= \displaystyle 1^{k} \displaystyle= \displaystyle 1. We may also observe that as k increases the upper and lower bounds on c get closer together. Because d_{i}>1 for all i , we have d_{1}d_{2}\cdots d_{k}\geq 2^{k} for all tuples (d_{1},d_{2},\ldots,d_{k}) . Therefore, \frac{(2+d_{1}+d_{1}d_{2}+\cdots+(d_{1}d_{2}\cdots d_{k}))^{\rho}}{(1+d_{1}+d_{1}d_{2}+\cdots+(d_{1}d_{2}\cdots d_{k}))^{\rho}}<\left(1+\frac{1}{2^{k}}\right)^{\rho} for any such tuple. The ratio between the upper and lower sums is also at most (1+2^{-k})^{\rho} . If we take the limit as k\to\infty , then we obtain an expression for c . Corollary 4 . We have c=-\frac{2}{\rho\zeta^{\prime}(\rho)}\lim_{k\to\infty}\sum_{d_{1},d_{2},\ldots,d_{k}>1}\frac{1}{(d_{1}+d_{1}d_{2}+\cdots+(d_{1}d_{2}\cdots d_{k}))^{\rho}}. The sums in Theorem 3 have closed forms in the k=1 case, namely -\frac{2(1-2^{-\rho}-3^{-\rho})}{\rho\zeta^{\prime}(\rho)}\leq c\leq-\frac{2(1-2^{-\rho})}{\rho\zeta^{\prime}(\rho)}. Unfortunately, I have been unable to obtain good numerical bounds on c . The previous inequality only gives us c\in[0.349,0.444] . If we remove the restriction that the parts have to be distinct, we obtain a completely different result. Theorem 5 ( [ 7 , Thm. 3 ] ) . Let f(n) be the number of partitions of n of the form a_{1}+a_{2}+\cdots+a_{k} with a_{i+1}|a_{i} for all i<k , where the a_{i} ’s are not necessarily distinct. Then, \displaystyle\log f(n)= \displaystyle\frac{1}{2\log 2}(\log n-\log\log n)^{2}+\left(\frac{1}{2}+\frac{1+\log\log 2}{\log 2}\right)\log n-\left(1+\frac{\log\log 2}{\log 2}\right)\log\log n \displaystyle+V\left(\frac{1}{\log 2}(\log n-\log\log n)\right)+o(1), where V(t) is a periodic function with period 1 . de Bruijn [ 1 ] had previously proved this result holds for binary partitions, i.e., partitions into powers of 2 , though he did not have the same periodic function V(x) . (Mahler [ 16 ] had previously obtained a weaker asymptotic.) In the next section, we prove Theorem 3 and in Section 3 we discuss some possibilities for future research. 2 The proof Before proving our main result, we write a short argument relating A(x) to G(x) . From here on, we let b(n) be the number of partitions of n counted by a(n) with the additional restriction that the last part is not 1 . Note that the number of partitions in which the smallest part is 1 is simply b(n-1) as we can simply remove the 1 from our partition to obtain a partition of n-1 into distinct parts in which every part is a multiple of the next part and the smallest part is not 1 . Therefore, a(n)=b(n)+b(n-1) . If we let B(x) be the sum of b(n) over all n\leq x , then we have A(x)=B(x)+B(x-1) , which is asymptotic to 2B(x) . From here on, we consider B(x) for notational convenience. Consider the following map between partitions and factorizations. Let a_{1}+a_{2}+\cdots+a_{k} be factorization of n with a_{k}>1 . As usual, we suppose that a_{i} is a multiple of a_{i+1} for all i<k . Then (a_{1}/a_{2})(a_{2}/a_{3})\cdots(a_{k-1}/a_{k})(a_{k}) is a factorization of a_{1} . Note that this map is bijective. The inverse maps the factorization d_{1}d_{2}\cdots d_{\ell} to the partition (d_{1}d_{2}\cdots d_{\ell})+(d_{2}d_{3}\cdots d_{\ell})+\cdots+d_{\ell} . Using this map, we can bound B(n) . Proposition 6 . For all x , we have G(x/2)\leq B(x)\leq G(x) . Proof. Let a_{1}+a_{2}+\cdots+a_{k} be a partition of some n\leq x . Then, a_{1}\leq n\leq x . Applying our map turns this partition into a factorization of a_{1}\leq n\leq x . Therefore, B(x)\leq G(x) . Likewise, suppose that a_{1}+a_{2}+\cdots+a_{k} is a partition with a_{1}\leq x/2 . Because a_{i+1} is a proper divisor of a_{i} , we have a_{i+1}\leq a_{i}/2 , giving us a_{1}+a_{2}+\cdots+a_{k}\leq a_{1}+(a_{1}/2)+\cdots+(a_{1}/2^{k-1})<2a_{1}\leq x. So, every partition in which the first number is \leq x/2 corresponds to a factorization of some number <x . Hence, B(x)\geq G(x/2) . ∎ Using the asymptotic formula for G(x) , we can bound c . We have -\frac{2}{2^{\rho}\rho\zeta^{\prime}(\rho)}\leq c\leq-\frac{2}{\rho\zeta^{\prime}(\rho)}. Applying a more sophisticated version of the argument in our previous proof gives us our main result. Proof of Theorem 3 . Once again, we consider B(x) . Fix a positive integer k . The number of partitions of n\leq x with

Read the complete text