This chapter is from the book
This chapter is from the book
This chapter is from the book
2.2 Orbits
To understand the global behavior of a transformation, we examine the structure of its orbits: elements reachable from a starting element by repeated applications of the transformation. y is reachable from x under a transformation f if for some n ≥ 0, y = fn(x). x is cyclic under f if for some n ≥ 1, x = fn(x). x is terminal under f if and only if x is not in the definition space of f. The orbit of x under a transformation f is the set of all elements reachable from x under f.
Lemma 2.2.
An orbit does not contain both a cyclic and a terminal element.
Lemma 2.3.
An orbit contains at most one terminal element.
If y is reachable from x under f, the distance from x to y is the least number of transformation steps from x to y. Obviously, distance is not always defined.
Given a transformation type F, DistanceType(F) is an integer type large enough to encode the maximum number of steps by any transformation f ∊ F from one element of T = Domain(F) to another. If type T occupies k bits, there can be as many as 2k values but only 2k – 1 steps between distinct values. Thus if T is a fixed-size type, an integral type of the same size is a valid distance type for any transformation on T. (Instead of using the distance type, we allow the use of any integer type in power_unary, since the extra generality does not appear to hurt there.) It is often the case that all transformation types over a domain have the same distance type. In this case the type function DistanceType is defined for the domain type and defines the corresponding type function for the transformation types.
The existence of DistanceType leads to the following procedure:
template<typename F>
requires(Transformation(F))
DistanceType(F) distance(Domain(F) x, Domain(F) y, F f)
{
// Precondition: y is reachable from x under f
typedef DistanceType(F) N;
N n(0);
while (x != y) {
x = f(x);
n = n + N(1);
}
return n;
}
Orbits have different shapes. An orbit of x under a transformation is
|
infinite |
if it has no cyclic or terminal elements |
|
terminating |
if it has a terminal element |
|
circular |
if x is cyclic |
|
ρ-shaped |
if x is not cyclic, but its orbit contains a cyclic element |
An orbit of x is finite if it is not infinite. Figure 2.1 illustrates the various cases.
)
Figure 2.1 Orbit Shapes.
The orbit cycle is the set of cyclic elements in the orbit and is empty for infinite and terminating orbits. The orbit handle, the complement of the orbit cycle with respect to the orbit, is empty for a circular orbit. The connection point is the first cyclic element, and is the first element of a circular orbit and the first element after the handle for a ρ-shaped orbit. The orbit size o of an orbit is the number of distinct elements in it. The handle size h of an orbit is the number of elements in the orbit handle. The cycle size c of an orbit is the number of elements in the orbit cycle.
Lemma 2.4.
o = h + c
Lemma 2.5.
The distance from any point in an orbit to a point in a cycle of that orbit is always defined.
Lemma 2.6.
If x and y are distinct points in a cycle of size c,
c = distance(x, y, f) + distance(y, x, f) |
Lemma 2.7.
If x and y are points in a cycle of size c, the distance from x to y satisfies
0 ≤ distance(x, y, f) < c |