nat_self_delimiting_code_length
The self-delimiting code of m has length twice the number of binary digits of m plus one.
Statement
theorem nat_self_delimiting_code_length (m : ℕ) :
(nat_self_delimiting_code m).length = 2 * (Nat.bits m).length + 1- Source
- Sanity check of nat_self_delimiting_code (OP-851 encoding): the code length is linear in the bit length.
- Verified
- 07 Nov 2026
- Axioms
Quot.soundpropext- Built on 1
- nat_self_delimiting_codeThe self-delimiting binary code of a natural number m: each bit b of the binary expansion of m (least significant bit first, as in…
The proof, explained
The proof proceeds by unpacking the definition of the self-delimiting code and then inducting on the list of binary digits of m. The code replaces each bit with a two-element block and appends a single terminating bit, so its length is twice the number of bits plus one. After simplifying the length operations over concatenation and flat-map, the base case holds trivially and the inductive step is settled by linear arithmetic.
The length of the self-delimiting code of m reduces to summing 2 for each bit of m plus 1 for the delimiter.
Expanding the definition of `nat_self_delimiting_code` shows that it flat-maps each bit b of m to the two-element list `[true, b]` and appends `[false]`. Applying `List.length_append` and `List.length_flatMap` expresses the total length as the sum of the lengths of the blocks `[true, b]` plus the length of `[false]`. Finally, `List.length_cons` and `List.length_nil` evaluate the length of each pair `[true, b]` to 2 (represented as 0 + 1 + 1) and the trailing delimiter to 1, reducing the goal to showing that summing 2 for each bit plus 1 equals 2 * (Nat.bits m).length + 1.
uses
nat_self_delimiting_code,List.length_append,List.length_flatMap,List.length_cons,List.length_nilsimp only [nat_self_delimiting_code, List.length_append, List.length_flatMap, List.length_cons, List.length_nil]The equality holds in the base case where m has no bits (`nil`).
We proceed by structural induction on the list of bits `Nat.bits m`. In the base case where the list is empty (`nil`), the sum over the empty list is 0 and the length is 0. Both sides evaluate to 0 + 1 = 2 * 0 + 1, which `simp` closes directly.
induction Nat.bits m with | nil => simp
The equality holds in the inductive step when prepending a bit b to the list l.
In the inductive step for `b :: l`, `simp` simplifies the map and sum across the new head bit b, which adds 2 to the sum and increases the list length by 1. This leaves the linear arithmetic identity 2 + 2 * l.length = 2 * (l.length + 1), which `omega` closes.
| cons b l ih => simp; omega
nat_self_delimiting_code- The self-delimiting code of a natural number m, which replaces each bit b of m with `[true, b]` and appends `[false]`.
List.length_append- The length of the concatenation of two lists is the sum of their lengths: (as ++ bs).length = as.length + bs.length.
List.length_flatMap- The length of flat-mapping a function over a list is the sum of the lengths of the resulting lists: (List.flatMap f l).length = (List.map (fun a => (f a).length) l).sum.
List.length_cons- Prepending an element to a list increases its length by 1: (a :: as).length = as.length + 1.
List.length_nil- The empty list has length 0: [].length = 0.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
theorem nat_self_delimiting_code_length (m : ℕ) : (nat_self_delimiting_code m).length = 2 * (Nat.bits m).length + 1 := by simp only [nat_self_delimiting_code, List.length_append, List.length_flatMap, List.length_cons, List.length_nil] induction Nat.bits m with | nil => simp | cons b l ih => simp; omega