# Is factorial computation known to be in a class smaller than $FEXP$?

Functional version of the counting hierarchy is $$FCH$$. It is an open problem whether there a sequence of $$poly(log(n))$$ number of $$+,\times$$ operations utilizing the assistance of $$O(1)$$ number of constants and arbitrary number of integer variables to compute $$n!$$.

In terms of output size $$n!$$ is not even in polynomial in $$log(n)$$ space. So in terms of Boolean complexity where is the computation of $$n!$$ in? It is clearly not in $$FCH$$ but in $$FEXPSPACE$$.

If we are given a prime $$p$$ is the computation of $$n!\bmod p$$ in $$FCH$$?

Will the answers change much if there is a sequence of $$poly(log(n))$$ number of $$+,\times$$ operations utilizing the assistance of $$O(1)$$ number of constants and arbitrary number of integer variables to compute $$n!$$?

A sequence of arithmetic operations is referred as a straightline program.

Yes, $$n!\bmod p$$ is computable in FCH. More generally, if $$f$$ is a polynomial-time computable function, then given $$n$$ and $$m$$ in binary, we can compute $$\prod_{i in FCH. This follows from the fact that if we are given in unary $$n$$, $$m$$, and a sequence of numbers $$a_0,\dots,a_{n-1}$$, then we can compute $$\prod_{i in uniform $$\mathrm{TC}^0$$, which was proved by

William Hesse, Eric Allender, and David A. Mix Barrington: Uniform constant-depth threshold circuits for division and iterated multiplication, Journal of Computer and System Sciences 65 (2002), no. 4, pp. 695–716, doi 10.1016/S0022-0000(02)00025-9.

In fact, we can avoid almost all the intricate machinery of the [HAB02] paper due to a combination of two factors:

• When the algorithms are exponentially scaled to FCH, we only need quasipolynomial $$\mathrm{TC}^0$$. Thus, for example, we can use the trivial polynomial-time algorithm for modular exponentiation by repeated squaring instead of the [HAB02] algorithm (which actually puts it in the linear-time hierarchy).

• Since the result is computed modulo $$m$$, we don’t need the full force of Chinese Remainder Reconstruction (which is the most complicated and most costly step in [HAB02]).

So, here is an explicit algorithm. First, if $$m=p$$ is prime, we have $$\prod_{i where $$g$$ is a generator of $$\mathbb F_p^\times$$, and $$d$$ is the inverse of $$g^x\bmod p$$ (i.e., discrete logarithm). (Let’s consider that $$d(0)=-\infty$$.) We can compute $$g$$ and $$d(f(i))$$ in FPH, thus $$\sum_id(f(i))$$ in $$\mathrm{\#P^{PH}}$$, thus the final result in $$\mathrm{FP^{\#P^{PH}}=FP^{\#P}=FP^{PP}}.$$ (I’m using here the fact that $$\mathrm{\#P^{PH}\subseteq P^{\#P}}$$.)

A similar argument works when $$m$$ is a prime power.

For general $$m$$, we can compute the prime factorization $$m=\prod_{j in FPH, thus (for each $$j) $$r_j=\prod_{i (or rather, the pair $$(p_j^{e_j},r_j)$$) in $$\mathrm{FP^{\#P^{PH}}=FP^{PP}}$$ as above, and we can reconstruct the result modulo $$m$$ in polynomial time. Thus again, the overall complexity is that we can compute (1) in $$\mathrm{FP^{PP}}.$$

The non-modular function $$n!$$ as such is an exponential-output-size function whose bit-graph is computable in CH (again, by [HAB02]). There is no common name for this class of functions, as far as I am aware. It is included in FPSPACE, as long as you make sure not to artificially restrict this class to functions with polynomial output size (for space classes, it is a standard definition that space usage only counts work tapes, not the read-only input tape or the write-only output tape).

• Thank you but where is $n!$? Aug 15, 2021 at 8:19
• Based on the statements you provide $n!$ is in $FCH$ it appears. Is there a definition for bit-graph? Aug 15, 2021 at 9:07
• Usually, FCH is defined so that it requires output size to be polynomial. (E.g., this follows from the definition $\mathrm{FCH}=\bigcup_n\mathrm{FC}_n$, where $\mathrm{FC_0=FP}$, $\mathrm{FC}_{n+1}=\mathrm{\#P}^{\mathrm{FC}_n}$.) The bit-graph of a function $f$ is the language $\{(x,i):\mathrm{bit}(f(x),i)=1\}$, where $\mathrm{bit}(w,i)$ is the $i$th bit of $w$. (I take $i$ to be written in binary.) Aug 15, 2021 at 9:29