Highly composite numbers

[joshuazelinsky]

 Highly composite numbers are numbers whose total number of divisors is greater than any smaller number. For example, 12 has 6 divisors, 1, 2, 3, 4, 6 and 12, and no number smaller than 12 has 6 or more divisors. There's a really good video on them here .

These were first studied by Ramanujan a little over a hundred years ago. He proved a bunch of statements about them, some of the easier ones of which are included in the video above with proofs. Here are two of those: First, If N is a highly composite number and we list its distinct prime factors in order, then we cannot skip any prime factor. For example, 66 cannot be a highly composite number because 66=2*3*11 and so we skipped 5 and 7. Second, if N is a highly composite number, we cannot have an exponent of a prime in the factorization be higher than the exponent for a smaller prime. For example, 150 cannot be highly composite because 150 = 2^1 * 3^1 * 5^2 and 2>1.

Now, I want to mention something not in the above video that was pretty surprising to me the first time I learned about it: If we list the number of distinct prime divisors each highly composite number has, we might expect that number to never go down. (By number of distinct prime divisors we mean that we count primes which repeat in the factorization only once. So for example, 150 above would have three distinct prime factors.) And for the first few this is true, as you can check. But it does break down! 27720 is a highly composite numbers. We have 27720 = 2^3 * 3^2 * 5 * 7 * 11 with 5 distinct prime divisors, and a total of 96 total divisors. But the next highly composite number is 45360 = 2^4 * 3^4 * 5 * 7 is the next highly composite number. 45360 has only 4 distinct prime divisors; notice we lost the 11. There are even larger examples where we lose two prime factors when going up. I don't know of any example where we lose 3 or more, and as far as I'm aware whether there are any is an open question.

Comments

[sniffnoy]

Oh, hm. So of course we can combine the two true statements into a single statement that says that their (full) sequence of exponents must be weakly decreasing.

For some reason when you wrote that I made the inference that this sequence of weakly decreasing sequences is itself increasing! (In the pointwise partial order, or you can think of all this as living in Young's lattice. :) ) But as your example shows that's not true. Huh...

[joshuazelinsky]

Hmm, thinking about this in terms of lattices raises a question: Let n be a positive integer. Call b a maximal highly composite divisor of n if 1) b is highly composite, 2) b|n and 3) If b|a and a|n and a is highly composite then a=b. How many maximal highly composite divisors can a number have? The obvious attempt above to make one with 2 maximal highly composite divisors is to take the lcm of 27720 and 45360. But this doesn't work because their lcm is 498960, which is itself highly composite. There are, however much smaller examples. For example, 72 has two maximal highly composite divisors 36 and 48. My guess is that for any k there exists an n with k maximal highly composite divisors. But I don't see any immediate way to prove this.

[sniffnoy]

You know Josh you could just say "b is a maximal highly composite divisor of n if b is maximal under divisibility among highly composite divisors of n". :P

[joshuazelinsky]

Yes, that's a substantially shorter way of putting it. Question remains.