Lemma 2 — the descendants of have numbers in
ProvedHarelTarjan.SymOrder.lemma2_descendants_rangeLet be the complete binary tree of depth , numbered in symmetric order. The descendants of a vertex are exactly the vertices with numbers in the range
That is, for all vertices : is a descendant of if and only if .
Lemma 2 is the ancestor test of the nca depth algorithm.
Formalization Note The two inequalities are stated additively, and , which are equivalent over the integers and avoid truncated subtraction.
import Mathlib import Definitions.Def_HarelTarjan_SymOrder_Tree import Definitions.Def_HarelTarjan_SymOrder_Sym
namespace HarelTarjan.SymOrder
/-- Lemma 2 (p. 342): the descendants of vertex `v` are those vertices with numbers in the range
`[sym(v) − 2^{h(v)} + 1, sym(v) + 2^{h(v)} − 1]`. The two endpoint inequalities are written
additively, to avoid truncated subtraction on `ℕ`. -/
theorem lemma2_descendants_range {d : ℕ} (v w : Vertex d) :
IsAncestor v w ↔
(sym v + 1 ≤ sym w + 2 ^ height v ∧ sym w + 1 ≤ sym v + 2 ^ height v) := by sorry
end HarelTarjan.SymOrder
Read-back
What the Lean code literally says, in plain math · claude-opus-5-5
This theorem characterises ancestry by the numbers . 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.
For all , the theorem asserts that is an ancestor of if and only if both of these hold:
Over the integers, the two conditions together say
Degenerate cases:
- If , both sides are true.
- For a leaf (where ), the range collapses to .
- For , only the root exists and the claim is trivial.
- Everything is stated additively on the naturals, so no truncated subtraction occurs.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.