标题： 无限词及其相关结构中的复杂性与递归性 显示英文标题

标题： Complexity and recurrence in infinite words and related structures

摘要： 我们研究无限词的定量组合度量及其相关动力和代数结构的渐近行为和细尺度行为。 我们构造了无限循环词$w$，其复杂度函数$p_w(n)$可以任意接近线性，但其离散导数不被$p_w(n)/n$从上方限制。 此外，我们构造了多项式复杂度有界的词，对于每一个给定的$\varepsilon>0$，其离散导数会无限次超过$p_w(n)/n^\varepsilon$。 这些结果在强烈意义上对 Cassaigne 于 1997 年提出的一个开放问题给出了否定回答，表明他在线性复杂度词上的定理是最佳的。 接下来，我们大致上通过线性乘法误差来刻画严格遍历子移位的复杂度函数，证明在此情形下每个非递减的、次乘函数都会出现。 这给出了第一个“工业”构造方法，用于构建具有指定次指数复杂度的严格遍历子移位。 随后，我们研究了均匀循环词中的定量重现，并作为应用，解决了 Bavula 在 2006 年提出的关于简单结合代数可能滤子维数谱上的解析不等式的相关问题：我们在$[1,\infty)$中构造了具有指定滤子维数的简单代数，并在分次情况下基本上完全解决了这个问题。 在整个过程中，我们构造了线性复杂度且具有任意多项式重现增长的均匀循环词。 显示英文摘要

摘要： We study the asymptotics and fine-scale behavior of quantitative combinatorial measures of infinite words and related dynamical and algebraic structures. We construct infinite recurrent words $w$ whose complexity functions $p_w(n)$ are arbitrarily close to linear, but whose discrete derivatives are not bounded from above by $p_w(n)/n$. Moreover, we construct words of polynomially bounded complexity whose discrete derivatives exceed $p_w(n)/n^\varepsilon$ infinitely often, for every given $\varepsilon>0$. These provide negative answers in a strong sense to an open question of Cassaigne from 1997, showing that his theorem on words of linear complexity is best possible. Next, we characterize, up to a linear multiplicative error, the complexity functions of strictly ergodic subshifts, showing that every non-decreasing, submultiplicative function arises in this setting. This gives the first `industrial' construction of strictly ergodic subshifts of prescribed subexponential complexity. We then investigate quantitative recurrence in uniformly recurrent words and, as an application, address a question of Bavula from 2006 related to holonomic inequalities on the spectrum of possible filter dimensions of simple associative algebras: we construct simple algebras of prescribed filter dimension in $[1,\infty)$ and essentially settling the problem entirely in the graded case. Throughout, we construct uniformly recurrent words of linear complexity and with arbitrary polynomial recurrence growth.