pith. sign in

arxiv: 2604.11212 · v1 · submitted 2026-04-13 · 🧮 math.PR · math.DS

Sofic measures

Marie-Pierre B\'eal , Vincent Jug\'e , Jean Mairesse , Dominique Perrin This is my paper

Pith reviewed 2026-05-10 15:39 UTC · model grok-4.3

classification 🧮 math.PR math.DS
keywords sofic measureshidden Markov measuresk-step Markov chainslinear representationsshift-invariant measuressymbolic dynamicsprobability measures on sequences
0
0 comments X

The pith

If an invariant sofic measure has an n-dimensional linear representation and is Markov, then it is at most 2^{n^2-1}-step Markov.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

Sofic measures, also called hidden Markov measures, are shift-invariant probability distributions on sequences that can be realized by finite linear representations. The paper improves an existing bound that helps decide whether a given sofic measure is Markovian. If such a measure with a representation of dimension n is a k-step Markov chain for any k, then the same measure is already a Markov chain of order at most 2 to the power of n squared minus one. The result follows from the standard equivalence between sofic measures and their linear representations and yields a finite test for the Markov property once n is fixed.

Core claim

We prove that if an invariant sofic measure with a linear representation of dimension n is a k-step Markov chain, then k can be chosen at most equal to 2^{n^2-1}.

What carries the argument

The n-dimensional linear representation of the sofic measure, which encodes the evolution of the measure under the shift via matrix or vector operations.

Load-bearing premise

The measure is invariant under the shift and admits a finite-dimensional linear representation of size n.

What would settle it

An explicit invariant sofic measure with an n-dimensional linear representation that is Markov but requires order strictly larger than 2^{n^2-1} would falsify the bound.

Figures

Figures reproduced from arXiv: 2604.11212 by Dominique Perrin, Jean Mairesse, Marie-Pierre B\'eal, Vincent Jug\'e.

Figure 3.1
Figure 3.1. Figure 3.1: A sofic measure. Using the 1-block map f(1) = a and f(2) = f(3) = b, we obtain an invariant sofic measure defined by the diagram of [PITH_FULL_IMAGE:figures/full_fig_p006_3_1.png] view at source ↗
Figure 4
Figure 4. Figure 4: on the left. Using the same 1-block factor map as in Example 3.2, [PITH_FULL_IMAGE:figures/full_fig_p007_4.png] view at source ↗
Figure 4.1
Figure 4.1. Figure 4.1: on the left. Using the same 1-block factor map as in Example 3.2, we obtain the sofic measure represented on the right. 1 2 3 1 2 1 2 1 2 1 2 1 2 1 2 1 2 3 b| 1 2 b| 1 2 a| 1 2 b| 1 2 b| 1 2 a| 1 2 [PITH_FULL_IMAGE:figures/full_fig_p007_4_1.png] view at source ↗
read the original abstract

Sofic measures, also known as hidden Markov measures, have been extensively studied. In this paper, we survey some equivalent definitions of this notion and improve a bound for deciding whether a sofic measure is~$k$-step Markov. We prove that if an invariant sofic measure with a linear representation of dimension~$n$ is a~$k$-step Markov chain, then~$k$ can be chosen at most equal to~$2^{n^2-1}$.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 2 minor

Summary. The manuscript surveys equivalent definitions of sofic measures (also called hidden Markov measures) and proves an improved bound: if an invariant sofic measure admits a linear representation of dimension n and is a k-step Markov chain, then k can be taken at most 2^{n^2-1}.

Significance. If the central claim holds, the result supplies an explicit, representation-dimension-dependent upper bound on Markov order for invariant sofic measures. The argument applies the pigeonhole principle to the finite collection of possible behaviors of the n-dimensional linear representation under the shift, using only the standard equivalence between sofic measures and such representations together with shift-invariance to guarantee a stationary initial vector. This strengthens prior bounds in symbolic dynamics and ergodic theory and could support algorithmic verification of the Markov property.

minor comments (2)
  1. The abstract states that equivalent definitions are surveyed, but the provided text does not enumerate or cross-reference them; the full manuscript should list the main equivalences and indicate which are used in the proof of the bound.
  2. The origin of the precise exponent 2^{n^2-1} is not explained in the abstract or the sketched argument; a short paragraph clarifying how the counting of distinct matrix-vector configurations under the shift produces this number (including the role of the -1) would improve readability without altering the result.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive assessment of our manuscript and for recognizing the significance of the improved bound on Markov order for invariant sofic measures. The referee's summary accurately captures the paper's contribution.

Circularity Check

0 steps flagged

No significant circularity; bound follows from pigeonhole on finite configurations

full rationale

The central result is a combinatorial bound: if an invariant sofic measure admits an n-dimensional linear representation and happens to be Markov of some order, then it is Markov of order at most 2^{n^2-1}. The proof applies the pigeonhole principle to the finite collection of distinct possible future behaviors encoded by vectors in R^n under the action of the n x n transition matrices. Invariance ensures the initial vector is stationary, but the repetition argument itself depends only on the finite dimensionality of the representation space and does not rely on any fitted parameter, self-referential definition, or load-bearing self-citation. The equivalence between sofic measures and linear representations is invoked as a standard external fact, not derived inside the paper. No step reduces the claimed bound to an input by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claim rests on the standard framework of sofic measures via linear representations and shift-invariance; no new free parameters, ad-hoc axioms, or invented entities are introduced.

axioms (2)
  • domain assumption Sofic measures admit equivalent definitions via finite automata and linear representations of finite dimension
    Invoked to state the hypothesis of the bound.
  • domain assumption The measure is invariant under the one-sided or two-sided shift
    Required for the Markov property to be well-defined in the stationary case.

pith-pipeline@v0.9.0 · 5364 in / 1320 out tokens · 49777 ms · 2026-05-10T15:39:33.580116+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

9 extracted references · 9 canonical work pages

  1. [1]

    Cambridge University Press, Cambridge, 2011

    Jean Berstel and Christophe Reutenauer.Noncommutative rational series with applications, volume 137 ofEncyclopedia of Mathematics and its Applications. Cambridge University Press, Cambridge, 2011

    work page 2011

  2. [2]

    Hidden markov processes in the context of symbolic dynamics

    Mike Boyle and Karl Petersen. Hidden markov processes in the context of symbolic dynamics. InEntropy of Hidden Markov Processes and Connections to Dynamical Systems, Papers from the Banff International Research Station Workshop. London Mathematical Society Lecture Note Series, Cambridge University Press, 2011

    work page 2011

  3. [3]

    Princeton University Press, 1960

    Harry Furstenberg.Stationary Processes and Prediction Theory. Princeton University Press, 1960. Annals of Mathematical Studies, 44

    work page 1960

  4. [4]

    Rational probability measures

    Georges Hansel and Dominique Perrin. Rational probability measures. Theoretical Computer Science, 65(2):171–188, 1989

    work page 1989

  5. [5]

    Variations on the Bollob´ as set-pair theorem.Eur

    G´ abor Heged¨ us and P´ eter Frankl. Variations on the Bollob´ as set-pair theorem.Eur. J. Comb., 120(C), August 2024. 11

    work page 2024

  6. [6]

    On Stochastic Processes Derived From Markov Chains.The Annals of Mathematical Statistics, 36(4):1286 – 1291, 1965

    Alex Heller. On Stochastic Processes Derived From Markov Chains.The Annals of Mathematical Statistics, 36(4):1286 – 1291, 1965

    work page 1965

  7. [7]

    Paul W. Holland. Some Properties of an Algebraic Representation of Stochastic Processes.The Annals of Mathematical Statistics, 39(1):164 – 170, 1968

    work page 1968

  8. [8]

    Flats in matroids and geometric graphs.Combinatorial Surveys, 01 1977

    L´ aszl´ o Lov´ asz. Flats in matroids and geometric graphs.Combinatorial Surveys, 01 1977

    work page 1977

  9. [9]

    Cambridge University Press, 2009

    Jacques Sakarovitch.Elements of Automata Theory. Cambridge University Press, 2009. 12

    work page 2009