Circle函数

Circle函数是Harvey Friedman提出的一个快速增长的函数

定义

由平面上n个不相交的圆(可能外离或内含)组成了一个序列$\{C_1,C_2,\cdots ,C_n\}$.把并集$C_a\cup C_{a+1}\cup \cdots C_{b-1}\cup C_b$记作$C_{[a,b]}$.给定一个正整数k，如果存在满足“$k\le i<j\le n/2$,且存在把$C_{[i,2i]}$变成$C_{[j,2j]}$的子集的同胚拓扑变换”的$(i,j)$对，那么称这样的n圆组为“k-好”的。我们定义如下的Circle序列：Circle(k)定义为所有不是“k-好”的n圆组中n的最大值。

森林解释

对于平面上任何圆的集合 S，我们自然可以将其 S 解释为森林，每个圆对应于森林中的不同顶点。根顶点将对应于不包含在任何其他圆中的圆。如果顶点 v 对应于圆 C，则 v 的子圆将对应于 C 中包含的 S 中的圆，中间没有中间圆。当且仅当对应的顶点$v_1$是$v_2$的后代时，圆$C_1$才会包含在圆$C_2$中。

对于任何一对圆的集合$S_1$和$S_2$使用相应的森林$F_1$和$F_2$，当且仅当存在$F_1$的嵌入时，$S_1$才会同胚到$S_2$到$F_2$.

因此，我们可以将 Circle（k） 的定义改写为最大的 n，使得存在一个森林 F，其中 n 个顶点标记为 1 到 n，满足以下条件：$F_i$是F的子林，由标记为i到2i的顶点组成(如果我们删除了任何顶点及其后代之间的顶点，则后一个顶点连接到其第一个未删除的祖先)。那么对于任何$k\le i<j\le n/2$，不存在$F_i$到$F_j$的嵌入。

取值

Friedman指出，Circle(k)一定是有限的，但我们对其具体取值仍了解不多。我们有$Circle(1)=1$以及$Circle(2)\ge 13$.

Circle函数的FGH增长率是${\epsilon }_0$.