We study the density of the weights of Generalized Reed--Muller codes. Let @math denote the code of multivariate polynomials over @math in @math variables of total degree at most @math . We consider the case of fixed degree @math , when we let the number of variables @math tend to infinity. We prove that the set of relative weights of codewords is quite sparse: for every @math which is not rational of the form @math , there exists an interval around @math in which no relative weight exists, for any value of @math . This line of research is to the best of our knowledge new, and complements the traditional lines of research, which focus on the weight distribution and the divisibility properties of the weights. Equivalently, we study distributions taking values in a finite field, which can be approximated by distributions coming from constant degree polynomials, where we do not bound the number of variables. We give a complete characterization of all such distributions.
The following theorem is proved. Let f(x_1, , x_m) be a binary nonzero polynomial of m variables of degree . H the number of binary m -tuples (a_1, , a_m) with f(a_1, , a_m) = 1 is less than 2^ m- +1 , then f can be reduced by an invertible affme transformation of its variables to one of the following forms. where m + and 3 . This theorem completely characterizes the codewords of the th-order Reed-Muller code whose weights are less than twice the minimum weight and leads to the weight enumerators for those codewords. These weight formulas are extensions of Berlekamp and Sloane's results.  Let P r be the set of all polynomials of degree r in m variables over GF (2). Polynomial ƒ in P r is said to be affine equivalent to polynomial g in P r , if ƒ is transformable to g by an invertible affine transformation of the variables. Any polynomial of weight less than 2 m − r +1 + 2 m − r −1 in P r is shown to have a simple structure. By using this fact, we find out a set of representative polynomials such that any polynomial of weight less than 2 m − r +1 + 2 m − r −1 in P r is affine equivalent to one and only one polynomial of the set. By counting the number of polynomials which are affine equivalent to each representative polynomial in the set, we derive explicit formulas for the enumerators of all weights less than 2.5 d of Reed—Muller codes, where d is the minimum weight. The polynomial formulation of generalized ReedMuller codes, first introduced by Kasami, Lin, and Peterson is somewhat formalized and an extensive study is made of the interrelations between the m -variable approach of Kasami, Lin, and Peterson and the one-variable approach of Mattson and Solomon. The automorphism group is studied in great detail, both in the m -variable and in the one-variable language. The number of minimum weight vectors is obtained in the general case. Two ways of restricting generalized ReedMuller codes to subcodes are studied: the nonprimitive and the subfield subcodes. Connections with geometric codes are pointed out and a new series of majority decodable codes is introduced.