Posts tagged #solvability

# Solvability of systems of polynomial equations over finite fields

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 Fp$F_p$, p$p$ prime, and look for sufficient conditions that guarantee their solvability over the field. Using the covering method of (Castro & Rubio, n.d.) we get conditions on the degrees of the terms that allow us to construct families of systems that have exact p$p$-divisibility of the number of solutions and therefore guarantee the solvability of the system over the finite field.

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 Fp$F_p$, donde p$p$ es primo, y buscamos condiciones suficientes para garantizar que el sistema tenga solución sobre el campo. Usando el método de la cubierta de (Castro & Rubio, n.d.) obtenemos condiciones en los grados de los términos de modo que podamos construir familias de sistemas que tengan divisibilidad exacta p$p$ del número de soluciones, y por consiguiente garantizar que el sistema tenga solución sobre el campo finito.

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

## 1 Introduction

The computation of the p$p$-divisibility of an exponential sum is a mathematical tool used for different purposes. In our research, the p$p$-divisibility is used to determine if a system of polynomial equations

a11(Xb1111Xb11nn)d11++a1r1(Xb1r111Xb1r1nn)d1r1=α1 at1(Xbt111Xbt1nn)dt1++atrt(Xbtrt11Xbtrtnn)dtrt=αt,

where bijk{0,1}$b_{ijk} \in \{0,1\}$, has solutions or not over a finite field.

The exact p$p$-divisibility of exponential sums was used in (Castro & Rubio, 2010) to determine the solvability of certain systems of polynomial equations. The results in that paper were obtained by solving systems of polynomial congruences. The covering method was used in (Castro & Rubio, n.d.) to prove that if a system of polynomial equations has a certain (p1)$(p-1)$-covering the system is solvable. We present sufficient conditions on the degrees of the terms of a system of polynomial equations that guarantee that it produces the type of (p1)$(p-1)$-covering in (Castro & Rubio, n.d.) and assure that the system is solvable.

## 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 𝔽q$\mathbb{F}_q$ is a field with q=pf$q=p^f$ elements, where p$p$ is a prime.

Example 1.

𝔽7=7={0, 1, 2, 3, 4, 5, 6},
with addition and multiplication mod 7 is a field.

Example 2.

6={0, 1, 2, 3, 4, 5},
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, q=p$q = p$.

Definition 2. A system of polynomial equations over 𝔽p$\mathbb{F}_p$ is a set of equations F1=0,...,Fn=0$F_1 = 0, ..., F_n = 0$, where Fi$F_i$ are polynomials in n$n$ variables X1,,Xn$X_1, \ldots , X_n$ and coefficients in 𝔽p$\mathbb{F}_p$.

We assume that every system of polynomial equations contains all the variables X1,,Xn$X_1, \cdots , X_n$, and denote the set of all polynomials in X1,,Xn$X_1, \cdots , X_n$ and coefficients in 𝔽p$\mathbb{F}_p$ by 𝔽p$\mathbb{F}_p$[X].

## 2.1 Exponential Sums and Solvability

Definition 3. The exponential sum over 𝔽p$\mathbb{F}_p$ associated with the polynomial F(X)$F( X )$ is given by

S(F)=xFnpζF(x),
where ζ$ζ$ is a p$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 p$p$ that divides the sum.

Definition 4. The exact p-divisibility of a positive integer k$k$, denoted as νp(k)$\nu _{p}(k)$, is the exponent of the highest power of p$p$ dividing k$k$.

νp(40)=νp(235).
Hence,
ν2(40)=3,ν5(40)=1, and νp(40)=0 for p2,5.

Note that, if k=0$k=0$, there is no highest power of p$p$ that divides k$k$. This is, the exact p$p$-divisibility of 0$0$ is not defined.

To determine if a system is solvable, we need to know if the exponential sum of the system of polynomials has exact p$p$-divisibility. The exponential sum is defined for a single polynomial; we construct a new polynomial from the system of polynomials. This new polynomial is obtained by multiplying a new variable to each polynomial in the system and adding the products. The exponential sum of this new polynomial gives the number of common zeros of the system.

Lemma 1 (Ax (1964)). Let F1(X),,Ft(X)𝔽p[X]$F_1(X), \ldots, F_t(X) \in \mathbb{F}_p[X]$ and N$N$ be the number of common zeros of F1,,Ft$F_1, \ldots , F_t$. Then,

N=ptS(Y1F1(X)++YtFt(X)).

The exact value of this number N$N$ is hard to compute because it depends on the exact value of the exponential sum. But we are interested on whether or not the system has solutions and it is enough to know if N=0$N = 0$ or N0$N \neq 0$.
Note that if νp(N)=a$\nu _{p}(N)=a$, this implies that pa|N$p^a |N$ and pa+1N$p^{a+1} \nmid N$, therefore N0$N \neq 0$, because 0$0$ is divisible by every number that is not 0$0$. This is, if the exponential sum associated with a system of polynomial equations has exact p$p$-divisibility, we guarantee that the system is solvable.
To determine systems which have exact p$p$-divisibility we use the covering method as it was presented in (Castro & Rubio, n.d.)

## 2.2 The Covering Method

We now define the (p1)$(p-1)$-covering of a polynomial F$F$, which encodes how many monomials of F$F$ (including repetitions) are needed to have each variable “represented” a multiple of p1$p-1$ times.

Definition 5. Let F(X)=a1F1+a2F2++arFr$F(X) = a_1F_1+a_2F_2+ \cdots + a_r F_r$. A set C={F1v1,,Frvr}$C = \left \{{{F_1}^{v_1}}, \ldots , {{F_r}^{v_r}} \right \}$ of powers of the monomials in F$F$ is a (p1)$(p-1)$-covering of F$F$ if in the product F1v1Frvr${F_1}^{v_1} \cdots {F_r}^{v_r}$ the exponent of each variable is a positive multiple of p1$p-1$. Note that some of the vi$v_i$ might be 0. The size of the (p1)$(p-1)$-covering is ri=1vi$\sum_{i=1}^{r} v_i$.

Definition 6. A set C={Fv11,,Fvrr}$C=\{F_1^{v_1},\ldots,F_r^{v_r}\}$ is a minimal (p1)$(p-1)$-covering of F$F$ if for any other (p1)$(p-1)$-covering C={Fv11,,Fvrr}$C'=\{F_1^{v'_1},\ldots,F_r^{v'_r}\}$ of F$F$, ri=1viri=1vi$\sum_{i=1}^{r} v'_i \geq \sum_{i=1}^{r} v_i$.

Example 4. Consider

F(X)=X1X2+X3X4+X1X2X3X4𝔽2[X].
Then C1={(X1X2),(X3X4)}$C_1 = \{ (X_1 X_2), (X_3 X_4)\}$ is a 1$1$-covering of F$F$ of size 2$2$ and the minimal 1$1$-covering of F$F$ is C2={(X1X2X3X4)}$C_2 = \{(X_1 X_2 X_3 X_4)\}$ and it has size 1$1$.

If F(X)𝔽5[X]$F(X) \in \mathbb{F}_5[X]$, then C1={(X1X2)4,(X3X4)4}$C_1 = \{ (X_1 X_2)^4, (X_3 X_4)^4\}$ is a 4$4$-covering of F$F$ of size 8$8$, and C2={(X1X2X3X4)4}$C_2 = \{(X_1 X_2 X_3 X_4)^4\}$ is the minimal 4$4$-covering of F$F$ of size 4$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 p$p$-divisibility.

Theorem 1 ((Castro & Rubio, n.d.), Theorem 3.7). Suppose that F=a1F1++arFr$F = {a_1}{F_1} + \cdots + {a_r}{F_r}$ has a unique minimal (p1)$(p-1)$-covering C={Fv11,,Fvrr}$C = \{ {F_1^{v_1}},\ldots,{F_r^{v_r}} \}$ where each monomial in C$C$ with vi0${{v_i} \neq 0}$ has at least two variables that are not contained in the other monomials of C$C$. Then νp(S(F))=ri=1vip1${\nu _{p}}(S(F)) = \sum_{i=1}^{r} \frac{v_i}{p-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 p$p$-divisibility. However, these conditions are on the type of (p1)$(p-1)$-coverings that the polynomials must have and it might be hard to know if these conditions are satisfied by just looking at the polynomials. Also, for the exact p$p$-divisibility of the number of solutions we have to consider the new variables Yi$Y_{i}$ as in Lemma 1. Here we present a result similar to Theorem 1 but with conditions in the degrees of the polynomials. We also present a similar theorem for the computation of the exact p$p$-divisibility of the number of solutions of the system of polynomials.
To use Theorem 1 we need the polynomial F$F$ to have a unique minimal (p1)$(p-1)$-covering. We now prove conditions so that polynomials of the form F=a1(Xb111Xb1nn)d1++ar(Xbr11Xbrnn)dr$F=a_1\left(X_1^{b_{11}} \cdots X_n^{b_{1n}}\right)^{d_1} + \cdots + a_r\left(X_1^{b_{r1}} \cdots X_n^{b_{rn}}\right)^{d_r}$, where bjk{0,1}$b_{jk} \in \{0, 1\}$, have this type of (p1)$(p-1)$-covering. Corollary 3.8 in (Castro & Rubio, n.d.) has a similar result but the proof was not provided.

Lemma 2. If the polynomial F=a1(Xb111Xb1nn)d1++ar(Xbr11Xbrnn)dr$F=a_1\left(X_1^{b_{11}} \cdots X_n^{b_{1n}}\right)^{d_1} + \cdots + a_r\left(X_1^{b_{r1}} \cdots X_n^{b_{rn}}\right)^{d_r}$
=a1F1++arFr𝔽p[X]$= a_1F_1+\cdots +a_rF_r \in{\mathbb{F}_{p}[X]}$, where bjk{0,1}$b_{jk} \in \{0,1\}$, is such that each Fj$F_j$ has at least one variable that is not contained in the other monomials of F$F$, then C={F1p1gcd(p1,d1),,Frp1gcd(p1,dr)}$C= \{ {F_1}^{{\frac{p-1}{gcd(p-1,d_1)}}},\ldots,{F_r}^{{\frac{p-1}{gcd(p-1,d_r)}}} \}$ is the unique minimal(p1)$(p-1)$-covering of F$F$.

Proof. First, in order to prove that C$C$ covers all the variables, we have to show that the exponent of each variable in the product F1p1gcd(p1,d1)Frp1gcd(p1,dr)${F_1}^{{\frac{p-1}{gcd(p-1,d_1)}}} \cdots {F_r}^{{\frac{p-1}{gcd(p-1,d_r)}}}$ is a positive multiple of (p1)$(p-1)$. The exponent of Xk$X_k$ has the form β=d1v1b1k++drvrbrk$\beta = {d_1}\cdot {v_1}\cdot {b_{1k}} + \cdots + {d_r}\cdot {v_r}\cdot {b_{rk}}$, where vj=p1gcd(p1,dj)$v_j = \frac{p-1}{gcd(p-1,{d_j})}$. Note that bjk=0${b_{jk}} = 0$ when Xk${X_k}$ is not in the monomial Fj${F_j}$ and bjk=1${b_{jk}} = 1$ when it is. This is,

β=d1p1gcd(p1,d1)b1k++drp1gcd(p1,dr)brk=lcm(p1,d1)b1k++lcm(p1,dr)brk=(p1)l1b1k++(p1)lrbrk, li=(p1)[l1b1k++lrbrk],

where li0$l_i \neq 0$, and, since F$F$ contains all the variables, there exist at least one k$k$ such that bjk=1${b_{jk}} = 1$. Therefore, l1b1k++lrbrk$l_1 b_{1k}+\cdots +l_r b_{rk} \in \mathbb{N}$, and the exponent of Xk${X_k}$ is a positive multiple of p1$p-1$. The same reasoning can be used for each of the other variables.
Now, we want to prove that the covering is minimal and unique. Since each Fi${F_i}$ has at least one variable that is not contained in Fj${F_j}$, for all ji$j \neq i$, we can take a variable Xk$X_{k}$, that only appears in Fi${F_i}$. Then, in the product F1p1gcd(p1,d1)Frp1gcd(p1,dr)${F_1}^{\frac{p-1}{gcd(p-1,{d_1})}} \cdots {F_r}^{\frac{p-1}{gcd(p-1,{d_r})}}$, Xk$X_k$ has exponent dip1gcd(p1,di)=lcm(p1,di)$d_i \cdot \frac{p-1}{gcd(p-1,d_i)} = lcm(p-1, d_i)$ and therefore the exponent of Xk${X_k}$ is the smallest multiple of p1$p-1$ and di$d_i$. This implies that the monomial Fi$F_i$ cannot have a smallest exponent in any other (p1)$(p-1)$-covering. The same argument works for all the other monomials in F$F$ and the (p1)$(p-1)$-covering is minimal and unique with this property.

Example 5. Consider the polynomial F=7X41+4X52+3X93𝔽13[X]$F = 7 X_{1}^{4} + 4 X_2^{5} + 3 X_3^{9} \in \mathbb{F}_{13}[X]$. A 12$12$-covering of F$F$ is

C={(X41)6,(X52)24,(X93)8}={X241,X1202,X723},

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

C={(X41)12gcd(12,4),(X52)12gcd(12,5),(X93)12gcd(12,9)}={(X41)3,(X52)12,(X93)4}={X121,X602,X363},

and has size 18$18$.

We now present sufficient conditions on the exponents d1,,dr${d_1}, \ldots , {d_r}$ of the terms in the polynomial F$F$ that guarantee that the equation F=α$F = \alpha$ is solvable for any α𝔽p$\alpha \in \mathbb{F}_p$.

Theorem 2. Suppose that F=a1(Xb111Xb1nn)d1++ar(Xbr11Xbrnn)dr$F=a_1\left(X_1^{b_{11}} \cdots X_n^{b_{1n}}\right)^{d_1} + \cdots + a_r\left(X_1^{b_{r1}} \cdots X_n^{b_{rn}}\right)^{d_r}$ \ =a1F1++arFr𝔽p[X]$= a_1F_1+\cdots +a_rF_r \in{\mathbb{F}_{p}[X]}$,
where bjk{0,1}$b_{jk} \in \{ 0,1 \}$, is such that each monomial Fi$F_i$ has at least two variables that are not contained in the other monomials of F$F$. If gcd(di,p1)=k$gcd(d_i,p-1) = k$ and k|r$k|r$, then F(X)=α$F(X) = \alpha$ is solvable for any α𝔽p$\alpha \in \mathbb{F}_p$.

Proof. By Lemma 1, the number of zeros of Fα$F-\alpha$ is N=p1S(Y(Fα))$N = {p^{-1}} \cdot S( Y(F-\alpha))$, where S(Y(Fα))$S(Y (F-\alpha))$ is the exponential sum of Y(Fα)$Y(F-\alpha)$. By Lemma 2, C={F1p1gcd(p1,d1),,Frp1gcd(p1,dr)}$C = \{{F_1}^{{\frac{p-1}{gcd(p-1,d_1)}}},\ldots,{F_r}^{{\frac{p-1}{gcd(p-1,d_r)}}} \}$ is the unique minimal (p1)$(p-1)$-covering of F$F$. Consider C={(YF1)p1gcd(p1,d1),,(YFr)p1gcd(p1,dr)}$C' = \{({YF_1})^{{\frac{p-1}{gcd(p-1,d_1)}}},\ldots,({YF_r})^{{\frac{p-1}{gcd(p-1,d_r)}}} \}$. Since gcd(p1,di)=k$gcd(p-1, {d_i}) = k$ and k|r$k|r$, the variable Y$Y$ in (YF1)p1gcd(p1,d1)(YFr)p1gcd(p1,dr)$({YF_1})^{{\frac{p-1}{gcd(p-1,d_1)}}} \cdots ({YF_r})^{{\frac{p-1}{gcd(p-1,d_r)}}}$ has exponent ri=1p1gcd(p1,di)=ri=1p1k=r(p1k)=c(p1)$\sum_{i=1}^{r} \frac{p-1}{gcd(p-1,{d_i})} = \sum_{i=1}^{r} \frac{p-1}{k} = r (\frac{p-1}{k}) = c (p-1)$, where c$c \in \mathbb{N}$, because k|r$k | r$. This implies that Y$Y$ is (p1)$(p-1)$-covered in C$C'$. By the same arguments in the proof of Lemma 2, C$C'$ is the unique minimal (p1)$(p-1)$-covering of F$F$.

Theorem 1 implies that

νp(S(Y(Fα)))=i=1rvi(p1)=i=1r(p1)gcd(p1,di)1(p1)=i=1r1k=r1k=c.

Now we have that

νp(N)=νp(p1S(Y(Fα)))=νp(p1)+νp(S(Y(Fα)))=1+c,

c$c \in \mathbb{N}$. Since νp(S(N))=c1$\nu _p \left ( S \left ( N \right ) \right ) = c-1$, we have that pcN$p^c \nmid N$ and therefore N0$N \neq 0$.

Example 6. Consider the polynomial F=(X1X2)8+(X3X4)10𝔽19[X]$F = (X_1 X_2)^{8} + (X_3 X_4)^{10}\in \mathbb{F}_{19}[X]$. The number of zeros of Fα$F-\alpha$, αF19$\alpha \in F_{19}$ is N=p1S(Y(Fα))$N = {p^{-1}} \cdot S\left ( Y \left ( F-\alpha \right ) \right )$. By Lemma 2, the unique minimal 18$18$-covering of Y(Fα)$Y(F-\alpha )$ is

C={(Y(X1X2)8)18gcd(18,8),(Y(X3X4)10)18gcd(18,10)}={(Y(X1X2)8)9,(Y(X3X4)10)9}={Y9(X1X2)72,Y9(X3X4)90}.

Using Theorem 1,

νp(S(Y(Fα)))=i=12vi(p1)=18gcd(18,8)118+18gcd(18,10)118=1.

By Lemma 1, this implies that νp(N)=11=0$\nu _{p}(N)=1-1=0$, where N$N$ is the number of solutions of Fα=0$F-\alpha =0$. Therefore, the equation F=α$F=\alpha$ is solvable for any αF19$\alpha \in F_{19}$.

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 𝔽p$\mathbb{F}_{p}$

F1F2=a11(Xb1111Xb11nn)d11++a1r1(Xb1r111Xb1r1nn)d1r1=a21(Xb2111Xb21nn)d21++a2r2(Xb2r211Xb2r2nn)d2r2,

where bjk{0,1}$b_{jk} \in \{0, 1\}$, and F1=a11F11++a1r1F1r1,F2=a21F21++a2r2F2r2$F_1 = a_{11}F_{11}+\cdots +a_{1{r_1}}F_{1{r_1}}, F_2 = a_{21}F_{21}+\cdots +a_{2{r_2}}F_{2{r_2}}$ are such that each monomial Fji$F_{ji}$ has at least two variables that are not contained in the other monomials of F1+F2$F_1 + F_2$. If gcd(p1,d1i)=k1,$gcd(p-1, {d_{1i}}) = k_1,$ where k1|r1$k_1|r_1$, and gcd(p1,d2i)=k2$gcd(p-1, {d_{2i}}) = k_2$, where k2|r2$k_2|r_2$, then the system F1=α1,F2=α2$F_1=\alpha_1, F_2=\alpha_2$ is solvable for any α1,α2Fp$\alpha_1, \alpha_2 \in F_p$.

Proof. Let F=Y1(F1α1)+Y2(F2α2)$F = Y_1(F_1 - \alpha_1) + Y_2(F_2 - \alpha_2)$. By Lemma 1, the number of common solutions of the system is

N=p2S(F),

where S(F)$S(F)$ is the exponential sum associated with the system. By Lemma 2, the unique minimal (p1)$(p-1)$-covering of F1+F2$F_1 + F_2$ is C={F11p1gcd(p1,d11),$C = \Big\{ {F_{11}}^{{\frac{p-1}{gcd\left(p-1,{d_{11}}\right)}}},$ ,F1r1p1gcd(p1,d1r1),(F21)p1gcd(p1,d21),$\ldots,{F_{1r_1}}^{{\frac{p-1}{gcd\left(p-1,d_{1r_1}\right)}}}, ({F_{21}})^{{\frac{p-1}{gcd\left(p-1,{d_{21}}\right)}}},$ ,(F2r2)p1gcd(p1,d2r2)}$\ldots,({F_{2r_2}})^{{\frac{p-1}{gcd\left(p-1,d_{2r_2}\right)}}} \Big\}$. Consider C={(Y1F11)p1gcd(p1,d11),,(Y2F2r2)p1gcd(p1,d2r2)}.$C' = \Big\{({Y_1F_{11}})^{{\frac{p-1}{gcd\left(p-1,d_{11}\right)}}}, \ldots, ({Y_2F_{2r_2}})^{{\frac{p-1}{gcd\left(p-1,d_{2r_2}\right)}}} \Big \}.$ Since gcd(p1,d1i)=k1$gcd\left(p-1, {d_{1_i}}\right) = {k_1}$ and gcd(p1,d2i)=k2$gcd\left(p-1, {d_{2_i}}\right) = {k_2}$, the exponents of Y1$Y_1$ in (Y1F11)p1gcd(p1,d11)$({Y_1F_{11}})^{{\frac{p-1}{gcd\left(p-1,d_{11}\right)}}}$ (Y1F1r1)p1gcd(p1,d1r1)$\cdots ({Y_1F_{1{r_1}}})^{{\frac{p-1}{gcd\left(p-1,d_{1{r_1}}\right)}}}$ and Y2$Y_2$ in (Y2F21)p1gcd(p1,d21)(Y2F2r2)p1gcd(p1,d2r2)$({Y_2F_{21}})^{{\frac{p-1}{gcd\left(p-1,d_{21}\right)}}} \cdots ({Y_2F_{2r2}})^{{\frac{p-1}{gcd\left(p-1,d_{2{r_2}}\right)}}}$ are r1i=1p1gcd(p1,d1i)=r1i=1p1k1=r1p1k1=(p1)c1$\sum_{i=1}^{r_1} \frac{p-1}{gcd(p-1,{d_{1i}})} = \sum_{i=1}^{r_1} \frac{p-1}{k_1} = r_1 \frac{p-1}{k_1} = (p-1)c_1$ and r2i=1p1gcd(p1,d2i)=r2i=1p1k2=r2p1k2=(p1)c2$\sum_{i=1}^{r_2} \frac{p-1}{gcd(p-1,{d_{2i}})} = \sum_{i=1}^{r_2} \frac{p-1}{k_2} = r_2 \frac{p-1}{k_2}= (p-1)c_2$, respectively, where c1,c2$c_1, c_2 \in \mathbb{N}$. Therefore Y1$Y_1$ and Y2$Y_2$ are (p1)$(p-1)$-covered in C$C'$. By the same arguments in the proof of Lemma2, C$C'$ is the unique minimal (p1)$(p-1)$-covering of F$F$.

Theorem 1 implies that

νp(S(F))=i=1r1v1i(p1)+i=1r2v2i(p1)

=i=1r1(p1)gcd(p1,d