Extensions of the point to set principle tofinite-state dimension
Elvira Mayordomo
Universidad de Zaragoza, Iowa State University

CiE 2023, Batumi, July 25th 2023

Where do I come from, where am I going to?

1

Effectivize a notion so that it is useful in acomputably-defined world

2

Use the effective notion to prove results in the classical world3

Effectivize it some more so that you can use it in a
finite-automata defined world → Use the finite-state notion
to prove results in the classical worldEffective Hausdorff dimension: Kolmogorov complexity

Given U a universal Turing Machine, and σ ∈ 2<ω , KU (σ) is
the Kolmogorov complexity of σ, which is the length of theshortest description of σ (from which U recovers σ):
KU (σ) = min {|p| |U(p) = σ }This concept is invariant on U up to an additive constant, wedrop the U
K(σ) = min {|p| |U(p) = σ }Effective Hausdorff dimension: Cantor space

Theorem (M 2002)
For x ∈ 2ω ,dim(x) = lim infnK(x[1..n])nIt extends the notion of Martin-Löf random sequence:x is ML-random iff there is a c such that for all n,
K(x[1..n]) > n − c
For a set E ⊆ 2ω ,dim(E ) = sup dim(x)x∈EWhy do we effectivize?

To quantify
Partial randomness
Geometric measure theory (correspondence principles)Sample results(Hitchcock 2005) If E is a union of Π01 -definable sets thendimH (E ) = dim(E )There are ∆02 -degrees of dimension 1 with no ML-random reals

Most extreme effectivitation: Finite-state dimension

Given a finite-state transducer D with input and output binaryalphabet (2-FST),KD (σ) = min {|p| | D(p) = σ ∨ p = σ }Most extreme effectivitation: Finite-state dimension
Theorem (Doty Moser 2006)
For x ∈ 2ω ,dim2FS (x) =inf

D2−FSTlim infn

KD (x[1..n])n

For a different input alphabet x ∈ {0, . . . , b − 1}ω
dimbFS (x) =inf

Db−FSTlim infn

KD (x[1..n])n

For a set E ⊆ {0, . . . , b − 1}ω ,dimbFS (E ) =inf

sup lim inf

Db−FST x∈En

KD (x[1..n])nSample result

Theorem(Lutz M 2021) There is an algorithm that computes an absolutely
normal real number in nearly-linear time

Effective Hausdorff dimension in Euclidean space

We identify x ∈ 2ω with the real number with binary
representation 0.x (also denoted x)
For x ∈ [0, 1],K(x[1..n])dim(x) = lim infnn
At Finite-State level, the alphabet matters, so for b ∈ N we
identify x ∈ {0, . . . , b − 1}ω with the real number in base b, 0.x
dimbFS (x) =inf

Db−FSTlim infnKD (x[1..n])n

Effective dimension in Euclidean space: adding geometry

Definition (Kolmogorov complexity of x at precision δ)Kδ (x) = inf {K(σ) | |x − 0.σ| < δ }For x ∈ [0, 1],dim(x) = lim inf+
δ→0Kδ (x)log(1/δ)Using information content at precision δ for FS

For D a finite-state transducer with input and output alphabet{0, . . . , b − 1} (b ∈ N), for x ∈ [0, 1],
KD,δ (x) = inf {KD (σ) | |x − 0.σ| < δ }Theorem (M 2022)
For x ∈ [0, 1],
dimbFS (x) =inflim inf+Db−FST δ→0KD,δ (x)log(1/δ)Effective Hausdorff dimension in other separable metricspaces
Let (X , ρ) be a separable metric space and let D ⊆ X be acountable dense set (fix f : 2<ω  D)

Definition (Kolmogorov complexity of x at precision δ)Kδ (x) = inf {K(σ) | ρ(x, f (σ)) < δ }Definition (Lutz et al 2022)
The algorithmic dimension of a point x ∈ X isdim(x) = lim inf+δ→0Kδ (x)log(1/δ)Using information content at precision δ for FS

For D a finite-state transducer with input and output alphabet{0, . . . , b − 1} (b ∈ N), x ∈ X ,KD,δ (x) = inf {KD (σ) | ρ(x, f (σ)) < δ }dimbFS (x) =inf

lim inf+

Db−FST δ→0KD,δ (x)log(1/δ)What next?

The relativization ingredientno
KA (σ) = min |p| U A (p) = σnoAKAδ (x) = inf K (σ) | ρ(x, f (σ)) < δ
dimA (x) = lim inf+
δ→0KA
δ (x)
log(1/δ)And for a set E ⊆ X
dimA (E ) = sup dimA (x)x∈EHausdorff definition of dimension (1919)

Let (X , ρ) be a separable metric space
For E ⊆ X and δ > 0, a δ-cover of E is a countable collection
U such that for all U ∈ U, diam(U) < δ and[E⊆UU∈UFor s ≥ 0,Ps
H s (E ) = limδ→0 inf U is a δ-cover of E
U∈U diam(U)The Hausdorff dimension of E ⊆ X isdimH (E ) = inf {s |H s (E ) = 0 }Point-to-set principle

Theorem (Lutz Lutz 2018, Lutz et al 2022)
Let E ⊆ X , thendimH (E ) = mindimA (E )<ωA⊆2

Two possible directions:
Use the point-to-set principle to prove results in geometricmeasure theory
Analyze the point-to-set principle to understandeffectivizations of dimension

Application of point to set principles to fractal geometry:projection formula

Theorem (Marstrand 1954, Mattila 1975)
Let E ⊆ Rn be an analytic set with dimH (E ) = s. Then foralmost every e ∈ S n−1 , dimH (pe E ) = min{s, 1}
It does not hold for arbitrary E (assuming CH). Recently anextension using PSPs

Theorem (N.Lutz Stull 2018)
Let E ⊆ Rn be an arbitrary set with dimH (E ) = dimP (E ) = s.
Then for almost every e ∈ S n−1 , dimH (pe E ) = min{s, 1}

Hausdorff optimal oracles (Stull 2022)(Informal) A is an Hausdorff optimal oracle for E if
dimH (E ) = dimA (E ) and any oracle A, B does not decrease
dimA,B (x) for some x ∈ ETheorem (Stull 2022)
Let E ⊆ Rn be a set that has a Hausdorff optimal oracle. Then foralmost every e ∈ S n−1 , dimH (pe E ) = min{dimH (E ), 1}
All known cases of the projection theorem are particular cases ofthisRevisiting the PTSPs

Let D ⊆ X be a countable dense set, let us consider different
enumerators f : 2<ω  DKfδ (x) = inf {K(σ) |ρ(x, f (σ)) < δ }Definition
The algorithmic dimension of a point x ∈ X with enumerator f isdimf (x) = lim inf+
δ→0Kfδ (x)log(1/δ)Revisiting the PTSPs

Theorem (M 2022)
Let E ⊆ X . ThendimH (E ) =minf :2<ω Ddimf (E ).

Some consequences

Relativization can be substituted by dense set enumeration
This is a robust alternative to relativization for Finite-Statedimension
for each enumeration f we can have a robust definition offinite-state dimension dimfFS
dimfFS (x) =inf

lim inf+D2−FST δ→0KfD,δ (x)log(1/δ)Finite-State dimension PTSP

Theorem (M 2022)
Let E ⊆ [0, 1).
dimH (E ) =minf :2<ω D

dimfFS (E ).

What we can learn from thisThe oracle for which dimH (E ) = minA⊆2<ω dimA (E ) requires
a single (functional) query
It can be interesting to separate compression and relativization
The concept of optimal oracles from (Stull 2022) should be
revisited for optimal enumerators

Further directions

For computability: Classification of PSP enumerators/oraclesof a set
For geometric m.t.: Can sets with optimal
enumerators/oracles replace analytic sets in different known
results?

References on the point to set principle
Jack H. Lutz and Neil Lutz, Who asked us? How the theoryof computing answers questions about analysis, Ding-Zhu Duand Jie Wang (eds.), Complexity and Approximation: In
Memory of Ker-I Ko, pp. 48-56, Springer, 2020
Jack H. Lutz and Elvira Mayordomo, Algorithmic fractal
dimensions in geometric measure theory. In Vasco Brattka
and Peter Hertling (eds.), Handbook of Computability andComplexity in Analysis, Springer-Verlag (2021)
Jack H. Lutz, Neil Lutz, and Elvira Mayordomo, Extending
the Reach of the Point-to-Set Principle. STACS 2022
Donald M. Stull, Optimal Oracles for Point-to-Set Principles.
STACS 2022
A point to set principle for finite-state dimension. E.
Mayordomo. arXiv:2208.00157 (2022)