Open Problem Resolution Map

Resolution map for neighboring open-problem families

Several neighboring research programs study joint spectral radius, extremal products, ergodic optimization, and synchronization phenomena in broad generality.
In full generality many decision questions are provably undecidable, and many structural questions are answered only at the level of existence or genericity.
The present work contributes a complementary kind of result: a certificate calculus that turns a range of these themes into finite objects whose validity is decidable on the certified positive-template class.

The table below records, for each commonly cited open-problem family, the concrete statement resolved within the certified class and the pipeline artifact that realizes the statement.

[t]
\centering
\small
\setlength{\tabcolsep}{4pt}

{p{0.30\linewidth} p{0.46\linewidth} p{0.20\linewidth}}
\toprule
Open-problem family & Resolved statement in the certified class & Pipeline artifact \\
\midrule
Decidability of robust switching stability / JSR-type questions [blondel_tsitsiklis_2000,kozyakin_jsr_bib]
&
Membership in \textup{RU-Stable} is decidable:
the pipeline returns either a robust contraction certificate (with $\varepsilon^*$ and explicit rate degradation) or an explicit obstruction witness (OG1–OG4), including the avoidance-cycle witness for recurrence failure (OG4).
&
robust_certificate \newline
or obstruction_witness
\\ \addlinespace

Mather-set structure for matrix sequences (ergodic optimization for JSR) [morris_mather_2013]
&
The extremal set is represented effectively by a finite symbolic system:
a tight-core subshift (Definition ) refined by the avoidance/recurrence automaton (Section ), yielding an explicit sofic description of extremal itineraries in the certified regime.
&
Tight-core graph $H$ \newline
+ avoidance automaton
\\ \addlinespace

Generic finiteness behavior for JSR and chamber regularity [devil_staircase_ems]
&
Away from certificate-failure surfaces (notably $\gamma \to 0$ and $\delta \to 0$) the tight core and obstruction regime are locally constant by the tight-core and Doeblin stability theorems, so extremal combinatorics and rates are stable on chambers.
Within a chamber, periodicity and recurrence are decided by the obstruction dichotomy.
&
$\gamma,\delta,\varepsilon^*$ \newline
+ chamber report
\\ \addlinespace

Devil’s-staircase boundary complexity vs.\ tame regions [devil_staircase_ems]
&
Complex behavior is confined to explicit boundary loci where the certificate margins collapse.
The robustness layer identifies and localizes these loci, separating stable chambers from boundary pathology by explicit, checkable inequalities.
&
Exceptional-set report \newline
(region mode)
\\
\bottomrule

\caption{How the robust certificate program resolves several open-problem families within the certified positive-template class (section 1).}

[t]
\centering
\small
\setlength{\tabcolsep}{4pt}

{p{0.30\linewidth} p{0.46\linewidth} p{0.20\linewidth}}
\toprule
Open-problem family & Resolved statement in the certified class & Pipeline artifact \\
\midrule
Černý-type synchronizing bounds for induced automata [slowly_sync_automata,synchronization_dfa]
&
For the specific automata generated by the certificate program (Doeblin-word search and avoidance automata),
the pipeline provides explicit state counts and either a bounded-gap modulus $B$ (acyclic avoidance) or an explicit cycle witness.
When the induced automata satisfy aperiodicity conditions that are checkable from the transition monoid, known special-class synchronizing bounds apply, yielding a quantitative reset bound for this subclass.
&
Automaton model \newline
+ modulus $B$ \newline
(+ optional reset bound)
\\ \addlinespace

Quantitative primitivity / length of a positive (Doeblin) product [primitive_digraph_exponent]
&
The Doeblin-word search is finite and yields either a positive product witness with margin $\delta$ or a certificate of failure within the searched regime.
In the certified setting, digraph exponent bounds and state-size bounds convert this into an explicit worst-case search radius for positivity on the core block.
&
Doeblin witness word \newline
(length $L$, margin $\delta$)
\\ \addlinespace

Barabanov/extremal norm geometry and constructive computation [barabanov_generic_unique]
&
A calibrated projective section together with recurrence (RC1) yields an explicit constructive extremal geometry:
a computable contraction mechanism and robustness neighborhood for the extremal dynamics.
This provides a concrete, checkable analogue of an extremal-norm package on the certified class.
&
Rate pack \newline
+ calibrated section \newline
+ robustness radii
\\ \addlinespace

Matrix-semigroup decision problems under bounded-language restrictions [freeness_bounded_language]
&
The certificate program restricts products to a constrained language (tight-core admissible words plus avoidance constraints).
Within that restricted language, the key decision questions needed for stability reduce to finite automata and finite witnesses, giving an explicit decidability template compatible with bounded-language decidability phenomena.
&
Language model \newline
(tight-core + constraints)
\\ \addlinespace

Mapping undecidable vs.\ decidable frontiers for matrix products [blondel_tsitsiklis_2000,kozyakin_jsr_bib]
&
The robust certificate contract isolates a decidable island and produces explicit exceptional sets where margins vanish.
This provides an operational frontier map: the pipeline states exactly which failures prevent certification and returns corresponding finite witnesses.
&
Frontier report \newline
(OG / RU margins)
\\
\bottomrule

\caption{How the robust certificate program resolves several open-problem families within the certified positive-template class (section 2).}

[t]
\centering
\small
\setlength{\tabcolsep}{4pt}

{p{0.30\linewidth} p{0.46\linewidth} p{0.20\linewidth}}
\toprule
Chaos-theory open-problem family & Resolved statement in the certified class & Pipeline artifact \\
\midrule
Effective description of chaos and turbulence [li_major_open_problems]
&
The long-run extremal dynamics admit an effective finite description: a tight-core symbolic model (graph/SFT/sofic refinement) together with a certificate dichotomy that returns either explicit uniform projective contraction data (rates and constants) or a finite obstruction witness.
On compact normalized parameter families within the certified regime, this upgrades to a finite cover/atlas: either a uniform good-global contraction certificate or a boundary-atlas report localizing degeneracy.
&
Tight-core + automata \\
+ robust certificate \\
+ cover/atlas report
\\ \addlinespace

Rough vs. sensitive dependence on initial data [li_major_open_problems]
&
In the \textup{RU-Stable} regime, extremal projective directions forget initial data at an explicit exponential rate (a quantitative “no-rough-dependence” statement on the certified observables).
Outside that regime, unpredictability is localized to explicit margin-collapse loci (e.g. $\gamma\to 0$ or $\delta\to 0$) with finite witnesses explaining the failure mechanism.
&
Rate pack $(\tau,C,\kappa)$ \\
+ margins $(\gamma,\delta,\varepsilon^*)$ \\
+ obstruction witnesses
\\ \addlinespace

Arrow of time / macroscopic irreversibility in chaotic settings [li_major_open_problems]
&
Uniform projective contraction on the extremal set yields a one-way “loss of memory” principle for coarse projective observables:
forward iteration collapses uncertainty to a unique attracting section at an explicit rate, while obstruction regimes certify persistent memory via periodic/avoidance witnesses.
&
Contraction theorem \\
+ recurrence modulus \\
+ obstruction taxonomy
\\ \addlinespace

Control-paradox themes (enrichment/pesticides/plankton as timing-sensitive forcing) [li_major_open_problems]
&
The certificate contract isolates when forcing/switching yields genuine mixing on the active face (Doeblin + recurrence) versus when timing constraints permit long avoidance of mixing.
In the latter case, the pipeline returns explicit avoidance-cycle witnesses, giving a rigorous “backfire” mechanism in the certified switching-template abstraction.
&
Doeblin-word witness \\
+ avoidance-cycle witness (OG4)
\\
\bottomrule

\caption{How the robust certificate program interfaces with major chaos-theory open-problem families (after Li) within the certified positive-template class.}

Interpretation.

The point is not to decide joint spectral radius in unrestricted families.
Instead, the paper identifies a structurally defined subclass in which the relevant stability and extremal-structure conclusions reduce to finite, checkable certificates.
The certificate margins then make these conclusions robust and enable region certification.

Chaos-theory positioning: “decidable islands” as effective description.

Li’s list of major open problems in chaos theory emphasizes a gap between qualitative narratives (“chaos”/“turbulence”) and effective structure that can be computed, verified, and transported across parameters [li_major_open_problems].
Within the certified positive-template class, the deliverable is precisely such effective structure: a finite symbolic descriptor (tight-core language plus finite refinements) together with a witness-producing dichotomy that either yields quantitative stability (explicit contraction data) or returns explicit finite obstructions localizing where stability cannot hold.
The robustness margins $(\gamma,\delta,\varepsilon^*)$ then turn this into a chamberwise and regionwise “frontier atlas” that separates stable regimes from boundary pathology by checkable inequalities.

Decidability frontier for robust switching stability.

Theorem gives a dichotomy:
either a robust certificate exists, producing explicit contraction rates and a robustness radius $\varepsilon^*$ (Definition ),
or an obstruction witness exists (OG1–OG4), and the witness is finite and verifiable.
This realizes a decidable island inside the broader JSR landscape where global decision problems are known to be hard and can be undecidable [blondel_tsitsiklis_2000].

Effective Mather-set and extremal-language description.

Within the certified class, the tight-core subshift (Definition ) and the avoidance/recurrence automata (Section ) produce an explicit sofic model for extremal itineraries.
This is the finite-state analogue of the qualitative Mather-set structure developed in the ergodic-optimization literature [morris_mather_2013].

Generic periodicity and chamber stability.

The chamber machinery (Section ) states that, away from explicit tie and margin-collapse loci, the tight combinatorics and the obstruction regime are locally constant.
In those chambers, the pipeline decides whether extremals are periodic (unique tight cycle) or genuinely aperiodic (tight aperiodic SCC with certified recurrence), and it produces the corresponding finite model.

Devil’s-staircase boundaries as certificate-failure surfaces.

The region certification layer (Section ) turns the informal slogan “complexity lives on the boundary” into a checkable statement:
nontrivial parameter dependence can only occur where the robustness margins $(\gamma,\delta,\varepsilon^*)$ collapse.
This separates stable chambers from boundary pathology in a way that complements known devil’s-staircase phenomena in broader families [devil_staircase_ems].

Synchronizing bounds for induced automata.

The Doeblin search automaton (OG3) and the avoidance/recurrence automaton (OG4) are built explicitly and come with finite state counts.
In the acyclic-avoidance regime, the return modulus $B$ is computed (Algorithm ), which is already a quantitative recurrence statement.
When the induced machines fall into tractable synchronizing subclasses (aperiodic, trivial group in the transition monoid, or related checkable hypotheses), known Černý-type bounds become available for these induced automata [slowly_sync_automata,synchronization_dfa].

Quantitative bounds on Doeblin-word length.

When a Doeblin block exists, the pipeline produces an explicit positive word and margin $\delta$ (OG3), and the robustness layer converts $\delta$ into contraction data.
In the certified setting, standard exponent bounds for primitive directed graphs can be used as plug-in upper bounds for the worst-case search radius on the core support [primitive_digraph_exponent].

Constructive extremal geometry and extremal-norm analogues.

The calibrated section and rate pack (Section ) provide a concrete geometric object that governs the extremal dynamics together with quantitative contraction and robustness radii.
This aligns with the extremal-norm narrative around Barabanov norms, but in the certified class the object is produced and verified by finite witnesses [barabanov_generic_unique].

Bounded-language semigroup decidability template.

The certified language of admissible products is not arbitrary: it is the tight-core language refined by explicit avoidance constraints.
This is precisely the kind of language restriction under which semigroup problems can become decidable in settings where the unrestricted problems are intractable [freeness_bounded_language].

Frontier mapping and explicit witnesses.

Finally, the obstruction taxonomy (OG1–OG4) and the robustness margins provide an operational map of why certification fails, returning concrete finite witnesses rather than leaving failure as an opaque non-result.
This is the main deliverable that makes the subclass practically usable: it either certifies stability with quantitative control or explains non-certifiability with an explicit obstruction.

Toward cover/atlas universality on compact normalized families within the certified class.

Theorem isolates the remaining step needed to upgrade from local robustness to a global statement on a compact region $\Theta$:
prove that the named margin-collapse loci are absent on $\Theta$ (equivalently: obtain uniform positive lower bounds for the certificate margins).
This can be achieved either by structural hypotheses that enforce uniform gaps, or by region mode plus a finite covering argument that certifies $\Theta$ and produces a global robustness radius.
If $\Theta$ intersects the named margin-collapse loci, the global procedure still terminates with a boundary-atlas report that localizes the degeneracy/obstruction region rather than asserting uniform contraction.