The Foundations


Let g:S -> S, and define a relation R on S such that x R y iff there are m, n in N such that gm(x) = gn(y), exponentiation indicating repeated composition. Then R is an equivalence relation and partitions S into sets I call classes. The set of all classes is called K(g). If K is in K(g), then g(K) is a subset of K. From this it follows that

Theorem: If K is in K(g), then K = U Ki for some Ki in K(g2).

Proof: Let gK be the restriction of g to the class K. The function (gK)2 partitions the domain K into disjoint classes {Ki} whose union is K. Because K is a class of g, there is no element x in S - K such that g(x) is in K. Thus each Ki is a class of g2 and U Ki = K, as desired. QED

Let g:S -> S and let C be a subset of g such that when x is in C, {gn(x): n in N} = C. Such a subset C is called a cycle of g.

Lemma: If g:S -> S and C1, C2 are distinct cycles of g, then they are disjoint.

Proof: Suppose they intersected at a point x. Then {gn(x): n in N} = C1 = C2, so the cycles are identical. Quite Easily Done

Theorem: Let g:S -> S and let K be a class of g. Then K contains at most one cycle.

Proof: Suppose K contained two cycles C1 and C2, and let x1, x2 be in C1, C2, respectively. Then for any m, n in N, gm(x1) is in C1 and gn(x2) is in C2, and since C1 and C2 are disjoint, K is not a class. QED

Classes with cycles are called "class with cycle". An n-class is a class containing a cycle of n elements. Classes without cycles are called 0-classes. 0-classes are always infinite in elements. Every class is an n-class for some non-negative integer n. An n-class with n even is called an even-class, otherwise it is called an odd-class.

Let g:S -> S, K in K(g), and C be a cycle contained in K. Then for any x in K, fn(x) is in C for some n. We use this fact in the following theorem.

Theorem: Let g:S -> S and let K be an n-class of g. Then (gK)2 has one or two classes accordingly when n is odd or even, respectively. If n is odd, the class in (gK)2 has a cycle of order n. If n is even, the two classes both have cycles with respect to (gK)2, each of order n/2.

Proof: Let n be odd, and let C = {x1, ..., xn} be the cycle of K. First, every class of (gK)2 has a cycle because of the fact stated above. We find that C is indeed a cycle of (gK)2 as well as gK, and it is clear that there cannot be others. Thus there can only be one class in (gK)2 to contain the cycle C, and being over the same elements, such a class is also an n-class. Let n be even and > 0. Then the set C in (gK)2 has two cycles whose union is C: {x1, x3, ..., xn - 1} and {x2, x4, ..., xn}. By a similar argument to the above, (gK)2 has two classes containing these cycles, each of which has order n/2. Finally, let n = 0. Clearly, (gK)2 cannot have any cycles. Define a relation R on K such that x R y iff there are m, n in N such that gm(x) = gn(y) and also m = n mod 2. Then R is an equivalence relation, as can be verified routinely. Moreover, the equivalence classes are classes of (gK)2 by the definition of the relation. Let K1 be one of these classes, so K - K1 = K2 is a union of classes of (gK)2. Let x, y be in K2, and let gm(x) = gn(y). Clearly gm + 1 is in K1 so m + 1 = n + 1 mod 2, and m = n mod 2. Thus, there are two classes in (gK)2. Quite Elusively Done

Corollary: Let g:S -> S. When n is even, the number of n-classes in g2 is even.

The direction we are taking can be seen; we are letting g:S -> S be completely arbitrary, and we are studying the necessary properties of g2. With our results we can immediately discard functions like g(k) = k + 1 over the integers from having a representation as f2. The primary aim of class theory is to establish necessary and sufficient conditions for a function f to exist. If g is a permutation, the result is easy:

Corollary: Let p:S -> S be a permutation. Then p = f2 for some f:S ->S iff there are an even number of infinite cycles, and for each even n, there are an even number of cycles of order n.

Sometimes we encounter odd-classes which obviously can't be represented as squares of any other odd-classes with cycle of the same order; for instance, the function f:N -> N by f(1) = 2, f(2) = 3, f(3) = 1, f(n) = n - 1 for all n > 3 is such a class. I shall advance the theory a bit further so to throw out this and similar classes. The concept of class isomorphism is a simple and profitable idea which simplifies the work of actually solving the functional equation.

Definitions:

Let g1:S1 -> S1, g2:S2 -> S2, let K1 be an n-class of g1, and K2 and n-class of g2.

Classes K1 and K2 are isomorphic iff there exists a bijective function f:K1 -> K2 such that if g1(x1) = x2 then g2(f(x1)) = f(x2). Such a function f:K1 -> K1 is called an automorphism of the class K1, and they're probably special, but I don't care about them right now.

Let g:S -> S, let K be an n-class of g with n > 0, and let c be a point in the cycle C of K.

K is called a rootable class iff there is another class K' such that (K')2 = K. An even-class is never rootable.
A point x of K is said to be under c iff gm(x) = c for some positive m and there is no k < m such that gk(x) is in C.
The set of all points under c is called the arm of c.
Given a point x, the least m such that gm(x) is in C is called the rank of x. The set of all points under a cycle element c with rank m is called the mth-rank of c.
The greatest m such that the mth-rank of c is nonempty is called the length of c, or the length of the arm of c, and it is denoted lc. If there is no largest m we write lc = infinity. In the proceeding formulas we always assume infinity is even, infinity + k = infinity, infinity * r = infinity for positive r.

I conclude this section with a useful and basic theorem on the lengths of a rootable odd-class. Let g:S -> S, K be an n-class of g for odd n, and let C = {x1, x2, ..., xn}, where g(xk) = xk + 1 and g(xn) = x1. Let lKxk be the length of xk in K and let lK2xk be the length of xk in K2.

Theorem: lK2xk = max{[lKxk/2], [(lKxk - 1 + 1)/2]}.

Proof: It is routine to show that the only points which are under xk in K2 must be points under xk and xk - 1 in K. The points under xk which are also under xk in K2 are those of even rank. Thus the greatest rank under xk in K which is also under xk in K2 is [lKxk/2]. Similarly, taking into consideration that x under xk - 1 must be moved an additional step by f(xk - 1) = xk, the greatest rank under xk - 1 that is under xk in K2 is easily seen to be [(lKxk - 1 + 1)/2]. The greatest rank below xk in K2 is the greatest of these two ranks, that is, it is rank max{[lKxk/2], [(lKxk - 1 + 1)/2]}. QED


This concludes the foundation of class theory. I am working with a friend of mine to establish exactly when, given 0-classes K1, K2, there exists a class K such that K2 is isomorphic to the disjoint union of K1 and K2. I have introduced the idea of the trunk of a 0-class which I believe should play a prominent role in this problem. An element x of K is a trunk-member iff for any n in N, there exists some y in K such that fn(y) = x. The trunk of K is then the set of all trunk-members of K. (It may be that the trunk is the empty set. For example, f(n) = n + 1 over the naturals.) Examination of the behavior of trunks when a 0-class is squared will be fruitful in solving this. If we can 1) discover when two 0-classes can be paired to form the square of another 0-class, 2) discover when an odd-class has a square root of the same cycle order, and 3) discover when two classes of the same nonzero order can be paired together to form the square of a class of double the cycle order, then the goal of class theory to decide when a given function g:S -> S has a square root f will not be out of sight.

Previous Next
Back to Table of Contents


Mail me
Back to my Homepage