TheoremStatement: Literature-sourcedProof: AI-adaptedPipeline-generatedprecheck passjudge pass (gpt-6-sol)audited 2026-09-27

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 polynomial-time explicit constant-rate constant-distance code

Statement

There is a deterministic uniform binary code family $(C_{k})_{k \geq 1}$ in the sense of Explicit binary codes of constant rate and distance, with $N (k) < 128 k, rate > \frac{1}{128}, relative distance \geq \frac{1}{8},$ each encoder computable by one algorithm in time polynomial in $k$ . Thus the definition of an explicit constant-rate constant-distance family is met with $C_{0} = 128$ , $c_{0} = 1 / 128$ and $δ_{0} = 1 / 8$ , and these three constants are absolute.

Facts & Assumptions

Given: an integer $k \geq 1$ , the family of concatenated codes of Reed-Solomon outer code and binary linear inner code indexed by $m \geq 1$ , and the constants $K = q / 2$ , $q = 2^{m}$ .

[F1]

For every $m \geq 1$ the concatenated code of Reed-Solomon outer code and binary linear inner code encodes $K m = 2^{m - 1} m$ bits into $16 q m = 32 \cdot 2^{m - 1} m$ bits; it is defined after choosing the first irreducible polynomial of degree $m$ in a fixed enumeration and the inner matrix produced by the uniform procedure of Conditional expectation constructs the inner code deterministically, and its bit encoding of field elements is the power-basis encoding $e n c$ .

[F2]

The Reed-Solomon outer code has rate $1 / 2$ and relative distance at least $1 / 2$ (Reed-Solomon outer code has constant rate and distance).

[F3]

The inner code is injective and linear of rate $1 / 16$ and relative distance at least $1 / 4$ , and the matrix is produced deterministically in time polynomial in $2^{m} m$ (Conditional expectation constructs the inner code deterministically).

[F4]

The concatenation of an outer code of rate $R_{o}$ and relative distance $δ_{o}$ with an injective linear inner code of rate $R_{i}$ and relative distance $δ_{i}$ has rate $R_{o} R_{i}$ and relative distance at least $δ_{o} δ_{i}$ (Concatenation multiplies rate and relative distance).

[F5]

A binary code family with $N (k) \leq C_{0} k$ , rate at least $c_{0}$ and relative distance at least $δ_{0}$ , encoded by one deterministic algorithm running in time polynomial in $k$ , is an explicit constant-rate constant-distance family (Explicit binary codes of constant rate and distance).

Proof

technique · constructive

1.1

Define $m (k)$ to be the least integer $m \geq 1$ with $2^{m - 1} m \geq k$ ; it exists because $2^{m - 1} m \to \infty$ , and for $m \geq 2$ minimality gives $2^{m - 2} (m - 1) < k$ . Given $x \in {0, 1}^{k}$ , pad it by zeros to the length $K m = 2^{m - 1} m$ and apply the concatenated encoding of [F1], whose output length is $N (k) : = 32 \cdot 2^{m - 1} m$ .

F1construct

2.1

For $m \geq 2$ we have $2^{m - 1} m = 2 \cdot 2^{m - 2} m \leq 4 \cdot 2^{m - 2} (m - 1) < 4 k$ , using $m \leq 2 (m - 1)$ ; hence $N (k) < 128 k$ . The case $m = 1$ occurs exactly for $k = 1$ , where $N (1) = 32 < 128$ . The rate of the padded $k$ -bit family is $k / N (k) > 1 / 128$ ; $K m / N (k) = 1 / 32$ is the rate of the full concatenated code before restricting it to padded messages. The relative distance remains at least $\frac{1}{2} \cdot \frac{1}{4} = \frac{1}{8}$ by [F2], [F3] and [F4], because restricting an injective code to padded messages cannot decrease its minimum pairwise distance.

F1F2F3F4step 1.1algebra

2.2

The family is injective: the padding is injective and the concatenated encoding is injective by [F4]. It is uniform and deterministic: $m$ is determined by $k$ , the field and its bit encoding by [F1], the inner matrix by [F3], and no step uses randomness.

F1F3F4step 1.1

3.1

The running time is polynomial in $k$ : $m \leq 2 + \log_{2} k$ because $2^{m - 1} < 2 k$ for $m \geq 2$ ; the degree- $m$ irreducible polynomial is found by scanning at most $2^{m}$ monic polynomials and testing each by trial division, in $2^{m} 2^{m / 2} m^{2} \leq 2^{3 m / 2} m^{2}$ field operations; evaluating the outer code at all $q$ field elements costs $O (q K) = O (q^{2})$ field operations; the inner matrix is computed in time polynomial in $2^{m} m$ by [F3]; and applying it to the $q$ outer symbols costs $O (q m^{2})$ . Since $q = 2^{m} \leq 4 k$ and $m = O (\log k)$ , every term is polynomial in $k$ , so one algorithm serves all $k$ within polynomial time.

F1F3step 1.1step 2.1algebra

4.1

By [F5] the family, with its length function, rate, relative distance and polynomial-time uniform encoder verified in steps 2.1, 2.2 and 3.1, is an explicit constant-rate constant-distance binary code family with the stated constants.

F5step 2.1step 2.2step 3.1discharge-construct∎

Remarks

The constants. The full concatenated code has rate $1 / 32$ , the product of the outer rate $1 / 2$ and inner rate $1 / 16$ . Padding the $k$ input bits changes that rate to $k / N (k) > 1 / 128$ because $N (k) < 128 k$ ; the distance bound $1 / 8$ is the product $1 / 2 \cdot 1 / 4$ and survives restriction to padded inputs. None of these constants depends on $k$ .
What is not claimed. The theorem asserts neither a decoder nor a parity-check description of the family, and it does not optimise the constants; the page needs only that a constant-rate constant-distance family with a polynomial-time uniform encoder exists, which is what Explicit binary codes of constant rate and distance asks for.
Small lengths. The padding makes the family total: $k = 1$ is encoded by the length- $32$ concatenation with $m = 1$ , $q = 2$ and the length-two repetition outer code of Reed-Solomon outer code has constant rate and distance, so no separate small-case convention is needed beyond the zero padding.

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

13 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

Arora and Barak, Computational Complexity: A Modern Approach, §17.5.2-17.5.3 (Reed-Solomon and concatenated codes) and §19.2 (explicit codes), printed pp. 346-348 and 405-407. (standard reference, not scraped)
Irit Dinur, The PCP theorem by gap amplification, §9 (explicit binary code of constant rate and constant distance), printed pp. 29-31. (standard reference, not scraped)