From: rusin@math.niu.edu (Dave Rusin)
Subject: Re: a question about polynomials
Date: 28 Jan 01 03:37:08 GMT
Newsgroups: sci.math.numberthy
Summary: Action of Steenrod algebra on polynomial rings over finite fields

susan.landau@East.Sun.COM recently wrote to NMBRTHRY,
>Do you know anything about the following question: I am given f(x) of
>degree n over Z/pZ, where p is very large (100 digits) and n is reasonably
>large (10^5) and f(x)-c is a product of linear factors.  I want to find
>c, or a linear factor of f(x)-c, and I want to do it quickly (e.g. in time
>polynomial in n, log p).  Now c may not be unique, though in general it
>will be.  I'm happy with an algorithm that solves this problem when given
>f, c is unique, or which finds a solution --- but not necessarily the right
>one --- when c is not unique.
>
>Do you know any work in the area of polynomials that are products of
>linears mod p for large p that might apply?


Here's a response which is more an answer to the last question than to
the specific task at hand.

If  F  is of characteristic  p  and  R = F [ x1, x2, ... x_k ]  is a
polynomial ring over  R,  we may define ring homomorphisms  phi : R --> R
by stating the action on  F  and on each  x_i.  For each power  q  of  p
we may define such a ring map  phi  by

    phi(a) = a^q  for  a  in  F
    phi(x_i) = x_i + x_i^q  for each  i.

This map has the property that  phi( L ) = L + L^q  for each linear form
in the  x_i's  whose coefficients lie in  GF(q). It also has the virtue
of being easily computable; if  f  is a homogeneous form in the variables
x_i  of degree  k, then  phi(f) = f + phi_1(f) + phi_2(f) + ...  where
phi_i(f)  is homogeneous of degree  k + i(q-1) :

    phi_0(f) = f
    phi_1(f) = df/dx1 * x1^q  +  df/dx2 * x2^q  +  df/dx3 * x3^q  +  ...
    phi_2(f) = (1/2)(d^2f/dx1^2)(x1)^(2q) etc.

The highest-degree nonzero form will be  phi_k(f) = f^q.
Since  phi  is a ring homomorphism, if  f  factors into
linear factors  L_i  over  GF(q)  we must have

    phi(f) = \prod ( L_i + L_i ^ q )
           = f * \prod ( 1 + L_i ^ (q-1) )
           = f  +  f * \sum ( L_i ^ (q-1) )  +  ...

In other words, each of the other forms  phi_i(f)  is divisible by  f.
(I'm not sure how much larger is the gcd of all these  phi_i(f)  than
the polynomial corresponding to all the roots of  f  lying in  GF(q). )

So there you have what was requested:
> work in the area of polynomials that are products of linears mod p
These maps  phi_i  and their composites are known to topologists as
the Steenrod algebra (at least in the case  q = p).

Unfortunately I can't quite see how to use this effectively.
We can freely pass from polynomials in one variable to forms in two.
So to apply to the problem at hand, "all" we need to do is to determine
the values of  c  for which  f(x,y) - c y^n  divides
    (df/dx)(x^p) + (df/dy)(y^p) - c n y^(n-1+p).
But I don't know how to do this efficiently. Passing back to a 1-variable
problem we can view this as reducing something like
(f'(x))(x^p) + g(x) - c n  with a relation
x^n = (x^n - f(x)) + c   to obtain a polynomial of degree less than  x
in  n  whose coefficients are supposed to vanish; this will give
polynomial relations binding  c.  The good news is that the reduction
can be done with something like  O(log p)  steps; the bad news is that
each step requires dragging around polynomials in  c  whose degree
will be comparable to  p.  So I don't think these ideas have yet
provided an answer to the original problem.

dave