First polynomial time algorithm to output Ramanujan's "highly composite numbers." =========Warren D. Smith==========Sept. 2014====================== Ramanujan defined a number N to be "highly composite" is it has more divisors than any lesser number. These are the "opposite" of the primes. I discovered for the first time, that there are algorithms to output the first K of Ramanujan's "highly composite numbers" (HCNs), or to output all HCNs N with lnN<K, or to decide whether a given K-bit number N is an HCN (all three goals work, in fact the first two can be shown to be computationally polynomially equivalent) each in time bounded by polynomial(K). I also found a very fast algorithm to output SHCNs (Ramanujan's "superior highly composite numbers," a sparse but infinite subset of the HCNs)... the ratio between successive SHCNs is always a prime, and so by outputting that sequence of prime ratios you can keep the output much shorter... and to output the first K SHCN ratios can be done in about O(logK) steps per SHCN, which note is much smaller time than would be required to output the SHCNs themselves (purely because they are bulky). I prove the Kth SHCN is K^([1-o(1)]K). I have been for some time trying to work on a paper about HCNs and SHCNs, but in case I never manage to finish it, here is a quick but reasonably complete sketch of how the HCN algorithmic results established. I rest heavily on the paper S.Ramanujan: Highly composite numbers, Proc. London Math. Soc. (2) 14 (1915) 347-409 which is available online here: http://ramanujan.sirinudi.org/Volumes/published/ram15.pdf but a goodly part of this 1915 paper was not published at that time due to financial difficulties. We will not need the missing part, but it was reconstructed (with annotations & corrections) from old notes by Ramanujan and was then published in The Ramanujan Journal I (1997) 119-153 (thus totalling 98 pages) available online here: http://math.univ-lyon1.fr/~nicolas/ramanujanNR.pdf The more I look at these Ramanujan papers, the more I appreciate them. Although Ramanujan was famous for finding mysterious identities with no explanation, when he did set his mind to delivering explanations, as here, result was very nice. FIRST TRICK: The numbers N will be represented in "fancy staircase form." That is, if the prime factorization of N is N = 2^a 3^b 5^c ... Q^z then Ramanujan showed a>=b>=c>=...>=z and that z=1 or z=2, with z=2 happening only when N=4 or 36. Thus the exponents a,b,c,...,z form a descending "staircase." Further important lemmas about this staircase (proved by Ramanujan and/or me): 1: The maximum prime is Q ~ lnN. 2: The maximum exponent is a ~ lnQ /(ln2)^2 ~ (lnlnN)/(ln2)^2. 3. Also a is an upper bound on the number of stairstep down-jumps. 4. If P^2 * (lnP)^3 < (lnQ)/8 then the primes 2,3,5,...,P all have distinct exponents. The exponent e of the greatest such P obeys e ~ (ln2)^(-2) * 2 * lnQ / lnlnQ. 5. lnN = a*ln2+b*ln3+c*ln5+...+*lnQ. 6. ln(d(N)) = (a+1)*(b+1)*(c+1)*...*(z+1). where d(N) is the number of divisors of N. 7. The exponent f of any prime R with 2<=R<=Q obeys floor( lnQ / lnR ) <= f <= 2*floor( ln(Q+) / lnR ) where Q+ is the least prime greater than Q. The "exponent list" representation of N is to state all the exponents a,b,c,...,z. This requires stating ~ lnN / (lnlnN) numbers. The "plain staircase" representation of N is to state, for each integer j=1,2,3,...,a, the greatest index of any prime P such that the exponent of P is >=j. This requires stating a ~ lnlnN / (ln2)^2 numbers. The "fancy staircase" representation of N is to state, for each integer j=1,2,3,...,e, the greatest index S[j] of any prime P such that the exponent of P is >=j, plus also state the stairstep heights (exponent differences) for the exponents of the primes 2,3,5,...,P. This requires stating <=e+P ~ (ln2)^(-2) * 2 * lnlnN / lnlnlnN numbers. It may be shown that the S[j] approximately equal Q^lg(1+1/j) where lg(x)=ln(x)/ln(2). In view of this, the total number of bits you need to write down all these numbers, is about lgQ * (1+1/2+1/3+1/4+...+1/e) i.e. O(lgQ * lglnQ) bits. Although the fancy staircase representation is much more concise than more-naive representations of N, this still by itself is not small enough to make a brute force search be a polynomial time algorithm. SECOND TRICK: Write it as an "integer convex program." Specifically, let T[j]=S[j-1]-S[j]>=0 now be regarded as the (non-negative integer) variables for j=1,2,3,...,e. (The remaining T[j] for j=e+1,e+2,...,a can be dealt with by brute force trial of all possible staircase-chunks, because the total number of bits needed to describe this remaining part of the staircase is small enough.) The T[j]>=0 are linear inequalities. ln(d(N)) = SUM_j T[j] * ln(j+1) is a linear function of the T[j], so it we have some HCN N' and want to find the next greater HCN N, we can demand d(N) >= d(N')+1 as a linear inequality. Finally lnN = SUM_j ln(primorial(S[j]) where primorial(k) is the product of the first k primes, is a concave-U function of the S[j]'s and hence of the T[j]'s. So finding the next HCN N is minimizing a concave-U function of v=O(lnlnN/lnlnlnN) variables subject to linear inequality constraints, and integrality constraints. This is exactly an "integer convex program." THIRD TRICK: I invented a new algorithm for integer convex programming. Ravi Kannan: Minkowski's convex body theorem and integer programming, Mathematics of Operations Research 12,3 (Aug. 1987) 415-440 available online here: http://repository.cmu.edu/cgi/viewcontent.cgi?article=2568&context=compsci showed how to solve v-variable integer programs in v^O(v) time. [He also found v^O(v)-time procedures for shortest nonzero vector in a lattice, and closest lattice vector, in for v-dimensional lattices, but these two algorithms have been obsoleted by later authors with 2^O(v)-time methods. It remains an important open problem as of year 2014 whether integer programming can be done in 2^O(v) time.] Strangely enough, Kannan and other authors never mentioned the fact -- but I claim it is true -- that ideas very much like his will solve CONVEX integer programs, a wider class than LINEAR IPs, still in v^O(v) time, where the convex objective function, and convex-membership constraints, both can be specified by a "weak membership oracle." I sketch the method to accomplish this. In the HCN application, there will be an outer binary search over N, trying to find the least N with d(N)>=d(N')+1. The search will continually ask yes/no existence questions of an integer convex programming subroutine, of the form "does an N exist with N'<N<X?" (If "no" then increase X. If "yes" then decrease X.) To build the existence-deciding subroutine, we first perform a rational linear transformation to "well round" the region we are asking about whether it contains an integer point. Such "well roundings" can be found in polynomial time using methods discussed in M.Gr"otschel, L.Lovas, A.Schrivjer: Geometric algorithms and combinatorial optimization, Springer 1988 based on the "ellipsoid algorithm" for polynomial time convex programming (for rationals, NOT for integers). Well rounding also can be done by by a different method (if you are willing to use nondeterministic algorithms) in U. Faigle, N. Gademann, W. Kern: A random polynomial time algorithm for well-rounding convex bodies, Discrete Applied Mathematics 58 (1995) 117-144. After rounding transform, the convex region is now spherical to within radial factors of v^O(1). We now find the shortest nonzero vector in the integer lattice (in the new linearly transformed space) and indeed a "good basis" for said lattice, using the methods by Kannan or his successors, in v^O(v) or 2^O(v) time. We then find all lattice vectors at most v^O(1) times longer than shortest. There are at most v^O(v) such vectors. One of them will yield an N solving our integer convex program existence question if any solution exists. That answers the yes/no question. FINAL RESULT: Since v=O(lnlnN/lnlnlnN) in the HCN application, v^O(v) is bounded by polynomial(lnN). Hence we can, given any HCN N', find the next HCN N, in time < polynomial(lnN). QED. -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)