mixle-discrete 0.7.0

Discrete and algebraic numerical methods: integer/binary least squares, finite fields, and the combinatorial-numerics pillar of the mixle ecosystem.

mixle-discrete

Discrete and algebraic numerical methods: integer/binary least squares, finite fields, and the combinatorial-numerics pillar of the mixle ecosystem.

Where mixle-pde handles continuous inverse problems (PDEs, ODEs, gradient-based fitting), mixle-discrete handles the discrete and exact ones: recovering integer parameters from noisy linear measurements, and computing exactly over finite fields. It is standalone (numpy only) and composes with the rest of the ecosystem but does not depend on it.

Install

pip install -e .            # from a checkout
pip install -e ".[test]"    # with the test extras

Quickstart

import numpy as np
from mixle_discrete import integer_least_squares, GF

# Recover an integer vector from noisy linear measurements — an exact closest-vector solve.
rng = np.random.default_rng(0)
A = rng.standard_normal((8, 4))                 # 8 noisy measurements of 4 integer unknowns
x_true = np.array([3, -1, 4, -2])
b = A @ x_true + 0.05 * rng.standard_normal(8)
integer_least_squares(A, b)                     # -> array([ 3, -1,  4, -2]); exact despite the noise

# Exact linear algebra over a finite field — no floating point, no round-off.
F = GF(7)
F.solve([[2, 1], [1, 3]], [1, 0])               # -> array([2, 4]); solves M x = y in GF(7)

What's here

Integer and binary least squares

min ||A x - b||^2 where x is constrained to the integers, to {0, 1}, or to a box. This is the closest-vector problem, and it is an inverse problem with a discrete solution space (GNSS carrier-phase ambiguity resolution, MIMO detection, lattice decoding). The stack is lattice reduction plus search:

• lll_reduce — LLL lattice basis reduction (size reduction + the Lovasz condition).
• babai_nearest_plane — Babai's nearest-plane approximate CVP.
• integer_least_squares — the exact optimum over the integers by Schnorr-Euchner sphere decoding with LLL preprocessing.
• box_integer_least_squares / boolean_least_squares — the box- and {0,1}-constrained variants.
• enumerate_integer_least_squares — the solution set, not just the argmin: every integer point within a residual radius, the max_solutions best, box-constrained or free, sorted by residual.
• integer_least_squares_posterior — the inverse-problem view: exact posterior weights over the enumerated candidates under Gaussian noise (lo=0, hi=1 gives the boolean posterior over all 2^n assignments).

Finite fields

Exact computation over GF(p) and GF(2^m): field arithmetic, linear algebra, and polynomials.

• GF(p) / GF(2, m) — field construction and elementwise arithmetic.
• linear algebra over a field — RREF, rank, solve, nullspace, inverse, determinant, plus the complete solution set of any linear system: solution_set (particular + nullspace basis) and enumerate_solutions (all q^nullity of them, materialized).
• polynomials over a field — add, multiply, divmod, gcd.
• large binary fields — GF(2, m, use_tables=False) drops the O(2^m) log tables and runs tableless (carryless multiply + Fermat inversion) so the crypto sizes work, e.g. GF(2, 128) on the GHASH polynomial.

Hashing, sketching, and membership

The hash families that streaming structures need, and structures built on them.

• MultiplyShift, PolynomialHash, TabulationHash — 2-universal / k-independent / 3-independent hash families, plus ghash / gcm_ghash, the GHASH polynomial MAC over GF(2^128) (the crypto hash on the field).
• CountMinSketch, CountSketch, HyperLogLog — sublinear-space stream summaries: one-sided and unbiased frequency estimation and distinct-count.
• BloomFilter, CountingBloomFilter, CuckooFilter — approximate membership (set inclusion without storing the set); no false negatives, a tunable false-positive rate, and deletion (counting / cuckoo).

Coding theory, lattice cryptography, and SAT

• ReedSolomon, BCH — error-correcting codes over GF(2^m) (Berlekamp-Massey, Chien search, Forney), correcting up to t = (n-k)/2 errors; list_decode returns every codeword within a chosen Hamming radius, including past t where unique decoding must fail.
• lwe_keygen / lwe_encrypt / lwe_decrypt and the ring_lwe_* variants — Regev LWE and Ring-LWE public-key encryption, with all secret and error sampling drawn from the constant-time discrete Gaussian below. These are side-channel-conscious reference implementations for study, not production cryptography: pure Python cannot guarantee hardware constant-time, so use a vetted library (liboqs and friends) for real keys.
• belief_propagation, survey_propagation — the statistical-physics message-passing solvers for SAT, with bp_decimation / sp_decimation; survey propagation works nearer the random-3-SAT threshold where BP fails.
• enumerate_sat — the exact counterpart for small n: every satisfying assignment, so the row count is the model count and the column means are the exact marginals BP estimates.

The discrete Gaussian has two samplers: sample_discrete_gaussian_1d (rejection, fast, not constant-time, for the statistical CVP/SVP routines) and ConstantTimeDiscreteGaussian / sample_discrete_gaussian_cdt (a fixed-point CDT with a single full-table compare — no early exit, no secret-dependent branch or memory access — for the crypto path). The constant-time one removes the algorithmic side channels only; see the caveat above.

Statistical solvers

The exact solvers above are the ground truth; these are the statistical route to the same problems, useful when the instance is too large for exact search. Every discrete optimization min E(x) becomes inference in a Gibbs distribution p(x) ∝ exp(-E(x)/T), and the optimum is the mode.

• sample_discrete_gaussian_1d, klein_sample — the discrete Gaussian over a lattice and the Klein/GPV sampler (a randomized Babai walk over the LLL-reduced basis), the primitive underneath lattice cryptography.
• cvp_sample / svp_sample — statistical closest- and shortest-vector solving by sampling.
• simulated_annealing — a generic Metropolis/Gibbs engine, with anneal_cvp, anneal_qubo (Ising), and anneal_ilp covering integer least squares, QUBO, and integer programming through one energy interface.

These grade against the exact solvers: cvp_sample and anneal_cvp match integer_least_squares on the vast majority of instances, anneal_qubo matches brute force over 2^n, and the sampler's distribution passes a chi-square goodness-of-fit against the discrete-Gaussian pmf.

Fast logsumexp: tropical convolution and Zech logarithms

logsumexp is the addition of the log-semiring, and its T→0 limit is the max-plus (tropical) semiring. Two number-/group-theoretic structures make it fast in the cases where it can be:

• tropical — max-plus convolution via the fast Legendre-Fenchel transform (the "tropical Fourier transform"), which diagonalizes sup-convolution into pointwise addition. fast_max_plus_convolution is O(n) on concave data (vs the O(n²) max_plus_convolution reference), top_k_max_plus_convolution keeps the k best decompositions per output index (the k-best-paths view) where the plain convolution keeps one winner, and lse_convolution is the temperature-smoothed logsumexp version that converges to it as T→0 (gap ≤ T·log n).
• BinaryField.log_add / zech_log — Zech logarithms, the exact finite-field logsumexp: log(gⁱ + gʲ) = i + Z(j−i) turns addition in the log representation into a single table gather. Verified against direct field addition over all of GF(2⁸) and sampled at GF(2¹⁶). (A log-table technique, so small-to-moderate fields only; large binary fields use tableless carryless multiply instead.)

Verification

Everything is checked against an exact reference: brute force over a bounded search space for the least-squares solvers, closed-form invariants for lattice reduction, A @ inv(A) == I for field linear algebra, sympy for the algebraic parts, the exact solvers themselves (plus chi-square goodness-of-fit) for the statistical ones, and the naive O(n²) convolution / direct field addition for the tropical and Zech routines.

Tests

pytest                              # the full suite (-n auto via pyproject)
pytest tests/integer_ls_test.py -q  # one file

Maintainers & contributors

Maintained by Grant Boquet (@gmboquet · [e-mail]).

Contributions, issues, and discussion are welcome — open a PR or an issue.

License

MIT — see LICENSE.