Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

The symmetric-order algorithm computes nca⁡(v,w)\operatorname{nca}(v,w)nca(v,w) in a complete binary tree

Proved
HarelTarjan.SymOrder.nca_algorithm_correct

by mikedeng1 · Sep 27, 2026 · Mathlib 0df444a (Lean v4.33.1)

algorithmsnearest-common-ancestorp2o-batch-p100bp2o-gran-per-chapterp2o-plan-paperp2o-v1trees

Let TTT be the complete binary tree of depth ddd whose vertices are numbered from 111 to nnn in symmetric order, sym(v)\mathrm{sym}(v)sym(v) the number of vvv and h(v)h(v)h(v) its height. The algorithm of §3 (p. 342) computes nca⁡(v,w)\operatorname{nca}(v,w)nca(v,w) from the numbers alone:

  1. Step 1. Compute d0d_0d0​, the depth of nca⁡(v,w)\operatorname{nca}(v,w)nca(v,w), by the nca depth algorithm: d0=d−h(v)d_0 = d - h(v)d0​=d−h(v) if sym(w)∈[sym(v)−2h(v)+1,sym(v)+2h(v)−1]\mathrm{sym}(w) \in [\mathrm{sym}(v) - 2^{h(v)} + 1, \mathrm{sym}(v) + 2^{h(v)} - 1]sym(w)∈[sym(v)−2h(v)+1,sym(v)+2h(v)−1]; otherwise d0=d−h(w)d_0 = d - h(w)d0​=d−h(w) if sym(v)∈[sym(w)−2h(w)+1,sym(w)+2h(w)−1]\mathrm{sym}(v) \in [\mathrm{sym}(w) - 2^{h(w)} + 1, \mathrm{sym}(w) + 2^{h(w)} - 1]sym(v)∈[sym(w)−2h(w)+1,sym(w)+2h(w)−1]; otherwise d0=d−⌊lg⁡(sym(v)⊕sym(w))⌋d_0 = d - \lfloor \lg(\mathrm{sym}(v) \oplus \mathrm{sym}(w)) \rfloord0​=d−⌊lg(sym(v)⊕sym(w))⌋.
  2. Step 2. Compute the depth-d0d_0d0​ ancestor of vvv by the depth algorithm: with h=d−d0h = d - d_0h=d−d0​, return sym−1(2h+1⌊sym(v)/2h+1⌋+2h)\mathrm{sym}^{-1}\left(2^{h+1} \lfloor \mathrm{sym}(v)/2^{h+1} \rfloor + 2^h\right)sym−1(2h+1⌊sym(v)/2h+1⌋+2h).

The theorem: for all vertices v,wv, wv,w of TTT, with h=d−d0h = d - d_0h=d−d0​, the vertex nca⁡(v,w)\operatorname{nca}(v,w)nca(v,w) is the unique vertex with number 2h+1⌊sym(v)/2h+1⌋+2h2^{h+1} \lfloor \mathrm{sym}(v)/2^{h+1} \rfloor + 2^h2h+1⌊sym(v)/2h+1⌋+2h, that is, for every vertex uuu,

sym(u)=2h+1⌊sym(v)/2h+1⌋+2h  ⟺  u=nca⁡(v,w),\mathrm{sym}(u) = 2^{h+1} \left\lfloor \mathrm{sym}(v)/2^{h+1} \right\rfloor + 2^h \iff u = \operatorname{nca}(v,w),sym(u)=2h+1⌊sym(v)/2h+1⌋+2h⟺u=nca(v,w),

so the algorithm returns nca⁡(v,w)\operatorname{nca}(v,w)nca(v,w).

This is the constant-time nearest common ancestor computation on complete binary trees that the paper's general algorithm reduces to.

Formalization Note ⌊lg⁡x⌋\lfloor \lg x \rfloor⌊lgx⌋ is Nat.log 2 x and ⊕\oplus⊕ is ^^^ on N\mathbb NN; interval tests are written additively. The returned vertex sym−1(N)\mathrm{sym}^{-1}(N)sym−1(N) is characterised as "a vertex has number NNN if and only if it is nca⁡(v,w)\operatorname{nca}(v,w)nca(v,w)", so no inverse function is defined. The O(1)O(1)O(1) running time is not formalized.

Preamble
import Mathlib
import Definitions.Def_HarelTarjan_SymOrder_Tree
import Definitions.Def_HarelTarjan_SymOrder_Sym
import Definitions.Def_HarelTarjan_SymOrder_Algorithms
Formal statement
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
Source
Harel, Tarjan, Fast Algorithms for Finding Nearest Common Ancestors, SIAM J. Comput. 13 (1984), p. 342, §3, Algorithm to compute nca(v, w) (unnumbered)
Read-back

What the Lean code literally says, in plain math · claude-opus-5-5

For every natural number ddd and every two vertices v,wv, wv,w of type Vertexd\mathrm{Vertex}_dVertexd​, the statement says this. The value depthAlgNum(v,ncaDepthAlg(v,w))\mathrm{depthAlgNum}(v, \mathrm{ncaDepthAlg}(v, w))depthAlgNum(v,ncaDepthAlg(v,w)) is the sym\mathrm{sym}sym-value of exactly one vertex, and that vertex is nca(v,w)\mathrm{nca}(v, w)nca(v,w).

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:

  • d∈Nd \in \mathbb{N}d∈N is an implicit parameter. It indexes the vertex type Vertexd\mathrm{Vertex}_dVertexd​. Nothing more about it is visible here.
  • Vertexd\mathrm{Vertex}_dVertexd​ is the type of vertices for parameter ddd. It is defined in the imported files.
  • sym:Vertexd→N\mathrm{sym} : \mathrm{Vertex}_d \to Nsym:Vertexd​→N is a map that assigns each vertex a value in some type NNN. The statement does not show what NNN is.
  • ncaDepthAlg(v,w)\mathrm{ncaDepthAlg}(v, w)ncaDepthAlg(v,w) is some value computed from vvv and www.
  • depthAlgNum(v,⋅)\mathrm{depthAlgNum}(v, \cdot)depthAlgNum(v,⋅) takes vvv and that value and returns an element of NNN.
  • nca(v,w)\mathrm{nca}(v, w)nca(v,w) is a vertex in Vertexd\mathrm{Vertex}_dVertexd​ determined by vvv and www.

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

nv,w  =  depthAlgNum(v, ncaDepthAlg(v,w)).n_{v,w} \;=\; \mathrm{depthAlgNum}\big(v,\ \mathrm{ncaDepthAlg}(v, w)\big).nv,w​=depthAlgNum(v, ncaDepthAlg(v,w)).

For all d∈Nd \in \mathbb{N}d∈N, all v,w∈Vertexdv, w \in \mathrm{Vertex}_dv,w∈Vertexd​, and every u∈Vertexdu \in \mathrm{Vertex}_du∈Vertexd​:

sym(u)=nv,w  ⟺  u=nca(v,w).\mathrm{sym}(u) = n_{v,w} \iff u = \mathrm{nca}(v, w).sym(u)=nv,w​⟺u=nca(v,w).

There are no other hypotheses: vvv and www are completely arbitrary, and v=wv = wv=w is allowed. The biconditional says two things:

  1. Existence: sym(nca(v,w))=nv,w\mathrm{sym}(\mathrm{nca}(v, w)) = n_{v,w}sym(nca(v,w))=nv,w​.
  2. Uniqueness: no vertex other than nca(v,w)\mathrm{nca}(v, w)nca(v,w) has sym\mathrm{sym}sym-value nv,wn_{v,w}nv,w​.

The statement does not assert that sym\mathrm{sym}sym is injective in general. It only asserts that the particular value nv,wn_{v,w}nv,w​ is hit by exactly one vertex. Nor does it describe what nca\mathrm{nca}nca is. nca\mathrm{nca}nca is used as a given function, and the statement only ties the computed number to it.

Degenerate cases. If Vertexd\mathrm{Vertex}_dVertexd​ is empty for some ddd (for example d=0d = 0d=0, depending on the unseen definition), the statement holds vacuously for that ddd. If Vertexd\mathrm{Vertex}_dVertexd​ has exactly one element rrr, then v=w=u=rv = w = u = rv=w=u=r. The statement then says only that sym(r)=depthAlgNum(r,ncaDepthAlg(r,r))\mathrm{sym}(r) = \mathrm{depthAlgNum}(r, \mathrm{ncaDepthAlg}(r, r))sym(r)=depthAlgNum(r,ncaDepthAlg(r,r)), provided nca(r,r)=r\mathrm{nca}(r, r) = rnca(r,r)=r, which is automatic in a one-element type. When v=wv = wv=w, it says the unique vertex whose sym\mathrm{sym}sym-value is depthAlgNum(v,ncaDepthAlg(v,v))\mathrm{depthAlgNum}(v, \mathrm{ncaDepthAlg}(v, v))depthAlgNum(v,ncaDepthAlg(v,v)) is nca(v,v)\mathrm{nca}(v, v)nca(v,v). The visible code makes no claim that nca(v,v)=v\mathrm{nca}(v, v) = vnca(v,v)=v. Any junk values from total functions (subtraction in N\mathbb{N}N, division by zero, defaults in a search) would be inside the unseen definitions of sym\mathrm{sym}sym, depthAlgNum\mathrm{depthAlgNum}depthAlgNum, ncaDepthAlg\mathrm{ncaDepthAlg}ncaDepthAlg or nca\mathrm{nca}nca. Whatever values those produce, the equivalence above is claimed to hold for them exactly as computed.

Human review
  • Endorsed by Shuze Chen · Sep 27, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Sep 27, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me