Topics for Course Projects

MTHSC 985 Spring 2001 Clemson University
Topics on Computational Algebra Instructor: Shuhong Gao
Lecture 15, March 7 Scribe: Todd Mateer

1 (Interpolation I). Let $P_1, P_2, .... , P_t \in {\mathbb F}^n$ be t distinct points and let

$$I(P_1, P_2, .... , P_t) = \{f \in {\mathbb F}[x_1, \dots, x_n]: f(P_i) = 0, 1 \leq i \leq t\}.$$

This is a radical ideal.

Problem. Given $P_1, P_2, .... , P_t \in {\mathbb F}^n$and a monomial order on ${\mathbb F}[x_1, \dots, x_n]$, find a Gröbner basis for I(P₁, P₂, .... , P_t)and the corresponding monomial basis B.

It may be possible to find an algorithm that solves the problem using only ${\mathcal O}(t^2 \cdot n)$ operations in ${\mathbb F}$.

Reference.

1.

Zeljko Zilic and Katarzyna Radecka, On feasible multivariate polynomial interpolations over arbitrary fields, preprint, 2000.

2.

H. M. Möller and B. Buchberger, The construction of multivariate polynomials with preassigned zeros, in Computer Algebra, EUROCAM '82, European Computer Algebra Conference, Marseille, France, April 1982, LNCS 144 (Springer-Verlag, Berlin-New York, 1982), 24-31.

Special case: n = 2. Suppose $P_i = (a_i, b_i) \in {\mathbb F}^2$ for $i \leq 1 \leq t$. First assume a₁, a₂, .... , a_t are distinct. Let

$$\begin{eqnarray*}f_1 & = & {\prod_{i=1}^{t} (x-a_i)}\\ f_2 & =& y - u(x), \end{eqnarray*}$$

where $u(x) \in {\mathbb F}[x]$ such that u(a_i) = b_i for $1\leq{i}\leq{t}$. Then $G = \{f_1, f_2\}$ is a Gröbner basis for I under lexicographic order with y > x.

Next assume that a₁, a₂, ... , a_t are not distinct. By reordering the points, we may assume that a₁, a₂, ..., a_k are all the distinct ones. Suppose that a_i repeats l_i times for all $1 \leq i \leq k$ and $l_1 \geq l_2 \geq ... \geq l_k$. The histogram of the distribution $l_1, \cdots, l_k$is plotted in Figure 15-1 where a point $(u,v) \in {\mathbb N}^2$ is in the shaded area if and only if $u\leq i$ and $v\leq l_i$ for some $1 \leq i \leq k$.

Figure 15-1: Histogram of point distribution

Claim (conjecture): Under lexicographic order with y > x, B(I) has the same shape as the graph in Figure 15-1, i.e., $(i,j) \in B(I)$ if and only if (i,j) is under the "stairs".

2 (Interpolation II). Let $P_1, P_2, .... , P_r \in {\mathbb F}^{n}$ and $m_1, m_2, ... , m_r \geq 1$ be integers. Define $I \subset {\mathbb F}[x_1, \dots, x_n]$ to be the unique ideal such that $V({\mathbf I}) = \{P_1, P_2, ... , P_r\}$ and P_i has multiplicity m_i for $1 \leq i \leq r$. Note that I is not a radical ideal if one of m_i is greater than 1.

The problem is to find a Gröbner basis for Iunder some monomial order. The algorithm should have running time ${\mathcal O}(n \cdot t^2)$ where $t = \sum_{i=1}^{r} m_i$.

This problem is related to a list decoding algorithm of Sudan.

Reference.

1.

Venkatesan Guruswami and Madhu Sudan, Improved decoding of Reed-Solomon and algebraic-geometric codes, Electronic Colloquium on Computational Complexity, Report No. 43 (1998).

3 (Chinese Remainder Theorem for ${\mathbb F}[x_1, \dots, x_n]/I$). Prove the theorem on page 40 in Lecture 13.

4 (Hermitian codes and BCH codes). The goal is to explore the possibility that Hermitian codes may be special BCH codes.

Specifically, let q = r² be a prime power and

$$I = \left<x^q - x, y^q - y, x^r + x - y^{r+1}\right> \subset F_q[x,y].$$

Then a Hermitian code C is the Fourier transform of a subspace $\widehat{C}$ of the ring

$$F_q[x,y]/I \subset {\mathbb F}_{q^2}[x,y]/({\mathbf I}\cdot {\mathbb F}_{q^2}[x,y]).$$

Let $H = V(I) = \{(\alpha, \beta) \in {\mathbb F}_q^2 : \alpha^r + \alpha = \beta^{r+1} \}$. Suppose $\gamma$ is such that ${\mathbb F}_{q^2} = {\mathbb F}_q[\gamma]$. Let

$$I_1 = \left<z - (x + \gamma \cdot y), x^q - x, y^q - y, x^r + x - y^{r + 1} \right> \subseteq {\mathbb F}_{q^2}[x,y,z].$$

Show that

$${\mathbb F}_{q^2}[x,y]/({\mathbf I}\cdot {\mathbb F}_{q^2}[x,... ... {\mathbb F}_{q^2}[x,y,z]/I_1 \cong {\mathbb F}_{q^2}[z]/(f(z))$$

where

$$f(z) = \prod_{(\alpha, \beta) \in H} (z - (\alpha + \gamma \beta)) \in {\mathbb F}_{q^2} [z].$$

Compute the discrete logarithms of the elements $\alpha + \gamma \beta$in ${\mathbb F}_{q^2}$, $(\alpha, \beta) \in H$. Study the isomorphic image of $\widehat{C}$ in ${\mathbb F}_{q^2}[z]/(f(z))$and check if they give BCH codes over ${\mathbb F}_{q}$.

5 (Solving equations and eigenvectors). Show how to use Gröbner bases and eigenvectors to find solutions for systems of polynomials that define a zero-dimensional algebra.

6 (Gröbner bases and Automatic theorem proving). Describe Wu's theory and show at least two interesting theorems in elementary geometry.

Reference:

1.

David Cox, John Little and Donal O'Shea, Ideals, varieties, and algorithms. An introduction to computational algebraic geometry and commutative algebra. Second edition. Undergraduate Texts in Mathematics. Springer-Verlag, New York, 1997.

2.

S.C. Chou, Mechanical Geometry Theorem Proving, Reidel, Dordrecht, 1988.

7 (Fast Fourier transform). In some rings, Fourier transform can be computed extremely fast. For example, in ${\mathbb C}[x]/(x^t-1)$ where t is a power of 2, the Fourier transform can be computed using ${\mathcal O}(t \log t)$ operations in ${\mathbb C}$.

Investigate other rings ${\mathbb F}[x_1, \dots, x_n]/{\mathbf I}$ where fast Fourier transform is possible. It's most interesting to consider the case of finite fields.

8 (Syzygies). Study Gröbner bases for modules over rings and its relations to decoding of BCH codes. Present a unified theory for the two methods of gcd and Berlekamp-Massey.

Reference:

1.

David Cox, John Little and Donal O'Shea, Using algebraic geometry. Graduate Texts in Mathematics, 185. Springer-Verlag, New York, 1998.

2.

Patrick Fitzpatrick, On the key equation, IEEE Trans. on Inform. Theory, vol. 41, No. 5, September, 1995, 1290-1302.

9 (Decoding affine codes via Gröbner bases). Survey the following three papers and compute an explicit example.

1.

A. Brint Cooper, Toward a new method of decoding algebraic codes using Gröbner bases, Trans. 10th Army Conference on Applied Mathematics and Computing (West Point, NY, 1992), pp. 1-11, U.S. Army Research Office, Research Triangle Park, NC, 1993.

2.

X. Chen, I.S. Reed, T. Helleseth, and T.K. Truong, Algebraic decoding of cyclic codes: a polynomial ideal point of view, in Finite Fields: Theory, Applications, and Algorithms (Las Vegas, NV, 1993), Contemp. Math. 168, Amer. Math. Soc., Providence, 1994, 15-22.

3.

J. Fitzgerald and R. F. Lax, Decoding affine variety codes using Gröbner bases, Designs, Codes and Cryptography, 13 (1998), 147-158.

10 (Solving large sparse linear systems). Give a survey of the current fast algorithms for solving large sparse linear systems over finite fields and implement some of them in NTL. Do some experiment for factoring polynomials of high degrees or for computing discrete logarithms in large finite fields.