$(2^n)! = \sum_{k=0}^{m-1} a_k b_k^{c_k} $? While reading Dick Lipton's blog, I stumbled across the following fact near the end of his Bourne Factor post:


  If, for every $n$, there exists a relation of the form
  $$ (2^n)! = \sum_{k=0}^{m-1} a_k b_k^{c_k} $$
  where $m = poly(n)$, and each of the $a_k$, $b_k$ and $c_k$ are $poly(n)$ in bit length, then factoring has polynomial sized circuits.


In other words, the $(2^n)!$, which has an exponential number of bits, can potentially be represented efficiently.

I have a few questions:


Could someone provide a proof of the above relation, tell me the name and/or provide any references?
If I were to give you $n$, $m$ and each of the $a_k$, $b_k$ and $c_k$, could you provide me a polynomial time algorithm to check the validity of the relation (i.e. is it in $NP$)?
I’ll comment on why a relation as in the question
$$ (2^n)! = \sum_{k=0}^{m-1} a_k b_k^{c_k} $$
(for every $n$) helps factoring. I can’t quite finish the argument, but maybe someone can.

The first observation is that a relation as above (and more generally, the existence of poly-size arithmetic circuits for $(2^n)!$) gives a poly-size circuit for computing $(2^n)!\bmod x$ for $x$ given in binary: simply evaluate the sum modulo $x$, using exponentiation by repeated squaring.

Now, if we could compute $y!\bmod x$ for arbitrary $y$, we could factor $x$: using binary search, find the smallest $y$ such that $\gcd(x,y!)\ne1$ (which we can compute using $\gcd(x,(y!\bmod x))$). Then $y$ must be the smallest prime divisor of $x$.

If we only can do powers of $2$ for $y$, we can still try to compute $\gcd(x,(2^n)!)$ for every $n\le\log x$. One of these will be a nontrivial divisor of $x$, except for the unfortunate case when there is an $n$ such that $x$ is coprime to $(2^n)!$, and divides $(2^{n+1})!$. This is equivalent to saying that $x$ is square-free, and all its prime factors have the same bit-length. I don’t know what to do in this (rather important, cf. Blum integers) case.