Nonlinear Systems

MTHSC 985 Spring 2001 Clemson University
Topics on Computational Algebra Instructor: Shuhong Gao
Lecture 2, January 22 Scribe: Jira Limbupasiriporn

In this lecture and the next, we consider general systems of polynomials and our main goals are

• Reduce Problem 1.1 and 1.2 to quadratic polynomials, and
• Reduce Problem 1.3 to a single cubic polynomial.

For any system of polynomials $h_1, \dots, h_m \in {\mathbb F}_{2}[x_1, \dots, x_n]$, define

$$N(h_1,\dots,h_m)=\char93 \{\mbox{\em common zeroes of } h_1,\dots,h_m \mbox{\em\ in } {\mathbb F}^{\, n}_{2}\},$$

and

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

$P(h_1, \dots, h_m)$ is called the reliability of the system $h_1, \dots, h_m$. If $x_1, \dots, x_n$ take values from ${\mathbb F}_{2}$ at random, then $P(h_1, \dots, h_m)$ is equal to the probability that $h_1, \dots, h_m$ evaluate to zero simultaneously. We write $P(h_1=\dots=h_m=0)$ to mean probability when the variables take random values from ${\mathbb F}_{2}$. Certainly, computing $N(h_1,\dots,h_m)$ is the equivalent to computing $P(h_1, \dots, h_m)$, but the latter depends only on the variables that actually appear in the system. The bias of a polynomial $h \in {\mathbb F}_{2}[x_1, \dots, x_n]$, denoted B(h), is defined as

$$B(h)=\left\vert\frac{1}{2}-P(h)\right\vert.$$

Examples:

(1)

If h=0, the zero polynomial, then every point in ${\mathbb F}^{\, n}_{2}$ is a zero of h, so N(h)= 2ⁿ, P(h)=1 and $B(h)=\frac{1}{2}$.

(2)

If h=1, then h has no zero in ${\mathbb F}^{\, n}_{2}$, so N(h)=0, P(h)=0 and $B(h)=\frac{1}{2}$.

(3)

Let h=x₁+f where $f \in {\mathbb F}_{2}[x_2, \dots, x_n]$. Then N(h) = 2^n-1, $P(h)=\frac{1}{2}$ and B(h)=0.

(4)

Let h=x₁x₂. Then h=1 if and only if both x₁ and x₂ are zero, thus $P(h)=\frac{3}{4}$ and $B(h)=\frac{1}{4}$.

(5)

Let h=x₁+x₁x₂+x₂. Then h=0 if and only if both x₁ and x₂ are zero, thus $P(h)=\frac{1}{4}$ and $B(h)=\frac{1}{4}$.

The above examples show that the bias is sometimes more convenient to compute, as the number of zeroes of a system depends on the affine space ${\mathbb F}^{\, n}_{2}$ where n may not be the number of variables that actually appear in the system.

Exercise 2.1   Compute the bias of the following polynomials:

(1)

$h=x_1x_2 + x_3x_4 + \dots + x_{2k-1}x_{2k}$, and

(2)

$h=x_1x_2 + x_2x_3 + x_3x_4 + \dots + x_{2k-1}x_{2k}$.

Theorem 2.2   For any quadratic $h \in {\mathbb F}_{2}[x_1, \dots, x_n]$,

$$B(h)=0 \quad \mbox{or} \quad \frac{1}{2^{i+1}} \quad \mbox{for some $0\leq i\leq \lfloor \frac{n}{2} \rfloor$ .}$$

Proof.     The proof is by induction on the number n of variables, and gives a straightforward method for computing B(h)using ${\mathcal O}(n^3)$ bit operations.

Note that x² =x for $x \in {\mathbb F}_{2}$. We may assume that all quadratic terms in h are of the form x_i x_j for $i\ne j$. For n=0, then either h=0 or 1 and we know from the previous example that $B(h)=\frac{1}{2}$, so the theorem is true. For n=1, h must be linear in x₁, and the bias is zero by Example (3) above.

Now assume that $n\geq 2$ and the theorem holds for all quadratic polynomials with n-2 variables. Let $h \in {\mathbb F}_{2}[x_1, \dots, x_n]$ be quadratic. We may assume that h contains at least one variable, say x_n. If h = x_n + h₁ for some $h_1 \in {\mathbb F}_{2}[x_1, \dots, x_{n-1}]$ then B(h)=0 as above. Hence may further assume that h has a quadratic term containing x_n. Then we write h as

 

h=x_n L₁+h₁ (1)

where $L_1 \in {\mathbb F}_{2}[x_1, \dots, x_{n-1}]$ is linear and nonconstant, and $h_1 \in {\mathbb F}_{2}[x_1, \dots, x_{n-1}]$.

Without loss of generality, we may assume that x_n-1 appears in L₁ and write L₁ as

 

L₁ = x_n-1 + L₂ (2)

where $L_2 \in {\mathbb F}_{2}[x_1, \dots, x_{n-2}]$. Also, rewrite h₁ in $(\ref{eq1})$ as

h₁ = x_n-1L₃ + h₂

where $L_3, h_2 \in {\mathbb F}_{2}[x_1, \dots, x_{n-2}]$. Substituting x_n-1 from $(\ref{eq2})$ into h₁, we get

h=x_nL₁+(L₁+L₂)L₃+h₂

Now treat L₁ as a variable. We see $x_1, \dots, x_{n-2}, L_1,x_n$ are independent variables. Thus

$$\begin{eqnarray*}P(h) &=& P(L_1=0)\cdot P(h=0\vert L_1=0)+P(L_1=1)\cdot P(h=0\ve... ...3+h_2)\\ &=& \frac{1}{2}\cdot P(g)+\frac{1}{2}\cdot\frac{1}{2} \end{eqnarray*}$$

where $g=L_2L_3+h_2\in {\mathbb F}_{2}[x_1, \dots, x_{n-2}]$ and is quadratic. Hence

 

$$\frac{1}{2} - P(h) = \frac{1}{2}\cdot \left( \frac{1}{2}-P(g) \right).$$ (3)

This means that $B(h) = \frac{1}{2}B(g)$. Since $g \in {\mathbb F}_{2}[x_1, \dots, x_{n-2}]$, the induction hypothesis implies that

$$B(g)=0 \quad \mbox{or} \quad \left(\frac{1}{2}\right)^{j+1} ... ...mbox{for some $0\leq j \leq \lfloor \frac{n-2}{2} \rfloor$ .}$$

Therefore,    B(h)=0 or $\left(\frac{1}{2}\right)^{i+1}$     for some $i=j+1 \leq \lfloor \frac{n}{2} \rfloor$. $\Box$

Corollary 2.3   For any quadratic polynomial $h \in {\mathbb F}_{2}[x_1, \dots, x_n]$, the number of zeroes of h in ${\mathbb F}^{\, n}_{2}$ can be computed in cubic time.

Now one may wonder whether there is a polynomial time algorithm for computing the number of zeroes of any cubic polynomial $h \in {\mathbb F}_{2}[x_1, \dots, x_n]$. This problem, however, seems to be quite hard and is still open, even though the degree increases only by one! The corresponding problem for an arbitrary system of quadratic polynomials is also open.

Problem 2.1   Given any cubic polynomial $h \in {\mathbb F}_{2}[x_1, \dots, x_n]$, compute N(h).

Problem 2.2   Given any system of quadratic polynomials $h_1, \dots, h_m \in {\mathbb F}_{2}[x_1, \dots, x_n]$, decide if they have a commom zero in ${\mathbb F}^{\, n}_{2}$.

Next we show how to reduce a system of polynomials to a single polynomial.

Theorem 2.4   Let $h_1, \dots, h_m \in {\mathbb F}_{2}[x_1, \dots, x_n]$ and let $y_1, \dots, y_m$be new variables. Then

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

Proof.     Let $x_1,\dots, x_n,y_1,\dots,y_m$ take values from ${\mathbb F}_{2}$ at random. Then

$$\begin{eqnarray*}& & P(y_1h_1+\dots +y_mh_m=0) \\ &=& P((h_1,\dots,h_m)=0)\cdot... ...t \frac{1}{2}\\ &=& \frac{1}{2}P(h_1, \dots, h_m) +\frac{1}{2}, \end{eqnarray*}$$

and the theorem is proved. $\Box$

Using this result, we shall see that Problem 2.2 can be solved in polynomial time if m is fixed.