A new theorem about the Mattson-Solomon polynomial, and some applications
A.M. Kerdock, F. J. Macwilliams, Andrew M. Odlyzko · IEEE Transactions on Information Theory · 1974
LetF = GF(2), andFG = F[x]/(x^n + 1). FGis the residue class ring of polynomials modx^n + 1. An element ofFGis represented by a polynomial of degree at mostn - 1\begin{equation} c(x) = c_0 + c_1 x + \cdots + c_{n-1} x^{n-1} \end{equation} with coefficients inF. It may also be represented by a polynomial \begin{equation} g(z) = \sum_{j=0}^{n-1} c(\alpha^j)z^j \end{equation} with coefficients inGF(2^m), wheremis the least integer such thatndivides2^m - 1, and\alphais a primitiventh root of unity. Mattson and Solomon [1] introduced this representation in 1961. The new theorem states that \begin{equation} zg'(z) = \frac{g(z)(g(z) + 1)}{z^n +l}. \end{equation} A typical application of this result is as follows. Letn = 2^m - 1, wherem \equiv 1mod 2. Let\mathcal{A}_1be the cyclic code of dimension 2m defined by the property that its check polynomial has zeros\alpha ^{-j}, wherej = 1,2,\cdots,2^{m-1}andj = l,2l,\cdots,2^{m-1} l, l = 2^i + 1. If(i,m) = 1this code has just three nonzero weights, namely,2^{m-1} \pm 2^{(m-1)/2}and2^{m-1}. The weight distribution can then be obtained from the MacWflliams identifies. These conditions are satisfied forn = 31, l = 3,5; n = 127,l= 3,5,9;n = 511, l = 3,5,17; etc. Thus forn= 127, for example, the three codes\mathcal{A}_3,\mathcal{A}_5, \mathcal{A}_9have the same weight distribution, although they are probably not equivalent in the usual sense.