# $(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$)?
• Doesn't that blog post actually claim the converse? That is, if equations of the above form $(2^n)! = \sum \cdots$ have solutions in general, then factoring has polynomial-sized circuits. – mikero May 2 '12 at 19:30
• I think you actually wrote the converse of what Dick Lipton wrote. He says that if such an equation exists for every $n$, then factoring has polynomial size circuits. So the implication is that if factoring is non-uniformly hard (for infinitely many $n$) then equations of the above form do not exist (for infinitely many $n$). – Sasho Nikolov May 2 '12 at 19:33
• @mikero, SashoNikolov, you both are correct, my apologies. I have edited my question. – user834 May 2 '12 at 19:42
• note that "polynomial time algorithm" usually means a uniform algorithm. Lipton's post only asserts the existence of a polysize circuit family for factoring. – Sasho Nikolov May 2 '12 at 19:44
• Note that in order for this property to be true, $a_k$, $b_k$ and $c_k$ should be $poly(n)$ in bit size /as stated on Lipton's blog/, and $poly(2^n)$ as integers. Your definition is not clear. – Gopi May 3 '12 at 12:55

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.
• If the relation holds (for all $n$), then perhaps it also holds (with a different choice of $a_k$, $b_k$ and $c_k$) when one replaces $2$ with another (small) prime, $p$. One could presumably search until a $p$ is found such that $x$ is coprime to $(p^n)!$ and not $(p^{n+1})!$ – user834 May 6 '12 at 6:24