# J. Maurice Rojas, Jan. 15, 2002 # Happy New Year! # # Last update: Apr. 7, 2003 # Digits:=40; c:=exp(1)/(exp(1)-1) ; addd:=(d,p,s)-> if s=0 then 1 # monos have at most one affine root elif s=1 then 1+ d*p*(p^d-1)/(p-1) # binoms have at most 1+B(L,2,1) roots... elif s=2 then 1+d*p*(p^d-1)*(1+4*c*(p^d-1)*(1+d*log(2*d/log(p))/log(p)))/(p-1) # really 1+B(L,2,1)+B(L,2,1)B(L,3,1) else 1+d*p*(p^d-1)*(1+4*c*(p^d-1)*(1+d*log(2*d/log(p))/log(p)))/(p-1) + sum((p^d-1)^k *floor(k*6^(k-1)*c^k*(1+d*log(d/log(p))/log(p)) *(1+d*log(2*d/log(p))/log(p))^(k-1) * (k!)),k=3..s); end if: ad:=(d,p,s)-> addd(d,p,s) : addd2:=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(L,2,1) roots... elif s=2 then 1+2*(1+6) # really 1+B(L,2,1)+B(L,2,1)B(L,3,1) else 15 + sum(3^(k-1) * floor(k*2^(k-1)*c^k*(1-log(log(2))/log(2)) *(2-log(log(2))/log(2))^(k-1) * (k!)),k=3..s); end if: ad2:=s-> addd2(s) : # ad(s) is our bound from theorem 4... # ad2(s) is the bound refined with the lenstra p=2 info... printf("The additive complexity bound from Theorem 1 reduces to\n %d , %d , %d , %d , %d, respectively, for\n sigma = %d , %d , %d , %d , %d\n When p=2 and d=1.\n\n", ad2(0),ad2(1),ad2(2),ad2(3),ad2(4),0,1,2,3,4) ; # simplified version below... # Risler's bound below... risler:= s-> (s+2)^(3*s+1)*2^((9*s^2+5*s+2)/2);