Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR09-030 | 5th April 2009 00:00

The density of weights of Generalized Reed-Muller codes


Authors: Shachar Lovett
Publication: 6th April 2009 09:49
Downloads: 3241


We study the density of the weights of Generalized Reed--Muller codes. Let $RM_p(r,m)$ denote the code of multivariate polynomials over $\F_p$ in $m$ variables of total degree at most $r$. We consider the case of fixed degree $r$, when we let the number of variables $m$ tend to infinity. We prove that the set of relative weights of codewords is quite sparse: for every $\alpha \in [0,1]$ which is not rational of the form $\frac{\ell}{p^k}$, there exists an interval around $\alpha$ in which no relative weight exists, for any value of $m$. 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.

ISSN 1433-8092 | Imprint