3
$\begingroup$

For a positive integer $n,$ let $f(n)$ denote the number of ordered pairs with lcm $n$. Since the total number of ordered pairs from the set $\{1,2,\ldots,n\}$ is $n^2$ it seems interesting to to see how the sequence $\left\langle \frac{f(n)}{n^2} \right\rangle$ behaves. I did some simulations and it seems the sequence should converge to zero but I am not analytically sure. Can somebody kindly help me out?

$\endgroup$
7
  • $\begingroup$ Since this (long-winded) response is (in my opinion) inappropriate as an answer, I am commenting. Initially, I thought that if the prime factorization of $n = \prod_{i=1}^r \,p_i^{(\alpha_i)},$ then the question would navigate towards considering $n = a\times b,$ with $a$ = the product of some subset of the $r$ primes, with each prime $p_i$ raised to the exponent $\alpha_i.$ ...See next comment. $\endgroup$ Aug 6, 2020 at 2:58
  • $\begingroup$ If $n = \prod_{i=1}^r \,p_i^{(\alpha_i)}$, the number of ordered pairs with lcm.$n $ can be shown to be $\prod_{i=1}^r \{(2.\alpha_i+1)}$ $\endgroup$ Aug 6, 2020 at 3:01
  • $\begingroup$ However, I now think that this navigation is oversimplified. With $n = a\times b,$ a given prime $p_i$ can be shared by both $a$ and $b.$ That is, $p_i^{(\beta_i)} | a$ and $p_i^{(\gamma_i)} | b$, with $\alpha_i = \max(\beta_i, \gamma_i).$ This sharing of prime factors throws a monkey wrench into my intuition and prevents me from trying to use my intuition to move forward on the problem. $\endgroup$ Aug 6, 2020 at 3:04
  • $\begingroup$ Just to be clear, re my reaction to your comment: the problem is too complicated for me, so I am forced to (currently) have no opinion re your comment. By the way, I upvoted; interesting problem. $\endgroup$ Aug 6, 2020 at 3:07
  • 1
    $\begingroup$ $f(n)$ is the number of divisors of $n^2$. It's tabulated at oeis.org/A048691 with links to the literature. The number of divisors of $n^2$ is trivially bounded above by $2n-1$, so the quotient you ask about certainly goes to zero as $n$ goes to infinity. $\endgroup$ Aug 6, 2020 at 4:01

1 Answer 1

2
$\begingroup$

First, for any prime $p$ the ordered pairs are $(1,p), (p,1), (p,p)$, so we have $f(p)=3, \frac{f(p)}{p^2}=\frac {3}{p^2}$ which goes to $0$ for large $p$, so $0$ is an accumulation point. To show it is the limit, we need to show the highest values also go to $0$.

Consider $f(n)$ for $n$ the power of a prime, $n=p^k$. We have $f(n)=2k+1$ because one of the elements of the ordered pair must be $p^k$ while the other can be any power of $p$ from $0$ to $k$. Now note that your function $f(n)$ is multiplicative. If $n=ab$ with $a,b$ coprime, $f(n)=f(a)\cdot f(b)$. If the prime factorization of $n$ is $n=p^aq^br^c$ we have $f(n)=(2a+1)(2b+1)(2c+1)$ because you can distribute the powers of each prime independently. You need $a,b,c$ powers of each prime in one of the two factors, then $0$ to the maximum in the other.

The $n$ that are maxima so far of $f(n)$ will be similar to the highly composite numbers but will have more large primes and less factors of $2$ because adding a new prime triples the number of pairs instead of only doubling the number of factors. For example $30$ is a new maximum of $f(n)$ with $27$ pairs, while it only has $8$ factors which is no more than $24$ has.

A rough way to see that $\frac {f(n)}{n^2}$ converges to $0$ is to consider the primorials, the products of the first $k$ primes. These have $3^k$ ordered pairs, which is a lot, but they are not the smallest numbers with that many ordered pairs-you want more small factors than that. The primorials are roughly $k^k$, so we are asking about $\frac {3^k}{k^{2k}}$, which goes to zero. I am sure that the same thing will happen with the maxima of $f(n)$ but don't know how to demonstrate it.

$\endgroup$
4
  • 2
    $\begingroup$ betraying the limit of my intuition: If you deem it worthwhile, please addendum/edit your answer to demonstrate that $f(n)$ is multiplicative. $\endgroup$ Aug 6, 2020 at 3:15
  • $\begingroup$ Please explain the case of $ n = p^{k}$. It's divisors will be $ 1, p,p^2,...,p^k$ which are total k+1 in number. In that case how can f(n) be 2k + 1? Shouldn't it be (k+1)? Other multiples of $p$ can only have a non trivial gcd with$ p^{k}$ but cannot yield the LCM as $p^k$ $\endgroup$
    – Laxmi
    Aug 6, 2020 at 14:16
  • $\begingroup$ @Laxmi: You can have $(p^k,p^m)$ with $m$ ranging from $0$ to $k$, which is $k+1$ of them. You can also have $(p^m,p^k)$ with $m$ in the same range, making a total of $2k+2$. We have counted $(p^k,p^k)$ twice, so the final answer is $2k+1$ $\endgroup$ Aug 6, 2020 at 14:25
  • $\begingroup$ @Ross Millikan: Got it. Thanks for explaining. $\endgroup$
    – Laxmi
    Aug 6, 2020 at 14:29

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .