Since \(r \le q-1\), restricting the total degree to at most \(r\) automatically forces every variable to have degree at most \(q-1\), so no individual-degree constraint is active. Hence the dimension equals the size of the set

since for every \((d_1,\ldots ,d_m) \in D\) the monomial \(X_1^{d_1} \cdots X_m^{d_m}\) is a monomial of degree at most \(r\), and these are all such monomials (a basis for the space of \(m\)-variate polynomials of total degree at most \(r\)).

It remains to show \(|D| = \binom {m+r}{r}\), a standard stars-and-bars count: introduce a slack variable \(d_0 = r - \sum _{i=1}^m d_i \geq 0\), giving a bijection between \(D\) and the set of \((m+1)\)-tuples of non-negative integers \((d_0,d_1,\ldots ,d_m)\) with \(\sum _{i=0}^m d_i = r\). The number of such tuples is the number of ways to place \(r\) indistinguishable balls into \(m+1\) distinguishable bins, which is \(\binom {r + m}{m} = \binom {m+r}{r}\).

The statement is equivalent to saying that the probability that \(f(\mathbf{a}) = 0\) is at most \(\frac{\deg (f)}{q}\) when \(\mathbf{a} = (a_1,\ldots ,a_m)\) is chosen uniformly at random from \(\mathbb {F}_q^m\). We prove this by induction on \(m \geq 1\).

Base case \(m=1\). This is exactly the degree mantra (Lemma 183): a nonzero univariate polynomial of degree \(\deg (f) \le r\) has at most \(\deg (f)\) roots, so the probability that a uniformly random \(a_1 \in \mathbb {F}_q\) is a root is at most \(\deg (f)/q \le r/q\).

Inductive step. Let \(m {\gt} 1\) and assume the lemma holds for \((m-1)\)-variate polynomials. Write \(f\) as a polynomial in \(X_m\) with coefficients in \(\mathbb {F}_q[X_1,\ldots ,X_{m-1}]\):

where each \(f_i(X_1,\ldots ,X_{m-1})\) is a polynomial from \(\mathbb {F}_q[X_1,\ldots ,X_{m-1}]\) with \(\deg (f_i) \leq r-i\), and \(t\) is the largest index such that \(f_t\) is not the zero polynomial. Pick \(\mathbf{a} \in \mathbb {F}_q^m\) in two steps: first pick \((a_1,\ldots ,a_{m-1})\) uniformly at random from \(\mathbb {F}_q^{m-1}\), and then pick \(a_m\) uniformly from \(\mathbb {F}_q\). Let

Consider the two events

By the inductive hypothesis applied to \(f_t\) (which is non-zero of degree at most \(r-t\)),

For every \((a_1,\ldots ,a_{m-1}) \in \mathbb {F}_q^{m-1}\) such that \(f_t(a_1,\ldots ,a_{m-1}) \neq 0\), the univariate polynomial \(f^{(a_1,\ldots ,a_{m-1})}(X_m)\) is non-zero of degree at most \(t\), and so by the degree mantra (base case) it has at most \(t\) roots; hence, over the random choice of \(a_m\), \(\Pr [f^{(a_1,\ldots ,a_{m-1})}(a_m) = 0] \le t/q\) for every such \((a_1,\ldots ,a_{m-1})\), and therefore

If neither \(\mathcal{E}_1\) nor \(\mathcal{E}_2\) occurs then \(f(\mathbf{a}) \neq 0\): indeed if \(f(\mathbf{a}) = 0\) then either \(f_t(a_1,\ldots ,a_{m-1}) = 0\) (giving \(\mathcal{E}_1\)) or \(f_t(a_1,\ldots ,a_{m-1}) \neq 0\) and \(f^{(a_1,\ldots ,a_{m-1})}(a_m) = 0\) (giving \(\mathcal{E}_2\)). Hence \(\Pr _{\mathbf{a}}[f(\mathbf{a}) = 0] \leq \Pr [\mathcal{E}_1 \cup \mathcal{E}_2]\), and by the union bound (Lemma 184),

This is a special case of the general Polynomial Distance Lemma (Lemma 190) with \(q=2\). Write \(r = \deg (f)\) and let \(s,t\) be the unique non-negative integers with \(t \le q-2 = 0\) and \(s(q-1)+t = r\); since \(q-1=1\) this forces \(t=0\) and \(s=r\). The hypothesis \(\deg _{X_i}(f) \le 1 = q-1\) for all \(i\) matches the hypothesis of Lemma 190, which then gives

as claimed.

Over \(\mathbb {F}_2\) the individual-degree constraint \(\deg _{X_i} \le q-1 = 1\) means every variable appears with exponent \(0\) or \(1\) in a reduced monomial, so the monomials of individual degree at most \(1\) are in bijection with subsets \(S \subseteq [m]\) (via \(S \mapsto \prod _{i\in S} X_i\)), and the total degree of the monomial corresponding to \(S\) is \(|S|\). Hence the dimension of \(\mathrm{RM}(2,m,r)\), which is the number of such monomials of total degree at most \(r\), equals the number of subsets of \([m]\) of size at most \(r\), namely \(\sum _{i=0}^{r}\binom {m}{i}\).

The block length \(2^m\) and dimension \(\sum _{i=0}^r \binom {m}{i}\) are immediate from the definition of \(\mathrm{RM}(2,m,r)\) (Definition 182) and Proposition 188. Since \(\mathrm{RM}(2,m,r)\) is linear, its minimum distance equals the minimum weight of a non-zero codeword, i.e. the minimum, over non-zero \(f \in \mathbb {F}_2[X_1,\ldots ,X_m]\) of individual degree at most \(1\) and total degree at most \(r\), of \(|\{ \mathbf{a} \in \mathbb {F}_2^m \mid f(\mathbf{a}) \ne 0\} |\). Every such \(f\) has \(\deg (f) \leq r\), and hence \(\deg _{X_i}(f) \le 1\) for all \(i\), so Lemma 187 applies to give \(|\{ \mathbf{a} \mid f(\mathbf{a}) \ne 0\} | \geq 2^{m - \deg (f)} \geq 2^{m-r}\). Thus the distance is at least \(2^{m-r}\); taking \(f = X_1 X_2 \cdots X_r\) (which has \(\deg (f) = r\), individual degree \(1\) in each variable, and by Lemma 187 weight exactly \(2^{m-r}\) since the bound is tight for this polynomial) shows the distance equals exactly \(2^{m-r}\).

We prove the first inequality by induction on \(m\).

Base case \(m=1\). By the degree mantra (Lemma 183), the probability that \(f(a_1) \neq 0\) is at least \(\frac{q - \deg (f)}{q} \geq \frac{q-r}{q}\). If \(r {\lt} q-1\) we have \(s=0\) and \(t=r\), and so the target expression \((q-t)\cdot q^{-1} = \frac{q-r}{q} \leq \Pr [f(a_1) \neq 0]\). If \(r = q-1\) we have \(s=1\) and \(t=0\), and \((q-t)\cdot q^{-2} = q\cdot q^{-2} = \frac{q-(q-1)}{q} \le \Pr [f(a_1) \ne 0]\), again by the degree mantra.

Inductive step. Assume the hypothesis holds for \((m-1)\)-variate polynomials. Write \(f = \sum _{i=0}^{b} f_i X_m^i\) where \(f_i \in \mathbb {F}_q[X_1,\ldots ,X_{m-1}]\), \(f_b \neq 0\), \(0 \le b \le q-1\), and \(\deg (f_b) \leq r-b\). Let

Bounding \(\Pr [\mathcal{E} \mid \mathcal{E}_1]\). Fix \(a_1,\ldots ,a_{m-1}\) with \(f_b(a_1,\ldots ,a_{m-1}) \neq 0\) and let \(P(Z) = \sum _{i=0}^{b} f_i(a_1,\ldots ,a_{m-1}) Z^i\). Then \(P\) is a non-zero univariate polynomial of degree \(b\), so by the degree mantra it has at most \(b\) roots and \(\Pr _{a_m}[P(a_m) \neq 0] \geq \frac{q-b}{q}\). Since \(\Pr [f(a_1,\ldots ,a_m) = 0 \mid a_1,\ldots ,a_{m-1}] = \Pr _{a_m}[P(a_m) = 0]\), we get

Bounding \(\Pr [\mathcal{E}_1]\). Write \(r - b = s'(q-1) + t'\) with \(s', t' \geq 0\) and \(t' \leq q-2\). Since \(\deg (f_b) \leq r-b\) and \(\deg _{X_i}(f_b) \le q-1\), the inductive hypothesis applied to \(f_b\) gives

Combining. Since \(\Pr [\mathcal{E}] \geq \Pr [\mathcal{E} \text{ and } \mathcal{E}_1] = \Pr [\mathcal{E}_1]\cdot \Pr [\mathcal{E}\mid \mathcal{E}_1]\), we get

By Claim 191 (applied with \(q,r,s,t,s',t',b\) satisfying \(r = s(q-1)+t\), \(r-b = s'(q-1)+t'\), \(t,t' \le q-2\), \(b \le q-1\)), this quantity is at least \((q-t)\cdot q^{-(s+1)}\), which establishes the first inequality \(|\{ \mathbf{a} \mid f(\mathbf{a}) \ne 0\} | \ge (q-t) \cdot q^{m-s-1}\) by induction.

Finally the second inequality \((q-t)\cdot q^{-(s+1)} \geq q^{-r/(q-1)}\) (equivalently, after multiplying by \(q^m\), \((q-t) \cdot q^{m-s-1} \ge q^{m - r/(q-1)}\)) is exactly Claim 192.

Since \(s\) (resp. \(s'\)) is the quotient when dividing \(r\) (resp. \(r-b\)) by \(q-1\), and \(0 \le b \le q-1\), we have either \(s'=s\) or \(s'=s-1\).

Case \(s=s'\). Then \(t = t'+b\), and it suffices to show \(\frac{q-b}{q}\cdot (q-t') \geq q - (t'+b)\), i.e. \((q-b)(q-t') \geq q(q-(t'+b))\). This holds since

using \(bt' \geq 0\).

Case \(s = s'+1\). Then \(t + (q-1) = t' + b\), and it suffices to show

i.e. (dividing by \(q\), and writing \(\alpha = q-b \ge 1\), \(\beta = q - t' \ge 1\), using \(b,t' \le q-1\)) that \(\alpha \beta \geq \alpha +\beta - 1\). This holds since \(\alpha \beta = \alpha + \alpha (\beta -1) \geq \alpha + (\beta - 1)\) using \(\alpha \geq 1\) and \(\beta - 1 \geq 0\).

In both cases the inequality holds, proving the claim.

Substituting \(r = s(q-1)+t\), it suffices to show \((q-t)\cdot q^{-(s+1)} \geq q^{-(s(q-1)+t)/(q-1)} = q^{-s}\cdot q^{-t/(q-1)}\). Dividing both (non-negative) sides by \(q^{-s}\), it suffices to show

Let \(f_q(t) = \frac{t}{q} + q^{-t/(q-1)} - 1\); we must show \(f_q(t) \leq 0\) for \(0 \le t \le q-2\). We have

so \(f_q\) is convex on \([0,q-2]\) and is therefore maximized at one of the two endpoints of the interval. We have \(f_q(0) = 0 \leq 0\), so it suffices to show \(f_q(q-2) \leq 0\), i.e.

Multiplying both sides by \(q\), it suffices to show \(q^{1/(q-1)} \leq 2\), equivalently \(q \leq 2^{q-1}\) for every \(q \geq 2\). This follows from Bernoulli’s inequality \(1+kx \leq (1+x)^k\) (valid for \(x \geq -1\), \(k \geq 1\)) applied with \(x=1\), \(k = q-1\), which gives \(q = 1 + (q-1)\cdot 1 \leq 2^{q-1}\).

We prove \(P=0\) by induction on \(m\).

Base case \(m=1\). \(P\) has degree at most \(q-1\) and \(q\) roots (all of \(\mathbb {F}_q\)). By the degree mantra (Lemma 183), a non-zero polynomial of degree at most \(q-1\) has at most \(q-1\) roots; since \(P\) has \(q {\gt} q-1\) roots, \(P\) must be the zero polynomial.

Inductive step. Write \(P = \sum _{i=0}^{q-1} P_i(X_1,\ldots ,X_{m-1}) X_m^i\) with each \(\deg _{X_j}(P_i) \le q-1\) for \(j {\lt} m\). Fix any \((a_1,\ldots ,a_{m-1}) \in \mathbb {F}_q^{m-1}\). The univariate polynomial \(Q(X_m) = \sum _{i=0}^{q-1} P_i(a_1,\ldots ,a_{m-1}) X_m^i\) has degree at most \(q-1\) and satisfies \(Q(a_m) = P(a_1,\ldots ,a_m) = 0\) for every \(a_m \in \mathbb {F}_q\), i.e. \(Q\) has \(q\) roots; by the base-case argument \(Q = 0\), i.e. \(P_i(a_1,\ldots ,a_{m-1}) = 0\) for every \(i\). As \((a_1,\ldots ,a_{m-1})\) was arbitrary, each \(P_i\) vanishes on all of \(\mathbb {F}_q^{m-1}\), and by the inductive hypothesis (applied to each \(P_i\), which has individual degrees at most \(q-1\) in \(X_1,\ldots ,X_{m-1}\)) \(P_i = 0\) for every \(i\). Hence \(P=0\).

For the consequence: any \(\mathbb {F}_q\)-linear combination \(\sum _{\mathbf{d} \in S_{q,m,r}} c_{\mathbf{d}} \mathbf{X}^{\mathbf{d}}\) that evaluates to zero at every point of \(\mathbb {F}_q^m\) is, by the above, the zero polynomial, i.e. all \(c_{\mathbf{d}} = 0\); this is exactly linear independence of the evaluation vectors of the monomials \(\mathbf{X}^{\mathbf d}\), \(\mathbf d \in S_{q,m,r}\). These evaluations also span \(\mathrm{RM}(q,m,r)\), since by definition every \(f \in \mathrm{RM}(q,m,r)\) is the evaluation of some polynomial of individual degree at most \(q-1\) in each variable and total degree at most \(r\), which is an \(\mathbb {F}_q\)-linear combination of the monomials \(\mathbf{X}^{\mathbf{d}}\), \(\mathbf{d} \in S_{q,m,r}\).

By Lemma 194, the evaluations of \(\mathbf{X}^{\mathbf{d}}\) for \(\mathbf{d} \in S_{q,m,r}\) form a basis for \(\mathrm{RM}(q,m,r)\), so the dimension of \(\mathrm{RM}(q,m,r)\) equals \(|S_{q,m,r}| = K_{q,m,r}\).

Monotone in \(r\). If \(r \le r'\) then every \(\mathbf{d} \in S_{q,m,r}\) satisfies \(\sum _i d_i \le r \le r'\) and \(0 \le d_i \le q-1\), so \(\mathbf{d} \in S_{q,m,r'}\); hence \(S_{q,m,r} \subseteq S_{q,m,r'}\) and \(K_{q,m,r} \le K_{q,m,r'}\).

Monotone in \(q\). If \(q \le q'\) then every \(\mathbf{d} \in S_{q,m,r}\) satisfies \(0 \le d_i \le q-1 \le q'-1\) for all \(i\) and \(\sum _i d_i \le r\), so \(\mathbf{d} \in S_{q',m,r}\); hence \(S_{q,m,r} \subseteq S_{q',m,r}\) and \(K_{q,m,r} \le K_{q',m,r}\).

We prove the three inequalities \(K_{q,m,r} \le K_{q,m,r}^+\), \(K_{q,m,r}^- \le K_{q,m,r}\), and \(K_{q,m,r}^+ \le c_1 (K_{q,m,r}^-)^{c_2}\) in turn, using monotonicity of \(K_{q,m,r}\) (Lemma 196) throughout.

Upper bound \(K_{q,m,r} \leq K_{q,m,r}^+\). On one hand, ignoring the total-degree restriction, \(K_{q,m,r} \leq K_{q,m,(q-1)m} = q^m\). On the other hand, ignoring the individual-degree restriction, \(K_{q,m,r} \leq K_{r+1,m,r} = \binom {m+r}{r}\) (this is exactly the count in Proposition 185, since with \(q' = r+1 {\gt} r\) the individual-degree constraint is vacuous). Taking the minimum gives \(K_{q,m,r} \le K_{q,m,r}^+\).

Lower bound \(K_{q,m,r}^- \leq K_{q,m,r}\), case \(r \geq (q-1)m/2\). Consider the map \(\mathbf{d} = (d_1,\ldots ,d_m) \mapsto \overline{\mathbf{d}} = (q-1-d_1,\ldots ,q-1-d_m)\) on vectors with \(0 \le d_i \le q-1\). This is a bijection on \(\{ 0,\ldots ,q-1\} ^m\) that sends \(\sum _i d_i {\gt} r\) to \(\sum _i \overline{d_i} {\lt} (q-1)m - r\). Hence exactly one of \(\mathbf{d} \in S_{q,m,r}\) or \(\overline{\mathbf{d}} \in S_{q,m,(q-1)m-r}\) holds for each \(\mathbf{d} \in \{ 0,\ldots ,q-1\} ^m\), giving

Since \(r \geq (q-1)m/2\) we have \((q-1)m - r \leq r\), so by monotonicity in \(r\) (Lemma 196), \(K_{q,m,(q-1)m-r} \leq K_{q,m,r}\), whence, combined with the identity above, \(2K_{q,m,r} \geq K_{q,m,r} + K_{q,m,(q-1)m-r} = q^m\), i.e. \(K_{q,m,r} \geq q^m/2\). Also, using \(K_{q,m,(q-1)m-r} \le K^+_{q,m,(q-1)m-r}\) from the upper bound proved above, \(K_{q,m,r} = q^m - K_{q,m,(q-1)m-r} \geq q^m - K^+_{q,m,(q-1)m-r}\). Together, \(K_{q,m,r} \geq K_{q,m,r}^-\) in this case.

Lower bound \(K_{q,m,r}^- \leq K_{q,m,r}\), case \(r {\lt} (q-1)m/2\). Let \(q' = \lfloor \frac{2r+m}{m} \rfloor \). Then \(r \geq (q'-1)m/2\), so by the previous case (applied with \(q'\) in place of \(q\)) \(K_{q',m,r} \geq (q')^m/2\); by monotonicity in \(q\) (Lemma 196), \(K_{q,m,r} \geq K_{q',m,r} \geq (q')^m/2 = \frac{1}{2} \left(\lfloor \frac{2r+m}{m}\rfloor \right)^m\). Also, using Proposition 188, \(K_{q,m,r} \geq K_{2,m,r} = \sum _{i=0}^r \binom {m}{i} \geq \binom {m}{r}\) (again using monotonicity in \(q\)). Taking the maximum of the two lower bounds gives \(K_{q,m,r} \geq K_{q,m,r}^-\) in this case.

Upper bound \(K_{q,m,r}^+ \leq c_1 (K_{q,m,r}^-)^{c_2}\). We split into three ranges.

Range \(r \geq (q-1)m/2\). Here \(\frac{q^m}{2} \le K_{q,m,r}^- \le K_{q,m,r}^+ \le q^m\), so \(K_{q,m,r}^+ \leq 2K_{q,m,r}^-\).

Range \(r {\lt} m/2\). Here \(K_{q,m,r}^- \geq \binom {m}{r} \geq (m/r)^r \geq 2^r\). Also, by the standard bound \(\binom {n}{k} \leq (en/k)^k\),

using \(m + r {\lt} \frac{3}{2}m\) in this range. From \(2^r \le K_{q,m,r}^-\) we get \(\left( \tfrac {3e}{2}\right)^r \le (K_{q,m,r}^-)^{\log _2(3e/2)}\), and combining with \((m/r)^r \le K_{q,m,r}^-\) and \(K_{q,m,r}^+ \le \binom {m+r}{r}\),

Range \(m/2 \le r {\lt} (q-1)m/2\). Here \(\left\lfloor \tfrac {2r+m}{m} \right\rfloor = 1 + \left\lfloor \tfrac {2r}{m} \right\rfloor \geq 1 + \tfrac {r}{m} = \tfrac {m+r}{m}\), so

On the other hand, using \(\binom {n}{k}\le (en/k)^k\) again,

Since \(\left(\tfrac {m+r}{m}\right)^m \leq 2K_{q,m,r}^-\) and, from \(K_{q,m,r}^- \geq \tfrac 12 (3/2)^m\) (i.e. \(2K^-_{q,m,r} \ge (3/2)^m\)), we get \(e^m \le \left(2K^-_{q,m,r}\right)^{\log _{3/2} e} \leq (2K_{q,m,r}^-)^{\log _2(3e/2)}\) after adjusting the exponent constant as in the previous range, we get \(K_{q,m,r}^+ \leq (2K_{q,m,r}^-)^{1+\log _2(3e/2)}\).

Combining the three ranges, in all cases \(K_{q,m,r}^+ \leq c_1 (K_{q,m,r}^-)^{c_2}\) holds for \(c_2 = 1+\log _2(3e/2) {\lt} 3.1\) and \(c_1 = 2^{c_2} {\lt} 8.2\).

By Lemma 186 (applicable since \(r {\lt} q-1 {\lt} q\)), the fraction of zeroes of a non-zero degree-\(\le r\) polynomial is at most \(r/q\), so the distance of \(\mathrm{RM}(q,m,r)\) is at least \(N(1-r/q) = \delta N\). By Proposition 197, in the regime \(r {\lt} (q-1)m/2\) (which holds once \(m\) is large enough, as \(r,q\) are fixed), \(K = K_{q,m,r} \geq K_{q,m,r}^- \geq \binom {m}{r} \geq (m/r)^r = (\log _q N / r)^r\), using \(N = q^m\).

Setting \(r = m-d\) in Theorem 189, \(\mathrm{RM}(2,m,m-d)\) has block length \(N = 2^m\), distance \(D = 2^{m-r} = 2^d\), and dimension

Each term \(\binom {m}{j}\) for \(j {\lt} d\) is at most \(\binom {m}{d-1} \le \binom {m+d}{d}\) (a crude bound sufficient here), and summing \(d\) such terms gives \(\sum _{j=0}^{d-1}\binom {m}{j} \le \binom {m+d}{d}\) for \(d,m\) in the relevant range; hence \(K \geq N - \binom {m+d}{d}\). Substituting \(m = \log _2 N\) gives \(K \geq N - \binom {\log _2 N + d}{d}\), and using \(\binom {n}{d} \le n^d\) gives \(K \geq N - (\log _2 N + d)^d \geq N - (\log _2 N)^d \cdot O(1)\), which for fixed \(d\) and \(N \to \infty \) still gives \(K/N \to 1\) (a precise constant for the bound \(K \ge N - (\log _2 N)^d\) is worked out in Exercise 9.12). As \(N \to \infty \) with \(d\) fixed, \((\log _2 N)^d / N \to 0\), so \(K/N \to 1\).

Here \(r = q/2 \geq (q-1)m/2\) once \(m \geq 1\) and \(q\) is large, so Proposition 197 gives (using the case \(r \geq (q-1)m/2\), together with monotonicity to compare against the individual-degree-unrestricted count)

the last step following the same style of bound as in the range analysis of Proposition 197, giving \(K \geq \tfrac 12 \left(\tfrac {q+m}{m}\right)^m \geq \tfrac {1}{2m^m}\cdot q^m = \tfrac {1}{2m^m}\cdot N\). By Lemma 190, the distance is at least \(q^{m - r/(q-1)}\); as \(q \to \infty \) with \(m\) fixed and \(r=q/2\), \(r/(q-1) \to m/2\), so the distance is \(q^{m/2 + o(1)} = N^{1/2+o(1)}\), and for \(q\) large enough this is at least \(N/2\) as claimed in the book. Writing \(N^\varepsilon \approx q\) (since \(m \approx 1/\varepsilon \) and \(N = q^m\)), the dimension is \(\Omega (\varepsilon ^{1/\varepsilon }) \cdot N\) and the alphabet has size \(N^\varepsilon \).

As in Example 200, distance \(N/2\) and the dimension bound \(K \geq \tfrac 12 \left(\tfrac {q+m}{m}\right)^m\) follow from Lemma 190 and Proposition 197. Since \(m = q^\varepsilon = o(q)\), \(\tfrac {q+m}{m} \geq \tfrac {q}{m} = q^{1-\varepsilon }\), giving \(K \geq \tfrac 12 (q^{1-\varepsilon })^m = \tfrac 12 (q^m)^{1-\varepsilon } = \tfrac 12 N^{1-\varepsilon }\). Since \(N = q^m = q^{q^\varepsilon }\), we have \(\log N \approx q^\varepsilon \log q\), so \(q \approx (\log N)^{1/\varepsilon }\) up to lower-order terms, giving an alphabet of size \((\log N)^{1/\varepsilon }\).