The symmetric-order algorithm computes in a complete binary tree
ProvedHarelTarjan.SymOrder.nca_algorithm_correctLet be the complete binary tree of depth whose vertices are numbered from to in symmetric order, the number of and its height. The algorithm of §3 (p. 342) computes from the numbers alone:
- Step 1. Compute , the depth of , by the nca depth algorithm: if ; otherwise if ; otherwise .
- Step 2. Compute the depth- ancestor of by the depth algorithm: with , return .
The theorem: for all vertices of , with , the vertex is the unique vertex with number , that is, for every vertex ,
so the algorithm returns .
This is the constant-time nearest common ancestor computation on complete binary trees that the paper's general algorithm reduces to.
Formalization Note is Nat.log 2 x and is ^^^ on ; interval tests are written additively. The returned vertex is characterised as "a vertex has number if and only if it is ", so no inverse function is defined. The running time is not formalized.
import Mathlib import Definitions.Def_HarelTarjan_SymOrder_Tree import Definitions.Def_HarelTarjan_SymOrder_Sym import Definitions.Def_HarelTarjan_SymOrder_Algorithms
namespace HarelTarjan.SymOrder
/-- The algorithm to compute `nca(v, w)` (§3, p. 342) is correct. Step 1 computes
`d₀ = ncaDepthAlg v w`, the depth of `nca(v, w)` by the nca depth algorithm; Step 2 computes the
number `depthAlgNum v d₀` of the depth-`d₀` ancestor of `v` by the depth algorithm, and returns
`sym⁻¹` of it, the vertex with that number. The theorem states that the vertex with that number
exists, is unique, and is `nca(v, w)`: a vertex `u` has number `depthAlgNum v (ncaDepthAlg v w)`
if and only if `u = nca(v, w)`. So the algorithm returns `nca(v, w)` for all vertices `v`, `w`. -/
theorem nca_algorithm_correct {d : ℕ} (v w : Vertex d) :
∀ u : Vertex d, sym u = depthAlgNum v (ncaDepthAlg v w) ↔ u = nca v w := by sorry
end HarelTarjan.SymOrder
Read-back
What the Lean code literally says, in plain math · claude-opus-5-5
For every natural number and every two vertices of type , the statement says this. The value is the -value of exactly one vertex, and that vertex is .
Symbols. None of these are standard notions. All of them come from the imported files Def_HarelTarjan_SymOrder_Tree, Def_HarelTarjan_SymOrder_Sym and Def_HarelTarjan_SymOrder_Algorithms, whose code was not provided. This read-back therefore cannot unfold them. It can only describe how the statement uses them:
- is an implicit parameter. It indexes the vertex type . Nothing more about it is visible here.
- is the type of vertices for parameter . It is defined in the imported files.
- is a map that assigns each vertex a value in some type . The statement does not show what is.
- is some value computed from and .
- takes and that value and returns an element of .
- is a vertex in determined by and .
The documentation comment describes these as the "nca depth algorithm", the "depth algorithm" and the nearest common ancestor. That comment is not part of the formal assertion, and the definitions themselves were not available to check it.
What is asserted. Write
For all , all , and every :
There are no other hypotheses: and are completely arbitrary, and is allowed. The biconditional says two things:
- Existence: .
- Uniqueness: no vertex other than has -value .
The statement does not assert that is injective in general. It only asserts that the particular value is hit by exactly one vertex. Nor does it describe what is. is used as a given function, and the statement only ties the computed number to it.
Degenerate cases. If is empty for some (for example , depending on the unseen definition), the statement holds vacuously for that . If has exactly one element , then . The statement then says only that , provided , which is automatic in a one-element type. When , it says the unique vertex whose -value is is . The visible code makes no claim that . Any junk values from total functions (subtraction in , division by zero, defaults in a search) would be inside the unseen definitions of , , or . Whatever values those produce, the equivalence above is claimed to hold for them exactly as computed.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.