Abelian maximal pattern complexity and extremal words
Abstract
In this paper, we study the Abelian maximal pattern complexity pα∗ ab(k), introduced by Kamae, Widmer and Zamboni, of infinite words α∈ 𝔸ℕ0 over finite alphabets 𝔸. For recurrent aperiodic words, we determine a lower bound and prove its sharpness. We further give a structural characterization of the words with minimal Abelian maximal pattern complexity. In the general case, we prove that an infinite word α is aperiodic if and only if binompα∗ ab(k)2≥ k for every k. For aperiodic words over ℓ ≥ 2 letters, each occurring infinitely often, we further prove that pα∗ ab(k)≥ m whenever binomm2≤ (ℓ −1)(k−ℓ +2), for all m,k. Together with a matching construction, this shows that the minimum Abelian maximal pattern complexity in this class is √(2(ℓ −1)k)+Oℓ (1). We call a word an Abelian pattern Sturmian word if, at every k, its Abelian maximal pattern complexity is the least positive integer m satisfying binomm2≥ k. We show that a word is Abelian pattern Sturmian if and only if, after relabeling its alphabet, it is the characteristic word of an infinite set E⊂ ℕ0 for which the bipartite graph on two disjoint copies of ℕ0, with a left vertex r adjacent to a right vertex s exactly when r+s∈ E, is a forest.
Related
- Abelian maximal pattern complexity of two-dimensional words
- Generating Forbidden Words and Measures of Maximal Entropy for Subshifts
- On the number of palindromic factors of low complexity words
- Complexes of pattern-avoiding injective words
- Maximal proper extremal subset in the crystal basis of a finite-dimensional irreducible module
BibTeX
@misc{zeng2026abelian,
title = {{Abelian maximal pattern complexity and extremal words}},
author = {Qingcheng Zeng and Yumei Xue and Cheng Zeng},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2609.28059},
eprint = {2609.28059},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.28059},
}
RIS
TY - UNPB
TI - Abelian maximal pattern complexity and extremal words
AU - Qingcheng Zeng
AU - Yumei Xue
AU - Cheng Zeng
PY - 2026
DA - 2026/10/22
PB - arXiv
DO - 10.48550/arxiv.2609.28059
UR - https://arxiv.org/abs/2609.28059
AB - In this paper, we study the Abelian maximal pattern complexity p_α^∗ ab(k), introduced by Kamae, Widmer and Zamboni, of infinite words α∈ 𝔸^ℕ_0 over finite alphabets 𝔸. For recurrent aperiodic words, we determine a lower bound and prove its sharpness. We further give a structural characterization of the words with minimal Abelian maximal pattern complexity. In the general case, we prove that an infinite word α is aperiodic if and only if binomp_α^∗ ab(k)2≥ k for every k. For aperiodic words over ℓ ≥ 2 letters, each occurring infinitely often, we further prove that p_α^∗ ab(k)≥ m whenever binomm2≤ (ℓ −1)(k−ℓ +2), for all m,k. Together with a matching construction, this shows that the minimum Abelian maximal pattern complexity in this class is √(2(ℓ −1)k)+O_ℓ (1). We call a word an Abelian pattern Sturmian word if, at every k, its Abelian maximal pattern complexity is the least positive integer m satisfying binomm2≥ k. We show that a word is Abelian pattern Sturmian if and only if, after relabeling its alphabet, it is the characteristic word of an infinite set E⊂ ℕ_0 for which the bipartite graph on two disjoint copies of ℕ_0, with a left vertex r adjacent to a right vertex s exactly when r+s∈ E, is a forest.
ER -