2025-11-16T20:37:12.974994

Low complexity binary words avoiding $(5/2)^+$-powers

Currie, Rampersad

Rote words are infinite words that contain $2n$ factors of length $n$ for every $n \geq 1$. Shallit and Shur, as well as Ollinger and Shallit, showed that there are Rote words that avoid $(5/2)^+$-powers and that this is best possible. In this note we give a structure theorem for the Rote words that avoid $(5/2)^+$-powers, confirming a conjecture of Ollinger and Shallit.

academic

Low complexity binary words avoiding $(5/2)^+$ -powers

基本信息

论文ID: 2506.19050
标题: Low complexity binary words avoiding $(5/2)^+$ -powers
作者: James Currie, Narad Rampersad
分类: math.CO (组合数学), cs.FL (形式语言)
发表时间: 2025年10月13日 (arXiv预印本)
论文链接: https://arxiv.org/abs/2506.19050

摘要

Rote序列是对每个 $n \geq 1$ 都恰好包含 $2n$ 个长度为 $n$ 的因子的无穷序列。Shallit和Shur以及Ollinger和Shallit证明了存在避免 $(5/2)^+$ -幂的Rote序列，且这是最优的。本文给出了避免 $(5/2)^+$ -幂的Rote序列的结构定理，证实了Ollinger和Shallit的一个猜想。

研究背景与动机

核心问题

本研究关注组合词理论中的两个核心概念：幂避免性和因子复杂度。具体要解决的问题是：刻画所有避免 $(5/2)^+$ -幂且具有最低复杂度( $2n$ )的二进制无穷序列的结构。

问题重要性

理论意义：幂避免性和因子复杂度是组合词理论的基础概念，它们的相互关系是该领域的核心研究方向
结构理论：类似于Restivo-Salemi关于无重叠序列的经典结构定理，本研究建立了新的结构定理
猜想验证：证实了Ollinger和Shallit提出的关于Rote序列结构的重要猜想

现有研究局限性

Shallit和Shur以及Ollinger和Shallit虽然证明了避免 $(5/2)^+$ -幂的Rote序列的存在性和最优性，但缺乏完整的结构刻画
现有工作只给出了具体的构造例子，没有提供一般性的结构定理

研究动机

建立完整的结构定理，类似于Restivo-Salemi定理对无重叠二进制序列的刻画，为理解低复杂度序列的幂避免性质提供理论基础。

核心贡献

提出了proper和antiproper序列的概念：定义了三进制序列的两个重要子类
建立了第一个结构定理：刻画了proper和antiproper序列的递归结构
证明了第二个结构定理：完全刻画了避免 $(5/2)^+$ -幂的Rote序列的结构
验证了Ollinger-Shallit猜想：提供了涉及态射 $f$ 和 $g$ 的完整结构刻画
提供了计算验证：通过回溯搜索验证了关键引理的正确性

方法详解

任务定义

输入：二进制无穷序列 $w$ 约束条件：

$w$ 是Rote序列（因子复杂度为 $2n$ ）
$w$ 避免 $(5/2)^+$ -幂

输出： $w$ 的结构刻画，即证明 $w$ 可以表示为特定态射作用于proper或antiproper序列的形式

关键定义

Proper和Antiproper序列

对于三进制序列 $u \in \Sigma_3^*$ ，定义Parikh向量 $\pi(u) = [|u|_0, |u|_1, |u|_2]$ 。

Proper序列满足：

不包含因子 $xyxyx$ ，其中 $\pi(x) > \pi(y)$
不包含因子： $00, 11, 22, 20, 10101, 2121, 10210210$

Antiproper序列：其逆序是proper序列

关键态射

定义态射 $f: \Sigma_3^* \to \Sigma_3^*$ 和 $h: \Sigma_3^* \to \Sigma_3^*$ ：

$f(0) = 0121$ , $f(1) = 021$ , $f(2) = 01$
$h(0) = 1210$ , $h(1) = 120$ , $h(2) = 10$

定义态射 $g: \Sigma_3^* \to \Sigma_2^*$ ：

$g(0) = 011$ , $g(1) = 0$ , $g(2) = 01$

核心技术方法

1. 因子分析法

通过详细分析避免 $(5/2)^+$ -幂的二进制序列必须包含的长度为4的因子，确定了这类序列的基本结构约束。

关键引理：

引理1：任何避免 $(5/2)^+$ -幂的无穷二进制序列都必须包含因子 $0110$ 和 $1001$
引理3：具有因子复杂度 $\leq 2n$ 且避免 $(5/2)^+$ -幂的序列必须包含因子 $0011$ 和 $1100$

2. 回溯搜索验证

使用计算机程序验证关键引理，通过构造性证明确定了约束条件的必要性。

3. 递归结构分析

证明proper和antiproper序列具有自相似的递归结构，可以通过态射 $f$ 和 $h$ 进行刻画。

实验设置

计算验证方法

论文使用Python实现了回溯搜索算法来验证关键引理：

def fhpf(w): # 检查序列w是否避免5/2+幂
    p=1
    while (5*p<2*len(w)):
        if (w[(-(p+1)//2)-p:]==w[(-(p+1)//2)-2*p:-p]):
            return(False)
        p=p+1
    return(True)

验证内容

引理1验证：最长的不包含 $0110$ 且避免 $(5/2)^+$ -幂的序列长度为14
引理2验证：验证了集合 $C = \{0010, 0100, 1011, 1101\}$ 中至少3个元素必须出现
引理3验证：对集合 $A$ 中的每个元素进行了详细验证
引理4验证：验证了17个长度为9的特定序列的约束条件

实验结果

主要结果

定理1（第一结构定理）

对于proper序列 $u \in \Sigma_3^{\omega}$ ，其某个后缀具有形式 $f(v)$ ，其中 $v$ 是proper序列
对于antiproper序列 $u \in \Sigma_3^{\omega}$ ，其某个后缀具有形式 $h(v)$ ，其中 $v$ 是antiproper序列