The Markov order of a stationary probability measure 
on sequences
over a finite alphabet 
is the least nonnegative integer 
for which the conditional
distribution of the future depends only on the preceding 
symbols. Here stationary means invariant under shifting the
sequence. More precisely, let 
denote the probability
of the finite word 
. The law is 
-step Markov if
 |
(1)
|
for all finite words 
, 
,
and 
such that 
. This formulation includes zero-probability words. Order 0 is equivalent to the symbols being independent
and identically distributed. If no such integer exists,
the Markov order is infinite.
Writing 
for the set of finite words over
, the intrinsic dimension of the law
can be defined using the vector space span of
the functions 
by
 |
(2)
|
Equivalently, 
is the matrix rank of the infinite matrix
whose 
entry is 
.
Béal et al. (2026) attribute the word-law rank criterion used in the
proof to Holland (1968).
For an invariant sofic measure with minimal linear representation of dimension 
and finite Markov order, Béal et al. (2026)
proved
 |
(3)
|
They proved that this bound is sharp even over an alphabet of size 3. The proof uses the second exterior power
to reduce the assertion to uniform nilpotence in dimension 
. Béal et al. (2026) report that Gemini
proposed an extremal-set-theory approach and GPT-6 Astra supplied the exterior-algebra
argument.
An earlier authorless release, "Sharp Finite Markov Order in Intrinsic Sofic Dimension" (2026), announced the same upper bound, with sharp examples over larger alphabets. The binomial-delay precedent for deterministic local automata is due to Béal and Senellart (1998), and the pair-chain core used in that construction appears in Trahtman (1998).
That earlier release's accompanying Lean development checks the one-sided upper bound and the rational stationary examples, but does not formalize the passage to two-sided processes or the literature comparison. As of Sep. 8, 2026, no specialist review had been reported. The released source identifies the work as AI-generated and gives GPT-6 Astra as a default attribution, while noting that runtime model provenance was not retained.
