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$
  • 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$ – Steven Stadnicki Jan 4 '16 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$ – Sebastian Goette Jan 4 '16 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 '16 at 17:49
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$
  • $\begingroup$ Thanks for the answer. Will the above ensure that the solutions are in F_q? $\endgroup$ – Adam Jan 8 '16 at 17:52
  • $\begingroup$ @Adam Yes. $ $ $ $ $\endgroup$ – Felipe Voloch Jan 8 '16 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 '16 at 19:29

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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