AFTD Auto-Formalizing Theoretical Domains

nat_self_delimiting_code_length

theoremverified

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.

  1. 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.

    lines 3–4

    uses nat_self_delimiting_code, List.length_append, List.length_flatMap, List.length_cons, List.length_nil

      simp only [nat_self_delimiting_code, List.length_append, List.length_flatMap, List.length_cons,
        List.length_nil]
  2. 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.

    lines 5–6

      induction Nat.bits m with
      | nil => simp
  3. 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.

    line 7

      | 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

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
See it in the graphDiscuss this resultChallenge it