Metadata-Version: 2.4
Name: mixle-discrete
Version: 0.7.0
Summary: Discrete and algebraic numerical methods: integer/binary least squares, finite fields, and the combinatorial-numerics pillar of the mixle ecosystem.
Author-email: Grant Boquet <grant.boquet@gmail.com>
License-Expression: MIT
Project-URL: Homepage, https://github.com/gmboquet/mixle-discrete
Project-URL: Repository, https://github.com/gmboquet/mixle-discrete
Keywords: integer least squares,lattice reduction,finite fields,coding theory,numerical methods
Classifier: Development Status :: 3 - Alpha
Classifier: Intended Audience :: Science/Research
Classifier: Operating System :: OS Independent
Classifier: Programming Language :: Python :: 3
Classifier: Programming Language :: Python :: 3.10
Classifier: Programming Language :: Python :: 3.11
Classifier: Programming Language :: Python :: 3.12
Classifier: Topic :: Scientific/Engineering :: Mathematics
Requires-Python: >=3.10
Description-Content-Type: text/markdown
License-File: LICENSE
Requires-Dist: numpy>=1.24
Provides-Extra: test
Requires-Dist: pytest>=8; extra == "test"
Requires-Dist: pytest-xdist; extra == "test"
Requires-Dist: sympy; extra == "test"
Provides-Extra: lint
Requires-Dist: ruff==0.15.17; extra == "lint"
Provides-Extra: gmp
Requires-Dist: gmpy2; extra == "gmp"
Provides-Extra: docs
Requires-Dist: sphinx>=7; extra == "docs"
Requires-Dist: furo; extra == "docs"
Requires-Dist: tomli>=2; python_version < "3.11" and extra == "docs"
Dynamic: license-file

# mixle-discrete

![license](https://img.shields.io/badge/license-MIT-green)
![python](https://img.shields.io/badge/python-3.10%2B-blue)

Discrete and algebraic numerical methods: integer/binary least squares, finite fields, and the
combinatorial-numerics pillar of the [mixle](https://github.com/gmboquet/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

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

## Quickstart

```python
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

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

## Maintainers & contributors

Maintained by **Grant Boquet** ([@gmboquet](https://github.com/gmboquet) ·
grant.boquet@gmail.com).

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

## License

MIT — see [LICENSE](https://github.com/gmboquet/mixle-discrete/blob/main/LICENSE).
