Theory of Complexity Budgets and Filtered Separation Spaces

Premise: what follows consists of original ideas and observations reorganized, presented, and elaborated by ChatGPT.

0. Purpose of the Theory

The goal is to build a common mathematical lens for problems that, across different fields, share the same deep form: a given construction, proof, description, computation, representation, measurement, or observation cannot succeed because the target requires more complexity than is available.

The initial formulation was:

every construction has a complexity budget; whatever exceeds that budget cannot have been constructed in that way.

This idea is correct, but too broad. Taken this way, it is a paraphrase of many already existing theories: Kolmogorov complexity, height theory, circuit lower bounds, proof complexity, automata theory, communication complexity, descriptive complexity, Minimum Description Length, controlled algebra, information theory, and counting arguments.

The next conceptual step is to recognize that the most fertile way to make the theory operational is not to start from one absolute notion of complexity, but from a more structural question:

what can a system distinguish within a given budget?

This leads to the central new formalism: filtered test spaces and separative complexity. The general theory then becomes a theory of failures of complexity transfer, but with a precise technical core: lower bounds are certificates of indistinguishability with respect to filtered families of tests.

1. The General Philosophy

Many mathematical problems have the form:

can I construct this object?
can I describe this property?
can I prove this statement?
can I distinguish these two objects?
can I recognize this language?
can I communicate enough information?
can I compress these data?
can I generically parametrize this family?
can I represent this structure with a simple encoding?
can I certify this truth with a short proof?
can I generate this dynamic behavior with a simple rule?

The negative answer is often:

no, because the available system does not have enough complexity, information, memory, expressiveness, height, dimension, entropy, depth, length, or separative capacity.

The proposed theory tries to unify these situations. The general principle is:

source + construction + budget -> target.

A problem is a transfer question. Here S is the source space, T is the target space, C is a class of constructions, every source has a complexity, every construction has a cost, every target has a required complexity, and the problem asks whether the available budget is sufficient to reach, distinguish, describe, certify, or produce the target.

The separative formalism refines this picture. Instead of asking immediately how complex the object is, we ask:

which tests are available at budget r, and which objects can those tests distinguish?

This question is more primitive and more transversal. A mathematical system is defined not only by the objects it produces, but also by the distinctions it can make.

2. Filtered Complexity Spaces

The most general basis remains a filtered space. A complexity space is a pair (X, C_X), where X is a set of objects and:

C_X : X -> Γ

is a complexity function with values in an ordered set Γ, for example N, R_≥0, or R_≥0 ∪ {∞}. Equivalently, this gives a filtration:

X_≤r = { x ∈ X : C_X(x) ≤ r }.

The sets X_≤r are the complexity balls. They contain the objects that are reachable, describable, observable, or controllable within budget r.

An important property is finiteness of balls:

|X_≤r| < ∞.

When this holds, the system has a Northcott-type property: every complexity bound reduces a potentially infinite search to a finite search.

This structure captures height of rational and algebraic points, binary length of integers, word length in groups, number of automaton states, circuit size, proof length, Kolmogorov complexity, degree of polynomials, vector norm, energy of configurations, dimension of finite structures, cost of programs, and number of communicated bits.

But this is only the first half of the theory. The second half, more new and more useful, concerns tests.

3. Filtered Test Spaces

A filtered test space is a structure:

X = (X, A, (T_r)_{r∈R})

where X is a space of objects, A is a space of observable answers, often {0, 1} but possibly a finite alphabet, a set of labels, or a set of numerical or logical values; R is an ordered set of budgets; and T_r ⊆ A^X is the set of tests available with cost at most r. The filtration is monotone:

r ≤ s ⇒ T_r ⊆ T_s.

A test is a function:

τ : X -> A.

The meaning is that T_r contains all observations, decisions, formulas, protocols, automata, circuits, queries, proofs, experiments, or procedures admitted within budget r.

The fundamental induced structure is an indistinguishability relation. Define:

x ≡^X_r y

if and only if:

∀τ ∈ T_r, τ(x) = τ(y).

In words, x and y are indistinguishable at budget r if no test of cost at most r separates them.

This definition is extremely general. Depending on what the tests are, it recovers bounded Myhill-Nerode equivalence for automata, logical indistinguishability for logical fragments, indistinguishability by communication protocols, indistinguishability by bounded queries, indistinguishability by small circuits, indistinguishability by short proofs, statistical indistinguishability, computational indistinguishability, observational indistinguishability in dynamic systems, and experimental equivalences in physical or probabilistic models.

The theory of lower bounds can be read as a theory of indistinguishable pairs:

x ≡_r y, but a target property separates them.

4. Separative Complexity

Let:

P : X -> B

be a property, classification, decision, function, or target observable. The separative complexity of P with respect to the filtered test space X is:

δ_X(P) = inf { r : P is constant on the classes of ≡^X_r }.

In other words, δ_X(P) is the minimum budget required for the available tests to distinguish enough to determine P.

If P is boolean:

P : X -> {0, 1},

then P is decidable at budget r if every pair indistinguishable at budget r has the same value of P. Thus:

P decidable at budget r ⇔ x ≡_r y ⇒ P(x) = P(y).

A separative lower bound has the form:

∃x, y ∈ X : x ≡_r y but P(x) ≠ P(y).

This is the fundamental negative certificate. No test of cost r distinguishes x from y, but the property to be decided distinguishes them. Therefore budget r is not enough. This sentence is the common form of many lower bounds.

5. Separative Spectrum

A filtered test space measures not only the complexity of individual properties, but also how many distinctions are available at each budget. Define the separative spectrum:

N_X(r) = |X / ≡^X_r|.

If X is infinite, one often works with finite subspaces X_n:

N_X(n, r) = |X_n / ≡^X_r|.

This number measures the separative power of the model at budget r. If N_X(r) is small, the model sees few observational types. If it is large, the model can distinguish many objects.

This notion generalizes the number of distinguishable states, the number of Myhill-Nerode classes, the number of transcripts in protocols, the number of decision regions of circuits or models, the number of logical types at bounded quantifier rank, the number of possible answers of bounded-query algorithms, and the number of observational classes in an experiment.

The separative spectrum is a structural version of model capacity.

6. Separative Deficit

If a system is supposed to represent or decide a family of properties requiring many distinctions, but its separative spectrum is too small, then there is a deficit. Informally:

D_sep(r) = log N_required(r) - log N_available(r).

If D_sep(r) > 0, then the system does not have enough separative power. This is the separative version of the entropic deficit.

The entropic deficit says: there are too many objects relative to the constructions. The separative deficit says: there are too many required distinctions relative to the distinctions available.

The second is often subtler than the first. A lower bound does not always require many objects; sometimes it is enough that there exist two objects the model cannot distinguish but the property distinguishes.

7. Filtered Interpretations

The notion that allows results to be transferred between different theories is that of a filtered interpretation. Let:

X = (X, A, (T^X_r)) and Y = (Y, A, (T^Y_r))

be two filtered test spaces. A map:

I : X -> Y

is a filtered interpretation with overhead σ if every cheap test on Y, pulled back along I, becomes a not-too-much-more-expensive test on X. Formally:

τ ∈ T^Y_r ⇒ τ ∘ I ∈ T^X_{σ(r)}.

That is:

I*(T^Y_r) ⊆ T^X_{σ(r)}.

The interpretation is filtered because it respects budgets. Its meaning is: if I know how to observe Y with cost r, then I can observe X through I with cost at most σ(r).

This is the abstract form of many reductions used in lower bounds: a small automaton for a language induces a small communication protocol; a small logical formula induces a test in a bounded logical game; a small circuit induces a matrix or function of bounded rank; an algorithm with few queries induces a coarse partition of the inputs; a short proof induces a short verifiable certificate; a compressed representation induces a compressed distinction procedure; a simple statistical model induces a limited class of decision regions.

A filtered interpretation formalizes the statement: if an economical solution existed in the target world, then an economical solution would exist in the source world. This is exactly the structure of reductions for lower bounds.

8. Separative Transfer Theorem

The central theorem of the new formalism is the following.

Let:

I : X -> Y

be a filtered interpretation with overhead σ. Then:

1. Pullback of Indistinguishability

If:

x ≡^X_{σ(r)} x',

then:

I(x) ≡^Y_r I(x').

2. Transfer of Lower Bounds

Let Q : Y -> B be a property on Y, and set:

P = Q ∘ I : X -> B.

Then:

δ_X(P) ≤ σ(δ_Y(Q)).

Equivalently, in contrapositive form:

δ_X(P) > σ(r) ⇒ δ_Y(Q) > r.

In words: if the pulled-back problem P = Q ∘ I is difficult in X, then the original problem Q is difficult in Y, with loss controlled by σ. This is the general form of lower-bound transfer.

9. Proof of the Theorem

Suppose:

x ≡^X_{σ(r)} x'.

We want to show:

I(x) ≡^Y_r I(x').

Let τ ∈ T^Y_r. Since I is filtered with overhead σ, we have:

τ ∘ I ∈ T^X_{σ(r)}.

Since x ≡^X_{σ(r)} x', it follows that:

(τ ∘ I)(x) = (τ ∘ I)(x').

Hence:

τ(I(x)) = τ(I(x')).

This holds for every τ ∈ T^Y_r. Therefore:

I(x) ≡^Y_r I(x').

Now suppose Q is decidable in Y at budget r. This means that Q is constant on the classes of ≡^Y_r. If x ≡^X_{σ(r)} x', then the first part gives:

I(x) ≡^Y_r I(x').

Therefore:

Q(I(x)) = Q(I(x')).

Since P(x) = Q(I(x)) and P(x') = Q(I(x')), we get P(x) = P(x'). Thus P is constant on the classes of ≡^X_{σ(r)}, and:

δ_X(P) ≤ σ(r).

Taking r = δ_Y(Q) gives:

δ_X(P) ≤ σ(δ_Y(Q)).

The contrapositive form is:

δ_X(P) > σ(r) ⇒ δ_Y(Q) > r.

10. Monotonicity of the Separative Spectrum

A filtered interpretation also controls separative spectra.

If:

I : X -> Y

is filtered with overhead σ, then on the image I(X):

N_Y(I(X), r) ≤ N_X(X, σ(r)).

In words: the world Y, restricted to the image of X, cannot distinguish more classes at budget r than X distinguishes at budget σ(r).

Proof: if two points x, x' ∈ X are equivalent in X at budget σ(r), then their images are equivalent in Y at budget r. Therefore every equivalence class in X at budget σ(r) is sent into one equivalence class in Y at budget r. Hence the number of distinguishable classes in the image cannot exceed the number of distinguishable classes in the source.

11. Composition of Overheads

Filtered interpretations compose. Let:

X --I--> Y --J--> Z

be filtered interpretations with overheads σ and ρ, respectively. Then:

J ∘ I : X -> Z

is filtered with overhead:

σ ∘ ρ.

Indeed, if τ ∈ T^Z_r, then τ ∘ J ∈ T^Y_{ρ(r)}. Then (τ ∘ J) ∘ I ∈ T^X_{σ(ρ(r))}. Thus τ ∘ J ∘ I ∈ T^X_{σ(ρ(r))}.

This property is fundamental because many modern lower bounds are chains of transfers:

query complexity -> communication complexity -> automata -> grammars -> encodings.

The formalism says that, if every arrow is filtered, the lower bound propagates automatically with composed overhead.

12. Normal Form of Separative Lower Bounds

In a filtered test space, every decision lower bound can be expressed as an indistinguishable pair. Let:

P : X -> {0, 1}.

Then the following conditions are equivalent:

P is not decidable at budget r;
P is not constant on the classes of ≡_r;
there exist x, y ∈ X such that x ≡_r y but P(x) ≠ P(y).

This equivalence is formally simple, but conceptually powerful. It says that a separative lower bound is always an indistinguishability certificate: the model does not distinguish two objects that the problem must distinguish. This is the common core of automata, finite logic, communication, query complexity, decision-tree lower bounds, inexpressibility proofs, and many computational lower bounds.

13. Link with the General Theory of Budgets

The separative formalism does not replace the other complexities; it organizes them. The general theory has four levels.

Level 1: Intrinsic Complexity

This measures how complex an object is in itself:

C_obj(x).

Examples include height, degree, length, dimension, norm, energy, and Kolmogorov complexity.

Level 2: Constructive Complexity

This measures how much it costs to produce an object:

C_prod(x) = inf { C(F) : F produces x }.

Examples include circuit size, shortest program, straight-line complexity, expression length, and number of generators.

Level 3: Certificative Complexity

This measures how much it costs to prove or certify a property:

C_cert(x, P).

Examples include proof length, certificate size, witness complexity, and refutation length.

Level 4: Separative Complexity

This measures how much it costs to distinguish objects enough to decide a property:

δ_X(P).

These levels interact. A cheap construction can induce a cheap test; a short certificate can induce a distinction; a short description can compress an object; a low-height object can be enumerated in a finite ball; a small circuit induces limited partitions of the input space; a small automaton induces few distinguishable classes; a small logical formula induces a coarse equivalence.

The separative formalism is the most useful bridge between models, because lower bounds often transfer through indistinguishability.

14. General Dictionary of Mathematical Areas

The following translates several areas into the common formalism.

14.1 Kolmogorov Complexity

The objects are finite strings X = {0, 1}*. The complexity K(x) is the length of the shortest program that prints x. The constructions are programs on a universal machine, and the budget is program length.

The lower bound K(x) > n means that no program of length at most n produces x. Kolmogorov complexity is a universal constructive/descriptive complexity theory. The filtered space is:

X_≤n = { x : K(x) ≤ n }.

An incompressibility argument says: if a situation produced a description of x shorter than K(x), there would be a contradiction. Separatively, a short program can be seen as a test or representation that induces few possibilities. Incompressible objects lie outside the low levels of the filtration. The certificate type is compressive.

14.2 The Incompressibility Method

The objects are strings, graphs, permutations, and finite structures encoded as strings. The complexity is Kolmogorov complexity. The schema is to choose an incompressible object x, assume that a property fails, and show that the failure yields a short encoding of x. This contradicts incompressibility.

This is the individual version of entropic obstruction. Entropy says that almost all objects are incompressible. The incompressibility method says: take a specific incompressible object and use it as a negative certificate. The certificate type is compressive, sometimes individualized entropic.

14.3 Algorithmic Probability and Solomonoff

The objects are finite strings or observations. The complexity is Kolmogorov complexity. The approximate weight is:

μ(x) ≈ 2^{-K(x)}.

This is the transformation:

C(x) -> e^{-sC(x)}.

In the general formalism, given a complexity C, one can define:

Z_C(s) = Σ_x e^{-sC(x)}

and, if it converges:

μ_s(x) = e^{-sC(x)} / Z_C(s).

Algorithmic probability is a case where the complexity is universal descriptive complexity. The structure type is a measure associated with complexity.

14.4 Minimum Description Length

The objects are data and models. The complexity is the length of the model description plus the residual length of the data given the model:

L(M) + L(D | M).

The constructions are statistical or computational models. MDL is a theory of descriptive-budget optimization. The question is not whether construction is possible, but which construction minimizes the total balance:

arg min_M [ C(M) + C(D | M) ].

The certificate is not necessarily negative; it is a principle for choosing a minimum-budget model.

14.5 Height Theory

The objects are rational numbers, algebraic numbers, and points on varieties. The complexity is height. For rationals:

x = a/b, gcd(a, b) = 1, H(x) = max(|a|, |b|), h(x) = log H(x).

The constructions are arithmetic operations, rational maps, and algebraic morphisms. The budgets are height inequalities, for example:

h(x + y) ≤ h(x) + h(y) + O(1), h(xy) ≤ h(x) + h(y), h(f(P)) ≤ d h(P) + O(1).

Height theory is a mature theory of intrinsic arithmetic complexity. Height-bounded balls are finite in many appropriate contexts, so height produces pointwise obstructions and finite reductions. The certificate type is pointwise, arithmetic, and Northcottian.

For example, to exclude x + y = z, one can use h(z) > h(x) + h(y) + O(1). Then z is too high to be the sum of x and y.

14.6 p-adic and Factorial Complexity

The objects are integers and rationals. For:

x = ± ∏_p p^{v_p(x)}

define:

C_val(x) = Σ_p |v_p(x)|.

For positive integers:

C_val(n) = Ω(n),

the number of prime factors counted with multiplicity. Multiplication and division are the natural constructions. The budget is controlled by:

C_val(xy) ≤ C_val(x) + C_val(y).

Addition, however, is irregular with respect to this complexity. This complexity is natural for multiplicative and p-adic operators, but not for additive operators. It shows that different complexities fit different operators. There is no single universal complexity. The certificate type is local arithmetic, multiplicative, and valuative.

14.7 Circuit Complexity

The objects are boolean functions f : {0, 1}^n -> {0, 1} or, in the arithmetic case, polynomials. The constructions are circuits. The budgets are size, depth, fan-in, fan-out, number of gates, degree, and width.

C(f) = min { cost of a circuit computing f }.

In filtered spaces:

C_≤r = { functions computable by circuits of cost ≤ r }.

A lower bound is f ∉ C_≤r. In the separative translation, tests are circuits of bounded size or depth:

T_r = { circuits of cost ≤ r }.

Two inputs, functions, or distributions are indistinguishable if all small circuits give the same answer or fail to separate them. Typical certificates include rank, degree, dimension, restrictions, partial derivatives, shifted partial derivatives, communication matrices, the polynomial method, and random restrictions.

These invariants show that every small circuit has a bounded invariant, the target has a large invariant, and therefore no small circuit computes it. The certificate type is constructive, separative, and algebraic.

14.8 Proof Complexity

The objects are formulas, tautologies, unsatisfiable sets, and statements. The constructions are proofs or refutations in a fixed system. The budgets are proof length, size, depth, width, degree, number of lines, or rank of the system.

C_P(φ) = min { |p| : p proves φ in system P }.

A filtered proof space has proofs of cost at most r. A lower bound is C_P(φ) > r. Separatively, a proof system can be viewed as a family of certificates or tests. If two structures or assignments are indistinguishable by short proofs, but a refutation would have to distinguish them, then a lower bound follows. The certificate type is certificative, sometimes separative or algebraic.

14.9 Automata Theory

The objects are words, languages, transducers, and regular relations. The constructions are finite automata, DFA, NFA, unambiguous automata, weighted automata, and transducers. The budgets are number of states, transitions, ambiguity, and representation size.

For a regular language L:

C(L) = minimum number of states of an automaton recognizing L.

Separatively, the tests are automata with at most r states:

T_r = { automata with ≤ r states }.

Two words are indistinguishable at budget r if no r-state automaton separates them. In the classical case, Myhill-Nerode measures how many distinguishable classes are needed to recognize a language. If a language requires N distinguishable classes, then every DFA requires at least N states.

Myhill-Nerode is an exact separative spectrum: an automaton with few states induces a coarse partition; if the property requires a finer partition, the state budget is insufficient. The certificate type is purely separative.

14.10 Communication Complexity

The objects are distributed functions f : X × Y -> Z. The constructions are communication protocols. The budgets are communicated bits, rounds, revealed information, randomness, and error.

C_comm(f) = minimum number of bits needed to compute f.

Separatively:

T_r = { communication protocols with cost ≤ r }.

Two inputs or distributions are indistinguishable if no economical protocol separates them. Certificates include fooling sets, rank, discrepancy, rectangle bounds, information complexity, and corruption bounds. The certificate type is separative and informational.

Communication complexity is a hub of transfer. Many lower bounds in other models are obtained by showing that, if an economical representation existed in model M, then an economical protocol would exist for a known hard communication problem. In this formalism, this is a filtered interpretation.

14.11 Query Complexity

The objects are functions or properties on inputs accessible through queries. The constructions are query algorithms, decision trees, randomized query algorithms, and quantum query algorithms. The budget is the number of queries.

Separatively, the tests are algorithms that query at most r positions. Two inputs are indistinguishable at budget r if every r-query algorithm has the same observable behavior on both.

Certificates include the adversary method, polynomial method, sensitivity, block sensitivity, certificate complexity, and distributional indistinguishability. The certificate type is separative, informational, and sometimes algebraic.

Query complexity often transfers lower bounds to communication complexity by composition with a gadget. In this formalism, that is a filtered interpretation with controlled overhead.

14.12 Descriptive Complexity and Finite Logic

The objects are finite structures, graphs, orders, databases, and finite models. The constructions are logical formulas. The budgets are quantifier rank, number of variables, depth, alternation, logical fragment, and order of the logic.

A property P has minimal logical complexity equal to the smallest formula budget that defines it. Separatively:

T_r = { formulas of budget ≤ r }.

Two structures are indistinguishable at budget r if they satisfy the same formulas of the fragment up to that budget. Ehrenfeucht-Fraïssé games and variants provide indistinguishability certificates. If A ≡_r B and P(A) ≠ P(B), then P is not definable at budget r. The certificate type is separative-logical.

Descriptive complexity is a theory of filtered test spaces where tests are formulas. Inexpressibility is exactly a separative lower bound.

14.13 Model Theory

The objects are structures, models, types, and theories. The tests are formulas. The budgets are logical fragments, quantifier rank, formula complexity, stability, depth, and partial types.

Two elements or structures are indistinguishable with respect to a family of formulas if they realize the same bounded types. In the formalism, x ≡_r y means that no formula of the fragment T_r distinguishes x and y. The certificate type is separative-logical.

Model theory already has a rich theory of types. This formalism does not replace it, but reads it as an advanced theory of filtered indistinguishability.

14.14 Learning Theory

The objects are distributions, target functions, classifiers, and hypotheses. The tests are classifiers or hypotheses in a class H. The budgets include VC dimension, number of parameters, norm, Rademacher complexity, depth, regularization, and sample size.

A hypothesis class with budget r induces:

T_r = H_≤r.

Two distributions or target functions are indistinguishable if no hypothesis within the budget separates them significantly. The separative complexity measures how much a model class can distinguish patterns or labels.

Certificates include VC lower bounds, sample complexity, shattering, statistical indistinguishability, and minimax lower bounds. The certificate type is separative, statistical, and entropic. MDL measures the descriptive cost of the model, while learning theory also measures the separative and generalization power of the class.

14.15 Information Theory

The objects are messages, sources, channels, and distributions. The constructions are codes, protocols, compressors, and channels. The budgets are bits, entropy, mutual information, and channel capacity.

A channel with limited capacity cannot transfer more information than allowed. In the formalism, messages are objects, codes are constructions, decoders are tests, and channel capacity is a separative or informational budget.

The certificate is: if the required distinction among messages exceeds the capacity of the channel, the transfer is impossible. The certificate type is entropic and separative.

14.16 Algebraic Complexity

The objects are polynomials, tensors, and algebraic functions. The constructions are arithmetic circuits, formulas, determinants, permanents, and tensor decompositions. The budgets are size, depth, degree, tensor rank, border rank, and number of multiplications.

A filtered space of polynomials P_≤r contains the polynomials constructible with algebraic cost at most r. Tests can be algebraic invariants that every small construction bounds.

Certificates include rank, border rank, dimension of secant varieties, partial derivatives, geometric invariants, support, and Newton polytopes. The certificate type is algebraic, separative, and dimensional.

Many algebraic lower bounds follow the schema:

I(small constructions) ≤ B, but I(target) > B.

Thus the invariant I is a test or separative measure.

14.17 Geometric Complexity Theory

The objects are orbits, varieties, representations, and polynomials such as permanent and determinant. The constructions are degenerations, orbit closures, and group representations. The budgets are dimension, degree, representational complexity, and inclusion of orbits.

A lower bound becomes the statement that the target does not belong to the filtered closure of economical constructions. The tests are functions or invariants that separate one variety from another. The certificate type is algebraic-geometric, separative, and representational.

14.18 Controlled Algebra

The objects are modules, complexes, algebras, and spaces filtered over metric spaces. The constructions are controlled morphisms. The budgets are propagation, metric control, support, and radius.

Controlled algebra is already a theory of filtered morphisms. In this language:

Hom_≤r(X, Y)

consists of morphisms with propagation at most r. It provides an existing categorical infrastructure for reasoning about composition, filtrations, and control.

The difference is that controlled algebra is often oriented toward K-theory, coarse geometry, and topology, while complexity-budget theory is oriented toward lower bounds, expressiveness, negative certificates, and transfer of impossibility.

14.19 Category Theory and Graded Monads

The objects are types, computations, effects, and resources. The constructions are morphisms, functors, monads, graded monads, and enriched categories. The budgets are grades, effects, costs, and resources.

A filtered category has:

Hom_≤r(X, Y).

Composition satisfies:

Hom_≤r(X, Y) ∘ Hom_≤s(Y, Z) ⊆ Hom_≤r⋆s(X, Z).

This is close to an abstract theory of resources. The filtered category organizes constructions; the filtered test space organizes observations. Together they give a theory of constructibility, observability, transfer, and indistinguishability.

14.20 Dynamical Systems

The objects are states, orbits, configurations, and invariant measures. The constructions are iterations:

x_{n+1} = F(x_n).

The budgets are time, energy, entropy, symbolic complexity, and orbital growth. A controlled dynamic may satisfy:

C(F(x)) ≤ aC(x) + b.

Iterating:

C(F^n(x)) ≤ a^n C(x) + b(1 + a + ... + a^{n-1}).

Separatively, tests can be observables available within bounded time or resolution. Two states are indistinguishable at budget r if no observation of cost r separates them. Certificates include topological entropy, orbital growth, orbit separation, symbolic complexity, and impossibility of dynamic compression. The certificate type is entropic, separative, and metric.

14.21 Enumerative Combinatorics and Counting Lower Bounds

The objects are graphs, hypergraphs, permutations, finite structures, and words. The constructions are families described by few parameters, grammars, circuits, formulas, and generators. The budgets are number of parameters, description length, and representation size.

If:

|constructible within r| ≪ |target objects within r|,

then almost all target objects are not constructible. This is the entropic obstruction theorem. The certificate type is entropic.

Its limitation is that a counting argument alone often does not identify explicit hard objects. The incompressibility method can individualize the argument.

14.22 Formal Grammars

The objects are languages, words, and derivation trees. The constructions are regular grammars, context-free grammars, unambiguous grammars, and weighted grammars. The budgets are number of nonterminals, rules, ambiguity, and grammar size.

An economical grammar can induce an economical test or protocol for distinguishing certain structures. If a lower bound in communication complexity rules out such a protocol, then it also rules out the economical grammar. The certificate type is separative, often transferred from communication complexity.

14.23 Data Structures

The objects are query problems over data. The constructions are data structures, storage schemes, and query algorithms. The budgets are space, query time, number of probed cells, and word size.

A data structure with efficient queries induces limited tests on inputs. Lower bounds are obtained by showing that certain distinctions require more cells, more bits, or more time. The certificate type is separative, informational, and communication-like.

14.24 Database Theory and Factorized Representations

The objects are relations, queries, joins, and databases. The constructions are factorized representations, relational circuits, and provenance polynomials. The budgets are representation size, width, factorization, and treewidth.

A compact representation induces limits on the distinctions or combinations representable. Lower bounds can be entropic or separative. The certificate type is entropic, separative, and structural.

15. The Four Main Forms of Obstruction

In light of the new formalism, negative certificates are organized as follows.

15.1 Pointwise Obstruction

C_T(y) > Φ(C_S(s), C_C(F)).

Meaning: the target has intrinsic complexity too high to be produced from that source through that construction. Typical areas include height theory, algebraic complexity, norms, degree, energy, and geometric invariants.

15.2 Entropic Obstruction

|Reach_≤r| ≪ |T_≤r|.

Meaning: the constructible class is too small to generically cover the target. Typical areas include counting arguments, incompressibility, random structures, parametrizations, generative models, and encodings.

15.3 Separative Obstruction

x ≡_r y but P(x) ≠ P(y).

Meaning: the system does not distinguish two objects that the property must distinguish. Typical areas include automata, logic, communication complexity, query complexity, circuit lower bounds, learning theory, and data structures.

15.4 Compressive Obstruction

economical representation ⇒ encoding shorter than the possible minimum.

Meaning: if the economical construction existed, it would compress an incompressible object. Typical areas include Kolmogorov complexity, the incompressibility method, MDL, random objects, and information theory.

16. The Role of Invariants

Classical invariants can be reinterpreted as tests or budget measures. An invariant:

I : X -> M

can serve as a test if it distinguishes objects. It can serve as a complexity if it measures size. It can serve as a certificate if it is monotone or controlled with respect to constructions.

The general form is:

I(F(x)) ≤ Ψ(I(x), C(F)).

If:

I(y) > Ψ(I(x), C(F)),

then y ≠ F(x). Thus invariants become tools for proving that certain regions of the space are not reachable.

Examples include rank, degree, dimension, height, entropy, cohomology, homology, fundamental group, VC dimension, communication matrix rank, number of Myhill-Nerode classes, proof width, polynomial degree, and tensor rank. In the separative formalism, an invariant is often a compressed family of tests.

17. Complexity and Probability

Given a complexity:

C : X -> R_≥0,

one can associate a partition function:

Z_C(s) = Σ_{x∈X} e^{-sC(x)}.

If it converges, we obtain a measure:

μ_s(x) = e^{-sC(x)} / Z_C(s).

This formula unifies algorithmic probability, Gibbs distributions, Occam-type Bayesian priors, MDL penalties, measures on rationals by height, zeta functions, and filtered random models.

The critical convergence point is linked to growth entropy:

β_X = limsup_{R->∞} log |X_≤R| / R.

If |X_≤R| ≈ e^{β_X R}, then convergence is expected for s > β_X. In the language of the theory: complexity induces a probabilistic geometry; entropy measures the volume of balls; exponential measures concentrate mass on simple objects.

18. Entropic Obstruction Theorem

Reformulate the entropic result in the general language. Let (T, C_T) be a filtered space with:

T_≤R = { t : C_T(t) ≤ R }.

Suppose:

|T_≤R| ≈ e^{β_T R}.

Let G be a constructive system such that:

the number of constructions of length at most n is at most Ae^{ηn};
every construction of length n produces an object of complexity at most an + b.

Then the constructible objects of complexity at most R are at most:

A' e^{(η/a)R}.

If:

η/a < β_T,

then the density of constructible objects tends to zero:

|Constructible ∩ T_≤R| / |T_≤R| -> 0.

More precisely, it tends to zero exponentially. This theorem says: if the entropy of the target exceeds the generative capacity of the grammar or construction, almost all targets are not constructible. In the new framework, this is the entropic counterpart of the separative spectrum.

19. Lower-Bound Transfer Theorem

The most important separative result is:

I : X -> Y filtered with overhead σ, P = Q ∘ I ⇒ δ_X(P) ≤ σ(δ_Y(Q)).

Contrapositively:

δ_X(P) > σ(r) ⇒ δ_Y(Q) > r.

This formalizes a standard and powerful strategy:

we want to prove that Q is hard in Y;
we construct an interpretation I : X -> Y;
we show that every economical test in Y induces an economical test in X;
we already know that P = Q ∘ I is hard in X;
we conclude that Q is hard in Y.

This is the core of lower-bound transfer.

20. Translating Classical Results into the Formalism

Here are some schematic translations.

20.1 Myhill-Nerode

Classically, a regular language has a minimal DFA whose number of states equals the number of Myhill-Nerode classes. In the formalism, X = Σ*, the tests are contexts, suffixes, or automata, and:

u ≡_L v ⇔ ∀w, uw ∈ L ⇔ vw ∈ L.

The number of classes is the separative spectrum necessary for L. An automaton with n states induces at most n classes. Therefore:

# Myhill-Nerode classes > n ⇒ no DFA with n states.

The type is purely separative.

20.2 Ehrenfeucht-Fraïssé Games

Classically, Duplicator wins an r-round game between structures A and B if no formula of quantifier rank r distinguishes them. In the formalism, X is a space of finite structures, T_r is the set of formulas of quantifier rank at most r, and A ≡_r B means same theory up to budget r.

If a property P separates A and B, then P is not definable at budget r. The type is separative-logical.

20.3 Communication Lower Bounds

Classically, a protocol with b bits induces at most 2^b transcripts and a certain partition into rectangles. In the formalism, T_b is the set of protocols of cost at most b. Two inputs are indistinguishable if all protocols of cost b treat them in the same way.

A lower bound constructs a family of inputs requiring more distinctions than b bits allow. The type is separative and informational.

20.4 Query Lower Bounds

Classically, an algorithm with few queries does not see enough coordinates. In the formalism, T_q is the set of algorithms with at most q queries, and x ≡_q y if no q-query algorithm distinguishes them. If P(x) ≠ P(y), then q queries are not enough. The type is separative.

20.5 Circuit Lower Bounds via Rank

Classically, every small circuit induces a matrix or object of low rank; the target has high rank. In the formalism, an invariant or test I satisfies I(F) ≤ B for every small construction, while I(T) > B for the target. Therefore the target is not constructible. The type is algebraic-separative.

20.6 Proof Complexity Lower Bounds

Classically, every short refutation has a certain bounded property; the formula requires a property beyond the bound. In the formalism, T_r is the set of proofs or refutations of length at most r. A lower bound shows that no certificate in level r separates the formula from falsity or unsatisfiability. Invariants such as width, degree, rank, or progress measures are indirect tests. The type is certificative-separative.

20.7 Height Bounds

Classically, a rational map controls height growth. In the formalism, objects are filtered by height and constructions are controlled:

h(f(P)) ≤ d h(P) + O(1).

If a target has height above the budget, it is not in the image. The type is pointwise.

20.8 Kolmogorov Incompressibility

Classically, most strings of length n have complexity almost n. In the formalism:

X_≤r = { x : K(x) ≤ r }, |X_≤r| ≤ 2^r.

A construction with a short description produces only compressible objects. An incompressible object cannot be produced. The type is compressive and entropic.

20.9 MDL

Classically, MDL chooses the model minimizing the description of the model plus the description of the data given the model. In the formalism, models are constructions, the residual is the unexplained part, and the total budget is:

C(M) + C(D | M).

The type is descriptive optimization.

21. The Complete Common Formalism

The complete theory can be organized along three axes.

Axis A: Filtered Objects

(X, C_X)

These measure intrinsic complexity.

Axis B: Filtered Constructions

Hom_≤r(X, Y)

These measure productive or constructive complexity.

Axis C: Filtered Tests

T_r ⊆ A^X

These measure separative or observational complexity.

These axes interact. A construction F : X -> Y has a growth budget:

C_Y(F(x)) ≤ Φ(C_X(x), C(F)).

A test τ : Y -> A pulled back along F gives τ ∘ F : X -> A. If:

τ ∈ T^Y_r ⇒ τ ∘ F ∈ T^X_{σ(r)},

then F is a filtered interpretation for tests. Thus the same map can be studied from two sides: as a construction, namely how much it increases object complexity; and as an interpretation, namely how it transfers tests and indistinguishability. This duality is central.

22. Construction-Test Duality

A construction:

F : X -> Y

sends objects forward:

x -> F(x).

A test on Y:

τ : Y -> A

pulls back to a test on X:

τ ∘ F : X -> A.

Therefore constructions transfer objects forward, while tests transfer observations backward. Lower bounds often work backward: if there were an economical construction in Y, then pulling it back would give an economical test in X, but this is impossible.

The theory should therefore be formulated in a two-sided way: forward, as growth of object complexity; and backward, as pullback of tests and lower bounds.

23. Complexity Transfer Problems

A general problem has the structure:

P = (S, T, C, Tests, C_S, C_T, C_C)

where S is the source, T is the target, C is a class of constructions, Tests is a class of tests on the target, C_S measures inputs, C_T measures targets, and C_C measures constructions.

A solution consists of:

F(s) = t.

A lower bound can prove impossibility in various ways:

the target is too high: C_T(t) > Φ(C_S(s), C_C(F));
the reachable class is too small: |Reach_≤r| ≪ |T_≤r|;
the available tests do not distinguish enough: x ≡_r y, P(x) ≠ P(y);
an economical representation would compress too much: K(x) > B;
a short proof cannot certify: C_proof(φ) > B.

These are different forms of the same philosophy.

24. Fundamental Results of the Theory

The fundamental results so far are the following.

Pointwise budget principle. If every admissible construction satisfies C_T(F(s)) ≤ Φ(C_S(s), C(F)), then C_T(t) > Φ(r, c) rules out every representation t = F(s) with C_S(s) ≤ r and C(F) ≤ c.
Finiteness from budget. If (T, C_T) has finite balls and every counterexample must have complexity ≤ B, then the possible counterexamples are finite.
Entropic obstruction. If constructible objects grow with entropy lower than the target, almost all targets are not constructible.
Filtered test spaces. Every increasing family of tests induces indistinguishability x ≡_r y.
Separative normal form. A property P is not decidable at budget r if and only if there exist x ≡_r y with P(x) ≠ P(y).
Filtered interpretations. A map I : X -> Y is filtered if τ ∈ T^Y_r ⇒ τ ∘ I ∈ T^X_{σ(r)}.
Lower-bound transfer. If I is filtered and P = Q ∘ I, then δ_X(P) ≤ σ(δ_Y(Q)), and hence δ_X(P) > σ(r) ⇒ δ_Y(Q) > r.
Monotonicity of the separative spectrum. N_Y(I(X), r) ≤ N_X(X, σ(r)).
Composition of overheads. If X --I--> Y --J--> Z have overheads σ and ρ, then J ∘ I has overhead σ ∘ ρ.

25. Where the Possible Originality Lies

The theory is not original in its individual ingredients. Many have existed for decades. The possible originality lies in the combination:

placing objects, constructions, and tests in a single filtered scheme;
clearly distinguishing intrinsic, constructive, certificative, and separative complexity;
treating lower bounds as typed negative certificates;
giving the separative formalism a central role;
viewing automata, communication, queries, logic, and proofs as filtered test spaces;
formalizing lower-bound transfers as filtered interpretations;
using separative spectrum and separative deficit as common invariants;
building a modular theory of overhead composition.

The most promising point for publishable results is an abstract calculus of transferable separative lower bounds. It is not enough to say that analogies exist. One must show that known results in different areas become corollaries of a single theorem, and then use the theorem to obtain at least one new application.

26. Updated Research Program

The new roadmap is as follows.

Phase 1: Formalize Filtered Test Spaces

Precise definitions: filtered test space, observational equivalence, separative complexity, separative spectrum, separative deficit, filtered interpretation, overhead, and composition.

Phase 2: Build the Dictionary

For each area, identify:

(X, A, T_r, ≡_r, δ, N).

The dictionary should list objects, tests, budgets, equivalence, lower bound, certificate, and interpretations toward other areas.

Phase 3: Prove the General Theorems

Prove the separative normal form, lower-bound transfer, spectrum monotonicity, overhead composition, entropy/separation comparison, pullback of certificates, pushforward of indistinguishability, and comparison between filtered tests.

Phase 4: Find a New Application

Search for a model M such that:

economical test in M ⇒ economical test in communication/query/logic.

Then use a known lower bound in the source to obtain a new lower bound in M. Candidates include constrained transducers, weighted grammars, nonstandard automata, database factorizations, encodings of finite structures, discrete generative models, compressed representations of relations, relational circuits, finite logics with mixed resources, and restricted proof systems.

Phase 5: Integrate Intrinsic Complexity and Measure

After the separative formalism, reintegrate height, complexity zeta functions, Gibbs measures, growth entropy, p-adic complexity, Kolmogorov complexity, and MDL. The goal is a complete theory, not only a separative one.

27. Possible Article Form

Possible titles:

Filtered Separation Spaces and Complexity-Budget Obstructions
A Unified Filtration Framework for Lower-Bound Transfer
Separation Spectra and the Transfer of Resource Lower Bounds

Possible structure:

introduction: lower bounds as failures of distinction; motivation from automata, communication, logic, and queries; philosophy of complexity budgets;
filtered test spaces: definitions, indistinguishability, and separative complexity;
negative certificates: normal form, indistinguishable pairs, and separative spectra;
filtered interpretations: definition, overhead, and pullback of tests;
theorems: lower-bound transfer, spectrum monotonicity, and overhead composition;
dictionary: automata, communication complexity, query complexity, descriptive complexity, proof complexity, and circuit complexity;
applications: one or more new applications, or substantial simplifications of known results;
connection with the general theory: filtered objects, filtered constructions, complexity measures, entropy, Kolmogorov, heights, and MDL;
conclusion and future program.

28. Synthetic Version of the Formalism

The theory can be summarized by this chain. A filtered test space is:

X = (X, A, T_r).

It induces:

x ≡_r y ⇔ ∀τ ∈ T_r, τ(x) = τ(y).

A property P : X -> B has separative complexity:

δ(P) = inf { r : P constant on ≡_r }.

A lower bound is a pair:

x ≡_r y, P(x) ≠ P(y).

A filtered interpretation:

I : X -> Y

satisfies:

τ ∈ T^Y_r ⇒ τ ∘ I ∈ T^X_{σ(r)}.

Therefore:

δ_X(Q ∘ I) ≤ σ(δ_Y(Q)).

And hence:

δ_X(Q ∘ I) > σ(r) ⇒ δ_Y(Q) > r.

This is the engine of transfer.

29. Updated Final Manifesto

Complexity-budget theory begins from the idea that every construction has limited capacity. But the most useful form of this idea is not only to measure how complex an object is; it is to measure which distinctions a system can make within a budget.

A mathematical, computational, or logical system is not only a producer of objects. It is also an observer. It has tests, formulas, protocols, automata, proofs, circuits, queries, and experiments. Every class of tests induces an indistinguishability relation. Every lower bound says that the system does not distinguish enough.

The central principle becomes:

a problem is hard when every economical observer identifies objects that the problem must separate.

From this follows a general theory:

objects are filtered by complexity;
constructions are filtered by cost;
tests are filtered by observational power;
properties have separative complexity;
lower bounds are indistinguishability certificates;
reductions are filtered interpretations;
overheads compose;
separative spectra measure capacity;
separative deficits measure insufficiency;
complexity measures transform filtrations into probabilities;
entropy measures growth of balls;
existing theories become instances of the same grammar.

The initial motto was:

every construction has a complexity budget; whatever exceeds that budget cannot have been constructed in that way.

The updated motto is:

every model has a distinction budget; whatever requires more distinctions than are available cannot be decided, expressed, represented, proved, or constructed in that model.

This is the most fertile form of the theory.

30. Conclusion

The general theory rewritten with the new formalism does not claim to replace existing theories. On the contrary, it uses them as model cases.

The thesis is:

many areas of mathematics and theoretical computer science study, in different languages, the same phenomenon: the failure of constructions, descriptions, proofs, or decisions under limited budgets.

The new formalism proposes to represent this phenomenon through:

filtered spaces of objects + budgeted morphisms + filtered test spaces + indistinguishability certificates.

The most promising part is the separative theory:

x ≡_r y but P(x) ≠ P(y).

From this single form emerge automata, finite logic, communication complexity, query complexity, proof complexity, circuit lower bounds, and learning theory.

The most important part for producing new results is the transfer theorem:

δ_X(Q ∘ I) > σ(r) ⇒ δ_Y(Q) > r.

This makes it possible to transform known lower bounds into new lower bounds, provided one finds a suitable filtered interpretation.

The future program is therefore clear:

rigorously formalize the calculus of filtered test spaces;
systematically translate known theories;
classify negative certificates;
find new filtered interpretations between models;
transfer lower bounds;
obtain at least one concrete new application.

Only then will the theory pass from unifying philosophy to publishable mathematical contribution.