# Prime-Gated Maximal-Length Binary Reservoir

- ID: 688
- Canonical URL: https://synthcore.org/idea/688/prime-gated-maximal-length-binary-reservoir
- API JSON: https://synthcore.org/api/idea/688.json
- API Markdown: https://synthcore.org/api/idea/688.md
- Verification status: unverified
- Source: [arXiv:2607.10453](https://arxiv.org/abs/2607.10453)
- Category: architecture
- Solves: memory, scalability, sample-efficiency
- ML areas: rnn, ssm, reservoir
- Math tags: dynamical-systems, combinatorics, algebra, logic
- Ratings: usefulness 5/10; difficulty 5/10; novelty 6/10

## Idea description

Replace a learned recurrent transition with a sparse binary reservoir compiled from prime-count gates. Three permanently active control vertices implement copy and XNOR transitions, allowing the signal state to realize an affine feedback register over \(\mathbb F_2\) with period \(2^m-1\) using only \(O(m)\) edges and bounded in-degree. Train only an input projection and readout, or use straight-through estimators if end-to-end adaptation is required.

## Mathematical statement

A Pulse Graph updates each Boolean vertex by prime activation: \(x_{t+1}(v)=\mathbf 1\{k_t(v)\text{ is prime}\}\), where \(k_t(v)=\sum_{u\in N^-(v)}x_t(u)\) is the number of active incoming neighbors. With \(q\) permanently active inputs and variable inputs \(x,y\), the gate \(F_q(x,y)=\mathbf 1\{q+x+y\text{ is prime}\}\) gives logic gates; in particular, \(q=3\) yields XNOR. Three mutually connected control vertices initialized to one remain active because each sees two active inputs. For a signal register \(s_0,\ldots,s_{m-1}\), an untapped transition is \(x_{t+1}(s_i)=x_t(s_{i-1})\), while a tapped transition with three controls, \(s_{i-1}\), and \(s_{m-1}\) has count \(3+x_t(s_{i-1})+x_t(s_{m-1})\), hence computes XNOR: \(x_{t+1}(s_i)=1+x_t(s_{i-1})+x_t(s_{m-1})\pmod 2\). Choosing tap bits \(a_i\in\{0,1\}\) from a primitive feedback polynomial gives an affine transformation \(x_{t+1}=Ax_t+b\) over \(\mathbb F_2\) with nonzero-state period \(2^m-1\). The construction uses \(a_{m-1}=0\), so it requires no self-loop, has maximum in-degree five, and uses \(O(m)\) edges.

## Key formulas

- $$x_{t+1}(v)=\mathbf 1\left\{\sum_{u\in N^-(v)}x_t(u)\text{ is prime}\right\},\qquad x_t(v)\in\{0,1\}.$$
- $$F_q(x,y)=\begin{cases}1,&q+x+y\text{ is prime},\\0,&q+x+y\text{ is not prime},\end{cases}\qquad F_3(x,y)=\operatorname{XNOR}(x,y).$$
- $$x_{t+1}(s_i)=\begin{cases}x_t(s_{i-1}),&a_i=0,\\1+x_t(s_{i-1})+x_t(s_{m-1})\pmod 2,&a_i=1,\end{cases}\qquad 1\le i<m.$$
- $$x_{t+1}=Ax_t+b\pmod 2,\qquad \operatorname{period}(x_t)=2^m-1\ \text{for every nonzero register state when the feedback polynomial is primitive}.$$

## Implementation notes

Integrate this as a fixed recurrent state-space feature layer before a readout, rather than replacing all hidden layers. Construct an m-bit binary state, three binary control units fixed to one, and choose a primitive degree-m feedback polynomial over \(\mathbb F_2\); its nonzero tap coefficients are the \(a_i\). At each time step, encode the input through a learned projection \(u_t=\mathbf 1\{W_{in}z_t>0\}\), then update the register with the copy/XNOR rules. Pseudocode: initialize a nonzero state \(x_0\); for each t, read the selected tapped bits, compute the affine feedback bit as their XOR plus the constant term modulo two, shift the register, apply XNOR at tapped stages and copy at untapped stages, then optionally XOR or concatenate an input bit. Feed \([x_t,z_t]\) or a leaky average of recent states to a linear ridge readout or small MLP. Keep the recurrent graph frozen during the first experiment. For a literal Pulse Graph implementation, count active inputs as integers and use a lookup table for primality; for ordinary software, directly use the equivalent XOR/XNOR circuit. The mathematical quantities are the primitive polynomial, tap set, and guaranteed period. Estimate useful memory empirically by delayed-input reconstruction, lagged autocorrelation, and rank of the collected state matrix. Start with m=32 and m=128 on adding, delayed-copy, and permuted sequential-MNIST tasks. Compare against a same-width random Boolean reservoir, an ESN, and a GRU at matched parameter count and recurrent operation count. Success means higher delayed-copy accuracy or longer reconstructible delays at equal compute, together with nonrepeating state trajectories over the predicted period scale. Failure is no improvement over random Boolean connectivity or rapid collapse of input information despite the long nominal cycle.

## Disclaimer

AI-generated research hypothesis, automatically tested. Not peer-reviewed.