---
title: "algorithm-subset-convolution — Mova code model"
description: "Mova code model of algorithms/src/subset_convolution/mod.rs: components with their labels, obernants and the model text."
url: "https://groupants.elamur.ai/free/en/mova/algorithms/src/subset_convolution/mod.rs.groupant/"
---
Elamur: [Mova](https://md.mova.elamur.ai/free/en/) · [Dictionary](https://md.dictionary.elamur.ai/free/en/) · [Research](https://md.research.elamur.ai/free/en/) · **Groupants**

This page as HTML: <https://groupants.elamur.ai/free/en/mova/algorithms/src/subset_convolution/mod.rs.groupant/>

# algorithm-subset-convolution

The groupant beside algorithms/src/subset_convolution/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

- **kind:** groupant
- **status:** partial source derived instance
- **source:** [`algorithms/src/subset_convolution/mod.rs`](https://github.com/ElamurAI/mova-free/blob/main/algorithms/src/subset_convolution/mod.rs)
- **source SHA-256:** `00210af867219bff…`
- **repository folder:** [`algorithms/src/subset_convolution/mod.rs.groupant`](https://github.com/ElamurAI/mova-free/tree/main/algorithms/src/subset_convolution/mod.rs.groupant)
- **repository commit:** `855da7bd4a7b`

> **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](#forward) |
| **ast** | partial | `syntax.json` |
| **cost** | conditional | [Cost](#cost) |
| **descriptant** | present | [descriptant](#descriptant) |
| **invariant** | partial | [Invariant](#invariant) |
| **tests** | bounded executed | [evidence](#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](#behavior-complement) |
| `reverse_reconstruction` | reverse_reconstruction | partial relational specification | [reverse_reconstruction](#reverse-reconstruction) |
| `rank_filter` | rank_filter | partial relational specification | [rank_filter](#rank-filter) |
| `zeta_inversion` | zeta_inversion | partial relational specification | [zeta_inversion](#zeta-inversion) |
| `arithmetic_bound` | arithmetic_bound | partial relational specification | [arithmetic_bound](#arithmetic-bound) |
| `validation_order` | validation_order | partial relational specification | [validation_order](#validation-order) |

## Model text


### descriptant

#### subset_convolution

Prospective model saved before implementation in ../prospective.md (relative from source directory). Original standard-library code. This epoch adds explicit supported domains and independent finite checks. See model.md for typed excluded-output and preimage relations. Partial syntax omits macro expansion and semantic resolution. No executable approximation profile is attached; useful cheaper metrics and evidence remain unsupported. No timing gain is claimed.

### model

## subset_convolution mod.rs

### Forward

Ranked zeta transforms F[k,S]=sum_{T subset S,|T|=k}a[T]; H[k,S]=sum_i F[i,S]G[k-i,S]; Mobius invert then return H[|S|,S]. Equal power2 lengths<=4096; modulus998244353. O(d²2^d) time O(d2^d) memory. Bjorklund et al., Fourier meets Mobius, STOC 2007.

### Invariant

After Mobius inversion, evaluating rank=popcount(S) removes overlapping pairs because |A|+|B|=|A union B| iff A and B are disjoint.

### Cost

Ranked zeta transforms F[k,S]=sum_{T subset S,|T|=k}a[T]; H[k,S]=sum_i F[i,S]G[k-i,S]; Mobius invert then return H[|S|,S]. Equal power2 lengths<=4096; modulus998244353. O(d²2^d) time O(d2^d) memory. Bjorklund et al., Fourier meets Mobius, STOC 2007.

### behavior_complement

At validated a,b, any candidate y with y[S] unequal to sum_{T subset S}a[T]b[S xor T] modulo p, or residue>=p, is excluded. Shape-invalid input paired with Ok is excluded.

### reverse_reconstruction

For observed y retain pairs satisfying every subset convolution equation. Zero a with any b maps to zero; for fixed a with a[0] nonzero the triangular equations uniquely recover b. Raw residue representatives remain ambiguous.

### rank_filter

After Mobius inversion, evaluating rank=popcount(S) removes overlapping pairs because |A|+|B|=|A union B| iff A and B are disjoint.

### zeta_inversion

Each bit update adds the lower subset; reverse Mobius subtracts it. In the field these transforms are inverse linear maps over ranked arrays.

### arithmetic_bound

Inputs reduce modulo998244353; each product<(p-1)^2<2^60 and each accumulated reduced sum<2p. No checked overflow is needed within the validated size domain.

### validation_order

Either length>4096 returns TooLarge before equal/power2 shape checks. d<=12. Three ranked tables use O(d2^d) elements; allocations use std policy.

### evidence

#### Evidence — 2026-10-30

Two tests per algorithm cover independent finite oracles and boundaries. Receipts: $MOVA_DATA/runs/octopus-wave25-algebra-2026-10-30. Paired debug/release logs, compiled-mutant rejection and restored rerun logs are retained there. Exact positive counts and final verification are reported in the integration receipt. Syntax projections are generated twice and compared. Source bindings are SHA-256; typed models are conditional specifications, not proofs. Allocator failure is not injected.

### prospective

#### Prospective model — 2026-10-30

Ranked zeta transforms F[k,S]=sum_{T subset S,|T|=k}a[T]; H[k,S]=sum_i F[i,S]G[k-i,S]; Mobius invert then return H[|S|,S]. Equal power2 lengths<=4096; modulus998244353. O(d²2^d) time O(d2^d) memory. Bjorklund et al., Fourier meets Mobius, STOC 2007.

Validation precedes arithmetic. Modular inputs normalize before products; products fit u64. Resource caps are policy refusals, distinct from algebraic absence. Allocator exhaustion is not recoverable in this bounded std implementation. No callbacks. Independent small oracles, repeated debug/release and compiled mutants are planned. No executable approximation profile is supported: no validated useful cheaper metric yet. Expected asymptotic improvement is a hypothesis, not measured speed.