Friedman序列

Friedman序列，是 Harvey Friedman 提出的。

定义

考虑一个正整数构成的序列$\{a_1,a_2,\cdots ,a_k\}$,我们定义Friedman序列如下：

若对于正整数k来说，序列满足不存在正整数$1\le i<j\le k/2$,使得$\{a_i,a_{i+1},\cdots ,a_{2i}\}$是$\{a_j,a_{j+1},\cdots ,a_{2j}\}$的子序列，则称其为关于k的Friedman序列。

函数$n(k)$定义为关于k的Friedman序列所可能具有的最大长度。

Friedman证明了，$n(k)$一定是有限的。

对于$k=1$的情况我们有$n(1)=3$.相应的Friedman序列为$\{1,1,1\}$.

对于$k=2$的情况我们有$n(2)=11$.相应的Friedman序列为$\{1,2,2,2,1,1,1,1,1,1,1\}$.

对于更大的k，我们不知道$n(k)$的具体数值。

对于k=3来说，我们有如下的上下界：$A(7198,158386)<n(3)\le A(A(5))$

对于k=4来说，我们有如下的上下界：$n(4)\ge A^{A(187196)}(1)$.

在上述表达式中，A函数定义为：

• $A(1,n)=2n$
• $A(m+1,n)=2{\uparrow }^{m-1}n$
• $A(n)=A(n,n)$
• $A^m(n)=\underset{m\text{个}A}{\underbrace{A(A(A(\cdots (A(}}n))\cdots )))$

n(k)的FGH增长率是${\omega }^{\omega }$.

传言

值得注意的是，n(4)是TREE3的老下界。因此$A^{A(187196)}(1)$在有些资料里作为TREE3的下界出现。但这是错误的。TREE3的下界已经提升。