SirRoboGarage/BNNBot_garage/analysis/domain_math.md

# Discrete Mathematics Lens on BNNBot

**Context**: 690-bit binary input (Gray-coded, 10-frame temporal window), online learning, reward =
miss distance from circular wave feedback. No gradient descent. Binary weights/activations.

---

## Structural Properties of Our Binary Space (Read First)

Before any framework, pin down what structure the 690-bit input *already has*. These properties
constrain which mathematical tools apply and where untapped leverage exists.

### Gray Coding = Embedded Metric Structure

Gray code is an isometry between adjacent integers and Hamming-1 neighbors. For our encoding:
- `x_t → x_t + δ` in physics space maps to `Gray(x_t) → Gray(x_t + δ)` with Hamming distance ≈ 1
  per bit-field (vs up to log2(n) for binary encoding)
- **Consequence**: physically similar states are Hamming-close states. The input manifold has
  Lipschitz-like smoothness in Hamming metric. Any distance-based hash, nearest-neighbor lookup, or
  locality-sensitive scheme exploits this for free.
- **Not exploiting this**: our Hebbian residual table uses only 24 cells (8 heading sectors × 3
  distance bands). The cells discretize the continuous physics space, but ignore the Hamming metric
  structure entirely. A hash-based retrieval over the full 690-bit vector would be more precise.

### Temporal Redundancy (10 frames × 69 bits)

Consecutive frames differ by ~1 enemy move. Gray-coded, that means Hamming distance between
frame i and frame i+1 ≈ 3-6 bits out of 69. The 690-bit vector has:
- **Strong temporal autocorrelation**: I(f_t; f_{t-1}) ≈ high (most bits identical tick-to-tick)
- **True information content < 690 bits**: an MDL estimate is ~69 bits (one frame) for near-constant
  velocity movement plus ~6-8 bits for heading+speed change. The 10× redundancy is useful for noise
  robustness but the *irreducible information* is small.
- **Implication**: a model that learns which bits *change* between frames carries more signal than one
  treating all 690 bits uniformly. Temporal XOR (frame[t] ⊕ frame[t-1]) compresses the motion into
  ~6-10 bits per step.

### Sparsity (10/24 residual cells active, observed)

The data shows only ~10 out of 24 residual cells activate meaningfully. This suggests the function
mapping input → correction is **sparse in some basis**. The true prediction correction depends on a
small number of input features. This is compressed-sensing territory: the signal is k-sparse in some
unknown basis with k << 690.

### Linearity Obstacle in GF(2)

XOR layers are linear over GF(2). XOR + popcount + threshold is the minimal non-linear binary
neuron. Any network restricted to XOR-only layers computes an affine function over GF(2), which
cannot represent the non-linear corrections needed. The algebraic normal form of any Boolean function
requires at least degree-2 monomials (AND of two variables) to be non-affine. Our residual correction
IS non-linear in the input (it depends on distance × heading interaction), so linear-over-GF(2)
architectures are fundamentally insufficient.

---

## Framework 1: Boolean Function Learning (PAC / Fourier Analysis)

### Mathematical Framework

Every Boolean function f: {0,1}^n → {-1,+1} has a unique representation as a multilinear polynomial
(the Walsh-Fourier expansion):

    f(x) = Σ_{S ⊆ [n]} f̂(S) · χ_S(x)

where χ_S(x) = Π_{i∈S} (1 - 2x_i) is a parity function over subset S, and f̂(S) are real Fourier
coefficients. The sum of squared coefficients is 1: Σ f̂(S)² = 1 (Parseval).

**PAC learnability classes (Valiant 1984)**:
- k-CNF and k-DNF (bounded clause width): efficiently PAC-learnable in poly time
- Monotone conjunctions: learnable
- General DNF: open problem; likely hard (hardness results by Klivans & Servedio, 2004)
- Decision trees of depth d: learnable from Fourier spectrum
- **Halfspaces (linear threshold functions)**: poly-time learnable (perceptron)
- **Majorities, parities of few bits**: learnable; sparse Fourier spectrum

Key result for us: a function is efficiently PAC-learnable iff it has a **sparse low-degree Fourier
spectrum** (KM algorithm, Kushilevitz & Mansour 1993). The SPRIGHT algorithm recovers K-sparse WHT
in O(K n log n) samples.

### Mapping to 690-bit → Predicted Position

Our output is not Boolean but real-valued (predicted x,y correction). We can still ask: what is the
structure of the Fourier spectrum of, say, the indicator function "will this input lead to a hit?"
Given that 10/24 sectors activate and the function appears to depend on a small number of features,
hypothesis: **the hit-prediction function has a sparse, low-degree Fourier spectrum**.

Key consequence: if the function is concentrated on degree-≤2 Fourier coefficients, it is
approximable by a sum of pairwise interactions — which maps directly to a Boltzmann machine or
second-order Hebbian network.

### Update Rule Sketch

Run a sparse Walsh-Hadamard transform incrementally:
1. Maintain counters c_S for each "candidate" subset S (start with S = singletons + pairs)
2. On each wave feedback: c_S += hit? ? +1 : -1 for each S where χ_S(x) = +1
3. Top-K coefficients define a linear predictor over parity features
4. Prediction: ŷ = Σ_S∈top-K ĉ_S · χ_S(x) (cast to position offset)

This is **online Fourier learning**. The KM algorithm suggests O(n/ε²) samples for ε-approximation
of sparse functions.

### Computational Cost

Tracking singletons: O(n) = O(690) counters, trivial. Tracking pairs: O(n²) = O(476K) — borderline.
Tracking triples: O(n³) — infeasible. Practical: limit to degree-1 (linear) + degree-2 (pairwise)
terms and test if this captures the signal. Expected O(1000) battle samples to recover top-10
coefficients if the function has 10-sparse Fourier spectrum.

### Untapped Structure

Gray coding means adjacent input values differ by Hamming-1. In Fourier space, a Gray-smooth function
has Fourier weight concentrated at **low-frequency (small S) coefficients**. This is the Grey-code
smoothness guarantee translating to Fourier sparsity at low degree. We should be able to identify
the top-K coefficients with far fewer samples than general Boolean functions because smoothness
bounds the spectrum.

---

## Framework 2: Combinatorial Bandits on the Binary Hypercube

### Mathematical Framework

A multi-armed bandit selects actions from an action set A. In the combinatorial bandit setting
(Chen et al. 2013, Kveton et al. 2015), each action is a subset of "base arms" (bits), with reward
that decomposes over the selected set. Regret bound: O(√(KT log K)) for CombLinUCB where K = number
of active bits and T = rounds.

For binary weight vectors, the action is a weight configuration w ∈ {0,1}^N, reward R(w) = hit
rate. This is a bandit over an exponential action space — we need structure to make it tractable.

**Thompson Sampling (binary/Bernoulli)**: each weight w_i has Beta(α_i, β_i) posterior on its
contribution to reward. Sample θ_i ~ Beta(α_i, β_i), set w_i = 1 if θ_i > 0.5, observe reward.
Update: α_i += hit, β_i += miss. This is the simplest online binary learning rule that is
principled under uncertainty.

### Mapping to Aiming

Reframe: each "arm" is not a single weight but a **candidate aiming strategy** — a specific
correction (Δx, Δy) to add to linear extrapolation. The bandit chooses which correction to apply
given input context x. Reward = did the bullet hit?

This is a **contextual bandit** (the reward depends on x). For contextual bandits with binary
context, the LinUCB / LinTS extensions apply.

**Practical sketch**: Discretize corrections into B bins (e.g., 50 bins per axis = 2500 joint
corrections). For each bin b, track Beta(α_b, β_b). Given input x, compute a context-conditioned
expected reward E[R | x, b] via Thompson sampling on the posterior. This gives a Bayesian bandit
over correction bins — exactly what the Hebbian residual table approximates, but with proper
uncertainty quantification and exploration.

### Update Rule Sketch

    # Per wave-hit event:
    b* = current correction bin (from predicted position)
    if hit:
        α[b*] += 1
    else:
        # reward is shaped by miss distance
        α[b*] += exp(-miss_distance / σ)
        β[b*] += 1 - exp(-miss_distance / σ)

    # Prediction:
    sample θ_b ~ Beta(α_b, β_b) for each b
    b_chosen = argmax_{b} f(x, b, θ_b)  # context-weighted Thompson sampling

### Computational Cost and Convergence

Beta updates: O(1) per arm per round. Sample from Beta: O(1). With B correction bins, total per-tick
cost: O(B). Convergence: Thompson sampling achieves O(√(BT log B)) regret (Agrawal & Goyal 2013),
meaning after T=1000 battle ticks, expected suboptimality ≈ O(√(B · 1000 · log B)). For B=100,
this is ~O(300) — significant but manageable for a battle that repeats.

**Key advantage over current table**: Thompson sampling maintains per-bin uncertainty and
auto-balances exploration/exploitation. The current Hebbian table uses fixed lr=0.2 with no
exploration bonus — it may get stuck in local optima in bins with few observations.

---

## Framework 3: Binary Optimization Without Gradients

### Simulated Annealing on Weight Vectors

SA on {-1,+1}^N: at temperature T, flip weight w_i with acceptance probability min(1, exp(-ΔE/T)).
Energy E = cumulative miss distance over recent battles. Schedule: T(t) = T_0 / log(1+t).

**Convergence theory**: SA converges to global optimum in probability if T→0 sufficiently slowly.
In practice, for binary problems with N=690 weights, O(N² log N) iterations needed for reliable
convergence — infeasible within a 1000-tick battle.

**Practical use**: SA is viable for the *small* residual table (24 cells × 2 floats = 48 params).
Current lr=0.2 Hebbian update is essentially SA with constant temperature. Adding a cooling schedule
would improve final-state quality at the cost of slower convergence.

**Key formula**: for binary weights, ΔE per bit flip is the reward delta from that flip. This is
exactly weight perturbation (Method 6 in learning_methods_report.md). SA IS weight perturbation
with a temperature schedule.

### Tabu Search

Maintain a tabu list of recently visited weight configurations. At each step, flip the bit that
most improves reward while not being on the tabu list. The tabu list prevents cycling.

For the 24-cell residual table, tabu search is practical. For the full BNN weight matrix (N >> 24),
the tabu list overhead grows prohibitively. Recent work (2023, ScienceDirect) shows tabu search
exploiting local optimality in binary problems achieves better solutions than SA when the objective
has many local optima — which is plausible for a non-stationary opponent.

**Convergence**: guaranteed if neighborhood is strongly connected (all {-1,+1}^N reachable) and
tabu tenure is bounded. In practice, tabu tenure τ ≈ sqrt(N) gives empirically good results.

### Convergence Comparison (rough, for context)

| Method | Iterations for N-bit problem | Notes |
|--------|------------------------------|-------|
| Brute force | 2^N | infeasible for N>30 |
| SA | O(N² log N) | with correct schedule |
| Tabu search | O(N^1.5) to O(N²) | empirically |
| Bandit (Thompson) | O(N log N) / O(√T) regret | if decomposable |
| Fourier / KM | O(N/ε²) | if function is sparse |
| Hebbian (current) | O(1/lr) per cell | greedy, may not converge |

For N=24 (current table): all methods viable within 1000 ticks.
For N=690 (full weight vector): only bandit and Fourier methods are feasible.

---

## Framework 4: Locality-Sensitive Hashing on Gray-Coded Inputs

### Mathematical Framework

LSH for Hamming distance: a random hash function h(x) = x[i] (select random bit i) collides two
binary vectors x, y with probability 1 - d_H(x,y)/n, where d_H is Hamming distance and n=690. This
is Hamming-LSH — trivially computable, requires no training.

For our Gray-coded inputs: two consecutive enemy positions differ by d_H ≈ 3-6 bits. The LSH
collision probability for such pairs is (690-5)/690 ≈ 99.3%. This means random bit-sampling is an
excellent locality-preserving hash for our input.

### Content-Addressable Memory (CAM) System

**Architecture**: store (input_hash, correction) pairs. On new input, retrieve the k nearest stored
inputs by Hamming distance, average their corrections.

This is the **k-nearest-neighbor predictor in Hamming space**, implemented via LSH buckets for
efficiency.

**Why this is powerful for us**: Gray coding guarantees that physically similar states (same heading,
similar distance) have Hamming-close encodings. A CAM retrieval over Hamming distance directly
recovers "similar situations had correction Δ_i", which is exactly the non-parametric Hebbian
correction we want but without the coarse 24-cell discretization.

### Implementation Sketch

    # Storage (bounded buffer, ~200 entries max)
    memory = []  # list of (x_690bit, correction_xy)

    # Learning (on wave hit):
    memory.append((current_input, observed_correction))
    if len(memory) > MAX: memory.pop(0)  # FIFO or evict worst

    # Prediction:
    # Find k nearest inputs by Hamming distance (XOR+popcount, hardware-accelerated)
    dists = [popcount(x XOR stored_x) for stored_x in memory]
    k_nearest = nsmallest(k, zip(dists, memory))
    correction = weighted_average([c for (_, c) in k_nearest],
                                  weights=[1/(d+1) for (d, _) in k_nearest])

**Cost**: O(|memory| × 690/64) per prediction (popcount on 64-bit words, ~11 ops per entry).
For 200 stored entries: ~2200 bitops per prediction — within 1ms budget.

**Convergence**: after M examples, k-NN with Hamming metric converges to the Bayes-optimal
predictor for any Lipschitz-continuous function in Hamming metric. Our Gray-coded input IS
Hamming-Lipschitz. This is non-parametric with O(M^{-d/(d+2)}) convergence rate for effective
dimension d. If d is small (our data suggests ~3-5 physical degrees of freedom map to the
correction), convergence is fast.

### What We're Not Exploiting

The current 24-cell table partitions input space by two hand-chosen features (heading sector,
distance band). LSH with Hamming distance exploits all 690 bits equally weighted. **The Gray
structure means we could use ANY two bits that differ between nearby states as an LSH hash for
those states.** The system naturally finds the relevant bits by collision frequency.

---

## Framework 5: Information-Theoretic Approaches

### Minimum Description Length (MDL) for Model Selection

MDL principle: choose the model M that minimizes L(M) + L(Data|M), where L is description length
in bits.

For our prediction problem, MDL gives a principled way to choose between:
- Linear extrapolation (24 params × 32 bits = 768 bits to describe)
- Hebbian 24-cell table (24 × 64 bits = 1536 bits + cell selection logic)
- k-NN memory (200 × (690+64) bits = ~150KB)
- Full BNN (690 × 128 + 128 × 64 = 97K params × 1 bit = 12KB binary)

MDL predicts: use the simplest model that compresses battle data. If linear extrapolation already
compresses (MAE 8.1 units baseline), the incremental description-length reduction from more complex
models must exceed their description cost. 

**Practical MDL estimate**:
- Linear: already needs 0 extra bits (hardcoded physics)
- Hebbian table: 24 cells, each storing 2 floats. If only 10 cells activate, effective description
  is 10 × 2 × 32 ≈ 640 bits. Very cheap.
- Full BNN: 12KB. This is only justified if it reduces prediction error enough to compress the
  residuals by > 12KB.

**Key insight**: Given that 10/24 Hebbian cells activate, the true model has ~10 degrees of freedom.
Any model with > 10 effectively independent parameters is overfitting to a sparse signal. This
argues strongly against large BNN architectures for this task.

### Mutual Information and the Information Bottleneck

The information bottleneck principle (Tishby & Zaslavsky 2015): an optimal representation Z of
input X for predicting output Y maximizes I(Z; Y) while minimizing I(Z; X) (compression).

For our 690-bit input:
- I(X; Y) = mutual information between input and correct correction ≈ a few bits
  (given that ~97.8% of motion is constant-velocity, the correction signal is low-entropy)
- Optimal bottleneck Z should be ~5-10 bits if the correction depends on ~3-5 physical variables

**Implication**: a 690-bit → 5-bit bottleneck should capture nearly all prediction-relevant
information. More hidden-layer capacity is wasted on input noise. The current Hebbian table with
24 cells (effectively log2(24) ≈ 4.5 bits of index) is close to the information-optimal representation
size.

### Rate-Distortion Lower Bound

For any binary encoding of corrections with rate R bits:
D*(R) ≥ D_max · 2^{-R/H}

where D_max is the baseline distortion and H is the entropy of the correction signal.

If H ≈ 5 bits (3-5 degrees of freedom): to halve prediction error (D = 0.5 D_max) we need R = 5
bits of model capacity. The current 4.5-bit residual table is near the Shannon limit for this task.
Going deeper adds computation without information-theoretic benefit unless we're wrong about H.

---

## Framework 6: Finite Field Arithmetic — GF(2)

### What GF(2) Can and Cannot Compute

A Boolean function f: {0,1}^n → {0,1} has a unique **algebraic normal form (ANF)**:

    f(x) = Σ_{S ⊆ [n]} a_S · Π_{i∈S} x_i   (sum/product mod 2)

- **Degree 1** (a_S = 0 for |S| > 1): affine functions = XOR of input bits + constant
- **Degree 2**: affine + pairwise products (AND of two bits XOR'd together)
- **Maximum degree n**: any Boolean function is representable

**Key result**: any function with full degree n in its ANF is not learnable from a linear (XOR-only)
network. Our required correction function, mapping Gray-coded position to position offset, has
non-trivial degree because distance × heading interactions are necessary for good corrections.

**Algebraic immunity**: A function with algebraic immunity d requires an adversary to know d+1
bits of correlation to predict the output. For cryptographic functions (bent functions), algebraic
immunity is maximized (≈ n/2). For our case, we want the OPPOSITE: low algebraic immunity means
few bits predict the output, which is what we observe.

### Bent Functions and Non-Linearity

A **bent function** is maximally non-linear: equally distant from all affine functions. The
correction from linear extrapolation is a non-affine function of the input, but we want to
characterize *how* non-linear it is to choose the right architecture.

If the correction function has low algebraic degree (2-3), a second-order Hebbian network (tracking
pairwise bit correlations) would suffice. If it has high degree, deeper architectures are needed.

**Hypothesis from data**: since 10/24 coarse cells captures 14-21% MAE reduction, the correction
is primarily a degree-1 function of the coarse features (heading, distance) plus small degree-2
perturbations. Algebraic degree ≤ 2 is a reasonable prior.

### Practical Consequence

XOR + popcount + threshold computes a **linear threshold function over GF(2)** — a halfspace in
{0,1}^n with the XOR inner product. This is equivalent to a single parity-check + threshold. It
is more expressive than pure XOR (which is degree-1 over GF(2)) but less expressive than arbitrary
degree-2 functions. The key non-linearity needed — "distance AND heading interaction" — requires
at minimum one AND gate, which is degree-2 over GF(2).

**Architecture implication**: XOR + popcount is necessary AND nearly sufficient for degree-2
correction functions, because popcount over a selected subset of bits computes a weighted degree-2
interaction. A single hidden layer with XOR + popcount neurons is algebraically adequate for the
signal we observe.

---

## Framework 7: Cellular Automata Rules

### Wolfram's Elementary CA Rule Space

Elementary 1D CA: 256 rules mapping (left, center, right) bits → new center bit. Wolfram's
Class IV (e.g., Rule 110, proven Turing-complete by Cook 2004) produces complex, structured patterns
from simple rules.

### Application to Temporal Pattern Prediction

Our 10-frame temporal window looks like a 1D CA: at each step, the state evolves according to some
rule that depends on neighbors (surrounding bits in the encoding). If enemy motion follows a simple
physical rule, the temporal evolution of the 690-bit vector might be approximated by a CA rule
applied to a small neighborhood of bits.

**Sketch**: identify which 3-7 bits in frame t most predict the change in bit b in frame t+1
(via correlation). Define a local rule: b_{t+1} = f(neighborhood_t). This rule, applied uniformly
across the 69-bit frame encoding, defines a CA-like predictor.

**Convergence and utility**: for the specific physical evolution (constant velocity), the CA rule
would be a simple linear shift in position bits — computable in O(n) time. For non-linear motions
(turns, acceleration), the CA rule would need higher complexity. The key value here is **structural
insight**: if the transition looks like a CA rule, we can predict the next frame without a full
network evaluation.

**Reality check**: CA rules are defined for spatial neighbors; our input is a flat binary vector
with non-spatial structure. The CA framing is more metaphorical than literal here — it suggests
looking for **local update rules** in the binary representation rather than global functions.

---

## Framework 8: Compressed Sensing / Sparse Recovery

### Mathematical Framework

Classical compressed sensing: y = Ax where y ∈ R^m, A ∈ R^{m×n}, x ∈ R^n is k-sparse (at most k
non-zero entries). Recovery guarantee (Candes & Tao 2005): if A satisfies the **restricted isometry
property (RIP)** with δ_{2k} < √2 - 1, then x is recoverable from m = O(k log(n/k)) measurements.

For n=690, k=10 (observed sparsity): m ≈ 10 × log(69) ≈ 43 measurements. We have ~1000 battle ticks
with wave feedback — well above threshold if measurements are well-structured.

### Binary Measurement Matrices

Our network weights ARE the measurement matrix A. A binary weight matrix W ∈ {-1,+1}^{m×690}
satisfies a form of RIP with high probability when entries are iid Rademacher (Baraniuk et al. 2008).
This means a single-hidden-layer BNN with ~43 neurons is mathematically sufficient to recover a
10-sparse correction signal from 690 binary inputs.

### Mapping to Our Problem

Reframe: the "true" correction vector c ∈ R^2 (Δx, Δy) is not sparse, but the function that maps
inputs to corrections is sparse in the **feature basis** — only ~10 features of the 690-bit input
predict the correction. This is compressed sensing in function space.

**Sparse recovery update rule**:
1. Treat each wave-feedback event as a measurement: y_t = c_true + noise
2. Build measurement matrix A from historical inputs x_t (690 bits each)
3. Solve: min ||w||_0 subject to Aw ≈ y (sparse regression)
4. Use LASSO (L1 relaxation) online: w ← w - η · (Aw - y) · sign(w)

The online L1 update is a soft-thresholding step — computable without gradients of the loss if we
treat (Aw - y) as a signal (not a derivative).

### What We're Not Exploiting

Our observation that "only 10/24 residual cells activate" is an empirical signal of sparsity. But
we're not measuring *which 690 bits* drive the prediction — we're only asking which of 24 coarse
cells. Compressed sensing applied at the bit level would:
1. Identify the ~10 input bits most predictive of the correction
2. Build a sparse predictor that ignores the other 680 bits
3. Potentially achieve better prediction with less memory than the current architecture

The LSH approach (Framework 4) implicitly does this via Hamming nearest-neighbors, but an explicit
sparse recovery would be more interpretable and theoretically grounded.

---

## Framework 9: SAT as Learning

### Framing the Learning Problem as Weighted MAX-SAT

Define a clause for each battle observation: "given input x_t, the aiming correction that would have
hit enemy was c_t." Binary weight vector w must satisfy (approximately):

    sign(w · x_t) = sign(c_t_x)   [x-component of correction]
    sign(w · x_t) = sign(c_t_y)   [y-component]

This is a linear feasibility problem over {-1,+1} — equivalent to finding w that satisfies a set
of soft halfspace constraints. Each battle tick adds a new clause.

**Weighted MAX-SAT reformulation**: each tick t has a "clause" (x_t, c_t) with weight w_t = 1.
Find w ∈ {-1,+1}^N that satisfies maximum total clause weight.

### Survey Propagation

SP (Mezard et al. 2002) is a message-passing algorithm for random SAT that operates near the SAT
threshold. It maintains probability distributions ("surveys") over variables and iteratively updates
them. SP solves instances with 10^6 variables in seconds at clause-to-variable ratios near the
phase transition.

**Relevance**: at each battle step, we have a growing SAT instance. SP could run incrementally as
new clauses arrive. Convergence: SP converges in O(n) iterations per update for satisfiable
instances. For our 690-variable problem with ~1000 clauses after a battle, this is in the
well-satisfiable regime (many more solutions than constraints) — SP would converge very fast.

**Practical obstacle**: SP outputs probability distributions, not binary assignments. It requires
a "decimation" step to extract a concrete assignment. The combined SP + decimation + local search
(WalkSAT) is a standard pipeline but adds complexity beyond what our 1ms budget allows for each tick.

### WalkSAT for Online Binary Weight Updates

WalkSAT local search: pick an unsatisfied clause at random, flip a bit that satisfies it (or random
flip with probability p). Convergence to satisfying assignment (if one exists) in O(n·2^{αn}) steps
for random 3-SAT, better for structured problems.

**For our problem**: each unsatisfied clause is a "this prediction was wrong" event. WalkSAT would
flip the weight bit that "fixes" the most errors. This is a greedy local search on {-1,+1}^N.

**Online WalkSAT sketch**:

    # On wave hit (new clause (x_t, c_t) arrives):
    if current_prediction wrong:
        best_flip = argmax_i [improvement in satisfied clauses if w[i] flipped]
        w[best_flip] = -w[best_flip]

Cost per update: O(N × |active_clauses|) — expensive for N=690 and |clauses|=100+. Maintain an
active clause buffer of bounded size to keep cost bounded.

**Convergence**: empirically O(N log N) flips to satisfy random binary clause sets. For N=24 (our
table), this is ~100 flips — achievable within a battle. For N=690, substantially more.

---

## Synthesis: Unexploited Structure Summary

### The Core Mathematical Insight We Are Missing

The 690-bit input has **Gray-coding × temporal autocorrelation × low-dimensional physics** structure
that we currently exploit only via a 24-cell coarse grid. The mathematically precise statement is:

> The function f: {0,1}^{690} → R² (correction) lies in a space of functions with sparse Fourier
> spectrum (few non-zero Walsh coefficients), low algebraic degree (≤2 over GF(2)), and Lipschitz
> continuity in Hamming metric (from Gray coding). This combination makes it efficiently learnable
> by any of: sparse Fourier recovery, degree-2 Hebbian network, or Hamming k-NN.

### Prioritized Opportunities

**Highest impact (small change, large gain)**:

1. **Hamming k-NN over raw bits** (Framework 4): Replace 24-cell table with a bounded memory buffer
   of (input_690bit, correction_xy) pairs. Retrieve k nearest by XOR+popcount. Exploits Gray
   structure, no architecture change needed, O(200 × 11) bitops per prediction. This gives the
   residual table infinite resolution at O(200) memory cost.

2. **Temporal XOR features** (implicit in Framework 1 and 8): Add frame[t] ⊕ frame[t-1] as
   explicit input features (~69 bits of velocity-change signal). These are the "sparse changing
   bits" that carry motion information. Near-zero cost to compute, likely captures the degree-2
   correction interactions.

**Medium impact (architecture changes)**:

3. **Sparse Fourier learning** (Framework 1): Track pairwise bit correlations with corrections. The
   KM algorithm guarantees recovery of the top-K Fourier coefficients with O(n/ε²) samples. For
   n=690, K=10, ε=0.1: needs ~69K samples — more than one battle provides. Feasible across multiple
   battles (inter-battle learning).

4. **Thompson sampling on correction bins** (Framework 2): Replace fixed lr=0.2 Hebbian with
   Beta(α,β) posterior per bin. Principled exploration, uncertainty-aware predictions. O(bins)
   extra memory, same architecture.

**Lower priority (diminishing returns)**:

5. MDL analysis confirms: 10 active degrees of freedom suggest the current architecture is near-
   optimal in capacity. Going deeper adds parameters without proportionate information gain unless
   opponent behavior is demonstrably multi-modal or adversarial.

6. GF(2) algebra analysis confirms: XOR + popcount + threshold (the planned BNN neuron) is the
   minimal architecture for degree-2 functions, and degree-2 is sufficient given the data. No need
   for deeper networks from this angle.

### What Structure We ARE Exploiting

- Gray coding (Hamming smoothness) → implicitly in the 8-sector heading table
- Temporal window (10 frames) → used as input, not architecturally modeled
- Physics sparsity (constant velocity) → linear extrapolation baseline

### What Structure We Are NOT Exploiting

- Hamming distance between full input vectors (nearest-neighbor retrieval)
- Temporal XOR (which bits change per tick = motion signal in compressed form)
- Fourier coefficient sparsity at low degree (sparse linear model over parity features)
- Information-theoretic limit (current table is near Shannon bound for this task)
- Uncertainty quantification (Bayesian correction bins vs fixed learning rate)

---

## Sources

- [A Theory of the Learnable — Valiant 1984 (acolyer.org summary)](https://blog.acolyer.org/2018/01/31/a-theory-of-the-learnable/)
- [On PAC Learning Algorithms for Rich Boolean Function Classes](https://link.springer.com/chapter/10.1007/11750321_42)
- [Analysis of Boolean Functions — O'Donnell (full text, CMU)](https://www.cs.cmu.edu/~odonnell/papers/Analysis-of-Boolean-Functions-by-Ryan-ODonnell.pdf)
- [SPRIGHT: Sparse Walsh-Hadamard Transform](https://arxiv.org/pdf/1508.06336)
- [An Efficient Algorithm for Combinatorial Semi-Bandits (JMLR 2016)](https://jmlr.org/papers/volume17/15-091/15-091.pdf)
- [A Tutorial on Thompson Sampling (Stanford)](http://web.stanford.edu/~bvr/pubs/TS_Tutorial.pdf)
- [Convergence Rate of Simulated Annealing with Noisy Observations](https://arxiv.org/pdf/1703.00329)
- [Tabu Search Exploiting Local Optimality in Binary Optimization (2023)](https://www.sciencedirect.com/science/article/abs/pii/S0377221723000012)
- [Locality Sensitive Hashing Lecture Notes (LUMS)](https://web.lums.edu.pk/~imdad/pdfs/CS5312_Notes/CS5312_Notes-14-LSH.pdf)
- [Hamming Distance Metric Learning](https://norouzi.github.io/research/papers/hdml.pdf)
- [Minimum Description Length — Scholarpedia](http://www.scholarpedia.org/article/Minimum_description_length)
- [Bent function — Wikipedia](https://en.wikipedia.org/wiki/Bent_function)
- [Algebraic Normal Form of a Bent Function](https://eprint.iacr.org/2018/1160.pdf)
- [Compressed Sensing Using Binary Matrices of Nearly Optimal Dimensions](https://arxiv.org/pdf/1808.03001)
- [Survey Propagation: An Algorithm for Satisfiability (Wiley 2002)](https://onlinelibrary.wiley.com/doi/pdf/10.1002/rsa.20057)
- [Rule 110 Turing Completeness — Matthew Cook proof](https://mirror.explodie.org/universality_in_elementary_cellular_automata_by_matthew_cook.pdf)
- [Learning DNF Expressions from Fourier Spectrum](https://arxiv.org/pdf/1203.0594)
- [Rate-Distortion Theory of Neural Coding and Working Memory (eLife)](https://elifesciences.org/articles/79450)