0
$\begingroup$

I am trying to find a cubic polynomial over GF(5) that evaluates to zero at the points (1,2,0),(2,0,0),(1,4,1),(-2,-1,-1),(-3,2,1),(1,-1,0),(2,-3,1),(-3,-2,2),(1,-2,1).

Clearly the zero polynomial would satisfy the condition, thus I'm looking for a proper cubic polynomial. I note that the generic form of such a polynomial is $f= ax^3+ by^3+ cz^3+ dx^2y + ex^2z+ fy^2x+ iy^2z+ gz^2x+ kz^2y+ lxyz$, that is I need to solve for the coefficients $a,b,\ldots,l$.

I would prefer to do this calculation in GAP as I am using the software already for other calculations.

$\endgroup$
  • $\begingroup$ P.S. See also math.stackexchange.com/q/347387 $\endgroup$ – Alexander Konovalov Mar 25 '15 at 13:43
  • $\begingroup$ I need some explanation please. what is the values of the coefficients with the nine points. $\endgroup$ – user23 Mar 25 '15 at 14:11
  • $\begingroup$ This is not a duplicate (but badly worded). My guess is that the user is a graduate student in finite geometry who wants to describe a set of points by a polynomial of restricted form. I.e. the question is an interpolation question. One can solve this with Grobner bases, but the space (as the question is marked as duplicate I cannot post an answer) is too short to explain. (The polynomial must have the form Z(5)^3*x^2*yb+x^2*ze-xy^2*b+xyzb+Z(5)*xyzc+xyze +Z(5)*xz^2*e+y^3*b-y^2*zb+Z(5)^3*y^2* zc-y^2*z e+Z(5)^3*yz^2*b+Z(5)*yz^2*c+y*z^2*e+z^3*c) $\endgroup$ – ahulpke Mar 25 '15 at 15:33
  • $\begingroup$ @ahulpke: thanks, then the question may be reopened once its author will edit it to give us more details and perhaps show attempts in GAP achieved so far (e.g. typing the polynomial as a GAP input would help) $\endgroup$ – Alexander Konovalov Mar 25 '15 at 17:39
  • $\begingroup$ Same about the list of points - please use comma instead of a colon as a separator. $\endgroup$ – Alexander Konovalov Mar 25 '15 at 17:40
1
$\begingroup$

To describe the solution of the linear system in GAP:

The first step is to get linear equations by evaluating the polynomial at the points. To allow distinguishing the coefficients we introduce the variables as extra polynomial variables:

field:=GF(5);
x:=X(field,"x");
y:=X(field,"y");
z:=X(field,"z");
a:=X(field,"a");
b:=X(field,"b");
c:=X(field,"c");
d:=X(field,"d");
e:=X(field,"e");
f:=X(field,"f");
g:=X(field,"g");
i:=X(field,"i");
k:=X(field,"k");
l:=X(field,"l");
pol:=a*x^3+b*y^3+c*z^3+d*x^2*y+e*x^2*z+f*y^2*x+i*y^2*z+g*z^2*x
     +k*z^2*y+l*x*y*z;

Next, define the points, move them over GF(5), and evaluate the polynomial:

pts:=[[1,2,0],[2,0,0],[1,4,1],[-2,-1,-1],[-3,2,1],[1,-1,0],
      [2,-3,1],[-3,-2,2],[1,-2,1]];
pts:=List(pts,x->x*One(field));
vals:=List(pts,p->Value(pol,[x,y,z],p));

The result you get are linear equations, but written as polynomials. While it probably is quickest to retype them, the following GAP code constructs the coefficient matrix for these equations. (The list mums gives the index numbers of the variables):

nums:=List([a,b,c,d,e,f,g,i,k,l],IndeterminateNumberOfUnivariateLaurentPolynomial);
mat:=[];
for v in vals do
  ex:=ExtRepPolynomialRatFun(v);
  vec:=List([1..Length(nums)],x->Zero(field));
  for s in [1,3..Length(ex)-1] do
    vec[Position(nums,ex[s][1])]:=ex[s+1];
  od;
  Add(mat,vec);
od;

Since GAP works with row vectors, we need to have the equation coefficients actually in the columns, thus transpose the matrix. We now calculate a basis for the nullspace, and construct the corresponding polynomials:

mat:=TransposedMat(mat);

sol:=[];
for v in TriangulizedNullspaceMat(mat) do
  Add(sol,Value(pol,[a,b,c,d,e,f,g,i,k,l],v));
od;

We get the following three basis elements for the solutions:

$Z(5)^{3}x^{2}y-xy^{2}+xyz+y^{3}-y^{2}z+Z(5)^{3}yz^{2}$,

$Z(5)xyz+Z(5)^{3}y^{2}z+Z(5)yz^{2}+z^{3}$,

$x^{2}z+xyz+Z(5)xz^{2}-y^{2}z+yz^{2}$

$\endgroup$
0
$\begingroup$

Hint: For each point, the condition that the cubic evaluates to zero at this point is equivalent to a linear equation in $a,\dots,l$. In all, you obtain a homogeneous system of 9 linear equations in the 10 variables $a,\dots,l$, and you are looking for a non-trivial solution to this system. You could do this by finding a basis for the null space of the matrix corresponding to the system.

$\endgroup$
  • $\begingroup$ Is there any help in gap $\endgroup$ – user23 Mar 26 '15 at 14:48
  • $\begingroup$ Yes, enter ?NullspaceMat in GAP to see help on this function. $\endgroup$ – Alexander Konovalov Mar 26 '15 at 15:22
  • $\begingroup$ I need to find the corresponding polynomial to these points in known coefficients. $\endgroup$ – user23 Mar 26 '15 at 18:30
  • $\begingroup$ a cubic polynomial I mean $\endgroup$ – user23 Mar 26 '15 at 18:34
  • $\begingroup$ Thanks so much Alexander ahulpke for this explanation . $\endgroup$ – user23 Mar 26 '15 at 21:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.