Unconditional Subexponential Arithmetic Circuits for Positive Factorial Multiples
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!)≤ exp (O ((log k)2/3(loglog k)1/3)). 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.
Related
- Square-root logarithmic bounds for the arithmetic complexity of factorial multiples
- Improved Subexponential Upper Bounds for $3$-Restricted Matching Vector Families
- Subexponential Approximation of the Permanent in Deterministic Polynomial Time
- Uniform Local Asymptotics for Lévy Processes with Subexponential Jumps
- Coûts de transaction, équilibres multiples avec chômage et concurrence monopolistique
BibTeX
@misc{zhang2026unconditional,
title = {{Unconditional Subexponential Arithmetic Circuits for Positive Factorial Multiples}},
author = {Liang Zhang},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.28338},
eprint = {2610.28338},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.28338},
}
RIS
TY - UNPB
TI - Unconditional Subexponential Arithmetic Circuits for Positive Factorial Multiples
AU - Liang Zhang
PY - 2026
DA - 2026/10/22
PB - arXiv
DO - 10.48550/arxiv.2610.28338
UR - https://arxiv.org/abs/2610.28338
AB - 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!)≤ exp (O ((log k)^2/3(loglog k)^1/3)). 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.
ER -