An Elementary Approach to Ax-Katz, McEliece’s Divisibility and Applications to Quasi-Perfect

Binary 2-Error Correcting Codes

Francis N. Castro

Department of Mathematics University of Puerto Rico

Río Piedras, Puerto Rico 00931-3355 Email: fcastro@goliath.cnnet.clu.edu

Ivelisse Rubio

Department of Mathematics University of Puerto Rico Humacao, Puerto Rico 00791 Email: ive@mate.uprh.edu

Hugues Randriam

Ecole nationale supérieure des télécommunications 46 rue Barrault 75634 Paris Cedex 13 – France Email: randriam@email.enst.fr

Oscar Moreno

Department of Computer Science

University of Puerto Rico Rııo Piedras, Puerto Rico 00931-3355

Email: moreno@upr.pr

H. F. Mattson, Jr.

Electrical Engineering and Computer Science Syracuse University CST 2-179 Syracuse, New York 13244-4100 Email: hmattson@syr.edu

Abstract— In this paper we present an algorithmic approach to the problem of the divisibility of the number of solutions to a system of polynomial equations. Using this method we prove that all binary cyclic codes with two zeros over 𝔽_{2^{f}} and minimum distance 5 are quasi-perfect for f ≤ 10. We also present elementary proofs of divisibility results that, in some cases, improve previous results.

I. Introduction

Even though the Ax-Katz, McEliece divisibility results have been used widely in coding theory (for example see [16],[10]) and cryptography (for example [3],[5]), most of the methods required advanced mathematical theory and were not algorithmic. This motivates us here to study elementary and algorithmic approaches to this problem.

In this paper we present new approaches to the problem of the divisibility of the number of solutions to a system of polynomial equations:

1) We use integer linear programming to estimate the divisibility in our generalization of McEliece’s theorem ([14]). In Section III, we show that this method has the advantage of being algorithmic and easy to program and, as a consequence, in Section IV we prove that all binary cyclic codes with two zeros over 𝔽_{2^{f}} and minimum distance 5 are quasi-perfect for f ≤ 10. This new result is remarkable since it was previously thought that being double error-correcting and quasi-perfect was a rare property.

2) We give an elementary proof of the divisibility result by Moreno-Moreno. For the prime field case we also present a new improvement to results by Adolphson-Sperber ([1]) and Ax-Katz ([8]), which solves a question raised by Ax in [2]. This proof is completely algorithmic, hence giving an elementary proof of the algorithmic treatment of the divisibility problem.

II. Generalization of McEliece’s Theorem The following is the characteristic 2 version of the well known theorem of McEliece ([15]) that we generalize to the multi-variable case:

Theorem 1 (McEliece [15]). Let C be a binary cyclic code and let l be the smallest number such that (l + 1) nonzeros of C (with repetitions allowed) have product equal to 1. Then the weight of every codeword is divisible by 2^{l} and there is a codeword w ∈ C such that 2^{l+1} does not divide the weight of w.

Let F (x_{1}, x_{2}, …, x_{n}) = ∑_{i=1}^{N} a_{i}x_{1}^{e_{1i}}x_{2}^{e_{2i}} ⋯ x_{n}^{e_{ni}} be a polynomial over a finite field 𝔽_{p^{f}}. We denote by ζ a primitive p-th root of unity over Q and put θ = 1 − ζ, so that pA = θ^{p−1}A where A = ℤ[ζ] is the ring of integers of Q(ζ). Set S(F) = ∑_{x∈𝔽_{p^{f}}^{n}} ζ^{T r(F (x))}, where T r is trace function

from 𝔽_{p^{f}} to 𝔽_{p}. We say that θ^{l} divides S(F) if there exists a ∈ ℤ[ζ] such that S(F) = aθ^{l}. The divisibility of S(F) gives us the divisibility of the number of solutions to a system of polynomial equations and hence the divisibility of the weights of codewords.

We associate to F the following system of modular equations:

e_{11}t_{1} + ⋯ + e_{1N}t_{N} ≡ 0 mod p^{f} − 1
⋮  ⋮  ⋮  (1)
e_{n1}t_{1} + ⋯ + e_{nN}t_{N} ≡ 0 mod p^{f} − 1,

where 0 ≤ t_{i} ≤ p^{f} − 1. The system (1) determines the pdivisibility of S(F); i.e., if

μ = min_{{(t_{1},...,t_{N}) \atop is solution of(1)}}\{σ_{p}(t_{1}) + ⋯ + σ_{p}(t_{N})\},  (2)

then p^{μ} divides S(F), where σ_{p} is the p-weight function. In [14] we needed p-adic analysis and the theorem of Stickelberger to justify that p^{μ}|S(F); an innovation in this paper is that, in Section V, we present a completely elementary proof of this result.

The relation of McEliece’s theorem and modular equations can be found in [4]. Now, using the above modular system and the properties of the p-weight function, the following generalization of McEliece’s theorem([15]) was proved in [14]. It also improves results by Ax-Katz [2] and Adolphson-Sperber [1].

Theorem 2. Let G be the set of polynomials spanned by the monomials of F. That is,

G = {a_{1}x_{1}^{e_{11}} ⋯ x_{n}^{e_{n1}} + ⋯ + a_{N}x_{1}^{e_{1N}} ⋯ x_{n}^{e_{nN}} |

a_{1}, …, a_{N} ∈ 𝔽_{p^{f}} } .

With μ as in (2), there is at least one polynomial G ∈ G such that S(G) is divisible by θ^{μ} but not by θ^{μ+1}.

III. Divisibility Properties Reduced to a Problem in Integer Linear Programming

In this section we estimate the divisibility of the exponential sum S(F) by associating it to a system of inequalities that form a problem of integer linear programming. Solving such a problem might be hard but, in many cases, we obtain good estimates using elementary methods.

The system (1) is equivalent to the following system of equations:

e_{11}t_{1} + ⋯ + e_{1N}t_{N} = c_{1}(p^{f} − 1)

⋮  ⋮  (3)

e_{n1}t_{1} + ⋯ + e_{nN}t_{N} = c_{n}(p^{f} − 1),

where 0 ≤ t_{i} ≤ p^{f} − 1 and c_{i} > 0. Using the properties of the p-weight function σ_{p}, we obtain

σ_{p}(e_{11})σ_{p}(t_{1}) + ⋯ + σ_{p}(e_{1N})σ_{p}(t_{N}) ≥ σ_{p}(c_{1}(p^{f} − 1)) ≥ (p − 1)f

⋮  ⋮  ⋮ (4)

σ_{p}(e_{n1})σ_{p}(t_{1}) + ⋯ + σ_{p}(e_{nN})σ(t_{N}) ≥ σ_{p}(c_{n}(p^{f} − 1)) ≥ (p − 1)f.

Now, our problem of finding the divisibility of S(F) reduces to the integer linear programming problem of finding \underline{μ} = min_{(T_{1},...,T_{N})}\{T_{1} + ⋯ + T_{N} |, (T_{1}, …, T_{N}) is a solution of system below} :

σ_{p}(e_{11})T_{1} + ⋯ + σ_{p}(e_{1N})T_{N} ≥ (p − 1)f

⋮  ⋮  ⋮  (5)

σ_{p}(e_{n1})T_{1} + ⋯ + σ_{p}(e_{nN})T_{N} ≥ (p − 1)f.

Note that \underline{μ} ≤ μ, therefore θ\underline{μ} divides S(F) if θ^{μ} does.

IV. Quasi-perfect Cyclic Codes In this section, we use the divisibility results and the

algorithmic methods to obtain that every binary primitive cyclic code with two zeros over 𝔽_{2^{f}} and minimum distance 5 is quasi-perfect for f ≤ 10.

Let N_{β_{1},β_{2}}(d_{1}, d_{2}) be the number of solutions over 𝔽_{2^{f}} of the following system of polynomial equations:

x_{1}^{d_{1}} + x_{2}^{d_{1}} + x_{3}^{d_{1}} = β_{1}x_{4}^{d_{1}}
x_{1}^{d_{2}} + x_{2}^{d_{2}} + x_{3}^{d_{2}} = β_{2}x_{4}^{d_{2}}.  (6)

Now consider the code C with zeros α^{d_{1}} and α^{d_{2}} over 𝔽_{2^{f}}, where α is a primitive root of 𝔽_{2^{f}}. C being quasi-perfect depends on the covering radius and the minimum distance of C. Double error-correcting codes with two zeros over 𝔽_{2^{f}} are known for f ≤ 25 (for example, see [4]). The covering radius of C is 3 if and only if system (6) has a solution with x_{1}x_{2}x_{3}x_{4} ≠ 0. The existence of this type of solutions to the system and hence quasi-perfection is given by the following theorem proved in [11].

Theorem 3. Let α be a primitive root of 𝔽_{2^{f}} and let C be the code with zeros α^{d_{1}}, α^{d_{2}} over 𝔽_{2^{f}}, and minimum distance 5. Then C is a quasi-perfect code whenever 4 divides N_{β_{1},β_{2}}(d_{1}, d_{2}).

Several infinite families of quasi-perfect codes with two zeros are known ([7], [5], [10]). Theorem 3 gives a way to get quasi-perfect codes, but, to apply it, we would need to give a theoretical proof that 4 divides N_{β_{1},β_{2}}(d_{1}, d_{2}) for all (β_{1}, β_{2}) ≠ (0, 0) and this can be very difficult. However, if we follow the techniques of Section III, we can determine divisibility with a computer program. For this, as in [14], consider the following modular system associated to (6):

d_{1}t_{1} + d_{2}t_{2} ≡ 0 mod 2^{f} − 1
⋯ ⋮  (7)
d_{1}t_{7} + d_{2}t_{8} ≡ 0 mod 2^{f} − 1
t_{1} + t_{3} + t_{5} + t_{7} ≡ 0 mod 2^{f} − 1
t_{2} + t_{4} + t_{6} + t_{8} ≡ 0 mod 2^{f} − 1.

Now, we need to prove that μ > 2f + 1, where μ is as defined in (2). Note that the computation of μ is not a difficult one. In the cases we computed, we only need to compute the minimum μ_{p} of just one modular equation,i.e.,

μ_{p} = min{σ_{2}(u) + σ_{2}(v) | d_{1}u + d_{2}v ≡ 0 mod 2^{f} − 1 },

and this is simple. This is true since μ ≥ 4μ_{p} − 2f.

Using the above procedure, we verified that μ > 2f + 1 for f ≤ 10 and obtained the following result:

Theorem 4. Let C be a binary primitive cyclic code with two zeros over 𝔽_{2^{f}} and minimum distance 5. If f ≤ 10, then C is a quasi-perfect code.

Formerly, finding primitive quasi-perfect codes with minimum distance 5 and two zeros was considered difficult, but, as we mentioned, there are infinite families of such codes. Now Theorem 4 suggests that it is difficult to find codes with minimum distance 5 that are not quasi-perfect.

Problem: Prove that all the binary primitive cyclic codes with two zeros and minimum distance 5 are quasi-perfect or find the smallest binary primitive cyclic code with two zeros and minimum distance 5 that it is not quasi-perfect.

V. Elementary Approach to the Divisibility of the Number of Solutions to Systems of Equations

There are several results on the divisibility of the number of solutions to systems of equations; some examples are the results by Ax-Katz ([2], [8]), Moreno-Moreno ([12]) and Adolphson-Sperber ([1]). These results have been widely used in applications to coding theory (for example see [16],[10]) and cryptography (for example [3],[5] ). However, the methods used to obtain these and other related results required advanced mathematics techniques such as p-adic analysis, the theorem of Stickelberger and Newton Polyhedra.

On [9] we presented an elementary proof of the Moreno-Moreno result for characteristic 2 that uses the covering method introduced in [13]. In the present paper we estimate the divisibility of exponential sums, for arbitrary characteristic, using a generalization of the covering method. This new generalization allows us to give a completely elementary proof of Moreno-Moreno’s result ([12]) for any characteristic and improvements to Ax-Katz and Adolphson-Sperber’s results over the prime field.

We have two different elementary proofs for this result ([6]); the one that we sketch here is algorithmic for the prime field 𝔽_{p}, providing then a completely elementary treatment of the algorithmic solution to the divisibility problem.

To generalize the covering method, let E = {e_{1}, …, e_{N}} be a set of n-tuples, e_{i} = (e_{i1}, …, e_{in}), where each e_{ij} is a non-negative integer. Let U = (ν_{i})_{1≤i≤N} be an N-tuple of non-negative integers. If m is a positive integer, we say that U is an m-covering when the vector sum f = ν_{1}e_{1} +⋯+ν_{N}e_{N} has all its entries nonzero and divisible by m, or equivalently, when there exist positive integers λ_{1}, …, λ_{n} such that

\begin{matrix}ν_{1}e_{11} + ⋯ + ν_{N}e_{N1} = mλ_{1} \\ … \\ ν_{1}e_{1n} + ⋯ + ν_{N}e_{Nn} = mλ_{n}. \end{matrix}  (8)

We define κ_{m}(E), the m-th covering number of E, as the smallest cardinality of any such m-covering, that is the minimal value of ν_{1} + ⋯ + ν_{N} for which the preceding system holds. One clearly has κ_{m}(E) ≤ mn.

Let now ζ be a primitive p-th root of unity over Q and put θ = 1−ζ, so that pA = θ^{p−1}A, where A is the ring of integers of Q(ζ). Also let F ∈ 𝔽_{p}[x_{1}, …, x_{n}] be a polynomial in n variables with coefficients in the finite field 𝔽_{p} with p elements, and such that E is the set of exponent n-tuples of monomials that appear in F with non-zero coefficient, that is

F (x) = ∑_{i=1}^{N} c_{i}x^{e_{i}}  (9)

with c_{i} ∈ 𝔽_{p}^{×}.

Consider S = {0, 1} if p = 2, and, for p ≥ 3 and g a generator of the group of units of ℤ_{p^{n}}, S = {0} ∪ {g^{ip^{n−1}} | 0 ≤ i ≤ p − 2}. This implies that S is a complete residue system modulo p.

We put

S(F) = ∑_{x∈(𝔽_{p})^{n}} ζ^{F (x)} ∈ A.  (10)

By abuse of notation we will also write F for the polynomial with integral coefficients obtained by lifting 𝔽_{p} to S. Since ζ^{m} depends only on m modulo p, the preceding can also be written as

S(F) = ∑_{s∈S^{n}} ζ^{F (s)}.  (11)

Now, if we write

S(F) = ∑_{s∈S^{n}} ∏_{i=1}^{N}(1 − θ)^{c_{i}s^{e_{i}}} ,  (12)

and use the binomial theorem to expand

(1 − θ)^{c_{i}s^{e_{i}}} = ∑_{ν≥0} \binom{c_{i}s^{e_{i}}}{ν}(−θ)^{ν},  (13)

we can obtain

Proposition 5. With these notations, if S(F) is a rational integer, then it is divisible by p^{⌈κ_{p−1}(F)/(p−1)⌉}.

With the above proposition we obtain the following new result, which gives an improvement of the main theorem of Adolphson-Sperber [1] for the finite field 𝔽_{p}. The result of Adolphson-Sperber is an improvement to Ax-Katz’s theorem ([2], [8]).

Theorem 6. With the above notations, κ_{p−1}(F) ≥ ω(F), where ω(F) is as defined in [1].

Also note that κ_{p−1}(E) coincides with μ of (2) when the finite field is 𝔽_{p}, and we then obtain an elementary proof of the algorithmic treatment in Section III.

Combining the generalization of the covering method with a generalization of the reduction to the prime field method ([12]) we can obtain an elementary proof of the following result by Moreno-Moreno for an arbitrary finite field.

Theorem 7. Let F_{i} be a polynomial over 𝔽_{p^{f}} with p-weight degree l_{i}, where i = 1, …, t. Then the number simultaneous solutions of F_{1}, …, F_{t} over 𝔽_{p^{f}} is divisible by p^{μ}, where

μ = ⌈\frac{f(n − ∑_{i=1}^{t} l_{i})}{max_{i} l_{i}}⌉.

Acknowledgments

The authors want to thank Carlos Corrada, UPR-RP, for the calculation of the covering radius of the codes on Section IV that led to Theorem 4. They also appreciate the comments made by the referees and the remark that the all primitive double error-correcting codes with two zeros over 𝔽_{2^{f}} and minimum distance 5 are known for f ≤ 25. The work of Ivelisse Rubio was supported by Program URMAA, NSA Grant H98230-04-C-0486.

References

[1] A. Adolphson and S. Sperber, “p-adic estimates for exponential sums and the theorem of Chevalley-Warning”, Ann. Scient. E. N. Superior 4th. series 20 (1987), 545-556.

[2] J. Ax, “Zeros of polynomials over finite fields”, Amer. J. math. 86 (1964),255-261.

[3] A. Canteaut, P. Charpin, H. Dobbertin, “Binary m-Sequences with Three-Valued Crosscorrelation: A Proof of Welch’s Conjecture”, IEEE Trans. Inform. Theory, 46, pp. 4-8, 2000.

[4] A. Canteaut, P. Charpin, H. Dobbertin, Weight “Divisibility of Cyclic Codes, Highly Nonlinear Functions on F_{2^{m}}, and Crosscorrelation of Maximum Length Sequences”, SIAM J. DISCRETE MATH. Vol. 13, No. 1, pp. 105-138, 2000.

[5] H. Dobbertin, T. Helleseth, P.V. Kumar and H. Martinsen, “Ternary m-Sequences with Three-Valued Cross-Correlation Function: New Decimations of Welch and Niho Type”,IEEE Trans. Inform. Theory, 47, pp. 1473-1481, 2001.

[6] H. Randriam, F. N. Castro, O. Moreno, I. Rubio and H. F. Mattson, Jr., “Generalization of the Covering Method for Arbitrary Characteristic and the Divisibility Properties of Exponential Sums”, draft.

[7] T. Kasami, “Weight Distribution of Bose-Chaudhuri-Hocquenghen Codes”, Combinatorial Math. and its Applications Univ. of North Carolina Press, Chapel Hill, NC 1969.

[8] N.M. Katz, “On a Theorem of Ax”, Amer. J. Math. 93 (1971), 485-499.

[9] O. Moreno, F. N. Castro, and H. F. Mattson, jr., Correction to “Divisibility properties for covering radius of certain cyclic codes”. To appear, IEEE Trans. Inform. Theory

[10] O. Moreno and F. N. Castro, “Divisibility Properties for Covering Radius of Certain Cyclic Codes”, IEEE Trans. Inform. Theory , 49:12(2003), pp. 3299-3303.

[11] O. Moreno and F. N. Castro, “On the Covering Radius of Certain Cyclic Codes”,Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, pp.129-138, Springer.

[12] O. Moreno and C.J. Moreno, “Improvement of the Chevalley-Warning and the Ax-Katz theorems”, Amer. J. Math. 117:1 (1995), pp. 241-244.

[13] O. Moreno and C. J. Moreno, “The MacWilliams-Sloane Conjecture on the Tightness of the Carlitz-Uchiyama Bound and the Weights of Duals of BCH Codes”, IEEE Trans. Inform. Theory 40:6 (1994), pp. 1894-1907.

[14] O. Moreno, K. Shum, F. N. Castro & P.V. Kumar, “Tight Bounds for Chevalley-Warning-Ax Type Estimates, with Improved Applications”, Proc. London Math. Soc. 88, pp. 545-564, 2004.

[15] R. McEliece, “Weight congruences for p-ary cyclic codes”, Discrete Math., 3(1972), pp. 177-192.

[16] H. N. Ward, “Weight Polarization and Divisibility”, Discrete Math., 83, pp. 315-226, 1990.