Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Let $\sigma_k(n)$ denote the sum of the k-th powers of the divisors of n. For any real value of k, we can find a sequence of numbers $s_k$ that has increasing values of n at which $\sigma_k(n)$ attains a new maximum. For k=0, that sequence is called the highly composite numbers, which is A002182 in the OEIS database. From numerical experimentation, it appears that if i > j >= 0, then $s_j$ is a subsequence of $s_i$. Is this a known result? If not, any ideas on how to prove it?

share|improve this question
    
It was just pointed out to me that 1084045767585249647898720000 provides a counterexample: it is in $s_0$ but not in $s_1$. –  tdnoe Oct 11 '10 at 17:32
    
Start with L. Alaoglu and P. Erdos, On highly composite and similar numbers, Trans. Amer. Math. Soc., 56 (1944), 448-469. $$ $$ en.wikipedia.org/wiki/Highly_abundant_number $$ $$ oeis.org/classic/A002093 –  Will Jagy Oct 11 '10 at 17:39
    
There are ten counterexamples in the new sequence oeis.org/classic/A181309 –  tdnoe Oct 19 '10 at 15:56
add comment

1 Answer

up vote 3 down vote accepted

It appears you got an answer while I was typing my comment. But let me expand the picture a bit. Ramanujan initiated a technique for finding certain subsequences of yours that possess a parametrization, where the highly composite numbers do not. First, see two articles,

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

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

The recipe is very simple, with one detail that is not usually pointed out: to define the sequence of "superior" numbers, note that for any $\varepsilon > 0,$ we can prove $$ \lim_{n \rightarrow \infty} \frac{\sigma_k(n)}{n^{k + \varepsilon}} = 0. $$ As a result, for any fixed $\varepsilon > 0,$ the ratio attains a maximum at a finite number of integers (usually just one). If the maximum is attained at more than one integer, take the largest of these, and call that $S_\varepsilon.$ As $\varepsilon$ decreases $S_\varepsilon$ stays the same until $\varepsilon$ passes below the next of a sequence of threshold values, and then at the threshold is multiplied by a certain prime. So we get an increasing sequence $S_\varepsilon,$ each a multiple of all before it, and each setting a new record for $\sigma_k.$

Now, about the recipe, the construction, if you work through it carefully, gives a specific prime factorization for $S_\varepsilon,$ where the exponent for any prime depends on $\varepsilon$ in a way that involves the greatest integer function $\lfloor \bullet \rfloor. $ However, as $\varepsilon$ decreases, the relative sizes of the exponents for two primes, say 2 and 3, depend upon the value of $k.$ And these sequences are a subsequence of yours. So, despite that fact that there are so many more numbers of a given size in one of your sequences, what this says to me is that we should not expect too much agreement for differing $k.$ At the same time, there are papers on the difficult Operations Research aspects of finding large highly composite numbers, say all those between two consecutive "superior" numbers. Thus the first disagreement (showing one is not a subsequence of the other) of two of your sequences may occur at a huge number, as you found.

Well, for $k=1$ this was written up by Alaoglu and Erdos. It was later discovered that Ramanujan did write this up as well, but the journal declined to publish the full length article owing to shortages of paper in 1915.

Contemporary authors working in this area include J.-L. Nicolas and G. Robin. Perhaps the most dramatic use of these numbers is that the Riemann hypothesis is equivalent to the statement that for $n > 5040,$ $$ \sigma_1(n) < e^\gamma n \log \log n, $$ and that any possible counterexample must occur at a colossally abundant number

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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