Counting Zeros of Polynomials Over Finite Fields Citation Erickson, Daniel Edwin (1974) Counting Zeros of Polynomials Over Finite Fields. Dissertation (Ph.D.), California Institute of Technology. doi:10.7907/Q28M-M322. https://resolver.caltech.edu/CaltechETD:etd-10132005-082129 Abstract NOTE: Text or symbols not renderable in plain ASCII are indicated by [...]. Abstract is included in .pdf document. The main results of this dissertation are described in the following theorem: Theorem 5.1 If P is a polynomial of degree r = s(q-1) + t, with 0 < t <= q - 1, in m variables over GF(q), and N(P) is the number of zeros of P, then: 1) N(P) > [...] implies that P is zero. 2) N(P) < [...] implies that N(P) [...] where [...] where (q-t+3) [...] ct [...] t - 1. Furthermore, there exists a polynomial Q in m variables over GF(q) of degree r such that N(Q) = [...]. In the parlance of Coding Theory 5.1 states: Theorem 5.1 The next-to-minimum weight of the rth order Generalized Reed-Muller Code of length [...] is (q-t)[...] + [...] where c, s, and t are defined above. Chapter 4 deals with blocking sets of order n in finite planes. An attempt is made to find the minimum size for such sets. Item Type: Thesis (Dissertation (Ph.D.)) Subject Keywords: (Mathematics and Economics) Degree Grantor: California Institute of Technology Division: Physics, Mathematics and Astronomy Major Option: Mathematics Minor Option: Economics Thesis Availability: Public (worldwide access) Research Advisor(s): Dilworth, Robert P. Thesis Committee: Unknown, Unknown Defense Date: 20 September 1973 Record Number: CaltechETD:etd-10132005-082129 Persistent URL: https://resolver.caltech.edu/CaltechETD:etd-10132005-082129 DOI: 10.7907/Q28M-M322 Default Usage Policy: No commercial reproduction, distribution, display or performance rights in this work are provided. ID Code: 4061 Collection: CaltechTHESIS Deposited By: Imported from ETD-db Deposited On: 14 Oct 2005 Last Modified: 24 Jul 2024 19:46 Thesis Files Preview PDF (Erickson_de_1974.pdf) - Final Version See Usage Policy. 2MB Repository Staff Only: item control page

Copyright @) by DANIEL EDWIN ERICKSON 1973 COUNTING ZEROS OF POLYNOMIALS OVER FINITE FIELDS Thesis by Daniel Edwin Erickson In Partial Fulfillment of the Requirements for the Degree of Doctor of Philosophy California Institute of Technology Pasadena, California 1974 (Submitted September 20, 1973) ii ACKNOWLEDGMENTS I would like to take this opportunity to thank Robert J. McEliece who suggested the topic for this study, directed me to source material in this field and has been a continual source of guidance and review. My thanks also to Professor Robert P. Dilworth who has guided my graduate study and helped review this thesis, and to Professor Marshall Hall who suggested the material on blocking sets. I must thank my wife Vicky who has endured many inconveniences while I was engaged in writing this thesis. Iam also grateful to Joyce Lundstedt who typed this work for me. For financial assistance, I am indebted to the State of California for a partial fellowship, the California Institute of Technology for tuition fellowships and teaching assistantships, and to the Jet Propulsion Laboratory for part-time and summer employment. iii ABSTRACT The main results of this dissertation are described in the following theorem: Theorem 5.1 oa If Pis a polynomial of degree r = s(q-1)+t, with 0 <t <q-1, in m variables over GF(q), and N(P) is the number of zeros of P, then: 1) N(P) >q™- g™-8 4 tqg™-s-1 implies that P is zero. 2) N(P) < q™ - g™@-8 4 tqm-s-1 implies that N(P) < q@ _ g™-8 4 tq™@-s-1 -eqm-8-2 where - q if s = m-1 or if t = 1 and either s = 0 or q 2 4 or if s = m-2 and q = 2. q-1 if t = 1 and either q =3 and0<s=m-2or q<4and0<s<m-2. t-1 if s<m-1 and either 1 <t < (q+5)/2 or 1<t=q-1 if q 2 4, (q+5)/2 <t<q-1l,ands<m-l. c Lt where (q-t+3) < c. < t-1. Furthermore, there exists a polynomial Q in m variables over GF(q) of degree r such that N(Q) = q™@-q™"§ m-s-1 . eq™8-2 In the parlance of Coding Theory 5.1 states: +tq iv Theorem 5. 1* The next-to-minimum weight of the rth order Generalized Reed- Muller Code of length q™ is (q-t)g@™~ 8-1, eg@ 8-2, where c, s, and t are defined above. Chapter 4 deals with blocking sets of order n in finite planes. An attempt is made to find the minimum size for such sets. ACKNOWLEDGMENTS ABSTRACT . CHAPTER 1 CHAPTER 2 CHAPTER 3 CHAPTER 4 CHAPTER 5 REFERENCES TABLE OF CONTENTS Page ii iii 14 39 62 80 87 CHAPTER 1 This dissertation examines polynomials in several variables over finite fields. The general problem of exhibiting canonical forms for such polynomials being extremely difficult, this work concentrates on their sets of zeros. The specific goal of the first three chapters is to explore the restrictions on the number of zeros of polynomials of degree r in m variables over GF(q), the field with q elements. Chapter one outlines the historical development in this area, the basic definitions, and the motivation for this particular specialization of the general problem. Chapters two and three contain the results of the author's research on zero-sets of polynomials. The fourth chapter deals with a related topic: blocking sets in affine planes. A discussion of the expected fruitfulness and difficulties of certain approaches to study in these areas occupies the fifth and final chapter. The following notation will be used in discussing polynomials over finite fields: Let K = GF(q) be the field with q elements. Let K™ be the vector space of dimension m over K consisting of all m-tuples @ = (@,,@,,...,@ a, €K. m)? Let P = P(x,,X,,...,X,,) be a polynomial in m variables over K. The degree or total degree of a term of Pis the sum of the powers of all of the indeterminates in that term. The degree or total degree of P is the degree of the maximum degree nonzero term of P. The degree of the zero polynomial is -~. deg P will denote the degree of P. The x, -degree of a term of P is the power of the indeterminate Xj in the term. | The x,-degree of Pis the x,-degree of the maximum x,-degree nonzero term of P. The x;-degree of the zero polynomial is -%. deg; P will denote the x;-degree of P. The zero set of Por set of zeros of P, Z(P), is the set of m-tuples o,... 2a) such that P(a@,,@,,...,@,) = 0. 1? 29° Z(P) = {a « K™ |P(@) =o}. The nullity of P, N(P), is the number of zeros of P. N(P) = ||Z(P) |]. The first results establishing restrictions on N(P) were published by C. Chevalley [4] and E. Warning [13] in 1936. E. Artin had conjectured that if P is homogeneous of degree r with r < m, then P has a zero besides 0 = (0,0,...,0). Chevalley showed that not only was Artin's conjecture true, but that it was still true if P was not homogeneous but had a zero constant term. Warning, using a lemma of Chevalley's, proved the theorem: Theorem 1.1: Chevalley-Warning If deg P < m then the characteristic of K divides N(P). Warning also showed that if N(P) > 0 and deg P< m, then It was not until 1964 that these results were improved upon by James Ax[1]. He proved the following theorem: Theorem 1.2: Ax Divisibility Condition Let P be a polynomial in m variables over GF(q) with deg P=r. Let b =[(m-1)/r], the greatest integer less than or equal to (m-1)/r. Then q? divides N(P). He also exhibited a polynomial P of degree r in m variables over GF(q) such that q? divides N(P), but pq? does not divide N(P) where p is the characteristic of K = GF(q). In this sense, Theorem 1.2 is the best possible p-adic divisibility theorem. More recently, results in this area have arisen from the study of Generalized Reed-Muller Codes in algebraic coding theory. It is not neces- sary, however to be familiar with coding theory to understand these results. The following discussion should suffice to illuminate these results. Each polynomial P(x) = P(x,,X,,...,X,) in m variables over K gen- erates a function @ + P(@) from K™ into K. But some different polynomials generate the same functions. For instance, xd - X, Maps every element of K™ into zero. Since every element of K satisfies a% = a, any polynomial can be reduced modulo (xd ~ X,); (xf - X,),..., and (xt - Xn) to a new polynomial P’(x) such that P and P’ agree on every point of K™ and deg; P <q-lfori-=1,...,m. This observation leads to the definition: A polynomial P(x,,... ,Xm) in m variables over K = GF(q) is called a reduced polynomial if deg; P <q-1 for i =1,2,...,m. There are qa reduced polynomials in m variables over GF(q). There are the same number of mappings from K™ into K. That these are in one-to-one correspondence may be shown either by proving that no two reduced polynomials act identically on K™ or by proving that for each function f:K™ — K there is a reduced polynomial P(x,,X,,...,Xyp) such that P(0,,0,,..., 0m) =f((0,, 02,..., Om)) for each O = (0,,0,,..., 0m) € K™. The latter method provides some additional insights. For each 6 =(0,,0,,..., 0m) € K™ define m = -1 F(x) = M (1 - (x,-0,)9) Fs is a reduced polynomial. Considered as a function, 1 if T=06 Q otherwise This can be seen from the fact that when A € K 0 if A=0 ,a-1 ‘ 1 if Az#0 Using the Fz as a basis, a reduced polynomial which represents any given function f :K™ — K can be generated as follows: Let P(x) = >) {(o)F=(x). Then P represents f. oeKm From this discussion the following theorem is obvious: Theorem 1.3 The natural mapping P ~ (o ~ P(c)) is a vector space isomorphism from the space of reduced polynomials in m variables over GF(q) to the space of mappings from K™ into K. For the remainder of this work, all polynomials referred to will be reduced polynomials unless a statement is made to the contrary. @ (m,q) will denote the set of reduced polynomials in m variables over GF(q). The subset of @(m,q) consisting of those polynomials with degree less than or equal to r will be denoted .(m,q). Since deg (P+Q) < max(deg P, deg Q) and deg(a@P) < deg P for @ € K, ? .(m,q) is a subspace of @ (m,q). If the elements of K™ are ordered @,,@,,...,@ m, the value table of a polynomial P « © (m,q) (with respect to this ordering) is the q™- tuple (P(@,), P(@,),..., PCO on) ). The set of value tables for all polynomials of (m,q) forms a vector space of dimension q™ over GF(q) which is isomorphic to @ (m, q). Definition The set of value tables of polynomials in P.(m, q) is called the r-th order Generalized Reed-Muller Code of length q™, denoted GRM,(m, q). Clearly GRM,,(m, q) is a subspace of GRM,,,( q-1)(™; q) which is the space of all value tables. The dimension of GRM,(m, q)asa vector space over GF(q) can be computed by calculating the dimension of the isomor- phic space & .(m,q). As a basis for .(m, q) we can pick those poly- nomials of the form: . m i, le 1 . . x, x,...x,/7 where 0< ij <q-1 and ») ij<r. =1 If p(k,m,q) represents the number of distinct m-tuples (a,,a),...,a,,) m such that 0 < a, <q and )) a; =k, then . j=l r dim @,(m,q) = )) p(i+m,m,q) i=0 The GRM codes are examples of linear block codes. A linear block code is a subspace of the space of n-tuples of elements of a finite field. The length of the code is n and the dimension of the code is the dimension of the subspace. A linear block code of dimension k and length n is called an (n, k) linear code. Under this definition: r GRM,(m,q) isa (q”, > p(itm,m,q)) linear code i=-0 The elements of a linear code are called code vectors. The Hamming distance between any two vectors (@,,@,,...,@,) and (8,,82,..+,8,) is defined as the number of positions in which they differ: The Hamming weight of a vector (@,,...,@n) is defined as the number of positions in which it is nonzero: \(,---54)| = [ie {t,... nf fe, eof |] The minimum distance of a linear block code C is the smallest distance between two distinct code vectors: minimum distance = min (x,y) x,yeC X#Y The minimum weight of a code C is the smallest nonzero weight of a code vector: minimum weight = min |x| xeEC x#0 For a linear block code, the minimum weight and the minimum m distance are equal. The natural isomorphism from C (m,q) onto K@ maps (P rim; q) onto GRM,.(m, q) and preserves weight if we define the weight of a polynomial P: |P| = ||S(P) || where S(P) is the set of support points of P: S(P) = {@eK™|P(a) +0} . Thus, the notion of a minimum weight (nonzero) polynomial of (Yr rim, q) is interchangable with that of a minimum weight code vector of GRM,,(m,q). The weight of a polynomial is the dual of its nullity since S(P) = K™ - Z(P) and [P| =q'™ - N(P). Many results of coding theory deal with constraints on the weights of code vectors of linear block codes. Some deal specifically with GRM codes. Through this duality, these results are directly applicable to the topic of this paper, restrictions on N(P). The two concepts of coding theory which encompass such considera- tions of restrictions on weights are weight enumerators and weight spectra of linear codes. If A; is the number of code vectors in a given (n,k) linear code which have weight i, then the generating function: n A(z) = Az i=0 is called the weight enumerator of the code. The weight spectrum of the code is just the set of i for which A, >0, (i.e., the set of weights which actually occur). The gaps in the spectrum are those i for which A, = 0. The weight enumerator contains the complete information on the distri- bution of the weights of the code vectors in a form which is convenient for probability calculations. The weight spectrum records all of the restric- tions on the weights of the code vectors (and hence on the number of zeros of polynomials in GRM codes). The minimum weight of the r-th order Generalized Reed-Muller Code of length q™ (GRM,.(m, q) ) was shown in 1968 by Kasami, Lin, and Peterson | 6] to be (q-t)q™~8-1 where r = s(q-1) + t withO <t <q-1. They also gave canonical forms for polynomials of this weight when q = 2. In 1970, Delsarte, Goethals, and MacWilliams [5] extended these results, giving canonical forms for minimum weight polynomials in the general q-ary case. (Proofs of the canonical forms and the minimum weight will be given in chapter two.) Once the canonical forms were found, A; was calculated for i = minimum weight. The canonical forms are represen- tatives of the equivalence classes under the equivalence described in the next paragraph. A substitution of variables is made in a polynomial P by replacing each x; by a linear polynomial, a,jX, + agjX, +... + AmiXm + W;- This substitution defines a new polynomial R(x) = P(xA+) such that for any a@eK™, R(@) = P(@A+). If Ais non-singular, then P(x) = R(xA™ + (-@A™")). In this case, deg R = deg P and N(R) = N(P). Sucha change of variables T(x) = xA+w is called an invertible affine transformation of variables. It is composed of an invertible homogeneous transformation x ~ xA and a translation x ~x+@. The notation [ T(x)] , will denote 4X, +... +4,,;X,, + W;. The homogeneous transformations all fix the origin and so are distinct from the nonzero translations. There are (q™-1)(q™-q) ...(q@-q™~*) invertible homogeneous transformations and q™ translations giving q™(q™-1)(q™-~q)... (q@-g™=") invertible affine transformation of variables. If R(x) = P(xA+) for some invertible A, then P and R are called equivalent. This is clearly an equivalence relation. Restating what was said above: Theorem 1.4 If P and R are equivalent polynomials, then deg P = deg R, N(P) = N(R), and |P| = [R]. In the special case, r = 2, Robert McEliece [9] has given canonical forms for the polynomials of 4 o(m,q) and calculated the A, for the second- order Generalized Reed-Muller Codes. The full result is quite complex and is presented in a series of tables, but the restrictions on the weight spectrum are simple enough to be given here: 10 Theorem 1.5: McEliece If P is a polynomial of degree < 2 over GF(q) in m variables, then the number of solutions to P(x) =a is of the form qu-t + yg i-1 where v =0, +1 or + (q-1) and0 <j <[m/2]. Another specialized case where significant results have been obtained is q = 2. The code GRM,,(m, 2) is called the r-th order Reed- Muller Code of length 2™ denoted RM(r,2™). In 1970, Tadao Kasami and Nobuki Tokura [7] characterized the polynomials of less than twice the minimum weight in P.(m, 2). This left coding theorists one equation short of a solution to a system of equations which would yield the weight enumerator for the code RM(3,2°). In April of 1971 three mathe- maticians independently found this weight enumerator; namely, T. Kasami, R. Sarivate, and J. H. van Tilborg. To fully understand the nature of this problem and the motivation for this paper, one must understand dual codes and the MacWilliams identity. Define a scalar product c- d of two n-tuples of elements of K. © = (C,,Ca,.-+,Cpy); d = (dy, dy,.--, dp) Given an (n, k) code (a subspace of dimension k), the dual of a is the set of vectors @={b |yae @, a-b = 0}. ® is also a linear code, QA is the dual of 8 and CG has dimension n-k. 11 Theorem 1.6 The dual of GRM,(m, q) is GRM (g-1)m-1-r™®- Proof: If Pe .(m, q) andQe & (m,q), then their product as (q-1)m-1-r polynomials PQ is in C (qet)m-10)- If a is the value table of P and b is the value table of Q, then a-b is the value table of PQ, so a-b= PQ(c). That 2 ‘a PQ(c) = 0, follows from Lemma 1.7 oekm below. If Qe ? (m,q) with deg KQ > (q-1)m-r, let one of the highest i degree terms of Q be ax,! x, vee Xn where 0 < i, < q-1 for j =1,...,m, , ij > (q-1)m-r, anda #0. Let P(x) = xd hi-tg-in-t ee xd-tmo? Then deg P = (q-1)m - deg Q <r and deg PQ = (q-1)m. By Lemmal.7, a-b= ) PQs) #0 oeK™ This completes the proof given Lemma 1.7. Lemma 1.7 Let P be a polynomial in ®(m,q), then deg P = m(q-1) if and only if >), Ps) #0. oe K™ 12 Proof of Lemma 1.7 m For each o € K™, let Fo= (1 - (x, - g.)t-}), then i=l t 1 if T=0 Fz (7) = Q otherwise also Fe(x) = (-1)™x9-4 9-4 wee xt + terms of lower degree, so any Pe @(m, q) may be written: P&) = > PO)Fs&)=(-1)™ YY Po) xo-t det xo oek™ oek™ + lower degree terms, so deg P< m(q-1) if and only if »: P(o) =0. Tek™ This completes the proof of Lemma 1.7 and Theorem 1.6. The MacWilliams identity relates the weight enumerator of a linear code to the weight enumerator of its dual. Theorem 1.8: MacWilliams Identity If A(z) is the weight enumerator of an (n,k) linear code,and B(z) is the weight enumerator of its dual, then B(z) = q “(1 - (q-1)z)" a(rtaa) Most recent texts on coding theory contain proofs of this theorem. See Coding Theory by van Lint, pp. 120-121 [11] or Algebraic Coding Theory by Berlekamp, pp. 400-403 [2] for examples of proofs. 13 Intuitively, the MacWilliams identity is a tool which can be used to solve for the two weight enumerators completely if enough of the A; and B; are known. It has been found to be quite useful in this regard. When r <m, the Ax divisibility condition proves that many of the A, are zero where (1 = GRM,,(m,q). The minimum weight results show that A, = 0 for 0<i< (q-t)q™@~ 8-1, Warning's result on the mini- mum number of zeros when r <m shows, in addition, that A; = 0 for qu-qut <i<q™. Because in Reed-Muller Codes, q = 2, a polynomial of weight |P may be mapped into P+1 with weight |P+1|=2™-|P|. In RM(3,2°) all of the gaps are either less than twice the minimum weight or more than 2°-twice the minimum weight (in which cases they are predicted by the Kasami, Tokura paper), or they are predicted by the Ax divisibility con- dition. In 1971, van Tilborg [12] revealed four gaps of RM(3,2°) which were not predicted by either paper: 132, 140 and their reflections 372 and 380. These gaps did fall under the scope of Kasami, Tokura and Azumi's 1973 publication [8] characterizing the code words with weight less than two- and-a-half times the minimum weight in a Reed-Muller Code. This paper concentrates on low-weight gaps in non-binary GRM codes. One specific question which this dissertation seeks to answer is: What is the next-to-minimum weight in a Generalized Reed-Muller Code? Theorem 2.1 gives a lower bound on the next-to-minimum weight. Theorem 3.1 improves this bound in some cases, shows that it cannot be improved for others, and for the rest of the cases, reduces the question of whether it can be improved upon to the case m = 2. 14 CHAPTER 2 The goal of this chapter is twofold; first, to prove Theorem 2.1, and secondly, to develop lemmas which will shed light on the structure of low-weight polynomials. Theorem 2.1 Let r = s(q-1) +t where 0 < t < q-1, and let g-l if t=1 c= q-2 if t=q-l#l min (q-t, t-1) otherwise If P is a polynomial of degree r in m variables over GF(q) such that |P | > (q-t)q@~8-}, then |p| > (q-t)q™~8~1 + eqm-8-2. The approach of this chapter is motivated by the work of Delsarte, Goethals, and MacWilliams [5]. In some cases, the lemmas are similar and will be cross-referenced to the D.G. and M. paper. The first lemma deals with linear factors, which will play an important role in this exposition. Lemma 2.2 (D.G. and M. Lemma Al1.1) If P(x,, ...,X,,) is a nonzero polynomial such that P(q@) = 0 when- ever a, = a, then P(x) = (x,-a) P(x) where deg Pp = deg P-1 and deg, P = deg, P-1. 15 Proof: P(a, @,..., @py) = O for all a,,...,Q@y,. Represent P — -1 -2 P(x) = goxt +g xt et By-2%1 + &y-1 where g, = g:(x,,.. -»>Xm), then P(X) = P(E) - P(a,X»..-,Xm) = go(xtt -at-}) +... 4 8y-2(%1 - a) = (x,-a) [eg(xo72 +... + ai~2) +e. + 84-2] Lemma 2.3 (D.G. and M. Corollary Al. 2) If P(X) = 0 unless a, = b, then P(X) = (1 - (x,-b)97))P(x,, ..., Xp) where deg Pp = deg P - (q-1). Proof: | 6 if x,=b 7 1 (x,-a) = = (1 ~ (x,-b)47) a € GF(q) 0 otherwise . a#b where p= Tl y#O. y#0 Lemma 2.4 If y(k) = BX, +... +BmXm +7 and y(a) = O=> P(a@) = 0, then y divides P. Proof: Let x + xA +@ be an invertible affine transformation such that w, =n and aj, = fj fori=1,...,m. Let R(x) = P(xA~ -@A™) so that P() =R(KA+5). And let @ = (0,@,,..., @,,) So that R(@) = P@A™ -@A™). 16 Let y =@A~ -@A Then @ = yA + So m m O=a,=6,+) ayant) By; so by the hypothesis, P(y)=0. Thus R(@)=0. Applying 2.2, R(x) = x RE ). But invertible affine transformations preserve polynomial products, so P(x) = R(KA+0)=y- R(XA+0). Separation of a variable is an extremely useful technique which will be used heavily in chapters two and three. It is refined from a similar technique used by D.G. and M. and expounded upon in their Lemmas Al.6 and Al.7. The concept behind this technique is the iso- lation of the effect of the variable x,. One may write: P(x) = P(X), X,.--,Xm) = P(x,x’) where x’ = (x,,..., Xp) For each P € O(m,q), m> 1 and eachae K = GF(q) define P(x’) = P(a, x’) € @(m-1,q). Then (201) IPlm = 2 IPylm-1 AEK where the subscripts on the weight serve only as reminders of the number of variables on which the polynomial depends. Given any ordering of the elements of K, ,,A,,..., Aq, define polynomials pi). pit) wees p(q-1) by: 17 P if i=0 202) pli) . . (202) fp{i-2) - PY?) 1a, =i) for i=1,2,...,q-1. That p{i) is a polynomial follows from Lemma 2.2. It is also evident from 2.2 that (203) deg p(k) < deg P - k; deg, p{k) = deg, P-k with the convention that deg, pk) < 0 means p(k) = 0. This, and the fact that P is a reduced polynomial imply that deg, P72) < 0 so that p(4-) - pe), From (202), By induction -1 . . j (204) pi) . pW it (x, -2,) L Aj ksivd "OK _ pli) (i+1) = Phd + (x, - Aj, Pry + (X -A3,4) (q-1) When i = 0 this becomes Siw 205 P = pj Il (x,-2 (205) 2 jad ed (x, -A,) j=0 j -1 = Py, + (x, -»,)P\) +... +(K,-A,)... (K, Agei)Pt ) 18 From the definition of Py: i-1 | (208) Pp, = y JPY tt aj-a) P, + (45 -a JPY? tere +QGQAd)--- (j--wPLY Lemma 2.5 If P « @(m,q) and Ay, +++,Ag is an ordering of the elements of K such that Px =...5 Pan = 0, then deg Py < deg P -n fori>n. Proof: By induction from (206), p\) =...5 pint) = 0so 1 n i-l j deg P,_ = deg », P) T] (A,-Ak) < deg P-n from (203). As an illustration of the use of this technique and also for the sake of completeness since this theorem will be used in future proofs, a proof is now given for Theorem 2.6. Theorem 2.6: Bound on Minimum Weight Let r= s(q-1) +t, 0<t <q-l and let a = (q-t)q™-8"1_ if P € (,,(m, q) such that P # 0, then [P| > a. Many authors have given proofs of this result including Kasami, Lin, and Peterson (6 ]. 19 Proof: The theorem is trivially true for m= 1. Proceed by induction. Assume 2.6 is true for m-1. By (201) [P| = 2s Py lm-1- if a. Py # 0 for all A € K, then by the induction hypothesis |P | m7? qd, Otherwise, order the elements of K so that P, =.+..=P, = 0, but 1 n Pa #Q0fori>n. Since P#0, 1 <n<q-1. By Lemma 2.5, deg P, <r-n for i>nso i q , (q-t+n)g™@~8~2 if n<t m- Pla = 2% [Palma 2 a-mddvy = (@-n) nce i=n+l (1-t+n)q if n2t (q-t)qg@-8-1 + n(t-n)q™@~8~2 if n<t (q-t)g™-S-1 + (n-t)(q-1-n)q™~87} if n2t > (q-t)q@™-S~1 since 0<n<q-l , completing the proof. The parameter n plays a significant role in the above inequalities. It will be called the linear divisibility of P by x, and will be formalized by the following definitions. A variable in @(m, q) is a polynomial y ¢ (?(m, q) such that deg y = 1. The linear divisibility of a polynomial P ¢ Y (m, q) by a variable y in @(m, q) is the number of distinct » € K such that y - A divides P. This value is denoted £d(P, y). Since polynomial products are preserved by invertible affine transformations, and we can always find an invertible 20 affine transformation which takes y into x,, there is a polynomial BY such that Py is equivalent to P and La(P,,, X,)=2£d(P, y). With the same proof as 2.6 then: Lemma 2.7 If Pe © .(m, q) P # 0 and there is a variable y in (?(m, q) such that £d(P, y) =n, then n(t-n)g™~8~2 if n<t m [P| > a> + (n-t)(q-1-n)g™~S"! it net -1 with equality if and only if |Q, | > 0 => la, | = den for any Q(x) = P(T(x)) where T is an invertible affine transformation such that T(x,) = y. Proof: |P | = IP, | because equivalence preserves weight. Apply (201) and Lemma 2.5 as in the proof of 2.6. This lemma provides the first step to a proof of Theorem 2.1 since it implies that gm-s-1 if t=1 |P | > day y r m-s-2 (t-1)q if t>1 unless £d(P, y) = 0, t, or q-1 for all variables y. If, for some y> £d(P, y) = q-1, then by Corollary 2. 3, P(x, »+0)Xp) = (1- (x,-b)474) : P(x,,.. -»Xp,) where Pe @ (q-1)m-1, q), and by (201), |p | wa = [P| met so induction may be applied. If, for some y, £d(P,y) = t, then |p| = |R| where R = Py so that where deg Ry, < s(q-1). Later lemmas will examine this case more thoroughly. If £d(P, y) = 0 for all y, then P has no linear factors. This case will be examined in greater detail in chapter three, but here a general lemma is given. The proof requires some knowledge of the relationships of affine subspaces of K™, An n-dimensional affine subspace of K™ is a set of vectors derived from a homogeneous n-dimensional subspace by the addition of a constant vector to each element. The zero set of a linear polynomial (variable) is an (m-1) dimensional affine subspace. Conversely,. every (m-1) dimensional affine subspace is the zero-set of some variable. Thus, if a polynomial P(x) is zero on every point of an (m-1) dimensional affine subspace, then there is a variable y such that y(a) = 0 P(q@) = 0.and, by Lemma 2.4, y divides P so that P has a linear factor. If G is an n-dimensional affine subspace of K™, a k-dimensional affine subspace of K™ which is contained in G will be called a k- dimensional affine subspace of G or, for brevity, a k-subspace of G. Given an (n-1)-subspace H, of G, there exist q-1 additional (n-1)- subspaces H.,..., Hg of G such that H; Hj = @ if i # j and H,=-G. qd =1 : 1 22 The subspaces H,,H,,...,H, will be called q parallel (n-1)-subspaces q of G. Given an (n-2)-subspace E of G, there exist q+1 (n-1)-subspaces Ho, .--,Hg of G such that Hj» H, = E if i+ j and q . |Ju,=G. i=0 In this case, the Hy will be called the q+1 (n-1)-subspaces of G containing E. D.G. and M. proved the following lemma in characterizing the mini- mum weight polynomials. D.G. and M. Lemma Al1.3 If S is a subset of K™ with the following properties: 1) |s| < aq?, 0<a<q-l, b <m-l, a,b integers 2) For any (n-1)-subspace G of K™ such that SaG # ¢, IS nG| > aq?-?, then there is an (m-1)-subspace of K™ which does not meet S. - For the purposes of this paper, a stronger lemma is needed, namely: Lemma 2.8 Given ann dimensional affine subspace B of K™, if S is a subset of B with the properties: 1) |s | < aq? +a b-1 a,b integers 0<a<q-l1, b<n-l 2) For any k dimensional affine subspace G contained in B, either |[SaG| = Oor |SnG| > agh “B+ 23 then there exists an (n-1)-subspace of B which does not meet S. Proof: If n = 1, then condition 1) implies |S| < q-1, so there exists a 0-subset (a point) of B which does not meet S. Proceeding by induction, assume 2. 8 is true for alln<N. Let B be an N-dimensional affine sub- space of K™ , Sa subset of B satisfying 1) and 2). Examine q parallel (N-1) subspaces of B. One of these, call it H, has fewer than age! + aq?” elements of S. By an application of the induction hypothesis to SAH as a subset of H satisfying 1) and 2) with n = N-1, there exists an (N-2)-subspace L of H which does not meet S. Let Hy,H,,... »Hy be the q+1 (N-1)-subspaces of B containing L. Then q q Is} = >} |H,o S]-q|lLns| = ) [A as| . i=0 i=0 Thus there is an i such that lH, Nn S| < (aq? + aq?” 1) /(q+1) =a b-1 ’ but by condition 2) with k = N-1, [H, AS|=0, so H, is the (N-1)-subspace we seek. This completes the proof of 2.8. Corollary 2.8.1 If Pe @ (m, q) and P has no linear factors, then |p| > (q-t)a™-s-1 + (q-t)q™~8-? =(1+ 1/q)d," where r = s(q-1) +t 0<t<q-l. 24 Proof: ‘Let S = S(P), the support points of P, and let a = (q-t), b = m-s-1. Then condition 2) is satisfied by Theorem 2.6. If |P | < (q-t)qg™-8-1 + (q-t)q™-S-2 then condition 1) is also satisfied and, by Lemma 2.8, P has a linear factor. The next corollary is the first step toward characterizing low- weight, low-degree polynomials. Corollary 2.8.2 If Pe @,(m,q) with r < q-1 and |P| < (1+ 1/q)d-", then P is the product of r linear factors. Certainly true for r =1. Assume this corollary is true for r < R-1 and proceed by induction on r. If Pe @ 2(m, a) and [IP] <(14 1/q)dp > then by 2.8.1, Phas a linear factor, so “~ P=2P where deg P <R-1 But |P| <|P| + q™-+ < (q-R+1)q™"? + (q-R)q™? < (1+ 1/q)dp_4 SO by induction, P breaks into linear factors, completing the proof. Corollary 2.8.1 establishes a lower bound for the weight of a polynomial without linear factors. We now turn our attention to low weight polynomials with linear factors. Delsarte, Goethals, and MacWilliams [5] state the following theorem as 2.6.3 and prove it in their appendix: 29 Theorem 2.9 (D.G. and M, 2.6.3) If Pe & .(m, a) where r = s(q-1) + t, O << t <q-1 and |P | = dn = (q-t)q™~ 8-1 then P is equivalent to a polynomial Q where _ s -1 (207) Q(x) =A (1- x; ) i=l j jr rFd t a (A, - si) %#0 A, #A A proof of this result will be given later in this chapter after several preparatory lemmas. It may be observed here, however, that for any r there exists sucha Q, deg Q =r, lQ | = dn so that the bound given in Lemma 2.6 is, in fact, the minimum weight. This well-known result is stated as: Theorem 2.10 Minimum Weight m-s-1 where The minimum weight of GRM _.(m,q) is de = (a-t)q =s(q-1) +t, O<t <q-l. Two other types of polynomials have low-weight and are closely related to (207). These are: = S q-1 t te on gs (208) Q(x) =AX, 15 3 (1-x*") ja Q; - X54) A#eOA eA, if iej t jal Li(xoi4 , X42) (209) Q(x) =A a (1-284) 1= where Lj(X.,1>%g,2) = WX.4+BiXe 10 and a8, # a8, if i¥¢ j Both describe polynomials Q such that deg Q =r = s(q-1) +t 0<t <q-l and if t #1, then [Q| = (q-t)q™" 8-1 4 (t-1)g™~8"2. In many 26 cases, these are precisely the next-to-minimum weight polynomials, as will be shown. The next two lemmas form a starting point for an induction proof of Theorem 2.9 and of Theorem 2.1. They deal with the case r < q-1 where £d(P,y) >r implies P =0. Lemma 2.11 (D.G. andM., Al. 5) 1 If P ¢ @(m,q) with r <q-1, and |P| =di = (q-t)q”*,then P is equivalent to a polynomial Q such that r Qe) = 2M Oye) AA i if i#j (i.e., form (207)) Proof: Corollary 2.8.1 states that P has a linear factor y(x). Let T be an invertible affine transformation such that x, = T(y) and let Q(x) = P(T(x)). Then £d(Q,x,) >0,and Q #0 so &(Q,x,) <r. Since |Q| = 4)", by Lemma 2.7, fd(Q, x) =r so Q = Q i (A;-x,), but a a j=l deg Q = 0, so Q= X, and the proof is completed. Lemma 2.12 If Pe @(m,q); r <q-1 and Phas a linear factor, then |P| > qn = (q-r)q@~! implies |P | = dn + (r-1)q™~2, Proof: Without loss of generality, assume x, divides P. Then 0 < Sd(P,x,) <r. If M(P,x,) =1, then |P| =d," contradicting |P| >d,". Otherwise, by Lemma 2.7, |P | > de + n(r-n)q™~2 > i + (r-1)q@"2, where n = 2d(P,x,). 27 Corollary 2.12.1 If 4 < 2r <q, a next-to-minimum weight polynomial of degree r in m variables over GF(q) has weight (q-r)q@"! + (r-1)q™~?, Proof: From Corollary 2.8.1, if P has no linear factors, then m-1 + m-2 |p| = (q-r)q™~4 + (q-r)q™~? > (q-r)q rq . From Lemma 2.12, if |P| >)" and P has a linear factor, then |P| > (q-r)q™"} + (r-1)q™?. With 1 <r<q, formulas (208) and (209) give polynomials with exactly this weight, so this is indeed the next-to-minimum weight. It is, in fact, true that (208) and (209) characterize all of the polynomials of this weight with r in the given range, as will be proved in chapter three. Corollary 2.12.1 is significant,in that given any r > 2 and any m, it establishes the next-to-minimum weight for all but a finite number of q. The next lemma begins the study of another special class of r's: r = s(q-1). Delsarte, Goethals and MacWilliams did not proceed by quite this route and so had no similar lemma. Lemma 2.13 If Pis a minimum-weight polynomial of @ .(m, q) where r = s(q-1), then P is equivalent to: Ss A Il ia 1) (that is, (207)) i= 28 Proof: i =q™"S, Let Pe .(m, q) such that |P| = dn. By Corollary 2.8.1, Phas a linear factor. Without loss of generality, assume x, divides P. Lemma 2.7 tells us that £d(P,x,) =q-1 and thus P-(1i - x; -1) P(x’) where P is minimum weight of degree (s-1)(q-1). With this argument as an induction step and Lemma 2.11 as a starting point, the proof is complete. The next lemma deals with sums of minimum weight polynomials and polynomials of lesser degree. Lemma 2.14 Let Q be a minimum weight polynomial in P.(m, q) where r= s(q-1), 0<s<m. Let R bea nonzero polynomial in © jm, a) where 0<k <q-1. If P=Q+R, then either |P| = kq™~® or |P] = (k+1)q™"8. Proof: When m =1, thens=1. Inthiscase |Q|=1, |R| >k+1, and the conclusion |P| =k or |P| > k+1 is obvious. Proceed by induction _ on m assuming 2.14 is true for m-1. By Lemma 2.13, it can be assumed that Q = (1 - x; hog *) where Q, is a minimum weight poly- nomial of degres (s-1)(q-1) in m-1 variables. Separating x, in P 1) IPla = 2 |Pylmet = RotQoln-a+ 2» /Ra leet (201) AEK r1+£0 29 Order the elements of K, d,,... Aq so that: Antl = 0, Ry, | =0 fori<n, [R,_|>0Ofori>n+l. Since R #0, n <deg R <r-k, 50 if i s =1, (n+k) <q-1. Ifn=q-1, thens >1 and |P | = [Ro+ Qoln-1° In this case, the induction hypothesis proves the conclusion. Otherwise, write: — n — “« — (2) R(x,,x’) =A i (x,-A;)[ Ro(x’) + x,R(x,,x’)] 1=— where deg Rg <r-(kin) and deg R<r- (k+n) - 1 If Py # 0, then deg P, = deg(Qg+ Ro) “maxir (q-1), r- (k+n) ) and +amt deg P, <r- (k+n) for i > n+1 so | P| 2 (q-n-1 yam r- Gen) * where b = min( (q-1), (k+n)). (ktn) > (q-1) implies [P| > (q-n-1)(n+k+2-q)qm@75 + g™"5 = [1+k+ (q-2-n)(n+k - (q-1))jq™~§ > (k+1)q™~§ (k+n) < (q-1) implies [P| > (q-n)(1+k+n)q™ s-1 = (1+k)q™~5 4 n(q-1-(k+n) yqm~s-1 > (k+1)q™~ If Pg = 0, then Ry = -Q, so deg R, = deg Q, = r-(q-1). This implies r- (k+n) = r-(q-1), so (k+n) < (q-1). (k+n) < (q-1) implies deg P, =deg Ry. i i < max(deg Rg, deg R) = r-(kin)-1 Yo) |p| = > (q-n-1)d27 (icen)- i= = (q-n-1)(k+n+2)q™~8"! = (k+1)q™?" S. (1+n)(q-2-(n+k) )qm-s-1 > (k+1)q™7§ 30 The only case left is (ktn) = (q-1). Here , (ene -1) 0 (cen) = kq™®, but the equality holds if and only if [R, | = aa ge1) for i>n+l. Suppose for some i > n+1, Ry, | > an (q-1)? then from (2) Ry (x’) =d'[ R(x’) +A; Ry Ace) where VR, is a minimum weight poly- nomial in (? y(m-1, is and )/A. Ry * 0, deg X’A; iR,. <r-(q-1)-1. r-(q-1 Applying the induction hypothesis, im, . | m-1 > q™ 5 implies A; 'm- IR). Imei 2 2@"”*. But this forces |P| > (k+1)q™~®, completing the i proof. Notice that in the preceding proof, the only cases in which |P| = kq™"§® could occur were n = q-1 and (n+k) = (q-1) with P, = 0 and [Ro| = minimum weight for i >n+1. This observation provides the basis for the next lemma. Lemma 2.15 Let P be a polynomial of P .(m, q) where r = s(q-1), O< s<m. | = m-1 then there is an If for some A,,A, € K A, # Az, |P, | = |P, 1 invertible affine transformation T fixing x, such that if R(x) = P(T(x)), then Ry = oR) for some o € K,. 1 2 By T fixing x, we mean [ T(x)], = Proof: If m =2, thens =1; d™-! <1 g0 IP, |= |P, |=1. Thus, P > ’ r A, Ay ‘ ’ has one support point such that x, = A, and one support point such that X, =A,. Call these (A,, 0,) and (A,,0,). Let 31 0,-0 1 — 1 27Ay A = 1 0 AgrA, and let T(x) =xA. (o,- O1)A\+X, er) ll Xr. P( (A,, X_) A) = PQ,, * NorAy (O5-0,)A,+X, » AgrA, similarly (Oy- Oy)A,+X, Ag-Ay thus, Ry, | = IR, | =1, soif S(R, ) = S(R,) then our conclusion Ry (or2 - 0,A,) = Py (o,) #0, so 2.15 is true for m =2. = oR), is confirmed. But Ry (Or2- O,r,) = Py (01) # O and Now proceed by induction, assuming 2.15 is true for m-1. Without loss of generality, assume P = Lae T (1 - x8) i and write P(x, ,x’) = Py (x’) + (x,-A,) P(x, X’) deg P <r-l , 1 then Py, = Py, + (AgrA,) P) (x’) deg Py, <r-1 This is precisely the situation in Lemma 2.14 with k =1. 32 [Py | = kat Separating x,, order the elements of K 0,,0,,..., oq so that ¢., = 0, (Po, lm-2 70 for i < nand (Py oj lm-2 > 0 for i >n+1. As observed from the proof of 2.14, n = q-1 or (n=q-2, (P, ), = 0 and (P, ) oq i8 minimum weight). Define Py o(X1»X”) = P(x,,0,x") for o € K, and Py go”) = (Py or = (Py) 5 = P(A, O,x"). =qel _ |p . . . If n =q-1, then IP, 0! | re, 0 |, So applying the induction hypothesis to P, g» there is an invertible affine transformation T”(x,, x“) 3 fixing x, such that if R’(x,,x”) = P o(T"(x1,x")), then R4, = oR’, . ¥» 1 2 Let T(x,,%,,X”) = (x,,X,| T’(x,,x”)],,...- »LT"’(x,,%”) J) and let R(x) = P(T(x)). Then Ry) = Py Gol T" EM 5-1 TEM 0 “if x, #0 HI R4, if x, =0 = eR), Ifn =q-2, then P, = (1 - (x,-9 I) BR” where Pis a minimum 2 weight polynomial in P.. (q- 1)(m-2,q) and@eK a0. Define the transformation T @ 2S follows. [Ty )], = x, for i2, [T,(x)],= %+ a ; Then let S(x) = P(T,(x)) S, =P (=P and Sy = (1 - xP HBR”) 33 Using the results of the previous case, n = q-1, there is an invertible affine transformation T’ such that if R(x) = S(T’(x)), then R, = OR, and T’ fixes x,. R(x) = P(T T(x) ) and TT’ fixes x,. 1 2 Corollary 2.15.1 Let P be a polynomial of © .(m, q) where r = s(q-1), O< s<m. m-1 rr? then there is an If for some A,,A, € K, A, #Aq, |P, | = |P, | =d 1 2 invertible affine transformation T fixing x, such that if R(x) = P(T(x)), then R), = R) . 2 Proof: This strengthening of 2.15 is proved by observing that oR, =R, 2 1 and R, = Ry, + (A,-A,) R(x’) where deg R <r-l Az QyA)R = Ry - Ry = (-o)Ry but if o # 1, this implies |R| = IR, | = amt < ams a contradiction! 2 The following proof of Delsarte, Goethals, and MacWilliams' Theorem 2.6.3 requires more lemmas than does theirs. It is not intended to be the most concise proof of the theorem, but to be illus- trative of the techniques to be used in proving 2.1. Restating 2.9: Theorem 2.9 Characterization of Minimum Weight Polynomials If Pe @ (m,q) where r = s(q-1) + t, 0 <t < q-1 and [P| = qe = (q-t)qg™@~ 8"! then P is equivalent to a polynomial Q where 34 uae Ss (207) QGe) =A H-K) M Ay-xyy) KDA EA if La; j J Proof: When m =1, s = 0 and Lemma 2.11 applies. Proceeding by induction, assume 2.9 is true for m-1. Corollary 2.8.1 states that P has a linear factor. Without loss of generality, assume x, divides P. By Lemma 2.7, éd(P,x,) =q-lor t. If €d(P,x,) = q-1, our induction hypothesis completes the proof. If £d(P,x,) =t < q-1, then P&,,x') ~ fH (x, -A,) P(X’). Order the elements of K, A,,...,A Then by 2.7, q: = ato) = gm-s-1 fori >t. By Corollary 2.15.1 we may assume P =P um AteL M42 where deg P < s(q-1)-2. This gives P= Py, it OAD OG-Aty2) By, &) i + » SO P(x, , x’) = Pvt + (X,-Ap, 4 )(%-Ap, 9) Pla, x’) fori>t+2. By Lemma 2.14, Py. =O fori>t+2soP) = Pred for a 1 i t i2t+2andP~ II (x.-a.)P which is the correct form by induction. jaa J Vo Ate It is helpful to prove one more lemma before beginning the proof of 2.1. This lemma is the restriction of 2.1 to the case r = s(q-1). Lemma 2.16 If Pe @ (m,q), r = s(q-1), and |p| > de =qu§, then {P| > qg™@-s + (q-2)q™-S-1, Proof: Ifm=1, s=1, andq™ %=1. |P/>1> |P| >2. Pro- ceeding by induction on m, assume 2.16 for m-1. If 35 |P| < gms + (q-2)q™7 8-1 then by Lemma 2.7, 2d(P,x,) =0 or gd(P,x,) =q-1. If d(P,x,) =q-1, then P = (1- xt-h BE) where IP] = |p| <q™"S4 (q-2)q™@~8-1 and Pe P.(q-1)(m-1, 0) so, by the induction hypothesis, |P| = q™~§. If £d(P,x,) = 0, order the elements of K A,,... eapores Ago so that |P,_| = q@™-S-1 for i <k and P| > g@-Sliop idk. If k =q, then |P | = guns, If k = 0, then the induction completes the proof. m-s-1 m-S-1 5) Lemma 2.14 so |P| =q + Ifk =1, then |P, | > 2q 1 2(q-1)g™-S-1 = g™-S . (q-1)q™~S"!, It k > 1, then by 2.15.1 we may assume that Py = P, so that for i > 2 1 2 P(e’) = P, (x’) + (Aj-21) QG-As) By (’) where deg P <r-2 -s-1 ~ . If IP, | = q™ S ,» by Lemma 2.14, 2 = 0 so, in fact, Pas = Pr and for i >k, k a TT (A,-A.)P, (x’) P, (x’) = Py &’) + rg where deg P<r-k . By Lemma 2.14, for i>k, |P,. | = kq™s-1 so [P| = kqm-s-1 + (q-k)kq™7 8-1 = k(qeke1)q™@-8-1, But since 2 <k <q-l, |p| = 2(q-1)q™~S-} = g™-S 4 (g-2)q™-S-!_ This completes the proof of 2.16. The proof of Theorem 2.1 splits into a number of cases. The 36 basic techniques used are the same as in the proof of 2.16. We begin by restating the theorem. Theorem 2.1 Let r = s(q-1)+t where 0 < t <q-1l, let dn = (q-t)q™8-1! | and let q-1 if t=1 c =¢ q-2 if t=q-l¥l min (q-t,t-1) otherwise If Pe @_,(m,q) such that |P| >d™, then [P| > a™ + eq™-S-?. Proof: Corollary 2.8.1 and Lemma 2.12 establish this result for s =0. Lemma 2.16 proves the case t = q-lifq>2. If Phas no linear factors, then Corollary 2.8.1 states that [P| > dp + (q-t)q™"5"?,, which satisfies the theorem except when t = q-1 and q > 2 which is covered above. To be a contradiction to the theorem, therefore, P must have a linear factor. Without loss of generality, assume x, divides P. If gd(P,x,) =q-1, then P ~ (1- xi-l)p and induction proves m-s-2 |p| > qn + Cq This completes the proof when q = 2. By Lemma 2.7, the only case left is when £d(P,x,) =t < q-1. t When this is true, P= Hwa) where dim P < s(q-1). . j= Order the elements of K, d,,... Aq, so that 37 IP, | = 1 lm-1 = =d™71 for i =t+l,...,tek and IP, | = Py, |> am at for i> tik. a a |P | = ) |P, | i=t+l1 by (201), so if k =q-t, then [P| = (q-t)qg@-S"! =a™. if k =0, then, by 1 2 . qm-s- m-s- Lemma 2.16, Py, | > + (q-2)q IP] > (q-(g™"S4 + (q-2)q™°8"%) = a™ + (q-1)(q-2)0™- 8 > dn + cqi-s-2 whenq >2. Ifk =1, then, by Lemma 2.14, IP, | = 2q™-S-! for i i >t+1 so |P | > qm-s-1 + (q-t-1)2q™~8-4 = de + (q-1-t)q@-8-1 >a 4 eqm 8-2 r since t < q-1. If k => 2, then, by Corollary 2.15.1, we may assume that im + _ gm-s-1 . . Pate 1 =P o if [P,_| = for i > t+2, write P,, = = Pre it (A. ip Ar ~ Ae2)P where deg P< s(q-1) - 2 which by Lemma 2.14 implies P =0. So Py = =P for i =t+1l,...,t+k. For k i >t+k, Py = P, Ate? Ht Opry, DR where deg R <s(q-1)-k, so by J= Lemma 2. 14, |P,. | = kq™-S-1 for i >t+k. Thus, i [P| > kq™"S1 4 (q-t-kykg@-S"? = al? + (ke1)(q-t-k)q™"&? > at + eqm- 8-1 38 since 1 <k<q-t. This completes the proof of Theorem 2.1. The full power of this approach is not realized in Theorem 2.1. Chapter three attempts to discover when the bound given by 2.1 is the best possible, and to characterize next-to-minimum weight polynomials. 39 CHAPTER 3 This chapter deals with two questions which arise from the techniques and results of chapter two: When is the bound given in Theorem 2.1 the best possible; that is, when is it the next-to- minimum weight ? What is the characterization of next-to-minimum weight polynomials ? Throughout this chapter, assume P ¢€ P (m,q), where r= s(q - 1) +t, 0 <t <(q - 1) unless stated otherwise. Theorem 2.1 states that the next-to-minimum weight for P. (m,q) is at least gm m-s-2 , tea , where an = (q- t)qg™78"! is the minimum weight, and q-lift=1 c= (q-2ift=q-1l#l min(t - 1, q - t) otherwise. The results of this chapter on the next-to-minimum weight are expressed in Theorem 3.1. Theorem 3.1 The next-to-minimum weight of Pm, q) is qn + eqm "8-2 where dq = (q ~ t) qu-s-1 is the minimum weight, and 40 4 if s = m-1 (Lemma 3. 2) t-1 ifs<m -1and1<t <(q +1)/2 (Lemma 3.3) or s<m-landt=q-1#1 q ifs=0, t= 1 (trivial) c= ¢ (q-l) ifq<4, s<m-2,t=1 (q-1) ifqg=3, sem-2,t=1 (Lemma 3. 4) q ifq=2,s=m-2,t=1 q ifq 24, 0<s<m~-2,t=1 (Theorem 3. 8) c, ifq 24, s<m - 2, (q+1)/2<t<q-1 (Theorem 3.11) t where Cy is defined to be the integer such that dy + C, is the next~to~ minimum weight of F,2, q). Proof: Each of the possible cases is proved in the result given in parentheses. The case s = 0, t= 1 is trivial, merely stating that the next-to-minimum weight for linear polynomials is q™. Lemma 3.2 Ifr=(m-1)(q-1)+t, 0<t<q-1, the next-to-mininum weight of H.(m, q) isq-t+1l= dn +1, Proof: The next-to-minimum weight is at least d)' +1, and the poly- nomial 41 m-l t-1 _ _ ,s7l _ _ .s Q(x) = in (1 Xe ) a (x, ri) where »; =A, > i=j l= j= . m _ 4m has weight det =d. + 1, Lemma 3.3 If s <m - 2 and either 1<t <(q+1)/2 ort=q-1# 1, with r = s(q - 1) +t, then the next-to-minimum weight of F(m, q) is qn +(t- 1)g"S-2, Proof: That the next-to-minimum weight is at least this value follows from Theorem 2.1. Formulas (208) and (209) give polynomials which s-2 have weight an + (t+ 1)qr” exactly. Ss t-1 -1 oo. Q(x) =A Xo MW = xt") MA; - Ky), =A; > EFI i=l j-1 s t -1 Q(x) =a (1 - x? ) Il Likes 1 X549)5 where i=l j=l Li (X41) X49) = OX os1 7 Bi X49 and a8; ~ OB, > ip}. The caset=1, 1 <s <m - 2 runs into some complexities. Theorem 2.1 states that the next-to-minimum weight in this case is at least (q - 1gm-s-1 1) g@7s-2, +(q- In most cases, however, 42 this is not the best possible lower bound, as will be shown later. When q = 2, 1 <s <m - 3, andt = 1, Kasami and Tokura [7] have found a polynomial, x,x,°°° Koy (K Xo + X41 9%543)) which has weight 27578 (g) = pm-S-1 , 9m-s-2) owing that the bound from 2.1 is best possible. Ifq=2, s=m - 2, t=1, however, all polynomials must have even weight. This fact follows from the Ax divisibility condition. It can also be proved by observing that r = (m - 2)+1=m-1< m(q - 1), so that, by Lemmal.7, >) — P(o) =0, oe€kK™ which implies that [P| is even, since P(o) « GF(2). Thus, the next- to-minimum weight cannot be 3, which is the bound given by 2.1. There is a polynomial, x,x, vee X,,.9? Which has degree m - 2 and weight 4, so we can conclude that the next-to-minimum weight of F., _y™, 2) is 4. When gq = 3, t=1, and 1 <s <m - 2, Theorem 2.1 gives the lower bound 2.3™787! 4 2,3™78-2 tor the next-to-minimum weight. The polynomial s-1 XXoii%s.9 HW Cl - x) i=1 has precisely this weight, so 2.1 does give the best bound in this case. 43 The preceeding discussion proves: Lemma 3.4 The next-to-minimum weight of Am, q) is: (4m ifr=1 gm-r , gm-r-1 if2<r<m- 2 when q = 2, ¢ 4 ifr=m-1 2 ifr=m = gm-s-1 , 3m-s-2 ifr=2s+2 0<s<m-2 when q = 3, ( 9.gm-s-1 + 9.3m-s-2 ifr=2s+11<s<m-2 3 if r = 2m- 1 2 if r= 2m S In the case t=1, 1 <s <m - 2, wheng 74, the situation is not as simple. From the proof of Theorem 2.1 it is evident that if qn < |p | < de + gm-s-1 then either P has no linear factors, or P~(1- x97) B, where deg B=(s- 1) (q- 1)+1 and |B] = [P|. Thus, to complete this case, a better understanding of polynomials without linear factors is needed. | Similarly, ifq 24, s<m - 2, and1<t<q - 1, the proof of 2.1 reveals: an <|P| <de +(t- 1)qg™~8~2 implies that either P has no linear factors or P~ @ - xa} B, Again, better bounds on the weight of polynomials without linear factors would be helpful. 44 In lemmas 2.14, 2.15, and 2.16 such bounds were developed for the case t=q- 1. Similar techniques will now be used to provide lemmas in the more general case. Lemma 3.5 Let Qe F(m, 4), r=s(q-1)+t, 0O<t<q-1, such that Q= (1 - x -1, Q, (x’). And let R € P59), 0<k <q-1, such that (1 - x27) does not divide R. If P= Q+R, then either [P| m2 (q-t+k)qg@7S"!, or k = 1 and there exists ad € K such that (1 - (x, - »)97}) divides P. Proof: Separate the variable x,, defining R, (x’) = RQ, x’) and P, (x’) = PQ,x’). By formula (201), AEK rA#0 Order the elements of K, A,,A,°°°, Xo so that A, = 9, IR, | = 0 for i <n, and IR), | >0 for i>n+41. By the hypothe- sis(1 - xa} { R, we know thatn<q-1. By Lemma 2.2, R(x, X”) = A(x, ~ Ai) (K - Az) ee> (K - AER, &’) +x, R&, ¥)], where deg R, <r ~ (k + n) and deg R<r - (k +n) - 1. 45 If P, #0, then deg P, = deg (Q, + R,) <max (r - (q - 1), r - (K+n)), ane dee Ra, <r-(k+n)fori>n+1, so |P| > (q-n- 1d (ican) + amet, where b = min((q- 1), (k+n)). (k +n) >(q - 1) implies |P| > q-n- 1)dy (cen) + oe): (q-n=1)((k+n) - (q+t-2)) q@™~5 + (q-t) gm-s-1 if (k+n)>q+t -1 (q-n-1)((+n) - (t-1))q™7S"* + (q-t) q™S" if (en) < qut-1 k QS 4 (q - t) gS lit(k+n)2> >qit-1 > k g@7Snhi(g-t) q@7S- lite +n)<qt+t-1 >(qet+k) g@78"1, (k + n) < (q - 1) implies |p| = (q-n)d, - (k + n) qq-t+(k+ n))q™@~8~2 if (k+n)<t = a= ) (1 -t+ (e+ n)q@"S"! if kan) et (q-t+ k)q™@~S-1 +n(t - (n+ k))q™@~S~2 if(k+n)<t (q-t+ k)q™"8"1 yn +k-t)(q- 1 -n)g@78-! if (k +n) 2t >(q-t+k)qg@s"} > with equality only when n+ k = t and P) are all minimum weight or zero. 46 If P, = 0, then R, = - Q,, so deg R, = degQ, =r - (q- 1). This implies r - (k + n) 2 r-(q-1), so (k+n) < (q- 1). (k +n)<q - 1 implies deg R,, <r ~ (k+n)-1fori>n+1, so (q-t+k+n+ qm 8? it k+n)<t-1 =(q-n-1) -ce (l-t+kens Yq?! if kan) et-1 (q-t+kjq@™7St4 m4 1(t-1- (n + k))q@™7872 if(kk+n)<t-1 (q-t+kjq@™7S-! 4 (n+k -(t-1))(q-2-n)g@™7S! if k +n) et-1 > (q-t+k)g™S}, with equality only whenn+k=t- 1 and P, is minimum weight or zero for eachd. (Note: n=q - 2 impliesn+k 2q- 1). 1 (k +n) =q - 1 implies |p| = (q-n- 1) qm 1) = k(q - t)q@-S- r- ‘@- =(q-tt+k~ 1qM7814 (ce - 1)q@-t - 1)q@7S" 2(q~-t+ k)gm-s-1 unless k = 1, sincet<q- 1. Ifk =1, then n=q - 2, and this is the special case which the lemma allows. 47 Lemma 3.6 Let Pe Fim, q), r= s(q - 1) + t,0<t<q-1. If, for some Ay, Ap € K, P, # O and (i - xt-}) |p, » andd< |P, |< 1 1 2 (q-t+1)q™~ $- 2 then there is an invertible affine transformation T, fixing x, for i¢ 2, such that if R(x) = P(T(x)), then (1 - xa7}) IR, and 1 -1 (1-xf")|R, . 2 Proof: P(x) = Py (x) + (x, - 4,) B(x), where deg BP <r - 1, so P, &’) = Py &’) + Q. -r,) BL &), deg Py <r - 1. Lemma 3.5 asserts the existence of ad such that (1 - (x, - yard) iP, . Define T(x) as follows: . 2 (x, - X,) [T(x)], = x, for i¢ 2, [T)], =x, +> Ann A 2744 Let R(X) = P(T(&)), then R, (x) = P, (x) and Ry’) = 0 unless 1 x, = 0, so, by Lemma 2.3, (1 - xd )|Ry,» and the lemma is proved. Lemma 3.7 Let P € /,(m, q) where r = s(q-1)+t, withhl1<s<m - 2, and 0<t<q-1. Let the elements of K, A,,°°--, dg be ordered so that IP, | Ks < PA | 48 If P has no linear factors, and P can be transformed R(x) = P(T(x)) by an invertible affine transformation T, fixing x,, so that - gq-1 i= eee o- q-1 (1 - xs IR, for i= 1, -+-,k but (1 - x27*) | Ryj,,1° then |p| = -g-2 de + k(q - k)q™ Swe Proof: [R | = |P |, and since T fixes x,, [R, | = [P| forA € K. R has no linear factors, sok <q. There is nothing to prove if | = k=0, soassumek >0. Then (1 - xa7}) IR, . If |R 1 Xx k+1 (q -t+k)q™@7S"2, then by (201), | k qa IRJ= Y IR |= Y IR 1+ YF IR i=1 j=1 i=k+1 >k(q - tha "8"? + (qQ- W\(q- t+ k)qg@™s? = an +(q- k)kq™@~S"2_ and we are done. i |R, .|<@-t+ka™*, write k+1 R(x, X2,%") = (1 - xB!) RG, H") + = AL e+ HL-A,) Rem, R"), where deg R<r-k. Then — #1, ~ — A —_— R. ( x”) = (1 - xd ) R (x”) + (> -X ae =“ ( ,x”). Arad Xe % Abad k+1 “1 k+1 Dat Xe 49 This is the situation of Lemma 3.5. If (1 - x24) | Ry, and -s-2 Ray |< -t+ka™"§ 3.6, there is a transformation T’, fixing x,, such that if S(x) = . xa7t - xa - xa R(T’(®)), then (1 - xf") |S, and (L- xf") |S, . If (2 - a) |S), for i<k’, but (1 - YS at? then since 2 <k’ <q-1, ls| 2 , then k = 1. But now, applying Lemma an + (q - 1)q™"S"*, which completes the proof. Theorem 3.8 The next-to-minimum weight of F. (m,q), where r = s(q - 1) +1, 0<s<m, andq 24, isq™®. Proof: The theorem is trivially true whenm=1, or s=0 orm- 1. Assume now that m 2 2 andl <s <m = 2, and that 3.8 holds for smaller m and smaller s with the same m. The theorem will be proved for this m and s by contradiction. Assume qe < [P| <q™". Then as observed in the proof of Theorem 2.1, P has no linear factors. Order the elements of K, A,, °+ "Ag so that IP), | Koee < [Pyq!- Then q |P| = 2 IP. | s alP, I, SO IP, | <qms-t 1= This implies, by our induction hypothesis, that |P, | = qmet 1 By Theorem 2.9, it may be assumed, without loss of generality, that (L- x9°1)|P, . Assume that (1 - £°4)|P,_ for i<k, but 1 1 30 (1-97) } p Then, by Lemma 3.7, Ake Thus, k= 1, q-1, orq. If k = q, then P has a linear factor; a contradiction. Ifk =q-1, then P(X, %) %") = (1 = A) BER) + (A = & - 2Q)1") BH, ®”), where deg P <r - (q ~ 1) anddeg P <r - (q-1). Thus, P, @) = xi-l) Be”) + Bx, %”). By (201), - | = SB | > (qn1)qmn2 Py glm-t 7 ok IP a olm-2 - P40! +P IPGL > @-ldpgny o#0 _ m-l = (q - 1) d. 7. q so|P|= Y |p, |= @-1)a™*+q-1amt=q™Ss i i=1 (q? - 4q+2)q™" 8-2 >q™-S when q > 4 Assume that k = 1. If Py, |< q@7s-1 then, by Lemma 3.6, there is an invertible affine transformation T, fixing x,, such that if R(x) = P(T(&)), then (1 - xa7}) IR, and (1 - xa7l) IR: Since |P| = |R|, the above reasoning may be applied by R to complete the proof. D1 Similarly, if (1- (x, - 474) IP, , there is such a transfor~ 2 m«s mation, and |p | 2q Thus, P, ,# 0, for at least two distinct 29 oe K. Let R.(x”)=P, (x”) = P, (o,x”) = P(Q,,0,X”). Order the o Az, 0 Ay elements of K, 0,, %, °**,0,, so that IR, | Keer. < IR, |. Suppose 1 q q that RR. =Ofori<n, andR # 0. By the above paragraph, 9% Cnt n<q-1l. Since (1 - xa71) |P, , write 1 (1) Play pK") = = PNY, 9 GD + OH = A) B Lm ®", where deg P< r-1-=s(q-1). Then 2) RyR) == oT) DL ok") + Oy - 1) B OL, E), so degR, < max(r - (q - 1), deg B(i,, 0, X”)). But deg B (A, o, ¥”) <(r-1)-n, by Lemma 2.7, so deg R, < r-1-n, and IR,.| 2 i (1 + n)qi™~8~2 for i>n. Thus, (3) Py, | > (q-n)(1+ n)g™~8~2 =q™u-s-l +n(q-1- n)gi~ 8-2. But |P| > |P, | + (@-1) |p, |, and, by assumption, ry re P| <q™"5, so |p| <q", (4) Py, I< (qg@78 - (q- 1)q™"8-2)/(q - 1) <qm7S-1y gm~s-2, 02 This contradicts (3) unless n= 0. Whenn= 0, (4) implies | < gim-s-2 + qm-s-3 IR, , which, together with Lemma 2.16, 1 forces IR, | = amt = gin-s-2, Suppose for i<k’, IR, | = qm- 8-2 1 : s-2 | 2 ; | . Then, by 2.16, fori>k’, |R and fori >k’, [R,,| >a" oj > g@S-2 4 (q - a)q™"S"3_ By (201), IP, | eer gS"? + q- kM = 2)q™S> + g™-s-2] = g@S-ly g -K/)(q - 2)qm™7S"3. Together with (4) above, this forces k’ =q-1lorgq. By arguments similar to those used in the proof of Lemma 2.16, there exists an i.a.t. T’(x’), fixing x, such that if R’ (x’) = Py (T'’)), then Ro = Ro for i<k’, where Rg ,is a minimum weight polynomial. i 1 L 1 By making the transformation T(x), defined by | T(x)], = x, for i #2, [T&],=x,- o HA , it may be assumed that 0, =0. Now 2 1 Ry = R, for o # 0, where IR, | = qm-s-2 and deg R, =r-1=s(q- 1). From (1), — ~j — “a — SO 1) (5) Py x") = (1- xf") P o(k”) + A, - A.) B (&, x”), where 2 1) 2 deg P, o=t- (q - 1) and deg B, <r- 1. 03 Since R, = R, when o # 0, (6) Py (%, %") = RR") + (1 - x27) R(x”), where deg R,=r-1landdegR<r - (q- 1). Combining (5) and (6), (1) Qa -Aa) Blas, X") = RAK) + (Leg YE-P, gH) + RE]. If R= 0,thendeg Py. =r. Since this is not true, R¢0. Letting 2 X,=0 in (6), Ry (x”) =R,(&") +R"). By Lemma 2.14, |R, | = (q-2)q™75-3, m-s-1 m-s-2 + qq - 3)q , contradicting (4). This final contra- SO Py, | 2q diction completes the proof. A similar proof could be given to establish the next-to- minimum weight in the case r = s(q - 1) + t, where s <m = 2 and (q + 1)/2<t<q-1, except that no starting point for the induction has been established. Such a point may be assumed as follows: Define C; for a fixed q and t, 0<t<q- 1, to be the difference between the next-to-minimum weight and the minimum weight of Y?.2; q). The minimum weight is d = (q~t)q. The next-to-minimum weight, is, by this definition, (q - t)q + c,. It has already been established that c, =q, and thatc,=t-1lforl<t< (q + 1)/2, by Lemma 3.3. Fort=q- 1, c=a- 2, by Lemma 3.3. From Theorem 2.1, when (q + 1)/2 <t<q- 1, then c, >q-t, and from the weights of polynomials (208) and (209), when (q - 1)/2<t<q- 1, then ce, <t-1. 04 The next lemma is analogous to Lemma 3.5 except that it deals with the case s = 0, which 3.5 does not cover. Lemma 3.9 Let P=Q+R, where Q € #,(m,q), 0<t<q-1; and R ef, (mM, q), 0<k <t. If Q depends only on x,, then either P depends only on x,, or lp| = ay +k qua} =(q-t+ k)g™=!, Proof: P=Q+R. Order the elements of K, A,, °*:, A, so that [P, |< .* < |P, [. From the definition (202) of P®, p® = Qf 4 a, oti) . Qi + it Ais Ait RD In (206), ind i _ (j) (j) P=) [Q R Tl (4, -A,), wh ri is [ Riad + Xa! - A; - A,) ere deg RG) i < t-k- j and a is aconstant. Suppose Py, = 0 if and Aj+ only if i <n, then pi) 1 =0 for i<n. This implies that Ait j _ [Qy + RG) ] 1 a, -A,), so jon Aj+1 kel i k 99 deg P,. < max (t-k-n, 0). Ifn2t-k, then RW) is a constant Aj Aj+1 for j?7n, soP,. is a constant for each i. Thus P depends only on i Xj. Ifn<t-k, then deg P, <t-k~n, so 1 | = Geoken = qQ+k+n- tq? Pp d | Anel an IP] > (q-n(qtk+n- tq? = (qQ-t+kq@ + n(t - k - ng? >(q-t+ k)gm=1 proving the lemma. -The next lemma proves a starting point for the induction proof of the following theorem. Lemma 3.10 Let Pe P,(m,q), 1<t<q-1. If |p| >a™, then |P| > -2 d,.+ Cy qm . Proof: True for m = 1 and m = 2, by the definition of Cy. Assume that the lemma is true for fewer than m variables m 7 3. Let P be a polynomial in m variables, with deg P <t and |P | > dy. Order the elements of K, A,,°°*°, doe so that IP, | KSeors IP |. Assume that P, =Ofori<nandP, #0fori>n. By Lemma 2.7, i i 06 |P| = a” + n(t - n)q@"2 2 qe +(t- 1)q™~2 > de + C} q@~2 unlessn=Oorn=t. Ifn=t, however, P is minimum weight. If n= 0, m-1 IP, | za". it |p, | >ad™-1, then by the induction hypothesis, |P, | > a7" + 1 1 C, g@ns so ipl =q P| > di" +e, gm? Without loss of generality, assume that P) depends only on x,. | 1 Further assume that P). depends only on x, for i = k, but P). i k+1 does not depend only on x,. If k= q, then P depends only on x, and | X,, and the lemma is true. Otherwise, 1 <k <q-1. Write P(X,, XX”) = P(x,,%) + (K, -~Ay)e + (K - d,) P (x,, x, X”), where deg B <t -k. P =B, (%) + yyy - And pay - Ay) BL eK” rd Mead? k+l 7 41 kt ~ “k) Try Me ) k+1 k+ | > qm-l + kg, By Lemma 2.9, |p ‘ Xx so k+1 o7 [P| =k at + q- KAM? + kq™"?) =d- +(q- ~k)k q@72 = oda (q=1a®? 2a? +0, Thus, in every case, |P| > ay > [P| >dP +e qm? Theorem 3.11 Let P € F(a, 4); where r = s(q-1)+t, 1<t<q-1, and q24. If [P| >d™=@-t)q™*7, then [P| > a +, 78, Proof: Lemma 3.10 proves this theorem for s= 0. The definition of Cy makes the theorem true form <2. Assume m ? 3, s 21, and assume that the theorem is true for smaller m and smaller s with the same m. Prove the theorem for this m and s by contradiction. Assume (1) aM < [P] <a™ +e, g™ "8"? < aM + & - 1)g™ 8”, If P has a linear factor y, then by Lemma 2.7, fd(P,y) = q-lort. If £d(P,y)=q-1, then P= (1 - x71) P, where Pe Pr-(q-1) (m - 1, q) so, from (1), qi -1) = a < [P| = |B | < a o-1) + Cy gm-s-2 contradicting the induction hypothesis. If n= t, then as in the proof of 2.1, |P| > qe > |p| = an +q" “sel Therefore, Phasno linear factors. If IB joa “1 , then, by the induction hypothesis, BR lea “1, +e.q0 “3 , SO ‘plea +e.q" s~ “2 Therefore, ow = =d0 1) . Assume without loss of generality, that (1- 1) xt 08 divides P,. Then, hy Lemma3.7, (P| zd +k(q- k)q™'~ 8-2 forl<k <q, 1 so |P| = qn +(q- 1)gm78~2 > qn +O qm-s-2. This completes the proof of 3.11. Theorem 3.11 completes the proof of Theorem 3.1. Theorem 3.1 reduces the area where the next-to-minimum weight of FP .(m, a) is not known, to the case m = 2,(q+ 1)/2<r<q-1l. In this case, if Cy, <(r - 1), then the next-to-minimum weight poly- nomials of F (2,4) have no linear factors, by Lemma 2.12. Corollary 2.8.1 gives a lower bound of (q-r) < c,. The next chapter discusses attempts to improve this bound by an examination of blocking sets in affine planes. The remainder of this chapter characterizes next-to-minimum weight polynomials of 7 (m, q) when0 <r <(q+1)/2. Lemma 3.12 Let Pe F (m, 4), where 1<t<q-1, such that [P| = a +(t- Lq™~?, If P is the product of t linear factors, then P is equivalent to a polynomial Q(x), such that either t-1 (1) Q(x) =A x, HW (x, -A,), where d, =A; =p i=j, i=1 or t (2) Q(x)=A Tl L(x, x), where L; = a, x, +8; x, and i=1 59 That is, Q is of form (208) or (209). Proof: If y is any variable, then, by Lemma 2.7, £d(P, y) = 0,1, t- 1, ort. If €d(P, y) =t for some y, then P is a minimum weight polynomial. If £d(P,y) =t- 1 for some y, then P is of form (1) above. If £d (P,y) = 0 for all y, then P has no linear factors. But P has t linear factors. Assume that for each variable y, £d(P, y) > 0>£d(P,y) =1. Then P is equivalent to a polynomial Q such that Q(x) = L,(x) L,(x) +> L, (x), where L, (x) = x,, L,(X) = %, the L. are all independent linear polynomials. t i-1 Z(Q) “VY [Z(L,) - Z(L,)A Y Z(LI, |= j= and this union is disjoint. Thus, t i~1 N@ =td™*- Y |[zayo\/ z@)I I. i=1 j=1 i-1 Let —-N, = ||Z(L,)a\L/ 2(L,) || and let N = N(Q). j=l N, = 0, N,=q™", and for i> 2, N, => q™@™%, If, for some i, Nj > qm? then 60 t t q@-! - (b= 1)gM72=q™- |p| =n=tq™t- J N,>tq™? ~ (t= Ug@?, i=l which is a contradiction. Thus N, = qm? for alli>2. i-1 | ge? =n, = |lz@ya Y 2a) || > [120 9 Za)v 2.) || j=1 = ||Z(L,) 4 ZL) || + []2(L,) 4 ZL.) || ~ ||Z(L,) a Z(Ly) 4 Z(L.) || 22M ~ ||z(L,) 0 2(L,) A ZL) || > a, so ||Z(L;) A Z(L,) 4 Z(L,) || = a™~*. Thus Z (L,) contains the (m-2) dimensional subspace of K™ described by x, = x, = 0. But then L;(x) = ajx, + 6jx,. The condition a8; = a8; = i = j assures that the factors are distinct. Theorem 3.13 If 1<r< (q+ 1)/2, then the next-to-minimum weight poly- nomials of 7 ,(m, q) are equivalent to either: r-l (301) Q(x) =A x, TE (x, ~ A,) where Aj = di; >i=j, or i=1 61 r (302) Q(x) =a L(x, X,) where L, = ax, + B;X»_ and i=1 o,f; = 08, pi=i. Proof: The next-to-minimum weight is ae +(r- 1L)q™=2, If |p| = ae +(r- 1)q™~2 < qn +(q - r)q™=2. then, by Corollary 2.8.2, P is the product of r linear factors. Applying 3.12 completes the proof, Given any r > 1, Theorem 3.13 characterizes the next-to- minimum weight polynomials for all but a finite number of q. The characterization of next-to-minimum weight polynomials in the general case requires better bounds on the weights of polynomials without linear factors. This subject will be dealt with in the next chapter. 62 CHAPTER 4 Using Theorem 3.1 and a complete knowledge of the next-to- minimum weights dy + C, of P(2,) for each t such that (q+1)/2 <t < q-1, the next-to-minimum weights of all Generalized Reed-Muller Codes could be calculated. In Chapter 2 it was proved that when (q+1)/2 <t <q-1, then q-t < c, <t-1, and further, that c, < t-1 implies that a next-to-minimum weight polynomial of (2, q) has no linear factors. The goal of this chapter is to improve the lower bound on Cy by improving the bound given by Corollary 2.8.1 for the weights of poly- nomials without linear factors. This will be done by exploring a related - topic; blocking sets. Blocking sets may be defined for either finite projective planes or finite affine planes. Much of the work of A. Bruen [3] concerning the former, can be extended to the latter. This chapter deals mainly with the affine plans K’ where K = GF(q), but, where possible, more general results will be derived, with results for projective planes being given in square brackets. Bruen gave the following definition of a blocking set. Given a finite projective plane II, a subset S of II is calleda blocking set in II if and only if each line of II contains at least one point of S and at least one point of IES. Clearly, this definition would still be meaningfulif 1] were an affine plane. For this study, a slightly more general concept is needed. Let fl be a finite affine [ projective] plane, and let S be a subset of Il. S is called a blocking set of order n in I] if and only if each line of I contains at least n points of S and at least n points of H-S. 63 The relationship between blocking sets and low-weight polynomials is expressed in the following lemmas. Lemma 4.1 lf Pe (2,4), 0<t <q-1 such that d < [P| < d, + (t-1), then S(P) is a blocking set of order q-~-t in the affine plane K’, (K = GF(q) ). Proof: By Lemma 2.12, sucha Phas no linear factors. The rest follows from the following lemma. Lemma 4.2 If Pe (2,4), 0 <t <q-1 such that P has no linear factors and |P | <d) + (t-1), then S(P) is a blocking set of order q-t in K’. Proof: Let £ be a line of K. Then & corresponds to the zeros of a linear polynomial (a variable) y. | 2 nS(P) || # 0, for that would imply y |P. But P restricted to 2 is a polynomial of degree at most t, so ||[2n S(P) || => q-t. Finally, to show that ||@S(P)|| <t, use the next lemma. Lemma 4.3 Let If be an affine plane of order q. Let S be a subset of H such that ||S|] =nq+b, where 0 <b <q-1-n. If, for each line 2 of H, ||Sag|| >n, then S is a blocking set of order n inf. 64 Proof: Suppose that for some line g of H, || 2n S|] =q. Let L, =£,L,,...,L,, be q parallel lines of HI. q nqt+b = ||s|} = |[Soul] =) |[saty||=a+ ) [saul i=l i=2 >q+(q-1)n=qn+ (q-n) , contradicting b <q-1-n. Now, suppose that ||2nS|| >q-n. Let x bea point of £-S, and let the q+1 lines through x be Ly, =2,L,,..., Lg: q nq+b = ||S{| = » [|]L, 9S || >q-n+ qn >ng+b , i=0 also a contradiction. This completes the proof of 4.1, 4.2, and 4.3. Thus, it has been shown that, to each sufficiently low weight poly- nomial P of degree t without linear factors, there corresponds a blocking set of order q-t, the set S(P). Whether the converse is true is not wholly known. The blocking sets of order one constructed in the proof of a later theorem will indicate that a meaningful converse to this lemma may not be possible. Many of the following lemmas concerning blocking sets were proved by A. Bruen [ 3] for blocking sets of order 1 in projective planes. 65 Lemma 4.4: (Generalization of Bruen, Lemma 3.2) Let S be a blocking set of order n ina finite affine [ projective] plane [I of order q, such that ls || =nq+b. If @ is any line of 1, then ||@ns|| <b. Proof: if ||2nS||>b, then letxe &-S. Let Ly = £,1,,...,Lg be the q+1 lines of If containing x. Then q si] = Y [Lia s|[>b+an , i-0 contradicting ||S|| = nq+b. From Lemma 4.4, one can conclude that a blocking set of order n in a plane of order q has at least nq+n elements. This conclusion is precisely the same as one may draw from Lemma 2.8. The next lemma is a counting argument which will be used later. Lemma 4.5: (Generalization of Bruen, Lemma 3. 3) Suppose that c objects are packed into a slots, at least n toa slot, and that an<c <a(n+1). Define afunction f on the objects x as follows: 1 if the slot containing x contains more than n objects f(x) = 0 if the slot containing x contains exactly n objects For each packing P, define A(P) = 2f(x), where the sum is taken over all the objects x. Then A(P) <(c-an)(n+1). -66 Proof: | If, in the partition P, some slot contains more than n+1 objects, then, by the restriction c < a(n+1), there is a slot with exactly n objects. If a new partition P’ is derived from P by removing one object from the slot with more than n+1 objects, and placing it in a slot with exactly n objects, then A(P’) = A(P) +a. Thus, A(P) is maximized when P has only slots with at most n+1 objects. In this case A(P) = (n+1)(c-an). For the next portion of this discussion, let II be an affine [ projective] plane of order q. Let S be a blocking set of order n in II such that I{s [| =nq+b. Define k = max [|e ns lI, the maximum taken over all lines £ off. By Lemma 4.4, k <b. Let L be a specific line of I such that ||L» S|| =k. Lemma 4.6: (Generalization of Bruen, Lemma 3.1) With the above definitions, k >n. Furthermore, k =n+1 implies b=n+1. Proot: By definition, k>n. Thus, b2>n. Let L,=L,L,,... Lig be the q+1 lines through a particular point x e L”S, then Gg S|] = ) [[sab,||-4<(q+)k-q i-0 If k =n, then ||S|| < qn + (n-q), contradicting [|S || > qn. If k =n+1, then 1s || = (q+1)(n+1)-q =qn+ (n+1). So, n+l =k <b= IIs || ~ qn <n+l. Thus, b =n+1, and Lemma 4.6 is proved. 67 Now, define B, the set of lines of 7 other than L which intersect L-S and contain more than n points of S: B ={2(|isa line of 1, 2 #1, such that Qa (L-S) ¢¢and ||gns|] >n} Define the set of incidences I of points of S with lines of B: I = {(x, 2) |g €B and xeLns} The next two lemmas count I. Lemma 4.7: (Generalization of Bruen, Lemma 3. 4) ||t]| < (@+1)(b-k)(q-k[+1]), that is |||] <(n+1)(b-k)(q-k) for affine M1, [ ||I|] <(n+1)(b-k)(q-k+1) for projective I]. Proof: For each point y e L-S, the nq+b-k points of S- L are packed into q lines through y. By Lemma 4.5, these lines through y yield at most (n+1)(b-k) incidences of I. Since there are q-k such points y e L-S [q-k+1 if fl is projective], the lemma is proved. For the next lemma, if B + $, define d = max ||€S||. Then LEB d>n. Lemma 4.8: (Generalization of Bruen, Lemma 3.5) If B#, then ||I|| > (qn+b-k)(nk+b-k’~k+q] +k-n] )(d-n)~. 68 Proof: Let x be any point of S-L. Then ||S|| - 1 = nq+b~1 other points of S are partitioned into q+1 lines through x. Exactly k of these lines intersect LAS. Each of these contains at most k-1 points of S - {xt . In the affine case, there is exactly one line through x parallel to L. This line contains at most k-1 points of S - { x} . {In the projective case, no such line exists.| Thus, in the affine case, there remain at least nq+b-1-(k+1)(k-1) points of S - {x}, partitioned among the remaining q-k lines. [In the projective case, nq+b-1-k(k-1) points; q-k+1 lines.] But, since no line of B contains more than d points of S, the number of incidences in I of the form (x, £) is at least (nq+b-k*~(n-1)(q-k)[+k-n])(d-n)~* = (nk+b-k’-k+q[ +k-n])(d-n)7* Since there are precisely nq+b-k such points x € S- L, the lemma is proved. The next lemma is used to delete d from the inequality. Lemma 4.9: (Generalization of Bruen, Lemma 3.6) (d-n) < 3(b-n). Proof: Some line of B, call it L,, contains d points of S. Letx=Lvnl,, thenx ¢S. Let Ly =L, and let Ly, L,,..., Lg be the q+1 lines through x. q nqg+b = |/S|| = »; |]L, 9 S|| => k+d+(q-1)n = qn+(d+k-n)_, i-0 sob 2>d+k-n. 69 Thus, b-n > (d-n)+(k-n). By definition, d < k, so (b-n) > 2(d-n), proving the lemma. Combining Lemmas 4.7, 4.8, and 4.9: (b-n)(n+1)(b-k)(q-k[ +1]) > (b-n) ||I|| > 2(qn+b-k) (nk+b-k?-k+ql +k-n]) , so when B ¥ ?, then (401) (b-n)(n+1)(b~k)(q-k[ +1]) > 2(qn+b-k) (nk+b-k’-k+q[ +k-n]) Furthermore, when B = ¢, then (401) still holds, since the right side must be non-positive, and the left side non-negative. Observing that (n+1)(q-k[ +1]) = 2 (na- k{ + nat ] - in-eria) < 2(nq-k+b), since n > 1 [and b > neh] ; simplify (401) to get (402) (b-n)(b-k) > nk+b-k’-k+qi[+k-n] Let (403) f(k) = (b-n)(b-k)+k°+k-nk-b-q[4n-k] _, then f(k) > 0. Evaluating f at 0 and b, £(0) = (b-n)b-b-q[+n] = b(b-n-1)-q[+n] f(b) = b°+b-nb-b-gq[+n-b] = b(b-n-1)-q+b[+n-b] > £(0) 70 Since f is concave upward, and 0 <k <b, then 0 < f(k) < f(b) = b(b-n) -q[+n-b]. This proves the following theorem. Theorem 4.10: (Generalization of Bruen, Theorem 3. 8) If S is a blocking set of order n in an affine [ projective] plane of order q, such that ls | | =nq+b, then: (404) | b(b-n) -q[+n-b] = 0 or, in other words, (405) b>3 (nf+4] + Veal 11)" 4a | In the projective case with n=1, Theorem 4.10 reduces to Bruen's result, |{S||>q+vq+1. When q isa square, Bruen points out that a subplane of order vq isa blocking set of order one with exactly q+ vq +1 elelents. When q is not a square, however, this bound is not necessarily "tight". He improved the bound by "point chasing" in specific cases. For q = 10 and q = 11, he expressed his results in his Theorems 4.1 and 4.2. Bruen's Theorem 4.1 Suppose there exists a projective plane Tof order 10. Assume that II contains no projective subplane of order 2. Then if S is a blocking set (of order 1) in II, we have ||S|| > 16. Bruen's Theorem 4.2 71 If M1 is a (projective) plane of order 11, and S is a blocking set (of order 1) in Tl, then ||S|| > 17. Further, the case ||S|| = 18 occurs. Table 4.1 summarizes Bruen's results for blocking sets of order one in small projective planes. Besides the lower bounds which he obtained, he gave constructions of the smallest blocking sets which had been found for planes of small order. deal with the existence of blocking sets. Lower Bound on the Size of a Blocking Set S of Order One in a Projective Plane of Order q”* Table 4.1 Bruen stated two theorems which q Bound from Improved Improvement Smallest Bruen Th. 3.8 Bound Technique Known 3 | |isil=6 Lee | wee ; 4 I|s|| >7 -o --- 7 5 I|s|] > 9 - --- 9 7 [Is || > 11 (IS |{ > 12 | "point chasing" 12 8 Ils || = 12 ||S|| =13 | “point chasing" 13 9 |[S|| = 13 ~--- | --- 13 10 [Is || > 15 [[s||}=16 |! Bruen Th. 4.1 20 (if no subplanes of order 2) 11 [|S |] = 16 [Is }| > 17 | Bruen Th. 4.2 18 *A. Bruen [ 3]. 72 Bruen's Theorem 2.1 If II is the projective plane of order 2, then there does not exist a blocking set in II. Bruen's Theorem 2.2 If Il is (a projective plane) of order n > 2, then there exists a blocking set S (of order 1) in 1 with ||S|| = 2n. Bruen also gave three, more specialized constructions of smaller blocking sets. His Theorems 5.1 to 5.3 deal with the projective planes PG(2,q) where q = v’, p prime, which may be derived from the affine planes AG(2,q) = K’, K = GF(q) by adding a line at infinity. Bruen's Theorem 5.1 Let II = PG(2,q), q = vt, p an odd prime. Then there exists a blocking set S in II such that ||S|| = pi + Apt, 3), Bruen's Theorem 5.2 Let II = PG(2,q°), t >2. Then there exists a blocking set S in H with |||] =q' + (q'-1)(q-1)™ Bruen's Theorem 5.3: (Due to Ostram) There ome blocking sets Sin II = PG(2, q°) such that Isl] =ab+qht44. (Ht>2.) The constructions used in these last three theorems do not readily adapt to the affine case. The first two theorems are adaptable as follows. 73 Theorem 4.11 There are no blocking sets of order 1 in an affine plane of order q, wheng <3. Proof: By Theorem 4.10, if S is such a blocking set, then [|S|] = q+ (1+ v4q+1). But, by the definition of blocking set, Il- $ is also a blocking set. Thus, q+ 3(1+ v4q+1) < {Is || <q'-q-#(1+ V4qgt+1) 2q+1+v4q+I < q° This implies q > 3. Theorem 4.12 If II is an affine plane of order q withq >4, then there isa blocking set S of order 1 in I such that ||S|| =2q-1. Proof: Let xy,Zy, be a parallelogram in Il. That is, if ab denotes the line through a and b, then xy, ||zy, and xy,||zy,. Let w be any point of Yi. except y, or y,. Let S be the set S = xy, uxy, v{zt u{wt - {y,} - ly.t The same construction would work for q = 4, except that wz might contain 4 points of S. We resolve this problem as follows. 74 Theorem 4.13 If II is an affine plane of order 4, then there exists a blocking set S of order 1 in II such that ||S|| ='7, if and only if Il + AG(2,4). There is, however, always a blocking set T of order 1 in II such that ||T || =8. Proof: Suppose that for some parallelogram xy,zy, in II, XZ Ny,y, # >. Then let w = xz/* y,y,, and let S = xy, u xy, u {zt} vu {w} - {y,} - {y,}. Thus a blocking set S with ||S|| = 7 exists if II does not satisfy the parallelogram condition: the diagonals of every parallelogram are parallel. If S is any blocking set of II such that ||s || = 7, then, by Lemma 4.6, there is a line L of II such that |[La S||=3. LetxeLasS. Consider the q+ 1 lines through x, L, = L,L,,..., Lg. 4 T= |[s|] = 2% [[byasl|-4 i=0 sO bs |[L,9 S]|=8. If |[L, 1 S|] > 2 for eachi=1,...,4, then S - fx is a blocking set, and [|S - {x} || = 6, contradiction 4.10. Thus, there is an i’ such that ||L,,9 S|] =3. Let L’=L,. Lety,eL-§, y, € L’ - S and let z complete the parallelogram xy,zy,. We have that xy, u xy, - {y,} - {y,} <S. This accounts for 5 points, and leaves 3 lines unblocked; y,z, y.z, and y,y,. Since y,,y, ¢ 8, z€S. We must also have . some w € SO y,y2 - {y.} - {yo . The line Zw intersects xy, and xy,. If it intersects them in distinct points, it would contain four points of S. Thus x € zw and w € xz 9 y,y, showing that II does not satisfy the 75 parallelogram condition. That AG(2, 4) is the only affine plane of order 4 which satisfies the parallelogram condition can be established by point chasing. To find T, let xy,xy, be a parallelogram. T = xy, uv xy, v y,Z -~{x}-{y,}. This completes 4.13. It is interesting to note that the blocking set S =xy, v xy, viz} u{w} -{y,}- t{y.} from Theorem 4.12 is not the support set of a polynomial P « (? q-1'2)%). If it were, then, by Theorem 1.6, if R € ,(2,q), then (1) >», P(O)R(G) =0 , EK since q > 5. Let R be the product of three linear factors corresponding to the lines Xy,, XYz, and y,z. Then |PR| = 1 contradicting (1). This observation casts some doubt on the conjecture: Every blocking set S of order 1 in the plane AG(2,q) such that ||S|] < 2q-1 is the support set, of a polynomial of degree q-1. This conjecture, along with earlier results on polynomials would imply that no such blocking sets exist. The conjecture is vacuously true for q <9, as established by a computer search. The hope of proving it in the general case as a | means to establishing a lower bound of 2q-1 on the number of elements in a blocking set, appears to be useless, however. The following conjecture would establish that c, =t- 1 for q > 4. 76 Conjecture 4.14 Let Il be the affine plane AG(2,q). If S is a blocking set of order n in Il, then ||S|| > nq + (q-n). Actually, to prove that c, =t-1, only [|S || => nq + (q-1-n) is needed, but 4.14, together with Theorem 4.12, would give the size of the smallest blocking set of order one. If n > q/2, then 4.14 is vacuously true. If n <q/2, then, by Theorem 4.10, IIs || =ngq +b, where b = (n+ ve — 4g | . Sincen<q-l, n’+4q >n’+ 4n+4. This proves Lemma 4.15. Lemma 4.15 Let I] be an affine plane of order q. If Sis a blocking set of order n in If, then I|s || >nqgin+ 2, (i.e., the case k =b =n+1 of Lemma 4.6 does not occur). The next lemma is a bit more difficult to prove. Lemma 4.16 Let Il be an affine plane of order q. Let S be a blocking set of order n in If such that ||S|/ =nq+b. If b =n+2, thenn = q/2 - 1. Proof: Let k = max||¢nS!||, where the max is taken over all lines @ of IL Let L be a line such that |[LaS|| =k. By Lemma 4.6, k =b =n+2. This being the case, every line except L which intersects L-S contains exactly n points of S. Picka pointx«S-L. Let Ly be the line through x parallel to L. Let L,,...,L, be the lines through x which intersect 77 La” S, and let Lay sees Ly be the lines through x which intersect L-S. Then q k nq+b= ||S||= )) |[L;9S||-q=(a-kyn-q+ )) ||/L,-S]| i=0 i=0 so, in using k = b =n+2, k >, (k- |L,- $]||) = 2k-q i=0 But, each term of the sum k - |b, a8 || is non-negative. Suppose 2k-q <1, then ||L,1 S|| >k-1=n+1, so each line of II which is parallel to L would have at least n+1 points of S. This would imply [|s || >qn+q = qn+n+2 acontradiction. Thus 2k-q = 2. Substituting k =n+2, 2n+4 > q+2 orn 2 (q-2)/2 which was to be proved. Lemma 4.15 and Lemma 4.16 establish Conjecture 4.14 for n > (q-3)/2 and the weaker result for n > (q-4)/2. In addition to these two lemmas, another technique may be used to establish the truth of Conjecture 4.14 in certain cases. A computer program was written to run on the Xerox Data Systems 930 computer, which accepts as input, values for q, n, and b, along with information on how to build the finite field GF(q). The program builds tables which represent the affine plane ff = AG(2,q). It then searches for blocking sets of order n in II with at most b elements. If it locates such a blocking set S, the program resets the value of b to ||s | - 1 and continues the search. Thus, the program is intended to finda minimum size blocking set with at most b elements. The number of subsets of {1 which must be tested, to 78 determine whether they are indeed blocking sets, is large. The program uses the technique of backtracking to reduce the number of possibilities which must be tested. Negative results from such a program must be accepted with a degree of reserve, because the accuracy of the coding of the program, and indeed, the functioning of the computer hardware, can- not be verified. Therefore, the lower bounds on the sizes of blocking sets derived by the computer program are annotated by being followed by asterisks. The following results, not given by previous lemmas, were derived by the program. Result 4.17 Let II be the affine plane AG(2,q), and let S be a blocking set of order n inII. Then a) q=7,n=1 => |/S|| > nqg+q-n =13"* b) q=8, n=1 => ||S|| >nq+q-n =15" c) q=8,n=2 => |S || => nq+q-n = 22* d) q=9, n=1 => ||S|| > nq+q-n =17* A summary of the results concerning blocking sets of order one is given in Table 4.2. Finally, these results on blocking sets of order n in affine planes may be applied to the prime objective of this paper, by Lemma 4.1. Lemma 4.18 Let the next-to-minimum weight of (P(2, q) be (q-t)q+c,. If (q+4)/2<t<q-1, thenc, > q-t+3. If (q+1)/2 <t < (q+4)/2, then Cy =t-1. 79 Table 4.2 Lower Bound on the Size of a Blocking Set S of Order One in an Affine Plane of Order q — <= Bound from Improved Improvement Smallest q Theorem 4.10 Bound Technique Known T 4 IIs|| >=7 Not AG(2, 4) 7 | [|S|| = 8 for AG(2, 4) 8 Theorem 4.13 5 \|s|| > 8 |Is|}=>9 | Theorem 4.16 9 7 Is || > 44 |s|| =13* | Computer search 13 8 [|S || = 12 [[s|| = 15* | Computer search 15 9 l|s|| = 13 [|s|] =17* | Computer search 17 11 [|S || = 15 | 21 Proof: Lemma 4.18 follows from Lemma 4.1 and the application of Lemmas 4.15 and 4.16. This lemma will be integrated with Theorem 3.1, to form Theorem 5.1 in the next chapter. 80 CHAPTER 5 This chapter begins with a theorem summarizing much of the work of chapters two through four. Theorem 5.1 If P is a polynomial of degree r = s(q-1) + t, withO <t <q-1, in m variables over GF(q), and N(P) is the number of zeros of P, then: 1) N(P) >q™ - g™-S + tq™~5-! implies that P is identically zero, 2) N(P) <q™ - g™S 4 tq™@-s-1 implies that N(P) < q™@ -qus m-s-1_ , .m-s-2 + tq cq where {~ q if s=m-1 or if t =1 and either s =0 or q24ors=m-2andq =2 c =(a-1 if t =1 and either q=3and0<s=m-2or q<4and0<s<m-2 t-1 if s<m-1 andeither 1 <t < (q+5)/2 or L 1<t=q-1. In the remaining case, (q+5)/2 <t<q-1, s<m-1, q >4, q-t+3<c <t-1. Furthermore, there exists a polynomial P € & .(m, q) with N(P) = q™- g™@-8, tq™-s-1 _ eqm 8-2, Proof: Theorem 3.1 and Lemma 4.18. In the notation of coding theory, Theorem 5.1 might be stated: 81 Theorem 5.1* The next-to-minimum weight of the rth order Generalized Reed- Muller Code of length q™, where r = s(q-l)+t, 0 << t <q-1, is m-s-l + m-s-2 (q-t)q cq . The restrictions on c are given in Theorem 5.1 and displayed in Table 5.1 The rest of this chapter concentrates on methods by which more knowledge about the weight spectra of Generalized Reed-Muller Codes might be obtained. Theorem 4.10 gives better results than Theorem 5.1 in the case (q+5)/2 <t <q-1 if 2 2 nt Be - Aqt+t > q-t+3 > when the smaller of the former expression and t-1 is a lower bound for c. This improvement in 5.1 is miniscule compared to the improvement which could be derived from proving Conjecture 4.14. In that case, the lower bound of t- 1 would stand, and it would be a tight bound. A back- tracking search by computer might establish 4.14 in a few more specific cases. The smallest case not yet tested would be q = 9, t =2. It would take an estimated fifty hours to complete this case with the currently implemented program on the XDS 930 computer. The program is equipped with a means of being interrupted and restarted so that it may be run during lulls in the computer's schedule. It is probably beyond the capacity of this program to complete the case q = 11 in a reasonable amount of time. 82 T-b>35 2/(gtb) 2/(g+b) > 34> T =9 b=90 b=90 b=90 b=90 b=0 b=90 [-w=s T-35 I-}=0]|1 b=0 T-}=0 b=9/| T-b=0,; b=90 Z-W=S>9Q os ¢4+4-b T-35 I-3=9] b=0d T-}=9 b=90] {-b=90| T-b=o]lz-w>s>9Q as ¢+43-b I-75 I-}=9] bd=0 T-32=9 b=0] b=0 b=090 T-wWw>s=9Q a> ¢+4-b zb ¢=b p<b p<b p<ebi ¢g=b z=) - b# T-b=3>fT qT + T= Z-S-W + pg-wyQ-b) = JusteM UNUITUTIN-07-7KON “T-bS4>0 4+(T-b)s= 4 SI9UM ‘,T'G Wetoay.L Sq usAtD (b‘w)" WUD Jo WBIEeM UNUTUTW-0}-7x0N UO suOToITSEY T°¢ S19eL 83 The computer might also be considered for use in an attempt to enumerate the equivalence classes of reduced polynomials of degree r in m variables over GF(q). Such an attempt does not seem to hold much promise for the following reason. The number of equivalence classes of & 7m, q) must be at least as great as the quotient of the num- ber of polynomials in O(m, q) by the number of invertible affine trans- formations. From Chapter 1, the number of invertible affine transfor- mations is q™(q™-1)---(q™ - qm), Also from Chapter 1, if p(k, m, q) represents the number of m-tuples of integers (a,,a,,...,€@y,) such that m 0<a, <q and Dy a, =k, then r (501) | dim @.(m,q) = ) p(itm,m,q) i=0 And,. since m™ml om i m’+m (502) the number ofi.a.t.'s =q” I (q°-q)<q ’ 1 (503) the number of equivalence classes of © .(m, q) is at least q? where r b = >, p(i+m,m,q) - m’ - m i=0 p(m,m,q) = 1 p(m+1,m,q) =m 84 m(m-1) /2 if q=2 p(m+2,m,q) = m(m+2) /2 if q >2 m(m-1)(m-2)/6 if q =2 p(m+3,m,q) = ¢« m(m-1)(m+4)/6 if q =3 m(m+1)(m+2)/6 if q >3 Thus, from (503), the number of equivalence classes of (mm, q) is at least q? where 1+ m(m°-6m-1)/6 if q =2 b =< 1+ m(m-1)/6 if q =3 1 + m(m*+5) /6 if q>3 In either of these cases, the number of equivalence classes grows rapidly with m. Therefore, there seems to be little hope of finding canonical forms for polynomials of Y.(m, q) when r = 3 and m is even moderately large. Since canonical forms have been found for r = 2 (McEliece [9]), there is little new knowledge to be gained in this area without significant new techniques. There is another way in which digital computers fail to obtain hoped-for results concerning weight spectra of GRM codes. One might hope to determine the weight spectrum of a GRM code empirically by a Monte Carlo method. That is, one might generate polynomials of & -(m, q) with random coefficients in GF(q), determine their weight, and tabulate the results. This technique fails because the distribution of 85 1 weights is so dense near q™ - que and so sparse in low weight poly- nomials that the probability of a random polynomial having low weight is very small. Since we expect no gaps near the mean weight, qn - gm lh other than those predicted by Ax, this process yields no interesting information. There is one exception to these gloomy predictions of the useless- ness of further computer applications in this area. A computer program may be able to determine, with a reasonable amount of computer time, _ the smallest subsets S of the plane K, K = GF(q) which correspond to support sets of polynomials of (P (2,4) without linear factors. Armed with these results and the results of chapters two and three, it might be possible to characterize the polynomials in Y (m, q) of less than a certain. weight for some specific r > 2 and q > 2. With enough results of this kind, conjectures and directions for further study might result. _ Even without computer aid, the techniques and results developed in chapters two and three hold the promise of characterizing the low weight polynomials in certain cases, especially when r = s(q-1) +t, 0<t < (q+1)/2. What types of theorems might we be able to prove once we have more data concerning weight spectra? We might hope to get results which generalize Kasami and Tokura's classification of all polynomials with weight less than 24 times the minimum weight when q = 2. In the general case, however, this bound may be q/(q-1) + (q-1)/q times the minimum weight, or some similar expression. The McEliece results on second order GRM codes hint at the possibility of an extension of the divisibility condition of Ax. McEliece found that if P ¢« & .(m,q), then 86 N(P) = gy vg-J- , where v = 0, +1 or + (q-1), andO <j <[s]. Thus, not only does q? divide N(P), where b = pat) =-m- [5] -1,as proved by Ax, but also |[N(P) - gu-t | > q* => q® divides |N(P) - gm-1 . These two divisibility conditions do not fully characterize McEliece's results. A condition similar to the second: |N(P) - gn} | = bound =>q* divides |N(P) - gn} l, where bound depends on a, q, m, andr; exists in the general case. Whether bound can be chosen to have a nice functional form remains to be seen. In conclusion, more data are needed. Knowing the weight spectrum of (_.(m, q) for specific q >2, r >2, m = 2 could prove helpful. Using the results of chapters two and three, more data on low weight poly- nomials might be derived. It appears that the general problem of characterizing all polynomials in ( im, q) or even of finding the weight spectrum, is extremely difficult. More work on low-weight polynomials could probably improve the results obtained herein, however. [1] [2] [3] [4] [5] [6] [7] [8] 87 REFERENCES Ax, James. "Zeroes of Polynomials over Finite Fields,'' American Journal of Mathematics, Vol. 86, No. 2 (April 1964), pp. 255-261. Berlekamp E.R. Algebraic Coding Theory, San Francisco; McGraw-Hill, 1968. Bruen, A. "Blocking Sets in Finite Projective Planes, '' SIAM Journal on Applied Mathematics, Vol. 21, No. 3 (November 1971), pp. 380-392. Chevalley, C. "Demonstration d'une hypothése de M. Artin," Abhandlungen aus dem Mathematischen Seminar der Universitat Hamburg, Vol. 11 (1936), pp. 73-75. Delsarte, P., Goethals, J.M., and MacWilliams, F.J., "On Generalized Reed-Muller Codes and Their Relatives, " Information and Control, Vol. 16 (1970), pp. 403-442. Kasami, T., Lin, S., and Peterson, W.W. "New Generalizations of the Reed-Muller Codes, ' IEEE Transactions on Information Theory, Vol. I-14 (1968), pp. 189-199. Kasami, T., and Tokura, N. "On the Weight Structure of Reed- Muller Codes," IEEE Transactions on Information Theory, Vol. II-16, No. 6 (November 1970), pp. 752-759. Kasami, T., Tokura, N., and Azumi, S. "Weight Enumerator Formulas of Reed-Muller Codes for 2d <w < 2.5d," (January 1973), Faculty of Engineering, Osaka University (in Japanese). [9] [10] [11] [12] [13] 88 McEliece, Robert J. "Combinatorial Communication: Quadratic Forms Over Finite Fields and Second-Order Reed-Muller Codes,'' Space Program Summary 37-58, Vol. II; Jet Propulsion Laboratory, Pasadena, California, pp. 28-33. Sugino, M., Ienaga, Y., Tokura, N., and Kasami, T. "Weight Distribution of (128, 64) Reed-Muller Code," IEEE Transactions on Information Theory, Vol. IT-17, No. 5 (September 1971), pp. 627-628. van Lint, J.H. Coding Theory, New York; Springer-Verlag, 1971. van Tilborg, H. 'Weights in the Third-Order Reed-Muller Codes," The Deep Space Network Progress Report for May and June 1971, Technical Report 32-1526, Vol. IV (August 1971); Jet Propulsion Laboratory, Pasadena, California; pp. 86-94. Warning, E. ''Bemerkung zur vorstehenden Arbeit von Herrn Chevalley, '' Abhandlungen aus den Mathematischen Seminar der Universitat Hamburg, Vol. 11 (1936), pp. 76-83.