# RRLS: independent mathematical and computational audit

Date: 2026-09-05. Companion to the Theory of Reality / Reality Bit Engine project.

**Result:** the attachment contains valid Boolean algebra and useful optimization ideas. This companion independently implements and tests selected methods. It establishes exact finite results, useful ordering effects, and explicit counterexamples to stronger claims. It does not reproduce the missing original search program or solve a Millennium Prize problem.

## 1. What the attachment establishes, and what it leaves open

| Claim or method | Assessment |
|---|---|
| Every finite Boolean function has an exact algebraic normal form (ANF) | Correct; proof below |
| Invertible binary coordinate changes preserve the represented function when the coordinate map is retained | Correct |
| A shear can be scored without recomputing the full transformed truth table | Correct; independently checked |
| A suitable basis can reduce ANF term count | Possible; no guarantee of finding the best basis |
| A basis change necessarily lowers algebraic degree | False for invertible affine binary changes |
| Adding higher-degree ANF terms necessarily improves prediction error | False; explicit counterexample below |
| Processing small relations first always saves computation linearly | False in general; intermediate interaction width governs the cost |
| The supplied benchmark timings and recovery percentages are reproducible from the attachment alone | Unestablished: the source ends partway through `search_linear_rotations`, and its benchmark driver is missing |
| Exact reconstruction proves a unique hidden mechanism or physical dimension | Does not follow |

The earlier 595-to-5-term example explicitly includes the planted correct basis among 62 candidates. That tests ranking a supplied answer among alternatives. It does not measure blind discovery of that basis. The later annealing results are separate reported claims; their complete implementation, generated cases, and scoring procedure are not supplied.

Reaching a planted term count also does not establish that the original basis was recovered: distinct bases and expressions can have the same cost and outputs. A compression objective should charge for the basis, its evaluation, and the transformed expression, rather than count expression terms alone.

## 2. Exact Boolean representation

Work in the Boolean polynomial ring

\[
\mathbb F_2[x_0,\ldots,x_{n-1}]/(x_i^2-x_i).
\]

Every function \(f:\{0,1\}^n\to\{0,1\}\) has exactly one expansion

\[
f(x)=\bigoplus_{S\subseteq\{0,\ldots,n-1\}}a_S\prod_{i\in S}x_i,
\qquad
a_S=\bigoplus_{U\subseteq S}f(1_U).
\]

**Proof.** Applying the subset transform twice gives each original entry at \(U\subseteq S\) multiplicity \(2^{|S\setminus U|}\). Modulo two this is zero unless \(U=S\), when it is one. The transform is therefore its own inverse, proving existence and uniqueness.

The dense transform uses \(n2^{n-1}\) XOR updates and \(2^n\) table entries. Being efficient relative to a supplied truth table does not make it polynomial in the number of input variables. A full truth table already contains every output on this finite domain; reconstructing it provides no additional unseen observations.

## 3. Why the shear optimization works

For each monomial in the other variables, collect its four coefficients as

\[
a+b x_i+c x_j+d x_i x_j.
\]

For the coordinate substitution \(x_i=y_i,\ x_j=y_j\oplus y_i\), Boolean multiplication gives

\[
a+(b\oplus c\oplus d)y_i+c y_j+d y_i y_j.
\]

Only the coefficient block \(b\) changes. With \(\delta=c\oplus d\), the term-count change is

\[
\Delta N=\operatorname{popcount}(\delta)
-2\operatorname{popcount}(\delta\mathbin{\&}b).
\]

The implementation uses strided NumPy views of the four coefficient blocks. Scoring reads arrays of length \(2^{n-2}\), without generating a new truth table or applying another Möbius transform. This is an exact local calculation; it does not identify the globally best sequence of shears.

**Degree obstruction.** If \(A\) is an invertible affine map, substitution gives \(\deg(f\circ A)\leq\deg(f)\). Applying the same argument to \(A^{-1}\) gives the reverse inequality. Thus

\[
\boxed{\deg(f\circ A)=\deg(f)}.
\]

Term count can change even though maximal algebraic degree cannot. This is an established affine-invariance property, also discussed in [Carlet's treatment of Boolean functions](https://www.math.univ-paris13.fr/~carlet/chap-vectorial-fcts-corr.pdf). A nonlinear change of variables requires a different analysis and must include the cost of encoding and evaluating that change.

## 4. A frozen error: lifting need not improve the fit at every step

Consider

\[
f=x_0(1\oplus x_1)(1\oplus x_2)
=x_0\oplus x_0x_1\oplus x_0x_2\oplus x_0x_1x_2.
\]

It equals one only at \((x_0,x_1,x_2)=(1,0,0)\). Retaining all ANF terms up to degree \(k\) gives:

| Largest retained degree | Wrong outputs among eight assignments |
|---:|---:|
| 0 | 1 |
| 1 | 3 |
| 2 | 1 |
| 3 | 0 |

The exact representation is eventually reached, but the intermediate error increases. This refutes monotonic improvement for this truncation rule. It does not refute every possible approximation algorithm: minimizing error over nested hypothesis classes would have a nonincreasing optimum, although finding that optimum has its own computational cost.

## 5. Making “small relations first” mathematically sound

For Boolean factors \(f_j\), count satisfying assignments by

\[
Z=\sum_{x\in\{0,1\}^n}\prod_j f_j(x_{S_j}).
\]

When eliminating variable \(v\), let \(B\) be all factors containing it, and let \(S=(\bigcup_{j\in B}S_j)\setminus\{v\}\). Replace those factors by the full boundary table

\[
g(x_S)=\sum_{x_v\in\{0,1\}}\prod_{j\in B}f_j(x_{S_j}).
\]

**Correctness.** Factors outside \(B\) do not depend on \(x_v\). Finite distributivity therefore permits summing over \(x_v\) inside its bucket, leaving the total \(Z\) unchanged. Repeating this identity eliminates all variables. Each replacement table contains nonnegative integer counts, so the implementation uses arbitrary-precision integers and stores backtracking choices for a satisfying assignment. The returned witness is checked against every original factor.

Crucially, \(g\) must preserve the joint relation among the remaining variables. Keeping only their individual allowed values loses information. For example,

\[
x_0=x_1,\qquad x_1=x_2,\qquad x_0\ne x_2
\]

has no solution, although every individual variable retains both possible values under unary projection of each constraint. Naïve independent-domain reasoning leaves eight candidates; exact joint elimination returns zero.

The implemented heuristic picks the variable whose entire touching bucket has the smallest union of variables. It recalculates this choice after each elimination. It does not merely pick the smallest original factor.

If an intermediate bucket contains \(w+1\) variables, its dense update can require \(2^{w+1}\) rows. This is the established induced-width limitation of [Dechter's bucket-elimination framework](https://www.ics.uci.edu/~csp/R48a.pdf). Ordering overhead, factor multiplicity, and integer bit lengths also contribute to runtime. Linear row growth in one graph family is not a general linear-runtime theorem.

## 6. Independently measured results

These are synthetic software experiments in this shared Linux x86-64 environment, using Python 3.12.13 and NumPy 2.3.5. No Numba or JIT was used. Each timed operation has one explicitly excluded warm run, followed by five samples for the ANF/shear tests and three for the BDD/elimination tests. Numbers below are medians from the frozen `results.json`; timings can vary on another run or PC. Data generation is outside the timers. Allocation performed inside each measured function is included.

| Experiment | Reference | Improved method / result | Exact check |
|---|---:|---:|---|
| ANF transform, 1,048,576 rows | Forward 9.913 ms | Inverse 7.573 ms | Full round trip matches |
| Score all 182 ordered shears at 14 variables | Rebuild: 34.331 ms | Delta: 2.273 ms; **15.10×** | All scores identical |
| Equality of two 10-bit words, BDD size | Grouped order: 3,069 internal nodes | Interleaved order: **30** nodes | All 1,048,576 outputs match |
| Same BDD construction time | 10.175 ms | 5.053 ms | Both builders read the full input table |
| 14-variable equality star, intermediate rows | Center first: 32,766 | Smallest bucket first: **54** | Both count exactly two models |
| Same star runtime | 36.565 ms | 0.251 ms; **145.68×** | Includes ordering and witness checking |
| 64-variable equality star | Center-first preflight refuses a 64-variable bucket | **254** intermediate rows; 5.330 ms | Exactly two models and a checked witness |
| Inconsistent equality/inequality triangle | Unary projections leave eight candidates | **Zero** satisfying assignments | Independent exhaustive check |

For the star constraints \(x_0=x_j\), \(j=1,\ldots,n-1\), the two models are all-zero and all-one. A leaf-first order needs \(4(n-1)+2\) intermediate rows. Center-first elimination generates a dense relation on all remaining leaves and enumerates \(2^{n+1}-2\) rows in this implementation. The 64-variable result exploits that structure; it does not enumerate or time all \(2^{64}\) assignments. Budget refusal is reported as unresolved under that requested order, never as unsatisfiable.

For the equality BDD, the grouped ordering uses \(3\cdot2^m-3\) internal nodes: \(2^m-1\) prefix nodes followed by \(2^{m+1}-2\) distinct suffix-test nodes. Interleaving pairs needs three nodes per pair, hence \(3m\). The companion checks these formulas through \(m=6\), then reconstructs the complete \(m=10\) table under both orders. These are deliberately selected orders for a known relation, not a blind search benchmark. Fixed-order reduction and variable-order sensitivity are established properties of [Bryant's binary decision diagrams](https://www.cs.cmu.edu/~bryant/pubdir/ieeetc86.pdf).

## 7. Verification and original-source issues

All **10 test groups passed**. They include all 256 three-variable Boolean functions under all six ordered shears (1,536 comparisons); all 256 functions under all six BDD orders (another 1,536 reconstructions); 128 seeded factor systems compared with exhaustive counts under two elimination orders; exact size formulas; malformed-input rejection; and width/work-budget refusal. `test-results.json` records source hashes; `test-results.txt` contains the test log. These are executable checks, not proof-assistant verification.

The original snippet also needs these repairs before treating its output as a trustworthy benchmark:

1. Supply the missing search body and benchmark driver, seeds, case definitions, tuning/test split, and exact success criterion.
2. Move first-use JIT compilation before the timing start. In the pasted `_anneal_once`, the timer currently starts before the optional warm-up calls. This affects first use, though previously warmed calls may be unaffected.
3. Independently reconstruct outputs before reporting a verified exact result. The shown `SearchResult` sets `exact=True` directly; valid shears provide a mathematical reason for exactness, but that flag is not an executed reconstruction check.
4. Validate bits before converting to `uint8`; reject unsupported dimensions and impossible sparse-term requests. The shown random-shear construction fails at one variable, and an excessive request for distinct sparse terms can make generation loop indefinitely.
5. Report lookup-table and basis costs alongside ANF term counts. Distinguish reaching a target cost, recovering a particular planted basis, and proving a global optimum.

## 8. Implications for the engine and the prize problems

The useful common principle is **retain enough information at each boundary to preserve the question being answered**. Coordinate transforms, factor elimination, and BDD reduction implement different versions of that principle. Their correctness does not imply uniform compression or efficient search for every input.

Likewise, a zero residual identifies the chosen fit criterion. It does not automatically identify a unique cause. Even a nonlinear map with a unique zero can have ambiguous nonzero observations: \(R(x)=x^2\) has \(R^{-1}(0)=\{0\}\), yet \(R(1)=R(-1)\). The existing engine's null-axis observability work addresses this distinction.

This companion changes neither the frozen v0.20 engine nor the Theory of Reality paper. It provides a reproducible candidate component and an audit record. Integration should preserve complete coordinate maps and joint boundary factors, verify equivalence after transformations, retain explicit budget-exhaustion status, and evaluate search quality on fresh cases without supplying the hidden basis.

For P versus NP, the remaining obstacle is a proven bound for all input instances, including large intermediate widths and the cost of obtaining a useful representation. For Riemann and Navier–Stokes, finite Boolean encodings additionally require rigorous analytic bridges, truncation/error control, and the respective unrestricted proof arguments. No such arguments are established by these benchmarks. **Millennium Prize problems solved by this work: zero.**