# Conformance Every claim this repository makes, by honesty level: | Level | Meaning | | --- | --- | | `some-true` | reproduced from an authority. **Not established here.** | | `build` | constructed here and checked against an oracle by a test. Evidence, not proof. | | `open` | measured and reported. **Never asserted.** | | `proved` | machine-checked by Agda under `--safe`, with no postulates. The evidence names the file and lemmas. Trusts Agda's kernel. | | `refined` | checked by Liquid Haskell. The evidence names a core source and the functions whose specs were checked. Trusts Liquid Haskell and Z3. | ## Register 65 IDs. Each is discharged by the tests tagged with it. ### mp-check | ID | Level | Claim | Checked against | | --- | --- | --- | --- | | `CK-01` | `build` | integerIn lo hi yields values in the closed interval [lo, hi]. | 200 generated intervals and draws. | | `CK-02` | `build` | The property runner reports a property that fails on one value in ten, and accepts a true one. | x /= 7 over [0, 9], 200 cases. | | `CK-03` | `build` | integerIn reaches every value of a small range. | 400 draws from [0, 9]. | | `CK-04` | `build` | The SplitMix64 stream matches the published algorithm. | First three outputs for seed 0 from an independent C implementation. (steele-2014) | ### mp-linalg | ID | Level | Claim | Checked against | | --- | --- | --- | --- | | `LA-01` | `build` | Integer, Rational, GF2 and MinPlus satisfy the semiring axioms. | Random triples, each axiom checked as an equation. | | `LA-02` | `build` | Matrix multiplication is associative, distributes over addition and has the identity as unit. | Random integer matrices of random compatible shapes up to 6. | | `LA-03` | `build` | Strassen multiplication equals the definition of the product, for every cutoff, over Integer, Rational and GF2. | The naive sum-of-products, on random shapes up to 20x20. (strassen-1969) | | `LA-04` | `build` | The Bareiss determinant equals the Leibniz expansion over Integer and GF2. | The permutation expansion, on random matrices up to 6x6, and a hand-checked matrix needing a pivot swap. (bareiss-1968) | | `LA-05` | `build` | det(AB) = det(A) det(B) and det(A^T) = det(A). | Random integer matrices up to 6x6. | | `LA-06` | `build` | Over Q the inverse exists exactly when det is non-zero and is a two-sided inverse; rank A = rank A^T, and rank is full exactly when det is non-zero. | Random rational and integer matrices up to 5x5. | | `LA-07` | `build` | Powers of a min-plus adjacency matrix give all-pairs shortest path lengths. | An independent Floyd-Warshall on random weighted digraphs up to 7 vertices. | | `LA-08` | `build` | Kish's effective sample size is the participation ratio of diag(w), lies in [1, number of non-zero weights], and is exact: [2^32, 2^32] has k_eff = 2 and is rejected against 3. | Random weight vectors; the saturating-arithmetic case from prism-ciris. (kish-1965) | | `LA-09` | `build` | For non-zero A, 1 <= PR(A^T A) <= rank(A^T A), and tr(G^2) is the squared Frobenius norm of symmetric G. | Random integer matrices up to 6x6. | | `LA-10` | `build` | For 2x2 symmetric G, tr(G^2) = tr(G)^2 - 2 det G; for PSD G, PR(G) lies in [1, 2] and equals 2 exactly when G is a multiple of the identity. | Random G = B^T B. | ### mp-lie | ID | Level | Claim | Checked against | | --- | --- | --- | --- | | `LI-01` | `build` | The constructed A1-A6, B2-B6, D4-D7, G2, F4, E6, E7 and E8 satisfy the axioms of a reduced crystallographic root system. | Exhaustive check of closure under reflections, integrality and reducedness; and rejection of E8 with a root deleted, a non-reduced set and a non-crystallographic set. | | `LI-02` | `build` | Each system has the tabulated number of roots, and the extracted simple roots number the rank. | The classification tables. (bourbaki-lie-4-6) | | `LI-03` | `build` | Every positive root is a non-negative integral combination of the extracted simple roots. | Exact rational solve against the Gram matrix of the simple roots. | | `LI-04` | `build` | The Weyl group order computed by orbit-stabilizer from the Cartan matrix matches the table, from A1 to E8 = 696729600. | The classification tables. (humphreys-1990) | | `LI-05` | `build` | The determinant of each computed Cartan matrix matches the table. | The classification tables. (bourbaki-lie-4-6) | | `LI-06` | `build` | For E8: \|W\| is the product of the degrees, the positive roots number the sum of (d_i - 1), \|Phi\| = rank times the Coxeter number 30, the root lattice is even and unimodular, and \|W\| does not depend on how the nodes are labelled. | The degrees 2, 8, 12, 14, 18, 20, 24, 30; random relabellings. (humphreys-1990) | ### mp-seq | ID | Level | Claim | Checked against | | --- | --- | --- | --- | | `SQ-01` | `build` | The Berlekamp-Massey connection polynomial generates the input sequence, over GF(2) and over Q. | Random sequences. (massey-1969) | | `SQ-02` | `build` | Berlekamp-Massey returns the least length: no shorter LFSR generates the sequence. | Brute force over every shorter connection polynomial, GF(2), lengths up to 11. | | `SQ-03` | `build` | From 2l terms of a length-l LFSR sequence, Berlekamp-Massey recovers a recurrence that predicts the rest. | Random LFSRs of length up to 8, run to 6l terms. (massey-1969) | | `SQ-04` | `build` | x^5 + x^2 + 1 gives period 31 and linear complexity 5; x^4 + x^2 + 1 = (x^2 + x + 1)^2 gives period 6, not 15. | Direct simulation of the shift register. (lidl-niederreiter-1997) | | `SQ-05` | `build` | The Fibonacci numbers have connection polynomial 1 - x - x^2, and the zero sequence has linear complexity 0. | Direct computation. | ### mp-analytic | ID | Level | Claim | Checked against | | --- | --- | --- | --- | | `AN-01` | `build` | The sieve agrees with trial division, and pi(10^k) for k = 1..6 matches the published counts. | Trial division to 5000; OEIS A006880. (oeis-a006880) | | `AN-02` | `build` | The product of p over prime powers p^k <= x equals lcm(1..x), so exp psi(x) = lcm(1..x); psi(x) matches log lcm(1..x) to 1e-12. | Exact integer lcm for x <= 300; logarithms for x <= 600. | | `AN-03` | `build` | The exact Bernoulli numbers match the classical values and satisfy von Staudt-Clausen up to B_80. | B_0..B_12 as tabulated; the theorem as an integrality check. (ireland-rosen-1990) | | `AN-04` | `build` | Euler-Maclaurin zeta matches zeta(2), zeta(4), zeta(0), zeta(-1), zeta(1/2) and Euler's formula for zeta(2k), k <= 10, to 1e-12. | Closed forms, using this package's own Bernoulli numbers for Euler's formula. (edwards-1974) | | `AN-05` | `build` | exp(i theta(t)) zeta(1/2 + it) is real to 1e-9 for t in [10, 800]. | The functional equation, which makes Z(t) real; 200 random t. (edwards-1974) | | `AN-06` | `build` | The zeros of Z(t) located on (10, 827] are exactly the 512 tabulated zeros, each to 1e-8. | Odlyzko's table, committed under oracles/. (odlyzko-zeros) | ### mp-gate | ID | Level | Claim | Checked against | | --- | --- | --- | --- | | `GT-00` | `build` | A repository that keeps the rules produces no violations. | A synthetic clean repository. | | `GT-01` | `build` | R1 fires on a hand-edited CONFORMANCE.md, a duplicated ID and an unparsable model, and on nothing else. | Planted defects. | | `GT-02` | `build` | R2 fires on an open ID, an asserting word in an open claim, some-true with no authority and a citation of an unknown authority. | Planted defects. | | `GT-03` | `build` | R3 fires on an ID with no test and on a test tagged with an unregistered ID. | Planted defects. | | `GT-04` | `build` | R4 fires on a deferral marker and on a stub, and not on the same word in a comment or a string. | Planted defects and planted near-misses. | | `GT-05` | `build` | R5 fires on a partial function, a partial operator and a missing -Werror, and not on primed names, strings or comments. | Planted defects and planted near-misses. | | `GT-06` | `build` | R6 fires on an outside dependency, an unbounded boot dependency, an unlisted package, a re-enabled package repository, and a source or .cabal file without the SPDX header. | Planted defects. | | `GT-07` | `build` | The TOML reader parses the subset the model uses and rejects what it cannot read. | Hand-written documents. | | `GT-08` | `build` | The formal rules fire on a proved claim citing a missing file or an undefined lemma, an ID at level proved, a postulate, a module without --safe, a module Everything.agda does not import, and an Agda file without the SPDX header; and asserting words are allowed at level proved. | Planted defects in a synthetic formal/ tree. | | `GT-09` | `build` | The Liquid Haskell exemption is one-directional: liquid sources without their own cabal.project, a root project that includes them, a core package depending on liquidhaskell, and an assumed or lazy refinement all fire. | Planted defects in a synthetic liquid/ tree. | | `GT-10` | `build` | A refined ledger claim must name a core source, functions with Liquid Haskell specs in it, and a module the liquid build compiles; each defect fires. | Planted defects against a synthetic core module and liquid cabal file. | | `GT-11` | `build` | Dex checks are tied to the register: a dex ID with no tagged check, a check tagged with an unregistered ID, and a Dex file without the SPDX header each fire. | Planted defects in a synthetic dex/ tree. | ### mp-hcalc | ID | Level | Claim | Checked against | | --- | --- | --- | --- | | `HC-01` | `build` | DPLL agrees with brute force on random CNF; its models satisfy the clauses and its refutations replay by resolution. | Truth tables over up to 7 variables. | | `HC-02` | `build` | The pigeonhole formula PHP(3,2) is refuted with a replaying refutation, and no refutation is accepted for a satisfiable CNF. | Random refutation trees against satisfiable CNFs. | | `HC-03` | `build` | Fourier-Motzkin models satisfy every constraint, its Farkas certificates check, and it never calls infeasible a system with a grid solution. | Exact evaluation; a grid of 17^3 rational points. | | `HC-04` | `build` | No Farkas certificate is accepted for a feasible system. | Random multipliers of either sign against systems with a grid solution, and a negative-weight forgery. | | `HC-05` | `build` | DPLL(T) models satisfy the formula, its unsatisfiability certificates check, and it never calls unsatisfiable a formula with a grid model. | Direct evaluation of the formula; a grid over two rationals and two propositions. | | `HC-06` | `build` | Transitivity, antisymmetry, a bounded polytope and excluded middle are proved valid with checked certificates; x < y ==> x + 1 <= y is refuted over Q with a checked counter-model. | Hand-written formulas. | | `HC-07` | `build` | The Tseitin encoding is equisatisfiable with the propositional formula. | Truth tables over three propositions. | | `HC-08` | `build` | An unsatisfiability certificate is rejected for a satisfiable formula. | Certificates of f /\ not f, offered for f. | ### mp-lambda | ID | Level | Claim | Checked against | | --- | --- | --- | --- | | `LM-01` | `build` | Generated terms of the simply typed lambda calculus have the type they were generated at. | The type checker. | | `LM-02` | `build` | Progress: every closed well-typed term on an evaluation trace is a value or takes a step. | Random closed well-typed terms. | | `LM-03` | `build` | Preservation: every step of evaluation keeps the type. | Random closed well-typed terms. | | `LM-04` | `build` | Evaluation of a closed well-typed term reaches a value. | Random terms, 10000 steps of fuel. | | `LM-05` | `build` | Substitution preserves types: G, x:S \|- t : T and G \|- s : S give G \|- t[x := s] : T, for open s under binders. | Random contexts, terms and substitutions. | | `LM-06` | `build` | Ill-typed terms are rejected, including self-application. | Hand-written terms. | | `LM-07` | `build` | abs, max, clamp, addNat and absTwice are accepted by the refinement checker, and on inputs meeting their preconditions their outputs meet their postconditions. | Running each program on random integers. | | `LM-08` | `build` | Wrong specifications are rejected, each with a counter-model that falsifies its verification condition. | Direct evaluation of the VC at the counter-model. | | `LM-09` | `build` | Substitution into refinement types avoids capture, and shadowing and reserved names are rejected. | A program whose check needs a capture-avoiding rename. | | `LM-10` | `build` | A specification valid over the integers but not the rationals is rejected, with a non-integral counter-model. | x < y ==> x + 1 <= y. | ### dex | ID | Level | Claim | Checked against | | --- | --- | --- | --- | | `DX-01` | `build` | In Dex, integer matrices typed by their index sets multiply to the hand-computed products, square and 2x3 by 3x2. | Products worked by hand. | | `DX-02` | `build` | In Dex, the integer product is associative and distributes over addition on a fixed example. | The two sides of each law, computed separately. | | `DX-03` | `build` | In Dex, Strassen's seven products recombine into the product given by the definition, on three integer examples. | The definition of the product, and one hand-computed product. | | `DX-04` | `build` | In Dex, Kish's effective sample size of [3, 3, 3] is at least 3 and not at least 4, decided exactly in integers. | (sum w)^2 = 81 against k * sum w^2 = 27k. | ## Ledger Claims with no ID, and so no test: reproduced facts and measured quantities. | Key | Level | Statement | Evidence | | --- | --- | --- | --- | | `strassen-exponent` | `some-true` | Strassen's algorithm uses O(n^log2(7)) ring operations. This repository checks that it computes the product, not how fast. | Cited, not measured. (strassen-1969) | | `zeta-zeros-complete` | `some-true` | Odlyzko's table lists every non-trivial zero of zeta with imaginary part in (0, 826.91], and each lies on the critical line. Here the zeros are located independently and matched to the table (AN-06); completeness is the table's, not verified by Turing's method here. | oracles/zeta-zeros-odlyzko.txt (odlyzko-zeros) | | `explicit-formula-truncation` | `open` | Error of the explicit formula truncated to the first M zeros, against psi(x), x in 20.5..980.5 off prime powers. Measured max \|err\|/sqrt(x): 0.529 (M=0), 0.317 (M=10), 0.199 (M=100), 0.112 (M=512). No bound on the truncation error is claimed. | cabal run mp-analytic-report | | `strassen-identities` | `proved` | In every abelian group with a product that distributes over addition on both sides (no associativity, commutativity or unit assumed), Strassen's seven products recombine into the four entries of the 2x2 product. n x n matrices over a ring form such a structure, so the identities apply to blocks; that fact is standard but not proved here. That MP.Matrix.strassenSq uses these same products is checked by reading, not mechanically. | formal/Montrepol/Strassen.agda: strassen-c11, strassen-c12, strassen-c21, strassen-c22 (strassen-1969) | | `abelian-solver-sound` | `proved` | The abelian-group normaliser used for the Strassen proof is sound in every model of the axioms: an expression and its normal form evaluate equally, so an equation between equal normal forms holds. | formal/Montrepol/Solver.agda: sound, solve | | `kish-lower-bound` | `proved` | For every list of natural numbers w, sum of w_i^2 <= (sum of w_i)^2, so Kish's k_eff = (sum w)^2 / sum w^2 is at least 1 wherever it is defined. The upper bound k_eff <= n (Cauchy-Schwarz) is not proved here; LA-08 tests it. | formal/Montrepol/Kish.agda: kish-lower (kish-1965) | | `lambda-simple-refined` | `refined` | Liquid Haskell checks MP.Lambda.Simple as it is in the core: size is at least 1; typeOf, shift, subst and step terminate, by the size of the term or structurally; evaluate terminates because its fuel decreases and is checked first; and every pattern match in the module is total. Trusts Liquid Haskell 0.9.10.1.2 and Z3 4.8.12. | packages/mp-lambda/src/MP/Lambda/Simple.hs: size, typeOf, evaluate | ## Authorities - **steele-2014**: G. L. Steele, D. Lea, C. H. Flood. Fast splittable pseudorandom number generators. OOPSLA 2014. (SplitMix64; constants as in Java's SplittableRandom.) - **strassen-1969**: V. Strassen. Gaussian elimination is not optimal. Numerische Mathematik 13 (1969) 354-356. - **bareiss-1968**: E. H. Bareiss. Sylvester's identity and multistep integer-preserving Gaussian elimination. Mathematics of Computation 22 (1968) 565-578. - **kish-1965**: L. Kish. Survey Sampling. Wiley, 1965. (Effective sample size.) - **humphreys-1990**: J. E. Humphreys. Reflection Groups and Coxeter Groups. Cambridge University Press, 1990. Sections 2.10-2.11 and 3.7 (orders and degrees). - **bourbaki-lie-4-6**: N. Bourbaki. Lie Groups and Lie Algebras, Chapters 4-6. Springer, 2002. Plates I-IX (root counts, Cartan matrices). - **massey-1969**: J. L. Massey. Shift-register synthesis and BCH decoding. IEEE Transactions on Information Theory 15 (1969) 122-127. - **lidl-niederreiter-1997**: R. Lidl, H. Niederreiter. Finite Fields, 2nd ed. Cambridge University Press, 1997. Chapter 8 (linear recurring sequences, periods). - **oeis-a006880**: OEIS A006880: number of primes below 10^n. - **ireland-rosen-1990**: K. Ireland, M. Rosen. A Classical Introduction to Modern Number Theory, 2nd ed. Springer, 1990. Chapter 15 (Bernoulli numbers, von Staudt-Clausen). - **edwards-1974**: H. M. Edwards. Riemann's Zeta Function. Academic Press, 1974. Chapter 3 (explicit formula), 6.4 (Euler-Maclaurin), 6.5 (Riemann-Siegel theta). - **odlyzko-zeros**: A. M. Odlyzko. Tables of zeros of the Riemann zeta function, file zeros1. https://www-users.cse.umn.edu/~odlyzko/zeta_tables/