10
$\begingroup$

if $x=d(n)$ is the number of divisors of $n$, what is the tightest lower-bound for $n$ only given $x$?

http://en.wikipedia.org/wiki/Highly_composite_number

$\endgroup$

2 Answers 2

21
$\begingroup$

I will start off with the simplest type, $$ d(n) \leq \sqrt{3 n} $$ and $$ d(n) \leq 48 \left(\frac{n}{2520}\right)^{1/3} $$ and $$ d(n) \leq 576 \left(\frac{n}{21621600}\right)^{1/4}. $$ The first one has equality only at $n = 12,$ second only at $n =2520,$ third only at $n= 21621600.$ Instead of continuing with fractional powers $1/k$ the better results switch to logarithms. Reference is a 1988 paper by J. L. Nicolas in a book called Ramanujan Revisited.

With equality at $n = 6983776800 = 2^5 \cdot 3^3 \cdot 5^2 \cdot 7 \cdot 11 \cdot 13 \cdot 17 \cdot 19$ and $d(n) = 2304,$ $$ d(n) \leq n^{ \left( \frac{\log 2}{\log \log n} \right) \left( 1.5379398606751... \right)} = n^{ \left( \frac{1.0660186782977...}{\log \log n} \right) }. $$ Full details of the proof appear in J.-L. Nicolas et G. Robin. Majorations explicites pour le nombre de diviseurs de n, Canad. Math. Bull., 26, 1983, 485--492. The next two appear in the dissertation of Robin, are repeated in the 1988 Nicolas survey article indicated.

With equality at a number $n$ near $6.929 \cdot 10^{40},$ $$ d(n) \leq n^{ \left( \frac{\log 2}{\log \log n} \right) \left( 1 + \frac{1.934850967971...}{\log \log n} \right)}. $$ Compare this one with Theorem 317 in Hardy and Wright, attributed to Wigert (1907), $$ \limsup \frac{\log d(n) \log \log n}{\log n} = \log 2. $$

With equality at a number $n$ near $3.309 \cdot 10^{135},$ $$ d(n) \leq n^{ \left( \frac{\log 2}{\log \log n} \right) \left( 1 + \frac{1}{\log \log n} + \frac{4.762350121177...}{\left(\log \log n \right)^2} \right)} $$

Just to fill in one blank, the special integers $n$ here are "superior highly composite numbers" using Ramanujan's original recipe for prime factorization, which I like to write, with $ \delta > 0,$ as $$ N_\delta = \prod_p \; p^{\left\lfloor \frac{1}{p^\delta - 1} \right\rfloor } $$ The first (largest) $\delta$ that assigns an exponent $k$ to a prime $p$ is $$ \delta = \frac{\log \left(1 + \frac{1}{k} \right)}{\log p}. $$ See Is there a formula that can predict the primes in the sequence of ratios of consecutive superior highly composite numbers? : $2, 3, 2, 5, 2, 3, 7,...$ for some detail, with computations.

So $$ N_{1/2} = 12, \; N_{1/3} = 2520, \; N_{1/4} = 21621600, $$
$$ N_{0.23} = 6983776800, \; N_{0.155} \approx 6.929 \cdot 10^{40}, \; N_{0.1218} \approx 3.309 \cdot 10^{135}.$$

$\endgroup$
1
  • 1
    $\begingroup$ For the benefit of future readers, let $x=d(n)$, then inverting the bounds given above, $x^2/3 \leq n, 2520(x/48)^3 \leq n, 21621600(x/576)^4 \leq n$, and soon. The more ambitious can try inverting the bound involving logarithms. Gerhard "Leaves Something For Future Readers" Paseman, 2015.12.04 $\endgroup$ Dec 5, 2015 at 5:58
2
$\begingroup$

It would be nice to have an inequality $n \ge f(x)$. If the poser wants numerical results, here are two:

The least number having exactly x divisors is given by OEIS sequence http://www.oeis.org/A005179. It is a pretty wild function. The nice paper by Grost is recommended.

The least number having x (or more) divisors is given by the OEIS sequence http://www.oeis.org/A061799.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.