*Not to be confused with the circle in Steinhaus-Moser Notation.*

**Friedman's circle theorem** is a theorem due to Harvey Friedman that leads to a fast-growing function \(\text{Circle}(n)\) that eventually dominates all recursive functions provably total in Peano arithmetic.^{[1]}

## Description

Let \(C_1, C_2, C_3, \ldots, C_n\) be a finite sequence of non-intersecting circles in the plane, and let \(C_{[a, b]}\) denote \(C_a \cup C_{a+1} \cup \ldots \cup C_{b-1} \cup C_{b}\). Call \(C_1, C_2, C_3, \ldots, C_n\) a *\(k\)-good sequence* if there exists \(k \le i < j \le \lfloor n/2 \rfloor\) such that there is a homeomorphism of the plane that maps \(C_{[i,2i]}\) into \(C_{[j,2j]}\). The theorem states that, given a positive integer \(k\), there exists a number \(n\) such that all sequences \(C_1, C_2, \ldots, C_n\) are \(k\)-good.

A homeomorphism is defined as a bijection \(f\) such that both \(f\) and \(f^{-1}\) are continuous (having no jumps or gaps).

Let \(\text{Circle}(k)\) be the largest \(n\) such that there exists a sequence of length \(n\) that is not \(k\)-good. It can be shown that \(\text{Circle}(1) = 5\) and \(\text{Circle}(2) \geq 13\). In general, \(\text{Circle}(k)\) grows at the rate of \(f_{\varepsilon_0}(k)\) in the fast-growing hierarchy.

## Forest interpretation

For any collection *S* of circles in the plane, we can naturally interpret *S* as a forest, with each circle corresponding to a different vertex in the forest. Root vertices will correspond to circles that are not contained in any other circles. If vertex *v* corresponds to a circle *C*, then the children of *v* will correspond to the circles in *S* that are contained in *C* with no intermediate circles in between. A circle \(C_1\) will be contained in a circle \(C_2\) if and only if the corresponding vertex \(v_1\) is a descendent of \(v_2\).

For any pair of collections of circles \(S_1\) and \(S_2\) with corresponding forests \(F_1\) and \(F_2\), there will be a homeomorphism of \(S_1\) into \(S_2\) if and only if there is an embedding of \(F_1\) into \(F_2\) (in other words, an isomorphism of \(F_1\) into a subforest of \(F_2\)).

Thus, we can rephrase the definition of Circle(*k*) to be the largest *n* such that there exists a forest *F* with *n* vertices labelled 1 through *n* satisfying the following: Let \(F_i\) be the subforest of \(F\) consisting of vertices labelled *i* through *2i* (if we deleted a vertex between any vertex and its descendant latter vertex connects to its first undeleted ancestor). Then for any \(k \le i < j \le \lfloor n/2 \rfloor\), there does not exist an embedding of \(F_i\) into \(F_j\).

## Sources

- ↑ H. Friedman, "Enormous integers in real life"

## See also

**By Harvey Friedman:** Mythical tree problem · Friedman's vector reduction problem · Friedman's finite ordered tree problem · block subsequence theorem n(4) · **Friedman's circle theorem** · TREE sequence TREE(3) · subcubic graph number SCG(13) · transcendental integer · finite promise games · Friedman's finite trees · Greedy clique sequence**Miscellaneous:** Factorial · Folkman's number · Exploding Tree Function · Graham's number · fusible number