ExampleConstruction: AI-adaptedVerification: AI-generatedPipeline-generatedjudge pass (gpt-6-luna)

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

A short Reed–Solomon code over $F_{5}$ and its symbol-error syndromes

Example

In $F_{5} = Z / 5 Z$ , evaluate the degree-less-than-two polynomials $f (x) = a + b x$ at $0, 1, 2, 3$ . This gives the Reed–Solomon evaluation code

$C = {(a, a + b, a + 2 b, a + 3 b) : a, b \in F_{5}} \subseteq F_{5}^{4},$

with encoding $(a, b) \mapsto (a, a + b, a + 2 b, a + 3 b)$ and generator/parity-check matrices

$G = [\begin{array}{cc} 1 & 0 \\ 1 & 1 \\ 1 & 2 \\ 1 & 3 \end{array}], H = [\begin{array}{cccc} 4 & 3 & 2 & 1 \\ 0 & 3 & 4 & 3 \end{array}] .$

It has parameters $[4, 2, 3]_{5}$ . Its four parity-check columns give distinct projective directions, so every one-symbol error value at every position has a distinct syndrome.

Facts & Assumptions

Given: The field $F_{5} = Z / 5 Z$ , evaluation points $0, 1, 2, 3$ , and matrices $G, H$ displayed above.

[F1]

For every prime $p$ , the two operations on $Z / p$ make it a field: For every prime $p$ , $Z / p Z$ is a field.

[F2]

Rectangular matrix multiplication and the identity matrix $I_{n}$ , including zero-sized shapes: Matrix products are the finite coordinate sums over the field.

[F3]

Rank-nullity: $\dim_{F} V = nullity T + rank T$ : The dimension of a finite-dimensional domain is the sum of kernel and image dimensions.

[F4]

If $\dim_{F} V = n$ and $U$ is a linear subspace of $V$ , then $U$ is finite-dimensional, $\dim_{F} U \leq n$ , and $\dim_{F} U = n$ if and only if $U = V$ : A subspace of a finite-dimensional space with equal dimension is the whole space.

[F5]

Row rank equals column rank, and both equal the number of pivots: The row rank and column rank of a finite matrix over a field are equal.

[L1]

A full-column-rank matrix has image dimension equal to its number of columns: The image of a full-column-rank $4 \times 2$ matrix has dimension $2$ .

[L2]

Syndrome of a received word over a finite field: A received vector's syndrome is $H r$ .

[L3]

Classical distance gives error detection, unique decoding, and erasure recovery: Distance $3$ uniquely decodes one unknown symbol error and distinct allowed errors have distinct syndromes.

Verification

1.1F1L1givenalgebra

The map $(a, b) \mapsto (a, a + b, a + 2 b, a + 3 b)$ is injective because its first two coordinates recover $a$ and $b$ . Hence the displayed $G$ has independent columns and [L1] gives $\dim C = 2$ .

1.2F2F5givenalgebra

Multiplication gives $H G = 0$ : the four row-column dot products are $10, 10, 10, 20$ , all zero in $F_{5}$ . The first two columns of $H$ , $(4, 0)$ and $(3, 3)$ , are independent, so its column rank is $2$ ; [F5] makes its row rank $2$ as well.

1.3givenalgebra

If $b = 0$ and $(a, b) \neq (0, 0)$ , then $f (x) = a$ has no roots. If $b \neq 0$ , the equation $a + b x = 0$ has the unique solution $x = - a b^{- 1}$ , so at most one of the four distinct evaluation points is a root. Every nonzero codeword therefore has weight at least $3$ , and $f (x) = x$ gives $(0, 1, 2, 3)$ of weight $3$ . Thus $d (C) = 3$ .

1.4F2givenalgebra

The columns of $H$ are $h_{0} = (4, 0)$ , $h_{1} = (3, 3)$ , $h_{2} = (2, 4)$ , and $h_{3} = (1, 3)$ . Their six pairwise determinants in $F_{5}$ are $2, 1, 2, 1, 1, 2$ , all nonzero, so no two are scalar multiples. A nonzero error $a e_{j}$ has syndrome $a h_{j}$ ; within one position distinct nonzero $a$ give distinct syndromes, and across positions equality would force proportional columns. Hence all $4 \cdot 4 = 16$ nonzero one-symbol errors have distinct syndromes.

2.1F3F4step 1.1step 1.2

Therefore $C = im G \subseteq \ker H$ . By [F3], $\dim \ker H = 4 - 2 = 2 = \dim C$ ; [F4] gives $C = \ker H$ .

3.1L2L3step 1.3step 1.4given∎

For example, the error $e = 2 e_{1}$ has syndrome $2 h_{1} = (6, 6) = (1, 1)$ in $F_{5}^{2}$ . Since $d (C) = 3$ , [L3] gives unique one-symbol correction. The example uses the evaluation-code definition; its exact distance and syndrome claims above are proved here rather than inferred from a source formula.

Remarks

The MIT lecture notes define Reed–Solomon codes by evaluating degree-less-than- $k$ polynomials at distinct field points. Their displayed root-count bound is one looser than the sharp degree bound needed to derive the stated exact distance formula; this example does not rely on it and proves its $[4, 2, 3]_{5}$ parameters directly.

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

59 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

Madhu Sudan, Essential Coding Theory, MIT 6.895, Lecture 5, “Reed-Solomon Codes” (Fall 2004) (standard reference, not scraped)
John Preskill, Quantum Computation, Chapter 7, §7.6 (standard reference, not scraped)

A short Reed–Solomon code over F5F5​ and its symbol-error syndromes