FOM: Degenerative Cloning Fix

[Harvey Friedman]

Reply to Holsztynski 5:00AM 5/7/01.

Here is a fix of the computation I gave in my 10:57AM 5/2/01 posting. Let
me know if you spot another error.

It turns out that it is easier to consider only proper single degenerative
cloning, or proper SDC. This means that the SDC operation does not consist
of just removing a circle. Note that thte proper SDC operations are exactly
the SDC operations that do not decrease the number of circles.

We give the exact calculation for the maximum number of successive proper
SDC operations first. We then go back to the original formulation with
arbitrary SDC operations, and modify the calculations accordingly.

An  SDC sequence is a nonempty sequence of finite sets of pairwise disjoint
circles, each successive term obtained by one single degenerative cloning
from the previous term. A proper SDC sequence is an SDC sequence in which
only proper SDC operations are used.

Note that the number of times single degenerative cloning is applied in an
SDC sequence is one less than the length of the SDC sequence.

A set of circles is said to be discrete if and only if no circle lies
inside any other. For each p >= 0, let Xp be the set consisting of a
maximum circle C together with a discrete set of p circles inside C.

Let S be any nonempty finite set of pairwise disjoint circles. We define
the set of preferred proper SDC sequences starting with S, which we call
S*. We will always identify finite sets of pairwise disjoint circles up to
isomorphism. We consider SDC sequences isomorphic if and only if they are
termwise isomorphic.

We begin by first inductively defining Xp* for all p >= 1. Each Xp* will
have only one element (up to isomorphism, of course).

X1* consists of just the sequence <X1,{C1,C2}>, where C1,C2 are circles.

Let p >= 1. The elements of Xp+1* start with Xp+1 followed by two
isomorphic copies of Xp, and then use the element of Xp* on one copy of Xp,
carrying along the second copy of Xp, and when that is finished, then use
the element of Xp* for the remaining copy of Xp.

Note that the length of the element of Xp* is 2^p, and the cardinality of
its last term is 2^p.

We now inductively define S* for any nonempty finite set S of pairwise
disjoint circles. We use induction on the number of elements of S.

Write S = x1 union ... union xk, where each xi has a maximum circle, k >=
1. The order of x1,...,xk is arbitrary, and this is the reason why S*
generally has more than one element.

case 1. k >= 2. The elements of S* are obtained by starting with S, and
then using an element of x1*, carrying along x2 union ... union xk, and
then using an element of (x2 union ... union xk)*.

case 2. k = 1 and S has at least two elements. Let C be the maximum circle
in S. Then S\{C} is nonempty, and so we have defined S\{C}*. The elements
of S* are obtained by starting with S, and then using an element of S\{C}*
staying inside C. This results in some Xp, p >= 1. S* is finished by using
an element of Xp*.

case 3. k = 1 and S has one element. Then S* has the unique element <S>.

THEOREM 1. Let S be a nonempty finite set of disjoint circles. All elements
of S* have the same length and start and end with the same terms (some Xp).

Let alpha(S) be the length of the elements of S* and beta(S) be the number
of elements in the last term of the elements of S*.

THEOREM 2. Let S = x1 union ... union xk, where each xi has a maximum
circle and k >= 1. Then alpha(S) = alpha(x1) + ... + alpha(xk) -k + 1 and
beta(S) = beta(x1) + ... + beta(xk). Let S = {C} union x, where x lies
inside C. Then alpha(S) = alpha(x) + 2^beta(x) - 1, and beta(S) =
2^beta(x). And alpha({C}) = beta({C}} = 1.

Let X*p consist of p concentric circles, p >= 1.

THEOREM 3. For p >= 1, beta(X*p) = 2^[p-1], which is an exponential stack
of p-1 2's. Here 2^[0]  = 1.

THEOREM 4. alpha(X*1) = 1, alpha(X*2) = 2, alpha(X*3) = 5, alpha(X*4) = 20,
alpha(X*5) = 65,555, alpha(X*6) = 2^65,536 + 65,554. beta(X*1) = 1,
beta(X*2) = 2, beta(X*3) = 4, beta(X*4) = 16, beta(X*5) = 65,536, beta(X*6)
= 2^65,536.

THEROEM 5. Let S be a nonempty finite set of pairwise disjoint circles. The
largest length among the proper SDC sequences starting with S is alpha(S).
The largest size among terms in any proper SDC starting with S is beta(S).
The greatest number of successive proper SDC operations starting with S is
alpha(S) - 1.

We now consider the original formulation with arbitrary SDC operations.

THEOREM 6. Let S be a nonempty finite set of pairwise disjoint circles. The
largest size among terms in any SDC sequence starting with S is beta(S).
The largest length among the SDC sequences starting with S is alpha(S) +
beta(S). The greatest number of successive SDC operations that can be
applied starting with S is alpha(S) + 2^beta(S) - 1.

The last line of Theorem 6 applied to X*1,X*2,X*3,X*4,X*5,X*6 is 1 + 1 - 1
= 1, 2 + 2 - 1 = 3, 5 + 4 - 1 = 8, 20 + 16 - 1 = 35, 65,555 + 65,536 - 1 =
131,090, 2^65,536 + 65,554 + 2^65,536 - 1 = 2^65,537 + 65,553.

Obviously, the neatest results are for beta = the largest size of any set
of pairwise disjoint circles than can be obtained by successive single
degenerate cloning from a given nonempty set of pairwise disjoint circles.

Actually, it is a stretch to even allow improper single degenerative
cloning - it is more like the death of a single cell. So I am planning to
make another numbered posting based on only proper SDC. The idea is just
how large can the object get by successive single degenerate cloning?