**Ramón L. Collazo**

**Julio J. de la Cruz**

**Daniel E. Ramírez**

Department of Computer Science

College of Natural Sciences

(*Para poder ver todas las formulas que se encuentran en este artículo debe utilizar un motor de búsqueda que no sea *Google Chrome*)

**Abstract**

An important problem in mathematics is to determine if a system of polynomial equations has or not solutions over a given set. We study systems of polynomial equations over finite fields

Keywords: mathematics, polynomial equations, finite fields, solvability

**Resumen:**

Un problema importante en las matemáticas es el determinar si un sistema de ecuaciones polinomiales tiene o no soluciones sobre un conjunto dado. Estudiamos sistemas de ecuaciones polinomiales sobre campos finitos

Palabras Claves: matemáticas, ecuaciones polinomiales, campos finitos, resolución

## 1 Introduction

The computation of the

where

The exact

## 2 Preliminaries

First, we introduce some concepts that will be used in our work. The handbook (Panario & Mullen, 2013) is a complete reference book for all the background and recent results in finite fields.

**Definition 1.** *A* *finite field*

**Example 1.**

*with addition and multiplication mod 7 is a field.*

**Example 2.**

*with addition and multiplication mod 6 is not a field because 3 does not have a multiplicative inverse.*

In this work we only deal with prime fields, this is,

**Definition 2.** *A* ** system of polynomial equations** over

We assume that every system of polynomial equations contains all the variables

## 2.1 Exponential Sums and Solvability

**Definition 3.** *The exponential sum over 𝔽p associated with the polynomial F(X) is given by*

*where*ζ is a p -th root of unity.

This number is hard to compute but we are not interested in the exact number, we just look for the greatest power of

**Definition 4.** *The exact p-divisibility of a positive integer k, denoted as νp(k), is the exponent of the highest power of p dividing k.*

*Hence,*

Note that, if

To determine if a system is solvable, we need to know if the exponential sum of the system of polynomials has exact

**Lemma 1** (Ax (1964)). *Let F1(X),…,Ft(X)∈𝔽p[X] and N be the number of common zeros of F1,…,Ft. Then,*

The exact value of this number

Note that if

To determine systems which have exact

## 2.2 The Covering Method

We now define the

**Definition 5.** *Let F(X)=a1F1+a2F2+⋯+arFr. A set C={F1v1,…,Frvr} of powers of the monomials in F is a (p−1)*

**-covering**of F if in the product F1v1⋯Frvr the exponent of each variable is a positive multiple of p−1. Note that some of the vi might be 0. The

**size**of the (p−1)-covering is ∑ri=1vi.

**Definition 6.** *A set C={Fv11,…,Fvrr} is a minimal (p−1)-covering of F if for any other (p−1)-covering C′={Fv′11,…,Fv′rr} of F, ∑ri=1v′i≥∑ri=1vi.*

**Example 4.** *Consider *

F(X)=X1X2+X3X4+X1X2X3X4∈𝔽2[X].

*Then*C1={(X1X2),(X3X4)} is a 1 -covering of F of size 2 and the minimal 1 -covering of F is C2={(X1X2X3X4)} and it has size 1 .

*If F(X)∈𝔽5[X], then C1={(X1X2)4,(X3X4)4} is a 4-covering of F of size 8, and C2={(X1X2X3X4)4} is the minimal 4-covering of F of size 4.*

The covering method for computing exact 2-divisibility of exponential sums of binary polynomials was introduced in (Castro, Medina, & Rubio, 2011). In (Castro & Rubio, n.d.) the authors presented the following sufficient conditions to obtain polynomials such that their exponential sum has exact

**Theorem 1** ((Castro & Rubio, n.d.), Theorem 3.7). *Suppose that F=a1F1+⋯+arFr has a unique minimal (p−1)-covering C={Fv11,…,Fvrr} where each monomial in C with vi≠0 has at least two variables that are not contained in the other monomials of C. Then νp(S(F))=∑ri=1vip−1. *

## 3 Conditions for solvability

The results in (Castro & Rubio, n.d.) gave sufficient conditions to guarantee that the exponential sum of the polynomials has exact

To use Theorem 1 we need the polynomial

**Lemma 2.** *If the polynomial F=a1(Xb111⋯Xb1nn)d1+⋯+ar(Xbr11⋯Xbrnn)dr*

=a1F1+⋯+arFr∈𝔽p[X] , where bjk∈{0,1} , is such that each Fj has at least one variable that is not contained in the other monomials of F , then C={F1p−1gcd(p−1,d1),…,Frp−1gcd(p−1,dr)} is the unique minimal(p−1) -covering of F .

*Proof.* First, in order to prove that

where

Now, we want to prove that the covering is minimal and unique. Since each

**Example 5.** *Consider the polynomial F=7X41+4X52+3X93∈𝔽13[X]. A 12-covering of F is*

*and has size 38, but the minimal 12-covering of F is*

*and has size*18 .

We now present sufficient conditions on the exponents

**Theorem 2.** Suppose that

where

*Proof.* By Lemma 1, the number of zeros of

Theorem 1 implies that

Now we have that

**Example 6.** *Consider the polynomial F=(X1X2)8+(X3X4)10∈𝔽19[X]. The number of zeros of F−α, α∈F19 is N=p−1⋅S(Y(F−α)). By Lemma 2, the unique minimal 18-covering of Y(F−α) is*

*Using Theorem 1,*

*By Lemma 1, this implies that*νp(N)=1−1=0 , where N is the number of solutions of F−α=0 . Therefore, the equation F=α is solvable for any α∈F19 .

We can extend this theorem to systems with several equations. To simplify the notation, we only state the result for 2 equations.

**Theorem 3.** Consider a system of two polynomials equations over

*where bjk∈{0,1}, and F1=a11F11+⋯+a1r1F1r1,F2=a21F21+⋯+a2r2F2r2 are such that each monomial Fji has at least two variables that are not contained in the other monomials of F1+F2. If gcd(p−1,d1i)=k1, where k1|r1, and gcd(p−1,d2i)=k2, where k2|r2, then the system F1=α1,F2=α2 is solvable for any α1,α2∈Fp.*

*Proof.* Let

where

Theorem 1 implies that