<p>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.</p>

<p>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.</p>

<p>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$.</p>

<p>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.</p>

CC BY-SA 3.0
2012-05-06T06:24:41.267Z
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
CC BY-SA 3.0
2012-05-03T18:22:13.553Z
2012-05-03T18:22:13.553Z
Emil Jeřábek
<p>While reading Dick Lipton's blog, I stumbled across the following fact near the end of his <a href="http://rjlipton.wordpress.com/2012/02/26/the-bourne-factor/" rel="nofollow">Bourne Factor</a> post:</p>

<blockquote>
  <p>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.</p>
</blockquote>

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

<p>I have a few questions:</p>

<ul>
<li>Could someone provide a proof of the above relation, tell me the name and/or provide any references?</li>
<li>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$)?</li>
</ul>

CC BY-SA 3.0
2012-05-02T19:30:20.183Z
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
CC BY-SA 3.0
2012-05-02T19:33:50.323Z
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
CC BY-SA 3.0
2012-05-02T19:42:29.687Z
@mikero, SashoNikolov, you both are correct, my apologies.  I have edited my question.
user834
CC BY-SA 3.0
2012-05-02T19:44:49.607Z
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
CC BY-SA 3.0
2012-05-03T12:55:39.350Z
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
CC BY-SA 3.0
2012-05-03T17:32:47.640Z
@Gopi, of course you're right.  I tried to make the wording a bit more clear and failed to state it correctly.  This has been fixed.
user834
CC BY-SA 3.0
2012-05-04T17:16:28.433Z
One could imagine a test mod $p < 2^n$, where we know $(2^n)! = 0 \ (\mod p)$ and we can confirm that efficiently to the right.  If we choose $p$ randomly, we can get a probability of the relation being correct, though this is nowhere near efficient enough.  Maybe someone can use this as a starting point for a deterministic/efficient probabilistic test?
user834
CC BY-SA 3.0
2012-05-07T00:22:09.393Z
One can also choose primes, $q$, slightly larger than $2^n$ and use Wilson's to confirm $(2^n)!$ is what it should be mod $q$.
user834
<ds.algorithms><reference-request><factoring><comp-number-theory>
$(2^n)! = \sum_{k=0}^{m-1} a_k b_k^{c_k} $?
user834
# $(2^n)! = \sum_{k=0}^{m-1} a_k b_k^{c_k} $?

(Asked by: username_0 on 2012-05-02)

While reading Dick Lipton's blog, I stumbled across the following fact near the end of his [Bourne Factor](http://rjlipton.wordpress.com/2012/02/26/the-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$)?

**Tags:** ds.algorithms, reference-request, factoring, comp-number-theory

> **Comments:**
> **username_1**: 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.  
> **username_2**: 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$).  
> **username_0**: @username_1, SashoNikolov, you both are correct, my apologies.  I have edited my question.  
> **username_2**: note that "polynomial time algorithm" usually means a uniform algorithm. Lipton's post only asserts the existence of a polysize circuit family for factoring.  
> **username_3**: 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.  
> **username_0**: @username_3, of course you're right.  I tried to make the wording a bit more clear and failed to state it correctly.  This has been fixed.  
> **username_0**: One could imagine a test mod $p < 2^n$, where we know $(2^n)! = 0 \ (\mod p)$ and we can confirm that efficiently to the right.  If we choose $p$ randomly, we can get a probability of the relation being correct, though this is nowhere near efficient enough.  Maybe someone can use this as a starting point for a deterministic/efficient probabilistic test?  
> **username_0**: One can also choose primes, $q$, slightly larger than $2^n$ and use Wilson's to confirm $(2^n)!$ is what it should be mod $q$.  

---

## 1 answers

### Answer by username_4 on 2012-05-03. Score: 8

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.

> **Comments:**
> **username_0**: 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})!$  

---

