File size: 17,821 Bytes
5316c4e | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 | <!-- Generated from model/*.toml by `mp-gate write`. Do not edit: R1. -->
# 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/
|