Lemma 3 — the height- ancestor of has number
ProvedHarelTarjan.SymOrder.lemma3_ancestor_numberLet be the complete binary tree of depth , numbered in symmetric order. If is a vertex and is a height () such that , then has an ancestor of height , and the ancestor of of height has number
Lemma 3 is the arithmetic behind the depth algorithm: an ancestor is found from the number of by clearing low-order bits.
Formalization Note " is a height" is made explicit as . The existence of the ancestor, presupposed by "the ancestor", is stated as a conjunct. The floor is natural-number division.
import Mathlib import Definitions.Def_HarelTarjan_SymOrder_Tree import Definitions.Def_HarelTarjan_SymOrder_Sym
namespace HarelTarjan.SymOrder
/-- Lemma 3 (p. 342): if `v` is a vertex and `h` is a height (`h ≤ d`) such that `h ≥ h(v)`, then
`v` has an ancestor of height `h`, and the ancestor of `v` of height `h` has number
`2^{h+1} ⌊sym(v) / 2^{h+1}⌋ + 2^h` (`/` is floor division on `ℕ`). -/
theorem lemma3_ancestor_number {d : ℕ} (v : Vertex d) (h : ℕ) (hvh : height v ≤ h)
(hhd : h ≤ d) :
(∃ u : Vertex d, IsAncestor u v ∧ height u = h) ∧
∀ u : Vertex d, IsAncestor u v → height u = h →
sym u = 2 ^ (h + 1) * (sym v / 2 ^ (h + 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 the number of an ancestor at a given height. Let and let be the set of boolean sequences of length . The height is , and is an ancestor of when is a prefix of , equality allowed. 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 takes a vertex and a natural number with
It then asserts two things:
- Some ancestor of has height .
- Every ancestor of with height satisfies
Degenerate cases:
- If , the ancestor is itself. The formula then gives back , provided is an odd multiple of .
- If , the ancestor is the root.
- For , only with the root is allowed.
- The hypotheses are always satisfiable, for example with .
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.