1
$\begingroup$

I want to know is there is an efficient way to figure out whether or not a ( underdetermined) system of non-linear equations have a solution over a finite field of large prime order. The equations are non-linear, however, the degree of each unknown in any equation is at most 1. Any guidance or a reference to a resource which might be of help would be appreciated.

I know that one way is to generate an ideal of those equations and add equations of the form x_i^q – x_i=0 for each unknown x_i where q is the order of the field. But this will take forever for large q.

Any help would be appreciated.

Thanks, Adam

To be more precise, the equations I have look something like the following: There are 9 unknown (x_1, ..., x_9). I want to show that there is a solution for any given a,b,c,d,e,f,g,h,i \in F_q

gx_6 + ex_8 = e - b*x_3*x_1 - cx_3 - ix_1

dx_6 + fx_8 = f - ax_3 - hx_1

gx_7 - ix_8 = - b*x_3*x_2 - i*x_2

gx_9 - cx_8 = - b*x_5*x_1 - c*x_5

dx_9 - ax_8 = - a*x_5

dx_7 - hx_8 = - h*x_2

bx_8 = bx_5*x_2

x_4 = 0

Hmmm, the system of equations I am interested in solving is more complex than the toy example above I used as an example but again the criteria about the degree of the polynomials is the same.

I do not want to do it manually. Is there a way to get, for instance, Sage or Singular to find the solutions in the field F_q itself? I am not interested in solutions in the Algebraic closure of the field, i.e. I am only interested in the solutions which are elements in F_q itself. I got to the point where I computed the groebner basis for the ideal I generated by my system of equations in the polynomial ring over F_q and I test that 1 is not in the ideal I which implies the system has a solution. Does this mean the solutions are by default guaranteed to exist in F_q? If I try to add the Field polynomials to the system, Sage hangs even for a toy example using small $q$, e.g., q=127.

Thanks

$\endgroup$
3
  • 1
    $\begingroup$ Unless I'm misunderstanding your question, I think this can be straightforwardly handled via the Gröbner basis and the effective Nullstellensatz - see en.wikipedia.org/wiki/Gröbner_basis#Intersecting_ideals for more details. You certainly shouldn't need to add your order-$q$ polynomials; you can just do all your work in the field directly. $\endgroup$ Jan 4, 2016 at 15:30
  • $\begingroup$ To get more responses, it usually helps to add at least one major tag (starting with two letters and a dot). $\endgroup$ Jan 4, 2016 at 15:32
  • $\begingroup$ Steven Stadnicki, can you please shed some light on how to check the solutions are in F_q itself without the need to add the order order-q polynomials. Thanks alot $\endgroup$
    – Adam
    Jan 8, 2016 at 17:49

1 Answer 1

3
$\begingroup$

First a general comment: if you have some information about the geometry of the variety that the equations define, you can apply the Weil bounds in some form and show that there is a solution.

If the unknowns only appear to the first order, then you have something like $fx_n + g =0$, where $f,g$ don't involve $x_n$ and all you need is a point where $f \ne 0$ to solve for $x_n$. The total number of zeros of $f$ do not exceed $(\deg f)q^{n-2}$ if $f$ depends on $n-1$ variables. But again you say the degree in each variable is at most one, so $\deg f \le n-1$. So, if $q > n$ there is always a point with $f \ne 0$ and you can solve for $x_n$.

Edit: This needs more detail. Eliminate $x_n$ from all but one equation. Now, do what I had before to induct on $n$.

$\endgroup$
3
  • $\begingroup$ Thanks for the answer. Will the above ensure that the solutions are in F_q? $\endgroup$
    – Adam
    Jan 8, 2016 at 17:52
  • $\begingroup$ @Adam Yes. $ $ $ $ $\endgroup$ Jan 8, 2016 at 18:58
  • $\begingroup$ Thank you again for your help. Is there a command in Sage which does the elimination process, i.e that eliminates x_n from all but one equation? The system I have is quite complex and do not want to do it manually. $\endgroup$
    – Adam
    Jan 8, 2016 at 19:29

You must log in to answer this question.

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