############################################### # # # Number of irreducible polynomials # # in several variables # # over finite fields # # # # # # Arnaud Bodin # # # # 2007/06/11 # # # ############################################### # This a library for Maple # See the file irredu.mw for use and examples # And the article for explanations. # The following variables should be already defined # mm : number of variables (say mm:=2;) # qq : cardinality of the filed (say qq := 2;) # ddmax : maximal degree for computations (say ddmax := 10;) # The following variables R is defined # It is table where entry R(k,d) is the number of polynomials # of degree d having exactly k factors. # Hence R(1,k) is the number I(d) of irreducible polynomials of degree d # This table is completed with the procedure ComputeAll(); R := matrix(ddmax,ddmax,0): # Main functions and procedures : # N(d); number of polynomials of degree d # TorsionProduct(L); the torsion product of a list of integers # Enumeration(k,d); list of all partition of d in k summands # Decomp(); return a table where entry (k,d) is Enumeration(k,d) # ComputeAll(); Main procedure, fill the matrix R # Estimation(); Compare I(d)/R(d) with its approximation with(linalg): # Number of polynomials N := d-> (qq^(binomial(mm+d-1,d))-1)*qq^(binomial(mm+d-1,d-1))/(qq-1): # Initialisation of the first term R[1,1] := N(1): # Torsion product PreTorsionProduct := proc(M) local myprod, i; myprod := 1; for i from 1 to coldim(M) do myprod := myprod * binomial(M[1,i]+M[2,i]-1,M[2,i]); end do; return(myprod); end proc: TransformList := proc(L) local i,ii,n,L1,L2,M; ii := 1; n:= 1; L1 := []; L2 := []; for i from 2 to nops(L) do if (L[i-1]<>L[i]) then L1 := [op(L1),L[i-1]]; L2 := [op(L2), n]; n := 1; else n := n+1; end if; end do; L1 := [op(L1),L[nops(L)]]; L2 := [op(L2), n]; M := matrix([L1,L2]); return(M); end proc: TorsionProduct := proc(L) local myprod,M; M := TransformList(L); myprod := PreTorsionProduct(M); return(myprod); end proc: # Enumeration of all list with k elements and sum equals to d (k <= d) Enumeration := proc(k,d) local i,j,L,LL,ret,s, Dec, count; L := [seq(1,i=1..(k-1))]; count := 1; Dec := []; while ((count < 100000) and (L[1]*(k-1) <= d)) do while (add(i, i=L) < d) do s := add(j,j=L); if (d-s >= L[k-1]) then LL := [op(L),d-s]; Dec := [op(Dec),LL]; end if; L[k-1] := L[k-1]+1; end do; ret := k-1; while ((add(i, i=L)>= d) and (ret>1)) do ret := ret-1; L[ret] := L[ret]+1; for j from ret to nops(L) do L[j] := L[ret]; end do; end do; count := count+1; end do; return(Dec); end proc: # Table of all possible decompositions Decomp := proc() local k,d,DD,L; global ddmax; for d from 1 to ddmax do L := [d]; DD[1,d] := [op([op(L)])]; # print(1,d,DD[1,d]); end do; for k from 2 to ddmax do for d from k to ddmax do DD[k,d] := [op(Enumeration(k,d))]; # print(k,d,DD[k,d]); end do; end do; return(DD); end proc: Substitution := proc(L) local i,LL; LL := []; for i from 1 to nops(L) do LL := [op(LL),R[1,L[i]]]; end do; return(LL); end proc: Reducible := proc(k,d) local i,j,s, D,L,LL; global DD; s := 0; D := DD[k,d]; for i from 1 to nops(D) do L := D[i]; LL := Substitution(L); s := s + TorsionProduct(LL); end do; return(s); end proc: # Main procedure ComputeAll := proc() local k,d; global R, ddmax; for d from 2 to ddmax do R[1,d] := N(d): for k from d to 2 by -1 do R[k,d] := Reducible(k,d); R[1,d] := R[1,d] - R[k,d]: end do; end do; return(); end proc: # Estimation Estimation := proc() local d; for d from 1 to ddmax do print(`d = `, d , ` N(d) = `, N(d), ` I(d) = `, R[1,d], ` I(d)/N(d) = `, evalf(R[1,d]/N(d)), ` Approx(d) = `, evalf(1-(qq^(mm+1)-qq)/(qq^(binomial(mm+d-1,mm-1))))); end do; end proc: EstimationShort := proc() local d; print(`d I(d)/N(d) Approx(d) `); for d from 2 to ddmax do print(d,` `, evalf(R[1,d]/N(d)),` `, evalf(1-((qq^(mm+1)-qq)/(qq-1))/(qq^(binomial(mm+d-1,mm-1))))); end do; end proc: print(`Are now available the following functions`); print(`N(d); TorsionProduct(L); Enumeration(k,d)`);; print(`Decomp(); ComputeAll(); Estimation()`);