Re: q-polynomials (linearized polynomials, or p-polynomials) in PARI/GP?

[Claus Fieker <claus@maths.usyd.edu.au>]

On Thu, May 07, 2009 at 02:13:46PM +0200, Bill Allombert wrote:
> On Thu, May 07, 2009 at 01:47:17PM +0300, Aurimas Fi?eras wrote:
> > Hello,
> > I'm writing some algorithms that deal with q-polynomials ([Ore33],
> > [LN84]). If I store them in PARI as regular polynomials they take a lot
> > of space (e.g. q-degree=10 2-polynomial is stored internally as degree
> > 1024 pol[mod]).
> > 
> > However, if I store them as vectors, (where vector's component number
> > represent q-degree, and vector holds only coefficients (variable x is
> > presumed), i=pos-1, x^(q^i) + x^(q^i) + ...) all operations with them
> > are quite difficult to perform.
> > 
> > For example:
> > simple substitution with regular polynomial:
> > Px=x^4+2*x^2+3*x;
> > a=2;
> > subst(Px, x, a);
> > %1 = 30
> > 
> > same 2-polynomial efficiently coded as vector:
> > qPx=[3,2,1];
> > res=0;for(i=1,length(qPx),res+= qPx[i] * a^(2^(i-1)));
> > res
> > %2 = 30
> > 
> > 1. Is there a more elegant way to work with q-polinomials in PARI?
> 
> I would suggest the function
> qexpand(x,q,n)=
> {
>   local(V=vectorv(n));
>   V[1]=x;
>   for(i=2,n,V[i]=V[i-1]^q);
>   V
> }
> Then you can do
> qeval(P,x,q)=P*qexpand(x,q,#P)
> 
> 
> > 2. Is there any other computer algebra system that can work natively
> > with q-polynomials (I couldn't find any)?
> 
> You might try a computer algebra system that handle sparse multivariate
> polynomials and treat your q-polynomials as sparse polynomials.
> 
Depends on what exactly you mean by q-polynomials and their operations.
They occur naturally as additive polynomials and as endomorphisms in
char. p in the Drinfeld theory for function fields as well as as twisted
polynimials (or skew polynomials) in coding theory. Elementary
operations motivated from here are available in Magma
http://magma.maths.usyd.edu.au

Greetings
 Claus

PS.: I do know this is the pari-dev list, but he asked... 
> Cheers,
> Bill.
>