2
$\begingroup$

In Sage (or any other package) when using Gröbner basis to solve a system of equations (some of which are non-linear equations) does computing the Gröbner basis for the ideal ID generated by the system of equations over the polynomial ring over a Finite Field (of prime order) ensures that the system has solutions in the field itself if 1 \notin ID? I mean if 1 is not in the ideal generated by the system of equation, does that mean there definitely are solutions for the system in the field itself? Note here that I am not adding the field polynomials to the system as I am working with large prime orders.

If the above test is not a correct indication of the existence of solutions in the field itself, what commands in Sage or Singular that can tell me if solutions exist in the field itself? Or is a manual work involved in the process?

Thanks in advance.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
4
$\begingroup$

If you obtain a Grobner basis that is $\not= [1]$, then your system has solutions in the algebraic closure of your finite field $K$ and not necessarily in $K$. If you want to consider only the solutions that stand in $K$, then you must add conditions. The most simple case is $K=F_2$. Then for each variable $x_i$, you add the condition $x_i^2-x_i=0$.

PS. The case when $K=\mathbb{R}$ is more difficult and is the subject of intense research (cf. the website of LIP 6 in France).

EDIT 1. @ Robert Israel . If $K=F_q$, ($q=p^r$) then we add the equalities $x_i^q-x_i=0$. When $q$ is a great number, eventually we can be in front of an overflow. For example, with Maple on a PC, we consider the system

$F := [x^7y^3-5x^4z^5+1, 3y^2z^6-4x^2y^3z+2, -x^2y^4z+xyz-3x+4y+5z-2]$

If $q=7^3$, then the associated matrices have more than $500000$ columns !

Yet, if we work in the algebraic closure of $F_7$, then we obtain easily a Grobner basis (there are $147$ solutions).

If $q=11^2$, then we obtain $2$ solutions in $1"5$.

If we work in the algebraic closure of $F_{11}$, then we obtain a Grobner basis ($154$ solutions).

EDIT 2. @ user84881 . 1. your software gives you a Grobner basis on $\overline{F_q}$; otherwise it is hopeless.

  1. Assume that your system has a finite number of solutions and choose one variable $x$. Often, from your soft, isolating the variable $x$, you can get an univariate polynomial $P(x)=0$ (the system is triangulated). Then calculate $gcd(P(x),x^q-x)$ and you are done.

This method works for my above example.

Improve this answer
$\endgroup$
6
  • $\begingroup$ If $K = GF(p)$, I guess you would add $\prod_{j=0..p-1} (x_i - j) = 0$. $\endgroup$
    – Robert Israel
    Commented Jan 12, 2016 at 1:52
  • $\begingroup$ I am taking about large primes (i.e. 128-bit numbers or so) $\endgroup$
    – user84881
    Commented Jan 12, 2016 at 15:18
  • $\begingroup$ Thank you very much. What is the east way to isolate a variable, e.g. using Sage? $\endgroup$
    – user84881
    Commented Jan 13, 2016 at 14:13
  • $\begingroup$ @loup blanc: Defining the field polynomial (x^q - x) even for a small field like F_605534459 results in an overflow so cannot even compute the gcd $\endgroup$
    – user84881
    Commented Jan 13, 2016 at 14:38
  • $\begingroup$ @ user84881 , I do not know anyone who works on fields having such a big characteristic. Maple accepts only $char(K)\leq 2^{16}$. Can you write some words about your problem ? $\endgroup$
    – loup blanc
    Commented Jan 13, 2016 at 18:11
2
$\begingroup$

For example, suppose you just have the one equation, say $x^2 + 1 = 0$. The Grobner basis will consist of $x^2+1$. This has no bearing on whether $-1$ is a square in your field.

EDIT: For finding solutions in your field, the following might work (in particular if the ideal is zero-dimensional).

Take a "plex" Gröbner basis, and factor the first polynomial in it over your field. Note that factoring a polynomial is pretty efficient, even modulo a $128$-bit prime. Any factors that are linear in one of the variables (say $x$) correspond to candidates for values of $x$, possibly dependent on other variables. For each of these, substitute that value for $x$ into the rest of your basis and continue. Any factors that are nonlinear and contain just one variable can be disregarded, as they won't correspond to solutions in the field. Factors with more than one variable, and no variable for which the factor has degree $1$, might be problematic, though.

For example, consider the polynomials $$ \matrix{21\,xy-121\,{z}^{2}+6\,x+7\,y-110\,z-23 \cr 33\,xz-49\,{y}^{2}+18\,x-42\, y+22\,z+3\cr-9\,{x}^{2}+77\,zy-6\,x+42\,y+11\,z+6 \cr {z}^{4}+{y}^{3}+{x}^{2 }+230208773171659848188232517051917004253} $$ over $F_p$ where $p$ is the prime $850705917302346158658436518579420528641$.

In Maple:

> with(PolynomialIdeals):
> p:= 850705917302346158658436518579420528641;
> G := [21*x*y-121*z^2+6*x+7*y-110*z-23, 33*x*z-49*y^2+18*x-42*y+22*z+3,
>  -9*x^2+77*y*z-6*x+42*y+11*z+6,
>   z^4+y^3+x^2+230208773171659848188232517051917004253];
> J:= PolynomialIdeal(G, characteristic=p);
> B:= Groebner[Basis](J, plex(x,y,z));
> B:= map(Factor, B) mod p;

$$B:= [ \left( {z}^{3}+638987694045812089487943040989684012240\,{z}^{2}+ 788559908137201150047779839724942410702\,z+ 166287164820212048829798599861338659586 \right) \left( z+ 154673803145881119756079367014440096117 \right) ,y+ 121529416757478022665490931225631504090\,z+ 729176500544868135992945587353789024549, 567137278201564105772291012386280352426+ 283568639100782052886145506193140176210\,z+x] $$

The first polynomial depends only on $z$ and there is one linear factor. Substituting the corresponding value $z = 696032114156465038902357151564980432524$ into the other two polynomials in the Gröbner basis, you get corresponding values for $x$ and $y$. There is just this one solution of the equations over $F_p$.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Thank you for the answer. Is there a definite way to figure out if a solution exists in the field?, $\endgroup$
    – user84881
    Commented Jan 8, 2016 at 18:44
  • $\begingroup$ Thank you. I tried taking the Gröbner basis using the plex ordering. In many cases I tried, the first polynomial in the Gröbner basis is not a univariate polynomial, am I doing something wrong? The system I tried is: x_6*u + x_8*e + x_3*bx_1 + x_3*c + x_1*w - e = 0; x_6*d + x_8*f + x_3*a + x_1*v - f = 0; x_7*u - x_8*w + x_3*bx_2 + x_2*w = 0; x_9*u - x_8*c + x_5*bx_1 + x_5*c = 0; x_9*d - x_8*a + x_5 * a = 0; x_7*d - x_8*v + x_2 * v = 0; x_8*b - bx_5*x_2 = 0; I tried different values of a,b,c,d,e,f,u,v,w and wanted to see if I can always solve for x_1,...,x_3,x_5,..,x_9 $\endgroup$
    – user84881
    Commented Jan 14, 2016 at 17:24
  • $\begingroup$ Are bx_1, bx_2, bx_5 supposed to be b * x_1, b * x_2, b * x_5? $\endgroup$
    – Robert Israel
    Commented Jan 14, 2016 at 18:56
  • $\begingroup$ Yes a,b,c,d,e,f,u,v,w are coefficients. So basically I want to figure out what values of a,b,c,d,e,f,u,v,w the system of equations in the unknowns x_1, ... x_3, x_5, x_9 do not have an answer in particular Field F_q $\endgroup$
    – user84881
    Commented Jan 14, 2016 at 19:32

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .