The depth algorithm computes the number of the depth- ancestor of
ProvedHarelTarjan.SymOrder.depthAlg_correctLet be the complete binary tree of depth , numbered in symmetric order. Let be a vertex of depth , let , and let . Let be the ancestor of at depth (the prefix of length of the path to ). Then is an ancestor of , has depth , and it is the unique vertex with number : for every vertex ,
so the algorithm to solve the depth problem of §3 (p. 342), which returns of this number, returns the ancestor of whose depth is .
This is Step 2 of the algorithm to compute ; the paper derives it from Lemmas 1 and 3.
Formalization Note is stated as "a vertex has number if and only if it is ", which asserts both that is a number of the tree and that is the vertex carrying it; no inverse function is defined. is natural-number subtraction and does not truncate since .
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 solve the depth problem (§3, p. 342) is correct: given a vertex `v` and a
depth `d₂ ≤ depth(v)`, with `h = d − d₂`, the vertex `sym⁻¹(2^{h+1} ⌊sym(v) / 2^{h+1}⌋ + 2^h)`
is the ancestor of `v` whose depth is `d₂`: `ancestorAtDepth v d₂` is an ancestor of `v` of depth
`d₂`, and a vertex `u` has number `2^{h+1} ⌊sym(v) / 2^{h+1}⌋ + 2^h` if and only if it is that
ancestor. -/
theorem depthAlg_correct {d : ℕ} (v : Vertex d) (d₂ : ℕ) (hd₂ : d₂ ≤ depth v) :
IsAncestor (ancestorAtDepth v d₂) v ∧ depth (ancestorAtDepth v d₂) = d₂ ∧
∀ u : Vertex d, sym u = depthAlgNum v d₂ ↔ u = ancestorAtDepth v d₂ := by sorry
end HarelTarjan.SymOrder
Read-back
What the Lean code literally says, in plain math · claude-opus-5-5
Undefined terms. This statement uses several terms that are defined in imported files, which I was not given: , , , , and . I cannot expand them, so this read-back treats them as opaque and uses only their names. The source has a documentation comment. It says the vertices form a tree of depth and that numbers them. It also gives a formula for :
That comment describes what the author intended. It is not part of the formal statement, and I could not check it against the hidden definitions.
Parameters.
- is a natural number, left implicit.
- is an element of the type .
- is a natural number.
- The hypothesis requires
Claim. Write for the vertex returned by that function. The theorem asserts all three of the following:
- is an ancestor of , in the sense of . The statement does not say whether this relation is reflexive or strict.
- .
- For every vertex :
Part 3 says two things. First, equals . Second, no other vertex of has that number, so exactly one vertex has it. The statement does not say is injective on all vertices; it only says that this one value has a single preimage. The theorem does not say that is the only ancestor of at depth .
Degenerate cases.
- . The hypothesis holds with equality. The theorem then says is an ancestor of at 's own depth. That only fits if lets a vertex be its own ancestor. If the relation is strict and no vertex is a strict ancestor at the same depth, then the theorem as stated is false in this case. It is not vacuous here, because the hypothesis does allow it.
- . The hypothesis always holds. The claim is that an ancestor of depth exists and is the unique vertex numbered .
- , or has only one element. The only possible presumably has depth , so only is allowed. The claim then reduces to that vertex being its own ancestor, having depth , and being numbered .
- is empty. The theorem holds vacuously.
- No link between and . The statement itself does not require . If the documented is used inside , it is subtraction on natural numbers. It would be cut off at whenever , which the statement does not rule out.
- Division in the documented formula. is never zero, so the division by it never hits a divide-by-zero default. The floor is presumably integer division rounding down.
Whether any of these edge cases actually happens depends on the hidden definitions of and , which I could not see.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.