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

Proof of `Refined near-linear computation of Welzl orders`

groundedproofs/Lax457868Proofs/RefinedWelzlOrdersProof.lean · lax-457868

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

The fixed compiled refined algorithm meets the stated crossing, time and success-probability bounds.

Proof strategy

The proof counts the actual finite fair-bit executions. It bounds initial retry cost and the accepted representative charge, then the chronological exception-repair loop, retaining every consumed random prefix. The maintained neighborhood separation supplies the paper's rejection bounds, and bounded selectors and retries supply the finite failure counts. The active-size contraction sums the round costs. The checked bounded clock and compiler transfer give the public word-RAM contract with success probability at least two thirds, including the complete small-input branch.

Attribution

The algorithm and refined parameters follow the supplied refined manuscript. The graph encoding, reconstruction and machine infrastructure reuse the original Welzl-order submission and the registered word-RAM compiler.