Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Node validity for the HintSketch recursion tree

Definition
LinearSetReconciliation327_Main_NodeValidity

by djwj233 · Nov 20, 2026 · Mathlib 0df444a (Lean v4.33.1)

decoderhintsketchlinear-set-reconciliation

AllValid is the node-wise validity predicate of a HintSketch recursion tree.

At a store leaf it is vacuous. At a cr leaf (cr N t) and at a direct node with row scheme sch it asserts Node.Valid N X Y x J: the stored input x⊆[N]x \subseteq [N]x⊆[N] has weight at most X+YX+YX+Y, the hint J⊆[N]J \subseteq [N]J⊆[N] has weight at most XXX, and the deviation x△Jx \mathbin{\triangle} Jx△J has weight at most YYY.

At a recursive node it asserts the same for the node itself and, recursively, for every child sss, evaluated at the exact child input Cs+PsC_s + P_sCs​+Ps​ and the exact child hint JsJ_sJs​.

This is the per-node hypothesis under which the tree decoder returns exactly the stored set; it is not an extra assumption, since the root's validity together with the capacity bounds implies it at every node.

Definition code
import Mathlib
import Definitions.Def_LinearSetReconciliation327_Main_Framework

open scoped ENNReal
open Finset

set_option autoImplicit false

noncomputable section

namespace LinearSetReconciliation327.Main


/-! ## 12.5  `AllValid`: `Valid` at every node, and its derivation from the root -/

/-- **`Valid` at every node of the tree**, with the capacities `WF` assigns to each node.

The decode needs this in addition to `AllBounds`.  At a `cr` leaf the only things available are
`t ≤ N` and `min N (X + Y) ≤ t` (`WF`), and `CR.Recovers` additionally wants `x.card ≤ t` — which
needs the *capacity* bound `x.card ≤ X + Y`, a fact about `Valid` alone (`Z`, `U`, `V` say nothing
about it).  `allValid_of_valid` shows the root's `Valid` already gives it. -/
def AllValid (X Y : ℕ) : (T : Node) → Node.Seed T → Finset ℕ → Finset ℕ → Prop
  | .store _, _, _, _ => True
  | .cr N _, _, x, J => Node.Valid N X Y x J
  | .direct sch _, _, x, J => Node.Valid sch.N X Y x J
  | .recursive sch _ Xs Ys child, r, x, J =>
      Node.Valid sch.N X Y x J ∧
        ∀ s, AllValid (Xs s) (Ys s) (child s) (r.2 s)
          (sch.exactChildInput r.1 x J s) (sch.exactHint r.1 x J s)

end LinearSetReconciliation327.Main
Source
arXiv:2611.11409, §5.4 (HintSketch decoding) and §9.2 (top-level decoder); Theorem 6.5 (main guarantee), conjunct 8. Formal statement extracted verbatim from the Theorem 5.1 development (`Solutions/_51_zzz_full.lean`, §12.6).

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