Singular Procedure: Vanishing polynomial function (A Singular Introduction to Commutative Algebra)
Before anything else, beware that the desired procedure itself demands exorbitant amounts of runtime: For given values $p$ and $d$, if $d\geq p $ the output consists of $p^{d-p+1}$ polynomials over $\Bbb{F}_p$, requiring a total of $$(d+1)p^{d-p+1},$$ elements of $\Bbb{F}_p$ to represent. As the size of the desired output is exponential in $d$, certainly the runtime will at least exponential.
As for an effective algorithm; as you note a polynomial with coefficients in $\Bbb{F}_p$ vanishes on $\Bbb{F}_p$ if and only if it is divisible by $X^p-X$. Polynomial long division shows that mod $X^p-X$ we have $X^i\equiv X^{i+(p-1)}$ for all $i\geq 1$, and so for an arbitrary polynomial $f=\sum_{i=0}^d c_iX^i\in\Bbb{F}_p[X]$ we have $$f\equiv c_0+\sum_{i=1}^{p-1}\left(\sum_{j\geq0}c_{i+(p-1)j}\right)X^i\pmod{X^p-X}.$$ This shows that $f$ vanishes if and only if $c_0=0$ and $\sum_{j\geq0}c_{i+(p-1)j}=0$ for all $i\in\{1,\ldots,p-1\}$.
In particular, if $d\leq p-1$ then this shows that $f\equiv0$, so there are no such polynomials for $d<p$, except perhaps $d=0$ if you consider the zero polynomial to have degree $0$. If $d\geq p$ then the constraints on the coefficients are equivalent to $$c_0=0\qquad\text{ and }\qquad c_i=-\sum_{j\geq1}c_{i+(p-1)j}\quad\text{ for all }\quad i\in\{1,\ldots,p-1\}.$$ In other words, the first $p$ coefficients of $f$ are uniquely determined by the remaining coefficients of $f$, and there are no constraints on the remaining coefficients of $f$. So every choice of coefficients $c_p,c_{p+1},\ldots,c_d\in\Bbb{F}_p$ (with $c_d\neq0$) yields a unique polynomail of degree $d$ that vanishes on $\Bbb{F}_p$. This yields the following algorithm:
- For $c_p,c_{p+1},\ldots,c_{d-1}$ in $\Bbb{F}_p$ and $c_d\in\Bbb{F}_p^{\times}$:
- $\qquad$For $i$ in $\{1,\ldots,p-1\}$
- $\qquad\qquad$Set $c_i:=-\sum_{j\geq1}c_{i+(p-1)j}$.
- $\qquad$Print $f:=\sum_{i=1}^dc_iX^i$.
This requires $d+2-2p$ additions per polynomial, so the runtime is a linear in the output.
Another way to reach the same construction is as follows:
- Take an arbitrary polynomial $f\in\Bbb{F}_p[X]$ of degree $d$.
- Compute the unique $g\in\Bbb{F}_p[X]$ with $\deg g<p$ such that $g\equiv f\pmod{X^p-X}$.
- Output $f-g$.
The computation in step $2$ is a matter of polynomial long division. Then $$f=(X^p-X)h+g,$$ which shows that $f-g$ vanishes on $\Bbb{F}_p$. Of course every polynomial of degree $d$ that vanishes on $\Bbb{F}_p$ arises in this way, because if $f\in\Bbb{F}_p[X]$ vanishes on $\Bbb{F}_p$ then $g\equiv0$.
I think I finally did it after uncountable tedious hours! The coding is not very elegant but Singular is a little bit sensitive as far as for-loops, recursion and deceleration is concerned. Due to the recursion this implementation will not work for larger $d-p$
ring A = 5, x, dp;
LIB "general.lib";
proc allpoly(int p, int d, int #) // p prime, d degree
{
list L;
int j;
int k;
if(d!=0)
{
list A = allpoly(p,d-1,0);
for(int i=1; i<=size(A);i++)
{
if(# == 0)
{
for(k=0; k<p; k++)
{
L = insert(L,k*x^d + A[i]);
}
}
else
{
for(j=1; j<p; j++)
{
L = insert(L,j*x^d + A[i]);
}
}
}
}
else
{
for(int t=0;t<p;t++)
{
L = insert(L,t);
}
}
return(L);
}
attrib(allpoly,"default_arg",1);
proc multi(poly f) // multiplying a polynomial with x^p - x where p is the characteristic of ring A
{
return(f * (x^(ringlist(A)[1]) - x));
}
proc vanish(int p, int d) // p prime, d degree, d => p
{
if(p>d)
{
list L = (0);
return(L);
}
else
{
list A = allpoly(p,d-p);
list L = apply(A, multi);
if(p==d) // will sort out the 0 polynomial if p = d
{
L = delete(L,size(L));
}
return(L);
}
}
If we now apply for instance vanish(5,6)
we get the output:
[1]:
-x6+x2
[2]:
-2x6+2x2
[3]:
2x6-2x2
[4]:
x6-x2
[5]:
-x6+x5+x2-x
[6]:
-2x6+x5+2x2-x
[7]:
2x6+x5-2x2-x
[8]:
x6+x5-x2-x
[9]:
-x6+2x5+x2-2x
[10]:
-2x6+2x5+2x2-2x
[11]:
2x6+2x5-2x2-2x
[12]:
x6+2x5-x2-2x
[13]:
-x6-2x5+x2+2x
[14]:
-2x6-2x5+2x2+2x
[15]:
2x6-2x5-2x2+2x
[16]:
x6-2x5-x2+2x
[17]:
-x6-x5+x2+x
[18]:
-2x6-x5+2x2+x
[19]:
2x6-x5-2x2+x
[20]:
x6-x5-x2+x
which should be correct.
If someone has a better solution that maybe does use some exclusive Singular functionalities which I'm not aware of I would be glad if you could share it with me.