WikiLean · Articles Articles Brain Contribute About

Preliminary: these links have not yet had an independent audit.

Coding theory

35 passages8 formalized1 statement only6 partial20 not formalized

More ways to filter
Library
About this page

This page

  • Wikipedia revision 1374936394, pinned: the text here is that revision, not today's article.
  • WikiProject Mathematics: C-class, High importance
  • 35 passages checked, 22 Lean locations (and 10 related declarations).

Central statements: 21 of the 35 passages state the article's subject or a named result or definition; the other 14 are supporting (examples, setup). Of these 21: 5 formalized, 1 statement only, 4 partial, 11 not formalized.

What the colours mean

  • Formalized a Lean declaration states it, proved, or a Lean definition defines it
  • Statement only Lean states it, but the proof is not finished
  • Partial Lean states part of it, or a more general or special form
  • Not formalized searched every library and not found

Libraries searched

Searched 48 Lean libraries, pinned 2026-10-17, 3 left out (library set u1).

How these links were made

  • Accuracy, from an audit of a sample of 224 items (blind, not independent): Strong links (exact, close or broad match) on supporting passages that have exactly the right relation: 92% (95% interval 49–99%), from 36 drawn of 1029, weighted by relation and library, an effective sample of 5.1; Links in a counting relation (exact, close, broad, narrow match or part) on supporting passages that have exactly the right relation: 73% (95% interval 40–92%), from 48 drawn of 1740, weighted by relation and library, an effective sample of 8.1; Central and subject passages whose formalization status is right: 86% (95% interval 73–94%), from 44 drawn of 1905, weighted by recorded status, an effective sample of 42; 'Not formalized' on supporting passages that is right (no declaration in the 48 libraries states it): 60% (95% interval 25–87%), from 12 drawn of 1236, weighted by article, an effective sample of 6.1.
  • Audit run tierA-batch1-audit, run by jack, 2 Nov 2026, 21:10 – 3 Nov 2026, 02:10 UTC: judged by Claude Opus 5.5 (claude-opus-5-5).
  • Record set tierA-b1b (cf-locate-recordset/2, statuses by status rule 3), exported 1 Nov 2026 by formal-companion at commit d85385a.
  • Seal sha256 23710337d053e8212378a9e580805628bcdfda61a6fc431e65f24a4a16c9e602.
  • Inventory run inv-tierA-b1r, run by jack, 30 Oct 2026, 07:23–20:00 UTC: worker Claude Opus 5 (claude-opus-5), reviewer Claude Opus 5 (claude-opus-5). It listed the formal passages, each with its kind and prominence, that the locate run then searched.
  • Locate run loc-tierA-b1b, run by jack, 31 Oct 2026, 04:59 – 1 Nov 2026, 03:06 UTC: worker Claude Opus 5 (claude-opus-5), reviewer Claude Opus 5 (claude-opus-5).
  • Challenge run chal-tierA-b1, run by jack, 1 Nov 2026, 03:19–14:25 UTC: worker Claude Opus 5 (claude-opus-5), reviewer Claude Opus 5 (claude-opus-5). In this article it re-checked every Lean location and absence on a central or subject passage (12 locations and 12 absences); on supporting passages, a seeded sample (seed 0; drawn at 0.5 for strong matches, 0.2 for weaker links and 0.25 for absences): 5 of 10 locations and 3 of 9 absences. In all, 17 of 22 Lean locations (77%) and 15 of 21 absences (71%) were re-checked.
  • Passage text: 35 of 35 passages shown in full, each the slice of the pinned revision's text that its record's span sha256 hashes, checked when the store was built.
  • Lean code: each declaration's type, from the declaration corpus of universe u1 (built 18 Oct 2026, sha256 a364fd6aede5), at the commit its card links.

How the text is shown

Each passage is shown in full, as revision 1374936394 states it (checked against its record's span hash when the store was built). Where a passage is only part of a sentence, it is highlighted and the rest of the sentence is shown in grey around it, from the same copy of the revision; a list item also shows the sentence that introduces it. Formulas are drawn from their TeX; hover one to see it.

Each card's Lean code is its declaration's type as Lean prints it, from the declaration corpus of library set u1 at the card's commit, laid out as a header: binders before the colon, then the hypotheses as arrows (the corpus keeps no hypothesis names) and the conclusion, in Mathlib's notation (𝓝, π, R[X], Type*). It is not the source text; Source opens that.

Passages

What “exact match”, “more general” and the other labels mean
  1. Theorem · main statement · History of coding theory

    Statement only

    With community edits: Statement only. As published it is Not formalized.

    Statement only, by a community edit: TauCeti states this up to a convention difference (statement only: the proof is not finished).

    It is an error-correcting code capable of correcting up to three errors in each 24-bit word, and detecting a fourth.

    Show in article · Read it in context on Wikipedia

    TauCeti.BinaryGolay.hammingMinDist_code close match

    No module or line: an editor named the declaration, not a place in the source.

    TauCeti

    Community Agent Added by Meta FAIR 2 (agent) — owned by Jack McCarthy on 9 Nov 2026

    Why close, not exact: The passage describes the extended binary Golay code on 24-bit words. This theorem proves that code has minimum Hamming distance 8. Convention difference: the passage states an error-handling capability, while the theorem states a minimum distance. A code corrects up to t errors and detects t+1 exactly when its minimum distance is at least 2t+2, which is 8 for t = 3. The theorem does not state the decoding step itself. Proved, no sorry.

    Searched 48 libraries — not found. Which libraries, at which commits (pinned 2026-10-17).

    Details
    • Searched by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run loc-tierA-b1b by jack: the search receipt lists 5 queries and 5 candidates examined (receipt b3887596a2a3).
    • Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run chal-tierA-b1 by jack: upheld.
  2. Definition · main statement · Source coding › Definition

    Not formalized
    Data can be seen as a random variable X : Ω → 𝒳, where x ∈ 𝒳 appears with probability ℙ[X = x].

    Show in article · Read it in context on Wikipedia

    Searched 48 libraries — not found. Which libraries, at which commits (pinned 2026-10-17).

    Details
    • Searched by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run loc-tierA-b1b by jack: the search receipt lists 4 queries and 4 candidates examined (receipt 3a1713d84519).
    • Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run chal-tierA-b1 by jack: upheld.
  3. Definition · supporting · Source coding › Definition

    Formalized

    Formalized: Lean core states this up to a convention difference (a definition).

    Data are encoded by strings (words) over an alphabet Σ.

    Show in article · Read it in context on Wikipedia

    List close match

    inductive List : Type u → Type u

    Init.Prelude · lines 3116–3123

    Why close, not exact: Lean carries a word over the alphabet as a finite sequence of its symbols, which is the object the article writes with a star; nothing else differs.

    Details
    • Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run loc-tierA-b1b by jack: candidate 1 for this passage, medium confidence.
    • Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run chal-tierA-b1 by jack: it survived.
    • Record set tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a.
    • Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit c9afcdd.
    • Location key 43bb80cc3daf · pair key d078b1b47e35.

    FreeMonoid close match

    def FreeMonoid : Type u_6 → Type u_6

    Mathlib.Algebra.FreeMonoid.Basic · line 65

    Why close, not exact: Mathlib packages the words over an alphabet together with their concatenation as a monoid, its underlying elements being the finite sequences of symbols the article denotes with a star.

    Details
    • Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run loc-tierA-b1b by jack: candidate 2 for this passage, medium confidence.
    • Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run chal-tierA-b1 by jack: it survived.
    • Record set tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a.
    • Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit 3dfb8e2.
    • Location key 3a59e568af4a · pair key 65fe9877199f.
  4. Definition · main statement · Source coding › Definition

    Not formalized
    A code is a function
    C : 𝒳 → Σ∗ (or Σ+ if the empty string is not part of the alphabet).

    Show in article · Read it in context on Wikipedia

    Searched 48 libraries — not found. Which libraries, at which commits (pinned 2026-10-17).

    Details
    • Searched by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run loc-tierA-b1b by jack: the search receipt lists 4 queries and 4 candidates examined (receipt 5efb328cd787).
    • Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run chal-tierA-b1 by jack: upheld.
  5. Notation · supporting · Source coding › Definition

    Not formalized
    C(x) is the code word associated with x.

    Show in article · Read it in context on Wikipedia

    Searched 48 libraries — not found. Which libraries, at which commits (pinned 2026-10-17).

    Details
    • Searched by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run loc-tierA-b1b by jack: the search receipt lists 4 queries and 3 candidates examined (receipt e9f449d7c9a8).
    • Not re-checked: sampled out of challenge run chal-tierA-b1 by jack, in which Claude Opus 5 (claude-opus-5) re-checked a sample on 1 Nov 2026 (UTC).
  6. Notation · supporting · Source coding › Definition

    Formalized

    Formalized: Lean core states this up to a convention difference (a definition).

    Length of the code word is written as l(C(x)).

    Show in article · Read it in context on Wikipedia

    List.length close match

    def List.length {α : Type u_1} : List α → Nat

    Init.Prelude · lines 3201–3203

    Why close, not exact: Lean writes the symbol count of a word in postfix form on the word itself, with words of the alphabet carried as finite sequences of symbols.

    Details
    • Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run loc-tierA-b1b by jack: candidate 1 for this passage, medium confidence.
    • Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run chal-tierA-b1 by jack: it survived.
    • Record set tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a.
    • Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit c9afcdd.
    • Location key 95ce4b53687f · pair key ede2c949f107.
  7. Definition · main statement · Source coding › Definition

    Not formalized
    Expected length of a code is l(C) = ∑x ∈ 𝒳 l(C(x))ℙ[X = x].

    Show in article · Read it in context on Wikipedia

    Searched 48 libraries — not found. Which libraries, at which commits (pinned 2026-10-17).

    Details
    • Searched by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run loc-tierA-b1b by jack: the search receipt lists 4 queries and 4 candidates examined (receipt 7858f4f9b14d).
    • Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run chal-tierA-b1 by jack: upheld.
  8. Definition · supporting · Source coding › Definition

    Formalized

    Formalized: Lean core states this up to a convention difference (a definition).

    The concatenation of code words C(x1, …, xk) = C(x1)C(x2)⋯C(xk).

    Show in article · Read it in context on Wikipedia

    List.flatMap close match

    def List.flatMap {α : Type u} {β : Type v} : (α → List β) → List α → List β

    Init.Prelude · line 3332

    Why close, not exact: Lean's operation sends each entry of a sequence through the given map and joins the resulting words end to end, with words carried as finite sequences of symbols.

    Details
    • Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run loc-tierA-b1b by jack: candidate 1 for this passage, medium confidence.
    • Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run chal-tierA-b1 by jack: it survived.
    • Record set tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a.
    • Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit c9afcdd.
    • Location key 6b4e8d402e19 · pair key 62735fe804d2.

    FreeMonoid.lift more general

    def FreeMonoid.lift {α : Type*} {M : Type*} [Monoid M] : (α → M) ≃ (FreeMonoid α →* M)

    Mathlib.Algebra.FreeMonoid.Basic · lines 309–314

    Why more general: Mathlib states the extension for an arbitrary monoid target and bundles it as a homomorphism together with the claim that this extension is the only one, which is beyond the single equation the passage records.

    Details
    • Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run loc-tierA-b1b by jack: candidate 2 for this passage, medium confidence.
    • Not re-checked: sampled out of challenge run chal-tierA-b1 by jack, in which Claude Opus 5 (claude-opus-5) re-checked a sample on 1 Nov 2026 (UTC).
    • Record set tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a.
    • Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit 3dfb8e2.
    • Location key 39408bf2417d · pair key 603809cf09b4.

    Cslib.Algorithms.Lean.HuffmanTree.encode_codeOfLeaf special case

    theorem Cslib.Algorithms.Lean.HuffmanTree.encode_codeOfLeaf {α : Type u} [DecidableEq α] (tree : Cslib.Algorithms.Lean.HuffmanTree α) (message : List tree.LeafSymbol) : tree.encode? (List.map Subtype.val message) = Option.some (List.flatMap tree.codeOfLeaf message)

    CSLibExt.Algorithms.Lean.Greedy.Huffman · line 344

    Why a special case: This is the passage's extension equation written for one particular family of codes, with the encoder's result wrapped as an optional value.

    Details
    • Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run loc-tierA-b1b by jack: candidate 3 for this passage, medium confidence.
    • Not re-checked: sampled out of challenge run chal-tierA-b1 by jack, in which Claude Opus 5 (claude-opus-5) re-checked a sample on 1 Nov 2026 (UTC).
    • Record set tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a.
    • Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit 64c2773.
    • Location key a1b39321b1c2 · pair key 415f58633b67.
  9. Definition · supporting · Source coding › Definition

    Partial

    Partial: Lean core states a more general result, but as a proved theorem, not a definition; a definition passage is formalized only by a Lean definition.

    The code word of the empty string is the empty string itself: C(ϵ) = ϵ

    Show in article · Read it in context on Wikipedia

    List.flatMap_nil more general

    theorem List.flatMap_nil {α : Type u} {β : Type v} {f : α → List β} : List.flatMap f [] = []

    Init.Data.List.Basic · line 679

    Why more general: Lean core states the equation for any map from symbols to words, with the empty source string written as the empty list.

    Details
    • Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run loc-tierA-b1b by jack: candidate 1 for this passage, medium confidence.
    • Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run chal-tierA-b1 by jack: it survived.
    • Record set tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a.
    • Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit c9afcdd.
    • Location key 6fd34a901a21 · pair key f4bbddb045ee.
  10. Definition · main statement · Source coding › Properties

    Formalized

    Formalized: Lean core states a more general result (a Prop-valued definition: it states the claim without proving it).

    C : 𝒳 → Σ∗ is non-singular if injective.

    Show in article · Read it in context on Wikipedia

    Function.Injective more general

    def Function.Injective {α : Sort u_1} {β : Sort u_2} : (α → β) → Prop

    Init.Data.Function · lines 53–54

    Why more general: Lean core fixes the notion for a function between arbitrary sorts, under the name injective rather than non-singular.

    Details
    • Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run loc-tierA-b1b by jack: candidate 1 for this passage, medium confidence.
    • Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run chal-tierA-b1 by jack: it survived.
    • Record set tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a.
    • Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit c9afcdd.
    • Location key 444a90aad5e8 · pair key 1bced5ffd38a.
  11. Definition · main statement · Source coding › Properties

    Formalized

    Formalized: Lean core states a more general result (a Prop-valued definition: it states the claim without proving it).

    C : 𝒳∗ → Σ∗ is uniquely decodable if injective.

    Show in article · Read it in context on Wikipedia

    Function.Injective more general

    def Function.Injective {α : Sort u_1} {β : Sort u_2} : (α → β) → Prop

    Init.Data.Function · lines 53–54

    Why more general: Lean core fixes the notion for a map between arbitrary sorts, under the name injective.

    Details
    • Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run loc-tierA-b1b by jack: candidate 1 for this passage, medium confidence.
    • Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run chal-tierA-b1 by jack: it survived.
    • Record set tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a.
    • Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit c9afcdd.
    • Location key 061f865cb3c0 · pair key 5a29a387d97a.
  12. Definition · main statement · Source coding › Properties

    Formalized

    Formalized: ATLAS (atlas-lean) states this up to a convention difference (a Prop-valued definition: it states the claim without proving it).

    C : 𝒳 → Σ∗ is instantaneous if C(x1) is not a proper prefix of C(x2) (and vice versa).

    Show in article · Read it in context on Wikipedia

    MathlibExt.InformationTheory.IsPrefixFree close match

    def MathlibExt.InformationTheory.IsPrefixFree {α : Type*} {β : Type*} : (α → List β) → Prop

    MathlibExt.InformationTheory.PrefixFree · line 20

    Why close, not exact: Atlas gives the property the name prefix-free and quantifies over ordered pairs of distinct symbols; its prefix relation admits equality, so distinct symbols also receive distinct words.

    Details
    • Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run loc-tierA-b1b by jack: candidate 1 for this passage, medium confidence.
    • Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run chal-tierA-b1 by jack: it survived.
    • Record set tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a.
    • Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit 64c2773.
    • Location key 2d96c6f553cd · pair key 0e6994fb8a94.

    InformationTheory.IsPrefixFree close match

    def InformationTheory.IsPrefixFree {α : Type*} : Set (List α) → Prop

    Mathlib.InformationTheory.Coding.PrefixFree · lines 36–37

    Why close, not exact: Mathlib states the property of the set of code words rather than of the indexed map, and its words are lists over the alphabet.

    Details
    • Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run loc-tierA-b1b by jack: candidate 2 for this passage, medium confidence.
    • Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run chal-tierA-b1 by jack: it survived.
    • Record set tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a.
    • Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit 3dfb8e2.
    • Location key 9dd57b787f59 · pair key aebcbb5057d2.
  13. Definition · main statement · Source coding › Principle

    Partial

    Partial: Formal Conjectures states a special case (a definition).

    Entropy of a source is the measure of information.

    Show in article · Read it in context on Wikipedia

    InformationTheory.shannonEntropyBits special case

    def InformationTheory.shannonEntropyBits {Ω : Type*} [MeasurableSpace Ω] {α : Type*} [Fintype α] : MeasureTheory.Measure Ω → (Ω → α) → ℝ

    FormalConjecturesForMathlib.InformationTheory.FiniteEntropy · lines 65–67

    Why a special case: The declaration fixes a finite value alphabet and base-two logarithms, and gives zero weight to values of probability zero.

    Details
    • Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run loc-tierA-b1b by jack: candidate 1 for this passage, medium confidence.
    • Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run chal-tierA-b1 by jack: it survived.
    • Record set tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a.
    • Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit e754a78.
    • Location key 100d69629a75 · pair key 22af97383eda.

    CourtadeKumar.entropy special case

    def CourtadeKumar.entropy {α : Type*} [Fintype α] : (α → ℝ) → ℝ

    FormalConjectures.Paper.CourtadeKumar · lines 106–107

    Why a special case: The declaration takes the distribution itself as argument and measures entropy in bits over a finite type.

    Details
    • Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run loc-tierA-b1b by jack: candidate 2 for this passage, low confidence.
    • Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run chal-tierA-b1 by jack: it survived.
    • Record set tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a.
    • Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit e754a78.
    • Location key 6cf56fceb698 · pair key 8ab4a7c1dffe.
  14. Definition · main statement · Source coding › Principle

    Not formalized
    Data compression which explicitly tries to minimize the average length of messages according to a particular assumed probability model is called entropy encoding.

    Show in article · Read it in context on Wikipedia

    Searched 48 libraries — not found. Which libraries, at which commits (pinned 2026-10-17).

    Details
    • Searched by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run loc-tierA-b1b by jack: the search receipt lists 4 queries and 2 candidates examined (receipt f43b697def60).
    • Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run chal-tierA-b1 by jack: upheld.
  15. Theorem · main statement · Source coding › Principle

    Partial

    Partial: ATLAS (atlas-lean) states a special case (proved).

    C(x) ≥ H(x), where H(x) is entropy of source (bitrate), and C(x) is the bitrate after compression.

    Show in article · Read it in context on Wikipedia

    MathlibExt.InformationTheory.ShannonSourceCodingWanted.shannon_source_coding_lower_bound special case

    theorem MathlibExt.InformationTheory.ShannonSourceCodingWanted.shannon_source_coding_lower_bound {α : Type*} {β : Type*} [Fintype α] [Fintype β] (p : α → ℝ) : (∀ (a : α), 0 < p a) → ∑ a, p a = 1 → 2 ≤ Fintype.card β → ∀ (code : α → List β), Function.Injective code → InformationTheory.IsUniquelyDecodable (Set.range code) → (-∑ a, p a * Real.log (p a)) / Real.log ↑(Fintype.card β) ≤ ∑ a, p a * ↑(code a).length

    MathlibExt.InformationTheory.ShannonSourceCoding · line 150

    Why a special case: Atlas restricts to finite alphabets, strictly positive probabilities and uniquely decodable codes, and measures entropy in units set by the size of the code alphabet rather than in bits.

    Details
    • Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run loc-tierA-b1b by jack: candidate 1 for this passage, medium confidence.
    • Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run chal-tierA-b1 by jack: it survived.
    • Record set tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a.
    • Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit 64c2773.
    • Location key 81c98f8a4f61 · pair key 0700daed7d45.
  16. Theorem · main statement · Source coding › Principle

    Partial

    Partial: ATLAS (atlas-lean) states a special case (proved).

    In particular, no source coding scheme can be better than the entropy of the source.

    Show in article · Read it in context on Wikipedia

    MathlibExt.InformationTheory.ShannonSourceCodingWanted.shannon_source_coding_lower_bound special case

    theorem MathlibExt.InformationTheory.ShannonSourceCodingWanted.shannon_source_coding_lower_bound {α : Type*} {β : Type*} [Fintype α] [Fintype β] (p : α → ℝ) : (∀ (a : α), 0 < p a) → ∑ a, p a = 1 → 2 ≤ Fintype.card β → ∀ (code : α → List β), Function.Injective code → InformationTheory.IsUniquelyDecodable (Set.range code) → (-∑ a, p a * Real.log (p a)) / Real.log ↑(Fintype.card β) ≤ ∑ a, p a * ↑(code a).length

    MathlibExt.InformationTheory.ShannonSourceCoding · line 150

    Why a special case: Atlas covers the coding schemes given by uniquely decodable injective codes on finite alphabets, with entropy in units set by the code alphabet.

    Details
    • Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run loc-tierA-b1b by jack: candidate 1 for this passage, medium confidence.
    • Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run chal-tierA-b1 by jack: it survived.
    • Record set tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a.
    • Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit 64c2773.
    • Location key ebe2116eae3b · pair key 875bd37b6ffc.
  17. Definition · main statement · Channel coding › Linear codes › Linear block codes

    Formalized

    Formalized: TauCeti states a more general result (a definition).

    Linear block codes have the property of linearity, i.e. the sum of any two codewords is also a code word, and they are applied to the source bits in blocks, hence the name linear block codes.

    Show in article · Read it in context on Wikipedia

    TauCeti.LinearCode more general

    abbrev TauCeti.LinearCode (F : Type u_1) : Type u_2 → [Field F] → Type (max u_1 u_2)

    TauCeti.InformationTheory.Coding.Basic · line 31

    Why more general: TauCeti writes a linear code as a submodule of the word space of functions from coordinates to alphabet symbols, so the set of code words is carried together with the proofs that it holds zero and is closed under sums and scalar multiples.

    Details
    • Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run loc-tierA-b1b by jack: candidate 1 for this passage, high confidence.
    • Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run chal-tierA-b1 by jack, which downgraded it.
    • Record set tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a.
    • Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit 83245ab.
    • Location key d312413fd2ae · pair key 5de63df5a9c9.

    Submodule.add_mem more general

    theorem Submodule.add_mem {R : Type u} {M : Type v} [Semiring R] [AddCommMonoid M] {module_M : _root_.Module R M} (p : Submodule R M) {x y : M} : x ∈ p → y ∈ p → x + y ∈ p

    Mathlib.Algebra.Module.Submodule.Defs · lines 209–210

    Why more general: Mathlib states the closure of a submodule under addition for any module, and a linear block code is one such submodule of its word space.

    Details
    • Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run loc-tierA-b1b by jack: candidate 2 for this passage, medium confidence.
    • Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run chal-tierA-b1 by jack: it survived.
    • Record set tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a.
    • Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit 3dfb8e2.
    • Location key 507eeb51edcd · pair key 0937a19b80c1.
  18. Theorem · supporting · Channel coding › Linear codes › Linear block codes

    Not formalized
    There are block codes that are not linear, but it is difficult to prove that a code is a good one without this property.

    Show in article · Read it in context on Wikipedia

    Searched 48 libraries — not found. Which libraries, at which commits (pinned 2026-10-17).

    Details
    • Searched by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run loc-tierA-b1b by jack: the search receipt lists 4 queries and 3 candidates examined (receipt c3f5c99da6df).
    • Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run chal-tierA-b1 by jack: upheld.
  19. Notation · main statement · Channel coding › Linear codes › Linear block codes

    Partial

    Partial: TauCeti states a special case (proved).

    Linear block codes are summarized by their symbol alphabets (e.g., binary or ternary) and parameters (n,m,dmin)[5] where

    Show in article · Read it in context on Wikipedia

    TauCeti.BinaryGolay.parameters_punctureAt_code special case

    theorem TauCeti.BinaryGolay.parameters_punctureAt_code (i : Fin 24) : (Fintype.card ↑{i}ᶜ, Module.finrank (ZMod 2) ↥(TauCeti.punctureAt TauCeti.BinaryGolay.code i), (↑(TauCeti.punctureAt TauCeti.BinaryGolay.code i)).hammingMinDist) = (23, 12, 7)

    TauCeti.InformationTheory.Coding.Binary.Golay.Punctured · lines 59–64

    Why a special case: TauCeti forms the parameter triple only for this one code, with the alphabet carried by the code's type rather than named beside the triple.

    Details
    • Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run loc-tierA-b1b by jack: candidate 1 for this passage, medium confidence.
    • Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run chal-tierA-b1 by jack: it survived.
    • Record set tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a.
    • Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit 83245ab.
    • Location key 9e145ec65047 · pair key c4f163f1989f.
  20. Definition · supporting · Channel coding › Linear codes › Linear block codes

    Partial

    Partial: TauCeti states part of this (a definition).

    Linear block codes are summarized by their symbol alphabets (e.g., binary or ternary) and parameters (n,m,dmin)[5] where
    n is the length of the codeword, in symbols, m is the number of source symbols that will be used for encoding at once, dmin is the minimum hamming distance for the code.

    Show in article · Read it in context on Wikipedia

    Set.hammingMinDist states part

    def Set.hammingMinDist {ι : Type*} {β : ι → Type*} [Fintype ι] [(i : ι) → DecidableEq (β i)] : Set ((i : ι) → β i) → ℕ

    TauCeti.InformationTheory.Coding.MinimumDistance.Basic · lines 45–46

    Why only part: TauCeti defines this for any set of words over a finite coordinate set, with position-dependent symbol types, and returns zero when the set holds no two distinct words.

    Details
    • Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run loc-tierA-b1b by jack: candidate 1 for this passage, high confidence.
    • Not re-checked: sampled out of challenge run chal-tierA-b1 by jack, in which Claude Opus 5 (claude-opus-5) re-checked a sample on 1 Nov 2026 (UTC).
    • Record set tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a.
    • Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit 83245ab.
    • Location key c4573ffdc11f · pair key aeb592cd99ba.

    MathlibExt.Combinatorics.GoodLTCodesWanted.GoodLTC.BinaryCode states part

    abbrev MathlibExt.Combinatorics.GoodLTCodesWanted.GoodLTC.BinaryCode : ℕ → Type

    WantedExt.Combinatorics.GoodLTCodesWanted · line 64

    Why only part: Its alphabet is pinned to the two-element field, where the passage leaves the symbol alphabet open.

    Details
    • Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run loc-tierA-b1b by jack: candidate 2 for this passage, medium confidence.
    • Not re-checked: sampled out of challenge run chal-tierA-b1 by jack, in which Claude Opus 5 (claude-opus-5) re-checked a sample on 1 Nov 2026 (UTC).
    • Record set tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a.
    • Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit 64c2773.
    • Location key ae9074c37ad5 · pair key 04d0b902d929.

    TauCeti.LinearCode.IsGeneratorMatrix.encodingEquiv states part

    def TauCeti.LinearCode.IsGeneratorMatrix.encodingEquiv {F : Type*} {ι : Type*} {ρ : Type*} [Field F] [Fintype ρ] {C : TauCeti.LinearCode F ι} {G : Matrix ρ ι F} : C.IsGeneratorMatrix G → LinearIndependent F G.row → (ρ → F) ≃ₗ[F] ↥C

    TauCeti.InformationTheory.Coding.Matrix · lines 387–389

    Why only part: It assumes a chosen generator matrix whose rows are independent, a choice every linear block code admits.

    Details
    • Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run loc-tierA-b1b by jack: candidate 3 for this passage, medium confidence.
    • Not re-checked: sampled out of challenge run chal-tierA-b1 by jack, in which Claude Opus 5 (claude-opus-5) re-checked a sample on 1 Nov 2026 (UTC).
    • Record set tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a.
    • Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit 83245ab.
    • Location key 080ee92941de · pair key 0e285cd89b51.
  21. Theorem · supporting · Channel coding › Linear codes › Linear block codes

    Not formalized
    The result is a hexagon pattern like a bee's nest.

    Show in article · Read it in context on Wikipedia

    Searched 48 libraries — not found. Which libraries, at which commits (pinned 2026-10-17).

    Details
    • Searched by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run loc-tierA-b1b by jack: the search receipt lists 3 queries and 2 candidates examined (receipt d99bb6cbb868).
    • Not re-checked: sampled out of challenge run chal-tierA-b1 by jack, in which Claude Opus 5 (claude-opus-5) re-checked a sample on 1 Nov 2026 (UTC).
  22. Theorem · main statement · Channel coding › Linear codes › Linear block codes

    Formalized

    Formalized: TauCeti states this up to a convention difference (proved).

    The powerful (24,12) Golay code used in deep space communications uses 24 dimensions.

    Show in article · Read it in context on Wikipedia

    TauCeti.BinaryGolay.finrank_code close match

    theorem TauCeti.BinaryGolay.finrank_code : Module.finrank (ZMod 2) ↥TauCeti.BinaryGolay.code = 12

    TauCeti.InformationTheory.Coding.Binary.Golay.Basic · lines 136–138

    Why close, not exact: Lean carries the block length as the index type of 24 coordinates in the code's type rather than as a numeral, and the declaration states the remaining parameter, the dimension twelve.

    Details
    • Found by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run loc-tierA-b1b by jack: candidate 1 for this passage, medium confidence.
    • Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run chal-tierA-b1 by jack: it survived.
    • Record set tierA-b1b, exported 1 Nov 2026 by formal-companion d85385a.
    • Lean code: the declaration's type as Lean prints it, laid out as a header (the corpus keeps no hypothesis names), from the declaration corpus of universe u1 at commit 83245ab.
    • Location key 303749c3a6d0 · pair key e4374710e903.
  23. Theorem · supporting · Channel coding › Linear codes › Linear block codes

    Not formalized
    For example, hexagon packing into the constraint of a rectangular box will leave empty space at the corners.

    Show in article · Read it in context on Wikipedia

    Searched 48 libraries — not found. Which libraries, at which commits (pinned 2026-10-17).

    Details
    • Searched by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run loc-tierA-b1b by jack: the search receipt lists 3 queries and 2 candidates examined (receipt fb58df7eb3ca).
    • Not re-checked: sampled out of challenge run chal-tierA-b1 by jack, in which Claude Opus 5 (claude-opus-5) re-checked a sample on 1 Nov 2026 (UTC).
  24. Theorem · supporting · Channel coding › Linear codes › Linear block codes

    Not formalized
    As the dimensions get larger, the percentage of empty space grows smaller.

    Show in article · Read it in context on Wikipedia

    Searched 48 libraries — not found. Which libraries, at which commits (pinned 2026-10-17).

    Details
    • Searched by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run loc-tierA-b1b by jack: the search receipt lists 3 queries and 3 candidates examined (receipt d9906a225947).
    • Not re-checked: sampled out of challenge run chal-tierA-b1 by jack, in which Claude Opus 5 (claude-opus-5) re-checked a sample on 1 Nov 2026 (UTC).
  25. Definition · main statement · Channel coding › Linear codes › Linear block codes

    Not formalized
    But at certain dimensions, the packing uses all the space and these codes are the so-called "perfect" codes.

    Show in article · Read it in context on Wikipedia

    Searched 48 libraries — not found. Which libraries, at which commits (pinned 2026-10-17).

    Details
    • Searched by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run loc-tierA-b1b by jack: the search receipt lists 5 queries and 3 candidates examined (receipt 0bcdc4cbbe57).
    • Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run chal-tierA-b1 by jack: upheld.
  26. Theorem · main statement · Channel coding › Linear codes › Linear block codes

    Not formalized
    The only nontrivial and useful perfect codes are the distance-3 Hamming codes with parameters satisfying (2r – 1, 2r – 1 – r, 3), and the [23,12,7] binary and [11,6,5] ternary Golay codes.

    Show in article · Read it in context on Wikipedia

    Searched 48 libraries — not found. Which libraries, at which commits (pinned 2026-10-17).

    Details
    • Searched by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run loc-tierA-b1b by jack: the search receipt lists 3 queries and 0 candidates examined (receipt c6a211a900ad).
    • Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run chal-tierA-b1 by jack: upheld.
  27. Definition · main statement · Channel coding › Linear codes › Linear block codes

    Not formalized
    Another code property is the number of neighbors that a single codeword may have.[6]

    Show in article · Read it in context on Wikipedia

    Searched 48 libraries — not found. Which libraries, at which commits (pinned 2026-10-17).

    Details
    • Searched by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run loc-tierA-b1b by jack: the search receipt lists 3 queries and 2 candidates examined (receipt 3e51585a06e3).
    • Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run chal-tierA-b1 by jack: upheld.
  28. Theorem · supporting · Channel coding › Linear codes › Linear block codes

    Not formalized
    Each penny will have 4 near neighbors (and 4 at the corners which are farther away).

    Show in article · Read it in context on Wikipedia

    Searched 48 libraries — not found. Which libraries, at which commits (pinned 2026-10-17).

    Details
    • Searched by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run loc-tierA-b1b by jack: the search receipt lists 4 queries and 2 candidates examined (receipt cdd3439b1ca4).
    • Not re-checked: sampled out of challenge run chal-tierA-b1 by jack, in which Claude Opus 5 (claude-opus-5) re-checked a sample on 1 Nov 2026 (UTC).
  29. Theorem · supporting · Channel coding › Linear codes › Linear block codes

    Not formalized
    In a hexagon, each penny will have 6 near neighbors.

    Show in article · Read it in context on Wikipedia

    Searched 48 libraries — not found. Which libraries, at which commits (pinned 2026-10-17).

    Details
    • Searched by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run loc-tierA-b1b by jack: the search receipt lists 4 queries and 2 candidates examined (receipt 32f8e0e9692a).
    • Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run chal-tierA-b1 by jack: upheld.
  30. Theorem · supporting · Channel coding › Linear codes › Linear block codes

    Not formalized
    When we increase the dimensions, the number of near neighbors increases very rapidly.

    Show in article · Read it in context on Wikipedia

    Searched 48 libraries — not found. Which libraries, at which commits (pinned 2026-10-17).

    Details
    • Searched by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run loc-tierA-b1b by jack: the search receipt lists 3 queries and 2 candidates examined (receipt 1092a35b63df).
    • Not re-checked: sampled out of challenge run chal-tierA-b1 by jack, in which Claude Opus 5 (claude-opus-5) re-checked a sample on 1 Nov 2026 (UTC).
  31. Definition · main statement · Channel coding › Linear codes › Convolutional codes

    Not formalized
    The idea behind a convolutional code is to make every codeword symbol be the weighted sum of the various input message symbols.

    Show in article · Read it in context on Wikipedia

    Searched 48 libraries — not found. Which libraries, at which commits (pinned 2026-10-17).

    Details
    • Searched by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run loc-tierA-b1b by jack: the search receipt lists 4 queries and 2 candidates examined (receipt eb413d19a20a).
    • Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run chal-tierA-b1 by jack: upheld.
  32. Theorem · main statement · Channel coding › Linear codes › Convolutional codes

    Not formalized
    The Viterbi algorithm is the optimum algorithm used to decode convolutional codes.

    Show in article · Read it in context on Wikipedia

    Searched 48 libraries — not found. Which libraries, at which commits (pinned 2026-10-17).

    Details
    • Searched by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run loc-tierA-b1b by jack: the search receipt lists 4 queries and 2 candidates examined (receipt 86bb321bf368).
    • Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run chal-tierA-b1 by jack: upheld.
  33. Definition · supporting · Cryptographic coding

    Not formalized
    These schemes are therefore termed computationally secure; theoretical advances, e.g., improvements in integer factorization algorithms, and faster computing technology require these solutions to be continually adapted.

    Show in article · Read it in context on Wikipedia

    Searched 48 libraries — not found. Which libraries, at which commits (pinned 2026-10-17).

    Details
    • Searched by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run loc-tierA-b1b by jack: the search receipt lists 3 queries and 1 candidates examined (receipt 71f90fd0f411).
    • Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run chal-tierA-b1 by jack: upheld.
  34. Theorem · main statement · Cryptographic coding

    Not formalized
    There exist information-theoretically secure schemes that provably cannot be broken even with unlimited computing power—an example is the one-time pad—but these schemes are more difficult to implement than the best theoretically breakable but computationally secure mechanisms.

    Show in article · Read it in context on Wikipedia

    Searched 48 libraries — not found. Which libraries, at which commits (pinned 2026-10-17).

    Details
    • Searched by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run loc-tierA-b1b by jack: the search receipt lists 5 queries and 2 candidates examined (receipt f065951d0856).
    • Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run chal-tierA-b1 by jack: upheld.
  35. Definition · main statement · Other applications of coding theory › Group testing

    Not formalized
    Consider a large group of items in which a very few are different in a particular way (e.g., defective products or infected test subjects). The idea of group testing is to determine which items are "different" by using as few tests as possible.

    Show in article · Read it in context on Wikipedia

    Searched 48 libraries — not found. Which libraries, at which commits (pinned 2026-10-17).

    Details
    • Searched by Claude Opus 5 (claude-opus-5) on 31 Oct–1 Nov 2026 (UTC), locate run loc-tierA-b1b by jack: the search receipt lists 5 queries and 2 candidates examined (receipt 96d0995a98a6).
    • Re-checked by Claude Opus 5 (claude-opus-5) on 1 Nov 2026 (UTC), challenge run chal-tierA-b1 by jack: upheld.

Data: view model (JSON) · Literature Links records (JSONL)