# Dimensional PRNG Tomography v4 — Formal Core

## Scope

The goal is **not** to claim that deterministic pseudorandom output is secretly
easy to predict. A PRNG is deterministic by definition. The meaningful
question is:

\[
\boxed{\text{Can relational transforms expose a low-complexity generating law
from observed outputs?}}
\]

This version targets deliberately non-cryptographic families:
LFSRs, polynomial congruential recurrences, and xorshift32.

A cryptographically secure PRNG is explicitly outside the claim.

---

## 1. The nonlinear annihilator theorem

Let \(p\) be prime and let

\[
x_{n+1}
=
c_0+c_1x_n+c_2x_n^2+\cdots+c_dx_n^d
\pmod p.
\]

Write the same law one step earlier:

\[
x_n
=
c_0+c_1x_{n-1}+c_2x_{n-1}^2+\cdots+c_dx_{n-1}^d.
\]

Subtract:

\[
\boxed{
x_{n+1}-x_n
=
\sum_{j=1}^{d}
c_j\left(x_n^j-x_{n-1}^j\right)
\pmod p.
}
\]

The constant dimension \(c_0\) is annihilated exactly.

Define the relational feature vector

\[
\Phi_n=
\left(
x_n-x_{n-1},
x_n^2-x_{n-1}^2,
\ldots,
x_n^d-x_{n-1}^d
\right).
\]

Then

\[
\boxed{
\Delta x_n
=
\Phi_n\cdot(c_1,\ldots,c_d).
}
\]

So a recurrence nonlinear in state becomes a **linear inverse problem in a
lifted relational feature space**.

If \(d\) such feature rows are linearly independent, \(c_1,\ldots,c_d\) are
unique. Then one original transition recovers \(c_0\).

This is the exact nonlinear extension of the earlier "move to a dimension
where the nuisance parameter vanishes" principle.

---

## 2. LCG as degree-1 special case

For

\[
x_{n+1}=ax_n+c\pmod p,
\]

subtracting consecutive equations gives

\[
\boxed{
x_{n+1}-x_n
=
a(x_n-x_{n-1})\pmod p.
}
\]

Thus the additive increment \(c\) disappears.

When \(x_n-x_{n-1}\ne0\),

\[
\boxed{
a=
\frac{x_{n+1}-x_n}{x_n-x_{n-1}}
\pmod p.
}
\]

Then

\[
c=x_n-ax_{n-1}\pmod p.
\]

This is a direct instance of relational projection revealing the encoder.

---

## 3. Quadratic generator

For

\[
x_{n+1}=a x_n^2+b x_n+c,
\]

the relational equation is

\[
\boxed{
x_{n+1}-x_n
=
a(x_n^2-x_{n-1}^2)
+
b(x_n-x_{n-1}).
}
\]

Two independent relational equations recover \(a,b\); then one original
equation recovers \(c\).

So nonlinear output does not imply nonlinear parameter inference.

---

## 4. LFSR / linear-complexity dimension

For a binary sequence \(s_n\), define its **linear complexity** \(L\) as the
length of the shortest binary linear feedback shift register generating it.

For an LFSR sequence of linear complexity \(L\), \(2L\) consecutive output
bits uniquely determine the minimal LFSR. This is the classical
Berlekamp-Massey result.

In this framework:

\[
\boxed{
D_{\rm LC}(s)=L
}
\]

is a relational complexity coordinate.

A long sequence can look statistically balanced while having a very small
\(D_{\rm LC}\), making it structurally predictable.

---

## 5. Two 265-bit observations

Concatenate two observed 265-bit words:

\[
W=A\Vert B
\]

to obtain 530 output bits.

If those 530 bits come from an LFSR of complexity \(L\le265\), then in
principle the first \(2L\le530\) bits are sufficient to identify the minimal
linear recurrence.

For example, if \(L=37\):

\[
74\text{ bits}
\]

can determine the recurrence, leaving

\[
456\text{ observed bits}
\]

as an enormous exact holdout test.

Thus two apparently random 265-bit numbers can contain enough evidence to
recover a hidden low-complexity linear generator.

They cannot, however, uniquely identify an unrestricted generator.

---

## 6. Model discovery rule

The engine never accepts a model merely because it interpolates the observations
used to fit it.

It uses:

\[
\boxed{\text{fit on prefix} \rightarrow \text{predict untouched suffix}.}
\]

A candidate generator class survives only if its future outputs are reproduced
exactly.

This is essential because sufficiently flexible models can fit arbitrary finite
data.

---

## 7. Falsifiability

For random control data, a low-degree polynomial recurrence may interpolate the
minimum fitting window but should fail the held-out sequence.

Similarly Berlekamp-Massey can always produce a recurrence for a finite prefix;
the meaningful test is whether that recurrence predicts independent future
bits.

Therefore:

\[
\boxed{
\text{compression without out-of-sample prediction is not evidence of a
generator law.}
}
\]

---

## 8. What would count as a genuinely new result?

The individual ingredients here are established mathematics:
finite-field recurrences, finite differences, feature lifting, LFSRs,
Berlekamp-Massey, and xorshift linearity.

Novelty would require the **unified relational operator search** to infer
unknown generator families more efficiently or from weaker observations than
existing system-identification methods.

That is the next benchmark.