{
  "abstract": "In this paper, we study the Abelian maximal pattern complexity $p_α^{\\ast \\mathrm{ab}}(k)$, introduced by Kamae, Widmer and Zamboni, of infinite words $α\\in \\mathbb{A}^{\\mathbb{N}_{0}}$ over finite alphabets $\\mathbb{A}$. 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 $\\binom{p_{α}^{\\ast \\mathrm{ab}}(k)}{2}\\geq k$ for every $k.$ For aperiodic words over $\\ell \\geq 2$ letters, each occurring infinitely often, we further prove that $p_{α}^{\\ast \\mathrm{ab}}(k)\\geq m$ whenever $\\binom{m}{2}\\leq (\\ell -1)(k-\\ell +2)$, for all $m,k$. Together with a matching construction, this shows that the minimum Abelian maximal pattern complexity in this class is $\\sqrt{2(\\ell -1)k}+O_{\\ell }(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 $\\binom{m}{2}\\geq 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\\subset \\mathbb{N}_{0}$ for which the bipartite graph on two disjoint copies of $\\mathbb{N}_{0}$, with a left vertex $r$ adjacent to a right vertex $s$ exactly when $r+s\\in E$, is a forest.",
  "abstract_shown": true,
  "affiliations": [],
  "article_type": null,
  "arxiv": "2609.28059",
  "author_total": 3,
  "authors": [
    {
      "name": "Qingcheng Zeng"
    },
    {
      "name": "Yumei Xue"
    },
    {
      "name": "Cheng Zeng"
    }
  ],
  "bibtex": "https://research.draconitic.com/paper/ajnyfhq6f6rsb.bib",
  "cited_by": 0,
  "doi": "10.48550/arxiv.2609.28059",
  "fulltext_url": null,
  "id": "ajnyfhq6f6rsb",
  "issns": [],
  "landing_url": "https://arxiv.org/abs/2609.28059",
  "language": null,
  "licence": "LicenseRef-arXiv-nonexclusive-1.0",
  "licence_label": "arXiv licence",
  "licence_source": "article",
  "licence_url": "http://arxiv.org/licenses/nonexclusive-distrib/1.0/",
  "metadata_licence": "CC0-1.0",
  "native_subjects": [
    [
      "arxiv",
      "math.CO"
    ],
    [
      "arxiv",
      "math.DS"
    ],
    [
      "openalex",
      "1703|semigroups and automata theory"
    ]
  ],
  "openalex": "W7214237291",
  "pdf_url": "https://arxiv.org/pdf/2609.28059",
  "pmcid": null,
  "pmid": null,
  "published": "2026-10-22",
  "publisher": null,
  "ris": "https://research.draconitic.com/paper/ajnyfhq6f6rsb.ris",
  "sources": [
    {
      "first_seen": "2026-10-30T12:34:38Z",
      "native_id": "2609.28059",
      "source": "arxiv",
      "url": "https://arxiv.org/abs/2609.28059"
    }
  ],
  "subjects": [
    {
      "field": "mathematics",
      "origin": "arxiv:math.CO",
      "subfield": "combinatorics"
    },
    {
      "field": "mathematics",
      "origin": "arxiv:math.DS",
      "subfield": "dynamical-systems"
    }
  ],
  "title": "Abelian maximal pattern complexity and extremal words",
  "title_text": "Abelian maximal pattern complexity and extremal words",
  "type": "preprint",
  "updated_at": "2026-11-05T15:20:22Z",
  "url": "https://research.draconitic.com/paper/ajnyfhq6f6rsb",
  "venue": "arXiv",
  "versions": []
}