While this submission is a draft, it cannot be used by other submissions.

Proof of `Near-linear-time computation of Welzl orders`

groundedproofs/Lax235315Proofs/Assembly.lean · lax-235315

What this proof establishes

no assumptions

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

Description

Near-linear Welzl-order algorithm. This proof assembles the construction's three independently proved contracts for the explicit source program.

Proof strategy

Take the sum of the three eventual resource thresholds. The runtime contract gives total halting on every tape. Every tape in the successful-final-state set yields a RunsToRunsTo witness, and the output contract makes that output acceptable. Monotonicity of finite cardinality transfers the probability lower bound from successful tapes to accepted tapes.

Attribution

The contracts are three proved lemmas about the proof-local program witness. The assembled target is the registered claim of Lax195003; the graph result is Theorem 1.4 in the supplied arXiv v1 PDF.