Download README-project.md from SNAPKITTYWEST/montrepol: direct link, hf CLI and curl.
- Browser
- Download file 10.9 kB
-
https://huggingface.co/SNAPKITTYWEST/montrepol/resolve/main/README-project.md
- Command line
-
hf download hf://SNAPKITTYWEST/montrepol/README-project.md
-
curl -L -o README-project.md https://huggingface.co/SNAPKITTYWEST/montrepol/resolve/main/README-project.md
montrepol
Exact mathematics in Haskell, with every claim tied to a test that can fail.
This repository consolidates the parts of five earlier repositories that held real mathematics, and drops the rest. It depends on nothing but GHC: no Hackage packages, no Rust, no Python. The test harness, pseudorandom generator, TOML reader and every algorithm are written here.
cabal build all # GHC 9.10.1, cabal 3.12
cabal test all # 182 checks across 6 packages
cabal run mp-gate # rules R1-R6 over the model, the sources and the build
cabal run mp-gate -- mutants # planted defects in code, proofs and refinements; each must be caught
agda --no-libraries -i formal formal/Everything.agda # Agda 2.6.3, --safe, no stdlib
Packages
| Package | What it is | Checked against |
|---|---|---|
mp-check |
Test harness: SplitMix64, generators, properties, ID-tagged tests | An independent C SplitMix64; a planted false property |
mp-linalg |
Semirings, matrices with dimensions in the type, naive and Strassen products, Bareiss determinant, rank, inverse, participation ratio | Leibniz expansion, the definition of the product, Floyd–Warshall |
mp-lie |
Root systems A–G, simple roots, Cartan matrices, Weyl group orders by orbit–stabilizer | The classification tables (Bourbaki, Humphreys) |
mp-seq |
Berlekamp–Massey over any field, LFSRs, periods | Brute-force minimality; Massey's 2L theorem |
mp-analytic |
Sieve, von Mangoldt, Chebyshev ψ, exact Bernoulli numbers, ζ by Euler–Maclaurin, Riemann–Siegel θ, Hardy Z, zeros, the explicit formula | Trial division, OEIS, lcm(1..x), von Staudt–Clausen, closed forms of ζ, Odlyzko's table |
mp-hcalc |
Hcalc: a certifying SMT core. DPLL SAT with resolution refutations, Fourier–Motzkin linear arithmetic over ℚ with Farkas certificates, and DPLL(T) over both | Brute-force truth tables, grids of rational points, and independent certificate checkers that must reject forged certificates |
mp-lambda |
The simply typed λ-calculus, and refinement types {v:Int | φ} over it whose verification conditions Hcalc decides |
Progress, preservation and substitution on random terms; accepted programs are run and their postconditions checked |
mp-gate |
The gate: R1–R6 over the model, sources, proofs, the Liquid layer and the build; mutant replay | Its own planted defects (GT-01..GT-10) |
Hcalc and refinement types
Hcalc is an SMT solver written here, for quantifier-free linear rational arithmetic with propositional structure. It is small and slow, and it does not ask to be trusted: every answer carries a certificate.
| Answer | Certificate | Checked by |
|---|---|---|
| SAT | a model | evaluating the formula directly, ignoring the encoding |
| UNSAT (propositional) | a tree-resolution refutation read off the DPLL search | replaying the resolution steps |
| UNSAT (arithmetic) | Farkas multipliers for every learned theory lemma | summing the constraints and checking the contradiction |
The checker trusts the Tseitin encoding and the reading of terms as linear expressions; HC-07 tests the encoding against truth tables.
mp-lambda's refinement checker sends each subtyping obligation to Hcalc and
accepts it only when the certificate checks. Hcalc decides over ℚ, and a
statement valid over ℚ is valid over ℤ, so acceptance is sound for integer
programs. The converse fails: x < y ⟹ x + 1 ≤ y holds over ℤ but is rejected,
with a non-integral counter-model (LM-10).
Liquid Haskell
liquid/ is a separate build that compiles core modules a second time with
the Liquid Haskell plugin and Z3. The refinements live in the core sources as
{-@ … @-} comments, which GHC ignores, so the core build is unchanged and
still depends on nothing outside GHC. liquid/ is the one place allowed to use
Hackage and an external solver. The gate enforces that the exemption runs one
way only: the root build may not include liquid/, and no core package may
depend on it.
Liquid Haskell checks MP.Lambda.Simple as it is in the core:
sizeis at least 1.typeOf,shift,substandstepterminate.evaluateterminates because its fuel decreases.- Every pattern match in the module is total.
GHC checks none of these. This is the refined level: it trusts Liquid
Haskell 0.9.10.1.2 and Z3 4.8.12, a larger trusted base than Agda's kernel,
and it is kept apart from proved for that reason.
cd liquid && cabal update && cabal build all # needs z3 on PATH
Dex
dex/ holds Dex code: integer
matrices typed by their index sets, the same seven Strassen products, and the
exact Kish comparison. Each check is compared with a hand-computed value or
an independent computation. The files are quines: Dex runs them, and the
output must equal the file, so every > line is an assertion. Checks are
tagged # check DX-01 and registered like any other ID.
Dex's last commit (January 2024) needs LLVM 12, GHC 8.10.7 and a pinned
llvm-hs. Ubuntu 24.04 does not package LLVM 12, so dex/build.sh installs
Ubuntu 22.04's packages of it, fetches Dex and llvm-hs by git at pinned
commits, and builds them into dex/.toolchain.
./dex/build.sh && ./dex/check.sh
Proofs
formal/ holds Agda proofs, checked under --safe --without-K with no
standard library: equality, naturals, vectors and the algebra are defined
there from nothing.
| Ledger key | What is proved | Where |
|---|---|---|
strassen-identities |
Strassen's seven products give the four entries of the 2×2 product, in any abelian group with a two-sided distributive product: no associativity, commutativity or unit assumed. Matrices over a ring are such a structure (standard, not proved here), so this covers blocks | formal/Montrepol/Strassen.agda |
abelian-solver-sound |
The abelian-group normaliser the Strassen proof uses is sound in every model, so its refl steps are trustworthy |
formal/Montrepol/Solver.agda |
kish-lower-bound |
Σ wᵢ² ≤ (Σ wᵢ)² for all natural weights, so k_eff ≥ 1 | formal/Montrepol/Kish.agda |
What is not proved is recorded too. That MP.Matrix.strassenSq uses exactly
these products is checked by reading and by the LA-03 tests, not mechanically.
The Kish upper bound (Cauchy–Schwarz) is tested, not proved.
CONFORMANCE.md lists all 39 conformance IDs and the ledger's
untested claims, by package and honesty level. It is generated from model/, never edited.
Where it came from
| Repository | Kept | Dropped, and why |
|---|---|---|
matmul |
The claim discipline: levels, register, generated conformance, the rules | All of the Rust. There was no matrix multiplication in it; it was an empty template. mp-linalg is the matmul. |
prism-ciris |
The integer kernel's ideas, done correctly: exact Kish k_eff and participation ratio (mp-linalg), GF(2) recurrences done properly with Berlekamp–Massey (mp-seq), E8 (mp-lie) |
The ethics, governance and "atlas" prose, the 188 vocabulary files and the .lex.tex "proofs": 200 of 223 theorems had no parameters, 196 were decide on constants, and no CI step ran Lean. See below for the two defects found in its kernel. |
prime-router |
ψ(x), the projection of ψ(x) − x onto zeta zeros, now as the explicit formula with measured error (mp-analytic); its zero table, as an oracle |
"Hypersphere brain", Λ − π, "hyperbolic deficit", GloVe, the Ollama server. The table file was named 100k and held 512 rows. |
cluster |
Not yet | 22k lines of infrastructure rendering. Porting it means byte-for-byte golden tests against its generated/, and it only means something with the hardware. |
jsonschema |
Not yet | A fork of an actively maintained upstream. A Haskell validator is a large, separate piece of work, with the official JSON-Schema-Test-Suite as its oracle. |
Defects found in the prism-ciris kernel
Both were reproduced by compiling the original functions on their own before anything here was written:
check_integer_kish_keffused saturatingu64arithmetic and was described as overflow-free. For weights[2^32, 2^32], whose effective size is exactly 2, it acceptedmin_keff = 3andmin_keff = 1000. Here the comparison is over unbounded integers (LA-08), and a mutant that reintroduces 64-bit saturation is caught.evaluate_gram_ratchet's comment saidtr(G)^2 >= 2 ||G||_F^2, but for a 2×2 positive semi-definite matrix that holds only whenGis a multiple of the identity, since(l1 + l2)^2 <= 2 (l1^2 + l2^2). The code checked4 tr^2 >= 7 ||G||_F^2instead. Here the participation ratiotr(G)^2 / tr(G^2)is shown to lie in[1, 2]and to equal 2 exactly for scalar matrices (LA-10).
How claims work
Every claim has one of five levels, and the gate fails if they blur:
some-true: reproduced from a cited authority. Not established here.build: constructed here and checked by a test against an oracle. Evidence, not proof.open: measured and reported. Never asserted.proved: machine-checked by Agda under--safe. The ledger names the file and the lemmas; the gate checks they exist, that the file is--safewith no escape hatches, and thatformal/Everything.agdaimports it so CI checks it.refined: checked by Liquid Haskell, trusting it and Z3. The ledger names a core source and functions; the gate checks each has a spec and that the liquid build compiles the module.
Asserting words ("proves", "guarantees", "establishes", ...) may not appear in
a build or open claim, and the gate checks that. Property tests over random
inputs are evidence; they are not proofs, and this repository calls a claim
proved only when Agda has checked it.
AGENTS.md defines the rules. VERIFICATION.md
says what each gate discharges and records the defects planted to show it can
fail.
Toolchain
GHC 9.10.1 and cabal 3.12.1.0, installed with ghcup. libgmp is needed to
link. Agda 2.6.3 (Ubuntu 24.04's agda-bin) for the proofs; run it under a
UTF-8 locale, since its messages print the proofs' Unicode. cabal.project sets active-repositories: :none: a dependency from
outside the compiler cannot even be resolved, and the build needs no network.
Licence
GNU Affero General Public License v3.0 or later (LICENSE). Parts
adapted from the UOR Foundation's template keep their MIT / Apache-2.0 notices;
see NOTICE. Every Haskell source carries
SPDX-License-Identifier: AGPL-3.0-or-later on its first line (.cabal files
on their second, after cabal-version), and the gate fails a file that does
not (R6).