Presentation Theory I: Description Systems, Costs, and Observable Fibres

1 Guiding idea

Many mathematical objects come with natural ways of being presented: by coordinates, generators and relations, equations, circuits, words, modules, kernels, local models, proof data, or finite approximations.

A presentation theory studies four related questions.

First, which descriptions are allowed?

Second, which observations are allowed?

Third, what fibres are created by realization maps and by observables?

Fourth, how do costs on descriptions or observations make these questions quantitative?

The basic principle is:

Conversely, an observation incompatible with every low-cost object proves that the object lies outside the corresponding bounded presentation class.

Complexity is assigned relative to a specified presentation system.

Presentation, observation, and cost play distinct roles. A description produces or specifies an object. An observable extracts information from an object. A cost imposes a budget on descriptions or observations.

This gives three complementary layers: presentation complexity for objects, observable complexity for tests, and fibre structure for the information forgotten by a chosen family of observables. In many examples, all observables of bounded arity, degree, rank, or test size factor through a smaller structural statistic.

2 Object classes

An object class is a class

of mathematical objects.

Depending on the application, \(\mathcal X\) may be a set of objects, a set of isomorphism classes, or a category/groupoid whose objects are studied up to an equivalence relation.

We write

for the chosen equivalence relation on \(\mathcal X\). If \(\mathcal X\) is already a set of equivalence classes, then \(\equiv_\mathcal X\) is equality. In categorical or groupoid settings it may be isomorphism or another declared equivalence.

Maps between object classes are assumed to respect the declared equivalence relations.

Examples include:

The first step is to choose what counts as the object class and what equivalence relation is being imposed.

This choice is not cosmetic. A finite group considered as an abstract group, a marked group, a permutation group, a matrix group, or a group equipped with structural data may lead to different presentation systems and different costs.

3 Resource scales

A resource scale is a preordered set

whose elements represent possible resource bounds.

The simplest case is

with the usual order.

More generally, \(B\) may be a multi-resource scale such as

with coordinatewise order.

This allows one to record several resources at once, such as size, depth, height, degree, arity, number of generators, number of relations, or total relation length.

A cost bound is an element

Informally, \(b\) is the available budget.

Costs may be scalar or multi-resource. In many applications the bounded part is defined by several simultaneous constraints.

4 Presentation systems

A presentation system for an object class \(\mathcal X\) consists of a triple

where:

is a class of descriptions,

is a realization map, and

is a cost function.

An element

is a description. The object realized by \(d\) is

The cost of the description is

The presentation system tells us which descriptions are allowed and how expensive they are.

The same object class may admit many different presentation systems. This plurality is central to the theory.

For example, finite groups may be presented by generators and relations, multiplication tables, permutation actions, matrix representations, semidirect-product data, module data, commutator tensors, normal covers, or finite local models.

Different presentation systems measure different mathematical resources.

Throughout, when an object class is studied up to \(\equiv_\mathcal X\), the notation

means \(\rho(d)\equiv_\mathcal X x\). This convention keeps the notation light while allowing the same formalism to cover equality of functions, isomorphism of groups, and equivalence of structured objects.

5 Admissibility and naturality

The formal definition of a presentation system is intentionally broad. In applications it is paired with admissibility conditions appropriate to the mathematical problem.

Common conditions include:

1. the realization map is effectively computable, verifiable, or mathematically canonical;

2. bounded description classes are finite, compact, constructible, recursively enumerable, or otherwise controllable;

3. the cost is monotone under natural enlargements of descriptions;

4. equivalent descriptions of the same object have controlled effects on cost;

5. natural operations in the domain admit cost-controlled transfers when such transfers are used;

6. low-cost descriptions do not encode target objects by ad hoc labels unless such labels are part of the declared presentation system;

7. observables used for lower bounds are canonical, or their selection and evaluation costs are explicitly charged.

These conditions keep the formalism aligned with the intended mathematical presentation problem. They also make clear that the generality of the definition is not a license to choose arbitrary encodings after the target object is known.

The corresponding methodological convention is:

6 Effectively finitary presentation systems

In effective applications one often works with presentation systems whose bounded parts can actually be searched.

A presentation system

is effectively finitary if, for every cost bound \(b\),

is finite and effectively enumerable, and the relevant realization comparisons

are decidable for the bounded descriptions under consideration.

This condition is deliberately modest. It says that bounded search is meaningful once the bound is fixed. It does not say that the unbounded realization problem, equivalence problem, or fibre recognition problem is decidable.

Proposition 6.1 (Bounded membership in effectively finitary systems).

Let \(\Gamma\) be effectively finitary. In any representation in which the comparisons \(\rho(d)\equiv_\mathcal X x\) are decidable for \(d\in\mathcal D^{\leq b}\), the predicate

\[ x\in\mathcal X_\Gamma^{\leq b} \]

is decidable.

7 Filtered effective presentation systems

The previous notion of effective finitarity says that bounded search is meaningful once a bound is fixed. A sharper computability model records how equality of represented objects is witnessed by finite stages.

Fix a finite alphabet \(\Sigma\). A filtered effective presentation system is a triple

such that:

1. \(D\subseteq\Sigma^*\) is decidable;

2. \(\kappa:D\to\mathbb N\) is computable and effectively proper, meaning that

   \[ D_{\leq b}:=\{d\in D:\kappa(d)\leq b\} \]

   is finite and computable uniformly in \(b\);

3. each relation \(E_t\subseteq D\times D\) is decidable uniformly in \(t\);

4. \(E_t\subseteq E_{t+1}\) for all \(t\);

5. the union

   \[ E=\bigcup_{t\in\mathbb N}E_t \]

   is an equivalence relation on \(D\).

The represented object class is the quotient \(D/E\). The realization map is the quotient map \(d\mapsto[d]\).

The bounded-presentation problem is

The minimal presentation cost of the object represented by \(d\) is

For a positive instance \((d,b)\in P_\Gamma\), define its presentation width by

The global bounded-presentation width profile is

with value \(0\) if the set is empty.

Similarly, define the equivalence problem

For \(d\,E\,e\), define

and define the bridge-width profile

again with value \(0\) if the set is empty.

Theorem 7.1 (Degree conservation for bounded presentation).

For every filtered effective presentation system,

\[ P_\Gamma\equiv_T C_\Gamma\equiv_T W_\Gamma. \]

Theorem 7.2 (Degree conservation for equivalence).

For every filtered effective presentation system,

\[ EQ_\Gamma\equiv_T B_\Gamma. \]

Corollary 7.3 (Computable majorants).

The following are equivalent:

\[ P_\Gamma\text{ is decidable},\qquad C_\Gamma\text{ is computable},\qquad W_\Gamma\text{ has a computable majorant}. \]

Likewise,

\[ EQ_\Gamma\text{ is decidable} \quad\Longleftrightarrow\quad B_\Gamma\text{ has a computable majorant}. \]

Proposition 7.4 (Cofinal filtrations).

Let \((E_t)\) and \((F_s)\) be two decidable increasing filtrations of the same equivalence relation \(E\) on \(D\). Suppose they are computably cofinal: there are computable functions \(\alpha,\beta:\mathbb N\to\mathbb N\) such that

\[ E_t\subseteq F_{\alpha(t)},\qquad F_s\subseteq E_{\beta(s)}. \]

Then the corresponding \(W\)-profiles and \(B\)-profiles majorize each other up to computable change of variable. In particular, the existence of a computable majorant is independent of replacing a filtration by a computably cofinal one.

Proposition 7.5 (Sharpness of the two degrees).

Every c.e. Turing degree occurs as \(\deg_T(P_\Gamma)\) for some filtered effective presentation system. More generally, for every pair of c.e. degrees \(\mathbf a\leq\mathbf b\), there is a filtered effective presentation system with

\[ \deg_T(P_\Gamma)=\mathbf a, \qquad \deg_T(EQ_\Gamma)=\mathbf b. \]

8 Bounded descriptions and bounded objects

For a cost bound \(b\in B\), define the bounded description class

The corresponding bounded part of \(\mathcal X\) is

Thus

is the class of objects admitting at least one \(\Gamma\)-description of cost at most \(b\).

Equivalently, an object \(x\in\mathcal X\) is \(b\)-presentable if

If \(b\leq b'\), then

Hence the bounded parts form a filtration of \(\mathcal X\):

This is the bounded-presentation filtration associated with \(\Gamma\).

The filtration is often the primary object. A single numerical complexity value may be less informative than the entire family of bounded parts.

9 Presentation complexity

When the resource scale admits a meaningful notion of infimum or minimum, one may define the presentation complexity of an object \(x\in\mathcal X\) by

In discrete settings this is often a minimum:

Thus \(C_\Gamma(x)\) is the cost of the cheapest allowed description of \(x\).

The bounded part can then be written as

whenever the minimum is attained or the inequality is interpreted as the existence of a description of cost at most \(b\).

The primary object is often the full filtration

with \(C_\Gamma(x)\) as its pointwise numerical summary when such a summary is available.

10 Basic upper bound principle

If \(d\in\mathcal D\) is a description of \(x\), meaning

then

Thus every explicit description gives an upper bound on presentation complexity.

This is the constructive half of the theory.

11 Presentation fibres

The realization map

is not only a way to assign objects to descriptions. It is a map with fibres.

For \(x\in\mathcal X\), define the presentation fibre

Thus \(\mathfrak F_\rho(x)\) is the class of all descriptions realizing \(x\).

The numerical invariant \(C_\Gamma(x)\) sees only the cheapest point in this fibre:

The full fibre may contain many other descriptions, with their own logic, computability, and geometry. A small value of \(C_\Gamma(x)\) says that the fibre meets a low-cost region of \(\mathcal D\); it does not by itself determine how difficult the fibre is to recognize, normalize, or navigate.

For a cost bound \(b\), the truncated fibre is

Studying the family

refines the study of \(C_\Gamma(x)\). It records how the descriptions of a fixed object populate the bounded parts of the description space.

12 Fibre membership and verification

In effective settings, assume the description class is encoded by finite words and let

be a coding length. For a fixed object \(x\), the fibre recognition problem is the decision problem

This problem may be much harder than producing one economical description of \(x\).

A verification relation for the fibre of \(x\) is a decidable relation

such that

The datum \(\pi\) is membership verification data for the statement \(d\in\mathfrak F_\rho(x)\).

Define the minimum verification-data length

for \(d\in\mathfrak F_\rho(x)\), and the bounded verification-length profile

with the usual convention that the maximum over an empty set is \(0\).

This profile measures the length of the shortest membership verification data needed to verify all fibre elements of coding length at most \(n\).

13 Move systems on fibres

A move system on descriptions is a relation

on \(\mathcal D\), usually chosen so that moves preserve realization:

Then every presentation fibre becomes a graph. Its vertices are the descriptions in \(\mathfrak F_\rho(x)\), and its edges are the elementary moves. In this note, bridge profiles use symmetric move systems; directed move systems can be treated by choosing an orientation convention for paths.

Let

be the shortest path length from \(d\) to \(e\), with value \(\infty\) if no path exists.

After fixing a base description \(d_x\in\mathfrak F_\rho(x)\), define the bridge profile

This measures how hard it is to return bounded descriptions of \(x\) to a chosen base description using the allowed moves.

A complementary invariant is the packing profile

The bridge profile measures long normalization paths; the packing profile measures many mutually distant descriptions. Diameter and entropy-type quantities can be recovered from these by taking pairwise suprema or logarithms of packing numbers.

14 Running example: group presentations

Finite presentations of groups give a useful model for the preceding definitions. Descriptions are finite presentations

and the realization map sends such a presentation to the group

viewed up to isomorphism. A natural cost records quantities such as

The presentation fibre of a group \(G\) is the class of all finite presentations realizing a group isomorphic to \(G\). Tietze transformations form a natural reversible move system on this fibre, and the associated bridge profile measures how hard it is to connect a bounded presentation of \(G\) to a chosen base presentation.

This example also shows why presentation and observation must be kept separate. Words used as relators are part of a description and contribute to presentation cost. Words used as word maps, word equations, or counting tests are observables and contribute to observation cost.

15 Cost-controlled maps

Let

be a presentation system for \(\mathcal X\), and let

be a presentation system for \(\mathcal Y\).

Let

be a map of object classes.

A description-level transfer for \(F\) is a map

such that

for every \(d\in\mathcal D_\mathcal X\).

The transfer is cost-controlled with monotone overhead \(f:B_\mathcal X\to B_\mathcal Y\) if

for every \(d\in\mathcal D_\mathcal X\).

The overhead function \(f\) is part of the declared transfer data. It need not be optimal, but it must be monotone and compatible with the chosen source and target resource scales. In effective settings one usually requires \(f\) to be computable; in quantitative complexity settings one may restrict to linear, polynomial, or primitive recursive overheads.

In that case,

When presentation complexities are defined and the minima or infima are compatible with the overhead, this gives

Thus cost-controlled transfers formalize the idea that natural operations transport low-cost descriptions to low-cost descriptions.

16 Cost-controlled operations

More generally, let

be an (n)-ary operation.

A description-level transfer for \(F\) is a map

such that

It is cost-controlled with monotone overhead \(f\) if

Then

whenever the corresponding presentation complexities are defined.

This is the basic form of a cost calculus.

Examples include products, quotients, extensions, tensor products, composition of maps, base change, blow-ups, reductions modulo primes, and passage to associated graded or local models.

17 Simulation between presentation systems

Let

and

be presentation systems for the same object class \(\mathcal X\).

A translation from \(\Gamma\) to \(\Delta\) with monotone overhead \(f\) is a map

such that

and

Then

When numerical presentation complexity is defined,

Thus \(\Delta\) simulates \(\Gamma\) up to monotone overhead \(f\).

If there are translations in both directions with controlled overheads, then the two presentation systems are equivalent up to the corresponding resource distortion.

Separations between presentation systems arise when a family (\(x_n\)) has low complexity in one system and high complexity in another.

18 Counting and volume

The bounded parts define a counting function whenever cardinality is meaningful:

This is the volume profile of the presentation system.

Counting arguments give generic lower bounds. If a family \(\mathcal S\subseteq\mathcal X\) satisfies

then some \(x\in\mathcal S\) has no description of cost at most \(b\).

This follows from

Similarly, if

then some \(x\in\mathcal S\) has no description of cost at most \(b\).

Thus volume and observable volume provide nonconstructive lower bounds.

Counting arguments prove the existence of complex objects. Additional structure turns those existence statements into explicit examples.

19 Observables

Let \(\mathcal X\) be an object class.

An observable on \(\mathcal X\) is a map

to an observation space \(A\).

The value

is the information about \(x\) seen by the observable.

The observation space \(A\) need not be numerical. It may consist of numbers, vectors, modules, lattices, distributions, ranks, graphs, isomorphism classes, hom-counts, reductions modulo primes, local data, cohomology groups, or other structured data.

A cost measures the expense of a description. An observable measures information extracted from the object.

A numerical invariant may serve as an observable independently of any presentation-cost interpretation.

20 Attainable observations below a bound

Let

be a presentation system for \(\mathcal X\), and let

be an observable.

For a cost bound \(b\in B\), define

This is the set of attainable observations below \(b\).

Equivalently, it is the set of observable values attained by objects admitting a \(\Gamma\)-description of cost at most \(b\).

It may also be called the bounded observable image of \(\mathcal X_\Gamma^{\leq b}\) under \(\omega\).

If \(b\leq b'\), then

Thus

is an increasing profile of observable values.

The phrase attainable observations below \(b\) will be used for this set.

21 Observable profiles

The observable profile of \(\omega\) relative to \(\Gamma\) is the function

It records how the observable sees the bounded-presentation filtration.

Instead of the full set \(\operatorname{Val}_{\Gamma,\omega}(b)\), one may study numerical summaries, such as

or other sizes, ranks, volumes, supports, or distributional statistics.

However, the full observable profile is the primary object.

22 Observable lower-bound principle

Let

If

then

Equivalently, \(x\) has no \(\Gamma\)-description of cost at most \(b\).

When presentation complexity is numerical in an ordered resource scale, this gives

In a totally ordered numerical scale this is the familiar statement \(C_\Gamma(x)>b\).

This is the basic observable lower-bound principle.

23 Cost-observable bounds

In practice, one often works with proved outer bounds for the full set

One proves an inclusion

for some explicit subset

Then

implies

Thus

whenever numerical presentation complexity is defined.

For totally ordered numerical costs this may be written as \(C_\Gamma(x)>b\).

This gives the usual form of a lower-bound criterion:

therefore the object lies outside the bounded presentation class.

24 Observed sizes

Suppose the observation space \(A\) has a size function

to another ordered resource scale (R). Then

is an observed size.

It is a numerical or resource-valued invariant of objects.

An observed size becomes a presentation complexity when it is induced by a presentation system.

The important mathematical question is often to relate observed sizes to presentation complexity. For example, if one proves

then

When numerical presentation complexity is defined,

This covers many familiar lower-bound arguments: degree too large, rank too large, denominator too large, dimension too large, relation lattice too constrained, or observable distribution outside the attainable range.

A useful distinction is:

25 Families of observables

A family of observables on \(\mathcal X\) is a collection

It may be viewed as a joint observable

defined by

The family \(\Omega\) is complete on a subclass \(\mathcal C\subseteq\mathcal X\) if, for all \(x,y\in\mathcal C\),

implies

or, in an isomorphism-based context,

A central problem is to determine which families of observables are complete on which bounded parts or natural subclasses.

26 Observable refinement, coarsening, and products

Observables carry a simple algebra.

If

is an observable and

is a map, then

is a coarsening of \(\omega\).

An observable

refines \(\omega\) if \(\omega=q\circ\eta\) for some map \(q:E\to A\). Refinement can only distinguish at least as much as the original observable.

Given observables

their product observable is

For any presentation system \(\Gamma\) and cost bound \(b\),

The inclusion can be strict. Strictness records correlations among observations imposed by the common bounded presentation class.

27 Indistinguishability fibres

Given an observable

the fibre

is the class of objects indistinguishable by \(\omega\) from the observable value (a).

If

then any method depending on \(\omega\) gives the same output on \(x\) and \(y\).

Thus every observable carries an intrinsic equivalence relation: it distinguishes objects up to its fibres.

For a family of observables \(\Omega\), define

if

for every \(\omega\in\Omega\).

The equivalence classes of \(\sim_\Omega\) are the indistinguishability fibres of \(\Omega\).

Large fibres indicate blindness; small or trivial fibres indicate completeness.

Studying these fibres is essential when observables are used for classification.

28 Reconstruction by observables

A family of observables may do more than distinguish objects. It may reconstruct a structural invariant.

Let

be a structural invariant, such as a module, tensor, rank profile, support profile, lattice, isomorphism class, or moduli parameter.

A family \(\Omega\) reconstructs \(\tau\) on \(\mathcal C\subseteq\mathcal X\) if

for all \(x,y\in\mathcal C\).

Equivalently, \(\tau\) factors through the observational quotient

If \(\tau\) is a complete invariant on \(\mathcal C\), then reconstruction of \(\tau\) implies classification.

Many concrete results have this form:

Thus reconstruction is a central use of observables beyond lower bounds.

29 Costed observables

Observations may also have costs.

A costed observable family on \(\mathcal X\) is a triple

where:

is a class of observables,

is an observation-resource scale, and

assigns an observation cost to each observable.

For an observation bound \(r\in R\), define

Thus \(\Omega^{\leq r}\) is the family of observables available with observation budget \(r\).

Examples of observation costs include arity of a word observable, length of a word, number or order of test groups, degree of a polynomial probe, rank or matrix size of a linear observable, number of evaluations, depth of a logical formula, or quantifier rank.

A declared costed observable family is also an observable scheme: it specifies which tests are allowed before a lower-bound argument begins. If an observable is selected using target-dependent information, then the selection procedure must be canonical or its cost must be included in \(\chi\). Otherwise singleton tests would trivialize distinguishability; such tests are part of the theory only when the declared observable scheme explicitly allows and charges for them.

This distinction is essential:

and

are different resources.

Costed observables form a second resource layer. They measure the complexity of observing, testing, and distinguishing once the object class and presentation systems have been fixed.

30 Distinguishing cost

Let

be a costed observable family.

For two objects \(x,y\in\mathcal X\), define their distinguishing cost by

If no observable in \(\Omega\) distinguishes \(x\) and (y), then

This measures the minimum observation budget needed to tell \(x\) and (y) apart using the allowed observables.

Observable-barrier results have the form:

but

for some larger \(r'\), often with \(r'\) optimal.

Such results show that observation itself has irreducible resource requirements.

31 Normal-form compilers

Many applications depend on a theorem that converts raw descriptions or raw observables into a simpler algebraic normal form.

A normal-form compiler is a result showing that a class of descriptions or observables is equivalent to a more structured class.

For descriptions, a normal-form compiler may have the form:

This says that every low-cost description can be replaced by a normal-form description with controlled overhead.

For observables, a normal-form compiler may have the form

where the raw observable and the normal-form observable determine the same information on the class under study.

Examples include:

Normal-form compilers are often the technical heart of applications. They make bounded objects and attainable observations computable, constrainable, or reconstructive.

32 Complete normal forms as resolutions

A stronger object is a complete normal form for the realization map itself.

Let

be a realization map. A complete normal form for \(\rho\) is a computable map

to an effectively coded space of normal forms with decidable equality, such that

Such an \(N\) is a computable resolution of the equivalence relation induced by \(\rho\). It replaces the problem of deciding whether two descriptions realize the same object by equality of their normal forms.

This is stronger than a cost-controlled compiler into a convenient class of descriptions. A compiler may give good representatives in a bounded range or for a structured subclass. A complete normal form resolves every fibre at once.

Consequently, undecidable fibres obstruct complete computable normalization: if \(d_x\) is a description of \(x\), then a complete normal form decides membership in \(\mathfrak F_\rho(x)\) by testing whether \(N(d)=N(d_x)\).

33 Realization images and algebraic obstructions

A presentation system contains a realization map

Often the key problem is to understand the image of \(\rho\), or the image of a bounded, evaluated, linearized, or reduced version of \(\rho\).

For a bound \(b\), the bounded image is

In algebraic settings, obstructions may arise from failure to lie in an image, cokernel classes, congruence conditions, rank constraints, lattice constraints, support constraints, or coefficient alphabet restrictions.

Thus some lower bounds are not initially about size. They are about realizability.

The general pattern is:

therefore

This is especially important when the presentation system is algebraic, linear, modular, or arithmetic.

34 Pullback and transport of observables

Let

be a map of object classes, and let

be an observable on \(\mathcal Y\).

Then

is an observable on \(\mathcal X\).

This is the pullback observable induced by \(F\) and \(\eta\).

If \(F\) is cost-controlled with monotone overhead \(f\), then

Therefore,

Thus maps between object classes transport observable profiles.

This is useful when (F(x)) is a quotient, reduction, abelianization, associated graded object, local model, or simpler invariant of \(x\).

A transported lower bound has the following form.

If

then

Thus a lower bound for a simpler transported object can imply a lower bound for the original object.

35 Relative and fibre methods

Sometimes an object is studied through a map

The object \(q(x)\) may be a quotient, reduction, base object, abelianization, associated graded object, invariant, or observable component of \(x\).

The fibre

contains the information not determined by \(q(x)\).

One may try to decompose the cost of \(x\) into the cost of the base object \(q(x)\) and the residual cost of specifying \(x\) inside the fibre.

Informally,

This method is useful for extensions, quotients, fibrations, local-to-global problems, model-plus-residual descriptions, cohomological classification, and situations where an observable sees only part of the object.

A full relative theory may introduce conditional presentation systems or relative costs

But the core idea is already present in the basic formalism through fibres of maps and observables.

36 Bounded-counterexample arguments

Let \(P\) be a property of objects in \(\mathcal X\). Define the bad set

Thus proving \(P\) for all objects in \(\mathcal X\) is the same as proving

Let \(\Gamma\) be a presentation system on \(\mathcal X\), and let \(b\) be a cost bound.

A bounded-counterexample principle for \(P\), with respect to \(\Gamma\) and \(b\), is an implication of the form

In words: if \(P\) fails somewhere, then it already fails on a \(\Gamma\)-presentable object of cost at most \(b\).

This principle reduces a universal statement to the bounded part \(\mathcal X_\Gamma^{\leq b}\): any failure of \(P\) has a low-cost counterexample.

To prove \(P\), one combines it with an exclusion result:

Together, the two statements imply

Indeed, if \(B_P\neq\varnothing\), the bounded-counterexample principle gives an element of

contradicting the exclusion result.

The exclusion result may be proved directly, by finite enumeration, by a normal-form theorem, or by observables.

The observable form is the following. Suppose there is an observable

and a subset \(S_b\subseteq A\) such that all objects of cost at most \(b\) have observable value in \(S_b\):

while every bad object has observable value outside \(S_b\):

Then no bad object can lie in the bounded part. If bad objects, if they exist, must lie in the bounded part, then no bad objects exist.

In slogan form:

The argument has a precise form: an independent mathematical reason forces counterexamples into a bounded presentation class, and a second argument excludes counterexamples from that bounded class.

Proposition 36.1 (No universal bounded-counterexample procedure).

There is no algorithm which, given an arbitrary decidable predicate \(P(n)\) on \(\mathbb N\), outputs a finite set \(S\subseteq\mathbb N\) such that

\[ \exists n\ \neg P(n) \quad\Longrightarrow\quad \exists s\in S\ \neg P(s). \]

Thus bounded-counterexample principles require separate mathematical input. They are powerful when available, but they cannot be generated uniformly from decidability alone.

37 Reusable General Theorems

The formalism gives stable proof patterns. The following theorems are abstract templates for height balls, coefficient boxes, word observables, hom-count tests, rank probes, normal forms, proof languages, and bounded counterexample searches.

Theorem 37.1 (Bounded realization-image obstruction).

Let \(\Gamma=(\mathcal D,\rho,\kappa)\) be a presentation system on \(\mathcal X\). Let

\[ \theta:\mathcal X\to T \]

be any invariant or observable, and suppose that for a cost bound \(b\) one has a proved inclusion

\[ \theta(\mathcal X_\Gamma^{\leq b})\subseteq S_b \]

for some subset \(S_b\subseteq T\). Then

\[ \theta(x)\notin S_b \quad\Longrightarrow\quad x\notin\mathcal X_\Gamma^{\leq b}. \]

If numerical presentation complexity is defined, then \(C_\Gamma(x)\nleq b\). In a totally ordered numerical scale this may be written \(C_\Gamma(x)>b\).

This is the common lower-bound pattern behind coefficient constraints, bounded realization images, rank constraints, height denominators, volume estimates, and algebraic support restrictions. The bounded set \(\mathcal X_\Gamma^{\leq b}\) supplies the constrained image \(S_b\).

Theorem 37.2 (Normal-form transfer).

Let \(\Gamma_{\mathrm{raw}}\) and \(\Gamma_{\mathrm{nf}}\) be presentation systems for the same object class \(\mathcal X\), with

\[ \Gamma_{\mathrm{raw}}=(\mathcal D_{\mathrm{raw}},\rho_{\mathrm{raw}},\kappa_{\mathrm{raw}}) \]

and

\[ \Gamma_{\mathrm{nf}}=(\mathcal D_{\mathrm{nf}},\rho_{\mathrm{nf}},\kappa_{\mathrm{nf}}). \]

Suppose there is a compiler

\[ T:\mathcal D_{\mathrm{raw}}\to\mathcal D_{\mathrm{nf}} \]

and a monotone overhead function \(f\) such that

\[ \rho_{\mathrm{nf}}(T(d))=\rho_{\mathrm{raw}}(d) \]

and

\[ \kappa_{\mathrm{nf}}(T(d))\leq f(\kappa_{\mathrm{raw}}(d)) \]

for all \(d\in\mathcal D_{\mathrm{raw}}\). Then

\[ \mathcal X_{\Gamma_{\mathrm{raw}}}^{\leq b} \subseteq \mathcal X_{\Gamma_{\mathrm{nf}}}^{\leq f(b)}. \]

Consequently, every lower bound against \(\Gamma_{\mathrm{nf}}\)-normal forms below \(f(b)\) is also a lower bound against raw presentations below \(b\).

The compiler is the mathematical content: the cost inequality turns a normal form into a transfer theorem.

Theorem 37.3 (Observable factorization).

Let \(\mathfrak O=(\Omega,\chi,R)\) be a costed observable family on \(\mathcal X\), and let \(r\in R\). Let \(\mathcal C\subseteq\mathcal X\), and suppose there is a structural statistic

\[ \tau_r:\mathcal C\to T_r \]

such that every observable of cost at most \(r\) factors through \(\tau_r\) on \(\mathcal C\):

\[ \omega=a_\omega\circ\tau_r \qquad (\omega\in\Omega^{\leq r}) \]

for suitable maps \(a_\omega:T_r\to A_\omega\). Then

\[ \tau_r(x)=\tau_r(y) \quad\Longrightarrow\quad \omega(x)=\omega(y) \quad \text{for all }\omega\in\Omega^{\leq r}. \]

Thus observables of budget \(r\) distinguish objects only up to the fibres of \(\tau_r\).

This theorem is the basic mechanism of observable complexity: bounded observables see the compressed statistic \(\tau_r\).

Corollary 37.4 (Finite-observable blindness).

In the setting of the observable factorization theorem, if one fibre of \(\tau_r\) contains two non-equivalent objects \(x,y\in\mathcal C\), then \(\Omega^{\leq r}\) is not complete on \(\mathcal C\). In particular,

\[ \operatorname{dc}_{\mathfrak O}(x,y)\not\leq r, \]

provided the distinguishing cost is interpreted in the preorder \(R\).

This is the abstract form of many bounded-observable blindness results.

Theorem 37.5 (Reconstruction from factored observables).

Keep the notation of the observable factorization theorem. Suppose, conversely, that \(\tau_r\) is determined by the observables \(\Omega^{\leq r}\): whenever \(x,y\in\mathcal C\) satisfy

\[ \omega(x)=\omega(y) \qquad(\omega\in\Omega^{\leq r}), \]

one has \(\tau_r(x)=\tau_r(y)\). Then the observational quotient of \(\mathcal C\) by \(\Omega^{\leq r}\) is exactly the quotient by the fibres of \(\tau_r\). If \(\tau_r\) is a complete invariant on \(\mathcal C\), then \(\Omega^{\leq r}\) is complete on \(\mathcal C\).

Proposition 37.6 (Cost-sensitive fibration bound).

Let \(q:\mathcal X\to\mathcal Y\) be a structural map. Suppose \(\mathcal Y\) has a presentation system \(\Gamma_\mathcal Y\), and suppose that for every \(y\in\mathcal Y\) there is a relative presentation system \(\Gamma_{\mathrm{rel}}(y)\) for the fibre \(q^{-1}(y)\). Assume objects of \(\mathcal X\) can be assembled from base and relative descriptions with overhead \(A\):

\[ \kappa_\mathcal X(\operatorname{Asm}(e,h)) \leq A(\kappa_\mathcal Y(e),\kappa_{\mathrm{rel}}(h)). \]

Then

\[ C_{\Gamma_\mathcal X}(x) \leq \inf_{e,h} A(\kappa_\mathcal Y(e),\kappa_{\mathrm{rel}}(h)), \]

where the infimum ranges over descriptions \(e\) of \(q(x)\) and relative descriptions \(h\) of \(x\) in the fibre over \(q(x)\).

This proposition is an upper-bound assembly statement. Relative lower bounds arise from converse hypotheses showing that every low-cost description of \(x\) yields low-cost base and fibre data.

Theorem 37.7 (Unbounded verification-length principle).

Let \(S\subseteq\{0,1\}^*\) be recursively enumerable but not decidable. Suppose there is a decidable relation \(R(u,\pi)\) such that

\[ u\in S \quad\Longleftrightarrow\quad \exists \pi\ R(u,\pi). \]

For \(u\in S\), define

\[ m_R(u)=\min\{|\pi|:R(u,\pi)\}, \]

and define

\[ b_R(n)= \max_{\substack{|u|\leq n\\u\in S}} m_R(u), \]

with value \(0\) if the maximum is taken over an empty set. Then \(b_R\) is not bounded above by any total computable function.

The theorem is elementary but important: recursively enumerable membership, once undecidable, forces shortest membership verification data to escape every computable uniform bound.

Theorem 37.8 (Undecidable fibres force nonrecursive verification-length growth).

Let \(\rho:\mathcal D\to\mathcal X\) be a realization map with effectively coded descriptions and coding length \(\ell\). Fix \(x\in\mathcal X\), and suppose the fibre

\[ \mathfrak F_\rho(x)=\{d\in\mathcal D:\rho(d)=x\} \]

is recursively enumerable but not decidable. Suppose moreover that membership in this fibre is represented by a decidable verification relation

\[ \rho(d)=x \quad\Longleftrightarrow\quad \exists \pi\ R_x(d,\pi). \]

Then the bounded verification-length profile

\[ L_{R_x}(n)= \max_{\substack{\ell(d)\leq n\\d\in\mathfrak F_\rho(x)}} \min\{|\pi|:R_x(d,\pi)\} \]

is not bounded above by any total computable function.

This turns undecidability of a presentation fibre into a quantitative lower bound on membership verification.

Corollary 37.9 (Effective reversible move systems force nonrecursive bridge growth).

Let \(\mathcal M\) be an effective finite-branching reversible move system on \(\mathcal D\) preserving realization. Fix \(d_x\in\mathfrak F_\rho(x)\). Suppose

\[ d\in\mathfrak F_\rho(x) \quad\Longleftrightarrow\quad d\text{ is connected to }d_x\text{ by an }\mathcal M\text{-path}. \]

If membership in \(\mathfrak F_\rho(x)\) is undecidable, then the bridge profile

\[ B_{\rho,\mathcal M,x,d_x}(n)= \sup_{\substack{\ell(d)\leq n\\ d\in\mathfrak F_\rho(x)}} d_{\mathcal M}(d,d_x) \]

is not bounded above by any total computable function.

Theorem 37.10 (No complete computable resolution).

Let \(\rho:\mathcal D\to\mathcal X\) be a realization map with effectively coded descriptions. Suppose there is a computable map

\[ N:\mathcal D\to\mathcal N \]

to an effectively coded set \(\mathcal N\) with decidable equality such that

\[ N(d)=N(e) \quad\Longleftrightarrow\quad \rho(d)\equiv_\mathcal X\rho(e). \]

Then every represented fibre \(\mathfrak F_\rho(x)\), with a fixed description \(d_x\) satisfying \(\rho(d_x)=x\), is decidable.

Consequently, if a represented fibre is undecidable, the realization map admits no complete computable normal form in the above sense. Normal forms of this strength are resolutions of the fibre equivalence relation.

Corollary 37.11 (Non-collapse of fibre complexity).

There are presentation systems with an object \(x\) satisfying

\[ C_\Gamma(x)=0 \]

while the verification-length profile of \(\mathfrak F_\rho(x)\) is not bounded above by any total computable function. Hence no function of minimal presentation complexity alone can bound fibre recognition or membership-verification cost in general.

This construction is deliberately schematic. Natural non-collapse examples require specific undecidability or lower-bound results.

The point of the corollary is that minimal presentation complexity alone cannot be a general bound for fibre recognition or membership-verification growth.

Theorem 37.12 (Prefix-free search penalty).

Let \((X,\mu)\) be a probability space, and let \(\{A_c\}_{c\in\mathcal C}\) be a countable family of searched events. Suppose

\[ \mu(A_c)\leq p_c \]

with \(p_c>0\), and suppose a search cost \(K(c)\) satisfies Kraft's inequality

\[ \sum_{c\in\mathcal C}2^{-K(c)}\leq 1. \]

Then, for every \(t\geq 0\),

\[ \mu\left( \bigcup_{\{c:\,-\log_2 p_c-K(c)\geq t\}} A_c \right) \leq 2^{-t}. \]

This is the formal search-penalty principle behind adaptive discovery. The relevant budget is the description cost of the searched event. For \(N\) independent samples, one replaces \(p_c\) by \(p_c^N\), producing the score \(N\log_2(1/p_c)-K(c)\).

Theorem 37.13 (Cheap-counterexample exclusion).

Let \(P\) be a property of objects in \(\mathcal X\), and let

\[ B_P=\{x\in\mathcal X:P(x)\text{ fails}\}. \]

Suppose a presentation system \(\Gamma\) and a bound \(b\) satisfy:

\[ B_P\neq\varnothing \quad\Longrightarrow\quad B_P\cap\mathcal X_\Gamma^{\leq b}\neq\varnothing \]

and

\[ B_P\cap\mathcal X_\Gamma^{\leq b}=\varnothing. \]

Then \(P\) holds for all objects in \(\mathcal X\).

This theorem captures finite-reduction arguments: counterexamples must be cheap, but cheap counterexamples are excluded.

38 Basic examples

38.1 Heights

For rational points in projective space,

one may take descriptions to be primitive integer coordinate vectors

with realization

and cost

The resulting presentation complexity is the logarithmic height.

Thus height theory is an arithmetic instance of presentation complexity.

Height balls are bounded parts. Height inequalities under morphisms are cost-controlled maps. Counting points of bounded height is volume theory for bounded parts.

38.2 Kolmogorov complexity

For finite binary strings,

take descriptions to be programs for a universal machine \(U\):

with realization

and cost

Then

is Kolmogorov complexity relative to \(U\).

38.3 Circuit complexity

For Boolean functions,

descriptions may be Boolean circuits, realization is the computed function, and cost is circuit size or depth.

The presentation complexity is minimum circuit size or depth.

38.4 Group presentations

For finite groups, one possible presentation system uses finite presentations

with realization

and cost such as

Another presentation system may use multiplication tables, word circuits, semidirect-product data, module data, commutator tensors, finite local models, or permutation-cover data.

Different presentation systems measure different mathematical resources.

Words may play two distinct roles. As relators, words are part of descriptions and contribute to presentation cost. As word maps or word equations, words define observables and contribute to observation cost.

38.5 Algebraic and straight-line complexity

For polynomials or algebraic expressions, descriptions may be arithmetic circuits or straight-line programs.

The realization map sends a circuit to the polynomial or function it computes.

The cost may be the number of operations, depth, degree of allowed gates, or circuit size.

Observables may include degree, rank of partial derivative spaces, support, evaluation data, or factorization patterns.

This gives a presentation-theoretic view of algebraic complexity.

Declaration of generative AI and AI-assisted technologies in the writing process

During the preparation of this work, ChatGPT, by OpenAI, was used to assist with mathematical drafting, formalization, review, and editing. This work is shared as a preliminary AI-assisted mathematical note. The mathematical content may have been only partially reviewed and may contain errors; it should not be treated as peer-reviewed or as a fully verified manuscript.