Nonlinear Systems (continued)

MTHSC 985 Spring 2001 Clemson University
Topics on Computational Algebra Instructor: Shuhong Gao
Lecture 3, January 24 Scribe: Virgínia Rodrigues

Recall: Let $h_1,...,h_m \in {\mathbb F}_{2}[x_1, \dots, x_n]$. We defined

$$\begin{eqnarray*}N(h_1,\dots,h_m) & = &\char93 \{\mbox{\em common zeroes of } h_... ...h_m) &=& \frac{ N(h_1,\dots,h_m) }{2^n} = Prob(h_1=\dots=h_m=0). \end{eqnarray*}$$

We showed that

$$\frac{1}{2}P(h_1,\dots,h_m)=P(y_1h_1+\dots+y_mh_m)-\frac 1 2.$$ (4)

This equation can be interpreted as follows.

Corollary 3.1   For any $h_1, \dots, h_m \in {\mathbb F}_{2}[x_1, \dots, x_n]$,

$$N(h_1,\dots,h_m)=\frac 1{2^{m-1}}N(y_1h_1+\dots+y_mh_m)-2^n.$$

Proof. It follows from the definitions above that

$$P(h_1,\dots,h_m) = \frac{N(h_1,\dots,h_m)}{2^n}$$

and

$$P(y_1h_1+\dots+y_mh_m) = \frac{N(y_1h_1+\dots+y_mh_m)}{2^{m+n}}.$$

So, from (4) we get

$$\frac 1 2\frac{N(h_1,\dots,h_m)}{2^n}=\frac{N(y_1h_1+\dots+y_mh_m)}{2^{m+n}}-\frac 1 2.$$

The result follows by multiplying both sides by 2ⁿ⁺¹. $\Box$

A direct proof. We count the zeroes of $y_1h_1+\dots+y_mh_m$ by first fixing $(x_1,\dots,x_n) \in {\mathbb F}^{\, n}_{2}$ and then check the number of choices for $(y_1,\dots,y_m) \in {\mathbb F}_2^m$. On the one hand, if $(x_1,\dots,x_n)$ is a common zero of $h_1, \dots, h_m$, which happens $N(h_1,\dots,h_m)$ times, then $(y_1,\dots,y_m)$ can be any m-tuple, which has 2^m choices. On the other hand, for any n-tuple $(x_1,\dots,x_n) \in {\mathbb F}^{\, n}_{2}$ such that $h_i(x_1,\dots,x_n) \neq 0$ for some $i \in \{1,\dots,m\}$, which happens $2^n-N(h_1,\dots,h_m)$ times, y_i is uniquely determined by $y_1,\dots,y_{i-1}, y_{i+1}, \dots, y_m$, which has 2^m-1 choices. Hence

$$N(y_1h_1+\dots+y_mh_m)=2^mN(h_1,\dots,h_m)+2^{m-1}(2^n-N(h_1,\dots,h_m)).$$

The formula follows immediately. $\Box$

Therefore, to compute $N(h_1,\dots,h_m)$ for an arbitrary system of quadratic polynomials $h_1, \dots, h_m$ $\in {\mathbb F}_{2}[x_1, \dots, x_n]$, we can run through $(y_1,\dots,y_m) \in {\mathbb F}_2^m$ and for each of them count the number of zeroes of the corresponding quadratic polynomial $y_1h_1+\dots+y_mh_m$ (which can be done in cubic time). Hence we have

Corollary 3.2   For any system of quadratic polynomials $h_1, \dots, h_m \in {\mathbb F}_{2}[x_1, \dots, x_n]$, one can compute $N(h_1,\dots,h_m)$ in ${\mathcal O}(2^mn^3)$ bit operations.

As a direct consequence, we see that for a fixed number m, any system of m quadratic polynomials over ${\mathbb F}_{2}$ can be solved in polynmial time.

Next, we want to reduce a general system of polynomials to a system of quadratic polynomials. The method works for polynomials over an arbitrary field and we illustrate it by an example. Let

h=x₁¹⁰x₂+x₁x₂x₃x₄+x₃x₄.

The basic idea is to record down a computation for h. First we let

$$z_1=x_1x_2 \mbox{\ and\ \ } z_2=x_3x_4.$$

Now write

x₁¹⁰x₂=x₁⁹x₁x₂=((x₁²)²)²x₁z₁,

where we use square and multiply method to compute a large power. Let $z_3=x_1^2,\ z_4=z_3^2$, and z₅=z₄². Then x₁¹⁰x₂=z₅x₁z₁. Thus, taking z₆=z₅x₁ we get

h=z₆z₁+z₁z₂+z₂,

a quadratic polynomial.

Now we consider the following quadratic polynomials in ${\mathbb F}_{2}[x_1,\dots,x_4,z_1,\dots,z_6]$ where $z_1,\dots,z_6$ are variables independent of $x_1,\dots,x_4$:

$$\begin{eqnarray*}g_1 & = & z_1-x_1x_2,\\ g_2 & = & z_2-x_3x_4,\\ g_3 & = & z_3... ...-z_4^2,\\ g_6 & = & z_6-z_5x_1,\\ g_7 & = & z_6z_1+z_1z_2+z_2. \end{eqnarray*}$$

Then

$$N(h)=N(g_1,\dots,g_7).$$

To see this, note that any common zero $(x_1,\dots,x_4, z_1,\dots,z_6)$of g₁,g₂,...,g₇ implies that

$$\begin{eqnarray*}0 & = & g_7\ =\ z_6z_1+z_1z_2+z_2\\ & = & (z_5x_1)(x_1x_2)+(x... ... & \dots \\ & = & x_1^{10}x_2+x_1x_2x_3x_4+x_3x_4\\ & = & h, \end{eqnarray*}$$

namely, $(x_1,\dots,x_4)$ is a zero of h. Conversely, each zero $(x_1,\dots,x_4)$ of h corresponds to a common zero of $g_1,\dots,g_7$, namely $(x_1,\dots,x_4, z_1,\dots,z_6)$, where $z_1,\dots,z_6$ are computed from $(x_1,\dots,x_4)$ as above.

Following the process above we can reduce any system of polynomials in ${\mathbb F}_{2}[x_1, \dots, x_n]$ to a system of quadratic polynomials.

Theorem 3.3   For any system $h_1, \dots, h_m \in {\mathbb F}_{2}[x_1, \dots, x_n]$, there is a system of quadratic polynomials $g_1, \dots, g_t$ (with additional new variables) such that $N(h_1,\dots,h_m) = N(g_1, \dots, g_t)$.

Note that number t in the above theorem corresponds to the length of any computation for the system $h_1, \dots, h_m$, and the number of new variables in $g_1, \dots, g_t$ is at most t. One may take tto be the length of a shortest straight-line program for computing the system $h_1, \dots, h_m$. In particular, t is bounded by the naive size of the system, which may be defined to be ${\mathcal O}(nT\log d)$ where n is the number of variables, d is the largest degree in each variable, and T is the total number of terms in the whole system.

By applying Corollary 3.1, we obtain the next result.

Theorem 3.4   For any system $h_1, \dots, h_m \in {\mathbb F}_{2}[x_1, \dots, x_n]$ there is a cubic polynomial g (with additional new variables) such that $N(h_1,\dots,h_m)$ is easily determined from N(g). Furthermore, the size of g is the same as that of the system $h_1, \dots, h_m$.

Homework. Find a polynomial time algorithm to count the number of zeroes of an arbitrary cubic polynomial in ${\mathbb F}_{2}[x_1, \dots, x_n]$.

Remark. All the problems and results we discussed so far apply to any finite field ${\mathbb F}_{q}$ with only slight modifications. All the problems are still solvable in finite time, though not necessarily in polynomial time.

Exercise 3.5   Generalize Corollary 3.1 to ${\mathbb F}_{q}$.

Over rational numbers. For polynomials over an infinite field, all the problems we discussed so far may become unsolvable. For example, consider polynomials with coefficients from the field ${\mathbb Q}$ of rational numbers. Let $h_1,...,h_m \in {\mathbb Q}[x_1,\dots,x_n]$. Is there an algorithm that decides in finite time whether $h_1, \dots, h_m$ have a common zero in ${\mathbb Q}^n$? This is Hilbert's tenth problem (one of the famous 23 problems proposed by him in 1900). It was answered negatively by Y. V. Matiyasevich in 1970 (when he was twenty years old). He proved that this problem is unsolvable, that is, no such algorithm exist at all! Even more amazing, there is a single polynomial with only 9 variables (constructed explicitly) that is unsolvable!

Over an algebraically closed field. A field ${\mathbb F}$ is called algebraically closed if every univariate polynomial in ${\mathbb F}[x]$ has a zero in ${\mathbb F}$. For example, the field ${\mathbb C}$ of complex numbers is algebraically closed. One can prove that every field ${\mathbb F}$ is contained in some algebraically closed field, and the smallest such field is called the algebraic closure of ${\mathbb F}$, denoted by $\overline{\mathbb F}$. (One may view $\overline{\mathbb F}$ as a wonder box that contains the roots of all polynomials in ${\mathbb F}[x]$.)

An algebraically closed field ${\mathbb F}$ must be infinite and, unlike the field ${\mathbb Q}$ of rational numbers, polynomials in ${\mathbb F}[x_1, \dots, x_n]$are solvable in finite time. This is done via Hilbert's Nullstellensatz which says that a system $h_1, \dots, h_m$in ${\mathbb F}[x_1, \dots, x_n]$ have no common zero in ${\mathbb F}^n$ if and only if there are polynomials $g_1, \dots, g_m$ in ${\mathbb F}[x_1, \dots, x_n]$such that

$$g_1 h_1 + \cdots + g_m h_m =1.$$ (5)

Recently bounds on the degrees of g_i have been proved, and in fact one may take $\deg g_i \leq D^n$ where D is the maximum of 3 and the total degrees of h_i. Hence (5) is a finite system of linear equations for the coefficients of g_i, so it can be decided in finite time. If one wants polynomial time algorithm, then the problem is widely open.

Over an arbitrary field. Let ${\mathbb F}$ be any field. Certainly one expects problems over ${\mathbb F}$ to be hard. There is, however, a simple bound on the number of zeroes which is extremely useful in practice. To be precise let $S\subseteq {\mathbb F}$ be a finite subset and $f\in {\mathbb F}[x_1,\dots,x_n]$. Define

$$N_f(S)=\char93 \{(a_1,...,a_n) \in S^n:f(a_1,...,a_n)=0\}.$$

Exercise 3.6   Prove that for any nonzero $f\in {\mathbb F}[x_1,\dots,x_n]$

$$N_f(S) \leq d\vert S\vert^{n-1}$$

where d is the total degree of f.

This result shows that a nonzero polynomial is likely to evaluate to nonzero value when the variables take random values from a large set.

Lemma 3.7   Let $f\in {\mathbb F}[x_1,\dots,x_n]$ be nonzero of total degree d and S a finite subset of ${\mathbb F}$. If $x_1, \dots, x_n$ take random values from S, then the the probability that f is nonzero is at least

$$1- \frac{d}{\vert S\vert}.$$

When S is large, the above probability is essentially one. Later we shall use this result to prove an effective Hilbert irreducibility theorem.