Decomposing a Factorial into Large Factors

Summary

I’ve just uploaded to the arXiv the paper “Decomposing a factorial into large factors“. This paper studies the quantity , defined as the largest quantity such that it is possible to factorize into factors , each of which is at least . The first few values of this sequence are (OEIS A034258). For instance, we have , because on the one hand we can factor but on the other hand it is not possible to factorize into nine factors, each of which is or higher. This quantity was introduced by Erdös, who asked for upper and lower bounds on ; informally, this asks how equitably one can split up into factors. When factoring an arbitrary number, this is essentially a variant of the notorious knapsack problem (after taking logarithms), but one can hope that the specific structure of the factorial can make this particular knapsack-type problem more tractable. Since for any putative factorization, we obtain an upper bound thanks to the Stirling approximation. At one point, Erdös, Selfridge, and Straus claimed that this upper bound was asymptotically sharp, in the sense that as ; informally, this means we can split into factors that are (mostly) approximately the same size, when is large. However, as reported in this later paper, Erdös “believed that Straus had written up our proof… Unfortunately Straus suddenly died and no trace was ever found of his notes. Furthermore, we never could reconstruct our proof, so our assertion now can be called only a conjecture”. Some further exploration of was conducted by Guy and Selfridge. There is a simple construction that gives the lower bound that comes from starting with the standard factorization and transferring some powers of from the later part of the sequence to the earlier part to rebalance the terms somewhat. More precisely, if one removes one power of two from the even numbers between and , and one additional power of two from the multiples of four between to , this frees up powers of two that one can then distribute amongst the number...