Unconditional Subexponential Arithmetic Circuits\ for Positive Factorial Multiples

Source abstract

Let $τ(n)$ be the least number of binary additions, subtractions and multiplications required to construct $n$ from $1$ and $2$, with reuse of intermediate values. We show that, for every sufficiently large integer $k$, some positive integer $m$ satisfies $$τ(mk!)\leq \exp\!\left(O\!\left((\log k)^{2/3}(\log\log k)^{1/3}\right)\right).$$ The proof combines unconditional results of Lenstra, Pila and Pomerance on smooth numbers in short intervals and on orders of genus-two Jacobians with a five-parameter family carrying a rational divisor class of infinite order. We encode rational divisor arithmetic, including the tests determining its branches, by a nonzero division-free integer circuit. A common finite sampling space yields circuits whose outputs collectively contain every prime at most $k$, and repeated squaring supplies the required factorial valuations. The circuit bound includes the cost of constructing all integer parameters. This work was carried out with assistance from the UniMath model, developed by UniDT (Shanghai) Co., Ltd., and GPT-6.1 Sol.