Sketch linearity for the HintSketch recursion tree
ProvedLinearSetReconciliation327.Main.synAdd_sketchhintsketchlinear-set-reconciliationlinearitysketchsymmetric-difference
For every CR family and every node of the HintSketch recursion tree, the syntactic sum Node.synAdd of the sketches of two sets and is the sketch of their symmetric difference: Node.synAdd T (Node.sketch CR T r a) (Node.sketch CR T r b) = Node.sketch CR T r (symmDiff a b) — i.e. the sketch map is -linear all the way down the tree, which is what makes the payload CR x + CR x̂ that Node.decode hands a child a legitimate child input.
Preamble
import Definitions.Def_LinearSetReconciliation327_Main_Framework
Formal statement
namespace LinearSetReconciliation327.Main
theorem synAdd_sketch (CR : CRFamily) (T : Node) :
∀ (r : Node.Seed T) (a b : Finset ℕ),
Node.synAdd T (Node.sketch CR T r a) (Node.sketch CR T r b)
= Node.sketch CR T r (symmDiff a b) := by sorry
end LinearSetReconciliation327.Main
Source
arXiv:2611.11409 (Liu, Xu, Yang, Zhou, *Linear Set Reconciliation with O(d) Additive Redundancy*), §5.2 (HintSketch tree recursion and the sketch payload of a child node) and §6 (§9.2 decoder stages: the residual syndrome `CR x + CR x̂`); extracted from the verified development `Solutions/_65_decode_correct.lean` §12.3.