# Exact table optimization for phase-product (Shor-type) schedules: Lean proofs and Fortran solver > **Scope: a classical, theoretical companion to ForShor.** This directory studies the *table-optimization problem* > behind ForShor's PhaseProduct benchmark: which shift/add table is cheapest, and how hard is it to find. It is **not** > part of ForShor's verified order-finding circuit. ForShor's correctness and gate-count theorems do not depend on > anything here, no Lean file on either side imports the other, and the Lake projects here have their own toolchains > (they are not built by ForShor's root `lakefile.lean` or its CI). > > Naming: ForShor's `PhaseProduct` is a lowered, verified quantum subroutine. The `PhaseProduct/` layer of this > directory's Lean library is the *optimization model* of the table that drives it. This repository accompanies a paper on computing optimal "tables" (shift/add programs with per-operation costs) for phase-product schedules at fixed arity. It contains | Path | What it is | |---|---| | `paper/` | The paper source (`.tex`) and its PDF. | | `lean/` | The Lean 4 proof library (167 modules and 20 small helper files), built on Mathlib, plus five newer developments in `lean/Foundations/SmallPoint/`, `lean/Foundations/RuntimeComposition/`, `lean/Foundations/SeparationLemmas/`, `lean/Provider/Ceiling/GroupedCharge.lean` and `lean/Foundations/PairedCharge/` (see below). | | `proof_notes/` | Prose proofs and review records behind the paper's cited research packages, and the informal sources of the two newer Lean developments. See [`proof_notes/MANIFEST.md`](proof_notes/MANIFEST.md). | | `scripts/` | `AxiomAudit.lean`, the module-dependency graph generator, and the record of the move from the flat layout. | | `MODULE_MAP.md` | Old flat module name to layered module name. | | `lean_hardness/` | A separate Lake project (Lean v4.35.0-rc3, complexitylib) with the sparsity barriers and the NP-hardness of the points-as-input structural-score problem. See [`lean_hardness/README.md`](lean_hardness/README.md). | | `fortran/phaseproduct_saturation_f90/` | The exact Fortran solver (Kannan/saturation backend), its tests and drivers. | Start with [`REPRODUCING.md`](REPRODUCING.md). ## What is and is not claimed Read this before citing anything here. * The Lean library is the machine-checked part. The files contain no `sorry`, `admit`, `axiom` or `native_decide`. Checking was done with Lean 4.28.0 and a pinned Mathlib (see `REPRODUCING.md`). The complete Lake project (`EfficientTables` and `EfficientTablesHelpers`) was built from this repository layout with `lake build` (8216 jobs, no errors, Lean 4.28.0 and the pinned Mathlib; rebuilt on 2026-10-28 after the reorganization and the additions below: 8241 jobs, no errors), and the axioms of `Paper.PPEndToEnd.pp_through_arity_K` were checked to be only `propext`, `Classical.choice`, `Quot.sound`. * Five developments were added after the first build. `lean/Foundations/SmallPoint/` proves the small-integer-point bound `(t+1)·t!·B^t` for a polyhedron `{x ≥ 0, Ax ≤ b}` with bounded integer data (`SmallPoint.small_integer_point`). `lean/Foundations/RuntimeComposition/` proves an **arithmetic composition**: from stage-wise cost bounds taken as hypotheses (including Kannan's theorem, as a contract) it derives `Total ≤ 2^(611·c·K⁴·bl K)·(n+1)^(e(11+3c)+2c+4)` (`RuntimeComposition.composition`). That is **not** a runtime theorem about the algorithm: the paper's `2^{O(K⁴ log K)}·poly(n)` bound and the saturation cutoff remain paper proofs. `lean/Foundations/SeparationLemmas/` proves the zero and anchored-integrality criteria for gap-separated finite sums of signed powers of two (`SeparationLemmas.zero_criterion`, `integrality_anchored`), the core of the encoding lemma that bounds the constants of the saturation argument; the encoding lemma itself is a reviewed prose proof in `proof_notes/threshold/`. `lean/Provider/Ceiling/GroupedCharge.lean` proves the exact charge `4·(k−1)·(2k−3) ≤ 8k²` of the repository's grouped literal baseline, whose legality and `8k²` peaks were already checked. `lean/Foundations/PairedCharge/` counts the instructions of the paper's *paired* constructor (charge `≤ 6k²`); that is counting only, and the constructor's legality remains a paper proof that has not been independently reviewed. All five developments contain no `sorry`, `admit`, `axiom` or `native_decide`, and every theorem in them depends only on `propext`, `Classical.choice`, `Quot.sound` (checked with `#print axioms`, see each folder's `Audit.lean`). They were compiled in the Lean 4.28.0 / Mathlib `fadcf92b…` workbench, which is the same toolchain as this project; the full `lake build` count above predates them and has not been repeated with them. * The Lean statements cover a phase-product optimum and the correctness of several source-level contracts. They do **not** formalize the whole Fortran program, and they do not prove polynomial-time synthesis of optimal tables. The strongest optimality theorem is `Paper.ComputableProfileProvider.optimal_raw_F2_exact` (module `Provider.Effective.ProfileExact`): for every `K ≥ 2`, root width `W` and multiplicity `N` it gives a policy that is semantically correct for all signed `W`-bit inputs and whose cost is at most that of every ladder of source-legal literal-F2 tables of arity `≤ K` with one table per arity. It is a statement for each fixed `(K, W, N)`; it is not the paper's algorithm and says nothing about running time. `Paper.PPEndToEnd.pp_through_arity_K` is weaker: it is optimal only relative to a catalogue of verified candidates. Both depend only on `propext`, `Classical.choice`, `Quot.sound`. The map from each paper statement to its Lean counterpart, with what each one quantifies over and what is paper-only, is in [`LEAN_MAP.md`](LEAN_MAP.md); the axiom audit is `scripts/AxiomAudit.lean`. * Complexity-theoretic statements in the paper and notes (sparseness of a threshold language, collapse consequences) are **conditional**: they say what would follow from a reduction that has not been constructed. The many-one sparsity barriers are machine-checked in `lean_hardness/Mahaney/`. * The only NP-hardness result is for the **structural score** `S = A + 5L` when the interpolation points are **supplied as input** (`Pts.genLang_NPHard`, already at arity 2; machine-checked in `lean_hardness/Points/`). It is **not** shown that T-count optimization is NP-hard, in general or for the KMY points. No unconditional non-membership in P and no uniform polynomial-time exact optimizer is claimed. The existence of a uniform polynomial-time exact optimizer for growing arity is open. * The four research packages the paper cites (thresholds, outer planner, profiles, normalization) are shipped as prose proofs with their review records in `proof_notes/`; see [`proof_notes/MANIFEST.md`](proof_notes/MANIFEST.md) for their status (reviewed by AI reviewers, not machine-checked, with one step now covered by `proof_notes/threshold/ENCODING_LEMMA.2026-10-28.md`). Other working notes the paper may mention are not included. ## Layout notes * Lean module names follow the directory layout under `lean/` (for example `lean/Model/Defs.lean` is `Model.Defs`). The modules are grouped into eight dependency layers (see [`lean/README.md`](lean/README.md)); `MODULE_MAP.md` maps the earlier flat module names to the current ones. Declaration namespaces (e.g. `Paper.PPEndToEnd`) are unchanged. `lean/Helpers/` holds small Mathlib-only lemma files kept as a separate library. * `scripts/check_layers.py` asserts the layer order of both Lake projects (a file may import only from its own layer or an earlier one, and the two projects must not import each other). CI runs it. * Some Lean files named `*Bundle/All.lean` concatenate many components and therefore carry many theorems each. * Some file names formerly carried development timestamps; these were removed in the reorganization (see `MODULE_MAP.md`). * `scripts/AxiomAudit.lean` is the axiom audit of the declarations named in [`LEAN_MAP.md`](LEAN_MAP.md); `scripts/apply_restructure.py` and `scripts/module_map.py` are the record of the one-shot move from the flat layout. Four newer self-contained developments sit in `lean/Foundations/` and one in `lean/Provider/Ceiling/` (see `lean/README.md`). ## Licensing * Code (`lean/`, `lean_hardness/`, `fortran/`, `lakefile.toml`, scripts): Apache License 2.0, see [`LICENSE`](LICENSE) (a copy is in [`lean_hardness/LICENSE`](lean_hardness/LICENSE) so that Lake project can be used on its own). * `lean_hardness/` fetches complexitylib at build time; it is not included. * Text (the paper source, PDF, and Markdown documents): Creative Commons Attribution 4.0 International, see [`LICENSE-TEXT`](LICENSE-TEXT). * Third-party material: Lean and Mathlib are Apache-2.0 and are fetched at build time, not included. The Fortran compiler distribution is not included. Citation and author information is intentionally absent and will be added by the repository owner.