Proof of `Construction sequences with few realized types`

groundedproofs/Lax185574Proofs/FewTypes.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 17 of this submission's paper

Description

The proof of the few-types theorem. Run the algorithm of the theorem on definable construction sequences with radius r+7qr + 7^q, where h=7qh = 7^q is the radius of the lemma passing from definability to few types. The output is radius-(r+7q)(r + 7^q) definable with ⌈A(r+7q)/ε⌉+A⌈A(r + 7^q)/ε⌉ + A predicates and s≤c0(n+1)(a0ε)s ≤ c₀ (n+1)^(a₀ε) parameters, so its radius-rr depth-qq width is at most F(s+1)DF (s+1)^D, which is O((n+1)(a0Dε))O((n+1)^(a₀Dε)). So a=a0D+a0a = a₀D + a₀ works for the width and the length, and a≥1a ≥ 1 since a0≥1a₀ ≥ 1. The exponent 3+η3 + η of the time is passed on to the theorem on definable construction sequences. The program is a simulation of the program of the theorem on definable construction sequences on the rewritten input, one word bit shorter, and the word-length exponent grows by one to pay for the larger first entry.

The proof is carried out for the input format with the graph in compressed sparse row form and the notion Lax185574.Computing.ComputesLax185574.Computing.Computes. The algorithm converts the word of the graph into compressed sparse rows (Interface.nbrbridgeInterface.nbr_bridge) and runs the program for that format. The script of a graph is the one whose encoding the program outputs on the converted input.