The straight line complexity of small factorials and primorials

In this paper we determine the straight-line complexity of $n!$ for $n\leq 22$ and give bounds for the complexities up to $n=46$. In the same way we determine the straight-line complexity of the product of the first primes up to $p=31$ and gives bounds for $p\leq 43$. Our results are based on an exhaustive computer search of the short length straight-line programs.


Introduction
In [SS95] Shub and Smale studied the complexity of a number of different algebraic problems in terms of the number of ring operations needed to compute a given ring element by a straight line program. A straight line program for for an integer y can be described as a sequence of tuples x k = (x i • x j ), where i ≤ j < k, x 1 = 1, • can be any of +, −, ×, and the final element x f is equal to y. The smallest integer f such that there exists a straight line program of length f is called the straight line complexity, or cost, of y and is denoted by τ (y) In [BSS89] a general complexity theory for computation over rings was introduced, see also [BCSS98], and the results from [SS95] implies that if the ultimate complexity of n!, here denoted as τ ′ (y), defined as the minimum τ (y) for all y which are integer multiples of n!, is less than (log n) c for some constant c, then P = N P for computation over the complex numbers, and otherwise P = N P . The existence of such a constant c would among other things provide a fast algorithm for factoring integers, see the discussion in [Che04, Che03], and the non-existence would provide strong lower bound for several important problems in complexity theory, see [Bür09] and [Koi04].
The results of [SS95,dMS96,dAM97] provide upper and lower bounds for the straight line complexity of general integers and imply that for most integers τ (n) is not O(p(log log n)) for any polynomial p. In [LSZ82] similar bounds were derived for functions over finite fields. The known bounds for a general integer n are log 2 (log 2 n) + 1 ≤ τ (n) ≤ 2 log 2 n (1) The lower bound is optimal since τ (2 2 k ) = k + 1. The upper bound is achieved by first computing the necessary powers of 2 and then adding them according to the binary expansion of n For specific integers, such as n!, there are few results which strengthen the general bounds. However for n! Cheng derived an improved algorithm, conditional on a conjecture regarding the distribution of smooth integers, and earlier [Str77] a weaker, unconditional, bound was derived by Strassen.
The purpose of this short note is to report the exact values of τ ′ (n!) for small values of n and likewise for τ ′ (p#), where p# is the primorial, which is the product of all primes less than or equal to p. It is easy to see that given a short straight line program for p# we can also find one for n! by using repeated squaring. Our results were obtained by first doing an exhaustive computer search of all straight line program up to a given length, followed by an extended search adapted to finding program for n! and p#.
Most of the material in this note was originally part of a longer paper but while preparing that paper the author found out that the non-computational results were already covered by other recently published papers. That was nearly ten years ago but given the slow progress on problems in this area we hope that these exact results and bounds will help draw attention to the problems and stimulate interest among new researchers. The only additions to the material from the older paper is a recomputation of all data using a newly written program and as a result of this an improvement of some of the lower bounds.
2 Searching for optimal straight line programs  2. Reduce the set of all such programs by removing redundant programs 3. Repeat step 1 and 2 for as large k as possible.
In step 2 we removed all programs in which x k was a number which was also x j for some j < k. For every sequence of numbers (x 1 , . . . , x k ) we kept only one of the programs which computed a permutation of this sequence. We also deleted all program which had x k ≤ 0. The computer resources at hand allowed us to continue this process up to k = 9. In Figure 1 we display some statistics for these programs. We say that an integer y has been reached if there is a straight line program of length at most k which computes y and that y has been covered if y is a divisor of x j for some j ≤ k. We also include the length of the longest interval of the form [1, . . . , x] in which all integers have been reached or covered. After these programs had been found a second search stage was done, with the specific aim. For each n such that τ ′ (n!) ≥ 10 each program of length 9 was extended in a depth first search. During the search every program in which the largest number was not large enough to given a multiple of n! was pruned from the search, as were methods which could not be optimal due to repeated values. Here each program was extended to k = 12, but the number of programs was too large to save so only those which computed a multiple of n! were recorded. Thus all relevant programs of length 12 have been searched, providing us with a lower bound for τ ′ (n!).
The optimal methods are noticeably better than then upper bound for τ (n!) given in 1. The method of Strassen [Str77] gives a bound τ (n!) = O( √ n log 2 n), which seems to deviate more and more from the optimal methods for larger n. The conditional method of Cheng [Che04] has a complexity of the form O(exp(c √ log n log log n)), which certainly seems compatible with the results for small n, but is so sensistive to the value of the constant c that very little can be said based on small values of n.
The same depth first search was done in order to extend the optimal programs of length 12 found for each factorial, as well as few heuristically chosen ones, in an attempt to find short programs for larger factorials as well. In Figure  2 we show the exact values for τ ′ (n!) for n ≤ 22 and for each such n an example of an optimal straight line program. For larger n we display the best method found by our partial search. The final columns states whether the method is optimal or not, and otherwise the lowest possible value.
Finally a similar extension search was performed in order to find optimal methods for the primorials p#. The resulting values and programs are displayed in Figure 3