Certified Adaptive Discovery of Algebraic Laws

1 Introduction

Many scientific-discovery and symbolic-regression procedures search through large families of polynomial relations. Given data, an algorithm may report an equation

or a more general algebraic condition

only after inspecting the data. This creates an immediate post-selection problem. A relation may look striking simply because the search space was large, the degree was high, or the algorithm was allowed to adapt.

This paper gives a finite-sample significance theory for such discoveries. The central idea is simple. If a candidate law cuts down the sample space from $X$ to a subset $A$, and one has a certificate

then an exact fit to $A$ is unlikely under a uniform null when $V/|X|$ is small. If many possible laws are searched, the search cost is paid through a prefix-free description length. This produces e-values and e-processes that remain valid after arbitrary adaptive search and optional stopping.

The framework is deliberately modular. The statistical component is based on e-values, Kraft weights, likelihood-ratio mixtures, and nonnegative supermartingales. The geometric component enters only through volume certificates. In arithmetic applications, these certificates may come from elementary height-counting bounds, determinant-method estimates, finite-field Schwartz-Zippel bounds, or problem-specific geometry.

The contribution is therefore not a new height-counting theorem. Instead, it is a certified inference layer for algebraic discovery: once an algebraic candidate comes with a valid volume certificate and a code length fixed in advance as part of a certificate language, it receives a post-selection-valid evidence score.

The main results are:

• exact-fit post-selection validity;

• partial and noisy-fit validity via binary KL scores;

• likelihood-ratio mixtures and oracle inequalities;

• conditional and sequential e-processes for adaptive data streams;

• a corrected finite-class model-selection consistency theorem;

• replicated-law aggregation under explicit independence or conditional-validity assumptions;

• a change-point mixture for emergent laws;

• universal dominance for effective volume-certified algebraic e-tests;

• concrete algebraic certificates for hypersurfaces, linear subspaces, projective varieties, and finite fields;

• applications to symbolic regression, algebraic subspace clustering, finite-field congruence discovery, low-rank structure, and conservation laws.

2 Background and terminology

An e-value for a null hypothesis $H_0$ is a nonnegative random variable $E$ satisfying

By Markov's inequality,

Thus a large e-value gives evidence against $H_0$, with $\min\{1,1/E\}$ acting as a valid p-value.

An e-process is a nonnegative process $(E_t)_{t\ge0}$ that is a supermartingale, or at least satisfies $\mathbb E_{H_0}E_t\le1$ for all $t$, under the null. If $(E_t)$ is a nonnegative supermartingale with $E_0\le1$, Ville's inequality gives

This gives optional-stopping validity.

We use prefix-free code lengths $\kappa(c)$ satisfying Kraft's inequality:

The certificate language and code lengths are fixed before the data are analyzed. The data-dependent discovery procedure may choose a certificate adaptively after seeing the data, but it must choose from this pre-specified language.

3 Abstract volume certificates

Let $X$ be a finite set. Under the basic null,

Definition 3.1 (Volume certificate).

A volume certificate is a triple

\[ c=(A_c,V_c,\kappa_c), \]

where

\[ A_c\subseteq X,\qquad V_c>0,\qquad |A_c|\le V_c, \]

and $\kappa_c$ is a prefix-free code length. Set

\[ p_c=\min\left\{1,\frac{V_c}{|X|}\right\}. \]

Then

The interpretation is that $A_c$ is the set satisfying a discovered law, $V_c$ is an upper bound on its null volume, and $\kappa_c$ is the search or description cost of the law.

Certificates with $p_c=1$ are valid but noninformative. Likelihood-ratio formulae below are stated for $0<p_c<1$; endpoint cases are handled by omission or by the corresponding limiting convention.

4 Exact-fit adaptive discovery

For fixed $c$, define

if

and define $S_N(c)=-\infty$ otherwise. Let

Theorem 4.1 (Exact-fit post-selection significance).

Under $H_0$, for every $s\ge0$,

\[ \mathbb P_{H_0}(S_N^*\ge s)\le2^{-s}. \]

Consequently, if an arbitrary adaptive discovery procedure reports a certificate $c$ with $S_N(c)=s$, then

\[ p_{\mathrm{post}}\le2^{-s} \]

is a valid post-selection p-value.

Equivalently,

is an e-value, and $\log_2E_N\ge S_N^*$.

5 Partial and noisy algebraic laws

Exact fit is often too strict. Define

For $q,p\in[0,1]$, let

be binary KL divergence in bits, with the usual boundary conventions.

For $0<p_c<1$, define

if $H_c/N>p_c$, and define $K_N(c)=-\infty$ otherwise. Let

Theorem 5.1 (Partial-fit post-selection significance).

Under $H_0$, for every $s\ge0$,

\[ \mathbb P_{H_0}(K_N^*\ge s)\le2^{-s}. \]

Thus, if a reported law $c$ contains $h$ of $N$ data points, the score

\[ N d_2(h/N\mid p_c)-\kappa_c-\log_2(N+1) \]

is a valid post-selection evidence score whenever $h/N>p_c$.

6 Likelihood-ratio mixtures and oracle bounds

For fixed $c$ with $0<p_c<1$ and for $\theta\in[p_c,1]$, define

For every $\theta\in[p_c,1]$, $L_{c,N}(\theta)$ is an e-value under $H_0$.

Let

Define

Proposition 6.1 (Robust GLR lower bound).

The quantity $M_{c,N}$ is an e-value. If $H_c/N>p_c$, then

\[ \log_2M_{c,N} \ge N d_2(H_c/N\mid p_c)-\log_2(N+1). \]

Mixing over certificates yields the oracle inequality

7 Conditional and sequential certificates

Let $(\mathcal F_t)_{t\ge0}$ be a filtration and let $X_t$ be the observation at time $t$.

A predictable certificate $c$ specifies events

where $A_{c,t}$ is $\mathcal F_{t-1}$-measurable, and predictable numbers

Assume the null satisfies

almost surely for every $c,t$.

Define

Let

be predictable. Define

Theorem 7.1 (Conditional-volume e-process).

For every $c$ and every predictable strategy $(\theta_{c,t})$, the process $(L_{c,t})_{t\ge0}$ is a nonnegative supermartingale under the null. Consequently,

\[ \mathbb P_{H_0}\left(\sup_{t\ge0}L_{c,t}\ge2^s\right)\le2^{-s}. \]

Now suppose $\mathcal C$ is prefix-free and, for each $c$, $\Pi_c$ is a countable family of predictable strategies with weights $w(\pi\mid c)\ge0$ satisfying

Define

Corollary 7.2 (Universal anytime-valid search).

The process $(U_t)$ is a nonnegative supermartingale with initial expectation at most $1$. Hence

\[ \mathbb P_{H_0}\left(\sup_{t\ge0}\log_2 U_t\ge s\right)\le2^{-s}. \]

8 Change-point discovery

We now make the change-point extension explicit. Suppose a certificate $c$ may become active after an unknown time $\tau$. For $t<\tau$, define

For $t\ge\tau$, define

where

Under the no-law null, this is an e-process that is inactive before $\tau$ and starts from value $1$ at time $\tau-1$.

Let $\Theta_c\subset[p_c,1]$ be countable with weights $a_{\theta\mid c}\ge0$, $\sum_{\theta\in\Theta_c}a_{\theta\mid c}\le1$. Let

Define the full mixture over all start times by

Theorem 8.1 (Change-point algebraic discovery).

Under the null, $(U_t^{\mathrm{cp}})_{t\ge0}$ is a nonnegative supermartingale with initial expectation at most $1$. In particular,

\[ \mathbb P_{H_0}\left(\sup_t\log_2U_t^{\mathrm{cp}}\ge s\right)\le2^{-s}. \]

For computation at time $t$, the infinite tail $\tau>t$ contributes only its inactive value. It may therefore be evaluated as a deterministic tail mass, or truncated with the remaining tail kept as an inactive reserve.

9 Power under planted algebraic incidence

Let $P$ be an alternative distribution on $X$. For certificate $c$, set

Assume

Theorem 9.1 (Linear power).

Under i.i.d. sampling from $P$,

\[ \frac1N K_N(c)\to d_2(\theta_c\mid p_c) \]

almost surely. Consequently, for every sequence $s_N=o(N)$,

\[ \mathbb P_P(K_N^*\ge s_N)\to1. \]

10 Finite-class model-selection consistency

The score $K_N(c)$ equals $-\infty$ whenever $H_c/N\le p_c$. Therefore, for consistency statements, it is cleaner to use the nonnegative score

where the KL term is interpreted as $0$ when $H_c/N\le p_c$.

Let $\mathcal C_0\subset\mathcal C$ be finite. Under an alternative distribution $P$, define

and

Assume $c_*$ is the unique maximizer of $J(c)$ over $\mathcal C_0$, and assume

Let

Theorem 10.1 (Finite-class consistency).

Under $P$,

\[ \mathbb P(\widehat c_N=c_*)\to1. \]

11 Replicated laws

Suppose there are environments $e=1,\dots,E$. In environment $e$, observations satisfy a null incidence certificate

There are two valid settings.

11.1 Independent environments

If the environments are independent under the null, then the product of environment-specific e-values is an e-value.

11.2 Ordered conditional validity

More generally, order all observations in a single global filtration. If each environment-specific factor is conditionally valid given the past, then the product process is a supermartingale.

Under either condition, if environment $e$ supplies $N_e$ observations, hit fraction $\widehat q_{c,e}$, and constant certificate $p_{c,e}$, the replicated score

is post-selection valid after mixing over $c$. The model cost $\kappa_c$ is paid once, while evidence accumulates across environments.

12 Simultaneous effect-size confidence sets

Let $q_c=P(X\in A_c)$ be the true incidence probability. For $u\in[0,1]$, let $M_{c,N}(u)$ be an e-value valid under the null

Define the confidence set

Theorem 12.1 (Simultaneous post-selection confidence sets).

With probability at least $1-\alpha$,

\[ q_c\in \mathcal I_{c,N}(\alpha) \]

for every $c$.

We call these confidence sets, not intervals; they need not be intervals without further monotonicity assumptions.

13 Information-theoretic optimality

Let $P_0$ be a reference distribution and let $A\subseteq X$ have exact null mass $P_0(A)=p$. For $\theta\in(0,1)$, define the tilted alternative

Then $P_\theta(A)=\theta$.

For $N$ observations, the likelihood ratio is

Also,

If a test has type-I error at most $\alpha$ under $P_0^N$ and type-II error at most $\beta$ under $P_\theta^N$, data processing gives

Thus

The KL scores above detect at the same information rate, up to description length and universal coding regret.

14 Necessity of search penalties

Let $A_1,\dots,A_M$ be disjoint subsets of $X$, each with null mass $p$. Assign each model code length

Kraft is tight:

The event that all $N$ samples fall into one of the $A_j$ has probability

For each such model, the exact-fit score is

Thus

Hence the bound in Theorem 4.1 is sharp in the abstract volume-certificate model, and the search penalty cannot be uniformly removed.

15 Universal dominance

Let $\mathcal E$ be a computably enumerable class of elementary certified e-values or e-processes. Let $\mathbf m(e)$ be a universal lower-semicomputable semimeasure on $\mathcal E$. Define

A certified e-test is any lower-semicomputable subprobability mixture

where $w(e)\ge0$, $\sum_e w(e)\le1$, and $w$ is lower semicomputable.

Theorem 15.1 (Universal dominance).

For every certified e-test $E$, there exists a constant $C_E$, depending only on the effective description of $E$, such that

\[ E\le C_EU \]

pointwise. Equivalently,

\[ \log_2E\le \log_2U+O(K(E)). \]

This theorem characterizes the precise class being dominated: effective tests built as mixtures of certified geometric evidence. It does not claim dominance over all possible statistical tests.

16 Algebraic certificates over height balls

Let

be a finite height ball in projective space. An algebraic certificate is a proper closed algebraic subset

together with a bound

Then

The statistical machinery is independent of how $V_B(Y)$ is obtained.

16.1 Hypersurfaces

Let $F\in\mathbb Z[X_0,\dots,X_n]$ be nonzero homogeneous of degree $D$, and let $Y=Z(F)$. A crude box-counting Schwartz-Zippel argument gives

Since

one obtains

Thus an exact degree-$D$ homogeneous polynomial law has leading score

16.2 Linear subspaces

If $L\subseteq\mathbb P^n$ is a rational $m$-plane, then

Thus

For a union of $K$ rational $m$-planes,

16.3 General projective varieties

Let $Y\subsetneq\mathbb P^n_{\mathbb Q}$ be a reduced closed algebraic subset of dimension $m\ge1$ and total degree $D$. A finite-projection argument, or sharper determinant-method estimates when available, can supply bounds of the schematic form

Consequently,

For $m=0$,

and

These bounds are intentionally crude and may be replaced by sharper arithmetic estimates.

16.4 Finite fields

Let $X=\mathbb F_q^d$. If $F\in\mathbb F_q[x_1,\dots,x_d]$ is nonzero of degree $D<q$, then Schwartz-Zippel gives

so

17 Application I: adaptive symbolic regression over rational data

Let a symbolic-regression procedure search through homogeneous polynomials and report

of degree $D$ and code length $\kappa(F)$, vanishing on $h$ of $N$ rational points in $X_B$.

Using

the valid post-selection score is

For exact fit, this becomes

Therefore a discovered degree-$D$ polynomial law is significant only if

This is a finite-sample anti-overfitting threshold.

18 Application II: algebraic subspace clustering

Suppose an algorithm discovers

a union of rational $m$-planes in $\mathbb P^n$. Then

If all $N$ observations lie in the discovered union, the exact-fit score is

Thus increasing the number of fitted subspaces is penalized both by increased null volume and by model description length. Partial-fit versions use the KL score and allow outliers.

19 Application III: finite-field congruence laws

Let

under the uniform null. Let $F\in\mathbb F_q[x_1,\dots,x_d]$ be nonzero of degree $D<q$. Since

an exact discovered congruence law

has score

If the same integer polynomial law is tested across fields

and remains nonzero modulo each $q_e$, then the replicated exact score is

under the independence or conditional-validity assumptions of Section 11.

20 Additional examples

The same framework applies whenever a valid volume certificate is available.

20.1 Low-rank matrices

Nonzero $a\times b$ rational matrices form a projective space $\mathbb P^{ab-1}$. The rank-$\le r$ determinantal variety has codimension

For fixed $a,b,r$, its degree is constant, hence

Exact low-rank structure across $N$ observations has leading evidence

20.2 Conservation laws

Let $X_t$ be a state process on a bounded integer box. A candidate invariant $I$ gives events

If one can certify

then the conditional e-process theorem applies. The scientific content lies in justifying this null certificate.

20.3 Missing data

If only coordinates indexed by a predictable pattern $\Omega_t$ are observed, replace $Y$ by its projection

The framework applies once one certifies

21 Multiple discoveries

If several independent or dependent discovery projects produce valid e-values

then e-value multiple-testing procedures such as e-BH may be used to control false discovery rate under their stated assumptions. This allows many algebraic-discovery pipelines to be run in parallel, provided each reported law is accompanied by a valid e-value.

22 Scope and limitations

This framework does not produce volume certificates automatically. It converts valid certificates into post-selection-valid inference.

The framework is not a new theorem in rational-point counting. Any sharper arithmetic or geometric estimate can be substituted for the crude certificates stated here.

The universal dominance theorem is relative to the chosen effective certificate language. It is not a dominance theorem over all possible statistical tests.

The algebraic null model must be meaningful for the application. Uniform height balls and finite fields are convenient reference cases, but applications may require conditional or nonuniform volume certificates.

The term ``model-selection consistency'' in this paper is finite-class and incidence-based. It does not assert recovery of an algebraic variety in a metric or scheme-theoretic sense.

23 Conclusion

We have developed a certified inference framework for algebraic laws discovered after adaptive search. The core mechanism is a volume certificate combined with a prefix-free model code. From this we obtain finite-sample post-selection validity, noisy and partial-fit validity, optional-stopping validity, finite-class consistency, replicated-law aggregation under explicit assumptions, change-point mixtures, and universal dominance over effective certified e-tests.

The main practical implication is an anti-overfitting law for algebraic discovery. A polynomial equation, subspace union, congruence law, or algebraic constraint discovered after inspecting the data is significant only when its certified volume reduction beats both its description length and its geometric complexity.

For symbolic regression over rational points, a degree-$D$ exact polynomial law receives leading evidence

Thus high-degree interpolation is not significant merely because it fits; the equation must be simple and its null volume must be small.

The framework is best viewed as a rigorous MDL/e-value layer for algebraic and arithmetic discovery. Its strength depends on the quality of the supplied volume certificates.