Elamur Groupantsalgorithm-linear-recurrence
The groupant beside algorithms/src/linear_recurrence/mod.rs in the Mova repository: what the code computes, what it never does, how to go back from its outputs, its invariants, cost and checks.
Facts
Implementation material. A Mova code model describes this code at one source revision: partial models, finite checks and their stated scope. It is not a reviewed general exposition, and its labels are shown as written, never raised.
Components
| component | label | where |
|---|---|---|
| approximant | partial | Forward |
| ast | partial | syntax.json |
| cost | conditional | Cost |
| descriptant | present | descriptant |
| invariant | partial | Invariant |
| tests | bounded executed | evidence |
Obernants
The typed relations around the forward model: the behaviour complement (what the code never does), the reverse reconstruction (every input compatible with an output) and specialised views.
| id | type | label | where |
|---|---|---|---|
behavior_complement | behavior_complement | partial relational specification | behavior_complement |
reverse_reconstruction | reverse_reconstruction | partial relational specification | reverse_reconstruction |
quotient_power | quotient_power | partial relational specification | quotient_power |
coefficient_orientation | coefficient_orientation | partial relational specification | coefficient_orientation |
linearity | linearity | partial relational specification | linearity |
normalization | normalization | partial relational specification | normalization |
overflow_envelope | overflow_envelope | partial relational specification | overflow_envelope |
validation_partition | validation_partition | partial relational specification | validation_partition |
Model text
descriptant
Modeling epoch 2026-10-30
Original exact implementation/test harness. Partial syntax, forward relation, invariant, cost and typed views share this source identity. The combiner retains their assumptions and finite evidence; it does not generate semantic proofs. Macro bodies are opaque in the syntax projection. No useful approximate profile is selected, so no executable surrogate or percentage-error claim is introduced.
Prospective recurrence model: polynomial reduction trades O(n*k) sequential advancement for O(k^2 log(n+1)) work. No recurrence runtime speedup was measured. Prospective NTT model: three transforms should lose to schoolbook at16 and overtake by512 or2048; comparisons below test this hypothesis on supplied equal operand lengths only.
| Operand length | NTT median ns/call | Schoolbook median ns/call | NTT range | Schoolbook range |
|---|---|---|---|---|
| 16 | 7006 | 602 | 5513..7901 | 467..748 |
| 128 | 24345 | 23031 | 19533..25922 | 10687..23220 |
| 512 | 54594 | 176265 | 53174..63443 | 170290..195138 |
| 2048 | 242709 | 2661481 | 242386..270817 | 2651024..2699745 |
Five batches alternate timing order; each supplied size checks output equality before its batches, and the benchmark normalizes schoolbook operands once. Timings include allocations, result materialization and destruction. Hardware contention and small samples limit generalization; no universal crossover, training speed or full-course claim. The measurements support the prospective prediction: schoolbook wins at16 and128; NTT wins at512 and2048. Thus the observed crossover is bracketed by128 and512 only for these operands and this run. No warm-up phase was used; the reported spread includes startup/cache effects.
Sources: recurrence reduction follows classical polynomial algebra (von zur Gathen and Gerhard, Modern Computer Algebra, third edition,2013); finite-field FFT follows Pollard, Mathematics of Computation25 (1971),365-374. The code and fixtures are original.
model
Source-bound mathematical views
Forward
For k seeds, a[t]=sum_{j=0}^{k-1}c[j]a[t-1-j] modulo nonzero m. Return a[n], using coefficients of x^n modulo x^k-sum c[j]x^(k-1-j) as weights on a[0..k]. Validation precedes the initial-prefix shortcut.
Invariant
Canonical residues and input immutability; test observations require the declared domains. Arithmetic/resource boundaries are explicit below. Structural checks are not semantic proofs.
Cost
Initial-prefix queries take O(1) after length validation. Otherwise at most2*floor(log2(n))+1 polynomial combines, each O(k^2), plus O(k) final dot product; O(k^2 log(n+1)) word time and O(k) peak words. u128 remainder cost is hardware-dependent. k<=4096 is a policy cap, not a promise of fast maximum-order queries.
behavior_complement
In the universe of validated calls and candidate residues, absent behavior consists of residues unequal to the declared recurrence term; invalid calls paired with Ok are absent under validation precedence. This is an exact specification target, with only finite Rust correspondence evidence.
Domain: this source's declared API or finite fixture schedule. Observation: returned values/errors and assertion outcomes; allocation environment remains external. Assumptions: integer arithmetic and classical algebra premises above. Status: partial mathematical specification with bounded evidence in evidence.md; no universal Rust proof or approximate substitution.
reverse_reconstruction
For fixed n and modulus m, the preimage of y contains all admissible seed/coefficient pairs whose nth term is y modulo m. Preserve every congruent seed and coefficient representative. At n=0 only the first seed is constrained; for zero seeds all coefficient vectors qualify for y=0. No unique recovery is implied.
Domain: this source's declared API or finite fixture schedule. Observation: returned values/errors and assertion outcomes; allocation environment remains external. Assumptions: integer arithmetic and classical algebra premises above. Status: partial mathematical specification with bounded evidence in evidence.md; no universal Rust proof or approximate substitution.
quotient_power
In the quotient ring (Z/mZ)[x]/(x^k-sum_j c[j]x^(k-1-j)), exponentiation maintains result*power^remaining = x^original_n. Descending reduction substitutes each high degree without changing its congruence class. Composite moduli need no inverse.
Domain: this source's declared API or finite fixture schedule. Observation: returned values/errors and assertion outcomes; allocation environment remains external. Assumptions: integer arithmetic and classical algebra premises above. Status: partial mathematical specification with bounded evidence in evidence.md; no universal Rust proof or approximate substitution.
coefficient_orientation
Fix k and coefficients indexed by lag: c[0] multiplies a[t-1], c[k-1] multiplies a[t-k]. For n=k, the output equals the reversed seed dot product. Reversing this policy produces a different recurrence; finite iterative oracle distinguishes them.
Domain: this source's declared API or finite fixture schedule. Observation: returned values/errors and assertion outcomes; allocation environment remains external. Assumptions: integer arithmetic and classical algebra premises above. Status: partial mathematical specification with bounded evidence in evidence.md; no universal Rust proof or approximate substitution.
linearity
For fixed coefficients,n,m, nth_term(s+t)=nth_term(s)+nth_term(t) modulo m. Scalar multiplication obeys the same relation. This constrains seeds without claiming injectivity; finite tests use two seed vectors and their sum.
Domain: this source's declared API or finite fixture schedule. Observation: returned values/errors and assertion outcomes; allocation environment remains external. Assumptions: integer arithmetic and classical algebra premises above. Status: partial mathematical specification with bounded evidence in evidence.md; no universal Rust proof or approximate substitution.
normalization
Replacing any input element by a congruent representable u64 leaves the result unchanged. Modulus1 gives zero for every valid call. Normalization does not relax empty/dimension/cap validation.
Domain: this source's declared API or finite fixture schedule. Observation: returned values/errors and assertion outcomes; allocation environment remains external. Assumptions: integer arithmetic and classical algebra premises above. Status: partial mathematical specification with bounded evidence in evidence.md; no universal Rust proof or approximate substitution.
overflow_envelope
Each modular accumulation has acc,a,b<m. Thus acc+ab <= (m-1)+(m-1)^2=m(m-1)<2^128 for every nonzero u64 m. k<=4096 ensures 2k-1 and indices fit usize on supported Rust platforms. Full-width fixtures exercise near-maximum products.
Domain: this source's declared API or finite fixture schedule. Observation: returned values/errors and assertion outcomes; allocation environment remains external. Assumptions: integer arithmetic and classical algebra premises above. Status: partial mathematical specification with bounded evidence in evidence.md; no universal Rust proof or approximate substitution.
validation_partition
First failing predicate partitions calls: modulus0; empty coefficient vector; differing lengths; k>4096; then allocation refusal. Initial prefix n<k bypasses allocations only after validation. Allocation refusal is represented but not force-injected.
Domain: this source's declared API or finite fixture schedule. Observation: returned values/errors and assertion outcomes; allocation environment remains external. Assumptions: integer arithmetic and classical algebra premises above. Status: partial mathematical specification with bounded evidence in evidence.md; no universal Rust proof or approximate substitution.
evidence
Finite evidence, 2026-10-30
Eight new tests pass, four per algorithm. With temporary local module exports, the existing library plus these tests passes306 unit tests twice debug and twice release with identical sorted test identities/results. Strict algorithms Clippy/all-targets and narrow rustfmt pass. Each implementation and each test source has a compiled assertion-failing mutation and byte-exact restoration; names and raw output are in external logs. No allocation refusal was injected, no maximal NTT array was allocated, and no global proof follows.
External evidence under $MOVA_DATA/runs/octopus-wave10-numeric-2026-10-30; SHA-256 bindings:
- prospective.md: 98f42d52c02a986739b71d7e7fcd33bca123e7b3801c0af7c63712d982f6965e
- normalized.txt: f7d0728613a44a1396116d3443a289382d5a32af5749ddacea032f59a5c21692
- debug1.log: 9bcc67b5002fb501a7e1e0324822331180cc71674b93b6a56d2328e5d3ed93f5
- debug2.log: b290a5766bbec05a0496c3ccd8a5e827cf508abd498974f8ff4b1775bd584450
- release1.log: bee75b34a3e2d1a62307f5ac9838e90361c2d5102cc81d1b68726ce7521c8597
- release2.log: b47c313f67bea615fa649d502dc1a1eaa5348869f6576884c4f37b0de8e13063
- clippy.log: c4befea3c686d896b0b23d975cf532278bf6609c76e42421548f41d7e151aa7b
- timing.rs: e5bec634506beb46db5cb2996a9c22ef09ffbef9a27ef67ec190121c97ce74c0
- timing.log: 2e9c541523a0ed1679c0e5beb8cb98d936b1bf7f3681de39e2a232d37d95805f
- validation.log: 148d3f6e6a3427aac131893b057a8323fa1de3ea67afeaeb2e5eaa5a9e6c79f7
- mutant-linear_recurrence-mod.rs.log: 1a41cdbb6ec6cc0c267973e5fcc96a2f181435d33b4eeccd28a9409da30894f4
- restored-linear_recurrence-mod.rs.log: 8fc9e98dbe4e83d28606849cb72189417850d011e2c7382c303194716a904f69
validation
Validation, 2026-10-30
Compiled control: Set polynomial identity coefficient to0 instead of1. Named assertion failure: linear_recurrence::tests::finite_iterative_oracle. The original bytes were restored and this named test passed again. The eight new tests and298 existing library tests pass twice per debug/release profile, with identical306 sorted identities. No root API join is claimed here; the root integrator owns exports and composition tests.
Four source projections were generated twice, byte-identically. Repeated groupants reports are identical; changed accepts the four new registered sources under an external registry scaffold. These check source/artifact declarations only.
- groupants1.json SHA-256: 748ffa97af5b5a0ce4d9ec5ad660d9ad194fa1de4206f34b5d19ecd8b2c4308b
- groupants2.json SHA-256: 748ffa97af5b5a0ce4d9ec5ad660d9ad194fa1de4206f34b5d19ecd8b2c4308b
- changed.json SHA-256: 7df3f3facfd9a1a76658abac9663a4994faa8b2813813502c817df26fd679176
- structure.log SHA-256: cb5a49c3e9a8d1cfa1f7e19110072ec8a864b4a2feb69941e329009daf325a7a
Limits: maximal NTT storage and allocation refusal are not executed; arbitrary off-fixture behavior remains unverified. The recurrence order cap4096 is a resource policy. Exact algorithms have no surrogate error budget.
This page in Markdown → https://md.groupants.elamur.ai/free/en/mova/algorithms/src/linear_recurrence/mod.rs.groupant/