Abelian maximal pattern complexity and extremal words

In this paper, we study the Abelian maximal pattern complexity $p_{\alpha }^{\ast ab}(k)$, introduced by Kamae, Widmer and Zamboni, of infinite words $\alpha \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 an exact structure of words with minimal Abelian maximal pattern complexity. In the general case, we prove that an infinite word $\alpha$ is aperiodic if and only if $\left(\genfrac{}{}{0ex}{}{p_{\alpha }^{\ast ab}(k)}{2}\right)\ge k$ for every $k.$ For aperiodic words over $\ell \ge 2$ letters, each occurring infinitely often, we further prove that $p_{\alpha }^{\ast ab}(k)\ge m$ whenever $\left(\genfrac{}{}{0ex}{}{m}{2}\right)\le (\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 $\left(\genfrac{}{}{0ex}{}{m}{2}\right)\ge 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.