# J. Maurice Rojas, Oct. 31, 2001 # Happy Halloween! # # Last update: Jan. 27, 2003 # c:=exp(1)/(exp(1)-1) ; u:=(m,n)-> if n=1 then m-1 elif n=2 then max(m-2,3*m-9)^2 else ((m+1-n)*(m-n)/2)^n end if; # the function below gives the maximal # number of edges for a 3-polytope in R^3 # with m vertices... e:= m-> if m=1 then 0 elif m=2 then 1 elif m=3 then 3 else 3*(m-2) end if : E:=(m1,m2)-> e(m1)*e(m2) : ff:= (m1,m2)-> E(m1,m2)*floor(c^2*2^2*(m1-1)*(1+log((m1-1)/log(2))/log(2))*(m2-1)*(1+log((m2-1)/log(2))/log(2))): f:= (m1,m2)-> ff(m1,m2) : gg:= (m,n)-> u(m,n)*floor((c*(m-n)*n*(1+log((m-n)/log(2))/log(2)))^n) : g:= (m,n)-> gg(m,n) : h:= m-> 4*(2^m-2) : # f is the bound for B(Q_2,m,2) (assuming 2 equations # where the first has m1 terms and the second has m2 terms) from corollary 1. # g is the bound for B(Q_2,m,n) from theorem 1. # h is the real analytic bound mentioned in example 1. # double-letter versions are the same thing without the floor... Digits:=4; printf("The bound from Example 1 of the introduction (Pg. 3) should read something like...\n"); evalf(gg(m+2,2)); printf("The bound from Remark 7 of Section 3 (Pg. 14) should read something like...\n"); evalf(ff(3,m)); printf("The bound from Example 6 of Section 3.1 (Pg. 15) should be...\n"); evalf(ff(3,2)); # asymptotically, f (m-1)*floor(c*(m-1)*(1+log((m-1)/log(2))/log(2))):# this is B(L,m,1)... # Below is B(L,m,n) in the special case of (3,...,3,2) for the # vector of monomial terms, and (2,3,4,...,s,s) for the number # of variables occuring in the ith poly... bq322ss:=s-> 3^(s-1)*floor(c^s * (2*2*c2)*(1*s*c1)*product(2*k*c2,k=3..s)); # bq322ss:=s-> 3^(s-1) *c^s * (2*2*c2)*(1*s*c1) # *product(2*k*c2,k=3..s); addd:=s-> if s=0 then 1 # monos have at most one affine root elif s=1 then 1+2 # binoms have at most 1+B(Q_2,2,1) roots... elif s=2 then 1+2+2*6 # really 1+B(Q_2,2,1)+B(Q_2,2,1)B(Q_2,3,1) else 1+2+2*6+sum(bq322ss(k),k=3..s); end if: ad:=s-> floor(addd(s)) : # ad(s) is our bound from theorem 4... printf("The additive complexity bound from Theorem 4 reduces to\n %d , %d , %d , %d , %d, respectively, for\n sigma = %d , %d , %d , %d , %d\n\n", ad(0),ad(1),ad(2),ad(3),ad(4),0,1,2,3,4) ; # simplified version below... Digits:=4: cc:=6*c2*c: ccc:=c1*c/(cc-1): printf("The simplified bound from Theorem 4 should read something like...\n") ; evalf(15+ccc*cc^sigma*sigma*sigma!); # Risler's bound below... risler:= s-> (s+2)^(3*s+1)*2^((9*s^2+5*s+2)/2): Digits:=30: printf("Risler's best bound for sigma = 0,1,2,3,4 (after Theorem 4 on Pg. 9)\n reduce to... %d , %d , %d , %d ,\n and %d\n",risler(0),risler(1),risler(2),risler(3),risler(4)) ;