查看“︁Friedman序列”︁的源代码

Friedman序列，是 Harvey Friedman 提出的。

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

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

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

Friedman证明了，<math>n(k)</math>一定是有限的。<ref>Harvey Friedman, [https://u.osu.edu/friedman.8/files/2014/01/LongFinSeq98-2f0wmq3.pdf Long Finite Sequences]</ref>

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

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

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

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

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

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

* <math>A(1,n)=2n</math>
* <math>A(m+1,n)=2\uparrow^{m-1}n</math>
* <math>A(n)=A(n,n)</math>
* <math>A^m(n)=\underbrace{A(A(A(\cdots(A(}_{m\text{个}A}n))\cdots)))</math>

n(k)的[[FGH]][[增长率]]是<math>\omega^\omega</math>.

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

{{默认排序:相关问题}}
[[分类:记号]]