p-th powers in characteristic p

edward · Sun Feb 12, 2012 1:19 am

Hi!

I am doing some calculations that involve taking very large polynomials and raising them to p-th powers in a field with characteristic p. The length of time it is taking leads me to believe that Singular is not using the fact that (x+y)^p = x^p + y^p in char p.

Is there some library or easy way to get Singular to do p-th powers of a polynomial in char p?

Thanks so much!

Edward

Re: p-th powers in characteristic p

steenpass · Mon Feb 13, 2012 8:26 am

Hi,

as far as I know, you're right, Singular doesn't use this fact and there is no built-in command nor library to compute such powers in the way you want. But it is easy to write such a procedure:

Code:

proc toThePowerOfChar(poly f)
{
  poly g;
  int p = char(basering);
  int i;
  for(i = size(f); i > 0; i--)
  {
    g = g+f[i]^p;
  }
  return(g);
}

This speeds up the computation a lot:

Code:

> system("--ticks-per-sec", 1000);
> ring r = 1009, (x,y,z), dp;
> poly f = x+y+z;
> int t = timer;
> f^char(basering);
x1009+y1009+z1009
> timer-t;
18650
> t = timer;
> poly h = toThePowerOfChar(f);
> timer-t;
10

Of course, it depends on your applications whether or not this helps in your case.

Best regards,
Andreas

Re: p-th powers in characteristic p

gorzel · Mon Feb 13, 2012 3:49 pm

In your particular, where case char(basering)=p>0, it holds:

raising the polynomial f to the p-th power commutes with
raising the variables to the p-th power.

This is, f^p is obtained instantly by:

Code:

> int p = char(basering);
> subst(f,x,x^p,y,y^p,z,z^p);

(In any case, at most, you have to cycle in a for-loop over var(1),...,var(n),
n=nvars(basering) but not over the single terms N=size(f)).

Don't care too much about the warnings (about possible overflow in the expont) which may appear.
(The warning refers to the total degree but not to the degree of the individual variables.)

You may also use the command substitite, which can be used for simultaneous substitution.
Here (at the moment) the warning does not occur.

Code:

> LIB "poly.linb";
> substitute(f,maxideal(1),ideal(x^p,y^p,z^p));

However, if your polynomial is huge with respect to the number of
monomials, then substitute may be a bit slower than subst,
since substitute is a proc and for this function-call the input
will be copied. If this is critical for you, then use map directly as substiute does.

Re: p-th powers in characteristic p

edward · Mon Feb 13, 2012 5:45 pm

Thanks steenpass and gorzel, this helps a lot!

Edward

Re: p-th powers in characteristic p

gorzel · Mon Feb 13, 2012 11:47 pm

In my answer I made the assumption that, as in the examples, the coefficients are 1.
Otherwise, it does not work in general as I proposed.