Lemma 4 — the nca of unrelated has height
ProvedHarelTarjan.SymOrder.lemma4_nca_height_xorLet be the complete binary tree of depth , numbered in symmetric order. If and are two unrelated vertices (neither is an ancestor of the other), the height of the nearest common ancestor of and is
where is the integer whose binary representation is the bitwise exclusive or of the binary representations of and .
Lemma 4 is the third case of the nca depth algorithm. The hypothesis that and are unrelated cannot be dropped: when is a proper ancestor of , the formula can give a height smaller than .
Formalization Note is ^^^ on and is Nat.log 2 x; they agree because unrelated vertices have distinct numbers, so the exclusive or is at least .
import Mathlib import Definitions.Def_HarelTarjan_SymOrder_Tree import Definitions.Def_HarelTarjan_SymOrder_Sym
namespace HarelTarjan.SymOrder
/-- Lemma 4 (p. 342): if `v` and `w` are two unrelated vertices, the height of the nearest common
ancestor of `v` and `w` is `⌊lg (sym(v) ⊕ sym(w))⌋`, where `⊕` is bitwise exclusive or
(`^^^` on `ℕ`) and `⌊lg x⌋ = Nat.log 2 x` for `x ≥ 1`. -/
theorem lemma4_nca_height_xor {d : ℕ} (v w : Vertex d) (hvw : Unrelated v w) :
height (nca v w) = Nat.log 2 (sym v ^^^ sym w) := by sorry
end HarelTarjan.SymOrder
Read-back
What the Lean code literally says, in plain math · claude-opus-5-5
This theorem gives the height of a nearest common ancestor in terms of . Let and let be the set of boolean sequences of length . The height is . Two vertices are unrelated when neither sequence is a prefix of the other; in particular they are distinct. The vertex has as its sequence the longest common prefix of and . 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 assumes that are unrelated. It then asserts
Here is bitwise exclusive or on binary expansions, and is taken to be .
Degenerate cases:
- For , no two vertices are unrelated, so the statement is vacuous.
- Pairs where one vertex is an ancestor of the other, including , are not covered.
- If the exclusive or were , the right side would be by convention. The statement itself does not rule this case out.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.