Bounds for constructing $n!$ with additions, subtractions, and multiplications starting from $1$

Question

Found this on Complexity Zoo warning expired certificate check NP Over The Complex Numbers.

[BCS+97] show the following striking result. For a positive integer $n$, let $t(n)$ denote the minimum number of additions, subtractions, and multiplications needed to construct $n$, starting from 1. If for every sequence ${n_k}$ of positive integers, $t(n_k k!)$ grows faster than polylogarithmically in $k$, then $P_C$ does not equal $NP_C$.

[BCS+97] L. Blum, F. Cucker, M. Shub, and S. Smale. Complexity and Real Computation, Springer-Verlag, 1997.

Couldn't find the paper online, so the exact definition would be helpful.

What are bounds for $t(n!)$?

---

Added later What are bounds for $t(a n!)$ where $a$ is nonzero and no other properties of $a$ are required?

---

Didn't spend much time, but couldn't solve this:

Find $a>1,k>1$ and $t(a k!) < t(k!)$.

---

Added I doubt this is of any practical interest because of the space complexity of factorial.

$$ n\log\left(\frac{n}{e}\right)+1 \leq \log n! $$

In OEIS A025201 a(n) = floor(log(n!))..

We have $n!=\Gamma(n+1)$ and $\log \log \Gamma(2^{1000})=699.6\ldots$ and $\log \log 2^{2^{1000}}=692.7\ldots$.

Even if an oracle computes the factorial, it is impossible to store in the computer space of all computers on earth.

---

Added later Comment from Gerhard "Wants To See Better Bounds" Paseman

I'd like to add that a similar sounding problem https://mathoverflow.net/a/75792/3206 using additions and multiplications has easy lower and upper bounds of O(log n). The computation model for this problem is different from the above problem, as "repeated subterms" do not add to the complexity of the computation, to state the matter (from memory) roughly. Gerhard "Wants To See Better Bounds" Paseman, 2015.01.26

References for the above answer in OEIS: http://oeis.org/A005245

Answer 1

If Gerhard Paseman is right that $t(7!)=8$ then $(k,a)=(7,13)$ is already an example of $t(ak!)<t(k!)$, because $$ 13 \cdot 7! = 65520 = 2^{16} - 2^4 $$ can be reached in six steps from $1$: $$ 1 + 1 = 2, \quad 2 \cdot 2 = 4, \quad 4 \cdot 4 = 16, \quad 16 \cdot 16 = 256, \quad 256 \cdot 256 = 65536, $$ and finally $65536 - 16 = 65520$. This also makes $(10,1183)$ a candidate if $10!$ can't be reached as quickly as the seven steps to $65520^2$. [Added later: Michael Stoll now confirms that $t(7!)=8$ $-$ and also reports that it takes nine steps to reach $10!$, and eight for $8!$ and $9!$, so this seven-step route to $65520^2$ gives $t(ak!)<t(k!)$ also for $k=8,9,10$. Later yet, Stoll links to OEIS A217032 which gives the values of $t(k!)-1$ for all $k \leq 19$; this lets us give some more examples, such as $16! \, | \, (2^{64}-2^4)^4$ with $t(16!) = 13$ and $t((2^{64}-2^4)^4) \leq 11$.]

But the asymptotic question is much harder because we don't have good lower bounds on $t(k!)$. Gerhard Paseman gives an upper bound of $2k$ or maybe $(1+o(1))k$, which is within a constant factor of what can be done for any number of this size: if $N < k^k$ we can use $k$ additions to get $1,2,3,\ldots,k$, then $k-1$ multiplications to reach $k^2, k^3, \ldots, k^k$, and then $k+k$ more multiplications and additions to reach $N$ via its base-$k$ expansion. For $t(k!)$ we can reduce this by a factor $\gg \log k$ for large $k$, because $k!$ is a product of powers of the $\pi(k)$ primes $p\leq k$. We can reach all those primes in $\pi(k) + O(k^{1/2})$ additions: let $r = \lfloor \sqrt{k} \rfloor$, then add to get $1,2,3,\ldots,r,2r,3r,\ldots, r^2$, and each prime is a sum of one or two of these. [The Masked Avenger notes that it's a bit faster to first get all the numbers that occur as gaps $p_n - p_{n-1}$, and then get from each prime to the next.] Now use fewer than $\pi(k)$ multiplications to make the products $$ P_i := \prod_{ip \leq k < (i+1) p} p $$ for $i=1,2,3,\ldots,r$, and then $k! = P_1^{\phantom 1} P_2^2 P_3^3 \cdots P_r^r$ times $\pi(r)$ prime powers.

If that approach were optimal then we could get $t(ak!) < t(k!)$ by replacing $\prod_{i=1}^r P_i^i$ by $\left(\prod_{i=1}^r P_i\right)^{2^\rho}$ once $2^\rho \geq r$. But it seems that in fact $t(k) \ll k^{1/2 + o(1)}$ because one can write $m^2! = \prod_{j=0}^{m-1} Q(jm)$ where $Q(X) = (X+1) (X+2) (X+3) \cdots (X+m)$ and use FFT-like tricks to evaluate a degree-$m$ polynomial at $m$ points in only $m \log^A m$ operations. (See for instance this page. I learned of this surprising fact some year back from Henry Cohn. Caveat: some more work might be needed to fit this method into the $\{+,-,\times\}$ model without losing a factor worse than $k^\epsilon$. Added later: Turbo notes that this paper by Q.Cheng (of which more in the next paragraph) cites a paper by Strassen from the 1970's that gives a route to $k!$ in $O(k^{1/2} \log^2 k)$ $\{+,-,\times\}$ steps.)

This might be asymptotically optimal, but proving $t(k!) \gg k^{1/2}$ (or even $t(k) \gg k^\theta$ for some $\theta>0$) seems to be beyond reach. Meanwhile, Lenstra's ECM (elliptic curve method) for factoring suggests that $t(ak!)$ can be as small as $\exp O(\sqrt{\log k\,})$. Turbo gave this link to a 2004 paper by Qi Cheng that spells out this connection; that's perhaps surprisingly late, since Lenstra's ECM paper dates back to 1987 $-$ I found some e-mails from 1996 where I noted that ECM suggests that some multiple of $k!$ can be computed in a number of operations subexponential in $\log k$, and I wouldn't be surprised if Lenstra himself noticed this some years earlier. Note that likewise the counterexamples involving $2^{16}-2^4$ etc. that I started with are in effect using Pollard's $p-1$ factorization method.

I tried to estimate how well this would work for $k = 10^7$ compared with the prime-factorization technique. There are $664579$ primes $p < 10^7$, so any route to $k!$ via prime factorization would have to take at least $2 \cdot 664579$ steps (one to reach each $p$ and one to multiply by it).
For the ECM approach to some multiple of $k!$, I tried the following experiment. For each of the first $96$ isogeny classes of rank-$1$ elliptic tables in Cremona's table (these being the first two columns of Table 2 on page 235 of his Algorithms for Modular Elliptic Curves, covering conductors $N \leq 220$), choose a curve $E_i$ and a generator $P_i$ ($i \leq 96$). Then, for each prime $p \leq 10^7$, factor the order of each $P_i \bmod p$ using the built-in gp command ellorder, factor it as $\prod_j l_j^{e_j}$, and note the minimal value $m(p)$ of $\max_j l_j^{e_j}$ over the $96$ choices of $(E_i,P_i)$; thus for each $p$ there's some $i$ for which the order of $P_i \bmod p$ is a product of prime powers $\leq m(p)$. This took a few hours. The largest $m(p)$ observed is $379$, for $p = 6978421$. But about 90% of these primes have $m(p) \leq 83$. (There are $67608$ primes $p\leq 10^7$ with $m(p)>83$; also $47193$ with $m(p)>100$ and $22518$ with $m(p)>113$.) There are $23$ primes $l \leq 83$; let $M = 2^6 3^4 5^2 7^2 \prod_{l=11}^{83} l$, and compute for each $i$ a nonzero multiple $D_i$ of the denominator of $M P_i$, which requires about $150$ group-law additions in $E_i$ because $M \approx 2^{122.6}$. Then form $\prod_{i=1}^{96} D_i$, multiply by the product of the $67608$ missing primes, and square the whole thing $23$ times to get a multiple of $10^7!$. I don't know how many arithmetic operations it takes these days to do an elliptic-curve addition or subtraction, but it must be under $40$, and this already puts us under half our estimate for computing $10^7!$ itself via prime factorization ($96 \cdot 150 \cdot 40 = 600000$). There's probably a significant additional factor to be saved by using more curves $E_i$, balancing the $m(p)$ cutoff, and choosing $E_i$ that allow for faster group operations such as Edwards curves.

Answer 2

$t(ak!)$ could have sub-exponential complexity (atleast in a randomized sense) at some $a\in\Bbb N$. Please refer interesting paper http://www.cs.ou.edu/~qcheng/paper/factorial.pdf.

My personal opinion is there is no polynomially many $\{+,-,\times\}$-operation algorithm to construct factorial in a deterministic sense.

However I do believe one of the two possibilities (possibly both) to be true:

1. The $exp(\sqrt{\log n})$ can be brought to $O((\log n)^c)$ in a randomized sense at a fixed $c>0$.

2. No deterministic algorithm can achieve $O((\log n)^c)$ $\{+,-,\times\}$-operations at any fixed $c>0$.

Answer 3

The post above has a link to the term-complexity measure based on size of a term computing a number. The following different model is from my memory of the BCSS paper, so verification would be appreciated.

For this problem, I define a computation string be a finite sequence of integers $a_i$, with $ 1 \leq i \leq n$, which obeys the following properties:

1. $a_1 = 1$
2. For every $i$ with $1 \lt i \leq n$, there is an allowed operation (say $++$) and indices $j$ and $k$ with $1 \leq j,k \lt i$ such that $a_i= a_j ++ a_k$. Note that $j$ can equal $k$.

Then over all such computation strings of varying lengths which contain an integer $s$, pick the shortest one, say of length $n$, and set $t(s)=n$.

Generally the allowed operations are total and are a fixed finite set, specified in advance. For the set with addition, subtraction, and multiplication, one can form at most $(n!)^23^n$ distinct computation strings of length $n+1$, and one can use associativity and commutativity to cut down on the bound. It is clear the largest number formed is $2^{2^n}$ in a computation string of length $n+1$. It is not clear that one can arrange a computation of $s$ of length $t(s)$ and at the same time avoid repeats as well as having $a_{i+1}$ depend on $a_i$ for all $1 \lt i \lt n$. Indeed one may need to compute two or three numbers of complexity $t$ and put them in the string for later use.

I hope to update this with a small program that does efficient listing of small computation strings, so that one can get an idea of how $t(n!)$ grows with $n$.

EDIT 2015.01.29 Awk code added to generate small computation strings

BEGIN{ SEP= "," ; SEP2 = ";" ; MAX = 40
heap[1]= SEP2 1  #empty computation string followed by possible values for next value
for(newidx=idx=1; newidx < MAX; idx++) {
   # read next computation string and possible next values
   split(heap[idx],stuff,SEP2) ; csqlen=split(substr(stuff[1],1+length(SEP)),csq,SEP)
   vlen=split(stuff[2],vs,SEP)
   for(i=1; i<= vlen; i++) {val=vs[i]
      scsqval=sortme(val); print "Sorted" scsqval
      if ( !(scsqval in db) ) { db[scsqval]=1; outv=""
         addvalues(val,val)
         for(j=1; j <= csqlen; j++) { addvalues((v=csq[j]), val) }
         for(j=1; j <= vlen; j++) { newvals[vs[j]]=1 }      
         ### remove redundant values
         for(j=1; j <= csqlen; j++) { if ((v=csq[j]) in newvals) delete newvals[v] }
         if (val in newvals) delete newvals[val]
         for (v in newvals) { outv = outv SEP v; delete newvals[v] }
         newidx++; heap[newidx] = stuff[1] SEP val SEP2 substr(outv,1+length(SEP))
         print heap[newidx] } }
    for (v in csq) delete csq[v]; for (v in vs) delete vs[v]; for (v in stuff) delete stuff[v]}
}  


function addvalues(a,b) {  newvals[a*b]=newvals[a+b]=newvals[a-b]=newvals[b-a]=1 }

function sortme(vv){ tmps=""
  for(ii=1; ii<=csqlen;ii++) ccsq[ii]=csq[ii]
  ccsq[(newlen=csqlen+1)]=vv
  for(ii=1; ii<=newlen;ii++)  for(jj=ii+1; jj <= newlen; jj++) {
          if (ccsq[ii] > ccsq[jj]) { t=ccsq[jj] ; ccsq[jj]=ccsq[ii] ; ccsq[ii]=t } }
  for(ii=1; ii<=newlen;ii++) {tmps = tmps SEP ccsq[ii] ; delete ccsq[ii] }
  return tmps }

END EDIT 2015.01.29

ADDED 2015.01.30

I am running computations to get strings of length 8. I invite verification of the following tuples $(i,t[i])$: (1,1) (2,2) (6,4) (24,5) (120,7) (720,7) (5040,8) .

Of course one has $t[n!]$ is less than $2n$, and by using prime powers and certain assumptions on the distribution of primes, one can likely prove that for every $\epsilon$ there is $n_0$ so that for $n > n_0$ one has $t[n!] \lt (1 + \epsilon) n$. If one did not have subtraction, it might be possible to prove a linear in $n$ lower bound on $t[n!]$.

The number of computationally distinct terms (I identify permuted strings) follows the pattern (1,1) (2,2), (3,3) (4,7) (5,25) (6,115) (7,714) (8,x) where x is at least 2403. If anyone verifies these numbers, I invite them to make an OEIS entry.

END ADDED 2015.01.30

Gerhard "Ask Me About Small Programming" Paseman, 2015.01.27

Answer 4

(Added 2015-02-01)

Perhaps the most relevant part of this answer is the reference to A217032, which gives the following values for $t(n!)$, $1 \le n \le 19$: $$1,2,4,5,7,7,8,9,9,10,10,11,12,12,13,13,13,14,14.$$

The problem whether $t(n!)$ can be bounded by a polynomial in $\log n$ (in the paper by Shub and Smale, see near the bottom of this answer) must be open, since a positive answer would imply a polynomial time factorization algorithm (assuming a straight-line program for $n!$ can also be constructed in time polynomial in $\log n$).

---

My comments to Gerhard Paseman's answer get a bit many and long, so it may be better to put all of this together in an answer.

I use the following Magma code to find all possible computations up to a given length.

step := func<s | {t : a, b in s, f in ['+','-','*'] | #t gt #s where t := Include(s, f(a,b))}>; gens := [{{1}}]; for n := 2 to 8 do l := gens[#gens]; Append(~gens, &join{step(s) : s in l}); end for;

The result of the computation is a set of integers; the next step adds an element that is a sum, difference or product of two elements in the set. I keep only sets that are larger than before, i.e., computations that do not repeat numbers. The numbers of these sets for lengths 1 to 8 are

1, 2, 5, 20, 149, 1852, 34354, 873386.

The counts for the number of distinct integers that can be computed are

1, 3, 6, 13, 38, 153, 867, 6930.

The factorials $n!$ first show up at step 1, 2, 4, 5, 7, 7, 8 (for $1 \le n \le 7$). No other factorial occurs up to length 8.

There are two computations of length 4 that compute 6: (1, 2, 3, 6) and (1, 2, 4, 6).

There is only one of length 5 for 24: (1, 2, 4, 6, 24).

There are close to 50 computations of length 7 for 120, but only five for 720:

(1, 2, 3, 9, 27, 729, 720), (1, 2, 3, 9, 81, 729, 720), (1, 2, 3, 9, 81, 80, 720), (1, 2, 4, 6, 24, 30, 720) and (1, 2, 4, 16, 20, 36, 720).

(All of this up to permutation.) There are 20 computations of length 8 of 5040, some of them containing 8 and 72, for example (1, 2, 4, 8, 9, 72, 70, 5040). It follows that $t(8!) = t(9!) = 9$. In fact, there are 94 computations of $8!$ and 18 of $9!$. I did run through all length-9 computations to check that (and also that $10!$ does not show up, so $t(10!) \ge 10$), generating them from the length-8 sets in gens[8], which took a few minutes, but I couldn't save all length-9 computation sets, because there are too many.

Added later: $t(10!) = 10$, one possibility being $(1,2,3,5,7,12,144,720,720^2,10!)$.

Further results:

• For all $n \ge 10$, $t(n!) \ge 10$.
• $t(11!) = 10$, for example $(1,2,3,9,81,80,77,720,720^2,11!)$

---

Thomas Sauvaget in the comment below points out that the sequence 1, 3, 6, 13, 38, ... mentioned above is A216999 in the OEIS (see also A173419). The OEIS links to this paper by Shub and Smale [this is probably what the book [BCS+97] that is mentioned in the Question refers to], where the following problem is formulated on page 3:

Problem. Is there a constant $c$ such that $$\tau(k!) \le (\log k)^c$$ for all $k$?

Their $\tau(n)$ is our $t(n)$. This is then related to the "intractability" of the Hilbert Nullstellensatz over $\mathbb C$.

From looking at the references to this paper in MathSciNet, my impression is that this problem is still open, but it is hard to know for sure.

The sequence $(t(n!)-1)$ is A217032. This gives the following values for $t(n!)$, $1 \le n \le 19$: $$1,2,4,5,7,7,8,9,9,10,10,11,12,12,13,13,13,14,14.$$ (Which is consistent with the data I have computed, but goes quite a bit further.)

Answer 5

Here is partial result about multiple of factorial based on heuristic code.

By the paper Michael Stoll cites,

$t(m) \le 2 \log{m}$.

By repeated squaring $t(a^{2^k}) \le t(a)+k$.

Let $M=\log{n}$ and $S=\{a \cdot b^{2^k}+c : 1\le a \le 2M, 1\le b\le 2M, - 2M \le c \le 2M, 0\le k \le M\}$.

First we try to compute primorial $n$ and then square few times.

Members of $S$ can be computed in polynomial in $\log{n}$ time.

So it depends if few members of $S$ contain all primes $\le n$.

Let $\{P\}$ be the set of primes $\le n$.

Greedy Algorithm 1. For $ a,b \in S$ and $c= a \{+,-,\times\} b$ find the $c$ which is divisible by largest number of members of $P$. Keep $c$ and remove the primes from $P$. Repeat. Terminate when $P$ is empty. I can't prove this always terminate ;).

Certainly $S$ can be extended by the other answers.

Here is algorithm (1) for multiples of $45\#$ and $55\#$:

sage: greedyfactorial(45,planc=False,allb=1)
#S= 1637
1 9 [2, 3, 5, 7, 11, 13, 17, 31, 41] -340282366920938463463374607431768211200 = (1*2^8+0)-(1*2^128+0)
early 2 5 [19, 23, 29, 37, 43] 10301051460877537454126135158480 = (1*5^16+6)+(3*3^64+6)
sage: greedyfactorial(55,planc=False,allb=1)
#S= 5821
1 11 [2, 3, 5, 7, 11, 13, 17, 19, 31, 37, 41] -39402006196394479212279040100143613805079739270465446667948293404245721771497210611414266254884915640806627973529600 = (1*2^24+0)-(1*2^384+0)
2 4 [23, 29, 47, 53] 19295810734578656668031216686940366563098640636282442092649989 = (6*2^8+1)*(2*2^192+5)
early 3 1 [43] 258 = 1+(1*2^8+1)

Sage code written in a hurry:

def greedyfactorial(n,deg=2,allb=True,planc=False):
    pri=list(primes(2,n+1)) #primorial
    k=floor(log(n))^deg
    lk=2*floor(log(n))
    pri1=[ 0 .. lk ]        
    pows=[]
    for p in pri1:
        if p==0:  continue
        for e in [ 2 .. lk]:
            pows += [p**(2**e)]
    pri1=[(i,str(i)) for i in pri1[:]]
    S=pri1[:]
    ca={}
    for p,_ in S:  ca[p]=1

    for p,_ in pri1:
      for q,_ in pri1:
        for b in pows:
            T=p*b+q
            if T in ca:  continue
            ca[T]=1
            S += [(p*b+q,'('+str(p)+'*'+str(factor(b))+ '+'+str(q)+')')]
            T=p*b-q
            if T in ca:  continue
            ca[T]=1
            S += [(p*b+q,'('+str(p)+'*'+str(factor(b))+ '-'+str(q)+')')]
    S=[(i,j) for i,j in S if i!=0]
    B=[(1,'1')]
    if allb:  B=S

    ops2=[ (lambda x,y:  x*y,'*'),(lambda x,y:  x + y,'+'), (lambda x,y:   x - y,'-')]
    print '#S=',len(S)
    def countp(A,S):
        r=[]
        for p in S:
            if A%p==0:  r += [p]
        return r    

    S=uniq(S)

    for ste in [ 1 .. k]:
        ma,br,BA=0,[],0
        for a,an in S:
            #for b,bn in S:
            for b,bn in B:
                for f,o in ops2:
                    A=f(a,b)
                    if A==0:  continue
                    r=countp(A,pri)
                    if len(r)>ma:
                        br=r
                        bs=an+o+bn
                        ma=len(r)
                        BA=A
                        if ma==len(pri):
                            print 'early',ste,ma,br,BA,'=',bs
                            return
                    if planc and ma>=len(pri)//2:  break    
                if planc and ma>=len(pri)//2:  break    

        print ste,ma,br,BA,'=',bs
        pri=[p for p in pri if not p in br]
        if pri==[]:
            print ' Done'
            return