Brik's sequence: a strange recursion

技术摘要：Brik 序列：一种奇怪的递归

问题陈述
本文研究了由 Garo Brik 于 2018 年提出的一种特定递归迭代生成的二进制词序列 $(B_i)_{i \ge 1}$ 及其产生的无限二进制序列 $b$ 的性质。该序列由基本情况 $B_1 = 101$ 和递推关系 $B_{i+1} = B_i C_i$（对于 $i \ge 1$）定义，其中 $C_i$ 是通过移除 $B_i$ 的前 $i$ 个符号得到的 $B_i$ 的后缀。由于对于所有 $i \ge 2$，$B_{i-1}$ 都是 $B_i$ 的前缀，这些词收敛于一个唯一的无限序列 $b$。本文旨在刻画 $b$ 的组合与算术性质，包括其递归性、因子复杂度、形态性质以及符号'1'的密度。

方法论
分析采用了归纳证明、关于词因子的组合论证以及解析数论技术的结合。

• 结构分析：作者通过平凡归纳法确立了词 $B_i$ 的长度及其后缀性质。他们利用“边界”（既是前缀又是后缀）的概念来证明特定索引是“好的”，即 $B_i$ 是 $B_{\ell_i}$ 的边界。
• 递归性与复杂度：本文分析了 $b$ 中因子的出现情况以确定递归性质。通过识别禁止子串，刻画了所有有效因子的集合。
• 增长分析：使用递推关系追踪特定模式（特别是连续 1 的序列）的起始位置，并利用 Knuth 的超幂记号分析增长率。
• 密度计算：通过分析长度为 $\ell_n = |B_n|$ 的前缀中 1 的数量推导出 1 的密度。作者导出了一个涉及序列本身二进制展开的极限公式，并利用误差项分析（$E(N)$）将该极限从特定前缀扩展到任意前缀。
• 超越性证明：为了确定密度极限 $\alpha$ 的性质，本文应用了 Adamczewski 和 Bugeaud 提出的“结巴”（stammering）判据的简化版本，该判据将序列的重复结构与其二进制展开所形成数的超越性联系起来。

主要贡献与结果

1. 递归性质：

   • 证明了无限词 $b$ 是递归的（每个有限因子都无限次出现），但非一致递归的。
   • 本文证明了 $b$ 包含任意长度的连续 1 序列（即对所有 $n$ 都有 $1^n$），这排除了其一致递归性。$1^n$ 首次出现的起始位置 $r_n$ 遵循递推关系 $r_{n+1} = 2^{r_{n-2}} + r_n$（对于 $n \ge 2$），导致极快的增长（超幂）。

2. 因子复杂度：

   • 提供了 $b$ 因子的完整刻画：一个二进制词是 $b$ 的因子，当且仅当它不包含两个连续的 0。
   • 因此，长度为 $n$ 的不同因子的数量恰好是 $F_{n+2}$（第 $n+2$ 个斐波那契数）。这确立了 $b$ 具有指数级因子复杂度。

3. 非形态性质：

   • 基于指数级因子复杂度，本文得出结论：$b$ 不是形态的。这遵循 Ehrenfeucht、Lee 和 Rozenberg 的结果，该结果指出形态序列必须具有多项式因子复杂度（具体为 $O(n^2)$）。

4. 1 的密度：

   • 本文证明了 $b$ 中 1 的渐近密度 $\alpha = \lim_{n \to \infty} \frac{a(n)}{n}$ 存在。
   • 该值由公式 $\alpha = 2 - 2\sum_{i \ge 1} b_i 2^{-i}$ 给出，其中 $b_i$ 是序列的第 $i$ 位。
   • 数值约为 $0.64505878493452$。

5. 超越性：

   • 证明了密度 $\alpha$ 是超越数。证明依赖于利用“结巴”判据证明相关数 $\beta = \sum b_i 2^{-i}$ 是超越数。由于 $\beta$ 不可能是有理数（否则意味着有界的因子复杂度），且该序列表现出所需的“结巴”结构（$B_{n+1}$ 包含 $B_n$ 后跟其后缀的重复），因此 $\beta$（从而 $\alpha$）必须是超越数。

意义与声明
本文展示了一个序列，尽管其定义基于简单的迭代规则，却表现出微妙且复杂的、并非显而易见的性质。其主要意义在于发现了一个递归但非一致递归、具有指数级因子复杂度并生成超越性 1 密度的序列。作者指出，该序列出现在 OEIS 中（作为 A334820，缺失初始项），并强调了递归定义与由此产生的算术性质之间的相互作用。

本文明确承认，这些结果是通过在 2026 年 5 月使用 APL 进行实验并与 ChatGPT 5.5 合作获得的，所有声明随后均由作者重写并验证。该工作作为递归定义二进制词的性质以及超越性判据在组合序列中应用的案例研究。