Past exam of the mathematics course of the University of Cambridge 2007 ii Paper 1 11G Solution Created 2026-09-24 Updated 2026-10-14
For binary linear codes of length , the bar product of binary linear codes is . The parametrization is injective and linear, so its dimension is . If , a nonzero word has Hamming weight at least ; if , . Taking and of minimum weight showsFor , the inner product of and is , since . The spaces have complementary dimensions, proving .
Define the Reed-Muller code by evaluating all multilinear polynomials of total degree at most at the points of . The squarefree monomials are independent functions, giving dimension . Splitting according to the last variable gives the Reed-Muller bar-product recursion , with the endpoint codes interpreted in the usual way. The distance recursion gives .
To identify the Dual of a Reed-Muller code, multiply a monomial of degree at most by one of degree at most . The product omits some variable, so its sum over is even and its binary inner product is zero. The binomial dimension identity then gives
Past exam of the mathematics course of the University of Cambridge 2015 ii Paper 4 3G Solution Created 2026-09-24 Updated 2026-10-06
Work over the finite field . Reduce polynomials modulo , so their monomials are square-free. The binary Reed-Muller code consists of the evaluation vectors of polynomials of degree at most at all points of , in a fixed order. This is a linear code of length and dimension , for . Square-free monomials give independent evaluation functions, as follows inductively by splitting according to the last variable.
The minimum Hamming distance of a linear code equals its least nonzero Hamming weight. The result isHere is the repetition code, while is the full binary vector space and has distance one. For the induction step, write , where and . Its evaluation vector is , the Reed-Muller bar-product recursion. If , its nonzero Hamming weight is at least , with the full-space endpoint treated as above. If , every position where contributes exactly one to the sum of the two weights; hence the weight is at least . The monomial is one exactly on points, attaining the bound. Degrees greater than give the same full code; the zero code at negative degree has no nonzero word whose weight could define a finite minimum.
Past exam of the mathematics course of the University of Cambridge 2022 ii Paper 3 3K b i Solution Created 2026-09-24 Updated 2026-09-25