Polynomial systems and the related problems

MTHSC 985 Spring 2001 Clemson University
Topics on Computational Algebra Instructor: Shuhong Gao
Lecture 1, January 17 Scribe: Jeff Farr

Polynomial systems play a fundamental role in many areas of mathematics and science in general. In this course, we are mainly concerned with polynomials over finite fields and the field of rational numbers. We shall consider some basic problems that arise in coding theory, cryptography, computational complexity, and symbolic computation.

We shall first consider polynomial systems and related problems over finite fields. For simplicity, let's start with the finite field ${\mathbb F}_{2}=\{0,1\}$where addition and multiplication are done modulo 2, or equivalently addition corresponds to XOR and multiplication corresponds to AND. Either of the two operations is called a bit operation. Further, let ${\mathbb F}_{2}[x_1, \dots, x_n]$ be the ring of all polynomials in n variables with coefficients from ${\mathbb F}_{2}$, and let ${{\mathbb F}^{\, n}_{2}} = \{(a_1, \dots, a_n) : a_i \in {\mathbb F}_{2}\}$ denote the set of n-tuples (or n-bit strings) over ${\mathbb F}_{2}$, which is a vector space of dimension n over ${\mathbb F}_{2}$. An n-tuple in ${\mathbb F}^{\, n}_{2}$ is also called a vector or a point.

For any system of polynomials $h_1, \dots, h_m \in {\mathbb F}_{2}[x_1, \dots, x_n]$, an n-tuple $a \in {\mathbb F}^{\, n}_{2}$ is called a common zero, or simply a zero, or a solution, of the system if

$$h_i(a)=0, \ \ i=1, \ldots, m.$$

Consider the following problems:

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

Problem 1.2   Given any system of polynomials $h_1, \dots, h_m \in {\mathbb F}_{2}[x_1, \dots, x_n]$, find a common zero in ${\mathbb F}^{\, n}_{2}$ if exists.

Problem 1.3   Given any system of polynomials $h_1, \dots, h_m \in {\mathbb F}_{2}[x_1, \dots, x_n]$, find the number of common zeroes in ${\mathbb F}^{\, n}_{2}$.

Problem 1.1 is a decision problem; the answer is simply a yes or no. Problem 1.2 asks for more, namely, actually finding a common zero whenever it exists. Problem 1.3 also asks for more than that of Problem 1.1, since if one can find the number of common zeroes then one knows for sure whether the system has a zero or not. A naive method to solving these problems would be the brute-force or exhaustive approach: plug each of the 2ⁿ points in ${\mathbb F}^{\, n}_{2}$ into the polynomials and check if they evaluate to zero. All the three problems are solved at once. In a worst-case scenario, this approach requires at least O(m2ⁿ) bit operations, which is exponential in n.

Can we do any better than this? That is, is there an algorithm to solve these problems using a polynomial number of bit operations? Let's look at some special cases.

Linear Systems

Consider the following example:

$$\begin{eqnarray*}f_1 & = & x_1+x_3+x_5+x_7 \\ f_2 & = & x_1+x_2+x_5+x_6 \\ f_3 & = & x_1+x_2+x_3+x_4. \end{eqnarray*}$$

The problem is equivalent to solving

$$\begin{pmatrix}1 0 1 0 1 0 1 \\ 1 1 0 0 1 1 0 \\ 1 1 1 1 0 0 ... ...matrix} \begin{pmatrix}x_1 \\ \vdots \\ x_7 \end{pmatrix} =0.$$

Certainly, one can easily solve this system by using Gaussian elimination:

$$\begin{pmatrix}1 0 1 0 1 0 1 \\ 1 1 0 0 1 1 0 \\ 1 1 1 1 0 0 ... ...x}1 0 0 1 0 1 1 \\ 0 1 0 1 1 0 1 \\ 0 0 1 1 1 1 0 \end{pmatrix}$$

where the last step corresponds to backward substitution. This means that the system is equivalent to the following system:

$$\begin{eqnarray*}g_1 & = & x_1+x_4+x_6+x_7 \\ g_2 & = & x_2+x_4+x_5+x_7 \\ g_3 & = & x_3+x_4+x_5+x_6. \end{eqnarray*}$$

Thus all the solutions are of the form

$$\begin{eqnarray*}x_1 & = & x_4+x_6+x_7 \\ x_2 & = & x_4+x_5+x_7 \\ x_3 & = & x_4+x_5+x_6, \end{eqnarray*}$$

where x₄, x₅, x₆, x₇ are free parameters taking arbitrary values in ${\mathbb F}_{2}$. Hence there are 2⁴ solutions.

How many bit operations does the Gaussian elimination method need? Suppose that H is an $m \times n$ matrix over ${\mathbb F}_{2}$. Then in the worst case one needs to eliminate m columns and eliminating each column (including backward substitution) involves at most (m-1) row operations, namely (m-1) additions of n-bit strings. One needs at most m(m-1)n = O(m²n) bit operations. Hence the Gaussian elimination method runs in cubic time when $m \sim n$. Essentially, we have proved the following result.

Theorem 1.1   For any $m \times n$ matrix H over ${\mathbb F}_{2}$ and any column n-vector b over ${\mathbb F}_{2}$, the linear system Hx=b can be solved by Gaussian elimination using O(m²n) bit operations.

Note the solutions of the above system can also be written as follows:

$$(x_1, \dots, x_7) = (x_4, \dots, x_7) \begin{pmatrix} 1 1 1 ... ...0 0 1 0 \\ 1 1 0 0 0 0 1 \end{pmatrix} = (x_4, \dots, x_7) G$$

where G denotes the matrix on the left. In general, the solutions of any linear system H x=0 can be written in the above form and they form a linear subspace of ${\mathbb F}^{\, n}_{2}$, called a linear code. The matrix H is called a parity-check matrix for the code, while matrix G is called a generator matrix for the code.

Now we put some restrictions on the solutions. The Hamming weight of an n-tuple is defined to be the number of its nonzero entries.

Problem 1.4   (Finding minimal distances of linear codes). Given an integer w and an $m \times n$ matrix H over ${\mathbb F}_{2}$, decide whether the linear system Hx=0 has a solution with Hamming weight exactly w.

For a linear code, its minimum distance is equal to the minimum weight of its nonzero vectors. Hence if one can solve the above decision problem efficiently then one can compute the minimum distance of any linear code by letting $w=1, 2, \dots, n$.

Problem 1.5   (Decoding linear codes). Given an integer w, an $m \times n$ matrix H and a column n-vector b, decide whether the linear system Hx=b has solutions with Hamming weight w.

Here one may think of b as the syndrome of a received vector and a solution x as an error vector. So the problem is to decide if b comes from a code word with w errors.

The performance of a code depends not only on its minimum distance but also on its weight distribution. To evaluate a code, it is critical to be able to find the number of code words with any given weight.

Problem 1.6   (Computing weight distribution). Given an integer w and an $m \times n$ matrix H over ${\mathbb F}_{2}$, find the number of solutions of the linear system Hx=0 with Hamming weight exactly w.

More generally, it is desirable to be able to compute the weight distribution of the cosets of a linear code, which measures the practical performance of a code more accurately.

Problem 1.7   (Computing weight distribution). Given an integer w, an $m \times n$ matrix H and a column n-vector b, find the number of solutions of the linear system Hx=b with Hamming weight exactly w.

We shall see later that Problems 1.4 and 1.5 are NP-complete and Problems 1.6 and 1.7 are NP-hard.

Finally, if there is no restriction on the solutions but the matrix Hhas some special structure, can one solve the system Hx=b faster than cubic time? We shall see on the one hand that in decoding of several classes of codes such as Reed-Solomon codes, BCH codes or possibly Hermitian codes, the matrix H is of Toeplitz type. On the other hand, linear systems arise from breaking public-key cryptosystems or from symbolic computation have few nonzero entries. In both cases, we say that the matrix H is sparse. It is desirable to have fast algorithms to solve sparse systems.

Problem 1.8   Given a sparse $m \times n$ matrix H and a column n-vector b over ${\mathbb F}_{2}$, solve the linear system Hx=b efficiently.

We shall see that the current methods for solving the above problem involve several techniques ranging from Gcd, resultant, continued fractions and Padé approximations to Berlekamp-Massey algorithm, Krylov subspace methods and fast FFT algorithms.