Functions which cycle through composition to the identity function.

Abstract.--This paper investigates iterative compositions of functions with themselves. Of particular interest will be functions that cycle members of their domain back to themselves through composition in either a finite or infinite number of compositions.

**********

TEXAS J. SCI. 55(4):297-306

Letting K denote a number interval of positive length, [f.sup.[1]] = f and [f.sup.[n]] = f ([f.sup.[n-1]]) for integers n > 1, one considers the following question which originated in a pre-calculus class:

For a given positive integer n (but no smaller integer), does there exist a function f:K[right arrow]K which satisfies the property that [f.sup.[n]] = I.

Clearly the identity function I satisfies the condition for n = 1 on any interval K and, for n = 2, the reciprocal function f(x) = 1/x defined on the interval K = (1/2,2) can be seen to satisfy the condition [f.sup.[2]] = f(f)) = I. For n = 3, the function f: [0,3)[right arrow] [0,3) defined by f(x) = x + 1 (mod 3) may be seen to satisfy the condition that [f.sup.[3]](x) = f(f(f(x))) = x for all x in the interval K = [0,3). By replacing the number 3 with the positive integer n, the last example may be generalized to give a function that answers the question posed above. Thus, for any positive integer n, a function f:K[right arrow]K exists which cycles through composition to the identity function in n but no fewer cycles. It is noted that the functions presented in the first two examples were continuous while the example for n = 3 (and the analogs for n > 3) had a point of discontinuity. The question then arises as to the existence of a continuous function f:K[right arrow]K which satisfies the property [f.sup.[n]] = I for n [greater than or equal to] 3. This question is investigated in the next section. In the third section infinite compositions of functions with themselves will be considered.

RESULTS FOR A FINITE NUMBER OF CYCLES

In this section the question of existence of continuous functions f:K[right arrow]K that satisfy the property [f.sup.[n]] = I will be considered. Examples of continuous functions that satisfied this property for n = 1 and n = 2 appear above in the Introduction. The question for integers n [greater than or equal to] 3 will be considered here.

Theorem 1:

If the function f:K[right arrow]K is continuous and satisfies the property that [f.sup.[n]] = I for some positive integer n, then f is one-to-one, onto and strictly monotonic.

Proof:

As the identity function satisfies these three properties, it will be assumed that n > 1. The proof that f is one-to-one follows from the observation that if f(x) = f(y), then

x = [f.sup.[n]] (x) = [f.sup.[n-1]] (f(x)) = [f.sup.[n-1]](f(y)) = [f.sup.[n]] (y) = Y.

Also, for each number x, we have that f([f.sup.[n-1]] (x)) = [f.sup.[n]] (x) = x which shows that f is onto. Finally, that f is strictly monotonic follows from the continuity of f and the Intermediate Value Theorem (Bartle & Sherbert 1992:156). For if f is not strictly monotonic on K, there will be points c < z < d in K such that either f(z) > max{f(c),f(d)} or f(z) < min{f(c),f(d)}. In either case the continuity of f would allow one to use the Intermediate Value Theorem to show that there numbers [x.sub.1] and [x.sub.2] such that c < [x.sub.1] < z < [x.sub.2] < d and f([x.sub.1]) = f([x.sub.2]) which provides the needed contradiction to the fact that f is one-to-one.

It is seen from Theorem 1 that a continuous function f:K[right arrow]K satisfying the property [f.sup.[n]] = I for some positive integer n must be strictly increasing or strictly decreasing. Theorem 2 presented below will consider the strictly increasing case while the strictly decreasing case will be handled with Theorem 3.

Theorem 2:

Suppose f:K[right arrow]K is a strictly increasing continuous function such that [f.sup.[n]] = I for some positive integer n. Then f = I.

Proof:

Suppose that f [not equal to] I. Then, for some number p [member of] K, p < f(p) or p > f(p). Since f is strictly increasing, the first possibility implies that

p < f(p) < [f.sup.[2]] (p) < ... < [f.sup.[n] (p) = p.

This produces the contradiction that p < p. A similar contradiction follows if p > f(p) which completes the proof.

Attention is now turned to the case where f is strictly decreasing and it is shown that n must equal two.

Theorem 3:

Suppose f:K[right arrow]K is a strictly decreasing continuous function and [f.sup.[n]] = I. Then n = 2 and [f.sup.[2]] = f(f) = I.

Proof:

Since f:K[right arrow]K is strictly decreasing, [f.sup.[n]] will be strictly decreasing for odd n and strictly increasing for even n. Since [f.sup.[n]] = I is strictly increasing, n must be even. This means that n = 2m for some positive integer m. Now

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Since [f.sup.[2]] is strictly increasing on K, Theorem 2 gives that m = 1 which implies that n = 2 and [f.sup.[2]] = f(f) = I.

Summarizing this section, one sees that if f:K[right arrow]K is a function satisfying the condition that [f.sup.[n]] = I for some positive integer n [greater than or equal to] 3 (but no smaller value of n), then f is discontinuous somewhere in K. Moreover, if f:K[right arrow]K is a continuous function satisfying the condition that [f.sup.[n]] = I for some positive integer n (but no smaller value of n), then n = 1 or n = 2. If n = 1, then f = I; and, if n = 2, then f will be a strictly decreasing function which is its own inverse (f(f) = I).

There is an algebraic application for these results. Letting C(K) denote the set of continuous functions from the interval K onto K, it may be seen that C(K) is a semi group with an identity under the operation of composition. The above results show that no element of C(K) can have order greater than two. The authors wish to thank the reviewer for suggestions with this observation.

In the next section attention will be turned to infinite composition iterations of functions with themselves.

RESULTS FOR AN INFINITE NUMBER OF CYCLES

In the last section it was shown that functions f:K[right arrow]K existed for any positive integer n which satisfied the condition that [f.sup.[n]] = I (the identity function on K) while failing to do so for k < n. Moreover, for n > 2, these functions failed to be continuous on K. In this section we extend this study by considering infinite composition iterations of a function f:K[right arrow]K with itself. As an aid to this study one will let [f.sup.[[infinity]]](x) = y denote that the composition sequence {[f.sup.[n](x)} converges to y. For a function f:K[right arrow]K, let [f.sup.[[infinity]]] = I denote that [f.sup.[[infinity]]](x) = x for all x in K (i.e., [f.sup.[[infinity]]] is the identity function on K). As [f.sup.[[infinity]]](x) = x whenever f(x) = x and [f.sup.[[infinity]]] = I whenever f is the identity function I, the authors chose to investigate the existence of non-identity functions f:K[right arrow]K which satisfy the condition that [f.sup.[[infinity]]] = I. The authors show below that no such function exists. The authors also investigate, in what follows, the existence and nature of subsets of K where f(x) [not equal to] x but [f.sup.[[infinity]]](x) = x. To this end, use [K.sub.[infinity]] to denote such subsets. Thus, for a function f:K[right arrow]K, [K.sub.[infinity]] will denote the subset of K which contains x if and only if f(x) [not equal to] x and the composition sequence {[f.sup.[n]](x)} converges to x (i.e., [f.sup.[[infinity]]](x) = x). The next theorem is stated without proof but may be found in most introductory real analysis texts (e.g., see Bartle & Sherbet 1992:95). It will be used to establish results on the existence and nature of [K.sub.[infinity]].

Theorem 4:

If a sequence A = {[a.sub.n]} converges to the number x, then any subsequence of A will converge to x.

The next theorem follows from Theorem 4 and establishes some structure for [K.sub.[infinity]].

Theorem 5:

Suppose f:K[right arrow]K is a function. Then

(1) if x [member of] [K.sub.[infinity]], then any subsequence of {[f.sup.[n]](x)} converges to x;

(2) if x [member of] [K.sub.[infinity]], then [f.sup.[n]](x) [not equal to] x for every positive integer n;

(3) if x [member of] [K.sub.[infinity]], then no subsequence of {[f.sup.[n]](x)} can converge to [f.sup.[p]](x) for any positive integer p;

(4) if x [member of] [K.sub.[infinity]], then [??] for any positive integer p

(5) if x [member of] [K.sub.[infinity]], then no two members of {[f.sup.[n]](x)} can agree;

(6) if x [not equal to] y and both belong to [K.sub.[infinity]], then the two composition sequences {[f.sup.[n]](x)} and {[f.sup.[n]](y)} are disjoint;

(7) f is discontinuous at any x [member of] [K.sub.[infinity]];

(8) if f [not equal to] I, then [f.sup.[infinity]] [not equal to] I; and

(9) [K.sub.[infinity]] can't contain the irrationals of K.

Proof:

Part 1 is a direct consequence of Theorem 4. Using Theorem 4, Part 3 follows directly from Part 2. Except for Part 9 an indirect argument may be used to establish the other parts of this theorem. In each case, assuming the negation quickly leads to the existence of a subsequence of {[f.sup.[n]](x)} which converges to an element other than x, a contradiction to Part 1. For example, if Part 2 is false, one would then have that [f.sup.[n]](x) = x for some positive integer n. Since x [member of] [K.sub.[infinity]], then f(x) [not equal to] x and n > 1. Furthermore, [f.sup.[kn+1]](x) = f(x) for every positive integer k which would imply that {[f.sup.[n](x)} contains a subsequence which converges to something other than x, a contradiction to Part 1. For Part 9, it is first observed that if [K.sub.[infinity]] contains the irrationals of K then K - [K.sub.[infinity]] can contain only rationals. This means that K - [K.sub.[infinity]] can be at most countably infinite. However, the previous parts of this theorem establish that for each x [member of] [K.sub.[infinity]], the composition sequence {[f.sup.[n](x)]} is an infinite subset of K - [K.sub.[infinity]], and, moreover, if x and y are distinct elements of [K.sub.[infinity]], then the corresponding composition sequences {[f.sup.[n]](x)} and {[f.sup.[n]](y)} are disjoint. This forces the set K - [K.sub.[infinity]] to be uncountable, a contradiction which establishes Part 9.

Although the work presented above may lead one to predict that the set [K.sub.[infinity]] will be empty or quite small, the examples given below show that is not the case. The examples that follow show that [K.sub.[infinity]] may be dense in K, uncountable, or uncountably dense in K.

Example: A function f:K[right arrow]K where [K.sub.[infinity]] is dense in K.

Let K = R, the set of real numbers; let A be the set of rational numbers; and let B be the set of irrationals such that x [member of] B if and only if x = p + [pi]/k for some rational p and some positive integer k. It is noted that if p + [pi]/k = q + [pi]/m for rational numbers p and q and positive integers k and m, then p = q and k = m. This means that each number x in set B is uniquely represented. Also, since A contains only rational numbers and B is a set of irrationals, A [intersection] B = [empty set]. Let set C = R - (A[union]B). That is, x [member of] C if and only if x is irrational and x [not equal to] p + [pi]/k for any rational p and positive integer k. By definition, A, B and C are three mutually disjoint sets whose union is K = R. Let f:K[right arrow]K be the function defined by:

(1) f x [member of] A (x is rational), f(x) = x + [pi];

(2) if x = p + [pi]/k [member of] B, f(x) = p + [pi]/(k+1); and

(3) if x [member of] C, f(x) = x.

For rational x, f(x) = x + [pi] [not equal to] x and the composition sequence {[f.sup.[n]](x)} = {x + [pi]/n} converges to x. By definition, this means that [K.sub.[infinity]] contains the rational numbers. However, if x is irrational then x = p + [pi]/k [member of] B or x [member of] C. If x = p + [pi]/k [member of] B, then {[f.sup.[n]](x)} = {p + [pi]/(k+n)} which converges to p which is different from x. This means that [K.sub.[infinity] does not contain any members of B. Also if x [member of] C, then x does not belong to [K.sub.[infinity]] by definition since f(x) = x. Thus, one can conclude that [K.sub.[infinity]] does not contain any irrationals. From this one sees that [K.sub.[infinity]] is exactly the set of rational numbers and is dense in K.

The next example shows that the set [K.sub.[infinity]] may be uncountable.

Example: A function f:K[right arrow]K where [K.sub.[infinity]] is uncountable.

Let K denote the interval [0,1) and let each number in K be represented in an infinite ternary decimal form as ([a.sub.1][a.sub.2][a.sub.3] ... [a.sub.n] ... )[.sub.3] where each digit [a.sub.n] is 0, 1, or 2. To avoid ambiguity we will use (whenever there is a choice) the terminal 10 or 20 representation of a number instead of the representation that ends in 2. Thus, we would use .10 for 1/3 instead of .02 and we would use .20 for 2/3 instead of .12. With this convention, we let set A denote the set of numbers in K whose infinite ternary representation contains no ones. Set A is the classical Cantor set less the number one and the left end points of the open intervals removed from [0,1] to form the Cantor set. As seen in the literature (Bartle & Sherbert 1992:352), the Cantor set is uncountable. Removing the number one and these left end points leaves an uncountable set since only a countable number of open intervals are removed from [0,1] to form the Cantor set. Let B denote the subset of K containing elements whose infinite ternary decimal representation has exactly one 1. Let C = K - (A[union]B). Note that A, B and C are three mutually disjoint sets.

The function is now defined as f: K[right arrow]K. For x = ([a.sub.1][a.sub.2][a.sub.3] ... [a.sub.n] ... )[.sub.3] in A, let f(x) = (1[a.sub.1][a.sub.2][a.sub.3] ... [a.sub.n] ... )[.sub.3]. That is, if x [member of] A, f(x) is the number found by taking the ternary decimal representation of x and inserting a 1 as the first digit and shifting all the original digits one place to the right. It is noted that the function f maps A into B. For x in B, f(x) is found by interchanging the lone "1" in the ternary representation of x with the digit to the immediate right of the 1, leaving the other digits of x unchanged. Thus, if x=([a.sub.1][a.sub.2] ... [a.sub.n- 2]1[a.sub.n][a.sub.n+1] ... )[.sub.3] belongs to the set B, f(x)=([a.sub.1][a.sub.2] ... [a.sub.n- 2][a.sub.n]1[a.sub.n+1] ... )[.sub.3]. It is noted that if x [member of] B, then both x and f(x) have exactly one 1 in their infinite ternary decimal representation. This means that f maps the set B into itself. For x [member of] C, let f(x)=x. Clearly, f maps C onto C.

One first shows that set A is a subset of [K.sub.[infinity]]. Now, if the element x = ([a.sub.1][a.sub.2] ... [a.sub.n] ... )[.sub.3] belongs to the set A and n is a positive integer, then [f.sup.[n]](x) = ([a.sub.1][a.sub.2][a.sub.3] ... 1[a.sub.n] ... )[.sub.3] where the lone "1" in the ternary representation of [f.sup.[n]](x) is located to the immediate left of the nth digit of the ternary representation of x. From this, it is seen that f(x) [not equal to] x and the composition sequence {[f.sup.[n]](x)} converges to x. It then follows, by definition, that [K.sub.[infinity]] contains A. This means that [K.sub.[infinity]] is uncountable since A is uncountable. Moreover, it is the case that [K.sub.[infinity]] is exactly set A. This is seen by showing that [K.sub.[infinity]] contains no elements of set B or of set C. Now, if x = ([a.sub.1][a.sub.2][a.sub.3] ... [a.sub.k-2]1[a.sub.k] ... )[.sub.3] is in B, then [f.sub.[n]](x)=([a.sub.1][a.sub.2][a.sub.3] ... 1[a.sub.k+n] ... )[.sub.3] for n = 1, 2, 3, ... which implies that the composition sequence {[f.sup.[n]](x)} converges to ([a.sub.1][a.sub.2][a.sub.3] ... [a.sub.n] ... )[.sub.3], an element in A which is not equal to x since sets A and B are disjoint. This means that no member of B is contained in [K.sub.[infinity]]. Also, since f(x) = x for x in C, it follows by definition that [K.sub.[infinity]] contains no members of C. We then can conclude that [K.sub.[infinity]] = A.

It is interesting to note that the last example can be altered such that [K.sub.[infinity]] is an uncountable dense subset K.

Example: A function f:K[right arrow]K with [K.sub.[infinity]] uncountable and dense in K.

Let K = [0,1]. Let [W.sub.0,0] be the classical Cantor set. For non-negative integers n and p with 0 [less than or equal to] p [less than or equal to] [3.sup.n]-1, let [W.sub.p,n] be the set obtained by inserting a copy of [W.sub.0,0] into the interval [p/[3.sup.n], (p+1)/[3.sup.n]] through contraction and translation. That is, for n and p as defined above, [W.sub.p,n] = { x/[3.sup.n] + p/[3.sup.n] | x [member of] [W.sub.0,0]}. Like [W.sub.0,0], each set [W.sub.p,n] will be uncountable. Let A be the union of all sets [W.sub.p,n] will be uncountable. Let A be the union of all sets [W.sub.p,n]. Since each interval of the form [p/[3.sup.n], (p+1)/[3.sup.n]] contains an uncountable subset of A (namely, [W.sub.p,n]), A will be uncountable and dense in K = [0,1]. Using the convention of the previous example, the ternary representation of each member of A will contain at most a finite number of ones. Let B be the set of numbers in K whose ternary representation ends with an unending

alternating sequence of ones and non-ones preceded by two or more consecutive digits different from one. Thus, the number x = ([a.sub.1][a.sub.2] ... [a.sub.k][a.sub.k+1]1[a.sub.k+3]1[a.sub.k+5]1 ... )[.sub.3][member of] B if and only if each of the digits [a.sub.k],[a.sub.k+1],[a.sub.k+3],[a.sub.k+5], ... is different from one. Since the ternary representation of each element of B has an infinite number of ones, A [intersection] B = [empty set]. Let C = K - (A [union] B). Then A, B and C are three mutually disjoint sets whose union is K = [0,1]. We now define the function f:K[right arrow]K by:

(1) if x = ([a.sub.1][a.sub.2] ... [a.sub.n][.sub.n+1][a.sub.n+2] ... [).sub.3] [member of] A with n being the smallest positive integer such that [a.sub.k] [not equal to] 1 for k [greater than or equal to] n, let f(x) = ([a.sub.1][a.sub.2] ... [a.sub.n][a.sub.n+1]1[a.sub.n+2]1[a.sub.n+3]1 ... )[.sub.3];

(2) if x = ([a.sub.1][a.sub.2] ... [a.sub.n][a.sub.n+1]1[a.sub.n+3]1[a.sub.n+5]1 ... )[.sub.3 [member of] B with [a.sub.n], [a.sub.n+1], [a.sub.n+3], [a.sub.n+5], ... [not equal to] 1, let

f(x) = ([a.sub.1][a.sub.2] ... [a.sub.n][a.sub.n+1][a.sub.n+3]1[a.sub.n+5]1[a.sub.n+7]1 ... )[.sub.3]; and

(3) if x [member of] C, let

f(x) = x.

Thus, if x [member of] A, f(x) is the element in B found by taking the ternary representation of x and inserting a one between every two digits starting between the second and third digit after the last one in the ternary representation for x. If x has no ones in its ternary representation, then f(x) is found by inserting a one between every two digits with the first insertion being between the second and third digits of the ternary representation of x. For x [member of] B, f(x) is the element in B found by removing the first one that appears in the unending alternating sequence of ones and non-ones. As constructed, f maps A into B, B into B and C onto C. Also, if x=([a.sub.1][a.sub.2] ... [a.sub.k][a.sub.k+1][a.sub.k+2] ... )[.sub.3] [member of] A with k being the smallest positive integer such that [a.sub.p] [not equal to] 1 for 'p [greater than or equal to] k, then [f.sup.[n]](x)=([a.sub.1][a.sub.2] ... [a.sub.k+n]1[a.sub.k+n+1]1[a.sub.k+n+2] ... )[.sub.3] which means that [f.sup.[n]](x) [not equal to] x but the ternary representation of x and [f.sup.[n]](x) agree through the n+k digit. Thus, for x [member of] A, f(x) [not equal to] x and the composition sequence {[f.sup.[n]](x)} converges to x. By definition, it follows that x [member of] [K.sub.[infinity]] whenever x [member of] A. Thus, A is a subset of [K.sub.[infinity]]. This means that [K.sub.[infinity]] will be uncountable and dense in K since A has this property. In addition, it is the case that [K.sub.[infinity]] is exactly set A. This is seen, as in the previous example, by showing that [K.sub.[infinity]] does not contain any elements from either set B or set C. Now, if x=([a.sub.1][a.sub.2] ... [a.sub.k][a.sub.k+1]1[a.sub.k+3]1[a.sub.k+5]1 ... )[.sub.3] is an element of B, the composition sequence {[f.sup.[n]](x)} converges to ([a.sub.1][a.sub.2] ... [a.sub.k][a.sub.k+1][a.sub.k+3][a.sub.k+5][a.sub.k+7] ... )[.sub.3] which is not equal to x while if x belongs to C, f(x) = x. This means that [K.sub.[infinity]] [intersection] (B[union]C) = [empty set]. Since A[union]B[union]C = K =[0,1] and A [subset] definition of K[infinity], it is seen that x [member of] [K.sub.[infinity]] whenever x [member of] B or x [member of] C. This [K.sub.[infinity]], we can conclude that A = [K.sub.[infinity]]. The authors wish to thank Professor G. Passty for his suggestions with this example.

Although not given with this paper, one should be able to expand the second example given above by working with a "fat" Cantor set of positive measure set instead of the classical Cantor set to produce an example where [K.sub.[infinity]] would have measure 1-[epsilon] for 0 < [epsilon] < 1. A similar alteration of the last example should be possible to produce an example where K = [0,1] and [K.sub.[infinity]] is dense in [0,1] and of measure one.

Common to the three examples given above was a set A [subset] K satisfying the property that for each x [member of] A there was a sequence X = {[x.sub.n]} of distinct numbers in K - A which converged to x. Moreover, if x and y were distinct members of A, the corresponding sequences X = {[x.sub.n]} and Y = {[y.sub.n]} were disjoint. In each case a function f:K[right arrow]K was constructed such that [K.sub.[infinity]] = A. This observation is stated as a theorem whose proof is embedded in the above examples.

Theorem 6:

Suppose K is a non-degenerate number interval and A [subset] K such that

(1) for each x [member of] A there is a sequence X = {[x.sub.n]} of distinct elements in K - A which converges to x; and

(2) if x and y are distinct points in A, the corresponding convergent sequences X = {[x.sub.n]} and Y = {[y.sub.n]} in K - A are disjoint.

Then there is a function f:K[right arrow]K such that [K.sub.[infinity]] = A.

JS at: js20@txstate.edu

LITERATURE CITED

Bartle, R. G. & D. R. Sherbert. 1992. Introduction to Real Analysis. John Wiley and Sons, Inc., 403pp.

John Spellmann and Stanley G. Wayment

Department of Mathematics

Texas State University-San Marcos

San Marcos, Texas 78666