On the weight structure of Reed-Muller codes

The following theorem is proved. Let <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">f(x_1,⋯, x_m)</tex> be a binary nonzero polynomial of <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">m</tex> variables of degree <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">ν</tex> . H the number of binary <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">m</tex> -tuples <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">(a_1,⋯, a_m)</tex> with <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">f(a_1, ⋯, a_m)</tex> = 1 is less than <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2m-ν+1</tex> , then <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">f</tex> can be reduced by an invertible affme transformation of its variables to one of the following forms. {equation} f = y_1 ⋯ yν - μ (yν-μ+1 ⋯ yν + yν+1 ⋯ yν+μ), {equation} where <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">m ≥ ν+μ</tex> and <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">ν ≥ μ ≥ 3</tex> . {equation} f = y_1 ⋯ yν-2(yν-1 yν + yν+1 yν+2 + ⋯ + yν+2μ -3 yν+2μ-2), {equation} This theorem completely characterizes the codewords of the <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">ν</tex> 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.