Linear Recurring Sequences Over Finite Fields Citation McEliece, Robert James (1967) Linear Recurring Sequences Over Finite Fields. Dissertation (Ph.D.), California Institute of Technology. doi:10.7907/1KMK-T118. https://resolver.caltech.edu/CaltechETD:etd-10012002-154611 Abstract This thesis deals with the problem of how the elements from a finite field F of characteristic p are distributed among the various linear recurrent sequences with a given fixed characteristic polynomial fε F[x]. The first main result is a method of extending the so-called "classical method" for solving linear recurrences in terms of the roots of f. The main difficulty is that f might have a root θ which occurs with multiplicity exceeding p-1; this is overcome by replacing the solutions θ t , tθ t , t 2 θ t , ..., by the solutions θ t , (t 1 )θ t , (t 2 )θ t , .... The other main result deals with the number N of times a given element a ε F appears in a period of the sequence, and for a≠0, the result is of the form N≡0 (mod p ε where ε is an integer which depends upon f, but not upon the particular sequence in question. Several applications of the main results are given. Item Type: Thesis (Dissertation (Ph.D.)) Subject Keywords: (Mathematics) Degree Grantor: California Institute of Technology Division: Physics, Mathematics and Astronomy Major Option: Mathematics Thesis Availability: Public (worldwide access) Research Advisor(s): Hall, Marshall Thesis Committee: Unknown, Unknown Defense Date: 27 March 1967 Funders: Funding Agency Grant Number NSF UNSPECIFIED Record Number: CaltechETD:etd-10012002-154611 Persistent URL: https://resolver.caltech.edu/CaltechETD:etd-10012002-154611 DOI: 10.7907/1KMK-T118 Default Usage Policy: No commercial reproduction, distribution, display or performance rights in this work are provided. ID Code: 3856 Collection: CaltechTHESIS Deposited By: Imported from ETD-db Deposited On: 02 Oct 2002 Last Modified: 19 Mar 2024 21:08 Thesis Files Preview PDF (McEliece_rj_1967.pdf) - Final Version See Usage Policy. 2MB Repository Staff Only: item control page

LINEAR RECURRING SEQUENCES OVER FINITE FIELDS by Robert James McEliece In Partial Fulfillment of the Requirements For the Degree of Doctor of Philosophy California Institute of Technology Pasadena, California 1967 (Submitted March 27, 1967) ii ACKNOWLEDGMENTS It is a pleasure for me to take this opportunity to thank the people who have helped me in the preparation of this thesis. Iam indebted to Professor Ernst Selmer, whose lectures on linear “recurrences given at Cambridge University in 1965 stimulated my interest in the subject. Throughout my thesis research, I have received a constant supply of ideas and advice from Dr, Gustave Solomon, to whom I am especially grateful. Finally, I should like to thank my adviser, Professor Marshall Hall, Jr., not only for the help he has given me in the preparation of this thesis, but also for the active interest he has taken in my career ever since my under- graduate days. I owe him much more than I shall ever be able to repay. I should also like to thank the National Science Foundation for their kind financial support of my graduate study. ABSTRACT This thesis deals with the problem of how the elements from a finite field F of characteristic p are distributed among the various linear recurrent sequences with a given fixed characteristic polynomial fe F[x]. The first main result is a method of extending the so-called "classical method" for solving linear recurrences in terms of the roots of f. The main difficulty is that f might have a root 6 which occurs with multiplicity exceeding p-1; this is overcome by replacing the solutions at te’, t2 gt ..., by the solutions at, Cj yet, (5 yot ~». « The other main result deals with the number N of times a given element ac F appears in a period of the sequence, and for a # 0, the result is of the form N = 0 (mod p’), where ¢ is an integer which depends upon f, but not upon the particular sequence in question, Several applications of the main results are given, iv TABLE OF CONTENTS Chapter Title Page I INTRODUCTION 1 st PRELIMINARIES 4 TH THE "CLASSICAL METHOD" 9 IV A THEOREM ON SYMMETRIC FUNCTIONS 28 V A COMBINATORIAL APPROACH 37 REFERENCES + }) I. INTRODUCTION This thesis is concerned with the problem of how the elements from a finite field F_ are distributed among the various sequences which satisfy a fixed linear recurrence relation with characteristic | polynomial f(x). The space a(f) of all such sequences is viewed as a subspace of an e-dimensional vector space over Fy? where e is the exponent of f; this involves no loss since each sequence in 9(f) is periodic of period e. Chapter II presents the necessary preliminary material. Chapter II extends the so-called "classical method" for solving linear recurrences in fields of characteristic zero to the case of finite fields. Theorem 3.2 gives an explicit (if rather unwieldy) expression for the pth element Sy of a sequence which salisfies the piven recurrence in terms of the tth powers of the roots of f ina splitting field. Previous attempts [10,14] to extend the classical method have met with difficulty when a root of f occurred with a multiplicity which exceeded the characteristic of the field; theorem 3.2 overcomes the problem by replacing the powers i which occur in the classical solution by the binomial coefficients ( : ) (which are suitably defined for the field Fy) Also, theorem 3.2 makes heavy use of the fact that if 9 is a root of f, then sois 9 a. this reduces the complexity of the solution considerably, since there are fewer "independent" roots of f than its degree. Chapter Til concludes with two applications of the main theorem 3.2. If f is an irreducible polynomial in F_, and m is an integer, let prt. m < py, (p") The polynomial f is obtained by raising each of the coefficients of f to the ph th power, Theorem 3.3 gives a precise description of the \d space a(t™) in terms of the space ae” )y and extends an earlier result of Zierlcr [14] , who proved the result in the special case m = q*. Theorem 3,4 gives an upper bound on the number of distinct distributions of elements from Fy which may occur in (f), when f is irreducible, in terms of the number of irreducible factors of a certain polynomial xe 1, Chapter IV, some of which appears in [11], is a digression and contains an explicit (though again somewhat unwieldy) expression for the so-called "monomial" symmetric functions in terms of the power-sum symmetric functions, in a field of characteristic zero. The method used to obtain the result, given in theorem 4. 1, uses the method of Mbbius inversion on a certain lattice of partitions, and may be of independent interest. A careful analysis shows that theorem 4, 1 may be used to compute symmetric functions of roots of unity in a field of arbitrary characteristic; this fact, stated in theorem 4, 2, is used heavily in the proof of theorem 5,2, the main result of chapter V. Chapter V is an extension of some of the ideas in [11]; it presents a combinatorial- algebraic method which appears capable of completely solving the distribution problem in Q(f), at least in the case that f has no repeated roots in a splitting field. Unfortunately, the difficulties encountered in pushing the method beyond a certain point are so great that theorem 5, 2 is the best single result it has been possible to obtain. If N(s;a) represents the number of times a residue ae Fy occurs in a sequence se O(f), theorem 5.2 gives information of the type N(s;a) = O(mod p°) for a 4 0, and N(s;0) = e(mod p’). Here ¢ is an integer which depends upon the fewest number of roots of f which can be multiplied together to give 1. Theorem 5,2 isa substantial generalization of the well-known result that if p = 2 and (x - 1) ¥ f(x), then each sequence se (f) contains an even number of ones; this result was previously thought to be peculiar to the binary case; theorem 5, 2 shows that it is not. Theorem 5, 2 frequently gives enough information about the space a(f) so that it is possible to combine it with other information to obtain very precise information about the distributions which occur in a(f). This is illustrated by an example with p = 3, at the end of chapter vz. Ti, PRELIMINARIES Throughout, if F is a field and x an indeterminant, then we denote by F[x] and F(x), respectively, the ring of polynomials _ with coefficients from F, and the field of rational fractions. We shall only be dealing with finite fields F, = GF[q] with q = p, Pp a prime, and in this case it is possible to identify the field F&) with the set of all ultimately periodic Laurent series; i.e., the set . n n+1 . . . of all expressions of the form ax +a4x +-+se- in which n is an integer (positive, negative, or zero), a,¢ F, such that there exist integers r and t for which a, = aie for all i>t. (Intuitively, in this representation one obtains the Laurent series corresponding to a fraction p(x)/ q(x) by actually performing the division.) For details about this isomorphism, see [14]. If a and b represent either integers or polynomials in F[x], we write a|b to mean that a divides b, (a, b) for the greatest common divisor of a and b, and lem(a, b) for the least common multiple of a and b. Let aj, a9,-++,4,, a, #0, be n arbitrary elements from Fy We shall study sequences of elements s = (So, Sy) Sore. .) from Fy which satisfy the linear recurrence relation S,+a48 ,+°°° +48) forall t>n. (2. 1) It is clear from (2.1) that the sequence s is completely determined by its initial values s and it follows that g? Syeree? Spy there are q’ distinct sequences s which satisfy (2.1), Also, if s and s' are two sequences which satisfy (2.1), and a and b are elements of Fy the sequence as + bs' = (asp + bsg, as, + bs},... ) will also satisfy (2.1), so that the sct of all such scqucnccs may be viewed as a vector space of dimension n over Fy We associate the polynomial f(x) = x 4 ax? cee + an with the linear recurrence (2.1), and call f(x) the characteristic _ polynomial of the recurrence, The vector space of all sequence satisfying (2. 1) is denoted by a(t). For an arbitrary polynomial p(x) « F [x] such that p(0) 4 0, let us define the exponent of f as the least integer e such that £(x) | x°-1. Then a basic fact [10] about the space a(f) is Theorem 2,1: All sequences which satisfy (2.1) are periodic; i.e., for all t. for each se A(f), there ig an integer ¢ such that $= Si, Furthermore, if the characteristic polynomial f(x) has exponent e, then every sequence in A(f) has period e, and some have no shorter period. In view of theorem 2,1, it is natural to regard the sequences in a(f) as finite sequences of length e: s = (Sp; Sys eres Sg 1)» and the space a(f) itself as an n-dimensional subspace of the space of all possible e-tuples from Fi We shall call e the block length of a(f). One of the results we shall require is the theory of the factorization of the polynomial x° - 1 in F [x]. The results given below are implicit in the books by Albert [1] and Dickson [3], for example, but the point of view we wish to emphasize is sufficiently unusual to merit a somewhat detailed discussion, We will not, however, attempt to prove each statement made. In factoring x - 1, we assume with no loss of generality that (e,q) = 1, for if e=e,q with (e5, = 1, then x -1 2) = (x © 0 m - 1)1 . The splitting field for x°- 1 is GF[q'], where n is the least integer such that q” = 1(mod e). Lemma 2.1: iffe Pylsd has 6 asa rool in some splilling field, then 9” is also a root. In the field GF Cq’] , the roots of x” - 1 will be powers ofa primitive element 6 of multiplicative order e; i.e., the roots are 2 e-1 1, 6, @ 42.58 f will have as one of its roots some power of 9; let us say f(9%) = 0, By lemma 2.2, f£ will also have as roots the powers 9” ; banal m-1 oa » where m is the least integer such that . If £(x) is an irreducible factor of x° - 1, then 2 gua geees 8 m . . aq =£a(mode), Conversely, the elementary symmetric functions m-1 of the set (e%, 9% gr CF tq] over GF[q], which is generated by the automorphism q ) are fixed by the Galois group of ge ea 9 x - x“, so that the polynomial whose roots are (6%, gud eens jad * is in fact an element of Fix] . This polynomial is then an irreducible divisor of x° - 1 of degree m. f turns out to be of exponent e if and only if (q,e) = 1. In this way we see that the question of the number of irreducible factors of any degree of x” - 1 can be answered in an elementary fashion: given e and q, we permute the residues modulo e by the mapping k ~ kq (mod e). From the cycle structure of this permutation one reads off the number of irreducible factors of each degree. For example, let q= 3 and e = 20; the cycles are (0)(1, 3, 9, 7)(2, 6, 18, 14)(4, 12, 16, 8)(5, 15)(10)(11, 13, 19,17). Con- sequently eZ? - 1 has 7 irreducible factors in Fs; two of degree ‘one (these are naturally x+1 and x - 1) one of degree two, and four of degree four. The cycles (1,3,9,'7) and (11,13, 19,17) exhaust the residues prime to 20, and correspond to the two irreducibles of degree four and exponent 20. It is clear that, conversely, given an exponent e, the degree n of an irreducible factor of x° - 1 which is of exponent e is uniquely determined as the exponent to which q belongs modulo e, so that there are y(e)/n such factors. Finally, we present three miscellaneous elementary number- theoretic results which will be needed in the proof of theorem 5. 2, below. Suppose p is a prime, n an integer >1. We write n in its unique p-ary expansion, n= [f my? where 0 < nh. < DB; and of k>0 © course only finitely many of the n, are different from zero, Similarly m= 5 m ok k>o * Definitions: Wie) =the "p-ary weight" of n= © n,. If r is any k>0 — rational integer, write r= vt » = where (a, p) = (b,p) = 1. Then Db t= Mp (t). Theorem 2.2: (Legendre; see Dickson [ 3 ; chapter IX].) up!) =z (a-Wia)). Theorem 2,3: (Lucas; see Dickson [3 ; chapter IX],) (yz 0 CE) (mod). n mm k>0O0 kK Lemma 2,2: If R is a finite set of rationals, £ rz=S5S, then re R Hy) > min {u)(r): Ye R} . Proof: Obvious. Throughout, if x is a finite set |x| denotes the number of elements in x. If r is a real number, [r] = the greatest integer < Yr; i.e., [r] is the unique integer n which satisfies r- l1<n< _r, I, THE "CLASSICAL METHOD" Let f(x) = x” + a +++. +a, bea polynomial in F [x of degree n and exponent e. Let (f(x)) be the principal ideal in Fy [x] generated by f(x), and denote the quotient ring Fix 1/(£(s)) by Rp. Then f(x) will have a "root" 9 in RF i,e., an element of Ry with 9° = 1 and such that the powers 1, 6, 62, oeey gant are linearly independent over Fy With each element xe R; we shall associate an ordered generalized coset of the multiplicative sub- group T= {1, 8, 02 eees oe as follows: xX 3 {x, XO, ..0, xe°"*} =xT. (These are not cosets in the ordinary sense since there can be fewer than e distinct elements in xT; indeed, unless f(x) is irreducible, it will always be possible to find x # 0 with [xT] < e.) Viewing R, as an n-dimensional vector space over Fy we f choose a linear functional t of Re over Fy (That is, t is an ty onto Fy) With the aid of t, it is possible linear mapping from R f to a sequence of elements from Fy with each element xe Re: x - xT + (t(x), t(xe),..., t(xe° 4) = s(x). (3. 1) Theorem 3.1: The set of sequences (3.1) is identical with the solution space a(f). Remark: Theorem 3,1 is a very minor generalization of the "secondary f and a(f) given by Hall [5]. The only difference is that Hall proved theorem 3.1 for a particular linear isomorphism" between R functional t. 10 Proof of theorem 3.1: First let us show that for each xe Ry, the sequence s(x) given by (3. 1) satisfies the appropriate linear recurrence. In Re , £(6) = 0 and so n n _ 6 +a,6 tere tai =O. Multiplying this expression by a Xx and operating with t, we obtain n+k n+k- 1) t(x9 + a,t(e feee st a, t(x8") = which is the statement that s(x) satisfies the recurrence with characteristic polynomial f, Conversely, since [Re| = [a(f)| = q’, if we show that the sequences s(x) are all distinct we will have also shown that every sequence in a(f) must occur as s(x) for some xe R,. We therefore assume by way of contradiction that s(y) = s(z) for some y # z. we let x=y- z, s(x) = (0, 0, ..., 0) or equivalently t(x94) = 0, i=0, 1,..., e- 1. This means that the elements y; > xe? are all in the nullspace of t, which has dimension n - 1, so that the elements Yo: Vy s++> Vyiy ave linearly dependent; i.e. , for certain b. € FY, it is true that & b, Jim 0, so that x= b.e = 0, which contradicts the fact that the set fi, 8, 52, wee, gurl } is linearly independent. Hence s(y) = s(z) implies y = z and so the sequences s(x) are all distinct. This completes the proof of theorem 3, 1. Corollary 3.1: If f is an irreducible polynomial, then R, is isomorphic with the finite field GF[q"]. In this case for each s¢Q(f) it is possible to find an element xe GFE q'] such that for all t > 0, 11 s =x9' 4 x4g ty... 4 x4 gM t (3. 2) Proof: It is of course one of the fundamental facts about finite fields that FY C=1/@@) 2S GF[q’] when f is irreducible of degree n. _ The corollary follows from theorem 3.1 if we choose the linear functional t to be the trace of GFE q?} over GF[q]; i.e., for xe GF[q"], Tr(x) =x+x24.--. 4x04, (And in fact it is not difficult to prove that every linear functional t of GF [qa] over GF[q] may be written as t(x) = Tr(ax) for some ae GF[q"]; so that there is no loss in replacing t by Tr in this case.) n-1 Since by lemma 2.1, the roots of f are 8, 94, wee, 04 , (3. 2) is an expression for s, in terms of the th powers of the roots t of f; and in this way (3.2) resembles the classical method of representing s It is therefore possible to view theorem 3.lasa generalization of the classical method to the case of finite fields, in which the "roots" of f are thought of as lying in the ring Rp. In some sense, however, the most natural place Lo look for the roots of f is in the splitting field for f. In the pages to follow, a generalization of (3. 2) will be given for arbitrary polynomials f, in which the basic algebraic structure is indeed the splitting field for f. The price we shall have to pay for this is a great deal of increased complexity of the solution. The following discussion follows the classical method as given in Hall [6], as closely as possible, under the circumstances. With a sequence s = (So; Sy) Sos+s .) which satisfies a linear recurrence with characteristic polynomial f, and which is considered to be infinite even though we know it is periodic, we associate a formal power series; i,e., an element of Fy), as follows: 12 s ~ s(x) = y sx . (3. 3) k=0 s(x) is called the generating function for s. (No confusion should arise because the same symbol s(x) was used in theorem 3.1; the notation s(x) in (3.3) is only temporary and will be abandoned shortly.) We emphasize that the series s(x) is to be viewed as an element of F &), and that it is meaningless to ask questions about the "convergence" of (3.3). (3.3) gives a representation of s(x) as a Laurent series; our first step will be to express s(x) as a corresponding rational fraction, Define f*(x) = ax +a ae ++s+ +1, so that £*(x) = x4( 2 ). Now let us form the Cauchy product of s(x) and £*(x) in F yo): e k sx)t(x)= Y x® Y as ay=1. (3. 4) k=0 j=0 a. = 0, k2n, For k > n, the coefficient of x in (3.4) vanishes because of the recurrence relation Ss, +a.,S +eeor +as t 1-t-1 n t-n? so that s(x)f*(x) = c(x) , (3. 5) 13 with c(x) a polynomia! of degree < n-1 in #YCx]. (3. 5) is the required expression for s(x) as a rational fraction. We suppose that f(x) has the following factorization into irreducible factors in ql *1 m mM f(x) - 1 &) *, (3.6) k=1 where degree (f,) = d. and so n= Edm It follows from (3.6) and the definition of £* that k (x) = 1 e+e) k=1 Then according to a generalized version of "partial fraction" decomposition [12, p.88], we may use (3.5) to express s(x) uniquely in the following way: m s(x) = y a? k=1 (f(x) * (x) “Ke (3, 7) where each polynomial c, (x) is of degree < d,m,,. Let us examine more closely expressions of the form c(x) 8 Gy 14 where f(x) is irreducible over F_ and degree (c(x)) < mn, n= degree (f).. If K is a splitting field for f, then | K:F| =a, and if @ is one root of f, then by lemma 2.1, the other roots 2 n-1 are et, g 4 rh We assume that f has exponent e, so that @ will have multiplicative order e. In the field K(x), f(x) ‘factors completely as a product of linear factors, and so also does f*, so that it is possible to further decompose o(x) into partial fractions in K(x), as follows: a n- m o (x) = 2 ) he (3. 8) where the O15 are uniquely determined elements of K, The field K(x) admits an automorphism A which is induced by the auto- morphism A*: y - yt of K itself; i.e., if an element p(x) « K(x) has the rational fraction representation i ua,x p (x) = > zb; x! then na, tx ab, x Clearly the fixed field of A is F&), and since o(x) Fi), it follows from (8. 8) that 15 n-1 m q kil, k=0 j=1 and since the coefficients in (3.8) are unique, we sce that Me 57 on ; ‘ ? oo? _ (Subscripts reduced modulo n if necessary.) Therefore there are m k elements from K, say a4, do, +++, 0), such that a jog , so that k, j n-1 m a(x)= ) Yat /(t- ot a, (3, 9) k=0 j=1 We pause for a brief degression. Consider the fraction (1 + ax)” as an element of F g > ae Fy. We wish to find the Laurent series corresponding to (1 + ax)"™ , and of course the natural thing to do is use the binomial theorem (1+ ax) ™ =r (- k my, x . k>0 | This is in fact valid, but one has to exercise a certain amount of care in defining the "binomial coefficients" (> k ). The most natural way of defining them from our point of view is by way of the recursion (. y=(™ i+ (nt ), along with the boundary conditions ( p j=l ( 0 ny) = (0 n : =1 for n# 0. (Of course these binomial coefficients are the usual ones reduced modulo p, the characteristic of FY) The recursive definition allows the usual proof of the binomial theorem to be applied - one uses induction on m, and in Fy) there are no convergence problems to complicate the situation. Thus let us expand the term (1 - gd x) which occurs in (3. 9) by the binomial theorem: 16 k : k a-eta I= (CD Ct»! t> 0 k ) PPE a . (3. 10) t>0- Combining (3. 9) and (3. 10) we obtain the following Laurent series for o(x): : rs - j+t-1 gS qt o)= Fox Yo oy CMP) od ofS. Lad t j t>0O k=O jql (3. 11) The coefficient of x in (8.11) may be written as n-1 m k YL {Phat k=0 j=l Tr {(F4y 1) ae} = Tr{o or a}. (3, 12) it 1B n-1 where as before Tr(x) = x + x4 ee txt in GF[q']. It is pussible to pul (3,12) into slightly more palatable form as follows: the identity (3) = ae Ny) 17 means that -1 m-1 m t+j _ », (Ga; =) j=0 j=0 a; (4) G) i m-1 “7 G)Y a= ) Gy» i j=0 i where Y= a. ( : ). Consequently the coefficient of x in (3.11) may be written as m-1 s,- Tr{e y (i)y,}. (3, 13) jr0 (3. 13) represents the general term of the sequence g = (So; Sq sees Sy. .--) Of ar), where f is irreducible, In the classical case, the expression (3.13) would be replaced by n m-1l _ v j,t S,= ), > ait Oy (3. 14) k=1 j=0 In 3,14, the elements 6, are the distinct roots of f; the fact that the roots of f in the case under consideration are all powers of a single one is reflected in the fact that the outer sum in (3. 14) is replaced by the trace in (3.13). The really crucial difference between 18 the two expressions, however, is that the powers J in (3,14) have been replaced by what we might call the "binomial functions" ( ; ) in (3.13). The essential reason why no expression of the form (3. 14) can represent every se O(f) is that the set of functions {1, t, i we te 4} may fail to be independent in Fy so that - the dimension of the space of all sequences of the form (3. 14) will be less than the dimension of the space a(e™), (For example tP=t in GF q’] .) However, the binomial functions ( ) are independent over any field? for let us take 6 = 1 in (8.13). Then f(x) = x - 1, and if there were a linear dependence among the t m-1 from Fy then the space of all sequences of the form (3, 13) would binomial functions (6 ), (5 ), + ), woe, ( ) with coefficients have dimension strictly less than m; but we have proved that every sequence in a(f'™) is of the form (3. 13), so no linear dependence is possible. (Of course a linear dependence in a larger field implies a linear dependence in F po) Let us extend (3.13) to the more general case where f(x) has the factorization given by (3.6). It is clear how to proceed, since at the carlicst stage (8.7), s(x) was decomposed into partial fractions whose denominators were irreducible powers. We simply observe that in a splitting field for f(x), say GF q*] , d=lce.m. (d,, dy, eee di? it is always possible to find a primitive element § of multiplicative order e' = 1.c.m. (e,, Cor sees en where e, is the exponent of fs, and integers by, bo, wees Dw such that 1 Although the fact shall not concern us here, it is possible to extend the classical method to arbitrary (not necessarily finite) fields of characteristic p. Naturally we could in general lose the fact that the roots are powers of each other, but the binomial functions would enable us to handle multiple roots with no difficulty. 19 b, d. 9 * is a root of f, in GF[q , Combining these remarks with the expressions (3, 7) and (3.13), we obtain m m. Theorem 3.2: Let fe F gl *! have the factorization f(x) = 1 (£,.()) k k=1 3 _ with each i. irreducible of degree d,. Then if GF ao] is a splitting field for f, there is a orimitive element 6 ¢ GF[ q@ ] and by integers b,, by, ..., 6, such that £ (8 ke 0. Furthermore, for any sequence se Q(f) it is possible to find elements oe e GF[q 7] i=1,2,..., m j=0,1,..., m, ~ 1 such that for each t = 0, m.-1 Tv m@sgit y (ty, _ Gi); , i > ty fi sy ) trv {e* ) G)yy"}, i=1 j=0 (i) qi where Tr” is the trace on GF[q "] over By i.e., d.-1 tr) =x4+xt4...4 x7 ° We emphasize once more that theorem 3. 2 is most valuable when f(x) has multiple roots; indeed, results essentially equivalent to theorem 3,2 are known when f is squarefree [8], or if f', the formal derivative of f, is squarefree [14]. As an application of some of these ideas, let us return to the case of a power of an irreducible polynomial f(x) of degree n, exponent e, Our goal is to give a relationship between the solution spaces a(f") and a(f). In view of (3.13), it will plainly be helpful to know the properties of the sequence (r Py whose general term is r= (t ) for a fixed integer r. In this case the generating function for “e) is 20 pts)= SY (ata Y (TH )st / r t> 0 t>0 r t,-(r+1), ¢ x" t>0 (1-x) If the sequence (r,) is to be periodic of period n, it must be true that (1-x)?*4 | (1-x"), since the Laurent series corresponding to 1/ (1-x") is 1+x” + xn +e«e. , Suppose therefore that n = Doe with (np; p)=1. Then f f nop f f (n, - Dp 1-x%=1- x? =(1- x? ya x2? a ..c4x © e where Q(1) = No #0, so that (1 - x)Ptt 1- x" if and only if r+l1l<¢ py’. Therefore the sequence (r,) of binomial coefficients is periodic of period vp’, where e is the least integer such that r+le Pp’, and (r,) is not periodic for any smaller value. We wish to apply the preceding remarks to formula (3. 13), which involves the binomial coefficients ( 5 ), ¢ ‘ ), vee, ( mane Hence if uy is the unique integer which satisfies pti <m<p", then each of the binomial coefficients will be constant on residue classes (mod p”), Let b= pe. We perform an operation, called decimation by b, on a sequence defined by (3,13), as follows: define b new 21 sequences (s,”) i=1, 2, ..., b: (i) _ ST Shai? i,e,, the sequence (s, ) is formed from (s)) by taking only those terms whose subscripts lie in the residue class containing i (mod b). Then from (3. 13), . . m-1 2 2, = ox foiiePyt y (Pedy, j=0 = Tr {eo ) Gy} since we have seen that ( ans T) = ( ; ) in F p (Of course the above calculations are performed in GF[q"], a splitting field for £(x). ) Continuing, m-1 (i) _ i, , byt . _ i s. = Tr{e6,(e)}, with 8, = y (ys: (3, 15) j=0 Formula (3. 15) resembles the formula for a sequence from a(f), with one exception: the root 6 is replaced by 3? in (8. 15). But this anomaly is easily understood: in GF[q"] , the minimum polynomial for 9? is (P) the polynomial formed from f by raising each coefficient of f to the b'’ power. (Recall b= p" so that $6) (9 >y = (t(9))” = 0.) Hence (3.15) represents a sequence from 22 ae) ), rathor than one from a(£) itsclf. (Of course if q- p' and rly, f= s(P) .) Thus according to the definition of the sequences (i) t , the sequence st e a(f™) is formed by interleaving certain sequences from ate), But it does not follow that given any Ss collection of b sequences from ae ) it is possible to interleave . them and obtain a sequence from a(e™). Indeed, there are gt sequences which may be formed by interleaving sequences from oe), but only q”™ sequences in a(f™), We shall now derive a relationship among the field elements B, which appear in (3. 15) which is both necessary and sufficient to ensure that the sequences (i) may be interleaved to be obtained a sequence, viz, St 5 (-1)8(T) a p20 20. (3, 16) For proof we present the following calculations, For simplicity we omit limits of summation, it being understood that undefined summands are all zero: ' k 7 k k ¥ GD) (i) P* CAP CRICS v5 by (8.15) Ky] =F COORG y= Y CMECP GEG; - i,j,k i,j,k The sum on k is 23 Yoos ey - Fen (mM) - ne: ‘) k =(1- 1/120 fori<m, Thus the B,'s themselves satisfy a linear recurrence relation (3.16) with characteristic polynomial (x - 1)™, Conversely, given any set of 6's which satisfy (3.16), it is possible to recover the Y's and obtain an element of a(e™) by interlacing the corre- sponding 5 Mrs, This can be done by inverting the formula (8. 15) for the 8's, but an easier way is to observe that there are qa possible selections for the 8's subject to (3.16), and this is precisely the number of elements in a(t™). We summarize these results in a theorem: | Theorem 3.3: If f(x) is irreducible of degree n, then every sequence in a) may be obtained by "interleaving" b sequences from Q (¢)), Here b= p" is the unique power of p such that w-d (i) p i= 1, 2, ..., b which correspond to the elements 9° B; in GF[q" 7 (with f(@) = 0) in the isomorphism hetween ace b), and CFE J <m< pM . Furthermore, a set of b Sequences S, may be interleaved to form a sequence from a(f™) if and only if the sequence (Bo, Bases .) satisfies the linear recurrence over GF[ qo ] whose characteristic polynomial is (x - 1), Theorem 3,3 is known in the special case that m = q° for some integer c [14, lemma 12]. Of course in this case °°) =f and b= m, so that there is no relation imposed upon the B'S. 24 We present another application of theorem 3.2 which involves the nation of decimation and is of interest. We assume for the following discussion that f(x) is an irreducible polynomial of degree n in FY tx; and that f belongs to exponent e, eE = q: - i, It frequently happens that one is interested only in knowing the way in which the residue from Fy are distributed among the various sequences in Q(f{). From this point of view, a complete knowledge of a(f) will consist of a list of distributions which occur in n(f), along with their multiplicities; in such a case there will of course be no need to distinguish between a sequence s = (Sp; S4a,e0-, S,_) and one of its translates, say (s,, Supe oets So_42 Sop aes S,_ ao We therefore (ignoring the all- zero sequence) view ©(f) not as a collection of q’-1 sequences, but rather as a collection of (q?- 1)/e = E cycles. (A cycle is nothing but a sequence whose starting point is considered irrelevant.) It is well known [10] that when f is irreducible, no sequence from (f) except the all-zero sequence has a period which is shorter than e, so that for each sequence s, all of its e translates are distinct. In terms of the isomorphism provided by corollary 3.1, this point of view amounts to regarding two elements of R= GFT q’] as indistinguishable if they are in the same coset of the subgroup T = {1, 05 64, sees eet}, The question about the distributions which occur in a(f) can be rephrased as follows: "How are the values of the trace distributed among (3. 17) the cosets of T?" We shall be able to simplify question (3. 17) somewhat by exhibiting a trace-preserving automorphism of GF[ q’] which permutes the cosets of T; viz, the automorphism q: x7 xf, To 25 show that this automorphism does in fact permute the cosets, suppose that xy = 9° for some r;i.e., that x and y are in the same coset of T, Then x%y%= (xy ta =e eT, Therefore the set X of cosets of T admits a cyclic permutation group A= {1, dy eee, Oo *y . Clearly two cosets in the same orbit . of X under A will have the same distribution of trace values, since Tr(x) = Tr(x%), Theorem 3,4: The number of orbits of X under the action of A is the same as the number of irreducible factors of xE_y in FYtx] . Proof: Choose 4 as a primitive root for GF[q"] such that 6 = y*, so that T = {1, a, oe oeey ye DEy It is clear that the coset of T to which an element 4° belongs is determined by the value of s modulo E, Thus if x= y® is taken as a coset representative of Tx, the successive images of Tx under a are Tu, Ty ea eee, so that the number of cosets in the orbit of Tx is the least integer m such that sq = s (mod E). But the process of mapping the q is exactly the process residues modulo E into themselves by x- x described in chapter 1 for determining the number of irreducible factors of 4, This proves theorem 3. 4. Corollary 3,2: The number of distinct distributions which occur in af) is less than or equal to the number of irreducible factors of xe o4, Corollary 3.2 is sometimes very accurate in giving the number of distributions in o(f), but usually not. It is possible, however, to formulate an amusing converse to corollary 3.2 which 26 will provide us with a large number of polynomials for which the bound is quite good. Theorem 3.5: For any integer E such that (E,q)=1, there are infinitely many irreducible polynomials i with degrees n, and t _ exponents C, such that e,E = q ‘1, Proof: Suppose » is the exponent to which q belongs modulo E, For each t > 1, let e, = é (q?t. 1). As pointed out in chapter I, for each exponent e prime to q, there is at least one polynomial f of exponent e, and the degree of f is the exponent to which q belongs modulo e. For each t, we let i be one such polynomial (i.e., with exponent e,) , and we shall show that with the possible exception of t= 1, each i, has degree n, = ot. Since g?t = 1 (mod B), it follows that n,| yt. But since n ot. _ (g Lys -~p. acl n it follows that Chas 1)/(q to 1) must be a divisor of E and therefore < E, Butfor t> 2, and n< et, et pt-n 5 —t sq ts q*%aq?>e, a contradiction. (For t= 1, there may or may not be an exception. This is illustrated by q = 2, E = 5 in which case t= 1 is exceptional, 27 and E = 11 for which t = 1 is not exceptional.) This completes the proof of theorem 3.5, Corollary 3.2 gives most information when E is such that xed has few factors; an especially interesting case is when x-1 has only the two irreducible factors x - 1 and gl, fe tees +x+1; it follows from the remarks in chapter 1 that this will be the case if and only if E is a prime for which q is a primitive root; so that with the aid of theorem 3.5 and a list of the primes for which q is a primitive root it is possible to find a very large number of irreducible polynomials f such that a(f) contains only two (non-zero) distinct distributions, In these cases it is usually possible to determine the distributions exactly; for an example see the end of chapter IV. 28 IV. A THEOREM ON SYMMETRIC FUNCTIONS This chapter does not deal directly with linear recurrence relations but presents certain results which will be needed in chapter V. Some of these results appear in [11]. Consider the algebra of all symmetric "polynomials" in a countably infinite set of variables Xy2 Xoo eee, with coefficients in afield F. Of course by "polynomial" we mean merely that the functions in question are formal sums of monomials x x see x ; Such functions, being symmetric, must all have infinitely many terms. We shall frequently make statements such as "the symmetric function of (yy) Yoo se. vn" This should be interpreted to mean "the symmetric function of (x,, Xoo += .) with the substitution X= Vyo cers HF Vy By * Sg 7° F o"" if A, is the space of all symmetric polynomials which arc homogeneous of degree n, then it is known that a basis for A, will be formed by the monomial symmetric functions k, defined by hq oA X 1. °2 r sym where 2 = (14, X49, «++, 4,) is any partition of the integer n (i.e., the ,’s are positive integers and hy tere t0,F n), and by the usual convention, the sum on the right-hand side of (4.1) is taken over all distinct monomials which can be obtained from the one actually written by permutations of the variables (x, Ko, se. ). When no confusion will arise, the abbreviation ''sym" on symmetric 29 sums of the form (4.1) will be omitted. As an example, let n= 6 and } = (4, 2, 2). The symmetric function k, of the variables Ky» Xo, Xq, Xy4 is given by _ 422 422 422 k= [4, 2, 2] = X Xy Xq t+ Ky Ky Xy + Xy Xy Xy at eat tia xh 22 Xo Xy Xg + Xy Xy Xq F Xp Xy Ry 3 *4 *g + *3 %1 %4 t+ ¥3 *2 %4 atti xt tte xt gt? Xq Xy Xo + Xq Ky Xy F M4 Ry Xs - If repetitions occur among the integers har hor cers it is customary to write r=(1 +2 73 9...) (4. 2) which means that the partition }, involves m, ones, My twos, etc. Thus we write (22 4) in place of (4, 2, 2). Besides the Kk, 's, there are several other important bases for AL} we present here only the two which will concern us in the applications: (1). The elementary symmetric functions a, are the functions [1°]; i.e. » 2, 72 4X9 °°* X,- For a partition = Ory hos ...) of n write a, = oo a *+e . The fact that the a. form a basis for AL is called the Fundamental Theorem on Symmetric Functions. [12, p. 78]. 30 (2). The power sum symmetric functions s m @re the functions [m]; ie, 8 = 2 x,» For a partition 1 = (ays Xo» ee @ of i = eee e T e f il i s , rn) n write s, a oe SO he functions " form a basis for A, whenever F has characteristic zero. The important difference between the bases {a, } and {s, } of A, when F has characteristic zero is that the {a, } form an integral basis for A, relative to the basis {k, }, while the {s, } donot. Thus a symmetric function which has integral coefficients when expressed in terms of the k 's will also have integral coefficients when expressed in terms of the a, 's, but this will not necessarily be the case when the function is expressed in terms of the Ss. 's. Itis for this reason that the Ss, 's cannot form a basis for A, when F has characteristic p > 0; indeed Ss} = s, in such a field, so that the set {s, } is not linearly independent. 1 The aim of this chapter is to express the functions k in terms of the functions 5.5 in the case that F has characteristic zero, Surprisingly, it will be possible to apply this result under certain special circumstances to fields of prime characteristic. Let us fix } and n for the rest of the chapter, with 1 = (Kgs dos +++, 4.) and with multiplicities m, as given in (4. 2). We define a new function hy of the variables (x,, .) as follows: i What is not difficult to show is that when the field F has characteristic p, the dimension of the subspace of A, spanned by {s ,} is exactly the number of partitions of n in ” which each summand is < p- 1, 31 Xx x X 1 = (1m, !)k, = y. Xy Ky see x”, (4, 3) i sym (*) By where the summation "sym(*)" is extended over all r! monomials - obtainable from the one actually written by permutations of the variables (1, 2, ..., r). Of course (4.3) follows since each distinct monomial appearing in the sum kK. occurs iim, ! times in the sum h, Another way to look at (4. 3) is to regard the integers (X45 hoe - an ) to be formally distinct; perhaps one gould “label!! two identical integers with subscripts. For example (2? 4) becomes (2, , Zo, 4). From this point of view the function hy is no different A from ks since now every monomial x; 1, x, x2, x AT is distinguisha- 1 2 r ble from every other. Now consider the set P. of all partitions of the set i = 1, yo hor cee rats regarding the A, asa set of formally distinct symbols, (It will always be clear whether we are viewing X as a collection of integers or as a set of symbols, so that we need not formally distinguish these logical differences.) A partition rr of the set P " is a way to write P, as a disjoint union of subsets B,, called blocks: with B.n B = @ if i# j and B.. # @ for all k, 4 is called the length of the partition r. 32 It is possible to introduce a partial order ">" on P. in such a way that P. becomes a lattice: if + and m' are both partitions of }, write 7 > m' if and only if every block of m is a subset of some block of T's i.eg, n> if mn is a refinement of m', It is easy to show [9] that under this partial ordering, P, - becomes a lattice with top element (maximal with respect to >) t, where t is the partition {a i} fh attr {n ar With each element n ¢ P. » given by (4.4), we recall that the elements of , are really integers and define, for each k = 1, 2, 22,4 8, = y. hae | (4. 5) We now associate with r two symmetric polynomials in (x,; Xo, + .}; they are f(n) =h and g(t) =h h «eh where 8 = (8, ; Bos «++, B . is the partition of n given by (4.5), and the functions h are given by (4.3). For example, if n= {Ryo Rgp Age Rgy Ash and om is {dys gs Agf {Ag Ag} [Ag f> then f(r) =h h h and yt het dg ho + he Ag’ g(r) =h . Ay t Ag + Age Ag + Ags Ag The following lemma is the crux of the matter: 33 Lemma 4,1: f(r)= ) g(r’) a'<mt Proof: By definition, B , B 8 Hm) = (J xy MS ay?) (Yay), where the sums are symmetric by the convention (4,1), We expand this as By By £(m) = Li, i, coe x,“ , (4. 6) 4 and this sum is extended over all possible monomials obtainable by selection of 2 of the variables x,, xX, ... . We do not require that the subscripts iy, in eoey i t be distinct. Let B= {B,, Bo, ones Bt, and to each monomial which occurs in the summation (4. 6) we assign a partition of B as follows: B. and B, are to be in the same block of the partition if and only if i, = ie We call two such monomials equivalent if they induce the same partition of B. Now to each equivalence class of monomials there corresponds in a natural way a partition rr' ¢ P. with n' <7; i.e., to a partition of B suchas {Pip Pig? vee \ 134 Pig’ _ -}. .- Y Bi, ve -| {B, U B, Ueee \ «++ , It is clear that the sum of the monomials 1 2 of (4.6) which belong to a fixed equivalence class is a g(n') for some we associate the following partition of ): {B, 34 a'<t, and conversely, given any 1'<7 there is an equivalence class corresponding to 7' which contributes g(r') to (4.6). This completes the proof of lemma 4, 1. . In view of lemma 4,1, it is now possible to apply MUbius inversion on the lattice Py in order to calculate the functions g(r): gn) = udm i(n") (4.7) t'<t where u(r‘) is the MUbius function associated with P. (For details about MU&bius inversion on a lattice, see [9].) In particular, we apply (4.7) with 7 =t, the top element of P, and obtain h=et)= YS alr)t(n)- | (4. 8) me P (4, 8) is almost an explicit expression for hy in terms of the power- sum functions f(r); all that lacks is the function u(1) for the lattice. Fortunately this function has already been calculated [9]; if the partition nm is given by (4.4), and if | B,, | = b, > 0, then & u(r) = Ca)” ye (4. 9) We combine these results in a theorem: my ™o Theorem 4,1: If , = (1 2 ee ) is a partition of n, then ina field F of characteristic zero, 35 Keep YS ulm itt) } omm.! o t eP TEN with the MUbius function yp given by (4. 9). The cases r=1 and r = 2 of theorem 4.1 appear in - MacMahon [7, p. 7], where, however, he dismisses the results with the remark 'In actual practice there are easier ways of calculating the many-part [monomial symmetric] functions and the general formula is of little importance, " With the aid of theorem 4,1 it is possible to compute the functions Kk, in the special case that the x, (i= 1, 2, ..., m) are the e always that F is of characteristic zero. In this case we know that roots of unity in F, and a re ee ii 0, remembering the functions Sn are all zero, unless m= 0 (mod e), in which case Si = & When applying theorem 4.1, therefore we need only include those partitions 7 e¢ Po whose associated numbers B. given by (4.5) are all multiples of e. We denote that subset of PY by P ° and so for the eth roots of unity theorem 4, 1 becomes ke aT y. wine") (4, 10) me P © i r where 2(r) is the length of the partition 7. In particular we see that k, = 0 unless e| Oy trgts vet his but it is not difficult to show this directly. | Finally we discuss the possibility of relaxing the assumption that F has characteristic zero, at least for the application (4. 10). 36 Although we have chosen to expand ao in terms of the functions Ss. it is nevertheless also possible to expand it in terms of the functions a.» at least in theory. Since the functions a. form an integral basis for the space A); such an expansion will have the form kK. = ), C a (4. 11) a where the summation is extended over all partitions of the integer n, and each cy is an integer (possibly negative or zero.) Further- more (4.11) is a polynomial identity, and so it is valid over any field, although naturally in a field of characteristic p > 0 one would reciuce the coefficients c, modulo p. If the variables x, are the e” roots of unity, the statement ''the elementary symmetric functions a, are all zero except that a, = (- et " is true in any field, so that in order to calculate the functions kK of the eth roots of unity we necd only insert the valucs of the appropriate a, (which do not depend on the field) into (4.11) and reduce the resulting expression modulo the characteristic of the field. But it is equally possible to find the value of (4,11) by using (4.10). Therefore it is possible to compute the Kk, in any field by using (4. 10): Theorem 4,2: Let F be a field of characteristic p> 0. In order th to compute the symmetric function Kk of the e” roots of unity in F, it is sufficient to compute the same function in the rational field and reduce the resulting expression modulo p, A careful application of (4.10), which is permissible because of theorem 4. 2, will allow us to prove the main theorem of chapter V. 37 V. A COMBINATORIAL APPROACH Throughout this chapter F = F p will be a finite prime field. Let V = V(F) be on e-dimensional vector space over F whose elements are the e-tuples v = (vo; Vv V _y with entries from id eee 3 F, For each ac F, we define a function N(v;a):N(v;a) is the number of times the element a occurs as a component for v. The function ee ee N(v;a) is not easily studied; let us instead write it in its formal p- ary expansion: N(v;a) = )) N,(v3a)p™ . (5. 1) k> 0 Thus N KY) a) represents the qth digit in the p-ary expansion of the number of a's which appear as coordinates for v. The advantage of expanding N(v;a) as in (5. 1) is that it is possible to view the functions N,(v3a) as mappings from V into F by regarding an integer between 0 and p- 1 as an element in the field F, Further- more, since F is finite each function N 1 V3 a) is in fact a polynomial in the coordinates (vo; Var tees Vo. p “ro prove this one could use an interpolation argument.) Also the function N, is clearly invariant under permutations of the coordinates of v, so that it is in fact a symmetric polynomial. We need not appeal to these abstract considerations, however, because of Theorem 5.1: NA; a)=a x (tr (vp -a)P"*, 1 1- (vy -a)P- a sees p* i- (ve 1" 1)?" 1 38 Proof: The abbreviation on the right-hand side of the equation is to represent the symmetric function a k of the variables - p y;= 1-(v,-a)? 1 i= 0, 1,..., e-1. Notice that the y, have the property that y3= 1 if v, =a, and y; = 0 otherwise. Theorem 5.1 is a consequence of Lucas’ theorem 2,3: in theorem 2,3 take m= p*. We obtain that ny, = ( -) (mod p). Hence N, (3a) = (NG: a)) p ) p (mod p), so that if we apply a x 10 the variables Yo, Yy, +++5 Voy) we get a contribution of 1 for each subset of order p* from (Yo: Vyr eee Voy) which has the form (1, 1, ..., 1). This completes the proof of theorem 5.1. Theorem 5.1 shows not only that N, polynomial, but also that it has degree p*(p- 1). Hence according is a symmetric to the fundamental theorem on symmetric functions it is possible to express N,.(v3 a) as a polynomial with integral coefficients in the symmetric functions a: N,(v3a) = ). ca, (5. 2) » where the summation is extended over all partitions of all integers < p*(p-1), and the c, The object of this chapter is to apply theorem 3,2, together are integers. with (5, 2), in order to obtain information about the functions N,. We shall depend heavily on the results of chapter IV. Let f(x) be a polynomial FLX] which has no repeated roots in a splitting field; f(x) = £, @)f, (x) eee fae with the f, distinct and irreducible. If 6 is a root of f(x) ina splitting field 39 F*, and if i. has degree nj and exponent e,, we may assume that F* = GF[p"] where n=lem. (ny, Ng, sees ns and that 9 is a primitive eo”) poot of unity with e = le.m. (e,, Co, o20, © mm" If g,= e/e., e then it may é also be assumed that ¢ 2 isa primitive e; root of unity in GF[p 7 and f. (0° = 0 = We apply theorem 3. 2 to the polynomial f; it tells us that for any sequence (s,) e 2 (f), it is possible to write the general term as m t - (i) , a °t S, = ) Tr (x, 8 ), | (5. 3) i=1 : a. where pr) is the trace of GF[p 1 over GF[p] and the x, are suitably chosen elements of the corresponding fields Grr pty. Let us expand (5. 3) by using the algebraic form for the trace: n.-1 i tr (x) = x+ xP. 4 xP n.-1 _ gj y FY & ey P. (5.4) i j= We regard the expression (5, 4) as a polynomial in ef, say S, = P(e), where n.-1 m i P@)= SY YY &e “HP Sco. (5.5) i=1 j=0 ke K 40 In (5.5), the set K is the set of integers k which the coefficient of x in P() is formally different from zero. It is clear from (5.5) that the set K is precisely the set { gp’: i=1, 2,...,m; j=0,1,..., n,-1}. The integers g.p" are all distinct since f is assumed to have no repeated roots, and | ep cet P __p so the coefficient of o in (5. 5) is x, (There is nothing new about regarding (5. 4) as a polynomial in woe in the case that f is squarefree; the idea is due to Mattson and Solomon [8]. The point to be emphasized is that the only case when theorem 3.2 yields such a polynomial is when f is squarefree, on account of the presence of the nonconstant binomial coefficients ( ; ) when f has a repeated factor. ) Using the polynomial P of (5.5) it is possible to express an element (s,) e Q(f) in the following form: s = (P(e°), P34), ..., P(e) ). We wish to compute the functions N,.(v3.a) for each ve aff), with a(f) regarded as a subspace V(F). To do this, we must apply theorem 5,1 along with expression (5,2), and compute the various functions a,(P(¢), P(e"), ..., P(e") ). This function is a= J Pp(sl---Pik)= Soa Y gle 6.6) r sym sym j=1keK We shift our emphasis and regard (5. 6) not as a polynomial in the single variable 4, but rather as a polynomial in the C,,'S. 41 From this point of view (5.6) is a linear combination of monomials GG st Oe To simplify the notation we replace ry by 6:3 “1 "2 r J then the coefficient of c, ¢, +++ ¢, in (5.6) is clearly 1 "2 a k, k k 12 r J 8 8% 8.4 » 80 that sym a, = y. kK, cy (5.7 (a) where the summation (.) is extended over all unordered collections A= (k,, Ky, eee, k of integers from K, c, is short for “14 Pky eee °K and k, is the monomial symmetric function of the variables Bo» 4s -00s Oa 4 (5. 7) is why the results of chapter IV will be needed; for the k. in (5.7) are the symmetric functions of the 9 ? which are the eth roots of unity in GF[ p° 1, so that theorem 4,2 will apply. As we remarked after (4.10), the functions Kk, are all zero unless Kk, + Ky eee + k. = 0 (mode). This leads us to the concept of the K-weight of an integer: Definitions: If K is a set of positive integers, and if a> 0 is an integer, we define the K-weight of a, written Wa), as the smallest integer s for which it is possible to write a= k, +k, +-:- +k, with each k,¢ K, (For example if K = {1, p, p’, eae i it is clear that W,,(a) = Wil) as defined in chapter IL.) Also define w,,(a) = min W_-(na); ice., w,-(a) is the least K n>1 K K integer s for which it is possible to write ky + Ky teee + Kk. = 0 (mod a). 42 It is now possible to state the main theorem of this chapter. Theorem 5.2: Let f(x) = £, ()£,&) see fn be a squarefree polynomial in F(x] , and let the set K be as defined by (5. 5). If w= Wyle), with e the exponent of f, and ¢« = [ orl Then for all se aff), N(s;a)s 0 (mod p*) for a #0, and N(s;0) = e (mod p*). Proof: Since the proof is rather lengthy, perhaps a brief sketch is in order. The idea is to apply (4. 10) to evaluate the functions Kk, which appear in (5.7), and to show that each k, is zero when- ever r is "sufficiently small" relative to w. This is the difficult part of the proof and is labelled lemma 5.2. The vanishing of the k n will in turn imply the vanishing of enough of the a x which appear in (5. 2) to force each of the polynomials N,v; a) to be zero for 1l< k<ec, and a#0,. The statement about N(s;0) follows auto- matically since = N(v;a) =e. a Lemma 5,1: If K is the set given by (5.5), and if m,k, + mok, +++ = 0 (mode), for integers m, and elements k e K, then Proof: We replace each integer m,; by its p-ary expansion as a sum of W y(n) powers of p and for each summand m,k, obtain an expression of the form 43 a a p k,+p 7k ++ . (5. 8) . n. We recall that each ke K is of the form gp’, and since g,P t = g; (mod e) by definition, we may replace each term in (5,8) by a bona fide element of K without destroying the fact that the sum is = 0 (mode). Hence starting with the expression 5 m,k, = 0 (mod e) we obtain a sum of £ W,(m,) elements of K with the same property. But we have defined Wxle) as the smallest possible number of elements with this property. Thus 5 W (m4) > ple), as asserted, Lemma 5,2: If W ye) > 1+ (p- 1)log, (r), then any monomial symmetric function Kk, k= 2 8g yoo By must vanish, provided that the FF = 9 are the eth roots of unity over Bo and the k are chosen from the set K. Proof: The plan is to show that under the given conditions, the rational integer given by (4.10) is divisible by p. It is however not the case that each summand o of (4,10) has Lo) > 1, which would be sufficient for our purposes in view of lemma 2.2, It will be necessary first to combine certain of the terms of (4. 10) to obtain the result. Let us first observe that since f is squarefree, (e,p) = 1, go that the terms e”'T) in (4,10) may be disregarded in a discussion of divisibility by p. 44 A typical partition tr ¢« n° which appears in the sum (4.10) with 2 = 2(n) blocks By, Bo, -++; B, is characterized by the integers M552 where m1, = the multiplicity of the integer . (Recall iin Bi. Then clearly ¥ m,.=m, and f= m4 = b, = | B, i that m, is the multiplicity of the integer i in , asa whole.) We . are of course interested only in partitions nm such that the numbers 6, given by (4.5) are all divisible by e; this is the definition of P,*. . | Let us recall that a given partition r ¢ Pp was only formally distinguishable from certain other partitions m' whose blocks contained the same integers with the same multiplicities; we assigned "labels" to the integers which occurred in } more than once, Our task now is to recombine those terms in the sum (4, 10) which are distinguishable only because of the artificial labels attached. The problem may be formulated as follows: given m m m 3 15 43 is it possible to partition x» into blocks B,; Bo, eees B with a collection ) = (1 ...) of integers, in how many ways given multiplicities M5» assuming the integers in ) are all some- how distinguishable? Stated this way the problem is a familiar combinatorial one: there are m, I/m,4!m49! es m,,! ordered ways of placing the I's, mo!/mo,!moo! ee My , | ordered ways of placing the 2's, etc. To obtain the total number of ways we must however account for the fact that the block lengths b. need not all be different; thus if re glock lengths (b,; Do, eee, b ) occur with multiplicities (1 --), we must divide the product of multinomial coefficients by 7 qd, ! The total contribution of all partitions 7 with the given muitiplicities m, ij to the sum (4.10) is the formidable expression 45 m.! (i ; )(q (b,-1)1) cacy mizimigh--s mit oi i ot (i.d.!) (1m. !) 1 1 a(b.-1)! _ r-2 1 h_ r-L B 4 = (-1) Ga Gm, 1 e’ = (-1) BD. M e, (5, 9) where B= m(b,-1)1, D= dt, M= mm,,! It is the object of the next few pages to show that BC) > 1, so that by lemma 2. 2 we obtain k = 0 in Fy We have already observed that the term of cannot contribute to (5,9), so that HAC) =u (B) - H) - HA tM) (5. 10) We may evaluate the terms on the right-hand side of (5.10) by means of Legendre's theorem 2. 2: bp(B) = hy J (bj 1-W, (b,-)) = Sy @-t- J Wi b,- 0) (5, 11) i i up) = sr) @,- W, 4) = sty & - Y WL @)) (5. 12) 4000) = 4 Fm, - Wn, )) = ee - F whl, )) (5.13) pe = Be La” Mpa? = per 2 hay 1, J 1, J 46 combining these last three relations with (5.10), we obtain up) = 44 (Y Wa (m,,) + Wa) = 22 - LwyheD. 6.14 i,j i Since Bp) is an integer, if we only wish to show that up(C) & 1, it will be sufficient to drop the factor st from (5, 14) and prove that the remaining expression is positive. This will be done by bounding certain of the terms in (5.14), We need one more lemma. n Lemma 5,3: Suppose f& Ss, = S for integers 8). > 0. Then k=1 3 W (2, < n(p- 1)log, (1 + S/n). Proof: We begin by showing that for any integer s > 0 it is true that W,,(s) < (p- log, (sti). (5. 15) For a fixed W > 0, let us find the least integer s such that WwW p's) =W. This can most easily be done by writing W = k(p-1)+ m with 0 < m < p-1, and observing that the smallest such s must use p-1 1's, p-1 p's, ..., (p-1) pe lig and finally m p's, Hence s= pe-1 + mp* = (m+1)p*- 1. For this value of s, (5.15) reduces to m < (p- log, (m+1). (5.16) Al But (5.16) is true for m = 0, m = p-1, and the function x/log, (x+1) is monotonic increasing for x > 1. Since the right-hand side of (5.15) is itself a monotonic function of s, (5.15) must be generally true, Because of (5.15) we may write n y W,(s,) < (p-1) ) tog, (8,41) = (p-1log (n(s,+1) ). k=1 But since s(s,+1) =S+n, the maximum value of the product m(s,+1) is attained when s,+1 = 1/n (S+n)=S/n+1. Hence 5S }, Wye) < (e-WNlog, (1 +S)? = n(p-i)iog, (1 + 8), as asserted, Note: Although the bound given by lemma 5.3 is usually very crude, the example Ss, = p -1, k=1, 2, ..., n, shows that it is sometimes sharp. We apply lemma 5.3 to the term 5 W ,(b;- 1) of (5.14), and obtain 4 ).W,,(b,- 1) < £(p-1)log,, (5 ). (5.17) i=1 We apply lemma 5.1 to the sum fF W (mn, )s and obtain that for each j, 5 W_(m,.) = w, so that j P YY 48 ), Wi) > wh . (5.18) i,j Combining (5.17) and (5.18) with (5.14), we conclude that 1 r B pC) = syle +) Wha) - 24 - 4 Ilog, (5 )). Hence in order to prove that Wy) > 0, we need yw te 2p (d, ,) + (p- 1)log,, (2) > 2+ (P- Hlog,, (r). (5.19) But by hypothesis w > 1+ (p- 1)log. (x), so it remains to show that =) Wa; )+ (p- log, (2) > 1. But if (p- Ilog (2) < 1, we have po} < p, sothat 2 = 1, in which case 4 py wi) > 1. This proves (5,19) and also that HC) > 1, so that by lemma 2, 2, Kk, = 0 in Fo This completes the proof of lemma 5, 2, Lemma 5. 2 allows us to complete the proof of theorem 5, 2 without much difficulty. According | to (5. 2), N , involves only the symmetric functions a. with r<p Kp 1). Furthermore, if a #0, N(0;a) = 0, and so also NO; a) = N, 0; a)=e+s = 0; ie., no constant terms are involved in me polynomials N,,(v; a) with a # 0, Therefore if each a . l<r<p K (+1) is zero, we have No = Ny = =N, = 0, and so N(v;a) = 0 (mod pk] kK . But as we have seen, 49 when v is restricted to the subspace a(f), each a, is a polynomial in the functions Ks with , a partition of r involving only elements of K; this was equation (5.7). By lemma 5,2, each k. will vanish if w> 14 (p- 1)log (7). Therefore in order that N(v;a) = 0 (mod p°), it is sufficient that each a. = 0 with r < po (p-1); i.e., w> lt (p-1)log (0° *(p- 1)) = 1+ (p-1)(t-1) + (p- 1)log,,(p- 1); this is equivalent to w-1 pi? e-1+ log, (p-1). And since log, (p-1) < 1 this follows from the hypothesis ol >. Hence theorem 5. 2 is proved for a # 0, and as we remarked earlier, the statement for a = U follows immediately since £ N(r;a) = e for each ve a(t). a In order to be able to make use of theorem 5, 2, it is necessary to have an effective means of calculating the value of wy = W le) = min {W,(me): m=1, 2,... } , and as given the definition appears to involve an infinite amount of calculation, But it is easy to see that this is not the case, as follows: Suppose that a minimum value for W,,(me) is attained by an equation of the form k, + ky +++- +k, = 0 (mode). (5.20) Now each k, in (5. 20) is an element of K and so has the form gp" n. But g;P 1 = g; (mod e), so that we may as well assume that a term of the form giP gp" occurs more than p-1 times in (5. 19) we could replace it by fewer which occurs in (5. 20) has j < nie Also if a term 50 terms of the same form; for example p- g; p would be replaced by +1 g; pit number of elements of K, this cannot happen. Thus the left-hand side of (5.20) is bounded by ; but since (5, 20) is assumed to involve the minimum possible m n-1 n (p-1) ¥ g,p’ = ) g,(o *-1) = Me, i=1 i oy i Sands ll bus for suitable M. We have proved Theorem 5, 3: W ac(e) = min {W,(me): m-=1, 2,..., m } . Remark: In the case that f is an tereducible polynomial of degree n, {he set K is K= {1, P, pi, wee, mye In this case M=E == = (° -1), so that Wxle) = wp (e) may be found by computing the values W ,(); W ,(2e), sees W (Ee). Let us observe that the value w may be interpreted as the least integer t for which it is possible to write 1 as a product of t of the roots of f. Using this interpretation it is possible to state theorem 5, 2 in a slightly different form, which does not add anything essentially new to the theory, but whichis possibly more suggestive: let us define a sequence of polynomials f = f,, 15, «++, where f(s) is the polynomial of F p *] whose roots are all possible products of k roots from among those of f, so that f Ks) has degree ni Theorem 5.2': Let f be a squarefree element of F Ux. : w is the smallest integer such that (x-1)|f, (x), andife =[{ 2 ard, then 51 N(s;a) = 0 (mod p’) a #0, and N(s;0) = e(modp) for all se a(f). Corollary 5.1: If w > p-1, then N(s;a) is divisible by p for each a# 0, andeach se a(f). Corollary 5.1 is well-known for the case p=2, where the hypothesis reduces merely to (x-1) 4 f(x). But the result had been thought to be peculiar to the binary case previously. (Selmer [10, p. 157] ). Let us illustrate how the theorems in this thesis can be applied to a particular example: consider the linear recurrence -s, =0 +S k * Seo 7 Sead 46 * Sk43 over GF[3]. The associated polynomial is f(x) = x + x + x? -x-1, and according to Church's table [2], f(x) is irreducible and belongs to exponent e = 104, Using only this one borrowed piece of information, it is possible to describe completely the distribution of the elements from GF[3] (which we take to be 0, +1, and -1) in the space a(f). Here cE = p-1 becomes 104.7 = 3°14, Let us first apply corollary 3.2; i.e., we regard 0(f) not as a vector space but as a set of E = 7 nonzero cycles of elements from GF[3], which correspond to the cosets of the cyclic subgroup T of order 104 in GF[3°]. Since q = 3 is a primitive root of E = 7, x4 has only two irreducible factors and so only two distinct distributions of trace values occur among the cycles of a(f); ie., 52 the subgroup T has one distribution and all other cosets Tx have the other distribution. Hence we denote by So: S,, Si4 and Co; Cy; and C4 the number of zeros, ones, and minus ones occurring in the subgroup, and the cosets, respectively. Since the trace assumes every value in GF[3] 3° = 243 times, we obtain Sy + 6Cy = 243 - 1 = 242 (5.21a) S, + 6C, = 243 (5.21) S + 6C_, = 248, (5.21¢) as well as the obvious relations S)+8,+8_,= 104 (5.22a) 0° 1 Co +C,+C_, = 104 . (5.22b) We now wish to apply theorem 5.2, and to do so it is necessary by theorem 5,3 to compute the values W, (104k) for k= 1, 2, 3, 4, 5, 6, 7. The ternary expansions are 104=3742-374342-1 : W,, (104) = 6 3 208 = 2-374 3942-3741 ; W,, (208) = 6 312 = 3° 42.354 3742-3; W,(312) = 6 2 416 = 39 42.34437%+2-1; W,(416) = 6 B20=2+3°4+3°42-3+1 3 W,(520) = 6 53 4 624 = 2-39 43742.3°43 ; W,(624) = 6 728 = 2+ 3°42. 344 2. 3549. 37 +2°34+2 ; W, (728) = 12. Consequently wg (104) = 6, since [ ay ] = 2, theorem 4. 2 - shows that S,iC FS 45 C_4F 0 (mod 9) 9 = Coz 1045 8 (mod 9). (5.23) From (5, 20a) and (5. 23) we obtain (242 - S_)/6 = Co =5 (mod 9), from which it follows that Sp = 212 = 50 (mod 54) so that Sy = 50. (The possibility So = 104 corresponds to the all-zero solution in a(f) which has explicitly been excluded from consideration. ) Similarly from (5. 20b) and (5. 23) we obtain S, = 243 = 27 (mod 54) and finally S4 = 27 (mod 54). Hence Sy and Sy are either 27 or 81, but the possibility 81 is excluded by (5.22a). Hence 8, =S_, = 27. Hence also, C 07 32, C, = 36, C , = 36. This completely solves the distribution problem for a (f), _ It would be interesting to know whether or not theorem 5. 2 is the best possible of its kind; i.e., as there exist polynomials f for which cithcr N(s;a) = O (mod petty a#0, or (5.24) N(s;0) = c (mod petty (5.25) for all se o(f)? It is the feeling of the author that this happens only rarely: 54 Conjecture: (5,24) is never true for all se ((f), and (5.25) can occur only for p> 2. One reason that a = 0 seems to play a special role in the conjecture is that the proof of theorem 5.2 for a= 0 only made use of the fact that © N(s;a)=e. It is possible that each N(s;a) # 0 (mod pth, while 5 N(s;a) = 0 (mod potty for p>2, And in fact a#0 this sort of thing happens for p= 3 and f(x) = x - x- 1 which has exponent 121, The values of N(s;1) and N(s;-1) are 45 and 36 for certain cycles s¢ a(f), and 36 and 45 for the others. But 36+ 45 = 81= 3 whereas theorem 5.2 gives only ¢ = 2, Let us observe finally that if we apply theorem 5. 2 to the case where f(x) is a primitive polynomial of degree n in Fes] ; i,e., when f has exponent e = p'-1. Here w ,(e) = Wl) =n(p-1), so that ¢ =n-1. And in this case theorem 5. 2 is exact since it is obvious that N(s;a) = prt for a #0 and N(s;0) = prt, for in this case the subgroup T of theorem 3,1 is the complete multiplicative subgroup of GF[p"7] , so that the trace assumes n-1 every nongero value p times on T, and zero prliy times. Thus theorem 5. 2 can be exact for both large and small values of é, and so it is unlikely that there is a general theorem which is stronger than theorem 5, 2, Ci] (2d [3] [4] [9] [6] [7] [8] [9] [10] 55 REFERENCES Albert, A, A.: Fundamental Concepts of Higher Algebra; University of Chicago Press, 1956, Church, R.: "Tables of Irreducible Polynomials for the First Four Prime Moduli;" Ann, Math. 36(1935) pp. 198-209, Dickson, L. E,: Linear Groups; Springer, Berlin, 1900; Dover Pub, 1958, Dickson, L. E,: History of the Theory of Numbers, vol. 1; Carnegie Publication No, 256, reprinted, Chelsea 1952, Hall, Marshall, Jr.: "An Isomorphism between Linear Recurring Sequences and Algebraic Rings;'' Trans. Am. Math, Soc, 44(1938), pp. 196-218. Hall, Marshall, Jr.: Combinatorial Theory, Blaisdell, 1967, MacMahon, P. A,: Combinatory Analysis, vol. 1; University Press, Cambridge, England, 1915; reprinted, Chelsea 1960. Mattison, H, F., and Solomon, G.: "A New Treatment of Bose-Chaudhuri Codes;" J, Soc. Ind. Appl. Math. 9(1961), -. pp. 654-669, Rota, G.-C,: "On the Foundations of Combinatorial Theory. I, Theory of Mébius Functions;" Zeit, Wahrshein, 2(1964), pp. 340-368. Selmer, E, S.: Linear Recurrence Relations over Finite Fields; mimeographed lecture notes available for $5. 00 from Dept. Math. , University of Bergen, Norway. [11] [12] [13] [14] 56 Solomon, G. and McEliece, R. J.: 'Weights of Cyclic Codes;" J. Comb. Theory, to appear. van der Warden, B. L.: Modern Algebra, vol. 1; Ungar, New York, 1953. Ward, M.: "The Arithmetical Theory of Linear Recurring Sequences, "' Trans. Am. Math. Soc. 35(1933), pp. 600-628. Zierler, N.: "Linear Recurring Sequences;" J. Soc. Ind, Appl. Math. 7(1959), pp. 31-48.