Every function is a graph.
The standard library is NOVA’s working corpus: real functions, written as typed graphs, built on one another with Call, and verified before they ship. People read the diagrams; AIs read the same structure.
- functions
- 554
- modules
- 12
- test cases
- 22,160
- verified results
- 135,547
- all passing
- 554/554
- also verified at float32
- 551/554
Six levels so far. L0 is composed from NOVA’s original primitives. L1 also uses the standard math primitives of Round 13.1: square root, exponential, logarithm, exact maximum and minimum, comparisons and Size. L2 also uses Round 13.2: windows and joins along an axis, positions as values, sorting, running sums and extremes, and Scan — a loop whose body is another function of the library. L3 also uses Round 13.3’s integer indices — Cast turns a computed position into an index, exactly or not at all; Gather and GatherAlong read at indices; ScatterAdd writes at them — and Round 13.4’s While, a loop that runs until a condition says stop, within a stated number of steps. Round 13.5 completes L3 with dense linear algebra: solving linear systems, the Cholesky factorization, and the eigenvalues and eigenvectors of symmetric matrices. L4 adds Round 13.6’s orthogonal factorizations (QR and the singular value decomposition), Round 13.7’s floor division and remainder — calendars, hashes, bins, the greatest common divisor, reproducible random numbers — and Round 13.8’s Fourier transform, on complex vectors kept as two real rows. L5 begins with Round 13.9’s special functions: erf and erfc, log-gamma, expm1 and log1p — the normal distribution, count models and stable losses — and continues with Round 13.10’s distribution functions: the normal quantile and the regularized incomplete gamma and beta functions, for p-values, quantiles and normal random draws. Round 14.1 adds their inverses: the chi-square, gamma, beta and t quantiles. Round 14.2 makes the gamma and beta functions and their inverses differentiable in their shape parameters too, which is what fitting a distribution needs. Round 14.3 adds upper tails that keep their accuracy, so p-values far below 10⁻¹⁶ no longer round to 0, and the Poisson and binomial quantiles. Round 14.4 adds bitwise integer operations and Philox4x32-10, a counter-based random number generator of modern statistical strength: every element draws its own number from its own counter, the same on every backend. Hypothesis tests follow: z, one-sample and Welch t, correlation and chi-square goodness of fit, whose p-values keep their digits far below 10⁻¹⁶, and the rank-based Spearman and Mann–Whitney tests, each stated as the approximation it is. An eighth module, optim, is where a graph learns: verified update steps (SGD, momentum, Adam) and logistic regression trained inside one Scan, which, on data where an optimum exists, reaches the optimum Newton’s method finds at 60 digits to the last bits. Round 14.5 lets an entry take a function: a template names it $f, and a caller binds it, as in rk4[f=…] or minimize_adam[df=…]; NOVA specializes the template into an ordinary graph, static, typed and hashable; each template in the library is verified through a witness binding. Round 14.6 lets the binding be a derivative: minimize_adam[df=@grad[f=loss,wrt=w]] trains a model on its loss alone, with NOVA deriving the gradient by reverse mode. Round 14.10 lets a loop carry several values, each of its own shape and dtype: lstm carries (h, c), kalman_level a mean and a variance, and bezout six integers. Rounds 14.11 to 14.21 add trigonometry; special functions, distributions and tests; quadrature, interpolation and polynomials; root finding; determinants, matrix powers and matrix functions; number theory; combinatorics, interest, recurrences and iteration; finite probability and Markov chains; graphs, automata and rank; linear programming and network flows; boundary-value problems and series. Round 14.22 adds the exact answers that need exhaustive search on small graphs: cliques, colourings, matchings and isomorphism. Rounds 14.23 to 14.28 add three new modules that decide finite structures by complete enumeration: algebra (groups on their Cayley tables, group actions, rings and fields), topology (finite topological spaces, by the full list of their open sets) and sets (relations, functions, logic and finite metrics). Alongside them come finite probability and measures, grammars by CYK, Turing machines, a rank decided exactly by fraction-free elimination, exact elementary checks and slices of analysis (fractions, the mean value theorem on quadratics, Taylor remainders and integrals of polynomials), regular expressions and pushdown runs. Round 14.29 makes the error bounds sharper where Sigmoid and Tanh saturate and for ill-conditioned QR (growing like κ, not κ³), and differentiates softplus and bce_with_logits correctly at 0, with the same values bit for bit; 21 more float32 cases are certified. Round 15.10 makes NOVA’s transcendental primitives — exponential, logarithm, the trigonometric functions, erf, log-gamma and the rest — correctly rounded: each value is the exact one rounded once, the same bits on every machine.
Three checks, all automatic
- 01
The right function
In exact arithmetic, the graph must equal an independent reference formula, usually the NumPy library call. Exactly, with rational numbers; to 80 digits where roots, exponentials, logarithms, eigenvalues, singular values, Fourier transforms or special functions appear.
- 02
A guaranteed accuracy
Every float64 result must lie inside an error bound computed from the graph itself, by running error analysis. The bound holds whatever order NumPy adds in. Where a step is a transcendental primitive — exp, tanh, erf or log-gamma, correctly rounded since NOVA Round 15.10, so within half a unit in the last place — or is handed to a routine — LAPACK for linear algebra, or NOVA’s own normal quantile and incomplete gamma and beta functions — the bound rests on a stated bound for that step’s error. Since NOVA Round 14.7 the same check also runs at float32: each case is rounded to float32, and the bound is computed at u = 2⁻²⁴. Three functions whose stopping rules are written in float64 terms are float64-only, and their pages say why.
- 03
The same answer everywhere
NOVA’s reference interpreter and its NumPy backend must return bit-identical results.
Before any of this, the signature is proven: NOVA’s shape solver checks every broadcast and every contraction, for every size.
Elementwise
std.elementwise · 83Absolute value, built from Relu. Exact: one of the two terms is always zero.
Elementwise square.
Elementwise cube.
Linear interpolation from a to b by a scalar t.
Leaky ReLU with slope alpha for negative inputs, built from Relu.
SiLU (also called swish): x times its own sigmoid.
GELU, tanh approximation, as used in GPT-style networks.
Softsign: a smooth, bounded alternative to tanh. Calls abs.
Clamp every element into [lo, hi] with exact Maximum and Minimum.
ReLU capped at 6, as in mobile networks.
Piecewise-linear sigmoid: relu6(x + 3) / 6. Calls relu6.
Sign of each element (−1, 0 or 1), from two comparison masks. Exact.
Softplus in its overflow-free form, as two smooth branches: x + log(1 + e^(−x)) for x ≥ 0 and log(1 + eˣ) for x < 0. Mathematically identical to log(1 + eˣ), which the reference uses.
The logistic function σ(x) = 1/(1 + e⁻ˣ), between 0 and 1: the derivative of softplus, and the inverse of the log-odds. NOVA's Sigmoid primitive, which uses eˣ/(1 + eˣ) where e⁻ˣ would overflow.
ELU: the identity for positive inputs, α(eˣ − 1) otherwise.
Mish: x · tanh(softplus(x)). Calls softplus.
An angle wrapped into [0, 2π): the remainder after dividing by 2π, which takes the divisor's sign, so negative angles come out positive.
The day of the week of a date given as days since 1970-01-01, Monday = 0: that day was a Thursday, so (days + 3) mod 7. Dates before 1970 work too, because the remainder is never negative.
1 for a leap year of the proleptic Gregorian calendar, else 0: divisible by 4, except centuries, except every fourth century.
Days since 1970-01-01 for a date of the proleptic Gregorian calendar, by Howard Hinnant's algorithm: the year is counted from March, so the leap day falls last, and every division is a floor.
The year, month and day of a date given as days since 1970-01-01, by Howard Hinnant's algorithm: floor divisions by the 400-year era, the year of the era, and a year that starts in March.
One step of Euclid's algorithm on pairs stored as two rows: (a, b) becomes (b, a mod b); a finished pair, with b = 0, stays as it is. gcd repeats it.
Whether any pair still has a non-zero second number, for pairs stored as two rows of non-negative integers: 1 or 0. The condition gcd's loop tests.
The greatest common divisor of each pair of positive integers, by Euclid's algorithm: a While loop of euclid_step until every remainder is zero.
Whether the extended Euclidean algorithm still has a pair to reduce: some remainder r1 above 0, as 1 or 0. The condition bezout loops on.
One step of the extended Euclidean algorithm on each pair: where r1 is above 0, with q = ⌊r0 / r1⌋, each of the pairs (r0, r1), (s0, s1), (t0, t1) becomes (second, first − q·second); a finished pair stays. The body that bezout runs.
The extended Euclidean algorithm on each pair of non-negative integers: their greatest common divisor g and Bézout coefficients x and y with a·x + b·y = g. A While with six int64 states (Round 14.10): the remainders and both coefficient sequences, carried side by side.
The elementwise product of two complex vectors, each stored as a [2, n] array of real parts and imaginary parts: (a + bi)(c + di) = (ac − bd) + (ad + bc)i.
log(1 − e^(−x)) for x > 0, accurate everywhere (Mächler's rule): log(−expm1(−x)) below log 2, log1p(−e^(−x)) above. Each naive form loses its digits on one side.
The normalized sinc function, sin(πx)/(πx), and 1 at x = 0: the Fourier transform of a box, zero at every other integer. π is computed as arccos(−1), so in exact arithmetic the graph means π itself.
The gamma function Γ(x) for x > 0, as e^(log Γ(x)): (n − 1)! at the positive integers, √π at ½.
The logarithm of the beta function, log B(a, b) = log Γ(a) + log Γ(b) − log Γ(a + b), for a, b > 0: finite where B itself underflows.
The beta function B(a, b) = Γ(a)Γ(b)/Γ(a + b) for a, b > 0, as e^(log B). Calls log_beta.
The inverse error function: the y with erf(y) = x, for −1 < x < 1. Written as −sign(x)·Φ⁻¹((1 − |x|)/2)/√2, so that near ±1, where erfinv grows without bound, the tail 1 − |x| is computed exactly and keeps its digits; for |x| < ½ one Newton step on erf restores the low bits of x that (1 − |x|)/2 rounds away (in exact arithmetic the step is zero).
Whether binary exponentiation still has an exponent bit to use: some k above 0, as 1 or 0. The condition pow_mod loops on.
One step of binary exponentiation modulo m: if k is odd, multiply the result by the base; square the base; halve k. Each product is reduced modulo m at once, so nothing grows past m². The body that pow_mod runs.
Modular exponentiation aᵏ mod m, elementwise, by binary exponentiation: a While over pow_mod_step, one exponent bit per step. Python's pow(a, k, m). The base is reduced modulo m first, so a may be negative.
The inverse of a modulo m, elementwise: the x in 0 … m − 1 with a·x ≡ 1 (mod m), from the Bézout certificate a·x + m·y = 1 that bezout gives. Where gcd(a, m) ≠ 1 there is no inverse: inv is 0 and ok is 0. Python's pow(a, −1, m).
Fold one congruence x ≡ rᵢ (mod mᵢ) into a solution x modulo M: x + M·t, with t = (rᵢ − x)·M⁻¹ mod mᵢ, and the modulus becomes M·mᵢ. The inverse comes from bezout. The body crt scans.
The Chinese remainder theorem: the x in 0 … M − 1, M = m₁·…·mₙ, with x ≡ rᵢ (mod mᵢ) for every i, for pairwise coprime moduli. A Scan of crt_step over the congruences. The solution is unique modulo M, not as an integer.
The Legendre symbol (a/p) for an odd prime p, elementwise: 0 if p divides a, 1 if a is a non-zero square modulo p, and −1 otherwise. Computed by Euler's criterion, a^((p−1)/2) mod p, through pow_mod. The reference instead searches for a square root, so the two routes are independent.
Whether some power aᵏ mod n has not yet returned to 1, as 1 or 0. The condition multiplicative_order loops on.
One more power: where aᵏ mod n is not yet 1, multiply it by a modulo n and count one more step. The body multiplicative_order runs.
The multiplicative order of a modulo n, elementwise: the smallest k ≥ 1 with aᵏ ≡ 1 (mod n), for gcd(a, n) = 1, found by taking powers until the first return to 1. Where gcd(a, n) ≠ 1 there is no order, and the result is 0.
Whether p still divides some m, as 1 or 0. The condition padic_valuation loops on.
Where p divides m, divide it out once and count it. The body padic_valuation runs.
The p-adic valuation vₚ(a), elementwise: the exponent of the highest power of p dividing a ≠ 0, found by dividing p out of |a| until it no longer divides. A negative a is taken by its absolute value. vₚ(0) is infinite, so for a = 0 the loop reaches max_steps and fails rather than return a number.
Whether trial division still has a candidate divisor d with d² ≤ m somewhere, as 1 or 0. The condition factor_summary loops on.
One step of trial division that records the factorization as it goes. Where d² ≤ m and d divides m, divide d out and record it: the smallest prime factor, the first time; a new distinct prime, with φ multiplied by (1 − 1/d) exactly; or a repeat, which makes the number not squarefree. Where d does not divide, move to the next candidate: 3 after 2, then odd numbers. The body factor_summary runs.
Trial division of each n ≥ 1, and four facts read from it: the smallest prime factor (0 for n = 1), ω(n), the number of distinct primes, whether n is squarefree, and Euler's φ(n). A While over trial_step that tries 2 and then odd d up to √n; what remains above 1 at the end is one more prime. The reference factors each n independently.
The smallest prime factor of each n ≥ 2, by trial division (factor_summary).
Whether each n ≥ 1 is prime, as 1 or 0: its smallest prime factor is n itself. 1 is not prime.
Euler's totient φ(n) for each n ≥ 1: how many k in 1 … n are coprime to n, as n·Π(1 − 1/p) over its prime factors (factor_summary). The reference counts the k directly.
The Möbius function μ(n) for each n ≥ 1: 0 if a square divides n, and otherwise (−1)ᵏ for k distinct prime factors (factor_summary). μ(1) = 1.
Whether some k is still at most n, as 1 or 0. The condition factorial_mod loops on.
Where k ≤ n, multiply the running product by k modulo m, and move to k + 1. The body factorial_mod runs.
n! mod m, elementwise, multiplying 1 … n and reducing modulo m at every step, so nothing grows past m·n. Wilson's theorem says (p − 1)! ≡ −1 (mod p) exactly when p is prime.
A solution of the linear Diophantine equation a·x + b·y = c, for a, b ≥ 0: where d = gcd(a, b) divides c, the particular solution x₀ = x·(c/d), y₀ = y·(c/d) from bezout's certificate, and ok = 1. Every solution is then (x₀ + (b/d)t, y₀ − (a/d)t). Where d does not divide c there is none, and ok = 0. a = b = 0 is solvable only for c = 0, by every pair.
Whether some counter i is still at most k, as 1 or 0. The condition the permutation and binomial loops test.
One factor of the falling product n(n − 1)…(n − k + 1): where i ≤ k, multiply by n − i + 1 and count. The body permutations runs.
The number of ordered selections of k from n distinct objects, P(n, k) = n!/(n − k)!, elementwise, as the falling product n(n − 1)…(n − k + 1): a While over falling_step. P(n, 0) = 1, and P(n, k) = 0 for k > n, since a factor n − n is reached.
n! for each n ≥ 0, as P(n, n) through permutations. 0! = 1. Exact through 18! = 6.4·10¹⁵ < 2⁵³; 21! overflows int64.
One factor of the multiplicative formula for C(n, k): where i ≤ k, multiply by n − k + i and divide by i. The division is exact, since the running value is C(n − k + i − 1, i − 1). The body binomial runs.
The binomial coefficient C(n, k) = n!/(k!(n − k)!), elementwise, by the multiplicative formula on the shorter side, min(k, n − k): a While over binomial_step. C(n, 0) = 1, and C(n, k) = 0 for k > n.
The Catalan number Cₙ = C(2n, n)/(n + 1), elementwise: 1, 1, 2, 5, 14, 42, … The division is exact. The reference uses the recurrence Cₙ₊₁ = Σ CᵢCₙ₋ᵢ instead.
Whether binary exponentiation still has an exponent bit to use, as 1 or 0. The condition ipow loops on.
One step of binary exponentiation on floats: if k is odd, multiply the result by the base; square the base; halve k. The body ipow runs.
xᵏ for a real x and an integer k ≥ 0, elementwise, by binary exponentiation: at most 2·log₂k + 1 multiplications. x⁰ = 1, 0⁰ included.
The roots of a·x² + b·x + c = 0, a ≠ 0, elementwise, in the form that avoids cancellation: q = −(b + sign(b)·√D)/2 with D = b² − 4ac, then x₁ = q/a and x₂ = c/q. For D < 0 the roots are re ± i·im, with re₁ = re₂ = −b/(2a) and im = √(−D)/|2a|; for D ≥ 0, im = 0. The naive (−b ± √D)/(2a) loses the smaller root to cancellation when b² ≫ |4ac|.
The modulus |z| = √(a² + b²) of each element of a complex vector stored as a [2, n] array of real and imaginary parts.
The conjugate a − bi of each element of a complex vector stored as a [2, n] array. z·z̄ = |z|², a real number.
The balance after n periods of compound interest at rate i per period, with no deposits, withdrawals or fees: B₀(1 + i)ⁿ, computed as B₀·exp(n·log1p(i)) so that a small rate keeps its digits. n may be fractional.
The present value of an amount F due n periods ahead, at rate i per period: F/(1 + i)ⁿ, computed as F·exp(−n·log1p(i)). It inverts compound_balance.
The k-th derivative of a polynomial, coefficients highest degree first and the length kept: each coefficient of xᵈ is multiplied by the falling factorial d(d − 1)…(d − k + 1) and moved k places toward the constant term, and the k leading places become 0. Past the degree the derivative is 0. k = 1 is poly_derivative with a leading 0.
Whether the fractions p/q and r/s (integers, q and s nonzero) are equal, as 1 or 0: ps = rq, exactly, without dividing. The same test decides a proportion a : b = c : d, ad = bc.
The reduced form of the fraction p/q (q ≠ 0): numerator and denominator divided by gcd(|p|, |q|), with the denominator made positive. It changes the representation and not the value; 0/q becomes 0/1.
The errors of an approximation a to a reference value x: the absolute error |a − x|; the relative error |a − x|/|x|, defined only when x ≠ 0 (has_rel says whether it is, and rel is 0 otherwise); and whether |a − x| ≤ τ for the tolerance τ ≥ 0, as 1 or 0. Truncation, rounding and data error are different sources and are not interchangeable.
Dimensional analysis with the base dimensions L, M and T, each quantity's dimension an exponent vector (a, b, c) for L^a M^b T^c: the dimension of a product (exponents add), of a quotient (they subtract), of the k-th power (they scale by k), and whether u and v have the same dimension, which an equality or a sum of the two quantities needs, as 1 or 0. Consistent dimensions are necessary for a physical equation, not sufficient.
Limits and continuity at a for the function equal to lm·x + lb left of a, to rm·x + rb right of a, and to V at a itself: the left limit lm·a + lb, the right limit rm·a + rb, whether the two-sided limit exists (they agree), and whether the function is continuous at a (both equal V), each decided exactly for exact inputs. The limit does not need V; continuity does.
The affine function f(x) = m·x + b through two points (x₁, y₁) and (x₂, y₂): whether it is defined (x₁ ≠ x₂, as 1 or 0), its slope m = (y₂ − y₁)/(x₂ − x₁), and its intercept b (both 0 when undefined). With m = 0 it is constant; it is linear in the sense of linear algebra only when b = 0.
The solution set of an equation L(x) = R(x) over a finite domain, from the values of both sides on every candidate x and whether both sides are defined there: x is a solution exactly when both sides are defined and their values are equal.
The mean value theorem for f(t) = A·t² + B·t + C on [a, b], a < b: the secant slope (f(b) − f(a))/(b − a), the midpoint c = (a + b)/2, which lies strictly inside, and f′(c) = 2A·c + B, which equals the secant slope: for a quadratic the midpoint is always a witness. When A = 0 every point of (a, b) is one; the witness need not be unique.
The improper integral ∫_lower^∞ scale/x^p dx for lower > 0, defined as the limit of the integrals up to b as b → ∞: it converges exactly when p > 1, to scale·lower^(1 − p)/(p − 1) (0 is returned when it diverges). Integrals up to finitely many cut-offs, however stable they look, do not show convergence.
Linear algebra
std.linalg · 111Inner product of two vectors.
Squared Euclidean norm. Calls dot.
Matrix times vector.
Row vector times matrix.
Outer product: every product xᵢ·yⱼ, by broadcasting. Exact up to one rounding per entry.
Gram matrix of the columns of X.
Bilinear form xᵀ·A·y. Calls matvec, then dot.
Linear combination of two vectors with scalar weights.
Orthogonal projection of x onto the line spanned by u. Calls dot twice.
The part of x orthogonal to u: x minus its projection. Calls proj.
Squared Frobenius norm: the sum of every squared entry.
Euclidean norm. Calls norm_sq.
Scale a non-zero vector to unit length. Calls norm.
Cosine of the angle between two non-zero vectors. Calls dot and norm.
Frobenius norm of a matrix. Calls frobenius_sq.
One Jacobi step for A·x = b, with A split into its diagonal d and the rest R: solve each row for its own unknown, using the others' current values. The body that jacobi_solve runs.
Whether x still misses A·x = b, with A given as its off-diagonal part R and diagonal d: ‖b − R·x − d⊙x‖² above 10⁻²⁰·‖b‖² (a relative residual of 10⁻¹⁰), as 1 or 0. The condition jacobi_solve loops on.
Solve A·x = b by Jacobi iteration for a diagonally dominant A, from x = 0 until the relative residual is below 10⁻¹⁰. The diagonal comes from an Iota mask; the loop is a While.
The solution of A·x = b, by Gaussian elimination with partial pivoting (the Solve primitive).
The inverse of A: Solve against the identity, which is built from two Iotas.
The Cholesky factor of a symmetric positive-definite A: the lower-triangular L with L·Lᵀ = A.
Solve A·x = b for a symmetric positive-definite A the way it is done in practice: factor A = L·Lᵀ, then one forward and one back substitution.
The log-determinant of a symmetric positive-definite A, from its Cholesky factor: twice the sum of the logs of L's diagonal. No determinant is ever formed, so nothing overflows.
The eigenvalues of a symmetric matrix, ascending.
The unit eigenvectors of a symmetric matrix, as columns in ascending order of eigenvalue, each signed so its largest component is positive.
Ridge regression: the coefficients β minimizing ‖X·β − y‖² + λ‖β‖², from the regularized normal equations. λ > 0 keeps them solvable for any X.
The orthonormal factor Q of A = Q·R, for a tall matrix of full column rank: its columns are an orthonormal basis of A's column space.
The triangular factor R of A = Q·R, upper triangular with a positive diagonal.
Least squares: the x minimizing ‖A·x − b‖ for a tall A of full column rank, through QR: R·x = Qᵀ·b. Unlike the normal equations, it does not square A's condition number.
The orthogonal projection onto A's column space, Q·Qᵀ from the QR factorization.
The singular values of A, largest first.
The spectral norm of A: its largest singular value, the most A can stretch a unit vector.
The condition number of A in the 2-norm, largest over smallest singular value: how much A can amplify a relative error.
The nuclear norm of A: the sum of its singular values, the convex stand-in for rank in low-rank recovery.
The Moore–Penrose pseudo-inverse of a tall A of full column rank, from its SVD: V·diag(1/σ)·Uᵀ. It maps b to the least-squares solution.
The orthogonal factor of the polar decomposition A = W·H: the orthogonal matrix nearest to A, U·Vᵀ from the SVD.
The best rank-1 approximation of A (Eckart–Young): σ₁·u₁·v₁ᵀ, from the leading singular triplet.
One more power of x: v ← v·x, elementwise. The body that vandermonde scans; it does not read its sequence element, only counts the steps.
The Vandermonde matrix with decreasing powers, Vᵢⱼ = xᵢ^(p−1−j), p the length of k (only its length is read): V·c evaluates the polynomial c, highest degree first, at every x. NumPy's np.vander(x, p). Each power is the previous one times x, by a reverse Scan of vandermonde_step.
The least-squares polynomial of degree p − 1 through the points (xᵢ, yᵢ), p the length of k (only its length is read), coefficients highest degree first. NumPy's np.polyfit: the columns of the Vandermonde matrix are scaled to unit norm, the scaled system is solved by QR (lstsq), and the scaling is undone. Scaling does not change the solution, only the conditioning.
The trace of a square matrix: the sum of its diagonal, which is also the sum of its eigenvalues.
One step of Gaussian elimination with partial pivoting, on column k: bring the row at or below k with the largest |U[i, k]| to row k, subtract multiples of it from the rows below, and multiply the running determinant d by the pivot, and by −1 for a swap. Columns and rows are taken by Gather, which is exact, so a choice between equal candidates is certain. The body that det scans.
The determinant of a square matrix, by Gaussian elimination with partial pivoting: the product of the pivots, with a sign for each row swap. A Scan of lu_det_step over the columns, carrying the matrix and the determinant so far. The reference is Bareiss's fraction-free elimination, in exact arithmetic.
One more factor of A: M ← M·A. The body that matrix_power scans; it does not read its sequence element, only counts the steps.
The matrix power Aᵖ, p the length of k (only its length is read), by p − 1 multiplications after the first: a Scan of matpow_step from the identity. NumPy's np.linalg.matrix_power(A, p).
The cross product of 3-vectors, row by row: u × v, perpendicular to both, with length |u||v| sin θ. NumPy's np.cross.
A function of a symmetric matrix, f(A) = V·f(Λ)·Vᵀ: f applied to the eigenvalues, the eigenvectors kept. A template over f, verified through f = square, where f(A) is A·A.
The matrix exponential of a symmetric matrix, V·e^Λ·Vᵀ. Through the eigen-decomposition, so f(A) is exact in exact arithmetic. The reference is mpmath's expm at 100 digits, which does not diagonalize.
The principal square root of a symmetric positive-definite matrix, V·√Λ·Vᵀ: the symmetric positive-definite S with S·S = A. Through the eigen-decomposition, so f(A) is exact in exact arithmetic. The reference is mpmath's sqrtm at 100 digits, which does not diagonalize.
The principal logarithm of a symmetric positive-definite matrix, V·log Λ·Vᵀ: the symmetric L with e^L = A. Through the eigen-decomposition, so f(A) is exact in exact arithmetic. The reference is mpmath's logm at 100 digits, which does not diagonalize.
The eigenvalues of a real 2×2 matrix, symmetric or not: the roots of λ² − tr(M)·λ + det(M) = 0, through quadratic_roots. A complex pair is λ ± i·imag, and imag = 0 for real eigenvalues.
One more edge of reachability: R ← min(1, R + R·A), so R picks up every vertex one step further along an edge. The body reachability scans; it does not read its sequence element.
Which vertices each vertex can reach in a finite directed graph, given as a 0/1 adjacency matrix: Rᵢⱼ = 1 when there is a path from i to j, of any length including 0. A Scan of reach_step, n steps from the identity. The reference runs a breadth-first search from every vertex.
The connected components of a finite undirected graph (a symmetric 0/1 adjacency matrix): each vertex is labelled by the smallest vertex it can reach, so two vertices share a label exactly when a path joins them. An isolated vertex is a component of its own.
The number of connected components of a finite undirected graph: the vertices that are their own label.
Whether a given sequence of vertices w₀ … w_k of a finite undirected simple graph is a walk, as 1 or 0: every two consecutive vertices are adjacent, so vertices and edges may repeat; whether it is a simple path, a walk with no vertex twice; and its length k, the number of edges. A single vertex is a simple path of length 0. Whether some path joins two vertices is reachability's question, not this one.
Whether a finite undirected simple graph is a tree, as 1 or 0: connected, with exactly n − 1 edges. Connected with n − 1 edges is a complete certificate; n − 1 edges alone is not.
Whether a finite undirected graph is bipartite, as 1 or 0: it has no closed walk of odd length, which is tr(Aᵏ) = 0 for every odd k ≤ n. The odd traces are read off without a parity test, as (tr(Aᵏ) − tr((−A)ᵏ))/2. The reference two-colours the graph by breadth-first search instead.
Whether a finite undirected simple graph has an Euler trail (a walk using every edge once) and an Euler circuit (one that ends where it started), as 1 or 0 each. Euler's criterion: every vertex with an edge lies in one component, and 0 or 2 vertices have odd degree (0 for a circuit). Isolated vertices do not matter, and a graph with no edges has the empty circuit.
One step of Kahn's algorithm: take the smallest vertex with no incoming edge left among those not yet taken, remove its outgoing edges from the in-degrees, and record it. If none is left, the graph has a cycle and ok becomes 0. The body topological_order scans.
A topological order of a finite directed graph by Kahn's algorithm, always taking the smallest available source, so the order is the lexicographically first one. dag is 1 when every vertex was taken, which is exactly when the graph has no cycle. A Scan of topo_step, n steps.
One step of Prim's algorithm: bring in the vertex outside the tree nearest to it, the smallest on a tie, add that distance to the total, and lower every distance to the new vertex's edges. Once every vertex is in, the step changes nothing. The body mst_prim scans.
The weight of a minimum spanning tree of a complete undirected graph with positive edge weights W, by Prim's algorithm from vertex 0: a Scan of prim_step, n steps. The reference is Kruskal's algorithm with union-find, a route independent of Prim's. On ties the tree may differ, but its weight is the same.
The numerical rank of a matrix with at least as many rows as columns (transpose a wide one first): how many singular values exceed rtol times the largest. NumPy's np.linalg.matrix_rank with tol = rtol·σ₁. For a rank-deficient matrix stored in floating point the exact rank is usually full, with tiny singular values; the tolerance is what makes the question answerable.
One layer of breadth-first search on a 0/1 matrix of open edges: every unvisited vertex with an edge from a visited one is visited, with the smallest such vertex as its parent. The body residual_bfs scans; it does not read its sequence element.
Breadth-first search from vertex 0 along the edges with positive residual capacity R: which vertices are reached, and each one's parent on a shortest path. A Scan of bfs_step, n layers.
One edge of the walk back from the sink along BFS parents: take the edge (parent(v), v), lower the bottleneck to its residual capacity, mark it, and move to the parent; at the source, stop. The body augment scans.
One Edmonds–Karp augmentation of a net flow F, skew-symmetric: breadth-first search in the residual network C − F, then push the bottleneck along the shortest path found, adding it forward and subtracting it backward. The body max_flow loops on.
Whether the sink n − 1 is reachable from the source 0 in the residual network C − F, as 1 or 0: an augmenting path exists. The condition max_flow loops on.
The maximum flow from vertex 0 to vertex n − 1 in a network with capacities C, by Edmonds–Karp: a While over augment until no augmenting path is left. Returns the value, the flow on each edge, and the source side of a minimum cut, the vertices still reachable in the final residual network. By the max-flow min-cut theorem the cut's capacity equals the value. The reference is Ford–Fulkerson with depth-first paths, a different route to the same value and cut.
The capacity of the cut with source side S (a 0/1 vector): the total capacity of the edges from S to its complement. Edges back into S do not count. Every feasible flow's value is at most every cut's capacity.
Whether f is a feasible flow in the network with capacities C, from vertex 0 to vertex n − 1, as 1 or 0: 0 ≤ f ≤ C on every edge, and inflow equals outflow at every inner vertex. Also its value twice, as the source's net outflow and as the sink's net inflow; for a feasible flow the two are equal.
Whether the subset counter c has not yet passed every subset, c < 2ⁿ, as 1 or 0. The condition max_clique loops on.
Test one vertex subset, the bits of c: it is a clique when every pair in it is adjacent, which is bitsᵀ·A·bits = k(k − 1) for k vertices. Keep the largest clique found so far, the first of its size in counter order, and count the cliques of that size. The body max_clique runs.
The clique number ω(G) of a finite undirected simple graph, a maximum clique as a 0/1 vector (the first in counter order), and the number of maximum cliques: every vertex subset is tested, 2ⁿ of them, in a While over clique_step. A maximal clique (one no vertex can join) need not be maximum; only the full search shows that none is larger. ω(G) ≤ χ(G), and the two can differ.
The independence number α(G), a maximum independent set (no two of its vertices adjacent), and the number of maximum independent sets, as the maximum cliques of the complement graph.
The size τ(G) of a minimum vertex cover (a set of vertices touching every edge), one such cover, and the number of minimum covers: the complements of the maximum independent sets, so τ(G) = n − α(G), and the minimizers correspond one to one. A smaller cover than a given one is a witness that the given one is not minimum. An inclusion-minimal cover, from which no vertex can be dropped, need not be minimum.
Whether a set of vertices C (a 0/1 vector) covers every edge of a finite undirected simple graph, as 1 or 0: an edge with neither end in C is a counterexample. The empty set covers a graph with no edges, and a superset of a cover is a cover.
Whether a colouring of the vertices is proper, as 1 or 0: no edge joins two vertices of the same colour. Vertices that are not adjacent may share a colour. A proper colouring with k colours shows χ(G) ≤ k, and only that.
Whether the colouring search is still running: 0 ≤ p < n, as 1 or 0. It ends with p = n when a colouring is complete, and with p = −1 when none exists. The condition k_colorable loops on.
One move of a backtracking search for a proper colouring with k colours: give vertex p its next colour; if it runs past k (past 1 for vertex 0, since colours are interchangeable), clear it and step back; if it clashes with an earlier neighbour, try the next colour; otherwise go on to vertex p + 1. The body k_colorable runs.
Whether a finite undirected simple graph has a proper colouring with k colours, as 1 or 0, and the first one in the search order (colours 1 … k), by backtracking: a While over color_step. A failure is a complete search, and so a proof that χ(G) > k.
Try one more colour: k ← k + 1 and run k_colorable. The body chromatic_number runs.
Whether no colouring has been found yet, as 1 or 0. The condition chromatic_number loops on.
The chromatic number χ(G) of a finite undirected simple graph with at least one vertex, and a proper colouring with χ(G) colours: k_colorable for k = 1, 2, …, until one succeeds. Each failure is a complete search, so the answer is exact; a greedy colouring is only an upper bound. A graph with no edges has χ = 1.
Whether a symmetric 0/1 selection of edges M is a matching of the graph A, as 1 or 0: every selected edge is an edge of A, and no vertex meets two of them. Also its size. A maximal matching, to which no edge can be added, need not be maximum.
One term of the Tutte–Berge formula: for the vertex set U given by the bits of c, (n + |U| − odd(G − U))/2, where odd counts the components of G − U with an odd number of vertices. Keep the smallest so far, and the first U that gives it. The body of max_matching's first loop.
Whether the subset counter c is still below 2ⁿ, as 1 or 0. The condition of max_matching's first loop.
Whether the matching search is still running: 0 ≤ p < n, as 1 or 0. The condition of max_matching's second loop.
One move of a backtracking search for a matching of ν edges: vertex p takes its next choice, a later free neighbour as its partner or, last, no partner of its own. A vertex an earlier one took has only that last choice. Leaving p unmatched is allowed only while at most n − 2ν vertices stay unmatched. Past the last choice, clear p and step back; on a choice not allowed, try the next; otherwise go on to p + 1. The body of max_matching's second loop.
A maximum matching of a finite undirected simple graph with its two certificates. First ν(G) by the Tutte–Berge formula, ν(G) = min over U of (n + |U| − odd(G − U))/2, a While over tutte_step through all 2ⁿ vertex sets U; the first U that attains it is returned, and it bounds every matching from above. Then a matching of ν edges, by a backtracking While over matching_step, as a symmetric 0/1 matrix. The two meet, so the matching is maximum. A maximum matching need not be perfect or unique, and a maximal one (no edge can be added) need not be maximum.
Whether the isomorphism search is still running: 0 ≤ p < n, as 1 or 0. The condition are_isomorphic loops on.
One move of a backtracking search for an isomorphism: give vertex p its next candidate image; if none is left, clear it and step back; if the image is already used, or the edges and non-edges to the earlier vertices do not match, try the next one; otherwise go on to vertex p + 1. The body are_isomorphic runs.
Whether two finite undirected simple graphs on n vertices are isomorphic, as 1 or 0, and the first isomorphism in the search order, as the image of each vertex: a bijection f with {u, v} an edge of A exactly when {f(u), f(v)} is an edge of B. Preserving edges alone is not enough; non-edges must map to non-edges too. By backtracking, a While over iso_step.
Whether a map f, given as the image of each vertex, is an isomorphism from graph A to graph B, as 1 or 0: f is a bijection, and A(u, v) = B(f(u), f(v)) for every pair, edges and non-edges alike.
One column of fraction-free Gaussian elimination (Bareiss) on an integer matrix: if some row at or below r has a nonzero entry in column c, swap the first such row into row r and replace each later row by (p·row − M[i, c]·row r)/prev, which is exact (p the new pivot, prev the one before), then r ← r + 1; otherwise nothing changes. The body rank_exact scans.
The rank of an integer matrix, decided exactly by fraction-free Gaussian elimination: a Scan of bareiss_step over the columns, every entry an integer and every division exact. Unlike matrix_rank, which reads singular values against a tolerance, there is no threshold; the entries must stay below 2⁵³, which the intermediate minors (Hadamard's bound) make the limit.
For k integer vectors in Rⁿ (the rows of V), by exact rank: the rank (the dimension of their span); whether they are linearly independent (rank k, only the zero combination gives 0); whether they span Rⁿ (rank n); and whether they are a basis, which needs both. Neither property stands in for the other.
Whether an integer vector t lies in the span of the integer vectors V (rows), as 1 or 0: adding t does not raise the exact rank. Spans are finite linear combinations; this decides membership over the reals, which a bounded search for coefficients could not. y is in the image of a matrix A exactly when it is in the span of A's columns.
A linear combination Σ cᵢvᵢ of the rows of V with coefficients c, and whether it equals the target t, as 1 or 0: a witness that t is in the span. With integer data the check is exact.
Whether Rⁿ is the internal direct sum of the subspaces U and W, each given by a basis (the rows of U and of W), by exact ranks: dim(U ∩ W) = dim U + dim W − dim(U + W); U ∩ W = {0} gives uniqueness of the decomposition inside U + W, and U + W = Rⁿ is a separate condition; the direct sum needs both. For three or more subspaces, pairwise trivial intersections are not enough.
The rank of an integer matrix A (m × n, a linear map Rⁿ → Rᵐ) and the dimension of its kernel, n − rank by rank-nullity, decided exactly. The kernel is the solution set of Ax = 0; a nonzero right-hand side gives an affine set, not the kernel.
Whether an integer vector x is in the kernel of an integer matrix A, Ax = 0, as 1 or 0, exactly. The solution set of homogeneous equations is a subspace; a set such as a line not through the origin is not.
Whether integer vectors u and v represent the same element of the quotient space Rⁿ/W, as 1 or 0: v − u ∈ W, decided by exact rank; and dim(Rⁿ/W) = n − dim W. The elements of the quotient are cosets, not chosen representatives; the zero coset is W itself.
One step of fraction-free elimination without row exchanges: the pivot M[k, k] is the k-th leading principal minor, and the later rows are eliminated exactly by it over the previous pivot. The body leading_minors scans.
The leading principal minors Δ₁, …, Δₙ of an integer matrix (the determinants of its top-left k × k blocks), exactly, by fraction-free elimination without row exchanges: a Scan of minor_step. Each Δ_k is right as long as the earlier ones are nonzero; valid marks those, and after the first zero minor the later values are not minors.
Whether an integer matrix is symmetric, and whether it is positive definite, each as 1 or 0, by Sylvester's criterion: a symmetric matrix is positive definite exactly when every leading principal minor is positive, decided exactly by leading_minors. Then ⟨x, y⟩ = xᵀAy is an inner product on Rⁿ. Testing ⟨x, x⟩ > 0 on finitely many vectors would not prove it.
The operator norms of a matrix A : Rⁿ → Rᵐ induced by ℓ₁ and by ℓ∞: ‖A‖₁ = max over columns of Σ|a_ij|, and ‖A‖∞ = max over rows of Σ|a_ij|. They are the least C with ‖Ax‖ ≤ C‖x‖ for every x, so A is a bounded operator; a few vectors x satisfying the bound would not be a certificate.
The ℓ₁ and ℓ∞ norms of a vector: Σ|vᵢ| and max |vᵢ|. Each is a norm on Rⁿ: zero only at 0, absolutely homogeneous, and subadditive (the triangle inequality).
The dual basis of a basis b₁ … bₙ of Rⁿ (the rows of B): the covectors φ₁ … φₙ (the rows of Φ) with φᵢ(bⱼ) = δᵢⱼ, which is Φ = (B⁻¹)ᵀ. A covector is a linear functional, not a vector of the space; without an inner product V and V* are not identified.
The eight vector-space axioms on given coordinate vectors u, v, w in Rⁿ and scalars a, b, as 1 or 0 when all hold: associativity and commutativity of addition, the zero vector, additive inverses, both distributive laws, compatibility of scalar multiplication, and 1u = u. With integer data they are checked exactly. Instances that pass do not prove that a candidate structure is a vector space; one that fails disproves it.
Geometry
std.geometry · 22Squared Euclidean distance between two points. Calls norm_sq.
Squared distances between every point of X and every point of Y, with one matrix product.
Centroid (mean point) of a set of points.
Shift a set of points so that its centroid is the origin.
Euclidean distance between two points. Calls sqdist.
Distances between every point of X and every point of Y. Calls pairwise_sqdist, and clamps at zero before the square root.
Lengths of the segments of a polyline through the points P, in order.
Total length of the polyline through the points P. Calls segment_lengths.
Arc length along the polyline at every point, starting from 0: the running sum of the segment lengths. Calls segment_lengths.
Signed area of a polygon by the shoelace formula: positive when the vertices run counter-clockwise. The next vertex of each one comes from joining P[1:] and P[:1].
One-nearest-neighbour classification: the label of the point closest to q. ArgMin gives the position; a mask built from Iota reads the label there.
k-nearest-neighbour regression: the mean value of the k points closest to q (ties by index). The ranks of the distances become a mask, so k can be an input.
Rotate points of the plane counterclockwise by the angle θ (radians) about the origin: each row p of P becomes R(θ)·p.
The angle between two non-zero vectors, in [0, π], by Kahan's formula 2·atan2(‖|v|u − |u|v‖, ‖|v|u + |u|v‖): its absolute error stays near one unit of roundoff (about 10⁻¹⁷ radians here) at every angle, where acos of the normalized dot product errs by up to √u ≈ 10⁻⁸ near 0 and π, and returns 0 for angles below about 10⁻⁸. Calls norm.
From polar coordinates (r, θ) to Cartesian ones: x = r·cos θ, y = r·sin θ.
From Cartesian coordinates (x, y) to polar ones: r = √(x² + y²) and θ = atan2(y, x) in [−π, π].
The central angle between two points on a sphere, given their latitudes and longitudes in radians, by the haversine formula in its atan2 form, which stays accurate for nearby and for nearly antipodal points. Multiply by the radius for the great-circle distance.
Where each point lies relative to the circle with centre O and radius r ≥ 0: −1 inside, 0 on the circle, 1 outside, from the squared distance against r². No square root is taken, so for exact inputs the decision is exact. r = 0 is the degenerate circle {O}.
The quadrant of each point (x, y) of the coordinate plane: 1 for x > 0 and y > 0, 2 for x < 0 and y > 0, 3 for both negative, 4 for x > 0 and y < 0, and 0 on an axis (y = 0 is the x-axis, x = 0 the y-axis, meeting at the origin).
Whether three points A, B, C of the plane (the rows of P) form a non-degenerate triangle, as 1 or 0: they are distinct and not collinear, which is (B − A) × (C − A) ≠ 0; and that cross product, twice the signed area (positive when A, B, C run counterclockwise). Exact for integer coordinates.
Whether triangle B is similar to triangle A with ratio k = p/q > 0 under the given correspondence Aᵢ ↔ Bᵢ (rows of A and B), as 1 or 0, by side-side-side: every corresponding side has |BᵢBⱼ| = k·|AᵢAⱼ|, checked exactly as q²·|BᵢBⱼ|² = p²·|AᵢAⱼ|² for integer coordinates. A reflection keeps the ratio. A failure rules out this ratio and correspondence only, not similarity by another.
Membership of points (the rows of X) in two convex sets: the closed box lo ≤ x ≤ hi, and the closed half-space w·x ≤ β, each as 1 or 0 per point. Both sets are convex for every choice of their data, which is the algebraic certificate; sampling convex combinations would not prove convexity, but one combination of members that falls outside refutes a set's convexity.
Statistics
std.stats · 109Population variance, two-pass: the mean first, then the mean squared deviation.
Population covariance of two paired samples.
Weighted mean with positive weights. Calls dot.
Population standard deviation. Calls variance.
Sample variance, dividing by n − 1. The count comes from the Size primitive. Calls variance.
Standard scores: each element's distance from the mean, in standard deviations. Calls std.
Population covariance matrix of the columns of X. Calls center; the row count comes from Size.
Pearson correlation of two paired samples. Calls covariance and std.
log Σ eˣ, computed stably by shifting by the maximum first.
Rescale to [0, 1] by the minimum and the maximum.
The q-quantile with linear interpolation (NumPy's default): sort, then weigh each sorted value by a tent 1 − |i − h| at position h = (n − 1)·q.
The median: the 0.5-quantile, the mean of the two middle values when n is even. Calls quantile.
Interquartile range: the 0.75-quantile minus the 0.25-quantile. Calls quantile twice.
Median absolute deviation, a robust spread: the median distance from the median. Calls median and abs.
Mean without the smallest and the largest value, which makes it resistant to one outlier at each end.
Maximum drawdown: the largest fall from a running peak to a later value, as used for price series.
Counts per bin for increasing bin edges, with NumPy's rules: half-open bins, the last one closed, values outside the edges not counted. Each value's bin comes from comparisons, becomes an integer slot with Cast, and is counted with ScatterAdd.
Add each value into its segment: x[k] goes to base[seg[k]], and segments that repeat accumulate. A ScatterAdd.
Reorder the values by the stable order of the keys: ArgSort the keys, Cast the positions to indices, Gather the values.
The rank of each value, 0 for the smallest; ties are ranked in input order. The argsort of the argsort.
The log-density of a multivariate normal N(μ, S) at x, computed the stable way: one Cholesky factorization gives both the log-determinant and, by a triangular solve, the quadratic form.
The Mahalanobis distance of x from μ under covariance S: the length of x − μ after whitening by S's Cholesky factor.
Principal component analysis, as the share of variance along each principal axis, largest first: the eigenvalues of the covariance matrix over their sum.
The principal axes of a data set, as columns, largest variance first: the right singular vectors of the centred data, each signed so its largest component is positive.
The bin each value falls into, for bins of equal width starting at lo: ⌊(x − lo)/width⌋, as an integer index. Values below lo get negative bins; nothing is clipped.
The normal distribution's cumulative probability, Φ((x − μ)/σ), written with erfc so the lower tail keeps its relative accuracy where 1 + erf would cancel to 0.
The logarithm of the binomial coefficient C(k + m, k), from log-gamma: log Γ(k+m+1) − log Γ(k+1) − log Γ(m+1). The coefficient itself would overflow long before its logarithm does.
The log-probability of k events under a Poisson distribution with mean λ: k·log λ − λ − log k!, with log k! as log Γ(k + 1).
The log-density of the gamma distribution with shape a and rate b: a·log b + (a − 1)·log x − b·x − log Γ(a).
The log-density of the beta distribution on (0, 1): (a − 1)·log x + (b − 1)·log(1 − x) − log B(a, b), with log(1 − x) as log1p(−x) and log B from log-gamma.
The log-density of Student's t distribution with ν degrees of freedom: log Γ((ν+1)/2) − log Γ(ν/2) − ½·log(νπ) − ((ν+1)/2)·log1p(x²/ν).
The normal distribution's quantile: the x with Φ((x − μ)/σ) = p, as μ + σ·Φ⁻¹(p).
One standard normal number for each element of x, by inverse-transform sampling: Φ⁻¹ of the Wichmann–Hill uniform draws. Reproducible from its state.
The chi-square distribution's cumulative probability with k degrees of freedom: P(k/2, x/2), the regularized lower incomplete gamma function.
The probability of at most k events under a Poisson distribution with mean λ: Q(k + 1, λ), the upper incomplete gamma function, so a small probability keeps its relative accuracy (Round 14.3; 1 − P(k + 1, λ) before).
The gamma distribution's cumulative probability with shape a and rate b: P(a, b·x).
The beta distribution's cumulative probability: I_x(a, b), the regularized incomplete beta function.
Student's t distribution's cumulative probability with ν degrees of freedom, through the incomplete beta function: ½·I_{ν/(ν+x²)}(ν/2, ½) on the left, one minus that on the right.
The probability of at most k successes in k + m independent trials with success probability p (m ≥ 1): I_{1−p}(m, k + 1).
The chi-square distribution's quantile with k degrees of freedom: the x with F(x; k) = p, as 2·P⁻¹(k/2, p).
The gamma distribution's quantile with shape a and rate b: P⁻¹(a, p)/b.
The beta distribution's quantile: the x with I_x(a, b) = p, the inverse incomplete beta function.
Student's t distribution's quantile with ν degrees of freedom, through the inverse incomplete beta function: with z = I⁻¹_{2·min(p, 1−p)}(ν/2, ½), x = ±√(ν(1 − z)/z), negative below the median.
The chi-square distribution's upper tail with k degrees of freedom, the p-value of a chi-square statistic: Q(k/2, x/2), the regularized upper incomplete gamma function. A small p-value keeps its relative accuracy, where 1 − chi2_cdf would round it to 0.
The gamma distribution's upper tail with shape a and rate b: Q(a, b·x).
One bisection step for the Poisson quantile, on every element at once: where the bracket [lo, hi] is still open, mid = ⌊(lo + hi)/2⌋ moves lo up to mid + 1 if F(mid) < p, else hi down to mid. F(mid) is Q(mid + 1, λ) below p = ½ and 1 − P(mid + 1, λ) above it. The body that poisson_quantile runs.
Whether any Poisson-quantile bracket is still open (lo < hi somewhere), as 1 or 0. The condition poisson_quantile loops on; it takes the loop's operands, of which only the bracket matters.
The Poisson distribution's quantile with mean λ: the smallest whole k with P(K ≤ k) ≥ p. A bisection on whole numbers (a While over poisson_quantile_step), from [0, ⌊λ + t⌋ + 2] with t from Bernstein's inequality for the upper tail.
One bisection step for the binomial quantile, on every element at once: where [lo, hi] is still open, mid = ⌊(lo + hi)/2⌋ moves lo up to mid + 1 if F(mid) < p, else hi down to mid. F(mid) is I_{1−π}(n − mid, mid + 1) below p = ½ and 1 − I_π(mid + 1, n − mid) above it. The body that binomial_quantile runs.
Whether any binomial-quantile bracket is still open (lo < hi somewhere), as 1 or 0. The condition binomial_quantile loops on; it takes the loop's operands, of which only the bracket matters.
The binomial distribution's quantile for n trials with success probability π: the smallest k in [0, n] with P(K ≤ k) ≥ p. A bisection on whole numbers (a While over binomial_quantile_step) from [0, n].
The two-sided p-value of a standard normal statistic z: P(|Z| > |z|) = erfc(|z|/√2). erfc keeps a small p-value's relative accuracy.
One-sample t-test of the mean against μ₀: [t, ν, p] with t = (x̄ − μ₀)/(s/√n), ν = n − 1, and the two-sided p = I_{ν/(ν+t²)}(ν/2, ½). The incomplete beta function's lower tail keeps a small p-value's relative accuracy.
Welch's two-sample t-test, without assuming equal variances: [t, ν, p] with t = (x̄ − ȳ)/√(sₓ²/n + s_y²/m), ν from the Welch–Satterthwaite formula, and the two-sided p = I_{ν/(ν+t²)}(ν/2, ½).
The test of a Pearson correlation against zero: [r, p], with the two-sided p from Student's t with ν = n − 2. Since ν/(ν + t²) = 1 − r² for t = r·√(ν/(1 − r²)), the p-value is I_{1−r²}((n − 2)/2, ½) directly. Calls correlation.
Pearson's chi-square goodness-of-fit test: [X², p] with X² = Σ (oᵢ − eᵢ)²/eᵢ over n categories and p = Q((n − 1)/2, X²/2), the chi-square upper tail with n − 1 degrees of freedom.
Midranks, 1 for the smallest value, with tied values sharing the average of the ranks they span. Each value's midrank is the number of values below it plus (the number equal to it + 1)/2, counted by exact comparisons of every pair.
Spearman's rank correlation: the Pearson correlation of the two samples' midranks, so ties are handled by average ranks. Calls midrank and correlation.
The test of Spearman's rank correlation against zero, by the usual t approximation: [ρ, p] with the two-sided p = I_{1−ρ²}((n − 2)/2, ½), Student's t with n − 2 degrees of freedom. An approximation to the exact permutation distribution, closer as n grows. Calls spearman_r.
The Mann–Whitney U test (Wilcoxon rank-sum) by the normal approximation with the tie correction, without a continuity correction: [U, p] with U = Rₓ − n(n + 1)/2 from x's midranks in the combined sample, σ² = nm/12·((N + 1) − Σ(t³ − t)/(N(N − 1))) and the two-sided p = erfc(|U − nm/2|/(σ√2)). An approximation to the exact distribution, closer as n and m grow.
One step of the Kalman filter for a local-level model, independently in each coordinate: predict the variance P + Q, weigh the observation z by the gain K = (P + Q)/(P + Q + R), and update the mean m and the variance. The body that kalman_level scans.
Filter a sequence of noisy observations with a local-level Kalman filter: a random walk observed with noise, in each coordinate independently. Returns the filtered mean and variance after every observation. A Scan with two carries, m and P (Round 14.10).
The mean direction of angles (radians): the direction of the sum of their unit vectors, atan2(Σ sin θ, Σ cos θ), in [−π, π]. The arithmetic mean of 359° and 1° is 180°; their circular mean is 0°.
The circular variance of angles (radians): 1 − R̄, with R̄ the length of the mean of their unit vectors; 0 when every angle is the same, near 1 when they spread evenly around the circle.
The exponential distribution's cumulative probability, 1 − e^(−λx) for x ≥ 0 and 0 below, written as −expm1(−λx) so that it keeps its relative accuracy for small λx.
The exponential distribution's quantile: −log(1 − p)/λ, written with log1p so that small p keep their relative accuracy.
The exponential distribution's log density at x ≥ 0: log λ − λx.
The log-normal distribution's cumulative probability: Φ((log x − μ)/σ) for x > 0. Calls normal_cdf.
The log-normal distribution's log density at x > 0: −log x − log σ − ½log 2π − (log x − μ)²/(2σ²), with π as arccos(−1).
The Weibull distribution's cumulative probability with shape k and scale λ: 1 − e^(−(x/λ)ᵏ) for x > 0, written with expm1.
The Weibull distribution's quantile: λ·(−log(1 − p))^(1/k), written with log1p.
The F distribution's cumulative probability with d₁ and d₂ degrees of freedom: I_{d₁x/(d₁x+d₂)}(d₁/2, d₂/2), the regularized incomplete beta function.
The F distribution's upper tail P(F > x): I_{d₂/(d₂+d₁x)}(d₂/2, d₁/2), the same beta integral read from the other end, so that a small tail keeps its relative accuracy.
Paired t-test of two matched samples: the one-sample t-test of their differences against 0, giving [t, ν, p]. Calls t_test_1samp.
One-way analysis of variance for g groups of n observations each, the rows of X: [F, d₁, d₂, p] with F the ratio of the between-group to the within-group mean square, d₁ = g − 1, d₂ = g(n − 1), and p = P(F_{d₁,d₂} > F). Calls f_sf.
Bayes' theorem on a finite partition of hypotheses: the posterior P(Hᵢ | E) = P(Hᵢ)·P(E | Hᵢ) / Σⱼ P(Hⱼ)·P(E | Hⱼ). The evidence in the denominator is the law of total probability, and it must be positive.
The two marginals of a finite joint distribution given as a table of masses P(X = i, Y = j): P(X = i) = Σⱼ, and P(Y = j) = Σᵢ.
The conditional distributions P(Y = j | X = i) = P(X = i, Y = j) / P(X = i) of a finite joint table, one row per value of X. Each row sums to 1; a row of zero mass has no conditional distribution.
The conditional expectation E[Y | X = i] = Σⱼ yⱼ·P(Y = yⱼ | X = i) for a finite joint table and the values yⱼ of Y. Averaging it over P(X) gives E[Y], the law of total expectation.
One step of a finite Markov chain: the distribution π over the states becomes π·P, for the transition matrix P with Pᵢⱼ = P(Xₙ₊₁ = j | Xₙ = i). The body markov_distribution scans; it does not read its sequence element.
The distributions of a finite Markov chain after 1 … s steps from π₀, s the length of steps (only its length is read): row n is π₀·Pⁿ⁺¹. A Scan of markov_step.
The stationary distribution π of a finite Markov chain, with π·P = π and Σπ = 1: one solve of (Pᵀ − I)·π = 0 with its last equation replaced by the normalization. Unique for an irreducible chain. The reference solves the full system with every equation and the normalization, by least squares, which is exact for a consistent system.
The probability of an event E on a finite sample space with masses p: the sum of the masses of the outcomes in E, given as a 0/1 indicator. Only when the outcomes are equally likely is it |E|/|S|.
The modes of a finite list of observations: the values that occur most often. Returned as the sorted observations with a 0/1 mark on the first occurrence of each mode, so the mode set is the marked values in increasing order. When every value occurs once, every value is a mode.
The bias E_θ[T] − θ of an estimator T whose finite sampling law under θ gives the value tᵢ the probability pᵢ.
The variance of an estimator T under its finite sampling law: Σ pᵢ(tᵢ − E[T])².
The mean squared error of an estimator T under its finite sampling law at θ, computed directly: Σ pᵢ(tᵢ − θ)². It equals bias² + variance, a theorem the tests check rather than the definition used. MSE = 0 exactly when T = θ almost surely.
The law of a random variable X on a finite sample space, for one law or a family of laws (one per row of P): P(X = t) = Σ over the outcomes s with X(s) = t of P(s). With a statistic T and a parametric family P_θ it is T's sampling distribution, one row per θ. X is given by value indices into 0 … k − 1 (a carrier vector of length k, only its length read). It is not a likelihood or a posterior.
The two sides of independence for events A and B on a finite probability space: P(A ∩ B) and P(A)·P(B), and their difference; A and B are independent when it is 0. When P(B) > 0 this is the same as P(A | B) = P(A); when P(B) = 0 the product form still applies and A and B are independent. Two events only: pairwise independence of three events does not give mutual independence.
Independence of two finite random variables from their joint table J (J[x, y] = P(X = x, Y = y)): the marginals of X and Y, the deviation J − P(X)·P(Y)ᵀ, and its largest magnitude. X and Y are independent exactly when every entry of the deviation is 0. Zero covariance is a consequence of independence, not a test for it.
The law of total variance on a finite probability space, with the conditioning given by a partition of the outcomes into cells (g[s] the cell of s): the expected conditional variance E[Var(X | G)], the variance of the conditional mean Var(E[X | G]), and Var(X), which is their sum. A zero-mass cell contributes nothing; its conditional values are determined only almost surely, so it is never divided by. The two parts are not interchangeable, and the cells need not be independent.
Markov's inequality on a finite law, for X ≥ 0 and a > 0: the actual tail P(X ≥ a) and the bound E[X]/a. The bound is not the tail, and it does not apply to a variable that takes negative values.
Chebyshev's inequality on a finite law, for ε > 0: the actual tail P(|X − μ| ≥ ε), decided as (X − μ)² ≥ ε², and the bound Var(X)/ε². It is Markov's inequality applied to the squared deviation; it needs no independence, and the bound is not the tail.
The coverage of an interval procedure [L(x), U(x)], fixed for every possible sample x before the data are seen, over a finite family of laws P_θ (one row per θ, with the θ values given): for each θ, Σ_x P_θ(x)·[L(x) ≤ θ ≤ U(x)], and the worst case, the minimum over θ. A high average coverage does not make the worst case high, and coverage is not a posterior probability. A selection rule must be part of the procedure before coverage is computed.
The maximum-likelihood estimator on a finite parametric model, one law P_θ per row: for every possible sample x, the likelihood θ ↦ P_θ(x) is maximized over all θ, and the estimate is the first θ attaining it, a fixed tie order that does not depend on the unknown θ. Also the maximal likelihood, whether there is a tie, and whether every likelihood is 0 there. The MLE maximizes the likelihood, not a posterior; it need not be unique, unbiased or consistent.
Sufficiency of a statistic T on a finite parametric model: the conditional law P_θ(x | T = T(x)) for every θ and sample x (0 on a zero-mass cell, where it is undefined), and for each x the spread of that conditional probability across the θ for which its cell has positive mass. T is sufficient exactly when every spread is 0: within each fibre of T the conditional law does not depend on θ. The factorization theorem is not used.
The expectation E_θ[T] of a statistic T (its value t(x) on each sample x, never indexed by θ) under every law of a finite parametric family, one per row: the vector P·t. It says nothing by itself about bias, consistency or sufficiency.
The one-time marginals of a discrete-time process on a finite horizon, given by the complete list of its paths (each a row of state indices over the times) and their probabilities: P(X_t = s) for every time t and state s. A finite-horizon joint law gives the marginals and the two-time joints; it does not by itself give the Markov property or stationarity.
The two-time joint law P(X_{t1} = s, X_{t2} = s′) of a finite-horizon process given by its complete list of paths and their probabilities.
One factor of a Bernoulli cylinder probability: acc·p for a 1, acc·(1 − p) for a 0. The body bernoulli_word scans.
The probability that an IID Bernoulli(p) sequence begins with a given finite 0/1 word: p^(number of 1s)·(1 − p)^(number of 0s), the cylinder probability of the product law. A finite prefix defines a finite IID family; it does not by itself establish an infinite IID sequence.
One step of a filtration check: the later partition (labels b2) refines the earlier one (labels a), so two outcomes in one block later were in one block before. The body is_filtration scans.
Whether a sequence of at least two partitions of one finite sample space (row t gives each outcome's block label at time t) is a filtration, as 1 or 0: each partition refines the one before, which is the inclusion F_s ⊆ F_t of the σ-algebras they generate, every pair of outcomes checked. A Scan of refine_step. A filtration only nests information; it does not make a process adapted, natural or Markov.
One time step of a martingale check on a finite probability space: on each block of the partition F_t, E[X_{t+1} | F_t] − X_t (0 on a zero-mass block, which is determined only almost surely), and whether X_t is constant on the blocks of F_t (adapted). The body martingale_check scans.
The martingale conditions for a process X_0 … X_T (one row per time) on a finite probability space with a filtration given by partitions L (one row per time): whether L is a filtration; whether X is adapted (each X_t constant on the blocks of F_t); and the gaps E[X_{t+1} | F_t] − X_t for t < T, which are all 0 for a martingale. Integrability is automatic on a finite space. A martingale need not have independent increments, be Markov, or converge.
The axioms of a σ-algebra on a finite set, given as the complete list of its members (one subset per row), as 1 or 0: it contains ∅ and X, it is closed under complements, and under unions. On a finite set a countable union reduces to finitely many distinct sets, so pairwise unions suffice.
The axioms of a measure on a finite σ-algebra (its members one per row, with their measures μ): whether μ ≥ 0 and whether μ(∅) = 0, each as 1 or 0; and the additivity gap, the largest |μ(A ∪ B) − μ(A) − μ(B)| over disjoint members A, B, which is 0 for a measure. On a finite σ-algebra countable additivity reduces to additivity over pairs of disjoint sets.
Whether a map f between finite measurable spaces (X, Σ_X) and (Y, Σ_Y), each σ-algebra listed in full, is measurable, as 1 or 0: the preimage f⁻¹(B) of every B ∈ Σ_Y is in Σ_X. The same preimage test as continuity; measurability implies neither continuity nor integrability.
The least N ≥ 0 with |u_n − L| = |c|/(n + d) < ε for every n ≥ N, for the sequences u_n = L + c/(n + d) (d ≥ 1) and ε = p/q > 0 given by positive integers, in exact integer arithmetic: N = max(0, ⌊|c|q/p⌋ − d + 1). The error never grows along the tail, so this one N works for the whole tail, which a finite sample of terms could not show; equality |c|/(n + d) = ε does not count. Over a finite domain, one c and d per point, it is a pointwise witness at each point, and their maximum is a uniform one.
Sequences
std.seq · 90First differences: each element minus the one before it. One element shorter than x.
Running total: element i is the sum of x₀ … xᵢ.
Running mean: element i is the mean of x₀ … xᵢ. The counts 1, 2, … come from Iota.
1² + 2² + … + n², with n the length of x (its values are not used): Iota counts 1 … n, each count is squared, and the squares are added. This is the intent the family home follows through EML-U, EML-P and EML-NOVA; for x of length 100 it is 338350.
Trapezoid rule with unit spacing: the area under the samples y.
Trapezoid rule over sample points x (any spacing, in order). Calls diff.
Moving average over a window of three, at every position where the window fits.
One-dimensional convolution with a three-tap kernel w, valid positions only — cross-correlation, as deep-learning libraries define it.
One step of an exponential moving average: blend the new value into the running one. The body that ema scans.
Exponential moving average of a series, started at its first value: a Scan of ema_step.
One step of a discounted return: this reward plus γ times the return after it. The body that discounted_returns scans, backwards.
Discounted returns of a reward sequence, as in reinforcement learning: a reverse Scan of discount_step.
One step of Horner's rule: multiply by t, add the next coefficient. The body that horner scans.
Evaluate a polynomial at t by Horner's rule, coefficients from the highest degree down: a Scan of horner_step, keeping the last value.
One forward-Euler step of the linear system x′ = A·x over a time step dt. The body that euler_linear scans.
Integrate x′ = A·x from x₀ by forward Euler over the time steps dts; returns the state after every step. A Scan of euler_step.
Reorder a vector by a permutation: element i of the result is x[perm[i]]. A Gather.
The inverse of a permutation: inv[perm[i]] = i. Each position is scattered to where it came from, then Cast back to integers.
One step of Newton's method for √a: average the guess with a divided by it. The body that sqrt_newton runs.
Whether a square-root guess still misses: |s² − a| above 10⁻¹² of a, as 1 or 0. The condition sqrt_newton loops on.
√a by Newton's method, starting from (a + 1)/2 and stopping once |s² − a| ≤ 10⁻¹²·a: a While over newton_sqrt_step until sqrt_unconverged says stop.
One bisection step for x³ = a: halve the bracket [lo, hi], keeping the half where x³ − a changes sign. The body that cbrt_bisect runs.
Whether a bisection bracket is still too wide: hi − lo above 10⁻¹²·(|a| + 1), as 1 or 0. The condition cbrt_bisect loops on.
∛a by bisection: start from the bracket ±(|a| + 1), which always contains the root, and halve it until it is narrower than 10⁻¹²·(|a| + 1). A While whose state is the bracket itself.
One step of a polynomial rolling hash: multiply by 131, add the next code, reduce modulo the prime 1 000 000 007. Every value stays below 2⁵³, so the arithmetic is exact. The body poly_hash scans.
A polynomial rolling hash of a sequence of byte codes: a Scan of hash_step from 0, keeping the last value. Equal sequences hash equally; it is not a cryptographic hash.
The discrete Fourier transform of a complex vector, unnormalized: yₖ = Σⱼ zⱼ·e^(−2πi·jk/n).
The inverse discrete Fourier transform: zⱼ = (1/n)·Σₖ yₖ·e^(2πi·jk/n), so ifft(fft(z)) = z.
The power spectrum of a real signal: |yₖ|² for its discrete Fourier transform y, the energy at each frequency.
The circular convolution of two real signals through the Fourier transform: transform both, multiply, transform back, keep the real part. Takes n log n operations instead of n².
The circular autocorrelation of a real signal, rₖ = Σⱼ xⱼ·x₍ⱼ₊ₖ₎ mod n, by the Wiener–Khinchin theorem: the inverse transform of the power spectrum.
One step of the Wichmann–Hill generator (AS 183, 1982): three small multiplicative congruential generators side by side, each sᵢ ↦ aᵢ·sᵢ mod mᵢ. It is the body uniform_draws scans; the element it is handed only sets how many steps there are.
One uniform number in [0, 1) for each element of x, from the Wichmann–Hill generator started at state: a Scan of wichmann_hill_step, then the fractional part of s₁/m₁ + s₂/m₂ + s₃/m₃. The same state always gives the same numbers, on every backend. Its period is about 7·10¹²; it is not for cryptography.
A reproducible random permutation of x: draw one uniform number per element, then sort the elements by their numbers.
The 64-bit product of two 32-bit words, as its high and low halves: [⌊a·b/2³²⌋, a·b mod 2³²]. Composed from 16-bit halves, so every intermediate stays below 2³⁴ and int64 holds it exactly; a·b itself would not fit.
One round of Philox4x32 on every counter at once: with the round key k = key + r·W mod 2³² and (hi, lo) the halves of M·x, the words (x₀, x₁, x₂, x₃) become (hi₁ ⊕ x₁ ⊕ k₀, lo₁, hi₀ ⊕ x₃ ⊕ k₁, lo₀). The body that philox4x32_10 scans, once per round r.
Philox4x32-10: ten rounds of philox4x32_round (a Scan over r = 0 … 9) on four-word counters under a two-word key. Random123's generator: each output depends only on its counter and the key, so a tensor of counters draws all its numbers at once. Its authors report that it passes TestU01's BigCrush.
Uniform draws in (0, 1) from Philox4x32-10, one per counter, under a key: 52 bits, the high 20 of the first word and all 32 of the second, as (v + ½)/2⁵². Exact in float64, and never 0 or 1. A key is a stream; counters 0, 1, 2, … are its draws, reproducible on every backend.
Standard normal draws from Philox4x32-10, one per counter: Φ⁻¹ of philox_uniform. Inverse-transform sampling; the uniform never reaches 0 or 1, so every draw is finite (|z| < 8.3).
Composite Simpson's rule on 2m + 1 equally spaced samples y with spacing h: (h/3)(y₀ + 4y₁ + 2y₂ + … + 4y₂ₘ₋₁ + y₂ₘ). It is exact for cubics, and for smooth functions its error falls as h⁴. The samples are read in pairs by reshaping 2m values into m rows of two, which the shape checker proves for every m.
One step of the Legendre recurrence (k + 1)Pₖ₊₁(x) = (2k + 1)·x·Pₖ(x) − k·Pₖ₋₁(x), at every point of x at once: from (Pₖ₋₁, Pₖ) to (Pₖ, Pₖ₊₁). The body that gauss_legendre scans.
The n-point Gauss–Legendre rule on [−1, 1], n the length of points (only its length is read): nodes x ascending and weights w, so that Σ wᵢ·f(xᵢ) is exact for every polynomial of degree up to 2n − 1. By Golub–Welsch: the nodes are the eigenvalues of the symmetric tridiagonal Jacobi matrix with off-diagonal βₘ = m/√(4m² − 1), then one Newton step on Pₙ, which is zero in exact arithmetic and brings each node to within about a unit of roundoff; each weight is 2(1 − x²)/(n·Pₙ₋₁(x))², with Pₙ and Pₙ₋₁ from the three-term recurrence.
Piecewise-linear interpolation through the points (xⱼ, yⱼ), x increasing, at each query point xq; beyond either end, the end value. NumPy's np.interp. The segment is found by counting the xⱼ at or below each query, exactly.
One column of Newton's divided-difference table: where the mask m is 1, dᵢ becomes (dᵢ − dᵢ₋₁)/gᵢ, with gᵢ = xᵢ − xᵢ₋ₖ; where it is 0, dᵢ stays. S shifts a vector down by one. The body that divided_differences scans, one order k per step.
The coefficients of Newton's form of the polynomial through (xⱼ, yⱼ), x distinct: cₖ = f[x₀, …, xₖ], the divided differences. A Scan of divided_difference_step, one order per step, so that p(t) = c₀ + c₁(t − x₀) + … + cₙ₋₁(t − x₀)…(t − xₙ₋₂).
One step of Horner's rule for Newton's form: p ← cₖ + (t − xₖ)·p, at every t. The body that newton_eval scans, from the last coefficient down.
Evaluate a polynomial in Newton's form, c₀ + c₁(t − x₀) + … + cₙ₋₁(t − x₀)…(t − xₙ₋₂), at each t, by Horner's rule: a reverse Scan of newton_horner_step.
The polynomial of degree n − 1 through the n points (xⱼ, yⱼ), x distinct, evaluated at each query point xq: Newton's divided differences, then Horner's rule for Newton's form. The same polynomial as Lagrange's formula, the reference.
The derivative of a polynomial, coefficients from the highest degree down as horner takes them: cₖ·(n − 1 − k) for every coefficient but the constant. NumPy's np.polyder.
The antiderivative of a polynomial that is 0 at t = 0, coefficients from the highest degree down: cₖ/(n − k), then a zero constant term. NumPy's np.polyint.
The product of two polynomials, coefficients highest degree first as horner takes them: (fg)ₖ = Σᵢ fᵢ·gₖ₋ᵢ, the finite convolution, computed as a Toeplitz matrix of g times f. Exact for integer coefficients, where every product and sum is an integer. NumPy's np.polymul.
Whether p = f·g as polynomials, as 1 or 0: the product's coefficients, every list highest degree first, compared with p's one by one, not at sample points; and the product itself. Factors and product are compared as given, so leading zeros must be removed first, and a rescaled or reordered factor is the caller's to normalize. Exact for integer coefficients; for rational ones, multiply p by the product of the factors' denominators, and each factor by its own, first.
The degree of a polynomial, coefficients highest degree first: whether it has one (1 or 0: the zero polynomial has no degree), the degree n − 1 − k for the first nonzero coefficient cₖ, and that leading coefficient; 0 for both when there is no degree. Leading zeros do not change the polynomial, and −0 counts as zero. Exact.
The net present value of a cash flow c₀, c₁, … at one per period, at rate i per period: Σ cₜ/(1 + i)ᵗ, with c₀ undiscounted. Computed as the discounted return at factor 1/(1 + i), by Horner's rule from the last cash flow back.
One step of a linear recurrence in companion form: the window of the last r terms becomes C·window + b, where C shifts the window up and puts Σ coefficients·window in the last place. The body linear_recurrence scans.
The next s terms of a linear recurrence of order r: aₙ = constant + Σⱼ coeffsⱼ·aₙ₋ᵣ₊ⱼ, from the initial values a₀ … aᵣ₋₁, s the length of steps (only its length is read). A Scan of recurrence_step on the companion matrix. Fibonacci is r = 2, coefficients (1, 1), constant 0.
One step of the discrete exponential model: x ← r·x. The body geometric_growth scans.
The trajectory of the discrete exponential model xₙ₊₁ = r·xₙ for s steps, s the length of steps (only its length is read): row n is x₀·rⁿ⁺¹. A Scan of growth_step.
One step of the discrete logistic model: x ← x + r·x·(1 − x/K). The body logistic_growth scans.
The trajectory of the discrete logistic model xₙ₊₁ = xₙ + r·xₙ(1 − xₙ/K) for s steps, s the length of steps (only its length is read). With K > 0, 0 ≤ r ≤ 1 and 0 ≤ x ≤ K, every step stays in [0, K], and 0 and K are fixed points. A Scan of logistic_step.
One transition of a deterministic finite automaton: state ← δ(state, symbol), read from the transition table δ. The body dfa_run scans.
Run a deterministic finite automaton on a word: from the start state, one transition per symbol through dfa_step, then accept when the final state is accepting. accept is 1 or 0 per state. The empty word is accepted exactly when the start state is accepting.
One symbol of a nondeterministic finite automaton run on the set of current states (a 0/1 vector): every transition on the symbol, then every ε-move, through the ε-closure C. The body nfa_accepts scans.
Whether a nondeterministic finite automaton with ε-moves accepts a word, as 1 or 0: the subset simulation, carrying the set of reachable states as a 0/1 vector. T[σ] is the 0/1 transition relation of symbol σ, E the ε-moves, and C its reflexive transitive closure (reachability). The reference follows the sets of states directly.
The finite-difference solution of the boundary-value problem −u″ = f on a uniform grid with spacing h and Dirichlet values u_a, u_b at the two ends: the values at the n interior points, from (2uᵢ − uᵢ₋₁ − uᵢ₊₁)/h² = fᵢ. One solve of the tridiagonal system. It is exact for every quadratic u. The reference is the Thomas algorithm.
The five-point Laplacian (uᵢ₋₁,ⱼ + uᵢ₊₁,ⱼ + uᵢ,ⱼ₋₁ + uᵢ,ⱼ₊₁ − 4uᵢⱼ)/h² at the interior points of a grid of values with spacing h. It equals the exact Laplacian for every polynomial of degree at most 3, so a candidate solution of Poisson's equation can be checked on a grid.
The Laplacian of the quadratic u(x, y) = c₀ + c₁x + c₂y + c₃x² + c₄xy + c₅y², a constant: 2c₃ + 2c₅. Poisson's equation Δu = f holds inside a domain for a quadratic candidate exactly when f is that constant.
The quadratic u(x, y) = c₀ + c₁x + c₂y + c₃x² + c₄xy + c₅y² restricted to the line x = x₀: a quadratic in y, coefficients highest degree first, (c₅, c₂ + c₄x₀, c₀ + c₁x₀ + c₃x₀²). Comparing them with the Dirichlet data on an edge, coefficient by coefficient, checks the boundary condition exactly.
The quadratic u(x, y) = c₀ + c₁x + c₂y + c₃x² + c₄xy + c₅y² restricted to the line y = y₀: a quadratic in x, coefficients highest degree first, (c₃, c₁ + c₄y₀, c₀ + c₂y₀ + c₅y₀²).
The geometric series Σ_{k≥0} a·rᵏ, elementwise: the partial sum of its first N terms, a(1 − rᴺ)/(1 − r) (N·a for r = 1); and, where |r| < 1, its limit a/(1 − r) and the remainder a·rᴺ/(1 − r) after N terms, with converges = 1. Where |r| ≥ 1 the series diverges (or, for r = −1, oscillates), and the limit, remainder and converges are 0. The reference adds the N terms one by one.
The telescoping sum Σ_{k=0}^{N−1} (b_k − b_{k+1}) = b_0 − b_N of a sequence b_0 … b_N: every inner term cancels. The infinite series converges exactly when b_N has a limit, to b_0 − lim b_N.
Two estimates of the radius of convergence R of Σ aₙ(x − c)ⁿ from its coefficients a₀ … a_N: the ratio |a_{N−1}/a_N| and the root |a_N|^(−1/N). Each converges to R when the corresponding limit exists, and for aₙ = qⁿ both equal 1/|q|. A finite prefix of coefficients does not determine R, so these are estimates, not the radius.
The motion of the linear harmonic oscillator m·x″ + k·x = 0 with mass m > 0 and stiffness k > 0, from x(0) = x₀ and x′(0) = v₀: x(t) = x₀ cos ωt + (v₀/ω) sin ωt and v(t) = v₀ cos ωt − x₀ω sin ωt, with ω = √(k/m). The energy ½mv² + ½kx² is constant.
One coefficient of a synthetic-division pass: out = cⱼ + mⱼ·a·(the previous output), where the mask mⱼ says whether this coefficient takes part in the pass. The body taylor_pass scans.
Pass t of the Taylor shift by repeated synthetic division: coefficients 1 … n − 1 − t each add a times the coefficient just before them, as already updated. The body poly_taylor_at scans.
The Taylor coefficients of a polynomial at a: the coefficients of p in powers of (x − a), highest degree first, so the last is p(a), the one before it p′(a), and the k-th from the end p⁽ᵏ⁾(a)/k!. By repeated synthetic division, n passes of taylor_pass. A polynomial of degree at most n − 1 is reconstructed exactly. The reference is the closed form with binomial coefficients.
One closure step of the CYK recognizer for a grammar in Chomsky normal form: X[A, i, j] = 1 when A derives the part w[i:j] of the word; for every rule A → B C (listed as RB, RC with the one-hot heads OHt) and every split point, a derivation of w[i:k] is added. The body cyk scans.
Whether a grammar in Chomsky normal form derives a word, as 1 or 0, by the CYK recognizer, and the table X[A, i, j] of which nonterminals derive which parts w[i:j]. The grammar is k nonterminals, terminal rules Tm[A, σ] for A → σ, binary rules A → B C listed as RA, RB, RC, and a start symbol. The table is closed under the binary rules by L steps of cyk_step, each one batched product per rule. A word of length L ≥ 1; CYK decides membership, unlike a bounded search, whose failure would prove nothing.
One step of a deterministic Turing machine on a tape of T listed cells (unlisted cells are blank and never needed while fell stays 0): in state q reading σ, write Write[q, σ], move by Move[q, σ] ∈ {−1, 0, +1}, and enter Next[q, σ]; a halting state (accept or reject) has no transitions and stays put. fell becomes 1 if the head would leave the listed tape. The body tm_run scans.
Run a deterministic Turing machine for s steps (s the length of steps, only its length read) from the start state with the head on cell 0 of the listed tape: a Scan of tm_step. Returns the final state, head and tape, whether the head ever tried to leave the listed tape, and whether the machine has halted. A finite trace settles that one input only: a run that has not halted proves neither rejection nor non-termination, and one halting trace does not make the machine a decider.
For a polynomial p (coefficients highest degree first), a center a, a point x and an order n: p(x), the Taylor polynomial T_n(x) of p at a, and the remainder p(x) − T_n(x), computed directly. The remainder is 0 when n ≥ deg p. A finite jet says nothing about the Taylor series of a non-polynomial function, or about analyticity.
The fundamental theorem of calculus for a polynomial f (coefficients highest degree first): an antiderivative F with F(0) = 0, and the directed integral ∫_a^b f = F(b) − F(a); reversed limits change its sign and equal ones give 0.
Whether a candidate polynomial F is an antiderivative of the polynomial f, F′ = f, checked coefficient by coefficient (coefficients highest degree first, F one longer than f), as 1 or 0. A candidate that fails does not show that f has no antiderivative; agreement at sampled points would not show F′ = f.
The residual of a quadratic candidate u = u₀ + u₁x + u₂y + u₃x² + u₄xy + u₅y² in the linear constant-coefficient equation a·u_xx + b·u_xy + c·u_yy + d·u_x + e·u_y + f·u = g, where g is a quadratic in the same basis, as a coefficient vector: u solves the equation everywhere exactly when every coefficient is 0 (a zero residual at one point proves only that point). Also the discriminant b² − 4ac of the principal part (by this convention: negative elliptic, zero parabolic, positive hyperbolic).
The values of the two-variable real polynomial u₀ + u₁x + u₂y + u₃x² + u₄xy + u₅y² (coefficients in that fixed order) at given points (x, y), the rows of pts.
One node of a regular expression's syntax tree, evaluated on the word's parts: the node's 0/1 span matrix over the fenceposts, from its children's matrices: ε the identity, a symbol the single steps that read it, union the elementwise or, concatenation the boolean product, star the reflexive transitive closure (reachability), the empty language 0. The body regex_match scans.
Whether a word is in the language of a regular expression, as 1 or 0, decided exactly: the syntax tree is listed node by node, children first (kind 0 empty, 1 ε, 2 symbol, 3 union, 4 concatenation, 5 star), the last node the root, and each node's span matrix over the word's fenceposts comes from its children's by regex_node_step. Star is the full closure, not a bounded unrolling, so membership is decided rather than searched. Two expressions agreeing on all words up to some length are not shown equal.
One step of checking a pushdown automaton's run: apply transition x if it fits the configuration (its from-state is the current state, it reads the next input symbol or ε, and the stack top is the symbol it needs): pop that top, push its replacement bottom to top, and move to its to-state. A transition that does not fit, or would overflow the listed stack, makes the run invalid and leaves the configuration as it was. The body pda_run_check scans.
Whether a given run, a list of transition indices, is an accepting run of a pushdown automaton on a word, as 1 or 0: every step fits its configuration (pda_step), the whole input is read, and the final state is accepting (acceptance by final state, not by empty stack); and whether every step fitted. A run is a witness of membership; failing to find one by a bounded search proves nothing, and says nothing about the automaton's determinism or its grammar.
The pumping-lemma split of a word read by a DFA: the first repeated state among the states after 0, 1, …, L symbols gives w = xyz with x the part before the first visit, y the loop (|y| > 0), and |xy| ≤ the number of states when the word is at least that long (pigeonhole). Reading y returns the automaton to the same state, so xyⁱz is accepted exactly when w is, for every i ≥ 0: the loop is a certificate for all i, not a check of a few. Also whether a repeat exists and the loop's state.
Neural networks
std.nn · 15Affine layer: a batch of rows times a weight matrix, plus a bias.
Two-layer perceptron with a ReLU between the layers. Calls linear twice.
Scaled dot-product attention for one head.
Log of the softmax, computed as x − logsumexp(x) without forming the softmax. Calls logsumexp.
Layer normalisation of one feature vector, with scale γ, shift β and a small ε. Calls variance.
Scaled dot-product attention with the standard 1/√d scale computed inside the graph (Size, then Sqrt). Calls attention.
One step of an Elman recurrent network: the next hidden state from the current one and an input. The body that rnn scans.
Run an Elman recurrent network over a sequence of inputs; returns every hidden state. A Scan of rnn_cell, differentiable end to end.
One step of a long short-term memory (LSTM) cell: from the hidden state h, the cell state c and an input x, the next h and c. The four gates (input, forget, output, candidate) each take their weights from W, U and b by index. The body that lstm scans.
Run an LSTM over a sequence of inputs; returns every hidden state and every cell state. A Scan of lstm_cell with two carries, h and c (Round 14.10), differentiable end to end.
Classification accuracy: the share of rows whose largest logit is at the position of the largest label entry (one-hot labels).
Causal (decoder) self-attention: row i attends only to rows j ≤ i. The mask compares positions from Iota (j > i is the future); future scores are replaced by the row minimum before the stable softmax, so nothing can overflow, and their weights are set to zero after it.
Embedding lookup: the rows of the table E at the integer ids, in order (repeats allowed).
The mean of the embeddings of a bag of ids: one vector for a whole set of tokens. Calls embedding_lookup.
The posterior mean of a Gaussian process with a squared-exponential kernel of length scale ℓ and noise variance σ², at new points Xs. The training system is solved by Cholesky (calls cholesky_solve).
Losses
std.loss · 11Mean squared error.
Mean absolute error. Calls abs.
Hinge loss for labels ±1 and real-valued scores.
L2 weight penalty. Calls frobenius_sq.
Cross-entropy between a target distribution and the softmax of logits. Calls log_softmax.
Huber loss: quadratic for small errors, linear beyond δ. Calls abs.
Binary cross-entropy for probabilities strictly between 0 and 1.
Log-cosh loss, in a form that never overflows. Calls abs.
Negative log-likelihood with integer class labels: minus the mean of each row's log-probability at its label.
Softmax cross-entropy over rows of logits with integer labels, the way classifiers are trained: a stable log-softmax per row, then nll_labels.
Binary cross-entropy taken from logits: max(z, 0) − z·t + log1p(e^(−|z|)), computed as two smooth branches (z ≥ 0 and z < 0). It never forms the probability, so it stays finite and accurate where sigmoid would round to 0 or 1.
Optimization
std.optim · 21One step of gradient descent: params − lr·grad.
One step of gradient descent with heavy-ball momentum, on the state [params; velocity]: v ← β·v + grad, then params ← params − lr·v.
One step of Adam (Kingma and Ba) on the state [params; m; v] at step t (1, 2, …): m ← β₁m + (1 − β₁)g, v ← β₂v + (1 − β₂)g², then params ← params − lr·m̂/(√v̂ + ε) with the bias corrections m̂ = m/(1 − β₁ᵗ), v̂ = v/(1 − β₂ᵗ).
Gradient clipping by norm: the gradient scaled by min(1, max_norm/‖g‖), computed as max_norm/max(‖g‖, max_norm) so a zero gradient stays zero.
The gradient of logistic regression's mean binary cross-entropy in the weights: Xᵀ(σ(Xw) − y)/n. Written out; a test checks it against NOVA's reverse mode applied to bce_with_logits.
One training step of logistic regression with Adam (β₁ = 0.9, β₂ = 0.999, ε = 10⁻⁸): the gradient from logistic_grad, then adam_step at the step's (t, lr). The body that logistic_fit_adam scans.
Logistic regression trained inside the graph: a Scan of logistic_adam_step over a learning-rate schedule, one step per entry of lr, from zero weights. Returns the weights after the last step. Every step is verified like any other entry, so the trained model is reproducible to the bit on every backend.
One Adam step (β₁ = 0.9, β₂ = 0.999, ε = 10⁻⁸) for any model, given its gradient df(w, X, y): a template over df. With df = logistic_grad it is logistic_adam_step.
Training for any model with Adam, from zero weights, one step per entry of the learning-rate schedule lr: a Scan of adam_descent_step. A template over the model's gradient df(w, X, y). With df = logistic_grad it is logistic_fit_adam, bit for bit.
Logistic regression's loss: the mean binary cross-entropy of the logits Xw against y, through bce_with_logits. Bind its gradient as @grad[f=std.optim.logistic_loss,wrt=w] and minimize_adam trains on the loss alone; NOVA derives the gradient by reverse mode.
One step of gradient descent for any model, given its gradient df(w, X, y): w − η·df(w, X, y). A template over df; the body minimize_gd scans.
Plain gradient descent for any model, from zero weights, one step per entry of the learning-rate schedule lr: a Scan of gd_step. A template over the model's gradient df(w, X, y); bound to @grad of a loss, NOVA derives the gradient by reverse mode.
The standard form of the constraints A·x ≤ b, x ≥ 0: the matrix [A | I], so that A·x + s = b with slacks s ≥ 0. Feasibility and the objective cᵀx carry over both ways between x and (x, s). The other conversions are done before it: a ≥ row is multiplied by −1, an equality becomes two ≤ rows, a free variable is x⁺ − x⁻, and minimizing cᵀx is maximizing −cᵀx.
The slacks s = b − A·x of the constraints A·x ≤ b at a point x: x satisfies them exactly when every slack is non-negative.
Whether the simplex method is still pivoting: status 2, as 1 or 0. It becomes 1 at an optimum and 0 when the problem is unbounded. The condition simplex_max loops on.
One pivot of the fraction-free simplex method on an integer tableau, by Bland's rule: the entering column is the first with a negative reduced cost; the leaving row has the smallest ratio rhs/column over positive entries, compared by cross-multiplication, ties to the smallest basic variable. Every row but the pivot row becomes (p·row − T[i, k]·row r)/D, an exact integer division, and D becomes the pivot p. With no entering column the status becomes 1 (optimal); with no leaving row, 0 (unbounded). The body simplex_max runs.
Maximize cᵀx subject to A·x ≤ b and x ≥ 0, for integer A, b ≥ 0 and c, by the fraction-free simplex method with Bland's rule: a While over simplex_step on the integer tableau [A | I | b; −c | 0 | 0]. Every entry stays an integer, so every decision is exact. status is 1 at an optimum and 0 when the objective is unbounded. The optimum is z_num/z_den in lowest terms; x and the duals y are x_num/den and y_num/den, and bᵀy = cᵀx by strong duality. The reference is the ordinary simplex method on Fractions.
Weak duality for max cᵀx, A·x ≤ b, x ≥ 0 and its dual min bᵀy, Aᵀy ≥ c, y ≥ 0: whether x and y are feasible, and the three numbers cᵀx ≤ yᵀAx ≤ bᵀy, which feasibility guarantees. Feasible x and y with cᵀx = bᵀy are both optimal, a certificate for each.
The Lagrange condition for minimizing ‖x − c‖² subject to one linear constraint g·x = h (g ≠ 0): the minimizer x* = c − ((g·c − h)/‖g‖²)·g, the multiplier λ with ∇f(x*) = λ·∇(g·x) (this sign convention), and the residuals of stationarity, 2(x* − c) − λg, and of feasibility, g·x* − h, both 0. The condition is necessary, not sufficient, in general; here the problem is convex, so x* is the global minimizer. It is not the KKT condition for inequalities.
Minimizing f(x) = A·x² + B·x + C over a closed interval [lo, hi]: whether f is convex there (A ≥ 0, which makes the problem a convex optimization problem, the interval being convex), as 1 or 0; a minimizer, the vertex −B/(2A) clipped to the interval when A > 0, otherwise the better endpoint (the first, lo, on a tie); and the minimum value. Comparing two feasible points, or one Jensen instance, decides nothing in general; the global answer here comes from the closed form.
An optimization problem over a finite list of candidates with their objective values and a feasibility mask: whether any candidate is feasible; the minimum over the feasible set, the first feasible minimizer, and all the minimizers (an optimum may be attained more than once); and the maximum and the first maximizer. On a finite set these are its infimum and supremum. Conclusions hold for the listed set only.
Functions
std.func · 15Function composition, g ∘ f: x ↦ g(f(x)), for any two functions from a vector to a vector of the same length. A template: bind f and g with an instance id, std.func.compose[f=…,g=…].
One row of map_rows: f(x), ignoring the carry. The body map_rows scans; a template over f.
f applied to every row of a matrix: a Scan over the rows whose body, map_rows_step, ignores its carry. A template over f, verified through f = log_softmax, where mapping row by row matters.
One classical Runge–Kutta step for y′ = f(y): y + (h/6)(k₁ + 2k₂ + 2k₃ + k₄) with k₁ = f(y), k₂ = f(y + (h/2)k₁), k₃ = f(y + (h/2)k₂), k₄ = f(y + h·k₃). The body rk4 scans; a template over the vector field f.
Integrate y′ = f(y) by classical Runge–Kutta from y₀, one step per entry of h (the step sizes): a Scan of rk4_step, returning the final state. A template over the vector field f, verified through f = silu; a test integrates y′ = −y and checks e^(−t) to the method's fourth order.
∫ₐᵇ f(t) dt by n-point Gauss–Legendre quadrature, n the length of points: the rule's nodes moved from [−1, 1] to [a, b], (b − a)/2 · Σ wᵢ·f(tᵢ). Exact for polynomials of degree up to 2n − 1. A template over the integrand f, verified through f = silu; a test integrates eᵗ and cos t to 10⁻¹⁵.
One bisection step for a root of f in each bracket [lo, hi]: halve it at the midpoint and keep the half where f changes sign. The body bisect loops on; it takes the loop's tolerance and does not use it. A template over f.
Whether any bisection bracket is still wider than tol, as 1 or 0. The condition bisect loops on.
A root of f in each bracket [lo, hi], where f(lo) and f(hi) differ in sign: bisection until every bracket is at most tol wide, then the midpoint. A While with two carries, lo and hi. A template over f, verified through f = silu; a test finds π/2 and 3π/2 as roots of cos.
One Newton step for f(x) = y, elementwise: x − (f(x) − y)/f′(x), with the derivative given as the function df. The body newton loops on; it takes the loop's tolerance and does not use it. A template over f and df.
Whether any residual |f(x) − y| is still above tol, as 1 or 0. The condition newton loops on. A template over f.
Solve f(x) = y elementwise by Newton's method from x₀, given f and its derivative df, until every residual |f(x) − y| is at most tol. A While over newton_step. A template over f and df, verified through f = softplus and df = sigmoid, which inverts softplus; a test takes √2 as the root of x² = 2.
One step of fixed-point (Picard) iteration: x ← g(x), elementwise. The body fixed_point loops on; it takes the loop's tolerance and does not use it. A template over g.
Whether some |g(x) − x| is still above tol, as 1 or 0. The condition fixed_point loops on. A template over g.
A fixed point x = g(x), elementwise, by Picard iteration from x₀ until every |g(x) − x| is at most tol. For a contraction with constant q < 1 the iteration converges to the unique fixed point, and the error is then at most q·tol/(1 − q). A While over fixed_point_step; a template over g, verified through g = sigmoid, a contraction with q = 1/4.
Algebraic structures
std.algebra · 31The group axioms of a finite Cayley table T (T[a, b] = a·b on the elements 0 … n − 1), each checked over the whole table, as 1 or 0: closure (every entry is an element), associativity over all n³ triples, a two-sided identity, and a two-sided inverse for every element. Also the identity e, the first that works (0 when there is none). Associativity checked on some triples only would not be a proof.
Whether a finite Cayley table is a group, as 1 or 0: all four axioms of group_axioms hold.
The inverse of every element of a finite group, a⁻¹ with a·a⁻¹ = a⁻¹·a = e, read from the table (0 where none exists).
Whether a finite Cayley table is an abelian group, as 1 or 0: a group in which a·b = b·a for every pair, checked over the whole table. A few commuting pairs, or commuting generators not shown to generate, are not enough.
One step of computing every element's powers at once: pw(g) ← pw(g)·g, so after k steps from e it is gᵏ; an element whose power first returns to e at this step k gets order k. The body element_orders scans.
The order of every element of a finite group: the least k ≥ 1 with gᵏ = e, found by checking every smaller power. A Scan of power_step over k = 1 … n; in a group every order is at most n and divides n (0 would mean no power returned to e, which a group rules out).
Whether a finite group has an element of order d, as 1 or 0, and the first one (0 when there is none). Cauchy's theorem says one exists for every prime p dividing |G|; for a composite divisor d there may be none (Z₂ × Z₂ has no element of order 4).
Whether a subset H of a finite group (a 0/1 mask) is a subgroup, as 1 or 0: it contains the identity, and it is closed under products and inverses, each checked over all its elements. Closed under products alone suffices in a finite group, but all three are checked.
The left cosets gH of a subgroup H of a finite group: each element g is labelled by the smallest element of gH, so two elements share a label exactly when they lie in the same coset; and the index [G : H], the number of cosets. Lagrange: the cosets partition G and each has |H| elements, so |G| = [G : H]·|H|.
The right cosets Hg of a subgroup H of a finite group, labelled by their smallest element, and their number, which equals the index [G : H].
Whether a subset H of a finite group is a normal subgroup, as 1 or 0: a subgroup with gH = Hg for every g, which is equivalent to gHg⁻¹ = H. The trivial subgroup and the whole group are always normal.
The quotient group G/H by a subgroup H: its elements are the cosets, labelled by their smallest element, and the product of the cosets of g and h is the coset of g·h, given as a table indexed by elements. Also whether H is normal and whether that product is well defined, the same for every choice of representatives. If H is not normal, representatives can give different cosets, and there is no quotient group. The number of cosets is the order of G/H.
The center Z(G) of a finite group as a 0/1 mask: the elements that commute with every element, each checked against the whole group. It is a normal subgroup; it is all of G exactly when G is abelian, and z ∈ Z(G) exactly when z's conjugacy class is {z}.
The conjugacy classes of a finite group: each x is labelled by the smallest element of its class {g·x·g⁻¹ : g ∈ G}, every g enumerated; and the number of classes. Two classes are equal or disjoint, and together they cover G. A class is not a coset.
Whether a map f from a finite group G to a finite group K (f[a] the image of a) is a homomorphism, as 1 or 0: f(a·b) = f(a)·f(b) for every pair. A homomorphism need not be injective.
The kernel of a homomorphism f : G → K, the full preimage of K's identity, as a 0/1 mask; its image in K as a 0/1 mask; and whether f is injective, which holds exactly when the kernel is the identity alone. The kernel is a normal subgroup of G, and the nonempty fibres of f are its cosets.
The first isomorphism theorem on a finite example, as 1 or 0: f : G → K is a homomorphism, the induced map gH ↦ f(g) on the cosets of H = ker f gives the same value for every representative, and it is a bijection onto the image, so G/ker f ≅ im f. Also |G/ker f| and |im f|. The image need not be all of K.
The axioms of a finite group action, A[g, x] = g·x for a group with Cayley table T acting on the points 0 … k − 1, each checked over the whole table, as 1 or 0: every g·x is a point; e·x = x for every x; and (gh)·x = g·(h·x) for every g, h and x. A valid action need not be faithful, free or transitive.
The orbits G·x = {g·x : g ∈ G} of a finite group action, every g enumerated: each point is labelled by the smallest point of its orbit, so two points share a label exactly when some g sends one to the other; and the number of orbits. The orbits partition the points. One generator's powers, or a single g·x, are not an orbit.
The stabilizer Stab(x) = {g : g·x = x} of a point under a finite group action, every g checked, as a 0/1 mask over G. It is a subgroup of G. It is not the orbit, and not the kernel of the action (the elements that fix every point).
The orbit-stabilizer theorem on a finite action, for the point x: |G·x|, |Stab(x)|, and whether |G| = |G·x|·|Stab(x)|, as 1 or 0. It holds for every action, faithful or not: g ↦ g·x maps G onto the orbit, and the fibre over y = g₀·x is the coset g₀·Stab(x).
The axioms of a finite ring with 1, given by its addition table Ad and multiplication table Mu, each checked over every pair or triple, as 1 or 0: addition is an abelian group; multiplication is closed and associative; it distributes over addition on both sides, a(b + c) = ab + ac and (a + b)c = ac + bc; there is a multiplicative identity 1; and 1 ≠ 0. Also the zero and the one. Multiplication need not commute.
Whether two finite tables form a ring with 1 ≠ 0, as 1 or 0: every axiom of ring_axioms holds.
Three properties of a finite ring with 1, each checked over every pair: whether it is a commutative ring (a ring with ab = ba for all a, b), as 1 or 0; its zero divisors, the nonzero a with ab = 0 or ba = 0 for some nonzero b, as a 0/1 mask; and its units, the a with a two-sided inverse, ab = ba = 1, as a 0/1 mask.
Whether a finite ring is an integral domain, as 1 or 0: a commutative ring with 1 ≠ 0 and no zero divisors, ab ≠ 0 for all nonzero a and b, checked over every pair. Every finite integral domain is a field (multiplication by a nonzero a is injective, so onto), but that is a theorem, not part of the definition.
Whether a finite ring is a field, as 1 or 0: a commutative ring with 1 ≠ 0 in which every nonzero element has a two-sided multiplicative inverse, checked for every nonzero element. Division is defined only by nonzero elements. The order of a finite field is a prime power, not necessarily a prime: there is a field with 4 elements, and Z/4 is not one.
Whether a subset I of a finite ring (a 0/1 mask) is a two-sided ideal, as 1 or 0: the tables form a ring; I contains 0, is closed under addition and additive inverses; and it absorbs multiplication on both sides, r·x ∈ I and x·r ∈ I for every r in the ring and x in I. Left and right absorption are checked separately, over every pair.
The quotient ring R/I by a two-sided ideal I: the classes a + I, labelled by their smallest element, with [a] + [b] = [a + b] and [a]·[b] = [ab], given as two tables indexed by elements; whether I is an ideal; whether it is proper (I ≠ R, so that 1 ≠ 0 in R/I); whether both operations are well defined, the same for every choice of representatives; and the number of classes.
The sum of two polynomials over a finite ring, coefficient by coefficient with the ring's addition table: (p + q)ᵢ = pᵢ + qᵢ. The coefficients are elements of the ring, as int64 labels, both lists the same length (pad the shorter with the ring's zero).
One pass of polynomial multiplication over a finite ring: add the term p_i·q, shifted i places, into the accumulated coefficients r, with the ring's own tables. The body ring_poly_mul scans.
The product of two polynomials over a finite commutative ring, by finite convolution with the ring's own tables: (pq)_k = Σ_{i+j=k} p_i·q_j, the sum taken with the addition table. A Scan of ring_poly_step over the coefficients of p. With zero divisors the degree of a product can fall below the sum of the degrees (over Z/4, (2x + 1)(2x + 1) = 1), so the degree formula is not used. R[x] is not a finite ring: when 1 ≠ 0 the powers 1, x, x², … are all distinct.
Finite topology
std.topology · 21The axioms of a topology on a finite set, given as the list of its open sets τ (an m × n 0/1 matrix), as 1 or 0: the empty set and the whole set are open, and the union and the intersection of any two open sets are open. For a finite family, pairs suffice for every union and every finite intersection; the empty union is ∅ and the empty intersection is X. Each test runs over all pairs, by set sizes: the smallest open set containing U and V must have |U ∪ V| points, and the largest inside both |U ∩ V|.
Whether a finite family of subsets is a topology, as 1 or 0: all four axioms of topology_axioms hold.
Whether a subset A (a 0/1 mask) is open in a finite topology τ, as 1 or 0: A is one of the listed open sets.
Whether a subset A is closed in a finite topology, as 1 or 0: its complement X \ A is open. Open and closed are not opposites: ∅ and X are both, and a set may be neither.
The interior of a subset A in a finite topology, as a 0/1 mask: the union of all the open sets contained in A, the largest open subset of A. It depends on the topology; no metric is used.
The closure of a subset A in a finite topology, as a 0/1 mask: the intersection of all the closed sets containing A, the smallest closed superset of A, computed as X \ int(X \ A).
The boundary of a subset A in a finite topology, as a 0/1 mask: cl A \ int A. A and its complement have the same boundary; ∅ and X have none.
Whether a subset N is a neighbourhood of the point x in a finite topology, as 1 or 0: some open U has x ∈ U ⊆ N, that is, x lies in the interior of N. A neighbourhood need not be open.
One row of the basis check: for the basis element B_i and every B_j, each point of B_i ∩ B_j lies in some basis element inside B_i ∩ B_j. The body is_basis scans.
Whether a finite family B of subsets is a basis for some topology, as 1 or 0: its members cover X, and for any two members, each point of their intersection lies in a member inside the intersection. A Scan of basis_step over the members. A basis is not a subbasis: the subbasis condition asks only that the members cover.
Whether every member of a finite family B is an open set of the topology τ, as 1 or 0.
Whether a finite family B is a basis of the given topology τ, as 1 or 0: B is a basis, its members are open, and every open set of τ is a union of members.
The subspace topology on a subset Y: τ_Y = {U ∩ Y : U ∈ τ}, one row for each open set of τ (rows may repeat; the family is the set of rows). A relatively open set need not be open in X.
Whether a map f from a finite space (X, τ_X) to (Y, τ_Y) is continuous, as 1 or 0: the preimage f⁻¹(V) of every open V of Y is open in X. It is the preimage that must be open; images of open sets need not be.
Whether a map f between finite spaces is a homeomorphism, as 1 or 0: a bijection that is continuous and whose inverse is continuous, which for a bijection means the image of every open set is open. A homeomorphism preserves the topology only: not distances, angles or smoothness.
Whether a finite topological space is Hausdorff, as 1 or 0: every two distinct points x ≠ y lie in disjoint open sets U ∋ x and V ∋ y, every pair checked. One failing pair disproves it. A finite Hausdorff space is discrete, which does not carry over to infinite spaces; the empty space and a single point are Hausdorff.
Whether a finite topological space is connected, as 1 or 0: no open set other than ∅ and X has an open complement, every open set checked. A disconnected space has a witness, an open set that is also closed; a connected one needs every candidate excluded. This is topological connectedness, not graph connectivity.
The connected components of a finite topological space, each point labelled by the smallest point of its component; and how many there are. τ must be a topology, which is_topology decides. A point's component is the union of every connected subset that contains it, connected in the subspace topology. In a finite space it is found through the smallest open set U_x of each point: x and y lie in one component when a chain of points joins them, each two comparable, one in the other's smallest open set. These are components of the topology, not of a graph; and every component of a finite space is both open and closed, which fails in general (in ℚ the components are points, which are not open).
Whether a finite family C (one set per row) is an open cover of the subset K in the topology τ: whether every member is open, and whether the members together contain K, each as 1 or 0. A finite space is compact, since its topology itself is finite, so every open cover has a finite subcover; one cover checked does not by itself prove compactness.
Whether the members of a cover C selected by sel (a 0/1 mask over the members, so a subcover takes members of the original cover only) still contain K, as 1 or 0.
Whether a subset U of Y is open in the quotient topology of a surjection q : X → Y, as 1 or 0: its preimage q⁻¹(U) is open in X. Only saturated open sets of X are preimages, so taking images of open sets would in general be wrong.
Sets, relations and logic
std.sets · 25Three parts of a finite relation R from A to B (a 0/1 matrix): its domain Dom R = {a : a R b for some b} as a mask over A; the image R[C] = {b : a R b for some a ∈ C} of a subset C of A, as a mask over B; and the inverse relation R⁻¹ from B to A, the transpose. Ordered pairs keep their direction.
Four properties of a relation R on a finite set (an n × n 0/1 matrix), each checked over every element, pair or triple, as 1 or 0: reflexive (x R x for all x), symmetric (x R y ⇒ y R x), transitive (x R y and y R z ⇒ x R z, checked as R∘R ⊆ R), and antisymmetric (x R y and y R x ⇒ x = y). One counterexample disproves the property it violates.
Whether a relation on a finite set is an equivalence relation (reflexive, symmetric and transitive), as 1 or 0, and its classes: each a labelled by the smallest element of [a] = {x : a R x}, which is the canonical projection onto the quotient set X/R; and the number of classes. Two classes are equal or disjoint and together cover X. The labels mean classes only when the relation is an equivalence.
The graph G_f = {(a, f(a))} of a function f from A = 0 … n − 1 to B = 0 … k − 1 (B given by a carrier vector of length k, only its length read), as an n × k relation: (u, v) ∈ G_f exactly when v = f(u).
Whether a finite relation R from A to B is a (total) function, as 1 or 0: every a relates to exactly one b. The codomain B need not be the range.
For a function f : A → B on finite sets, each as 1 or 0: injective (every fibre f⁻¹(b) has at most one element), surjective (every b is hit, the range equals the codomain), bijective (both); and the range f[A] as a mask over B. On finite sets an injection A → B shows |A| ≤ |B|, a surjection |A| ≥ |B|, a bijection |A| = |B|; equal sizes do not make a given f a bijection.
The inverse g : B → A of a function f on finite sets, by swapping the pairs of its graph, and whether f is a bijection, as 1 or 0. Only for a bijection is g a function with g(f(a)) = a and f(g(b)) = b; otherwise the swapped table is not an inverse, and g is the first preimage, or 0 where there is none.
The pigeonhole principle on a function f : A → B between finite sets: whether two elements share an image, as 1 or 0, and the first such pair a₁ < a₂ (0, 0 when there is none); and the largest load, the size of the biggest fibre. When |A| > |B| a collision must exist, and the largest load is at least ⌈|A|/|B|⌉; |A| ≤ |B| does not make f injective.
Union A ∪ B, intersection A ∩ B, difference A \ B and complement U \ A of subsets of one finite universe U, as 0/1 masks. The complement is always taken relative to the stated universe.
Whether A ⊆ B for subsets of one finite universe, as 1 or 0: every element of A is in B. Also whether A is a proper subset (A ⊆ B, A ≠ B) and whether A = B (sets with the same elements are equal).
Whether x ∈ A for a subset A of a finite universe, as 1 or 0.
One term of inclusion-exclusion: for the index set I given by the bits of c, (−1)^(|I|+1)·|∩_{i ∈ I} S_i|, added to the running total (the empty I adds nothing). The body inclusion_exclusion runs.
Whether the index-set counter c is still below 2^s, as 1 or 0. The condition inclusion_exclusion loops on.
Inclusion-exclusion for a finite indexed family S_1 … S_s of subsets of 0 … m − 1 (one row each): the size of the union counted directly, and the alternating sum Σ over all 2^s − 1 nonempty index sets I of (−1)^(|I|+1)|∩_{i ∈ I} S_i|, a While over ie_step. The two agree. Repeated sets are counted by index; stopping after singles and pairs gives only a Bonferroni bound for s ≥ 3.
The truth values of the classical connectives, elementwise on truth values 0 and 1: ¬P, P ∧ Q, P ∨ Q, P → Q (false only when P is true and Q false) and P ↔ Q.
Quantifiers over a finite domain U, for a predicate given by its truth values P(x): ∀x P(x) and ∃x P(x), each as 1 or 0; whether a counterexample to ∀x P(x) exists, and the first one (0 when there is none). One counterexample refutes the universal statement; failing to find one proves it only because the domain is finite and was checked completely. ¬∀x P(x) ⇔ ∃x ¬P(x).
The axioms of a metric on a finite set, given as its full distance table D, each checked over every pair or triple, as 1 or 0: d(x, y) ≥ 0; d(x, y) = 0 exactly when x = y; d(x, y) = d(y, x); and the triangle inequality d(x, z) ≤ d(x, y) + d(y, z), checked for every y at once as d ≤ the min-plus square of d. A finite metric space is complete: below its smallest positive distance a Cauchy sequence is eventually constant.
The smallest positive distance δ in a finite distance table (0 for a single point). Every ε < δ forces d(x_m, x_n) < ε to mean x_m = x_n, so a Cauchy sequence in a finite metric space is eventually constant and converges: finite metric spaces are complete. A few sampled sequences would not prove it.
Correctness of a finite computational model (S, Init, Step, Halt), possibly nondeterministic, against a postcondition Post: the states reachable from Init (a halting state is an end, its outgoing steps cut); the stuck states, reachable, not halting, with no successor, which are not halts; partial correctness, every reachable halting state satisfies Post; termination, no execution runs forever (no reachable cycle) or gets stuck; and total correctness, both. Every execution is covered, as nondeterminism requires: one successful path proves nothing.
Whether a decider's answers D(x) (0 or 1, for every input x of a finite input set) decide the problem with yes-instances Y, as 1 or 0: D(x) = 1 exactly when x ∈ Y; and the first input where they differ (0 when none). A finite table settles that finite input set only; decidability of an infinite problem needs an algorithm that halts on every input.
Whether a total map f from a finite input set of problem A to one of problem B is a many-one reduction A ≤ₘ B, as 1 or 0: x ∈ A exactly when f(x) ∈ B, both directions checked for every x (yes-instances alone are not enough); and the first x where it fails. If A ≤ₘ B and B is decidable, computing f and then B's decider decides A; the converse does not hold. A finite table proves the reduction on that finite domain only.
One step of following every point's forward orbit under a self-map f of a finite set at once: pw(x) ← f(pw(x)), so after k steps from x it is fᵏ(x); a point that first returns to itself at step k gets period k. The body orbit_periods scans.
Fixed and periodic points of a self-map f of a finite set {0, …, n − 1}: the minimal period of each x, the least p ≥ 1 with fᵖ(x) = x (0 when x is not periodic: its orbit enters a cycle without returning to x), checked for every smaller power; and the fixed points, period 1. A Scan of orbit_step over n steps, enough on a finite set: every orbit repeats within n steps. Entering a cycle does not make the starting point periodic.
One factor of a product: acc·v. The body counting_rules scans.
The two counting principles for finite choices given the number of options in each part: the sum rule, Σ counts, for choosing one option from mutually exclusive categories; and the product rule, Π counts, for a sequence of stages whose option counts do not depend on earlier choices. Overlapping categories must be corrected by inclusion-exclusion first.