The vertices of height are numbered from left to right
ProvedHarelTarjan.SymOrder.height_numberingLet be the complete binary tree of depth , numbered in symmetric order. For any height , the vertices of height are numbered from left to right. Precisely:
- every vertex that is the -th vertex of its depth from the left (counting from ) has
- for every height , the set of numbers of the vertices of height is .
This is the basic fact about the numbering from which Lemmas 1–4 of §3 are verified.
Formalization Note "The -th vertex from the left" is leftIndex v = j, the path to read as a binary numeral (left , right , most significant turn first). The subtraction is on under .
import Mathlib import Definitions.Def_HarelTarjan_SymOrder_Tree import Definitions.Def_HarelTarjan_SymOrder_Sym
namespace HarelTarjan.SymOrder
/-- The numbers at height `h` (§3, p. 341): the vertices of height `h` are numbered
`2^h, 3·2^h, 5·2^h, …` from left to right. Pointwise, the vertex `v` that is `j`-th from the left
(counting from `0`) among the vertices of its depth has number `(2j + 1)·2^{h(v)}`; and for each
height `h ≤ d` the set of numbers of the vertices of height `h` is
`{(2j + 1)·2^h : 0 ≤ j < 2^{d−h}}`. -/
theorem height_numbering {d : ℕ} :
(∀ v : Vertex d, sym v = (2 * leftIndex v + 1) * 2 ^ height v) ∧
∀ h : ℕ, h ≤ d →
(Finset.univ.filter (fun v : Vertex d => height v = h)).image sym =
(Finset.range (2 ^ (d - h))).image (fun j => (2 * j + 1) * 2 ^ h) := by sorry
end HarelTarjan.SymOrder
Read-back
What the Lean code literally says, in plain math · claude-opus-5-5
This theorem gives a closed formula for . Let and let be the set of boolean sequences with . The height is . The left index is , i.e. read as a binary numeral with true , most significant entry first. The number counts the with . The key replaces false by and true by and appends , and the order is lexicographic with a proper prefix counting as smaller.
The theorem asserts two things:
- For every vertex ,
- For every , the set of values over the vertices with equals
Degenerate cases:
- For the root, and , so part 1 gives .
- For , only is covered, and both sides of part 2 are .
- Part 2 says nothing about heights .
- The subtraction in part 2 never truncates, because .
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.