#C17.txt (March 24, 2016) Littlewood polynoials and Rudin-Shapiro polynomials Help:=proc(): print(` Pn(n,z), ChampS(n,z) , P(n,z), Q(n,z), Check3(n) , HM(k,r) `): print(`SeqHM(K,r), GRc(L) `): end: #studff from C7.txt #RecToSeq(R,N): inputs a C-finite sequence [ini,rec] where ini is a list #of numbers of length k say, and rec is a list of coefficients of the #C-finite sequence defined UNIQELY by #x(n)=ini[n+1], for n=0..k-1, #and rec is a list of numbers [c1,c2,...,ck] #and for n>=k defined recursively by #x(n)=c1*x(n-1)+c2*x(n-2)+...+ck*x(n-k). #For example the sequence 2^n is coded as #[[1],[2]], and the sequence of Fib. numbers are given by #[[0,1],[1,1]] #It outputs the list consisting of the first N terms of that sequence starting at n=0 RecToSeq:=proc(R,N) local ini,rec,Se,k,n,nt: ini:=R[1]: rec:=R[2]: k:=nops(ini): if nops(rec)<>k then RETURN(FAIL): fi: Se:=ini: for n from k+1 to N do #nt:=c1*Se[n]+c2*Se[n-1]+...+ ck*se[n-k+1] nt:=add(rec[i]*Se[n-i],i=1..k): Se:=[op(Se),nt]: od: Se: end: #Pn(n,z): the set of all poly in z of degree n whose coefficients are +1 or -1 Pn:=proc(n,z) local S,p: option remember: if n=0 then RETURN({1}): fi: S:=Pn(n-1,z): {seq(p+z^n,p in S), seq(p-z^n,p in S)}: end: #ChampS(n,z): the set of Littlewood polynomials of degree n whose maximum on the #unit circle as small as possible and as big as possible, as well as the #actual maxx and min ChampS:=proc(n,z) local S, reco, cham,i,hope: S:=Pn(n,z): cham:={S[1]}: reco:= maximize( abs(subs(z=exp(I*t),S[1])),t=0..2*Pi): for i from 2 to nops(S) do hope:=maximize( abs(subs(z=exp(I*t),S[i])),t=0..2*Pi): if evalf(hope)(nops(L)-4)/2 then print(`Not enough data`): RETURN(FAIL): fi: ini:=[op(1..k,L)]: rec:=[seq(c[i],i=1..k)]: var:={seq(c[i],i=1..k)}: #L[n]=c1*L[n-1]+ ... + ck*L[n-k] eq:={ seq(L[n]-add(c[i]*L[n-i],i=1..k),n=k+1..2*k+4)}: var1:=solve(eq,var): if var1=NULL then RETURN(FAIL): fi: R:=[ini,subs(var1,rec)]: if RecToSeq(R,nops(L))<>L then RETURN(FAIL): fi: R: end: #GRc(L): inputs a list of rational numbers L and tries to find a linear #recurrence equation with constant coefficient in the form [ini,rec] #where rec=[c1,..., ck], and the recurrence is #x(n)=c1*x(n-1)+...+ck*x(n-k) GRc:=proc(L) local k,R: for k from 1 to (nops(L)-4)/2 do R:=GRc1(L,k): if R<>FAIL then RETURN(R): fi: od: FAIL: end: