|
Download CONFORMANCE.md from SNAPKITTYWEST/montrepol: direct link, hf CLI and curl.
- Browser
- Download file 17.8 kB
-
https://huggingface.co/SNAPKITTYWEST/montrepol/resolve/main/CONFORMANCE.md
- Command line
-
hf download hf://SNAPKITTYWEST/montrepol/CONFORMANCE.md
-
curl -L -o CONFORMANCE.md https://huggingface.co/SNAPKITTYWEST/montrepol/resolve/main/CONFORMANCE.md
17.8 kB
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/