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

低複雑度二進法語における $(5/2)^+$ -べき乗の回避

基本情報

論文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$ に対して長さ $n$ の因子をちょうど $2n$ 個含む無限数列である。ShalitとShur、およびOllingerとShalitは、 $(5/2)^+$ -べき乗を回避するRote数列が存在し、これが最適であることを証明した。本論文は、 $(5/2)^+$ -べき乗を回避するRote数列の構造定理を与え、OllingerとShalitの予想を確認する。

研究背景と動機

中心的問題

本研究は、組合せ語理論における2つの中心的概念、すなわちべき乗回避性と因子複雑度に焦点を当てている。具体的には、 $(5/2)^+$ -べき乗を回避し、最低複雑度（ $2n$ ）を持つすべての二進法無限数列の構造を特徴付けることを目指している。

問題の重要性

理論的意義：べき乗回避性と因子複雑度は組合せ語理論の基礎概念であり、それらの相互関係はこの分野の中心的研究方向である
構造理論：Restivo-Salemiの重複なし数列に関する古典的構造定理と同様に、本研究は新しい構造定理を確立する
予想の検証：OllingerとShalitが提出したRote数列の構造に関する重要な予想を確認する

既存研究の限界

ShalitとShur、およびOllingerとShalitは、 $(5/2)^+$ -べき乗を回避するRote数列の存在性と最適性を証明したが、完全な構造特性付けが欠けている
既存の研究は具体的な構築例のみを提供し、一般的な構造定理を提供していない

研究動機

Restivo-Salemi定理が重複なし二進法数列を特徴付けるのと同様に、完全な構造定理を確立し、低複雑度数列のべき乗回避特性を理解するための理論的基礎を提供する。

中核的貢献

適切（proper）および反適切（antiproper）数列の概念を提案：三進法数列の2つの重要な部分クラスを定義
第1の構造定理を確立：適切および反適切数列の再帰的構造を特徴付け
第2の構造定理を証明： $(5/2)^+$ -べき乗を回避するRote数列の構造を完全に特徴付け
Ollinger-Shallit予想を検証：態射 $f$ と $g$ を含む完全な構造特性付けを提供
計算検証を提供：バックトラッキング探索により主要補題の正確性を検証

方法の詳細説明

タスク定義

入力：二進法無限数列 $w$ 制約条件：

$w$ はRote数列である（因子複雑度は $2n$ ）
$w$ は $(5/2)^+$ -べき乗を回避する

出力： $w$ の構造特性付け、すなわち $w$ が特定の態射を適切または反適切数列に作用させた形式で表現できることの証明

主要定義

適切および反適切数列

三進法数列 $u \in \Sigma_3^*$ に対して、Parikh ベクトル $\pi(u) = [|u|_0, |u|_1, |u|_2]$ を定義する。

適切数列は以下を満たす：

$\pi(x) > \pi(y)$ である因子 $xyxyx$ を含まない
以下の因子を含まない： $00, 11, 22, 20, 10101, 2121, 10210210$

反適切数列：その逆順が適切数列である

主要な態射

態射 $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. 再帰的構造分析

適切および反適切数列が自己相似の再帰的構造を持ち、態射 $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)