Proof of `Computing the far tree`

groundedproofs/Lax185574Proofs/ToFarTree.lean · lax-185574

What this proof establishes

Assuming the claims on the left, the claim on the right holds — checked by the archive's pipeline. Proof code is not displayed here.

Read the Lean proof on GitHub

In the paper

  • page 46 of this submission's paper

Description

The program runs the glue program FarRam.glueFarRam.glue and the restriction program of the restriction lemma in the loop driver loopsoundloop_sound. Round jj of the glue program reads the tree, the scatter type and the answers so far, and asks for the restriction μ↾(ℓ+1)μ ↾ (ℓ+1) of the child of extension jj to its last position, one call per extension. The last round reads the radius and the blocks off the root, the met and far bits off the roots of the children, scans the scatter type and writes the selected trees, as in the proof of the far tree lemma. Its output is the far tree by farTreetreefarTree_tree, which applies the clustering lemma. Every run inside the driver is right at an admissible word length: the runs of the glue program because their values are polynomial in the input with a factor depending on the rank, the runs of the restriction program because their queries are admissible at the word lengths of their regions.

The proof is carried out for the notion Lax185574.Computing.ComputesLax185574.Computing.Computes, and transferred to Lax185574.Algorithms.Algorithm.ComputesLax185574.Algorithms.Algorithm.Computes through Lax185574Proofs.InterfaceLax185574Proofs.Interface.