Covering codes, perfect codes, and codes from algebraic curves

../

chapter_1_conjecture_p50: Van Wee's conjecture that, whenever a perfect R-error-correcting q-ary code of length n exists, the optimal covering code of length n+1 and radius R has exactly q^(n+1)/V_q(n,R) words.

chapter_1_corollary_1: The radius-one case of van Wee's Theorem 9, which gives K(n,1) >= 2^n/n for even n and determines K(2^r,1) exactly for every r >= 1.

chapter_1_theorem_10: Van Wee's second lower bound on K(n,R) for n >= 2R, obtained by counting multiple coverage on radius-two balls, which fills some of the cases left by Theorem 9.

chapter_1_theorem_12: Van Wee's verification, from his table of bounds, of the Cohen-Lobstein-Sloane inequality K(n+2,R+1) <= K(n,R) in the case R = 1 for all n >= 2 except n = 9.

chapter_1_theorem_9: Van Wee's lower bound on K(n,R), the least size of a binary code of length n with covering radius R, which improves the sphere covering bound whenever n+1 is not divisible by R+1.

chapter_2_corollary_1: A perfect q-ary code is normal exactly when it is binary or trivial.

chapter_2_theorem_4: The norm of a perfect R-error-correcting q-ary code is qR when the code has one word and qR+q-1+(q-2)R otherwise, with respect to every coordinate.

chapter_2_theorem_5: The minimum distance of a subnormal q-ary code with covering radius R is at most (q/(q-1))R+1, so nonbinary nontrivial perfect codes are absubnormal.

chapter_2_theorem_6: Every subnormal ternary code of length n > 3 with covering radius 1 has at least 3^n/(2n) codewords, improving the sphere covering bound 3^n/(1+2n) for such codes.

chapter_3_corollary_2: A nontrivial perfect e-code in a mixed Hamming space can exist only if every difference of two alphabet sizes is divisible by e+1.

chapter_3_theorem_1: Van Wee's divisibility conditions on the alphabet sizes, radius and length of a nontrivial perfect code in a mixed Hamming space.

chapter_4_corollary_1: Every binary covering code of radius one with the least possible number of words is normal, with every coordinate acceptable.

chapter_4_theorem_1: In an optimal binary covering code of radius one and length at least 3, every punctured coordinate slice is nonempty and has covering radius at most 2.

chapter_4_theorem_2: A binary code with more than one word whose minimum distance is at least twice its covering radius is normal, with all coordinates acceptable.

chapter_4_theorem_4: Van Wee's generalization of Frankl's construction, giving abnormal binary codes with covering radius R for every R >= 1.

chapter_5_theorem_11: Van Wee's upper bound on the size of a q-ary code with packing radius e, which improves the sphere packing bound whenever (n-e)(q-1) is not divisible by e+1.

chapter_5_theorem_14: Van Wee's lower bounds on K_3(n,1), the football pool numbers, for n congruent to 2 or 0 modulo 3, with the resulting improvements for n = 8, 9, 11 and 12.

chapter_5_theorem_16: Van Wee's lower bound on the size of a code with covering radius 1 in the mixed space of t ternary and b binary coordinates, with separate forms for b even and b odd.

chapter_5_theorem_17: Van Wee's upper bound on the size of a code with packing radius 1 in the mixed space of t ternary and b binary coordinates, the packing counterpart of Theorem 16.

chapter_5_theorem_6: Van Wee's q-ary lower bound on K_q(n,R), which improves the sphere covering bound whenever (n-R)(q-1) is not divisible by R+1.

chapter_6_theorem_5: Van Lint and van Wee's inequality that every code of covering radius R in the mixed binary/ternary space must satisfy, which yields a lower bound on K(t,b,R) for every R.

chapter_6_theorem_9: Van Lint and van Wee's upper bound on the size of a code with packing radius e in the mixed binary/ternary space, for every e < t+b.

chapter_7_theorem_2: Van Wee, Cohen and Litsyn's constructions of perfect multiple coverings of radius one over prime-power alphabets, linear ones when n = (mu q^i - 1)/(q-1).

chapter_7_theorem_3: Van Wee, Cohen and Litsyn's determination of all parameters of linear perfect multiple 1-coverings over prime-power fields, and of all perfect multiple 1-coverings over alphabets of prime size.

chapter_7_theorem_4: Van Wee, Cohen and Litsyn's necessary conditions on a perfect multiple 1-covering over an alphabet of prime-power size whose parameters fall outside condition (7), giving mu >= p+q-1 in that case.

chapter_8_theorem_2: Pellikaan, Shen and van Wee's theorem that every linear code arises from Goppa's construction on some curve when no condition is placed on the degree of the divisor.

chapter_8_theorem_6: Pellikaan, Shen and van Wee's classification of the algebraic-geometric Hamming codes: H(1,q), H(2,q) and the binary [7,4,3] code H(3,2) are SAG, no other H(r,q) is AG, and H(3,2) has a unique minimal AG representation class.

---

Source and selected scope

G. J. M. van Wee, Covering codes, perfect codes, and codes from algebraic curves, doctoral dissertation, Eindhoven University of Technology (1991), DOI 10.6100/IR353803. The repository record identifies the file it serves as the version of record. The copy read for this card is that file: 220 pages in eight chapters. The file's first page is the repository's cover sheet, which states that "Copyright and moral rights for the publications made accessible in the public portal are retained by the authors and/or other copyright owners", that "Users may download and print one copy of any publication from the public portal for the purpose of private study or research" and that "You may not further distribute the material or use it for any profit-making activity or commercial gain", and indicates no license above that statement, every other right reserved.

The dissertation is an introduction followed by eight reprinted papers, one per chapter, which its Preface lists as: (1) "Improved sphere bounds on the covering radius of codes," IEEE Trans. Inform. Theory 34 (1988), 237–245; (2) with A. C. Lobstein, "On normal and subnormal $q$-ary codes," IEEE Trans. Inform. Theory 35 (1989), 1291–1295, and 36 (1990), 1498; (3) "On the non-existence of certain perfect mixed codes," Discrete Math. 87 (1991), 323–326; (4) "More binary covering codes are normal," IEEE Trans. Inform. Theory 36 (1990), 1466–1470; (5) "Bounds on packings and coverings by spheres in $q$-ary and mixed Hamming spaces," to appear in J. Combin. Theory Ser. A 56 (1991); (6) with J. H. van Lint, Jr., "Generalized bounds on binary/ternary mixed packing- and covering codes," to appear in J. Combin. Theory Ser. A 56 (1991); (7) with G. D. Cohen and S. N. Litsyn, "A note on perfect multiple coverings of the Hamming space," to appear in IEEE Trans. Inform. Theory 37 (1991); and (8) with R. Pellikaan and B. Z. Shen, "Which linear codes are algebraic-geometric?," to appear in IEEE Trans. Inform. Theory 37 (1991). Labels below and on the result pages are the chapters' own, which restart in each chapter; pages are the dissertation's printed page numbers, which run eight behind the file's page numbers.

This digest records the introduction's definitions and the Taussky–Todd question, Chapter 1's survey statements, and the main results of every chapter, each on its own result page (listed below). It makes no claim about the remaining numbered statements or the tables.

Covering-radius conventions

For an alphabet $Q$ of size $q\ge2$, the Hamming space is $Q^n$, and a code is a nonempty subset. Its covering radius is the exact maximum

$$\operatorname{CR}(C)=\max_{x\in Q^n}d(x,C), \qquad d(x,C)=\min_{c\in C}d(x,c).$$

The introduction defines $K_q(n,R)$ as the least size of a $q$-ary code of length $n$ with $\operatorname{CR}(C)=R$ (printed p. 4; PDF p. 12). Chapter 1 likewise calls a binary code an $(n,M)R$ code when its covering radius is exactly $R$ and defines $K(n,R)$ from that notation (printed p. 34; PDF p. 42). The statements below retain the notation printed in their respective sections.

Selected binary covering bounds

For $n\in\mathbb N$ and $R\in\{0,1,\ldots,n\}$, Chapter 1 defines $V_2(n,R)$ on printed p. 33 (PDF p. 41), and Theorem 1 (printed p. 34; PDF p. 42) gives the binary sphere bound

$$K(n,R)\ge\frac{2^n}{V_2(n,R)}, \qquad V_2(n,R)=\sum_{i=0}^{R}\binom ni.$$

Theorem 1 adds: "Equality holds in (6) if and only if a perfect $R$-error-correcting code of length $n$ exists" (printed p. 34), where (6) is the displayed bound. Theorem 2 on the same page records

$$K(R,R)=1\quad(R=1,2,\ldots),$$ $$K(n,R)=2\quad(n,R\in\mathbb N,\ R+1\le n\le2R+1),$$

and $K(n,0)=2^n$ for $n\in\mathbb N$.

For $n_1,n_2\in\mathbb N$ and $R_i\in\{0,1,\ldots,n_i\}$, Theorem 3 (printed p. 35; PDF p. 43) gives

$$K(n_1+n_2,R_1+R_2) \le K(n_1,R_1)K(n_2,R_2).$$

Its displayed special case is

$$K(n+1,R)\le2K(n,R) \qquad(n\in\mathbb N,\ 0\le R\le n).$$

Taussky–Todd group formulation

The introduction quotes Taussky and Todd's problem (printed p. 12; PDF p. 20): "Let $G$ be an abelian group with $n$ base elements $g_1,g_2,\ldots,g_n$, each of order $p$ (not necessarily a prime). Let $S$ denote the set of the $\nu=n(p-1)+1$ distinct powers of the base elements." The count $\nu$ takes the identity once, together with the $p-1$ nonidentity powers of each base element. Their Problem 1 asks for the least integer $\sigma=\sigma(n,p)$ for which some set $H\subseteq G$ of $\sigma$ elements satisfies

$$G=HS,$$

where $HS$ is the set of all products $hs$ with $h\in H$ and $s\in S$.

Normal binary codes

Let $C\subseteq\mathbb F_2^n$ have covering radius $R=\operatorname{CR}(C)$. For $a\in\mathbb F_2$, its unpunctured coordinate slice is

$$C_a^{(i)}=\{c\in C:c_i=a\}\subseteq\mathbb F_2^n.$$

Printed p. 75 (PDF p. 83) defines

$$N^{(i)}(C)= \max_{x\in\mathbb F_2^n} \bigl(d(x,C_0^{(i)})+d(x,C_1^{(i)})\bigr),$$

with the convention $d(x,\varnothing)=n$. Coordinate $i$ is acceptable if $N^{(i)}(C)\le2R+1$, and $C$ is normal if it has at least one acceptable coordinate.

The punctured slice $C_a^{(i)\prime}\subseteq\mathbb F_2^{n-1}$ is obtained by deleting coordinate $i$ from every word in $C_a^{(i)}$. In this chapter, optimal means $M=K(n,R)$. Chapter 4, Theorem 1 (printed p. 76; PDF p. 84) says that if $C$ is an optimal binary $(n,M)R$ code with $R=1$ and $n\ge3$, then for every coordinate $i$ and $a\in\mathbb F_2$,

$$C_a^{(i)\prime}\ne\varnothing \qquad\text{and}\qquad \operatorname{CR}\bigl(C_a^{(i)\prime}\bigr)\le2.$$

Corollary 1 (printed p. 79; PDF p. 87) concludes that every optimal binary radius-one code is normal and every coordinate is acceptable. Chapter 4, Theorem 2 on that page gives a broader binary criterion: if $|C|>1$ and

$$d_{\min}(C)\ge2\operatorname{CR}(C),$$

then $C$ is normal and every coordinate is acceptable.

Binary/ternary radius-one bound

Let $t,b$ be nonnegative integer coordinate counts. The premise of the result below has covering radius one, so it forces $t+b>0$. Put

$$\mathcal H=\mathbb F_3^t\times\mathbb F_2^b.$$

The mixed-space notation is introduced on printed p. 11 (PDF p. 19), and Chapter 5, Section V restates this space on printed p. 96 (PDF p. 104). Theorem 16 (printed p. 97; PDF p. 105) says that a code $C\subseteq\mathcal H$ with exact covering radius $\operatorname{CR}(C)=1$ satisfies

$$|C|\ge \frac{(2t+b)3^t2^b} {(2t+b)(1+2t+b)-b} \qquad\text{if $b$ is even},$$

and

$$|C|\ge \frac{(2t+b)3^t2^b} {(2t+b)(1+2t+b)-2t} \qquad\text{if $b$ is odd}.$$

The surrounding text says that this section treats only radius-one coverings in detail; higher-radius generalizations are attributed to separate joint work.

Result pages

Chapter 1, improved sphere bounds for binary covering codes:

• Theorem 9 (pp. 39–40): a lower bound on $K(n,R)$ for $n>R$ that beats the sphere bound when $n\not\equiv-1\pmod{R+1}$.
• Corollary 1 (p. 41): $K(n,1)\ge2^n/n$ for even $n$, and $K(2^r,1)=2^{(2^r-r)}$.
• Theorem 10 (pp. 43–44): a second lower bound on $K(n,R)$ for $n\ge2R$, with Corollary 2 (p. 46) for $R=1$.
• Theorem 12 (p. 48): $K(n+2,2)\le K(n,1)$ for $n\ge2$, $n\ne9$.
• Conjecture (p. 50): a perfect code of length $n$ would give $K_q(n+1,R)=qK_q(n,R)$.

Chapter 2, normal and subnormal $q$-ary codes:

• Theorem 4 (p. 62): the norm of a perfect $q$-ary code.
• Corollary 1 (p. 62): a $q$-ary perfect code is normal if and only if it is binary or trivial.
• Theorem 5 (p. 63): a subnormal code has $d\le qR/(q-1)+1$.
• Theorem 6 (p. 64): a subnormal ternary radius-one code of length $n>3$ has at least $3^n/2n$ words.

Chapter 3, perfect mixed codes:

• Theorem 1 (p. 71): divisibility conditions for a nontrivial perfect mixed $e$-code.
• Corollary 2 (p. 72): all differences $q_k-q_l$ must be divisible by $e+1$.

Chapter 4, normal binary codes:

• Theorem 1 (p. 76): slices of an optimal radius-one code have covering radius at most 2.
• Corollary 1 (p. 79): optimal binary radius-one codes are normal.
• Theorem 2 (p. 79): $d_{\min}(C)\ge2\operatorname{CR}(C)$ implies normal.
• Theorem 4 (p. 81): abnormal binary codes of every covering radius.

Chapter 5, packings and coverings in $q$-ary and mixed spaces:

• Theorem 6 (p. 89): improved $q$-ary sphere covering bound.
• Theorem 11 (p. 92): improved $q$-ary sphere packing bound.
• Theorem 14 (p. 94): football pool bounds, with Corollary 15 (p. 96).
• Theorem 16 (p. 97): binary/ternary radius-one covering bound.
• Theorem 17 (p. 98): binary/ternary radius-one packing bound.

Chapter 6, binary/ternary mixed codes of any radius:

• Theorem 5 (p. 105): covering inequality for every radius $R$.
• Theorem 9 (p. 109): packing bound for every radius $e$.

Chapter 7, perfect multiple coverings:

• Theorem 2 (p. 131): constructions of perfect multiple 1-coverings.
• Theorem 3 (p. 133): their parameters over prime alphabets and in the linear case.
• Theorem 4 (p. 135): conditions over prime-power alphabets, with Corollary 1 (p. 137).

Chapter 8, algebraic-geometric codes:

• Theorem 2 (p. 168): every linear code is weakly algebraic-geometric.
• Theorem 6 (p. 201): which Hamming codes are algebraic-geometric.

Read status. Claims checked: each result page records its own read depth; no proof is credited beyond what those pages state.

Relation to the library

This dissertation is a covering-code and coding-theory source.

Bears on. No Erdős problem: none of the results above concerns a numbered Erdős problem, and no problem page cites the dissertation.

No file of this source is held: no license on record permits its redistribution, and the card cites the edition it names above.