Home
Back to AI-assisted math

A theory about complexity

We present drafts and notes about a mathematics toolkit that hopefully will be able to produce new proofs and relevant results. The rough idea is assigning an appropriate complexity value to math objects that behaves properly under the operations relevant to those objects, meaning that it acts as a budget that restricts the possible outputs.

This toolkit primed many of the ai-assisted math notes in this section.

The first description of the ideas that led to the formalisations 
Automatic English translation generated from the Italian original. Mathematical notation and formula blocks are intentionally left close to the source.

Mathematics Theory of Complexity

Objective: to build a theoretical framework to be able to say something like “this cannot be a response to this problem because it is too complex”, or “”a counter-example cannot exist because it would be infinitely complex”.

Something like 2+2!= sqrt(pi) because sqrt(pi) is too complex, and + does not increase so much the complexity of its inputs. Or similarly 1/2 + 1/3!= 37/43.

An idea: I choose a random vector on R2... what is the probability that it is [1, 2]? NOT zero, because a very simple carrier should have high probability, and zero probability numbers should be very complex.

(May the theory go in the direction of combining entire/real positive(?) elements (“completeness”) and see how they behave compared to operators (a funtor? )).

Ideally the theory will go deep into fine logic issues, allowing to produce numerous arguments for absurdity in a manner similar to algebraic unchanged.
The theory was born with ideas of measurement and probability and information, but is there a great way to transform a map of complexity into a measure (of probability)? Do you play some arguments?

Also something like “this algorithm or encoding is too simple and therefore not expressive enough for the purposes”

—

Bits are a measure of complexity for natural interesting
0->1 (or 0? )
1->1
10-> point
11->2
100->3
...

Also C(n)=n and C(n) = log(n) seem sensible. The complexity chosen should be linked to the problem to be solved and to the natural encoding of the objects that are concerned.

If I want low probability <-> high complexity, they have C(x)=1/p(x) (but not convince me) and C(x)=-log(x) (better).

Es.
num|completeness
0 | 1 | 1/2
1 | 1 | 1/2
1/4
1/4
1/8
101.
...

We note that if everyone had complexity 1 there would be no sensible chance to assign it.

For rationale: if a/b is at the minimum terms, we can say C(a/b) = C(a) + C(b)
(As C(a sqrt(2) + b) = C(a) + C(b) in Q(sqrt(2)).

C(a/b + c/d) <= C(ad + bc) + C(bd) (if complexity goes up the number).

C(a/b * c/d) = C(ac/bd) <= C(ac) + C(bd)

Quindi sì:
1/2 + 1/3 != 37/43 perché una somma non può aumentare così tanto la complessità (!)

Similmente sqrt(2) è irrazionale perché se 2 = a^2/b^2, C(a^2/b^2) = C(2), quindi a^2 e b^2 devono essere poco complessi e nessun esempio funziona. Superficialmente qualcuno potrebbe dire che potrebbero essere estremamente complessi numeratore e denominatore e tornare esattamente sqrt(2), ma in questo modo formalizziamo che l’esempio deve essere “semplice” e possiamo escludere tutti tranne finiti casi da testare.

Possiamo definire la complessità di numeri irrazionali (come e e pi) in base agli algoritmi per calcolarli/definirli (numeri non calcolabili <-> complessità infinita).

—

Scegliamo un numero naturale >0 casualmente così:
Partiamo da 1; 50% di proseguire con un numero casuale e ripetere questo step

num -> probab -> informazione con log2
1 -> 1/2 -> 1
10 -> 1/8 -> 3
11 -> 1/8 -> 3
100 -> 1/32 -> 5
…
Vediamo che l’info con log2 non sono proprio i bit

L’informazione di una distribuzione di probabilità si può sempre considerare una valida complessità ( è un requisito per avere una complessità utile?).

Da complessità a probabilità, ha senso un round per troncare la complessità massima, e poi una scelta casuale. Es., 1/2 che la complessità max sia 1, 1/4 che sia 2, 1/8 che sia 3, ecc., e poi ho finite scelte.
Questo è un trick di molti possibili per un caso infinito, potrebbe aver senso trattare prima un caso finito.

n=2*p1 3^p3 5^p5 , C(n)=p2 + p3 + p5 + … è una complessità con un po’ di senso.

Numeri p-adici?
Automi a stati finiti?
Invariati algebrici e geometria/topologia?
A formalisation 
Automatic English translation generated from the Italian original. Mathematical notation and formula blocks are intentionally left close to the source.

Yes. The correct version, according to me, is: do not immediately seek a single “universal complexity”, but build an atlas of complexity: a coordinated family of measures, filtrations, controlled operators, descriptions, tests, tests and probable measures. The unique lens is not “all is separation” or “all is Kolmogorov”, but:
[
\boxed{
\text{un oggetto può essere escluso quando nessun processo ammesso può trasferire abbastanza complessità, informazione, distinzione o certificazione verso di lui.}
}
]
This preserves your original philosophy without forcing it immediately in a unique direction.

1. Primary object: budget scales
Even before objects, you need to decide where budgets live.
A budget scale is an orderly monoid
[
(B,\le,0,\oplus)
]
where:
* (b\le c) means “(b) costs as much as (c)”;
* (0) is no cost;
* (b\oplus c) is the compound cost;
* possibly there is an element (\infty).
Examples:
[
(\mathbb N,\le,0,+),\qquad
(\mathbb R_{\ge0},\le,0,+),\qquad
(\mathbb N^k,\le_{\mathrm{coord}},0,+).
]
This choice is important: often complexity is not climbing. An object can have low degree but high height, low algorithmic description but high logical complexity, low entropy but high separative complexity.
So the first philosophical correction is:
[
\textbf{la complessità giusta è spesso un profilo, non un numero.}
]
This is linked to ideas already present in the mathematical theories of resources, where resources are modeled through neat structures and compositions, often monoidal. (arXiv)

2. Filtered spaces of complexity
A space of complexity is a couple
[
(X,C)
]
where (X) is a space of objects and
[
C:X\to B
]
is a function of complexity.
It causes a filtration:
[
X_{\le b}={x\in X:C(x)\le b}.
]
These are the objects within budget (b).
The decisive property is the property of finesse:
[
|X_{\le b}|<\infty.
]
This is the abstract form of the Northcottian principle: a bound of complexity transforms infinite research into finite research. In the theory of heights, Northcott's theorem says, in a classical form, that there are only finitely many algebraic points of fixed degree and limited height. (Rhul)
This property is central to your philosophy, because it allows topics like:
[
\text{se un controesempio esiste, allora ne esiste uno con } C(x)\le b;
]
but
[
X_{\le b}
]
It's over, so I can control it.

3. Controlled operators
Here is the most faithful heart to your initial idea.
Siano
[
F:X_1\times\cdots\times X_n\to Y
]
an operation, and are given complexity
[
C_i:X_i\to B_i,\qquad C_Y:Y\to B_Y.
]
Saying that (F) is controlled means giving a monotonous function
[
\Phi_F:B_1\times\cdots\times B_n\to B_Y
]
that the
[
C_Y(F(x_1,\dots,x_n))
\le
\Phi_F(C_1(x_1),\dots,C_n(x_n)).
]
This is the exact formalization of:
the operator cannot arbitrarily increase complexity.
From here, the first demonstration tool is immediately followed.
Punctuality of obstruction
♪
[
C_Y(y)>
\Phi_F(C_1(x_1),\dots,C_n(x_n)),
]
then
[
F(x_1,\dots,x_n)\ne y.
]
This is the principle behind examples such as:
[
\frac12+\frac13\ne\frac{37}{43}.
]
If you use rational height
[
H(a/b)=\max(|a|,|b|)
]
in reduced form, then there are inequalities of the type
[
H(x+y)\le 2H(x)H(y).
]
Time
[
H(1/2)=2,\qquad H(1/3)=3,
]
therefore
[
H(1/2+1/3)\le 12.
]
Ma
[
H(37/43)=43.
]
So (37/43) is too high to be that sum.
This is much closer to your original philosophy than the only filtered test theory.

4. Complexity as a demonstrative variable
An invariant of complexity is a map
[
I:X\to M
]
towards an ordered space (M), with an estimate of control over operators:
[
I(F(x))\le \Psi_F(I(x)).
]
Then you can prove impossibility by comparing invariants:
[
I(y)>\Psi_F(I(x))
\quad\Longrightarrow\quad
y\ne F(x).
]
This is the abstract version of many classical mathematical topics:
[
\text{grado},\quad
\text{altezza},\quad
v_p,\quad
\text{rango},\quad
\text{dimensione},\quad
\text{norma},\quad
\text{energia},\quad
\text{entropia},\quad
\text{numero di stati}.
]
So the toolkit should not seek only one complexity, but a theory of filtered invariants controlled by operators.
This is the central phrase:
[
\boxed{
\text{un invariante diventa una complessità quando è filtrante, finitario e controllato dalle operazioni rilevanti.}
}
]

5. Descriptions, encoding and building complexity
Now we add a second source of complexity.
A descriptive scheme is a partial map
[
E:D\rightharpoonup X,
]
where (D) is a space of descriptions, programs, formulas, words, codes, grammages, tests, circuits.
If (D) has a length (\ell:D\to\mathbb N), we define
[
K_E(x)=\inf{\ell(d):E(d)=x}.
]
This is the descriptive complexity of the scheme (E).
The complexity of Kolmogorov is the case in which (D) is the space of programs and (E) is a universal machine; in this context, (K(x))) is the length of the shortest program it produces (x). (Enciclopedia di Filosofia Stanford)
From here comes the second great demonstration tool.
Unable compression blade
♪
[
K_E(x)>b,
]
then no length description (\le b) produces (x).
More interesting:
if hiring a certain structure (S) implies a short description of (x), i.e.
[
S\Longrightarrow K_E(x)\le b,
]
but you know
[
K_E(x)>b,
]
then (S) is impossible.
This formalizes the method of incomprimibility.

6. From probability to complexity
If you have a probability distribution
[
p:X\to[0,1],
]
the natural informational complexity is
[
C_p(x)=-\log p(x).
]
This is the right choice, not (1/p(x)), because it makes multiplication of probability and addition of compatible information:
[
-\log(pq)= -\log p-\log q.
]
So:
[
\boxed{
\text{probabilità bassa} \iff \text{alta informazione}
}
]
but only compared to the chosen distribution.

7. From complexity to probability
In the opposite direction, given a complexity
[
C:X\to\mathbb R_{\ge0},
]
there is generally no unique “good” probability. However, canonical transformations exist.
The most natural is Gibbs' measurement:
[
\mu_s(x)=\frac{e^{-sC(x)}}{Z(s)},
]
where
[
Z(s)=\sum_{x\in X}e^{-sC(x)}.
]
This works when (Z(s)<\infty). The parameter (s) regulates how much you press simple objects.
Another building, very close to your intuition “first I choose a maximum complexity, then I choose a simple object”, is:
[
\mu(x)=
\sum_{r\ge C(x)}
q_r\frac{1}{|X_{\le r}|},
]
where (q r) is a distribution on budget levels.
This construction is often more robust when the balls (X {\le r}) are finished.
In the algorithmic world, Solomonoff's algorithmic probability assigns more weight to objects produced by short programs; it is one of the strongest formalizations of the idea that simple objects should be more likely. (Raysolomonoff. (c)
So the correct formulation is:
[
\boxed{
\text{una complessità non induce una probabilità unica, ma una famiglia naturale di prior di semplicità.}
}
]

8. The case of the reals: simple points with positive mass
Your intuition:
choosing a random carrier in (\mathbb R^2), ([1,2]) should be non-zero likely because it is simple
is incompatible with the measure of pure Lebesgue, where each point has zero mass.
But it can be formalized with a mixed measure:
[
\mu
(1-\varepsilon)\lambda
+
\varepsilon
\sum_{x\in S}
w_x\delta_x.
]
Here:
* (\lambda) is a continuous measure;
* (S) is a numberable set of simple points, for example rational, algebraic, computable or defined;
* (\delta x) is the punctual mass in (x);
* (w x) decreases with the complexity of (x).
For example:
[
w_x\propto e^{-sC(x)}.
]
Thus ([1,2]) may be positive, but a generic real does not.
This is not “the” natural geometric probability. It is an epistemic prior of simplicity.

9. Testing, Observers and Separative Complexities
Now we insert the part of the previous formalization, but as a toolkit module, not as a unique direction.
A filtered test space is given by
[
(X,A,(T_b)_{b\in B}),
]
where
[
T_b\subseteq A^X
]
is the set of tests available within budget (b).
We define:
[
x\equiv_b y
\quad\Longleftrightarrow\quad
\forall \tau\in T_b,\ \tau(x)=\tau(y).
]
A property
[
P:X\to R
]
is decidable within budget (b) if it is constant on classes (\equiv b).
Then a separate lower bound has form:
[
x\equiv_b y
\quad\text{ma}\quad
P(x)\ne P(y).
]
This part is perfect for automatons, finite logic, query, communication complexity, proof matching, circuit lower bounds and learning theory. Your previous formalization had already isolated this core well through filtered test spaces, indistinguishability and transfer of lower bounds.
In literature, this area has very close relatives: for example game comonads give a categorical read of comparison games between models, limited logical resources, treewidth, treedepth and logical fragments to limited resources. (arXiv)

10. Tests and certificates
A test system can be treated as a special descriptive scheme.
You have:
[
\Pi\subseteq D\times \mathrm{Stmt}
]
where (d) is a test and (\varphi) is a statement.
Define:
[
C_\Pi(\varphi)=
\inf{\ell(d):d\text{ prova }\varphi}.
]
A lower bound of proof says:
[
C_\Pi(\varphi)>b.
]
But the toolkit also allows more refined shapes:
* every short test induces a poor test;
* each short test has a limited invariant;
* each short refutation should separate two indistinguishable objects;
* every short certificate would compress too much an incomprehensible object.
Therefore proof complexity can live both in the descriptive module, and in the separating module, and in the invariant module.

11. Transfer between worlds
To truly unify the areas, you need a translation notion.
An interpretation of complexity between two worlds
[
X\to Y
]
can have two aspects.
forward appearance: object control
A map
[
I:X\to Y
]
is controlled if
[
C_Y(I(x))\le \Phi(C_X(x)).
]
That says:
simple objects remain simple enough.
Back Appearance: Test Control
If (Y) has tests (T b^Y) and (X) has tests (T b^X), we ask:
[
\tau\in T_b^Y
\quad\Longrightarrow\quad
\tau\circ I\in T_{\sigma(b)}^X.
]
That says:
every economic observation on the target draws back to an economic observation on the source.
This is the abstract form of reductions in lower bounds.
The basic theorem is:
[
\delta_X(Q\circ I)\le \sigma(\delta_Y(Q)).
]
In contrast form:
[
\delta_X(Q\circ I)>\sigma(b)
\quad\Longrightarrow\quad
\delta_Y(Q)>b.
]
Then a lower bound in (X) transfers a lower bound in (Y).

12. Compact definition: atlas of complexity
I would put everything in a modular definition.
An atlas of complexity on a class of objects (X) consists of:
[
\mathfrak A_X=
(B,\mathcal C,\mathcal O,\mathcal D,\mathcal T,\mathcal M)
]
where:
* (B) is a budget scale;
* (\mathcal C) is a family of intrinsic complexity (C:X\to B);
* (\mathcal O) is a family of controlled operators;
* (\mathcal D) is a family of descriptive schemes (E:D\rightharpoonup X);
* (\mathcal T) is a family of filtered tests;
* (\mathcal M) is a family of measures or priors induced by complexity.
This definition does not immediately choose a direction. It allows various specializations.

13. The main demonstration instruments
The toolkit should produce at least these patterns.
A. Punctually obstruction
[
C(y)>\Phi(C(x))
\quad\Longrightarrow\quad
y\ne F(x).
]
Examples: heights, degrees, norms, rank, ratings (p)-adiche.
B. Endless obstruction
[
\exists x\in X\ P(x)
\quad\Longrightarrow\quad
\exists x\in X_{\le b}\ P(x).
]
If (X {\le b}) is finished, it is reduced to finite control.
C. Compressed obstruction
[
S\Longrightarrow K(x)\le b,
\qquad
K(x)>b
\quad\Longrightarrow\quad
\neg S.
]
Examples: Kolmogorov, incompressibility, MDL.
The MDL principle, in fact, selects models balancing complexity of the model and ability to describe the data; it is a statistical-informative formalization of the idea that better explanations are those that compress better without losing fit. (homepages. cwi.nl)
D. Intestinal obstruction
♪
[
|\mathrm{Costruibili}{\le b}|
\ll
|X{\le b}|,
]
then almost all objects in (X {\le b}) are not buildable.
This is the abstract form of the count arguments.
E. Separative obstruction
[
x\equiv_b y
\quad\text{ma}\quad
P(x)\ne P(y).
]
Examples: automous, finite logic, query, communication, circuits, learning theory.
F. Probability obstruction
If a class of simple processes causes distributions that assign too small mass or too rigid structure to an event (E), then (E) is not explained by that class within that budget.
This is a general form of:
[
\text{modello troppo semplice} \Longrightarrow \text{distribuzioni troppo vincolate}.
]
G. Certificate obstruction
[
C_{\mathrm{proof}}(\varphi)>b.
]
Or:
[
\text{ogni prova corta avrebbe invariante basso, ma }\varphi\text{ richiede invariante alto.}
]

14. How your examples fall
Binary numbers
Binary length
[
C(n)=\lfloor\log_2 n\rfloor+1
]
is a natural complexity compared to positional encoding.
Distribution
[
p(n)\propto 2^{-sC(n)}
]
is not always normal for every (s). In fact there are about (2^k) length numbers (k). So...
[
\sum_n2^{-sC(n)}
\sim
\sum_k2^k2^{-sk}
\sum_k2^{(1-s)k},
]
which converges only by (s>1).
This is an important point: a complexity induces a measure only if it beats the entropy of growth of the balls.
Rational
For
[
x=a/b
]
in reduced form, you can use:
[
H(x)=\max(|a|,|b|)
]
or
[
h(x)=\log H(x).
]
Then sum and product have inequalities checked.
This is a perfect theory for arguments “the result is too high.”
(p) index and factorization
Complexity
[
C(n)=\Omega(n)
]
number of first factors counted with multiplicity, it is natural for multiplication:
[
C(mn)=C(m)+C(n).
]
But it is bad for the addition, because (n+(1)) can completely change the factorization.
This shows one of the central thesis:
[
\boxed{
\text{una complessità è buona solo rispetto agli operatori per cui ha leggi di propagazione.}
}
]
(\sqrt)
The irrationality of (\sqrt2) can be seen through an invariant (2)-adic.
♪
[
\sqrt2=a/b
]
with (a,b) cover me, then
[
a^2=2b^2.
]
Taking (v 2):
[
2v_2(a)=1+2v_2(b),
]
impossible because the left side is even and the right is odd.
Here the certificate is not “high height”, but parity of an evaluation. Therefore the toolkit must include many invariants, not only a numerical notion of magnitude.
Cars
For finished cars, the budget is the number of states.
A language requires many states if it requires many different classes.
This is exactly the right module.
Royal Vectors
For ([1,2]\in\mathbb R^2), simplicity cannot be captured by pure Lebesgue, but can be captured by a mixed prior with atoms on simple points.

15. Category form, without force
If you want a categorical version, I wouldn't start with a single speaker. I would start from a filtered category of processes.
You have objects (X,Y,Z) and filtered morphism sets:
[
\mathrm{Hom}_{\le b}(X,Y).
]
The composition meets:
[
\mathrm{Hom}{\le b}(X,Y)
\circ
\mathrm{Hom}{\le c}(Y,Z)
\subseteq
\mathrm{Hom}_{\le b\oplus c}(X,Z).
]
This is the abstract form of:
composing two processes costs the sum, or a controlled combination, of costs.
If you want an even more flexible structure, you can interpret costs such as asymmetrical distances or categorical enrichments; the idea that the spaces can be seen as enriched categories goes back to Lawvere. (tac.mta.ca)
But I wouldn't do the philosophical point of departure. I would use it as a language when it serves composition.

16. What this theory should not say
To stay correct, you must avoid four errors.
Error 1: “infinite complexity implies non-existence”
No. Objects not computable or indescribable may exist. What you can say is:
[
\text{nessun oggetto entro il budget dato può essere questo.}
]
Or:
[
\text{se esiste un controesempio, ne esiste uno semplice;}
]
and then exclude the simple ones.
Error 2: “existing absolute complexity”
No. (\sqrt\pi) is simple algorithmically, but it is not rational, it is not algebraic, and can be out of certain arithmetic filter spaces.
An object can be simple in one coordinate and complex in another.
Error 3: “zero probability means high complexity”
No. In a continuous distribution, all points are zero probability.
The probability/complexity connection applies to a prior discrete, mixed or descriptive.
Error 4: “unification = same formula for everything”
No. The unique lens must be modular:
[
\text{budget}+\text{filtrazione}+\text{controllo}+\text{ostruzione}.
]
Not just a notion of complexity.

17. The final core of the theory
I would formulate it like that.
Basic principle
A mathematical problem often admits a form:
[
\text{input semplice}
+
\text{processo economico}
\longrightarrow
\text{bersaglio}.
]
A theory of demonstrative complexity studies when this arrow is impossible because the target requires more than what the process can transfer.
That “more” can be:
[
\text{altezza},
\quad
\text{grado},
\quad
\text{rango},
\quad
\text{descrizione},
\quad
\text{informazione},
\quad
\text{probabilità},
\quad
\text{stati},
\quad
\text{distinzioni},
\quad
\text{prove},
\quad
\text{energia},
\quad
\text{entropia}.
]
So the correct motto is not only one, but this:
[
\boxed{
\text{ogni operatore, descrizione, prova o osservatore ha un budget; ciò che richiede più complessità, informazione o distinzione di quanto quel budget possa trasferire è escluso.}
}
]

18. Judgement on potential
This version has more potential than the previous formalization, because it does not immediately decide that the heart is separation. Maintains four genuine sources of mathematics:
1. invariants controlled by operators, close to height, rank, degree, norms, ratings;
2. descriptive complexity, close to Kolmogorov, MDL, encoding, compression;
3. measures from complexity, close to Gibbs, Solomonoff, prior to simplicity;
4. filtered tests, close to automatons, logic, query, communication, proof complexity.
The most promising form is not a “general theory of complexity” too vague, but a calculation of budget obstructions.
That would be a real demonstration toolkit.
Handoff of ai-assisted math research 
Automatic English translation generated from the Italian original. Mathematical notation and formula blocks are intentionally left close to the source.

Complexity 2.unif

Program: demonstrative complexity, arithmetic heights and Kolmogorov
This document summarizes a research program developed from an initial philosophy:
build a mathematical theory of complexity able to say, rigorously, that certain objects, counterexamples, answers, certificates or images of operators cannot exist or cannot be produced because they would require more complexity, information, distinction, certification or budget than the allowed process can transfer.
The initial naive idea was something like:
[
2+2\ne \sqrt{\pi}
]
not only because the values are different, but because the right side seems too complex compared to the inputs and operators allowed. Or:
[
\frac12+\frac13\ne\frac{37}{43}
]
because a sum of rational small cannot generate a rational of height too large.
The program then refined very much. The main conclusion is that there is no single universal complexity capable of explaining everything. The mature form is:
[
\boxed{
\text{presentazioni naturali}
+
\text{costi}
+
\text{filtrazioni}
+
\text{operatori controllati}
+
\text{volumi}
+
\text{ostruzioni}
}
]
The theoretical nucleus is a theory of controlled normative presentations, i.e. a framework in which an object is complex not because it possesses a mysterious absolute complexity, but because every one of its admitted presentation costs a lot.

1. Initial philosophy
The original goal was to build a formalism to make stringent phrases like:
[
\text{“questa non può essere una risposta a questo problema perché è troppo complessa”}
]
or:
[
\text{“un controesempio non può esistere perché sarebbe infinitamente complesso”}.
]
Motivating examples:
1. A result obtained from simple inputs through simple operators should remain within a certain budget.
2. A function, an algorithm, a test or too simple encoding should not be able to express too complex objects.
3. A simple object should be more likely in a prior of simplicity.
4. Very low probability objects should correspond to great information, through:
[
C_p(x)=-\log p(x).
]
5. For rational numbers, height or length of description seem natural measures.
6. For real, automous, testing, algorithms, dynamic systems, modules, representations and geometric objects serve different notions.
The first major clarification was:
[
\boxed{
\text{la complessità giusta non è quasi mai un numero singolo, ma un profilo.}
}
]
An object can be simple algorithmically but high arithmetic, low can but high in height, simple to define but difficult to find, easy to verify but difficult to produce.
Basic example:
[
n_m=2^{2^m}.
]
Its logarithmic height is enormous:
[
h(n_m)=2^m\log 2,
]
but its complexity of Kolmogorov is small:
[
K(n_m)\le K(m)+O(1)\approx \log m.
]
So it cannot be worth a naive theory:
[
K(x)\approx h(x).
]
The bridge between Kolmogorov and heights must be thinner.

2. Negative diagnosis: what does not work
2.1 There is no absolute complexity
It makes no sense to seek a universal function:
[
C:X\to \mathbb R_{\ge0}
]
that simultaneously explain arithmetic height, Kolmogorov, computational cost, entropy, size, degree, rank, energy, test, automatons and information.
For example:
* (\sqrt{\pi}) can be algorithmically simple if we have an algorithm for (\pi), but it is not rational or algebraic known in elementary sense.
* (2^{2^m}) is high arithmetic but low algorithmically.
* A generic real point has zero probability compared to Lebesgue measurement, but also ([1,2]) is zero probability compared to the same measure, although it is simple.
* An object can be simple to describe but difficult to build within time constraints.
So the question is not:
[
\text{“quanto è complesso assolutamente }x\text{?”}
]
but:
[
\boxed{
\text{“quanto costa presentare, produrre, distinguere o certificare }x
\text{ nel sistema ammesso?”}
}
]
2.2 Zero probability does not mean high complexity
To a continuous extent, each point has zero mass. So you can't say:
[
p(x)=0\Rightarrow C(x)=\infty.
]
To give positive mass to simple points in (\mathbb R^n), it serves a mixed measure:
[
\mu=(1-\varepsilon)\lambda+\varepsilon\sum_{x\in S}w_x\delta_x,
]
where:
* (\lambda) is a continuous measure,
* (S) is a numberable set of simple points,
* (w x) decreases with complexity,
* (\delta x) is the atomic mass in (x).
This is not “natural geometric measurement”; it is an epistemic prior of simplicity.
2.3 “Complex object” does not imply “non-existence”
Objects not computable or indescribable may exist. Complexity does not automatically give non-existence.
A valid phrase is:
[
\text{nessun oggetto ottenibile entro questo budget può essere }y.
]
Or:
[
\text{se un controesempio esiste, allora ne esiste uno entro budget }b.
]
Then, if the budget ball is over, you can check.
But it is not valid to say:
[
\text{“un controesempio sarebbe molto complesso, quindi non esiste”.}
]
In fact, if the counterexamples are enumerable by height and the property is decidable, then the first example is often algorithmically simple: just say “the first example”. This is a fundamental obstacle against many naive subjects based on Kolmogorov.

3. Central Formalism: standard presentations
The correct primitive is not a function of complexity on objects, but a presentation.
3.1 Budget
A budget is an orderly monoid:
[
(B,\le,0,\oplus).
]
Examples:
[
(\mathbb N,\le,0,+),
]
[
(\mathbb R_{\ge0},\le,0,+),
]
[
(\mathbb N^k,\le_{\mathrm{coord}},0,+),
]
[
(\mathbb R_{\ge0}^k,\le_{\mathrm{coord}},0,+).
]
The budget can be multidimensional. For example:
[
C(x)=
(\text{grado},\text{altezza},\text{tempo},\text{spazio},\text{lunghezza descrizione}).
]
In the theory of heights on (\overline{\mathbb Q}), the only height is not enough to have finitude; it also serves the degree:
[
C(P)=([K(P):K],h(P)).
]
This is a vector complexity.
3.2 Standard presentation
A standard presentation of an object space (X) is a terna:
[
\Gamma=(D,\pi,\ell),
]
where:
* (D) is the space of descriptions, programs, coordinates, tests, circuits, models, codes, certificates;
* (\pi:D\rightharpoonup X) is a partial map that says what object is presented;
* (\ell:D\to B) is the cost of the description.
Induced complexity is:
[
C_\Gamma(x)=
\inf{\ell(d):\pi(d)=x}.
]
The budget ball is:
[
X_{\le b}^{\Gamma}
{x\in X:C_\Gamma(x)\le b}.
]
This definition includes:
* Kolmogorov: (D={0,1}^*), (\pi(p)=U(p)), (\ell(p)=|p|).
* Rational heights: (D=) primitive coordinates, (\pi=) projection to (\mathbb P^n), (\ell=\log\max |x i|).
* Circuit complexity: (D=) circuits, (\pi(C)=) function calculated, (\ell(C)=) size/depth.
* Proof complexity: (D=) tests, (\pi(p)=) theorem shown, (\ell(p)=) length/size/width.
* Information theory: (D=) codes, (\ell=) code length, or (C p(x)=-\log p(x)).
* Automorphic/Galois: (D=) local/global data, (\ell=) conductor/discriminator/ramification/parameters archimedei.
3.3 Properness / Northcott abstract
A presentation is only useful if the balls are controllable:
[
X_{\le b}
]
must be finished, compact, effectively enumerable, or at least have known volume.
In the discreet case:
[
|X_{\le b}|<\infty.
]
This is the abstract form of Northcott's property.
In theory of heights:
[
{P\in \mathbb P^n(\overline K):[K(P):K]\le d,\ h(P)\le B}
]
It's over.
In Kolmogorov:
[
|{x:K(x)\le n}|\le 2^{n+1}-1.
]
In circuit complexity:
[
|{\text{funzioni calcolabili da circuiti di size }\le s}|
\le 2^{O(s\log s)}.
]
Information:
[
|\text{typical set}|\approx 2^{nH}.
]
The general principle is:
[
\boxed{
\text{pochi oggetti hanno presentazioni molto economiche.}
}
]

4. Controlled disease
An operation:
[
F:X\to Y
]
is controlled if there is a monotonous function:
[
\Phi_F:B_X\to B_Y
]
such that:
[
C_Y(F(x))\le \Phi_F(C_X(x)).
]
More correctly, (F) should rise to a transformation of descriptions:
[
\widetilde F:D_X\to D_Y,
]
with:
[
\pi_Y(\widetilde F(d))=F(\pi_X(d)),
]
[
\ell_Y(\widetilde F(d))\le \Phi_F(\ell_X(d)).
]
This formalizes the phrase:
[
\text{un operatore ammesso non può trasferire arbitrariamente complessità.}
]
The fundamental lemma follows:
[
C_Y(y)>\Phi_F(b)
\quad\Longrightarrow\quad
y\notin F(X_{\le b}).
]
On time:
[
C_Y(y)>\Phi_F(C_X(x))
\quad\Longrightarrow\quad
F(x)\ne y.
]
This is the demonstrative heart of the framework.

5. General Structural Theorems
5.1 No-go against tautology
If (X) is any set and (C:X\to\mathbb N) is any function with finite sublevels, then you can always realize (C) as complexity of presentation by placing:
[
D=X,
]
[
\pi=\mathrm{id}_X,
]
[
\ell=C.
]
So “objects + cost” alone is tautological.
Content starts only when we impose:
[
\text{naturalità},
\quad
\text{properness},
\quad
\text{computabilità},
\quad
\text{functorialità},
\quad
\text{controllo degli operatori},
\quad
\text{leggi di volume}.
]
5.2 Invariance Theorem for Simulation
Siano (\Gamma=(D,\pi,\ell))) and (\Gamma'=(D',\pi',\ell'))) two presentations of the same (X).
If there is a compiler:
[
S:D\to D'
]
such that:
[
\pi'(S(d))=\pi(d),
]
[
\ell'(S(d))\le \alpha(\ell(d))+c,
]
Then:
[
C_{\Gamma'}(x)\le \alpha(C_\Gamma(x))+c.
]
If there is also a reverse compiler, the two complexities are equivalent within overhead.
Sources:
* in Kolmogorov is the theorem of invariance of universal machines;
* in height is the height machine module (O(1));
* in computational complexity is robustness compared to equivalent calculation models;
* Information is the stability of codes within overhead.
5.3 Controlled image obstruction
If:
[
C_Y(F(x))\le \Phi(C_X(x)),
]
Then:
[
F(X_{\le b})\subseteq Y_{\le\Phi(b)}.
]
So:
[
y\notin Y_{\le \Phi(b)}
\Rightarrow
y\notin F(X_{\le b}).
]
Examples:
* Heights:
[
h(\alpha+\beta)\le h(\alpha)+h(\beta)+O(1).
]
* Kolmogorov:
[
K(f(x))\le K(x)+K(f)+O(1).
]
* Circuits:
[
C_{\mathrm{circ}}(f\circ g)\le C_{\mathrm{circ}}(f)+C_{\mathrm{circ}}(g)+O(1).
]
* Information:
[
X\to Y\to Z
\Rightarrow
I(X;Z)\le I(X;Y).
]
5.4 Volume Theorem/Kolmogorov
Be ((X,h)) a class of objects with finite balls:
[
X_{\le B}={x:h(x)\le B},
]
[
N_X(B)=|X_{\le B}|.
]
If (X {\le B}) is actually enumerable, then for each (x\in X {\le B}):
[
K(x\mid B,X,h)\le \log_2 N_X(B)+O(1).
]
In addition, for each (t\ge0):
[
\frac{
|{x\in X_{\le B}:K(x\mid B)<\log_2 N_X(B)-t}|
}
{N_X(B)}
\le 2^{-t+O(1)}.
]
So a typical element of the ball has:
[
K(x\mid B)\approx \log_2 N_X(B).
]
This is the strongest technical bridge between heights and Kolmogorov:
[
\boxed{
\text{l’altezza controlla il volume delle palle;}
\quad
\text{Kolmogorov misura la posizione informazionale dentro la palla.}
}
]
5.5 Input of Processes
Siano:
[
P_{\le r}=\text{processi ammessi di costo }\le r,
]
[
X_{\le b}=\text{input di costo }\le b,
]
[
Y_{\le B}=\text{bersagli di costo }\le B.
]
Then the reachable targets are at most:
[
|P_{\le r}|\cdot |X_{\le b}|.
]
If:
[
|Y_{\le B}|\gg |P_{\le r}|\cdot |X_{\le b}|,
]
then almost all targets are not reachable.
Sources:
* almost all strings are incomprehensible;
* almost all Boolean functions require large circuits;
* a channel cannot transmit more information of its capacity;
* a simple parametric family cannot cover a much larger volume environment.
5.6 Zeta/Gibbs and entropic threshold
Given a complexity:
[
C:X\to\mathbb R_{\ge0},
]
define:
[
Z(s)=\sum_{x\in X}e^{-sC(x)}.
]
If:
[
N(t)=|{x:C(x)\le t}|,
]
and:
[
\delta=\limsup_{t\to\infty}\frac{\log N(t)}{t},
]
then (Z(s)) converges only when decay (e^{-sC}) beats volume growth.
Principle:
[
\boxed{
\text{una prior di semplicità è normalizzabile solo se il decadimento batte l’entropia di crescita.}
}
]
This explains why a unique probability is not born from complexity: prior families are born, for example:
[
\mu_s(x)=\frac{e^{-sC(x)}}{Z(s)}.
]
5.7 Abstract Canonicalization
Both:
[
T:X\to X,
]
and suppose:
[
|C(Tx)-\lambda C(x)|\le A,
\qquad \lambda>1.
]
Then the limit:
[
\widehat C(x)=
\lim_{n\to\infty}\lambda^{-n}C(T^n x)
]
exists and meets:
[
\widehat C(Tx)=\lambda \widehat C(x),
]
[
|\widehat C(x)-C(x)|\le \frac{A}{\lambda-1}.
]
Sources:
* Canon height of Néron–Tate;
* canonical heights in arithmetic dynamics;
* asymptotic normalizations in information;
* average cost for iterates or products.
5.8 Abstract descent type Mordell–Weil
Both (G) an Abelian group with a pseudo-norma (|\cdot|) such as:
1. the balls ({x:|x|\le R}) are finished;
2. (|x+y|\le |x|+|y|);
3. (|mx|=m|x|) for some (m\ge2);
4. (G/mG) is finished.
Then (G) is finitely generated.
This is the abstract structure behind Mordell–Weil:
[
\text{altezza canonica}
+
\text{quoziente finito}
+
\text{Northcott}
+
\text{discesa}
\Rightarrow
\text{generazione finita}.
]
5.9 Transfer of lower bounds via test
Siano (X,Y) with filtered tests:
[
T_b^X,\qquad T_b^Y.
]
A map:
[
I:X\to Y
]
has backward control on the tests if:
[
\tau\in T_b^Y
\Rightarrow
\tau\circ I\in T_{\sigma(b)}^X.
]
If a property (Q) on (Y) was decidable with budget (b), then (Q\circ I) would be decidable on (X) with budget (\sigma(b)). By contrast:
[
\delta_X(Q\circ I)>\sigma(b)
\Rightarrow
\delta_Y(Q)>b.
]
This is the abstract form of reductions in computational complexity, finite model theory, automi, communication complexity and proof complexity.
5.10 Approximate complexity and rate-distortion
For continuous or analytical spaces, punctual fineness often fails. It replaces with approximation:
[
C_\varepsilon(x)=
\inf{\ell(d):d(x,\pi(d))\le \varepsilon}.
]
This is the version of:
* metric entropy,
* Kolmogorov (\varepsilon)-entropy,
* rate-distortion,
* compression with error,
* numerical approximation,
* analysis/PDE.
In many continuous contexts Northcott's replacement is:
[
\text{bound di regolarità/energia}
\Rightarrow
\text{compattezza o precompattezza}.
]

6. Rewriting the theory of heights
6.1 Projective height at minimum cost of coordinates
For:
[
P=[x_0:\cdots:x_n]\in\mathbb P^n(\mathbb Q),
]
choose primitive coordinates:
[
(x_0,\dots,x_n)\in\mathbb Z^{n+1},
\qquad
\gcd(x_0,\dots,x_n)=1.
]
Define:
[
H(P)=\max_i |x_i|,
]
[
h(P)=\log H(P).
]
This is a complexity of presentation:
[
D=\text{coordinate primitive},
]
[
\pi(x_0,\dots,x_n)=[x_0:\cdots:x_n],
]
[
\ell(x)=\log\max_i|x_i|.
]
For (\overline{\mathbb Q}), the height is adelicate:
[
h([x_0:\cdots:x_n])
\frac1{[K:\mathbb Q]}
\sum_{v\in M_K}
n_v\log\max_i|x_i|_v.
]
The product on all places guarantees the invariance with the choice of coordinates.
6.2 Height machine
For a projective variety (X) and a linear or divider fiber (L), the height machine assigns:
[
L\mapsto h_L.
]
Property:
[
h_{L\otimes M}=h_L+h_M+O(1),
]
[
h_{f^*L}(P)=h_L(f(P))+O(1).
]
So a geometric morphism is a controlled morphism.
6.3 Northcott
Northcott's property says:
[
{P:[K(P):K]\le d,\ h(P)\le B}
]
It's over.
In formalism:
[
C(P)=([K(P):K],h(P))
]
is a proper complexity.
6.4 Elementary operations
For algebraic numbers:
[
h(\alpha\beta)\le h(\alpha)+h(\beta),
]
[
h(\alpha+\beta)\le h(\alpha)+h(\beta)+\log 2,
]
[
h(\alpha^n)=|n|h(\alpha).
]
These are laws of propagation of complexity.
For example:
[
\frac12+\frac13\ne \frac{37}{43}
]
can be seen via rational height:
[
H(1/2)=2,
\qquad
H(1/3)=3,
]
[
H(x+y)\le 2H(x)H(y),
]
then:
[
H(1/2+1/3)\le 12,
]
While:
[
H(37/43)=43.
]
The target is too high to be that sum.
6.5 Rational Morphism
If:
[
f:\mathbb P^n\dashrightarrow \mathbb P^m
]
is given by homogeneous forms of grade (d), then:
[
h(f(P))\le d,h(P)+O(1).
]
If:
[
f^*L\simeq L^{\otimes q},
]
Then:
[
h_L(f(P))=q h_L(P)+O(1).
]
From here comes the canonical height:
[
\widehat h_f(P)=\lim_{n\to\infty}q^{-n}h_L(f^n(P)).
]
6.6 Néron–Tate
For an Abelian variety:
[
\widehat h(P)=\lim_{n\to\infty}4^{-n}h([2]^nP).
]
Property:
[
\widehat h([m]P)=m^2\widehat h(P),
]
[
\widehat h(P+Q)+\widehat h(P-Q)
2\widehat h(P)+2\widehat h(Q).
]
This is a canonicalization of an almost functorial cost.
6.7 Mordell–Weil
Mordell–Weil becomes:
[
\text{altezza canonica}
+
\text{quoziente finito}
+
\text{Northcott}
+
\text{discesa}
\Rightarrow
A(K)\text{ finitamente generato}.
]
6.8 Roth, Subspace Theorem, Vojta
Roth:
[
\text{un algebrico irrazionale non può avere troppe approssimazioni razionali troppo buone rispetto all’altezza}.
]
Subspace Theorem:
[
\text{troppa concentrazione locale}
\Rightarrow
\text{l’oggetto cade in sottospazi eccezionali}.
]
Vojta:
[
\text{prossimità locale}
+
\text{funzioni di conteggio}
+
\text{altezze globali}
]
are tied by a dictionary between diofantea approximation and Nevanlinna theory.
In our language:
[
\text{budget locale troppo alto rispetto al budget globale}
\Rightarrow
\text{eccezione strutturale}.
]
6.9 Bogomolov, small points, equidistribution
Bogomolov type results:
[
\text{troppi punti di altezza quasi zero}
\Rightarrow
\text{sottovarietà speciale}.
]
Equidistribution:
[
h(P_n)\to h_{\min}
\quad\Rightarrow\quad
\text{le orbite di Galois si equidistribuiscono verso una misura canonica},
]
in general.
Important: equidistribution does not imply high complexity of Kolmogorov. The roots of unity are equidistributed, but they are individually very compressible.
6.10 Manin–Peyre
Manin's problem studies:
[
N_X(B)=|{P\in X(K):H(P)\le B}|.
]
Often it is expected:
[
N_X(B)\sim cB^a(\log B)^{b-1}.
]
In our language:
[
\text{Manin studia il volume delle palle di altezza.}
]
From this follow the Kolmogorovian Bridge:
[
K_{\mathrm{tipico}}(P\mid B)
\approx
a\log_2B+(b-1)\log_2\log B.
]
6.11 Stack heights and Malle
The heights on stack allow to treat:
* variety,
* modules,
* classifying stacks,
* (G)-tors,
* numerical fields,
* Malle type problems.
Counting numbers for discriminant becomes a case of counting points of bounded height on stack.
In our language:
[
\log|\mathrm{Disc}(L)|
]
is a Galoisian height.

7. Rewriting of Kolmogorov theory
7.1 Complexity of Kolmogorov
Fixed a universal machine:
[
U:{0,1}^\rightharpoonup {0,1}^,
]
define:
[
K_U(x)=\min{|p|:U(p)=x}.
]
It is a standard presentation:
[
D={0,1}^*,
]
[
\pi(p)=U(p),
]
[
\ell(p)=|p|.
]
7.2 Invariance Theorem
For each other machine (M), it exists (c M) such that:
[
K_U(x)\le K_M(x)+c_M.
]
This is universal by compiler.
7.3 Incompressibility
There are less than (2^n) length programmes (<n). So almost all length strings (n) meet:
[
K(x)\ge n-O(1).
]
This is a pure form of counting/properness.
7.4 Prefix and Kraft
If the programs are prefix-free:
[
\sum_p2^{-|p|}\le1.
]
The universal semi-measure is:
[
m(x)=\sum_{U(p)=x}2^{-|p|}.
]
The coding theorem of Levin says:
[
K(x)=-\log m(x)+O(1).
]
This is the strongest algorithmic form of duality:
[
\text{complessità}
\leftrightarrow
\text{probabilità}.
]
7.5 Overall condition
[
K(x\mid y)=\min{|p|:U(p,y)=x}.
]
The data (y) changes the allowed presentation: it is a free parameter.
The chain rule says, grossly:
[
K(x,y)=K(x)+K(y\mid x,K(x))+O(1).
]
7.6 mutual algorithmic information
[
I(x:y)=K(x)+K(y)-K(x,y).
]
Measure how much you save by presenting (x,y) together instead of separately.
7.7 Randomness algorithmic
An infinite sequence (X) is Martin-Löf random if:
[
K(X{\upharpoonright n})\ge n-O(1)
]
for each (n).
It is an individual version of the Shannon principle: evenly typical sequences are not compressible.
7.8 Algorithmic statistics
The classical structure function is:
[
h_x(\alpha)=
\min{\log|A|:x\in A,\ K(A)\le\alpha}.
]
Interpretation:
* (\alpha): model cost (A);
* (\log|A|): residual cost to locate (x) in the model.
The total cost is:
[
K(A)+\log|A|.
]
This idea has become the model for arithmetic structure function.
7.9 Resource-bounded Kolmogorov
Ordinary complexity is too permissive. Vector budgets are considered:
[
(|p|,\operatorname{time}(p),\operatorname{space}(p)).
]
Examples:
[
K^t(x),
\quad
Kt(x),
\quad
KT(x),
\quad
CD^t(x).
]
These versions are crucial to connect Kolmogorov to:
* circuit complexity,
* derandomization,
* one-way functions,
* metacomplexity,
* search complexity.

8. Algorithms and computational complexity
8.1 Algoritmi as morphisms presented
An algorithm is a presentation of a function:
[
\varphi_p:\Sigma^\rightharpoonup \Sigma^.
]
The cost can be:
[
|p|,
\quad
T_p(n),
\quad
S_p(n),
\quad
\text{random bits},
\quad
\text{query},
\quad
\text{communication}.
]
8.2 Class of complexity as filtered balls
[
\mathrm P=\bigcup_k\mathrm{TIME}(n^k),
]
[
\mathrm{EXP}=\bigcup_k\mathrm{TIME}(2^{n^k}),
]
[
\mathrm{PSPACE},
\quad
\mathrm{BPP},
\quad
\mathrm{NP},
\quad
\mathrm{NC},
\quad
\mathrm{AC^0}.
]
A class of complexity is a filtered ball of computational morphisms.
8.3 Reductions as controlled pullbacks
A reduction:
[
A\le_m^p B
]
back economic algorithms for (B) in economic algorithms for (A).
So the lower bounds move backwards.
8.4 Cook–Levin
SAT is a universal presentation of NP certificates:
[
\text{computazione non deterministica polinomiale}
\Rightarrow
\text{formula booleana polinomiale}.
]
8.5 Time allocated
[
\mathrm{TIME}(f(n))\subsetneq \mathrm{TIME}(g(n))
]
for (g) sufficiently larger.
In our language:
[
\text{la filtrazione per tempo non collassa}.
]
8.6 Circuit
A circuit is a finite presentation of a Boolean function.
[
C_{\mathrm{circ}}(f)=
\min{|C|:C\text{ calcola }f}.
]
Counting:
[
|\text{circuiti di size }s|\le 2^{O(s\log s)}.
]
But:
[
|\text{funzioni booleane }n\to1|=2^{2^n}.
]
So almost all functions require huge circuits.
8.7 Communication
A short protocol produces few configurations/partitions/rectangles.
Lower bound away:
* rank,
* discrepancy,
* fooling sets,
* rectangle bounds,
are separate obstructions.

9. Information Theory
9.1 Codes as presentations
A prefix-free code is a presentation:
[
D\subseteq{0,1}^*,
]
[
\pi:D\to X,
]
[
\ell(d)=|d|.
]
9.2 Entropy
For a distribution (p):
[
C_p(x)=-\log p(x).
]
The average is:
[
\mathbb E[-\log p(X)]=H(X).
]
So:
[
\boxed{
\text{entropia = complessità media rispetto alla distribuzione.}
}
]
9.3 Source coding
For optimal prefix-free codes:
[
H(X)\le \mathbb E[\ell(C(X))]<H(X)+1.
]
9.4 Typical set
For an ergodic source:
[
-\frac1n\log P(X_1,\dots,X_n)\to H.
]
The typical set has about:
[
2^{nH}
]
elements.
So:
[
H
]
is the exponent volume informative.
9.5 Channel capacity
A channel has capacity:
[
C=\max_{P_X}I(X;Y).
]
Interpretation:
[
\boxed{
\text{capacità = budget informazionale massimo trasferibile per uso del canale.}
}
]
If the rate (R>C), reliable transmission impossible.
9.6 Rate-distortion
[
R(D)=
\inf_{\mathbb E d(X,\hat X)\le D}I(X;\hat X).
]
Interpretation:
[
\boxed{
\text{costo minimo di presentazione entro errore }D.
}
]
This is the probable relative of the approximate complexity.

10. Kolmogorov bridge–altitudes
10.1 The bridge is not (K=h)
It is false that:
[
K(x)\approx h(x).
]
Against example:
[
x=2^{2^m}.
]
So...
[
h(x)=2^m\log2,
]
but:
[
K(x)\le K(m)+O(1)\approx \log m.
]
So:
[
\boxed{
\text{altezza e Kolmogorov sono complessità di presentazione diverse.}
}
]
10.2 Correct bridge: height volume
Date:
[
X_{\le B}={x:h(x)\le B},
]
[
N_X(B)=|X_{\le B}|,
]
you have:
[
K(x\mid B,X,h)\le \log_2N_X(B)+O(1).
]
And almost all (x\in X {\le B}) satisfy:
[
K(x\mid B,X,h)\ge \log_2N_X(B)-O(1).
]
So:
[
\boxed{
K_{\mathrm{tipico}}(x\mid h(x)\le B)
\approx
\log_2 |X_{\le B}|.
}
]
Examples:
(\mathbb P^1(\mathbb Q)):
[
N(B)\asymp B^2,
\quad
K_{\mathrm{tipico}}\approx 2\log_2 B.
]
(\mathbb P^n(\mathbb Q)):
[
N(B)\asymp B^{n+1},
\quad
K_{\mathrm{tipico}}\approx (n+1)\log_2B.
]
* Manin:
[
N_X(B)\sim cB^a(\log B)^{b-1}
]
implies:
[
K_{\mathrm{tipico}}\approx
a\log_2B+(b-1)\log_2\log B.
]
10.3 Arithmetic Deficiency-Kolmogorov
Define:
[
\boxed{
\delta_X(x;B)=
\log_2N_X(B)-K(x\mid B,X,h).
}
]
Interpretation:
* (\delta\approx0): (x) is generic in the height ball;
* (\delta\gg0): (x) is compressible, therefore potentially special.
This is a new central quantity.
10.4 Conjecture A: Arithmetic Kolmogorov Deficiency Principle
Native form:
[
\text{speciale}
\Rightarrow
\text{Kolmogorov-deficiente}.
]
The naive form is too vague. The correct and demonstration version is:
[
\boxed{
\text{modello semplice + volume minore}
\Rightarrow
\text{deficienza}.
}
]
Both (M\subseteq X) an arithmetic model with description (\kappa(M)). Both:
[
N_M(B)=|M\cap X_{\le B}|.
]
Se (x\in M_{\le B}), allora:
[
K(x\mid B,X,h)\le \kappa(M)+\log_2N_M(B)+O(1).
]
So:
[
\boxed{
\delta_X(x;B)
\ge
\log_2N_X(B)-\log_2N_M(B)-\kappa(M)-O(1).
}
]
If:
[
N_X(B)\asymp B^{a_X}(\log B)^{b_X},
]
[
N_M(B)\asymp B^{a_M}(\log B)^{b_M},
]
and (a M<a X), then:
[
\delta_X(x;B)
\ge
(a_X-a_M)\log_2B
+
(b_X-b_M)\log_2\log B
\kappa(M)
O(1).
]
Subvariety, thin sets, modular families, special locies, subgroups, automorphic lifts or subfamilies of fields produce deficiency if they have lower volume and short description.
10.5 Example: subspaces in (\mathbb P^n)
Both:
[
X=\mathbb P^n(\mathbb Q),
]
[
N_X(B)\asymp B^{n+1}.
]
If:
[
L\simeq\mathbb P^m\subset\mathbb P^n
]
is a rational subspace of fixed complexity:
[
N_L(B)\asymp B^{m+1}.
]
Per (x\in L_{\le B}):
[
\delta_X(x;B)
\ge
(n-m)\log_2B-O(1).
]
Deficiency measures volumetric codimensions.
10.6 Arithmetic structure function
Inspired by the structure function of Kolmogorov, we fix a class of geometric/arithmetic models (\mathcal G):
[
\mathcal G=
{\text{sottovarietà, sottogruppi, torsion cosets, thin maps, loci speciali, stack substacks, famiglie modulari, lift automorfi, ecc.}}.
]
We define:
[
\boxed{
S_x^{\mathcal G}(\alpha;B)
\min_{\substack{M\in\mathcal G\x\in M\\kappa(M)\le\alpha}}
\log_2N_M(B).
}
]
The total cost of the explanation is:
[
\Lambda_x^{\mathcal G}(\alpha;B)
\alpha+S_x^{\mathcal G}(\alpha;B).
]
A model (M) explains (x) with gain (t) if:
[
\kappa(M)+\log_2N_M(B)
\le
\log_2N_X(B)-t.
]
This is perhaps the new most important structure:
[
\boxed{
\text{un punto è aritmeticamente strutturato se appartiene a un modello semplice di volume residuo piccolo.}
}
]
10.7 Arithmetic Structure Theorem
The wish would be:
[
\delta_X(x;B)\gg0
\Rightarrow
x\text{ appartiene a un modello geometrico naturale di basso volume}.
]
But this is false without restrictions.
Reason: each point (x) belongs to the singleton ({x}), which has volume (1), but describe ({x}) coast (K(x)). In general algorithmic statistics, structure functions can be extremely arbitrary.
So you need a conditioned version:
[
\boxed{
\text{se la classe geometrica }\mathcal G
\text{ è completa rispetto alle compressioni rilevanti,}
}
]
Then:
[
\delta_X(x;B)\gg0
\Rightarrow
\exists M\in\mathcal G
\text{ che spiega }x.
]
The true mathematical content becomes to demonstrate, in specific contexts, that a natural class (\mathcal G) captures significant compressions.
10.8 Height priors
From an height you can build:
[
Z(s)=\sum_x e^{-s h(x)},
]
[
\mu_s(x)=\frac{e^{-s h(x)}}{Z(s)}.
]
So...
[
-\log\mu_s(x)=s h(x)+\log Z(s).
]
For random objects compared to this prior, (K(x)) can be near (-\log\mu s(x)). But this is a prior of height, not the universal probability of Solomonoff.
10.9 Small points and equity
Sequences of small points can equidistribute, but remain Kolmogorov-comprimibili.
Example: roots of unity. They have zero height and are equidistributed on the circle, but the yet another root is described with (\log n) bits.
So:
[
\text{equidistribuzione}
\not\Rightarrow
\text{Kolmogorov-randomness individuale}.
]
It serves a notion of deficiency compared to actual partitions and canonical measures.

11. Restricted-computation algebraic digits
11.1 Why (K) ordinary fails on algebraic figures
If (\alpha) is a real computable, in particular an algebraic number, then:
[
K(\alpha_1\ldots\alpha_n)\le K(n)+O(1)=O(\log n).
]
Just describe (n) and use the fixed algorithm that calculates (\alpha).
Therefore the complexity of ordinary Kolmogorov cannot measure the normality or randomness of the digits of the algebras.
It needs a small complexity:
[
\text{automi finiti},
\quad
\text{morfismi},
\quad
\text{pushdown automata},
\quad
\text{grammatiche},
\quad
\text{low-depth circuits},
\quad
\text{small space},
\quad
\text{time-bounded }K.
]
11.2 Deep known results
There are results of Adamczewski–Bugeaud and others according to which whole expansions of irrational algebraic numbers cannot have low combinatorial complexity of certain types.
In particular:
[
\text{bassa complessità di parole}
+
\text{Subspace Theorem}
\Rightarrow
\text{trascendenza}.
]
This is one of the most concrete and fertile bridges:
[
\boxed{
\text{teoria delle altezze/Subspace Theorem}
\Rightarrow
\text{lower bound per descrizioni computazionali ristrette}.
}
]
11.3 General programme
For a restricted computational class (\mathcal C), define:
[
K_{\mathcal C}(w)=
\min{\ell(M):M\in\mathcal C,\ M\text{ genera }w}.
]
For an irrational algebra (\alpha), study:
[
K_{\mathcal C}(\alpha_1\ldots\alpha_n).
]
General design:
[
\alpha\in\overline{\mathbb Q}\setminus\mathbb Q
\Rightarrow
\alpha_1\alpha_2\ldots
\text{ non è generabile da modelli computazionali troppo poveri}.
]
Demonstration scheme:
[
\text{bassa }\mathcal C\text{-complessità}
\Rightarrow
\text{ripetizioni/struttura combinatoria}
\Rightarrow
\text{approssimazioni razionali troppo buone}
\Rightarrow
\text{contraddizione con Subspace/Roth/Mahler/trascendenza}.
]
This frontier is very promising.

12. Height-bounded search
The heights say:
[
X_{\le B}\text{ è finito o controllabile}.
]
But they don't say how difficult it is.
* find a point,
* sample a point,
* generate a generic point,
* certify a point,
* enumerate all points.
We define:
[
K_B^T(x)
\min{|p|:U(p,B)=x\text{ in tempo }\le T(B)}.
]
Deficiency time-bounded:
[
\delta_X^T(x;B)
\log_2N_X(B)-K_B^T(x).
]
Counting:
[
|{x:K_B^T(x)\le k}|\le 2^{k+1}.
]
So, even with bound of time, almost all points of the ball require long descriptions than that resource.
Natural problems:
12.1 HB-Find
Given (B), find a (x\in X {\le B}) with properties (P).
12.2 HB-Sample
Sample almost uniformly from (X {\le B}).
12.3 HB-Enumerated
Enumera (X_{\le B}).
12.4 HB-Witness
Dato che esiste una soluzione di altezza (\le B), producila.
Principio nuovo:
[
\boxed{
\text{altezza piccola non implica ricerca facile.}
}
]
This is a computational dimension absent in the classical theory of heights.

13. Height machine automorphic and Galoisiana
13.1 Motivation
For automorphic representations and Galoisian serves a theory similar to heights.
The natural candidate is the conductor:
* arithmetic conductor,
* analytical conductor,
* discriminatory,
* branching,
* archimedei parameters,
* weights,
* coefficient field.
13.2 Objects
Automorphic side:
[
\pi\in\mathcal A(G,F).
]
Galoisian side:
[
\rho:\operatorname{Gal}(\overline F/F)\to {}^LG.
]
13.3 Automorphic height profile
It's not enough. Serves:
[
H_{\mathrm{aut}}(\pi)=
(
G,F,
\log C_{\mathrm{an}}(\pi),
\text{central character},
\text{archimedean type},
\text{coefficient field},
K(\pi)
).
]
For Galois:
[
H_{\mathrm{Gal}}(\rho)=
(
\dim\rho,
\log N\mathfrak f(\rho),
\text{ramification filtration},
\text{Hodge--Tate weights},
\text{coefficient field},
K(\rho)
).
]
13.4 desired axioms
A1. Northcott automorphic
For (G,F) fixed:
[
{\pi:C(\pi)\le Q}
]
must be finished or have controlled volume.
A2. Location
[
C(\pi)=\prod_v C_v(\pi_v).
]
A3. Controlled function
For a map (L)-group:
[
r:{}^LG\to {}^LH,
]
if the lift (r *\pi) exists:
[
h_H(r_*\pi)\le A_r h_G(\pi)+O_r(1).
]
A4. Controlled operators
We want estimates like:
[
h(\pi^\vee)=h(\pi)+O(1),
]
[
h(\pi\otimes\chi)\le h(\pi)+n h(\chi)+O(1),
]
[
h(\pi\boxplus\sigma)\le h(\pi)+h(\sigma)+O(1),
]
[
h(\pi\boxtimes\sigma)
\le
(\dim\sigma)h(\pi)+(\dim\pi)h(\sigma)+O(1).
]
A5. Volume/Weyl law
Serve:
[
|\mathfrak F(Q)|\sim \text{termine principale}.
]
A6. Distribution
Host families should have limit measures:
[
\text{Plancherel},
\quad
\text{Sato--Tate},
\quad
\text{misure automorfe canoniche}.
]
13.5 Deficiency of functoral lifts
Both:
[
r:{}^LG\to{}^LH
]
a functorial lift with:
[
h_H(r_*\pi)\le A_r h_G(\pi)+O(1).
]
Suppose:
[
|\mathfrak F_G(Q)|\asymp Q^{a_G}(\log Q)^{b_G},
]
[
|\mathfrak F_H(Q)|\asymp Q^{a_H}(\log Q)^{b_H}.
]
Then a lift:
[
\Pi=r_*\pi
]
is described through (\pi), so it has deficiency in the target family if:
[
a_H>\frac{a_G}{A_r}.
]
Interpretation:
[
\boxed{
\text{lift functoriali/endoscopici/base change/CM}
\Rightarrow
\text{sottofamiglie Kolmogorov-deficienti}.
}
]
13.6 Galois and Malle
For numerical fields:
[
h_{\mathrm{Gal}}(L)=\log|\mathrm{Disc}(L)|.
]
For a group (G), define:
[
\mathcal F_G(X)=
{L/F:\operatorname{Gal}(L^{\mathrm{gal}}/F)\simeq G,\ |\mathrm{Disc}(L)|\le X}.
]
Deficiency:
[
\delta_G(L;X)
\log_2|\mathcal F_G(X)|
K(L\mid X,G,F).
]
Parametric subfamilies, towers, composites, families with common subfield or special branching should be deficiencies.
This can become a diagnostic tool in arithmetic statistics.

14. New natural presentations in various areas
14.1 Theory of Numbers
Objects:
[
\text{numeri algebrici},
\quad
\text{campi numerici},
\quad
\text{curve},
\quad
\text{forme modulari},
\quad
L\text{-funzioni}.
]
Profile:
[
C(x)=
(\text{altezza},
\text{grado},
\text{discriminante},
\text{conduttore},
\text{ramificazione},
K(x),
K^T(x)).
]
14.2 Theory of Galois
Objects:
[
G\text{-torsori},
\quad
\text{estensioni},
\quad
\text{rappresentazioni Galoisiane}.
]
Profile:
[
C(T)=
(
\log|\mathrm{Disc}|,
\text{ramification profile},
\text{subfield lattice},
K(T)
).
]
14.3 Groups
For finitely generated groups:
[
C_G(g)=\ell_S(g).
]
Volume:
[
N_G(n)=|{g:\ell_S(g)\le n}|.
]
A typical element of the ball has:
[
K(g\mid n,G,S)\approx\log N_G(n).
]
In polynomial growth groups:
[
K_{\mathrm{tipico}}\approx d\log n.
]
In exponential growth groups:
[
K_{\mathrm{tipico}}\approx cn.
]
High Deficiency reports membership of subgroups, centralizers, cosits, special words.
14.4 Switching rings and algebra
For:
[
R=k[x_1,\dots,x_n]/I,
]
profile:
[
C(R)=
(n,
\deg\text{ generatori},
h(\text{coefficienti}),
\text{Betti table},
K(I)).
]
Operators:
[
R/I,
\quad
R_f,
\quad
R\otimes S,
\quad
\operatorname{Tor},
\quad
\operatorname{Ext}.
]
14.5 Algebraic geometry
For:
[
X\subseteq\mathbb P^n,
]
profile:
[
C(X)=
(n,\deg X,h(\text{equazioni}),\text{Hilbert polynomial},K(X)).
]
For points:
[
C(P)=(h_X(P),K(P),\delta_X(P;B)).
]
Structure function:
[
S_P^{\mathrm{geom}}(\alpha;B)
\min_{\substack{Y\ni P\K(Y)\le\alpha}}
\log N_Y(B).
]
14.6 Theory of modules
Objects:
[
\text{curve},
\quad
\text{varietà abeliane},
\quad
\text{K3},
\quad
G\text{-bundles},
\quad
\text{stacks}.
]
Profile:
[
C(M)=
(
\text{altezza moduli},
\text{automorphism complexity},
\text{level structure},
K(M)
).
]
The stack heights are one of the most mature achievements of the program.
14.7 Representations
For a representation:
[
C(\rho)=
(
\dim\rho,
h(\chi_\rho),
\text{conduttore},
\text{campo dei coefficienti},
K(\rho)
).
]
For quiver:
[
C(M)=
(
\vec d,
\dim\operatorname{End}M,
\dim\operatorname{Ext}^1(M,M),
K(M)
).
]
Operators:
[
\oplus,
\quad
\otimes,
\quad
\operatorname{Ind},
\quad
\operatorname{Res},
\quad
\operatorname{Ext}.
]
14.8 Differential equations and (D)-modules
For:
[
L=\sum_{i=0}^r a_i(x)\partial^i,
]
profile:
[
C(L)=
(
r,
\max\deg a_i,
h(a_i),
\text{singular divisor},
\text{irregularity},
K(L)
).
]
Operators:
[
\text{pullback},
\quad
\text{tensor product},
\quad
\text{Fourier--Laplace},
\quad
\text{middle convolution}.
]
Objective:
[
\text{monodromia/Stokes data troppo complessi}
\Rightarrow
\text{non provenienza da equazioni semplici}.
]
14.9 Dynamic systems
For a map:
[
f:X\to X,
]
profile:
[
C(f)=(\deg f,h(f),\lambda_1(f),K(f)).
]
For one point:
[
C(P)=(h(P),\widehat h_f(P),K(P),\delta_{\mathrm{orbit}}(P,n)).
]
Orbital Deficiency:
[
\delta_{\mathrm{orbit}}(P,n)
\log N_{\mathrm{orbit}}(n)-K(f^n(P)\mid f,n).
]
It is necessary to distinguish generic orbits from preperiodic, special or compressible orbits.
14.10 Logic, models and demonstrations
For a test system:
[
C_\Pi(\varphi)=
\min{\ell(p):p\text{ prova }\varphi}.
]
For finite logic:
[
C_{\mathrm{logic}}(P)
\min{\text{quantifier rank, variabili, depth}:P\text{ definibile}}.
]
For models:
[
C(M)=
\min{\ell(\varphi):\varphi\text{ definisce }M}.
]
Proof complexity:
[
\text{prova corta}
\Rightarrow
\text{certificato/test/invariante povero}.
]
Lower bound:
[
\text{invariante necessario alto}
\Rightarrow
\text{prova lunga}.
]
14.11 Graphs
Profile:
[
C(G)=
(
|V|,
|E|,
\mathrm{tw}(G),
\mathrm{cw}(G),
K(G)
).
]
Operators:
[
\text{minor},
\quad
\text{subdivision},
\quad
\text{join},
\quad
\text{graph product}.
]
Deficiency:
[
\delta_{\mathcal G}(G;n)
\log|\mathcal G_n|-K(G\mid n,\mathcal G).
]
Planar graphs, bounded treewidth, Cayley graphs, strongly regular graphs, graph classes lower-closed are potential sources of deficiency.
14.12 Algebraic topology and low size
Presentations:
[
C(X)=
\min{#\text{celle in un CW complex che presenta }X},
]
[
C(M)=
\min{#\text{tetraedri in una triangolazione di }M}.
]
Operators:
[
#,
\quad
\text{surgery},
\quad
\text{covering},
\quad
\text{mapping torus}.
]
Objective:
[
\text{una topological height machine}
]
with property type:
[
C(M#N)=C(M)+C(N)+O(1),
]
[
C(\text{surgery}(M,K,r))\le \Phi(C(M),C(K),h(r)).
]
14.13 Analysis, PDE, continuous geometry
Approximate complexity:
[
C_\varepsilon(f)=
\min{\ell(d):|f-\pi(d)|\le\varepsilon}.
]
Substitutes of Northcott:
[
\text{compattezza},
\quad
\text{precompattezza},
\quad
\text{metric entropy},
\quad
\text{covering numbers}.
]
Objects:
[
\text{funzioni},
\quad
\text{soluzioni PDE},
\quad
\text{misure},
\quad
\text{flussi},
\quad
\text{operatori}.
]
Possible principle:
[
\text{ansatz troppo semplice}
\Rightarrow
\text{non approssima genericamente la soluzione}.
]

15. Projects and programmes
15.1 Conjecture A correct
[
\boxed{
\text{modello aritmetico semplice + volume minore}
\Rightarrow
\text{deficienza Kolmogoroviana}.
}
]
This is demonstrated by the counting:
[
K(x)\le \kappa(M)+\log N_M(B)+O(1).
]
15.2 Arithmetic Structure Theorem
desired shape:
[
\delta_X(x;B)\gg0
\Rightarrow
x\text{ appartiene a un modello geometrico naturale semplice}.
]
But it is false without restrictions.
Correct version:
[
\boxed{
\text{relativa a una classe naturale }\mathcal G
\text{ di modelli.}
}
]
The real problem is to demonstrate that (\mathcal G) captures arithmeticly significant compressions.
15.3 Restricted-computation algebraic digits
For each irrational algebra (\alpha), its expansion based (b) should be complex compared to each subuniverse natural computational model:
[
\text{finite automata},
\quad
\text{morfismi},
\quad
\text{pushdown},
\quad
\text{small circuits},
\quad
\text{small space}.
]
The strategy is:
[
\text{bassa complessità ristretta}
\Rightarrow
\text{struttura combinatoria}
\Rightarrow
\text{approssimazione diofantea troppo buona}
\Rightarrow
\text{trascendenza}.
]
15.4 Height-bounded search complexity
Define:
[
K_B^T(x)
]
for height points (\le B).
Central issue:
[
\text{altezza piccola}
\not\Rightarrow
\text{facile da trovare}.
]
Study:
* finding,
* sampling,
* enumeration,
* witnessing,
* average-case hardness in the balls of height.
15.5 Langlands/automorphic height machine
Build a height machine for automorphic/Galoisiane representations:
[
H_{\mathrm{aut}}(\pi),
\qquad
H_{\mathrm{Gal}}(\rho),
]
with:
* Northcott/volume,
* location,
* controlled functoriality,
* tensoral operators,
* Weyl laws,
* equidistribution,
* deficiencies of special subfamilies.
15.6 Galois/statistic deficiency
For families of fields:
[
\delta_G(L;X)=
\log|\mathcal F_G(X)|-K(L\mid X,G,F).
]
Objective:
[
\text{sottofamiglie anomale}
\leftrightarrow
\text{deficienza algoritmica}.
]

16. Severe evaluation of the programme
16.1 Originality
The separate bricks are not original:
* heights,
* Kolmogorov,
* resource-bounded complexity,
* entropy,
* height zeta,
* Northcott,
* filtration,
* enriched/filtered categories,
* proof complexity
* finite model theory,
* game comonads,
* circuit lower bounds,
* metric entropy.
The originality possible is in the package:
[
\boxed{
\text{presentazioni controllate}
+
\text{volumi di altezza}
+
\text{deficienza Kolmogoroviana}
+
\text{structure function aritmetica}
+
\text{search complexity}
}
]
as a unified language.
16.2 Real Fertility
The most fertile directions seem:
1. Structure function arithmetic for special subvarieties, thin sets, modules, Malle/Manin.
2. Restricted algebraic digits, where there are already deep results.
3. Height-bounded search, because it adds a new computational dimension.
4. Height machine automorph/Galoisiana, because the conductor is already a height-like quantity.
5. Stack heights and arithmetic statistics, because they are already a real bridge between Manin and Malle.
6. Deficiency in families ordered by height, as a quantitative measure of specialty.
16.3 Sterility risk
The risk is high if formalism remains:
[
C(Fx)\le\Phi(Cx)
\Rightarrow
\text{ostruzione}.
]
This, alone, is often only a rewriting.
To be fertile must produce at least one between:
1. a new natural presentation;
2. a property of new Northcott;
3. a new volume law;
4. a Canoncal height new;
5. a transfer of lower bound not obvious;
6. a new control inequality;
7. a measure of useful specialties;
8. an effective link between heights and computational complexity.

17. Severe summary table
Result Status Theme obtained Fertility
General Formalism Valid but risk tautology Controlled normative presentations Media
No-go universal complexity Solido (K\ne h), no absolute complexity High as bond
Rilette bene Height machine = arithmetic functoral presentations Media
Kolmogorov Fine collar Universal machine = actual terminal presentation Media
Bridge (K)-highness Strong in volumetric form (K {\mathrm{tipico} ♪ N(B) High
Arithmetic deficiency New central quantity (\delta X=\log N X-K) High
Conjecture A Vera only in correct form simple model + smaller volume (\Rightarrow) deficiency High
Structure theorem Not universal serves geometric class (\mathcal G) High but difficult
Restricted digits Very promising Subspace Theorem (\Rightarrow) lower bound computational restricted Very high
Height-bounded search New frontier adds operating cost to the heights High
Automorphic height machine Partially existing analytical conductor + controlled functoriality Very high
Galois/Malle/stacks Already discriminatory royal frontier as height stacky Alta
Analysis PDE Approximate version only (C \varepsilon), metric entropy Media
Topology/groups/graphs Promising but various volume of balls, word length, triangular media-high
Royal sterile risk avoid pure categorylization High
18. Final Program Formula
The mature formulation is:
[
\boxed{
\textbf{una complessità utile è il costo minimo di una presentazione naturale.}
}
]
A demonstration theory requires:
[
\boxed{
\text{palle controllabili}
+
\text{operatori controllati}
+
\text{volume}
+
\text{trasferimento di lower bound}.
}
]
The correct bridge between heights and Kolmogorov is:
[
\boxed{
\text{altezza} \Rightarrow \text{volume delle palle};
}
]
[
\boxed{
\text{volume delle palle} \Rightarrow \text{Kolmogorov complexity tipica};
}
]
[
\boxed{
\text{modelli piccoli} \Rightarrow \text{deficienza};
}
]
[
\boxed{
\text{deficienza persistente} \Rightarrow \text{cercare struttura geometrica}.
}
]
The theory does not say:
[
K(x)=h(x).
]
He says:
[
\boxed{
K_{\mathrm{tipico}}(x\mid h(x)\le B)
\approx
\log |{y:h(y)\le B}|.
}
]
And introduces:
[
\boxed{
\delta_X(x;B)
\log |X_{\le B}|-K(x\mid B)
}
]
as an individual measure of specialty.
The most compact form of the program is:
[
\boxed{
\textbf{specialità = compressibilità rispetto al volume naturale di altezza.}
}
]
But with a fundamental caution:
[
\boxed{
\text{il converso richiede una classe naturale di modelli geometrici;}
}
]
otherwise the theory collapses in general algorithmic statistics and loses arithmetic content.

19. What remains to do
The next mathematically promising moves are:
1. Formalize a concrete category of geometric patterns (\mathcal G) for specific cases:
[
\mathbb P^n,\quad
\text{varietà toriche},\quad
\text{varietà abeliane},\quad
\text{Shimura varieties},\quad
\text{stack }BG.
]
2. Demonstrare structure theorem locale:
[
\delta_X(x;B)\gg0
\Rightarrow
x\in M\in\mathcal G
]
for narrow classes of models.
3. Develop arithmetic structure functions computabili:
[
S_x^{\mathcal G}(\alpha;B).
]
4. Connect thin sets, exceptional sets of Manin, special subvarieties and unlikely intersections to deficiencies.
5. Extend the results on the algebraic figures from automatons/morphisms/pushdown to stronger computational models.
6. Define and study:
[
K_B^T(x)
]
in concrete diphants contexts.
7. Build a height machine automorphic:
[
H_{\mathrm{aut}}(\pi)
]
with analytical conductor, branching, archimedei parameters and functoriality.
8. Build a height machine Galoisiana/stacky:
[
H_{\mathrm{Gal}}(\rho),
\quad
H(BG),
\quad
\delta_G(L;X).
]
9. Search for new Northcott properties in non-classical areas:
* Low dimensional topology,
* derived categories,
* (D)-modules,
* dynamic systems,
* representations,
* PDE via metric entropy.
10. Avoid the trap of doing only “rephrasing category”: each new definition must produce at least one finiteness, a volume estimate, a lower bound or an unobtrusive transfer.

20. Ultra-compact summary
The program develops a theory of demonstrative complexity based on standard presentations. An object is complex if every allowed presentation costs a lot. The theories of Kolmogorov, heights, information, algorithms, proof complexity and computational resources are instances of this scheme.
Useful formalism requires:
[
\text{budget}
+
\text{presentazioni}
+
\text{palle}
+
\text{properness}
+
\text{operatori controllati}
+
\text{volumi}
+
\text{ostruzioni}.
]
The theory of heights does not coincide with Kolmogorov. The correct bridge is:
[
K_{\mathrm{tipico}}(x\mid h(x)\le B)
\approx
\log |X_{\le B}|.
]
From here comes the deficiency:
[
\delta_X(x;B)=
\log|X_{\le B}|-K(x\mid B),
]
that measures how much (x) is compressible compared to the natural ball of height.
A simple model (M\subseteq X) with smaller volume produces deficiency:
[
x\in M_{\le B}
\Rightarrow
\delta_X(x;B)
\ge
\log N_X(B)-\log N_M(B)-\kappa(M)-O(1).
]
This formalizes:
[
\text{speciale}
\Rightarrow
\text{comprimibile}.
]
The converse is the real problem:
[
\text{comprimibile}
\Rightarrow
\text{speciale?}
]
It is false without narrowing the patterns; it becomes a possible arithmetic structure theorem only compared to a natural class (\mathcal G) of geometric patterns.
The most promising borders are:
[
\text{structure function aritmetica},
]
[
\text{restricted-computation algebraic digits},
]
[
\text{height-bounded search complexity},
]
[
\text{height machine automorfa/Galoisiana},
]
[
\text{stack heights e arithmetic statistics}.
]
The final motto is:
[
\boxed{
\textbf{specialità matematica come compressione rispetto al volume naturale di altezza.}
}
]
And the critical bond is:
[
\boxed{
\textbf{nessuna nuova teoria è utile se non produce nuove finitezze, volumi, lower bound o trasferimenti.}
}
]

————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————

Operating state to continue the program.
The next phase should not yet expand formalism in abstract. You need to fix a concrete lab and prove non-tautologic theorems. The cleanest candidate is
X
== sync, corrected by elderman ==
P
No
(
Q
)
X=\mathbb P^n(\mathbb Q)
X=Pn(Q), con altezza proiettiva usuale e modelli
G
\mathcal G
G costituiti da sottovarietà razionali di grado e altezza controllati. L’obiettivo è studiare la function aritmetica
S
x
G
(
α
;
B
)
=
min
⁡
Y
∋
x
K
(
Y
)
≤
α
log
⁡
∣
Y
(
Q
)
≤
B
∣
S_x^{\mathcal G}(\alpha;B) = \min_{\substack{Y\ni x\\K(Y)\le \alpha}} \log |Y(\mathbb Q)_{\le B}|
SxG (α;B)=Y∋xK(Y)≤α min log∣Y(Q)≤B ∣
e capire quando una grande deficienza
δ
X
(
x
;
B
)
=
log
⁡
∣
X
≤
B
∣
−
K
(
x
∣
B
)
\delta_X(x;B)=\log |X_{\le B}|-K(x\mid B)
δX (x;B)=log∣X≤B ∣−K(x∣B)
forza l’esistenza di una relazione geometrica semplice: sottospazio, ipersuperficie di piccolo grado, thin map, sottovarietà speciale, famiglia parametrica.
La regola metodologica è severa: nessuna nuova definizione va accettata se non produce una stima di volume, una finitezza, un lower bound, una canonicalizzazione, o un trasferimento non ovvio. Il rischio principale resta la categorializzazione sterile.
A second handoff 
Automatic English translation generated from the Italian original. Mathematical notation and formula blocks are intentionally left close to the source.

Complexity 2.5.lib

Note of complete handoff — Atlas of finitary descriptive systems, budget obstructions and finite observers
This note serves to resume the project from scratch, as if those who read did not have access to the previous conversation. Summary of philosophy, critical diagnosis, formalism, system library, technical corrections, finite observer theory, pilot borders and next steps.

0. Provisional name of the project
The most suitable names are:
[
\boxed{\text{Atlante di sistemi descrittivi finitarî}}
]
or:
[
\boxed{\text{Teoria delle ostruzioni filtrate da budget}}
]
or, in English:
[
\boxed{\text{Budgeted Obstruction Systems}}
]
The project should not be presented as “general mathematical theory of complexity”. This name would be too wide, too vague, and would create wrong expectations.
The most sober and defendable name is:
[
\boxed{\text{Atlante di sistemi descrittivi finitarî}}
]
because the heart of the project is to build and compare many local systems, not a single universal complexity.

1. Original philosophical motivation
The starting intuition is to formalize statements such as:
[
\text{“questo oggetto non può essere la risposta perché è troppo complesso.”}
]
or:
[
\text{“questo controesempio non può essere ottenuto dai processi ammessi entro questo budget.”}
]
or:
[
\text{“se la congettura è falsa, allora dovrebbe esserci un controesempio abbastanza semplice da cercare in una palla finita.”}
]
Initial examples:
[
\frac12+\frac13\ne \frac{37}{43}
]
because, using rational height
[
H(a/b)=\max(|a|,|b|)
]
in reduced form, a sum of small-height rationales cannot arbitrarily produce a much higher level rationale. More precisely:
[
H(x+y)\le 2H(x)H(y).
]
So:
[
H(1/2)=2,\qquad H(1/3)=3,
]
and therefore:
[
H(1/2+1/3)\le 12,
]
While:
[
H(37/43)=43.
]
Other example:
[
\sqrt2\notin \mathbb Q.
]
Here the best explanation is not “high too high”, but an invariant (2)-adica. If:
[
\sqrt2=\frac ab
]
(\gcd(a,b)=1), then:
[
a^2=2b^2.
]
Applying (v 2):
[
2v_2(a)=1+2v_2(b),
]
equal to odds, impossible.
This immediately shows that complexity should not be a single number. It often has to be an invariant profile.

2. Severe diagnosis on originality
The naive version of the project:
[
\text{“costruire una teoria generale della complessità degli oggetti matematici”}
]
is too wide and it is not yet a new theory.
The core:
[
\text{oggetti}+\text{budget}+\text{processi ammessi}+\text{monotoni}+\text{ostruzioni}
]
is already close to many known ideas: resource theories, monotonous invariants, filtered categories, Kolmogorov complexity, height theory, proof complexity, automi, finite logic, etc.
So the project is not original if it is presented as:
[
\text{“ho scoperto che molte teorie parlano di complessità.”}
]
That's true, but it's too weak.
The promising version is:
[
\boxed{
\text{classificare sistemi descrittivi effettivamente finitarî e usarli come macchine di ostruzione.}
}
]
The possible originality begins when you get:
1. robust definitions;
2. general non-tautological issues;
3. systematic recovery of classical theorems;
4. transfers between different systems;
5. principles of small counter-example for specific classes;
6. new lower bound or new obstructions.
The honest verdict is:
[
\boxed{
\text{non c’è ancora un breakthrough;}
}
]
but:
[
\boxed{
\text{c’è un programma tecnico plausibile, se ristretto a sistemi locali, finitarî e decidibili.}
}
]

3. Mature central principle
The central principle is not:
[
\text{“ogni oggetto ha una complessità vera.”}
]
It is:
[
\boxed{
\text{un sistema descrittivo finitario trasforma un bound di semplicità in una lista finita di oggetti testabili.}
}
]
And the highest form of the program is:
[
\boxed{
\text{dimostrare principi di piccolo controesempio e teoremi di trasferimento tra sistemi descrittivi diversi.}
}
]

4. Basic formalism: descriptive systems
A descriptive system is a quadruple:
[
\mathcal D=(D,\ell,\llbracket-\rrbracket,X),
]
where:
* (D) is the set of descriptions;
* (\ell:D\to \mathbb N) is the description size;
* (\llbracket-\rrbracket:D\rightharpoonup X) is semantic, possibly partial;
* (X) is the space of the objects described.
Induced complexity is:
[
K_{\mathcal D}(x)
\min{\ell(d):\llbracket d\rrbracket=x}.
]
The radius ball (b) is:
[
\mathcal B_{\mathcal D}(b)
{x\in X:K_{\mathcal D}(x)\le b}.
]
The project requires that these balls are finished, better yet effectively enumerable.

5. Systems actually finite
A descriptive system (\mathcal D) is actually finirio if:
1. for each (b), the set
[
D_{\le b}={d\in D:\ell(d)\le b}
]
is finished;
1. (D {\le b}) is actually enumerable;
2. given (d), is decidable if (\llbracket d\rrbracket) is defined;
3. if defined, (\llbracket d\rrbracket) is calculated in an effective representation of (X);
4. equality in (X) is decidable, at least for generated objects.
Lemma base:
[
\boxed{
\mathcal D\text{ effettivamente finitario}
\Rightarrow
K_{\mathcal D}(x)>b\text{ è decidibile.}
}
]
Demonstration: enumerate all descriptions (d\in D {\le b}), calculate those defined, and check if someone denotes (x).
This lemma is elementary, but basic.

6. Budget stairs
A budget can live in an ordered monoid:
[
(B,\le,0,\oplus).
]
Examples:
[
(\mathbb N,\le,0,+),
]
[
(\mathbb R_{\ge0},\le,0,+),
]
[
(\mathbb N^k,\le_{\mathrm{coord}},0,+).
]
The important point is:
[
\boxed{
\text{la complessità giusta è spesso un profilo, non un numero.}
}
]
For example:
[
C(x)=(\text{bit-length},\text{altezza},\text{grado},\text{SLP-size},v_p,\text{proof length}).
]

7. Controlled operators
Both:
[
F:X\to Y.
]
With complexity:
[
C_X:X\to B_X,\qquad C_Y:Y\to B_Y.
]
Saying that (F) is controlled means having:
[
C_Y(F(x))\le \Phi(C_X(x)).
]
To avoid excessive elasticity, (\Phi) should not be an arbitrary monotonous function. It is necessary to fix an admissible class (\mathcal A) of controls:
[
\Phi\in\mathcal A.
]
Possible classes:
* monotonous computable functions;
* recurring primitive functions;
* elementary functions;
* polynomial functions;
* linear/additive functions.
More robust definition:
[
F\text{ è }\mathcal A\text{-controllato}
]
if it exists:
[
\Phi\in\mathcal A
]
such that:
[
C_Y(F(x))\le \Phi(C_X(x)).
]
Obstruction Lemma:
[
C_Y(y)>\Phi(b)
\Rightarrow
y\notin F(X_{\le b}).
]

8. No-go basic
8.1 There is no actual general theory of small counterparts
Suppose we have a general instrument that, given a conjecture:
[
\forall n,P(n),
]
produces a finite set (S P) such that:
[
\exists n,\neg P(n)
\Rightarrow
\exists n\in S_P,\neg P(n).
]
Then we could decide the problem of arrest.
Given a programme (M), consider:
[
P(t)=\text{“}M\text{ non si è arrestato entro il tempo }t\text{”}.
]
If the method produced (S M), it would be enough to control those times. If no one is against example, (M) does not stop. Impossible.
So:
[
\boxed{
\text{non esiste un metodo generale effettivo che riduca ogni congettura a finiti controesempi candidati.}
}
]

8.2 “The minimum against example” is not bounded
A description as:
[
\text{“il minimo controesempio alla congettura }C\text{”}
]
is short if (C) is short. But knowing if you denote something is like knowing if the conjecture is false. This leads to problems like Berry/Chaitin and the problem of arrest.
It is forbidden to use:
[
\mu n:\neg P(n)
]
without bound.
It is admitted:
[
\mu n<N:\neg P(n),
]
if (N) is explicitly described and (P) belongs to an encoded class of decidable preachers.

8.3 Non-adjustability is not non-existence
Demonstrate:
[
x\notin \mathcal B_{\mathcal D}(b)
]
means:
[
x\text{ non è descrivibile entro budget }b\text{ nel sistema }\mathcal D.
]
It does not mean that (x) does not exist.
To prove non-existence of counterexamples, a further theorem is needed:
[
\text{se un controesempio esiste, allora ne esiste uno in }\mathcal B_{\mathcal D}(b).
]
This is a principle of small counter-example.

8.4 Simple output does not imply simple input
From:
[
C(F(x))\text{ basso}
]
do not follow:
[
C(x)\text{ basso}.
]
Operators can compress, delete, project, forget information.
The safe direction is:
[
C(x)\text{ basso}
\Rightarrow
C(F(x))\text{ controllato}.
]

9. Bounded Minimization Correct
The naive form:
[
\mu n<N:P(n),
\qquad
P\text{ decidibile}
]
is not strong enough.
It serves a class encoded by preachers:
[
\mathcal P=(E,\ell_E,(P_e)_{e\in E}),
]
where:
* (E) is a set of codes;
* (\ell_E:E\to\mathbb N);
* per ogni (b),
[
E_{\le b}={e:\ell_E(e)\le b}
]
is finished and enumerable;
* each (P e(n)) is decidable.
Then the safe operator is:
[
(e,N)\mapsto \mu n<N:P_e(n).
]
Terrority comes from the finiteness of codes (e) and bounds (N), not from a vague external decidability.
Lemma:
If (\mathcal P) is a finite encoded class of decidable preachers and bounds (N) come from an actually finite system, then the extension with:
[
\mu n<N:P_e(n)
]
remains actually finite.

10. Types of obstruction
10.1 punctual obstruction
[
C(y)>\Phi(C(x))
\Rightarrow
y\ne F(x).
]
10.2 Endurance obstruction
[
\exists x,P(x)
\Rightarrow
\exists x\in X_{\le b},P(x).
]
If (X {\le b}) is finished, the problem is reduced to finite control.
10.3 Compressed obstruction
[
S\Rightarrow K(x)\le b,
\qquad
K(x)>b
\Rightarrow
\neg S.
]
10.4 Intestinal obstruction
If:
[
|\mathrm{Costruibili}{\le b}|\ll |X{\le b}|,
]
then almost all objects are not built within that budget.
10.5 Separative obstruction
[
x\equiv_b y,
\qquad
P(x)\ne P(y).
]
Then (P) is not decidable/observable within budget (b).
10.6 Certificate obstruction
[
C_{\mathrm{proof}}(\varphi)>b.
]
10.7 Probability obstruction
A simple model causes too tight distributions to explain certain events.

11. Library of descriptive systems: order of priority
The library is wide, but the next phase should not be expanded further. Priority is to develop pilot systems.
11.1 Priority pilot schemes
The most promising systems are now:
[
\boxed{
\text{bounded minimization, Presburger, altezze algebriche, SLP + altezza, dinamica + altezza, osservatori modulari/CRT.}
}
]
A. Bounded minimization
Descriptions:
[
(e,N)\mapsto \mu n<N:P_e(n).
]
Strong because it securely formalizes “the minimum example under a bound”.
B. Presburger unique definers
Formulas in language:
[
(\mathbb N,+,<,0,1,\equiv_m)
]
that define a single natural.
Strong because decidable, finite, and connected to semi-linearity and periodicity.
C. Algebraic heights
Complexity:
[
C(\alpha)=(\deg\alpha,h(\alpha)).
]
Strong because it has true fineness type Northcott: degree and bounded height give finite sets.
D. SLP + height + local profiles
Hybrid system:
[
C(n)=(\tau(n),h(n),\text{profilo }p\text{-adico},\text{residui CRT}).
]
Strong because it can connect short algorithmic descriptions and arithmetic invariants.
E. Dynamics + height
Descriptions:
[
x=f^{\circ k}(a).
]
Complexity:
[
C(x)=C(f)+C(a)+C(k)+h(x).
]
Strong for dynamic problems, including Collatz systems.
F. Collatz-word descriptors
Words ended in operators like:
[
O(n)=n/2,
\qquad
E(n)=(3n+1)/2.
]
One word (E/O) is:
[
\text{classe residua modulo }2^k
\leftrightarrow
\text{mappa affine}
\leftrightarrow
\text{cilindro }2\text{-adico}.
]

11.2 Other important library systems
* integer complexity with (1,+,\times);
* addition chains;
* addition-subtraction chains;
* positional notation;
* scattered notation;
* continuous fractions;
* Egyptian fractions;
* rational (a/b) with height;
* rational expressions (1,+,-,\times,/);
* expressions with exponentiation;
* factorization;
* CRT;
* profiles (p)-adici;
* algebraic numbers via polynomial and insulating;
* numerical fields fixed;
* field towers;
* radicals;
* line and compact;
* origami;
* zero-dimensional polynomial systems;
* basics of Gröbner;
* resultants;
* algebraic curves;
* elliptical curves;
* square forms;
* DFA singleton;
* regex with representatives;
* straight-line grammages for strings;
* automatic sequences;
* finished transducers;
* MSO on words;
* MSO on trees;
* game comonads;
* graph bounded treewidth;
* graph grammars;
* matroids;
* permutations by pattern;
* rational polytopes;
* reticular polytopes;
* Ehrhart;
* Newton polytopes;
* tropical geometry;
* simplicial complexes;
* knots;
* 3-variety;
* finitely generated groups;
* SLP in groups;
* finite monoids;
* finite categories;
* work;
* linear occurrences;
* high-powered matrices;
* rational generation functions;
* algebraic generating functions;
* holonomic sequences;
* automata bounded-time cell phone;
* rewriting ending;
* proof-witness compatibility;
* resolution;
* Nullstellensatz certifieds;
* Ideal Proof System;
* SOS certificates;
* Boolean circuits;
* arithmetic circuits;
* decision trees;
* communication protocols;
* branching programs;
* integer linear programming;
* SDP rational bounded;
* latex reduction;
* local descriptors;
* Hensel lifts;
* adelic height profiles;
* rational finite distributions;
* finished Markov chains;
* graphical models;
* MDL models;
* empirical types;
* primitive recursive descriptions;
* Grzegorczyk isolated;
* fast-growing hierarchy;
* lambda tipati terms;
* type theory restricted.

11.3 Systems to avoid or use only as meta-inspiration
Arbitration Turing Programs
Syntactically finite balls, but halting and undecided equality. Kolmogorov cannot be computable.
Peano Arithmetic Formules that define a single number
Too expressive. Definibility and lower bound glue against incompleteness/Berry/Chaitin.
Minim against unbounded example
[
\mu n:\neg P(n)
]
banned in the operating core.
Free special functions
[
\sin,\cos,\exp,\Gamma,\zeta,\ldots
]
without decitable equality theory. Use only certified subclasses.

12. Theory of finite observers
The theory of finite observers became the most promising technical nucleus.
12.1 Definition
A finite observer on (X) is a computable map:
[
\pi:X\to A,
]
where (A) is an actual finite set.
Examples:
[
\pi_m(n)=n\bmod m.
]
[
\pi_p(a/b)=[a:b]\in\mathbb P^1(\mathbb F_p).
]
[
\pi_{\mathfrak p}(\alpha)=\alpha\bmod\mathfrak p.
]
[
\pi_A(w)=\text{stato finale di un DFA su }w.
]
[
\pi(G)=\text{tipo logico bounded di un grafo }G.
]

12.2 Observation Shadow
Given a descriptive system (\mathcal D), a budget (b), and an observer:
[
\pi:X\to A,
]
we define:
[
\operatorname{Sh}_{\mathcal D}(b,\pi)
{\pi(\llbracket d\rrbracket):d\in D_{\le b},\ \llbracket d\rrbracket\text{ definita}}.
]
This is the shadow of simple objects under the observer.
The fundamental lemma is:
[
\boxed{
\pi(x)\notin \operatorname{Sh}{\mathcal D}(b,\pi)
\Rightarrow
K{\mathcal D}(x)>b.
}
]
This is the operating heart of theory.

12.3 Observation certificate
An observational certificate of:
[
K_{\mathcal D}(x)>b
]
is an observer (\pi) such that:
[
\pi(x)\notin \operatorname{Sh}_{\mathcal D}(b,\pi).
]
The certificate contains:
1. description of the observer;
2. finished co-domain (A);
3. value (\pi(x));
4. shadow of simple objects;
5. verification of not belonging.

12.4 Observation schemes
A single observer is not enough. We need a scheme:
[
\Omega=(O,\kappa,(A_o){o\in O},(\pi_o){o\in O}),
]
where:
* (O) is the set of observer codes;
* (\kappa:O\to C) is the cost of the observer;
* (A o) is finished;
* (\pi_o:X\to A_o);
* per ogni costo (c), (O_{\le c}) è finito ed enumerabile.
Questo evita cheating: non si possono inventare osservatori ad hoc gratis.

12.5 Algebra degli osservatori
Coarsening
Se:
[
\pi:X\to A
]
and:
[
q:A\to B,
]
Then:
[
q\circ \pi:X\to B
]
It's grosser.
Refinement
(\rho:X\to B) refines (\pi:X\to A) if:
[
\pi=q\circ \rho.
]
Product
[
(\pi\times\rho)(x)=(\pi(x),\rho(x)).
]
The shadow meets:
[
\operatorname{Sh}(b,\pi\times\rho)
\subseteq
\operatorname{Sh}(b,\pi)\times\operatorname{Sh}(b,\rho).
]
The inclusion can be narrow: the product captures correlations.
This is important for CRT and profiles (p)-adici.

12.6 Quality completeness
A scheme (\Omega) is punctually separating if for each (x\ne y) exists (o) with:
[
\pi_o(x)\ne \pi_o(y).
]
It is closed for finished products if finished products of observers are still admitted observers, or are refined by one admitted.
Theorem:
If (\Omega) is punctually separating and closed for finished products, then:
[
K_{\mathcal D}(x)>b
]
if and only if there is an observer (or\in\Omega) such that:
[
\pi_o(x)\notin \operatorname{Sh}_{\mathcal D}(b,\pi_o).
]
Attention: this is qualitative. The necessary observer can have huge cost. Interesting theory is quantitative.

12.7 Homomorphic Observers
If (X) has operations and (\pi:X\to A) is homomorphic, then the shadow can be calculated directly in the finite world (A).
Example:
[
\pi_m:\mathbb Z\to \mathbb Z/m\mathbb Z
]
is homomorphic for:
[
+,-,\times.
]
Then the outputs of SLP module (m) are calculated by performing the SLP in the finished ring:
[
\mathbb Z/m\mathbb Z.
]

12.8 Overapproximation
Sometimes the exact shadow is not calculated, but a super-shadow:
[
\operatorname{Sh}_{\mathcal D}(b,\pi)\subseteq U\subseteq A.
]
If:
[
\pi(x)\notin U,
]
Then:
[
K_{\mathcal D}(x)>b.
]
This is soundness with overapproximation.

12.9 Modular Observers for SLP
System:
[
\mathcal D=\mathrm{SLP}_{+,-,\times}.
]
Objects:
[
X=\mathbb Z.
]
Observer:
[
\pi_m(n)=n\bmod m.
]
For budget (s), define:
[
R_s(m)=
{\llbracket P\rrbracket\bmod m: |P|\le s}.
]
If:
[
n\bmod m\notin R_s(m),
]
Then:
[
\tau(n)>s.
]
This is the first true fertile technical scheme:
[
\boxed{
\text{assenza modulare}
\Rightarrow
\text{lower bound SLP}.
}
]

12.10 CRT and profiles
For modules cover me:
[
m_1,\dots,m_r,
]
the product of observers is:
[
n\mapsto(n\bmod m_1,\dots,n\bmod m_r),
]
equivalent to:
[
n\bmod M,
\qquad
M=m_1\cdots m_r.
]
The shadow produced can be strictly smaller than the product of the individual shadows:
[
R_s(M)
\subsetneq
R_s(m_1)\times\cdots\times R_s(m_r).
]
These correlations are a source of power.

12.11 Modular completeness on the whole
For each descriptive system actually finite entire, if:
[
K_{\mathcal D}(n)>b,
]
then there is a first (p) such that:
[
n\bmod p\notin \operatorname{Sh}_{\mathcal D}(b,\pi_p).
]
Demonstration: the ball (\mathcal B {\mathcal D}(b)) is over. For each (y) in the ball, (n-y\ne0). Choose a first (p) that does not divide:
[
\prod_{y\in \mathcal B_{\mathcal D}(b)}(n-y).
]
Then (n\not\equiv y\pmod p) for each (y) in the ball.
This completeness is qualitative, not quantitative. The first (p) can be huge.

12.12 Rational and objective observers
For rationale:
[
q=a/b,
]
use:
[
\pi_p(q)=[a:b]\in\mathbb P^1(\mathbb F_p).
]
This avoids problems when (b\equiv0\pmod p).
If:
[
a/b\ne c/d,
]
Then:
[
ad-bc\ne0,
]
and almost every first separates the two rationales.

12.13 Numerical fields
For a numerical field (K), use initial ideal module reductions:
[
\pi_{\mathfrak p}:\mathcal O_K\to \mathcal O_K/\mathfrak p.
]
For general elements of (K), check denominators or use projective/localized versions.
These observers link:
[
\text{altezze}
]
a:
[
\text{profili locali finiti}.
]

12.14 Groups and residual finiteness
For a group (G), a finite observer is a homomorphism:
[
G\to Q
]
with (Q) finished.
The family of these observers is separating if and only if (G) is residually finished.
So:
[
\boxed{
\text{residual finiteness}
\text{completezza degli osservatori finiti di quoziente.}
}
]

12.15 Observation blind points
Given a scheme (\Omega), define:
[
x\sim_\Omega y
]
if:
[
\forall o\in\Omega,\quad \pi_o(x)=\pi_o(y).
]
If (x\ne y) but (x\sim \Omega y), no observer of (\Omega) distinguishes them.
Examples:
* groups not residually finished;
* graphs not distinguished by Weisfeiler-Leman;
* structures not distinct from weak logic;
* mouse spaces with same omology but not equivalent;
* Cospectral objects.
The theory must always indicate its blind points.

12.16 Profinite geometry
A scheme (\Omega) induces:
[
\eta_\Omega:X\to\prod_{o\in\Omega}A_o.
]
The product is a perfect space.
(\Omega) is punctually separating if (\eta \Omega) is injective.
Separating (x) from a finite ball means finding a finished projection in which:
[
\eta_\Omega(x)
]
does not fall on the image of the ball.
So:
[
\boxed{
\text{gli osservatori finiti studiano la geometria profinita delle palle di complessità.}
}
]

13. Theorems to write formally
Theorem A — Observation Soundness
If:
[
\pi(x)\notin \operatorname{Sh}_{\mathcal D}(b,\pi),
]
Then:
[
K_{\mathcal D}(x)>b.
]
Theorem B — Soundness with overapproximation
If:
[
\operatorname{Sh}_{\mathcal D}(b,\pi)\subseteq U
]
and:
[
\pi(x)\notin U,
]
Then:
[
K_{\mathcal D}(x)>b.
]
Theorem C — Completeness for separating families
If (\Omega) is punctually separating and product-closed, each lower bound true compared to a finite ball has an observational certificate.
Theorem D — Disjunction of two systems
If:
[
\operatorname{Sh}{\mathcal D}(b,\pi)
\cap
\operatorname{Sh}{\mathcal E}(c,\pi)
\varnothing,
]
Then:
[
\mathcal B_{\mathcal D}(b)
\cap
\mathcal B_{\mathcal E}(c)
\varnothing.
]
Theorem E — Completeness for finite deviations
If (\Omega) is separating and closed for products, each split of two finite sets can be certified by an observer of (\Omega).
Theorem F — Modular completeness on (\mathbb Z)
For each descriptive system actually finite entire, if:
[
K_{\mathcal D}(n)>b,
]
then there is a first (p) such that:
[
n\bmod p
\notin
\operatorname{Sh}_{\mathcal D}(b,\pi_p).
]
Theorem G — Homomorphic Observers
If (\pi:X\to A) is homomorphic compared to the operations they generate (\mathcal D), then the shadow is calculated entirely in the finite system (A).
Theorem H — Test Pullback
If (I:X\to Y) pulls back economic observers of (Y) into economic observers of (X), then lower bound separatives transfer long (I).

14. Quantitative functions to study
Define the minimum cost of separation:
[
\operatorname{Sep}_\Omega(x,y)
\min{\kappa(o):\pi_o(x)\ne\pi_o(y)}.
]
For a finite set (S):
[
\operatorname{Sep}_\Omega(x,S)
\min{\kappa(o):\pi_o(x)\notin\pi_o(S)}.
]
For a ball:
[
\operatorname{Sep}_{\mathcal D,\Omega}(x,b)
\operatorname{Sep}\Omega(x,\mathcal B{\mathcal D}(b)).
]
This measure costs to certify:
[
K_{\mathcal D}(x)>b.
]
The really interesting problem is not only to know if an observer exists, but to estimate the minimum cost of the observer.

15. Information capacity of an observer
Define:
[
\Delta_{\mathcal D}(b,\pi)
\log |A|
\log |\operatorname{Sh}_{\mathcal D}(b,\pi)|.
]
This measure how many observations are excluded from simple objects.
The excluded fraction is:
[
1-\frac{|\operatorname{Sh}_{\mathcal D}(b,\pi)|}{|A|}.
]
If a target is random compared to (A), this is the probability that the observer excludes it.
For products:
[
\operatorname{Sh}(b,\pi\times\rho)
\subseteq
\operatorname{Sh}(b,\pi)\times\operatorname{Sh}(b,\rho).
]
The correlations between observations can increase the power of the product.

16. Anti-cheating observers
If arbitrary observers are allowed, the theory becomes trivial.
Date (S) finite and target (x\notin S), you can define ad hoc:
[
\pi(y)=
\begin{cases}
1,&y=x,\
0,&\text{altrimenti}.
\end{cases}
]
This separates (x) from (S), but does not have mathematical value if the observer is built free using the target.
Anti-cheating Principle:
[
\boxed{
\text{un osservatore è ammissibile solo se appartiene a uno schema fissato, oppure se il costo della sua dipendenza dal target è pagato.}
}
]

17. Pilot applications of observers
17.1 SLP + CRT + (p)-adici
System:
[
\mathcal D=\mathrm{SLP}_{+,-,\times}.
]
Observers:
[
\pi_m(n)=n\bmod m,
]
CRT profiles,
[
(n\bmod m_1,\dots,n\bmod m_r),
]
and profiles (p)-toteen truncated.
Objective:
[
n\bmod m\notin R_s(m)
\Rightarrow
\tau(n)>s.
]
This is the most fertile frontier.

17.2 Riga and compass
Descriptive system: finite geometric constructions.
Invariant/observer:
[
\deg_{\mathbb Q}(\alpha)\text{ è potenza di }2\text{ oppure no}.
]
Recover:
* duplication of the cube;
* general trisection;
* impossibility of certain buildings.

17.3 Galois and radicals
Descriptive system: radical expressions.
Observer:
[
\operatorname{Gal}(P)\text{ solubile/non solubile}.
]
If the Galois group is not soluble, there is no expression for radicals.

17.4 Cars and Myhill-Nerode
Observers:
[
\pi_w(L)=1 \iff w\in L.
]
Profiles on suffixes distinguish classes. Recover lower bound on states.

17.5 Graphies and weak logic
Observers:
* FO/MSO bounded types;
* Weisfeiler-Leman colors;
* homomorphism counts;
* Spectro Module (p).
Lower bound: properties not defined or not distinguishable within a logical budget.

17.6 Proof complexity
Observers:
* width;
* degree;
* rank;
* restrictions;
* finite evaluations;
* pseudoexpectations.
Objective: to demonstrate that no short evidence can have the required observation.

18. First technical package to write
The next phase must produce a founding section with:
1. descriptive systems actually finitary;
2. lower bound decidable by enumeration;
3. encoded classes of preachers;
4. bounded minimization secure;
5. eligible classes of controls (\mathcal A);
6. operators (\mathcal A)-controlled;
7. finite observers;
8. shadows;
9. observative soundness;
10. overapproximation;
11. Observer products;
12. qualitative completeness;
13. Modular observers on (\mathbb Z);
14. Modular SLP as the first laboratory.

19. First truly promising frontier
The best frontier is:
[
\boxed{
\mathrm{SLP}_{+,-,\times}
+
\text{osservatori modulari}
+
\text{CRT}
+
\text{profili }p\text{-adici}.
}
]
Minimum objective:
[
\text{costruire certificati modulari di }\tau(n)>s.
]
Average target:
[
\text{stimare il costo minimo del modulo separante.}
]
Strong objective:
[
\text{ottenere lower bound asintotici su SLP-size usando osservatori aritmetici.}
]
Transfer target:
[
\text{profilo locale/global aritmetico}
\Rightarrow
\text{assenza di descrizione algoritmica corta}.
]

20. First concrete question on modular SLP
For each (s,m), define:
[
R_s(m)=
{\llbracket P\rrbracket\bmod m: |P|\le s}.
]
Questions:
1. How much does it grow (|R s(m)|)?
2. For which (m) is (R s(m)) everything (\mathbb Z/m\mathbb Z)?
3. For which (m) is small?
4. Are the first modules better than composites?
5. First power modules capture useful profiles (p)-adics?
6. Does CRT products introduce unseen correlations single module?
7. Are there natural targets (n) for which small modules certify (\tau(n)>s)?
8. Are there lower bounds on the size of the necessary module?
9. Is the shadow SLP module (m) closed under any operation?
10. What is the relationship between (R s(m)) and subring generated by (1) with (s) operations?

21. Recommended experimental method
For children (s,m):
1. enumerate all SLPs of length (\le s);
2. calculate the module outputs (m);
3. building (R s(m));
4. compare with (\mathbb Z/m\mathbb Z);
5. search for missing residues;
6. for target (n), check if (n\bmod m) is missing;
7. repeat with CRT profiles;
8. measure correlations:
[
R_s(mn)
\subseteq R_s(m)\times R_s(n).
]
Although this is computational, it serves to understand the geometry of shadows.

22. Criteria for severity
Any future result must be classified.
Type 0 — Slogan
A suggestive idea without definitions or theorems.
Type 1 — Taxonomy
A known theory is inserted in the framework.
Type 2 — Recovery
A classic theorem is rewritten as obstruction.
Type 3 — Structural
A general property of systems/observers is demonstrated.
Type 4 — Transfer
A lower bound goes from one system to another.
Type 5 — New application
The framework shows something not natural in separate languages.
Immediate realistic target: get to Type 3 and Type 4.

23. Form of a possible first internal paper
Title possible:
[
\textbf{Finite Observers for Finitary Description Systems}
]
Structure:
Section 1 — Motivation
Budget obstructions, short descriptions, no-go general, need for local systems.
Section 2 — Descriptive systems actually ended
Definitions, balls, lower bound lemma per enumeration.
Section 3 — Bounded Miniature Safe
Classified by preachers, bounded operators, stability dilemmas.
Section 4 — Finished remarks
Definitions, shadows, soundness, overapproximation.
Section 5 — Observer Algebra
Products, refinement, coarsening, costs, profiles.
Section 6 — Quality completeness
Separate families, products, completeness on finite balls.
Section 7 — Modular Observers
Entire, rational, numerical fields, modular completeness.
Section 8 — SLP Laboratory
Definition of (R s(m)), modular certificates, examples, questions.
Section 9 — Classical recovery
Riga and compass, Galois/radicali, automi/Myhill-Nerode.
Section 10 — Perspectives
Transfers, small-counterexample principles, pilot systems.

24. What to do now
Don't expand the library yet.
Don't try to solve Collatz right now.
Do not seek a universal theory of Kolmogorov/highs/tests.
Do not use unbounded minimization.
Do not call “new” what is only a reformulation.
Do not use ad hoc observers without paying the cost.
Do not assume that large height hangs long SLP.
Do not confuse:
[
x\notin \mathcal B_{\mathcal D}(b)
]
with:
[
x\text{ non esiste}.
]

25. Next recommended move
The next best move is to formally write the chapter:
[
\boxed{
\text{Finite Observers for Finitary Description Systems}
}
]
with definitions and theorems A–H.
Immediately afterwards, develop the laboratory:
[
\boxed{
\mathrm{SLP}_{+,-,\times}\text{ modulo }m.
}
]
The first concrete result should be:
[
n\bmod m\notin R_s(m)
\Rightarrow
\tau(n)>s.
]
Then study when and how (R s(m)) is small, structured, or separating.

26. Final project formula
The project is not:
[
\text{“trovare la complessità vera degli oggetti matematici”.}
]
It is:
[
\boxed{
\text{costruire sistemi descrittivi finitarî, studiare le loro palle di semplicità, e usare osservatori finiti per certificare che certi oggetti non appartengono a tali palle.}
}
]
The technical heart is:
[
\operatorname{Sh}_{\mathcal D}(b,\pi)
\pi(\mathcal B_{\mathcal D}(b)).
]
The basic certificate is:
[
\pi(x)\notin \operatorname{Sh}_{\mathcal D}(b,\pi).
]
The high form of the program is:
[
\boxed{
\text{dimostrare principi di piccolo controesempio e teoremi di trasferimento tra sistemi descrittivi diversi.}
}
]
The first concrete frontier is:
[
\boxed{
\text{SLP}+\text{CRT}+\text{profili }p\text{-adici}.
}
]
The next useful answer, if you resume from here, should preferably start writing the formal theory of finite observers, or the modular SLP laboratory.

27. Operating Prompt to continue
If you resume the project from this note, proceed as follows:
1. do not ask for general clarifications again;
2. not start again from philosophy;
3. choose one of the two directions:
* formal foundation of finite observers;
* SLP laboratory module (m);
4. be strict in distinguishing definition, lemma, theorem, heuristic;
5. do not promise originality before having new transfers or applications;
6. do not extend the library unless necessary;
7. keep the compass:
[
\boxed{
\text{osservatori finiti come certificati di lower bound per sistemi descrittivi effettivamente finitarî.}
}
]

— Appendix:

Technical Annex — Modular SLP Laboratory
This appendix makes the first concrete laboratory of the project operational:
[
\boxed{
\mathrm{SLP}_{+,-,\times}
+
\text{osservatori modulari}
+
\text{CRT}
+
\text{profili }p\text{-adici}.
}
]
The purpose is to study how to certify lower bound of descriptive complexity for whole using modular finite observatories.
The basic principle is:
[
\boxed{
n\bmod m\notin R_s(m)
\Rightarrow
\tau(n)>s.
}
]
Where:
* (\tau(n)) is the minimum length of a straight-line program that produces (n);
* (R s(m)) is the set of form residues (m) which can be produced by length SLP (\le s).
This appendix fixes conventions, definitions, first examples, algorithms and search questions.

1. Internal SLP Convention
We set the descriptive system:
[
\mathcal D_{\mathrm{SLP}}
\mathrm{SLP}_{+,-,\times}.
]
A length program (s) is a sequence of logs:
[
a_0,a_1,\dots,a_s
]
where:
[
a_0=1,
]
and for each (i=1,\dots,s):
[
a_i=a_j\circ a_k
]
with:
[
0\le j,k<i,
\qquad
\circ\in{+,-,\times}.
]
The length is the number of assignments after (a 0), i.e. (s).
Important Convention: a long program (s) can produce as output any log between:
[
a_0,\dots,a_s.
]
Then a number is produced within budget (s) if it appears in at least one log of some length program (\le s).
This convention avoids unnecessary details on “copying” a final register and makes the ball of complexity natural:
[
V_s
{n\in\mathbb Z:\tau(n)\le s}.
]
Where:
[
\tau(n)=\min{s:n\in V_s}.
]

2. SLP
A state after (s) steps can be seen as the set of available values:
[
S={a_0,\dots,a_s}.
]
The order of the registers does not matter for future values: if two programs have the same set of available values, then they have the same future possibilities.
We then recursively define states on a ring (R).
[
\mathfrak S_0(R)={{1_R}}.
]
Then:
[
\mathfrak S_{s+1}(R)
\left{
S\cup{x\circ y}:
S\in\mathfrak S_s(R),
\ x,y\in S,
\ \circ\in{+,-,\times}
\right}.
]
The shadow of accessibility within (s) is:
[
R_s(R)
\bigcup_{t\le s}
\bigcup_{S\in\mathfrak S_t(R)}
S.
]
In case (R=\mathbb Z), we write:
[
V_s=R_s(\mathbb Z).
]
In case (R=\mathbb Z/m\mathbb Z), we write:
[
R_s(m)=R_s(\mathbb Z/m\mathbb Z).
]

3. First lemma: accuracy of states
Lemma. (V s) is exactly the whole set of SLPs of length (\le s).
Demonstration.
Each SLP builds a sequence of register sets:
[
{a_0}\subseteq {a_0,a_1}\subseteq\cdots\subseteq{a_0,\dots,a_s}.
]
Each new register is obtained by applying (+,-,\times) to two already available values. So each product value appears in a state of occurrence.
Conversely, every transition:
[
S\mapsto S\cup{x\circ y}
]
can be achieved by a new SLP step, choosing logs containing (x) and (y).
So the recurrence on states describes exactly the SLP accessibility.

4. First values on (\mathbb Z)
With the conventions fixed:
[
V_0={1}.
]
[
V_1={0,1,2}.
]
In fact:
[
1-1=0,
\qquad
1\cdot1=1,
\qquad
1+1=2.
]
For (s=2):
[
V_2={-1,0,1,2,3,4}.
]
Examples:
[
-1=0-1,
]
[
3=2+1,
]
[
4=2\cdot2.
]
For (s=3):
[
V_3=
{-3,-2,-1,0,1,2,3,4,5,6,8,9,16}.
]
Examples:
[
-2=-1-1,
]
[
-3=-1-2,
]
[
5=4+1,
]
[
6=3\cdot2,
]
[
8=4\cdot2,
]
[
9=3\cdot3,
]
[
16=4\cdot4.
]
Already here we see an important phenomenon: not all the whole small are present. For example, with these conventions:
[
7\notin V_3,
\qquad
10\notin V_3,
\qquad
12\notin V_3.
]
So:
[
\tau(7)>3,
\qquad
\tau(10)>3,
\qquad
\tau(12)>3.
]
These lower bounds are banal for exact enumeration, but the modular lab searches for more structured certificates.

5. Modular Observers
For each module (m\ge2), we define the finite observer:
[
\pi_m:\mathbb Z\to\mathbb Z/m\mathbb Z,
]
[
\pi_m(n)=n\bmod m.
]
The shadow SLP module (m) is:
[
R_s(m)=
{\llbracket P\rrbracket\bmod m:
P\text{ SLP di lunghezza }\le s}.
]
Equivalently, using states:
[
R_s(m)
R_s(\mathbb Z/m\mathbb Z).
]
Since (\mathbb Z/m\mathbb Z) is finished, (R s(m)) is calculated entirely in the finite world.

6. Basic modular design
Lemma.
If:
[
n\bmod m\notin R_s(m),
]
Then:
[
\tau(n)>s.
]
Demonstration.
If (\tau(n)\le s), then there is a long SLP (P) that produces (n). By reducing module (m), the same program produces:
[
n\bmod m.
]
So:
[
n\bmod m\in R_s(m).
]
Contradition.
This is the first concrete observational certificate:
[
\boxed{
\pi_m(n)\notin \operatorname{Sh}_{\mathrm{SLP}}(s,\pi_m)
\Rightarrow
\tau(n)>s.
}
]

7. Initial table of modular shadows
With the conventions of this appendix, for small modules the following cardinalities are obtained:
[
|R_s(m)|,\qquad s=0,1,2,3,4.
]
[
\begin{array}{c|ccccc}
m & |R_0(m)| & |R_1(m)| & |R_2(m)| & |R_3(m)| & |R_4(m)|\
\hline
2 & 1&2&2&2&2\
3 & 1&3&3&3&3\
4 & 1&3&4&4&4\
5 & 1&3&5&5&5\
6 & 1&3&6&6&6\
7 & 1&3&6&7&7\
8 & 1&3&6&8&8\
9 & 1&3&6&9&9\
10 & 1&3&6&10&10\
11 & 1&3&6&10&11\
12 & 1&3&6&11&12
\end{array}
]
Interpretation: for small modules, the shadow often saturates quickly all the codomain. So small modules can be too weak to certify deep lower bounds.
This is not a failure of the method. It is structural information: we need to look for modules, CRT products or more fine profiles that do not saturate too soon.

8. Modular quality finish
The first module observers are qualitatively complete to separate an entire from a finished ball.
Theorem.
Be (\mathcal D) any actually finite descriptive system of entire. If:
[
K_{\mathcal D}(n)>b,
]
then there is a first (p) such that:
[
n\bmod p
\notin
\operatorname{Sh}_{\mathcal D}(b,\pi_p).
]
Demonstration.
The ball:
[
\mathcal B_{\mathcal D}(b)
]
It's over. For:
[
n\notin \mathcal B_{\mathcal D}(b),
]
for each:
[
y\in \mathcal B_{\mathcal D}(b)
]
we have:
[
n-y\ne0.
]
The product:
[
M=\prod_{y\in\mathcal B_{\mathcal D}(b)}(n-y)
]
It's a non-nothing whole. Choose a first (p) that does not divide (M). Then for each (y) in the ball:
[
n\not\equiv y\pmod p.
]
So:
[
n\bmod p
\notin
\pi_p(\mathcal B_{\mathcal D}(b)).
]
End.
Warning. This theorem is qualitative. The first (p) separating can be huge. Interesting mathematics is quantitative:
[
\text{quanto piccolo può essere }p?
]

9. Observers CRT
For modules cover me:
[
m_1,\dots,m_r,
]
the product of observers is:
[
\pi_{m_1,\dots,m_r}(n)
(n\bmod m_1,\dots,n\bmod m_r).
]
For the Chinese theorem of the rest, this is equivalent to observing:
[
n\bmod M,
\qquad
M=m_1\cdots m_r.
]
The shadow CRT is:
[
R_s(m_1,\dots,m_r)
{(\llbracket P\rrbracket\bmod m_1,\dots,\llbracket P\rrbracket\bmod m_r): |P|\le s}.
]
We always have:
[
R_s(m_1,\dots,m_r)
\subseteq
R_s(m_1)\times\cdots\times R_s(m_r).
]
Inclusion can be narrow.
This is essential: the individual modules can saturate, but the product can preserve non-banal correlations, because the same program must simultaneously carry out all residues.

10. Profiles (p) - truncated indexes
In addition to module residues (m), type observers can be used:
[
\nu_{p,r}(n)=\min(v_p(n),r).
]
The codomain is over:
[
{0,1,\dots,r}.
]
A profile (p)-adico truncated is:
[
\Pi(n)=
(\nu_{p_1,r_1}(n),\dots,\nu_{p_k,r_k}(n)).
]
Or combined with residues:
[
\Pi(n)
(n\bmod m,\nu_{p_1,r_1}(n),\dots,\nu_{p_k,r_k}(n)).
]
These observers are not always homomorphical for (+,-,\times), but can be treated with secure over-approximations.
For example:
[
v_p(xy)=v_p(x)+v_p(y),
]
While:
[
v_p(x+y)\ge \min(v_p(x),v_p(y)),
]
with possible increase in case of cancellation.
Then a profile (p)-adico lends itself to an analysis through overapproximation.

11. Exact Shadows and Overshadows
For an observer (\pi), the exact shadow is:
[
R_s^\pi
{\pi(\llbracket P\rrbracket): |P|\le s}.
]
Sometimes it is expensive to calculate it exactly. You can then calculate a super-shadow:
[
U_s^\pi
\supseteq
R_s^\pi.
]
The soundness rule is:
[
\pi(n)\notin U_s^\pi
\Rightarrow
\tau(n)>s.
]
So accuracy is not necessary. Just don't lose soundness.
This is useful for observers (p)-adics, truncated height observers, logical observers, graphic observers, etc.

12. Pseudocode for (R s(m))
To calculate exactly (R s(m)), work in finished states.
Input:
[
s,m.
]
Initiation:
[
\mathfrak S_0={{1\bmod m}}.
]
Transition:
for (t=0,\dots,s-1), build:
[
\mathfrak S_{t+1}
\left{
S\cup{x+y},
S\cup{x-y},
S\cup{xy}
:
S\in\mathfrak S_t,\ x,y\in S
\right},
]
all form (m).
Finally:
[
R_s(m)
\bigcup_{t\le s}
\bigcup_{S\in\mathfrak S_t}
S.
]
Note: since there are at most (2^m) subsets of (\mathbb Z/m\mathbb Z), the module process (m) is finished.

13. Variant with final output
The convention of this appendix allows output from any register.
If you want the classic variant “output only last register”, define:
[
R_s^{\mathrm{last}}(m)
{a_s\bmod m:
(a_0,\dots,a_s)\text{ è una SLP modulo }m}.
]
So...
[
R_s^{\mathrm{last}}(m)\subseteq R_s(m).
]
For lower bound within budget (\le s), the output version any log is more natural. In fact:
[
R_s(m)
\bigcup_{t\le s}R_t^{\mathrm{last}}(m)
]
if you allow to stop the program when the value is produced.
The main note uses the cumulative version (R s(m)).

14. Variant without subtraction
You can also study:
[
\mathrm{SLP}_{+,\times}
]
without subtraction.
So...
[
a_i=a_j+a_k
]
or:
[
a_i=a_j a_k.
]
The ball on (\mathbb Z) contains only natural positives.
This system is close to the classic integer complexity.
The shadows module (m) are:
[
R_s^{+,\times}(m).
]
Important differences:
1. without subtraction, it is not produced (0) in one step;
2. no negative;
3. module (m), saturation can be different;
4. some lower bounds are easier because it lacks deletion.
With subtraction, the system is more expressive but more difficult to control.

15. Variant with division
You can consider:
[
\mathrm{SLP}_{+,-,\times,/}.
]
Objects:
[
\mathbb Q
]
or rational/algebraic.
Module (p), the division is defined only if the denominator is invertible.
A safe form is to use objective observers:
[
q=a/b
\mapsto
[a:b]\in \mathbb P^1(\mathbb F_p).
]
The variant with division is important, but it is not the first laboratory. First develop well:
[
\mathrm{SLP}_{+,-,\times}
]
on whole.

16. Structural questions on (R s(m))
For each (s,m), (R s(m)) is a subset of:
[
\mathbb Z/m\mathbb Z.
]
The main questions are:
Question 1 — Saturation
For which couples ((s,m)) it is worth:
[
R_s(m)=\mathbb Z/m\mathbb Z?
]
If (R s(m)) satura, module (m) cannot certify:
[
\tau(n)>s.
]
Question 2 — First separating module
Given (n,s), define:
[
\mu_{\mathrm{sep}}(n,s)
\min{m\ge2:n\bmod m\notin R_s(m)}.
]
If there is no (m), then (n\in V s). But if (\tau(n)>s), modular completeness guarantees that some (m), indeed some first, exists.
Study the growth of:
[
\mu_{\mathrm{sep}}(n,s)
]
is a central quantitative question.
Question 3 — First separating
Define:
[
p_{\mathrm{sep}}(n,s)
\min{p\text{ primo}:n\bmod p\notin R_s(p)}.
]
How big can it be?
Question 4 — Shadow density
Study:
[
\delta_s(m)=\frac{|R_s(m)|}{m}.
]
If (\delta s(m)<1), there are missing residues.
If (\delta s(m)\ll1), a random target module (m) is excluded with high probability.
Question 5 — CRT correlations
For (\gcd(m,n)=1), measure:
[
\operatorname{Corr}_s(m,n)
\frac{|R_s(m)\times R_s(n)|}{|R_s(mn)|}.
]
If:
[
\operatorname{Corr}_s(m,n)>1,
]
the product module contains correlations not visible from individual modules.
Question 6 — Observation costs
Define:
[
\kappa(m)=\log m
]
or:
[
\kappa(m)=\text{bit-length di }m.
]
Study:
[
\operatorname{Sep}_{\mathrm{SLP}}(n,s)
\min{\kappa(m):n\bmod m\notin R_s(m)}.
]
This is the observatory difficulty of certifying:
[
\tau(n)>s.
]

17. Natural Target Questions
Study (p {\mathrm{sep}}(n,s))) for natural families:
[
n=2^k-1,
]
[
n=2^k+1,
]
[
n=k!,
]
[
n=F_k,
]
[
n=\binom{2k}{k},
]
[
n=p_k\text{ primo }k\text{-esimo},
]
[
n=\lfloor \alpha^k\rfloor,
]
[
n=\text{valori di ricorrenze lineari},
]
[
n=\text{valori di iterazioni dinamiche}.
]
For each family, ask:
1. Does SLP have short notes?
2. has special modular profiles?
3. Small modules separate from (V s)?
4. Does CRT help?
5. profiles (p)-adici help?

18. Height ratio
Caution: Large height does not imply long SLP.
Example:
[
2^{2^k}
]
has huge height, but short SLP through successive squares.
So the correct line is not:
[
h(n)\text{ grande}
\Rightarrow
\tau(n)\text{ grande}.
]
The correct line is:
[
\text{profilo aritmetico incompatibile con gli output SLP corti}
\Rightarrow
\tau(n)>s.
]
Modular observers and (p)-adics serve precisely to test this incompatibility.

19. Report with counting arguments
The SLP number of length (s) is finished.
A rough estimate is:
in step (i), you choose:
[
j,k<i
]
and one in three operations. Then the number of programs exactly length (s) is at most:
[
\prod_{i=1}^s 3i^2
3^s(s!)^2.
]
So:
[
|V_s|
\le
3^s(s!)^2.
]
This estimate is very gross, because many programs produce the same value.
Module (m):
[
|R_s(m)|
\le
\min(m,3^s(s!)^2).
]
So if:
[
m>3^s(s!)^2,
]
then (R s(m)) cannot cover all residues for pure counting.
This shows that big observers necessarily have missing residues.
But for a specific target (n), it is necessary that the missing residue be proper:
[
n\bmod m.
]

20. Report with maximum values
Without subtraction, with (1,+,\times), the maximum value produced in (s) steps is obtained for repeated squares after producing (2):
[
1\mapsto 2\mapsto 4\mapsto 16\mapsto 256\mapsto\cdots
]
With current conventions:
[
\max V_0=1,
]
[
\max V_1=2,
]
[
\max V_2=4,
]
[
\max V_3=16,
]
[
\max V_4=256.
]
More generally, for (s\ge1):
[
\max V_s=2^{2^{s-1}}.
]
With subtraction, the maximum positive remains the same, because subtracting does not help to maximize in absolute positive value at fixed budgets, at least in this basic grammar.
This gives a banal lower bound:
[
n>2^{2^{s-1}}
\Rightarrow
\tau(n)>s.
]
But this lower bound is of growth type, not observative. Modular observers seek lower bound even when (n) is not huge.

21. Report by Integer
The system:
[
\mathrm{SLP}_{+,\times}
]
with constant (1) and sharing is close but not identical to classical integer complexity.
The classic integer counts the number of (1) used in an expression with (+,\times), without explicit sharing.
Here instead (\tau(n))) counts the number of SLP operations and allows reuse of the registers.
So:
[
\mathrm{SLP\ complexity}
]
and:
[
\mathrm{integer\ complexity}
]
are related but different.
Both must be kept in the library, but not confused.

22. Relationship with straight-line programs
In the context of computational algebra, SLPs are programs without branch and without loop.
Here we use a version without input, with initial constant (1), to describe whole singles.
Possible variations:
1. initial constants ({0,1});
2. constant (-1) allowed;
3. operazioni ({+,-,\times});
4. operazioni ({+,\times});
5. divisione ammessa;
6. output ultimo registro;
7. output qualunque registro;
8. costo per bit delle costanti iniziali se si ammettono costanti grandi.
La versione di questa appendice è:
[
a_0=1,\quad +,-,\times,\quad output qualunque registro.
]
Any change of convention must be declared, because it changes (V s) and (R s(m)).

23. Possible normalization of module states (m)
To calculate (R s(m)), states can be represented as subsets:
[
S\subseteq\mathbb Z/m\mathbb Z.
]
The transition is:
[
S\mapsto S\cup{x+y},
]
[
S\mapsto S\cup{x-y},
]
[
S\mapsto S\cup{xy}.
]
This eliminates duplication of logs with the same module value (m).
In addition, if two programs produce the same state (S), they have the same future module (m). So you can do dynamic programming on the distinct states.
This is essential for experiments.

24. Most fine observers of module states (m)
The module reduction (m) can lose too much information. Observers can be refined.
24.1 Observer module plus trace of zero dividers
For (m) composite, distinguish:
[
\gcd(n,m).
]
Observer:
[
\pi(n)=(n\bmod m,\gcd(n,m)).
]
Actually (\gcd(n,m))) is determined by (n\bmod m), but can be useful as a conceptual coordination.
24.2 Observer (p)-adic valuation truncated
[
\nu_{p,r}(n)=\min(v_p(n),r).
]
24.3 Mixed Observer
[
\pi(n)=
(n\bmod m,\nu_{p_1,r_1}(n),\dots,\nu_{p_k,r_k}(n)).
]
24.4 Observer module plus local factorization
For (n\bmod p^r), distinguish:
[
v_p(n)
]
and the unitary part:
[
n p^{-v_p(n)}\bmod p^{r-v_p(n)}.
]
This is often more natural (p)-adiously.

25. First manual experiment
With (s=3):
[
V_3=
{-3,-2,-1,0,1,2,3,4,5,6,8,9,16}.
]
To certify:
[
\tau(7)>3,
]
we can look for a module (m) such that:
[
7\bmod m
\notin
V_3\bmod m.
]
Module (2):
[
7\equiv1,
]
but (1\in V 3\bmod2), does not separate.
Module (3):
[
7\equiv1,
]
but (1\in V 3\bmod3), does not separate.
Module (5):
[
7\equiv2,
]
but (2\in V 3\bmod5), does not separate.
Module (7):
[
7\equiv0,
]
but (0\in V 3\bmod7), does not separate.
Module (11):
[
7\equiv7.
]
Reducing (V 3) form (11):
[
V_3\bmod11=
{0,1,2,3,4,5,6,8,9,10}.
]
Miss (7). Then module (11) certifies:
[
\tau(7)>3.
]
This is a first concrete example of observational certificate:
[
7\bmod11\notin R_3(11).
]

26. Attention: Modular certificate vs full enumeration
In the case of (7), we have already enumerated (V 3), so the module certificate (11) does not add power.
But for (s) large, enumerating (V s\subset\mathbb Z) can be impossible by size of numbers.
Instead (R s(m)) lives in a small finite set:
[
\mathbb Z/m\mathbb Z.
]
So the modular certificate can be much more practical.
The hope is that for certain targets, modular observers small certifichino lower bound without having to manipulate whole huge.

27. Possible quantitative theorem to seek
A first non-banal result would be an estimate of the type:
[
\tau(n)>s
\Rightarrow
\exists p\le f(n,s)
\text{ tale che }
n\bmod p\notin R_s(p).
]
The qualitative completeness gives some (p), but with potentially huge bound.
A useful quantitative result should give (f(n,s) reasonable.
Even a weak but explicit estimate would be interesting.

28. Possible probable theorem
For a module (m), if:
[
|R_s(m)|\ll m,
]
then a random remnant module (m) is excluded with probability:
[
1-\frac{|R_s(m)|}{m}.
]
So for “casual” targets compared to module (m), frequent certificates are expected.
Question:
For which (m) and (s) it is worth:
[
|R_s(m)|\ll m?
]
Counting Rough says:
[
|R_s(m)|\le 3^s(s!)^2.
]
So if (m) is much larger than (3^s(s)^2), many residues are missing.
But for specific targets it needs more fine analysis.

29. Possible CRT Theorem
For modules cover me (m,n), you have:
[
R_s(mn)
\subseteq
R_s(m)\times R_s(n).
]
Question:
When is inclusion narrow?
The close inclusion measures correlations between the residues that must be realized by the same program.
A possible objective:
[
|R_s(mn)|
\ll
|R_s(m)|,|R_s(n)|
]
for certain families of modules.
If this happens, CRT gives much more powerful observers than the sum of individual modules.

30. Possible theorem (p)-adic
Study profile dynamics:
[
v_p(a_i)
]
in a SLP.
By multiplication:
[
v_p(xy)=v_p(x)+v_p(y).
]
For sum:
[
v_p(x+y)\ge \min(v_p(x),v_p(y)).
]
Cancellation may increase the rating.
Questions:
1. which profiles (v p) truncated are within (s)?
2. how often does the cancellation allow big jumps?
3. can you limit the jumps of (v p) without knowing unit residues?
4. combine (v p) with unitary module part (p^r) makes the exact system?
An exact form is to work module (p^r). Then (v p) truncated is determined by the residual module (p^r).

31. Report by homomorphic observers
Module observers (m) are homomorphic:
[
\pi_m(x+y)=\pi_m(x)+\pi_m(y),
]
[
\pi_m(x-y)=\pi_m(x)-\pi_m(y),
]
[
\pi_m(xy)=\pi_m(x)\pi_m(y).
]
So:
[
R_s(m)
]
is exactly the SLP ray ball (s) in the finished ring:
[
\mathbb Z/m\mathbb Z.
]
This is the main advantage of the modules.

32. Report by non-homomorphic observers
Observers like:
[
n\mapsto \text{bit-length}(n)\bmod k
]
or:
[
n\mapsto \text{altezza troncata}
]
are not homomorphic compared to (+,-,\times).
They can still be useful through overapproximation.
But the first laboratory should favour homomorphic observers, because they allow exact shadows.

33. Possible generalization
The modular SLP laboratory is a particular case of this scheme.
Both (A) a finished structure with operations:
[
+,-,\times.
]
You can define:
[
R_s(A)
]
like the set of (A) elements produced by SLP length (\le s) starting from (1 A).
For every homomorphism:
[
\pi:\mathbb Z\to A,
]
if:
[
\pi(n)\notin R_s(A),
]
Then:
[
\tau(n)>s.
]
For (A=\mathbb Z/m\mathbb Z), the modular case is recovered.
But you can also use:
* finished products of rings;
* whole rings quotients;
* finished algebras;
* finished matrices;
* finite non commutative structures.
This generalization can become very powerful.

34. Version for rational
For SLP with division, objects are rational.
A safe observer is:
[
\pi_p(a/b)=[a:b]\in\mathbb P^1(\mathbb F_p).
]
But rational operations are not everywhere defined in (\mathbb P^1(\mathbb F p)). You have to manage:
* division by zero;
* Multiple denominators of (p);
* infinite points;
* partial semantic.
That is why the rational version must be postponed.
First develop well the whole case without division.

35. Version for numerical fields
For a numerical field (K), set an ideal first (\mathfrak p), use:
[
\pi_{\mathfrak p}:\mathcal O_K\to \mathcal O_K/\mathfrak p.
]
For elements of (K), locate or use projective versions.
The analogue laboratory is:
[
R_s(\mathfrak p)
{\llbracket P\rrbracket\bmod \mathfrak p: |P|\le s}.
]
If:
[
\alpha\bmod \mathfrak p\notin R_s(\mathfrak p),
]
then (\alpha) did not have short SLP in the considered system.
This is a possible arithmetic extension.

36. What would be a new result?
Low level results:
[
n\bmod m\notin R_s(m)\Rightarrow\tau(n)>s
]
are structurally correct but almost tautologic.
More interesting results would be:
Type A — Classification of saturation
Determine for which (m,s):
[
R_s(m)=\mathbb Z/m\mathbb Z.
]
Type B — Bound on the first separator
Give estimates on:
[
p_{\mathrm{sep}}(n,s).
]
Type C — Families with small separators
Build families (n s) such that:
[
\tau(n_s)>s
]
is certified by small modules (p s).
Type D — Resistant families
Build families (n s\notin V s) such that each separate module must be large.
Type E — CRT not trivial
Show that for certain families:
[
R_s(mn)
]
is much smaller than:
[
R_s(m)\times R_s(n).
]
Type F — Lower bound asymptotic
Get:
[
\tau(n_s)\ge f(s)
]
for a natural family (n s) through modular observers.
This would be the real local breakthrough.

37. First concrete work plan
Step 1
Formalize well:
[
\mathrm{SLP}_{+,-,\times}
]
and length conventions.
Step 2
Calculate (V s) for (s\le4) or (s\le5) on (\mathbb Z), for familiarity.
Step 3
Calculate (R s(m)) for:
[
s\le6,\quad m\le N
]
for a reasonable (N).
Step 4
Measuring:
[
|R_s(m)|,
\qquad
\delta_s(m)=|R_s(m)|/m.
]
Step 5
Find unsaturated modules for (s) fixed.
Step 6
For natural targets (n), look for the first (m) separating.
Step 7
Study CRT:
[
R_s(mn)
\subseteq R_s(m)\times R_s(n).
]
Step 8
Formulate first conjectures.

38. Prime conjectures possible
These are just conjecture-laboratory, not results.
Conjecture 1 — Rapid dismantling of small modules
For each (s), many small modules (m) compared to the maximum growth:
[
2^{2^{s-1}}
]
saturano:
[
R_s(m)=\mathbb Z/m\mathbb Z.
]
Conjecture 2 — Separation with moderate modules
If:
[
n\notin V_s,
]
often there is a separate module:
[
m\ll \max(1,|n|)^C
]
with (C) small, or even (m) polynomial in (s) for natural families.
Conjecture 3 — CRT produces useful correlations
For certain modules cover me:
[
R_s(mn)
\subsetneq
R_s(m)\times R_s(n)
]
quantitatively significant.
Conjecture 4 — Profiles (p)-axis help more than crude residues
For targets with structured factorization, observatories (p)- truncated indexes separate before the simple first form residues.
Conjecture 5 — “natural” targets have natural separators
Numbers defined by celebrations, products, farms, binomials or simple dynamics often have modular separators related to their arithmetic structure.

39. Methodological warning
This lab is likely to become computational only. It should be avoided.
Experiments serve to discover patterns, but the goal is to produce theorems:
* soundness;
* qualitative completeness;
* quantitative bounds;
* saturation classification;
* transfers;
* lower bound asymptotics.
Each experiment should aim at a precise definition or design.

40. Connection with the general project
This lab is the first test bench of the project.
In general language:
[
\mathcal D=\mathrm{SLP}_{+,-,\times}
]
is an actually finite descriptive system.
Observers:
[
\pi_m(n)=n\bmod m
]
are homomorphic finite observers.
The shadows:
[
R_s(m)
]
are:
[
\operatorname{Sh}_{\mathcal D}(s,\pi_m).
]
The certificate:
[
n\bmod m\notin R_s(m)
]
is an observational certificate of:
[
K_{\mathcal D}(n)>s.
]
So this laboratory concretely realizes the central formula:
[
\boxed{
\pi(x)\notin \pi(\mathcal B_{\mathcal D}(b))
\Rightarrow
K_{\mathcal D}(x)>b.
}
]

41. Point to continue
If you recover from this appendix, the next most useful move is one of the following.
Option A — Theoretical development
formally demonstrate the dilemmas of:
1. accuracy of states;
2. modular soundness;
3. modular quality completeness;
4. soundness CRT;
5. overapproximation (p)-adica.
Option B — Experimental development
Build a wide table of:
[
|R_s(m)|
]
for small (s,m), seeking saturation, gaps and CRT correlations.
Option C — First target
Choose a natural family:
[
2^k-1,\quad F_k,\quad k!,\quad \binom{2k}{k}
]
and search for modular certificates of lower bound SLP.
Option D — First quantitative theorem
Look for an explicit bound on:
[
p_{\mathrm{sep}}(n,s).
]
The firmest choice is A.
The most exploratory choice is B.
The most ambitious choice is D.

42. Final formula of the appendix
The modular SLP laboratory is used to transform a difficult question:
[
\text{“quanto è lunga la più corta SLP per }n\text{?”}
]
in a family of finished questions:
[
\text{“quali residui modulo }m\text{ sono prodotti da SLP corte?”}
]
The motto is:
[
\boxed{
\text{per provare che un intero non è prodotto da programmi corti, basta trovare un mondo finito in cui la sua immagine non è prodotta da programmi corti.}
}
]
The first concrete frontier is:
[
\boxed{
R_s(m)=
{\text{residui modulo }m\text{ prodotti da SLP di lunghezza }\le s}.
}
]
The first certificate is:
[
\boxed{
n\bmod m\notin R_s(m)
\Rightarrow
\tau(n)>s.
}
]
The first real problem is quantitative:
[
\boxed{
\text{trovare osservatori modulari piccoli, naturali e potenti.}
}
]