*2^a*3^b*n+c* -- The
general
form of the arithmetic expressions which denote the set memberships of
the left descent assembliles (l.d.a.s) in the abstract
predecessor tree,
used when the powers of 2 and 3 seem relevant. Otherwise {c[d]} is
used.

3n+1 problem -- Mathematicians prefer the name "3x+1" or "Collatz 3x+1" problem. Proving this unproved conjecture is the subject of these pages.

8n+5 -- The
formula representing the infinite set of integers obtained by taking
*n* as 0, 1, 2, 3, ... ,
or,
equivalently *{5[8]}*, all the integers congruent to 5 modulo
8..

abstract tree -- In this
work, a binary tree whose nodes consist of infinite residue
sets. The root of the abstract tree contains the whole set of left
descent asssembly headers (which serve also as extensions)
({8n+5} or 5[8] integers) as its root and follows their
partitioning as it develops all possible left descents (in the binary
tree) by separating the *s*-descendant subset, the
*b*-descendant subset, and the leaf subset at every level of
its development.

*b*-descendant -- The kind of
descendant in a left descent in the binary predecessor tree *b*igger
than its parent, or the set at a level in the abstract predecessor
tree containing all those descendants bigger than their immediate
parents. These children arise when the parent (set) is
congruent to 1 modulo 3, i.e. in 1[3].

*b*-step -- The steps in an l.d.a. are labeled *b* steps
when they connect a parent to a *b*-descendant, allowing the
letter *b* to be used as an element in the
*e*{*s*|*b*}*t* notation for l.d.a.s.
.

binary tree -- A tree in which a parent may bear only zero, one, or two children, and the left child is distinguished from the right child. In this work, the binary tree is a predecessor tree rooted at one in which a series of left children constitute a "left descent", a node with no left child is called a "leaf node", and right children are called "extensions". Every node in the tree has a right child.

Collatz graph -- A graph designed to depict the pathways through which integers move towards one under the Collatz trajectories.

conjecture -- Any mathematical proposition believed to be true but which has not been rigorously shown to be true. The conjecture studied in these pages is that the Collatz 3n+1 trajectory leads to 1 from any positive integer.

canonical form -- The representation of a
residue set is here done as *{c[d]}*, where usually (canonically)
c<d,
meaning the set of integers congruent to *c* modulo *d*. Sometimes, a
calculation yields *{c[d]}* with *c*>*d*, making it desirable to normalize
the result into the canonical form.

descendant rules -- The rules which specify the calculation of the next level in the predecessor trees from the parental value. Effectively, they provide the inverse of the Collatz process by calculating an odd integer (Collatz) predecessor from an odd integer (Collatz) successor, thus facilitating predecessor tree construction.

disjoint graphs -- Two graphs are disjoint if the union of their nodes is null. One possibility for failure of the Collatz conjecture is that there is a separate, disjoint predecessor tree from that headed by 1.

dn+c -- The general form of
the arithmetic expressions which denote the set memberships in the
abstract predecessor tree, usually used when the powers of 2 and 3
are not particularly relevant and/or before subsetting is completed so
that the subsets are not yet unique to a particular left descent.
Equivalently referred to *{c[d]}*.

e -- The symbol used to denote the extension (header) of a left descent in the string which characterizes each one.

*e(s|b) _{n}/t* notation
-- An
alphabetic string descriptive of a fully anchored left descent. It
starts with

extension -- A synonym for a right descendant in the binary predecessor tree, so named because every element in a right descent produces the odd Collatz successor identical with that produced by the node which heads the right descent. An extension heads every left descent. An alternative term, "proxy", might have better served to connote the way extensions produce the same result as their header element.

extended hexadecimal Collatz trajectories can sometimes contain a greater number of successive divisions by 2 than can be represented by the decimal digits 1 through 9. To provide a single digit representation for these cases, the familiar hexadecimal system of computer science is extended as follows, '123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz', to provide digit values from 1 through 61.

Fibonacci series -- The
recursively defined series in which F(0)=0 and F(1)=1 and
F(n)=F(n-2)+F(n-1) for n>=2. This series (and its multiples
by 2^i, i>=1) is observed in the cardinalities of
occurrences of formulas sharing a common {*a,b*} pair for a given
value of *a* (see entry for __formula__).

finite sum -- A summation performed over a finite number of terms. In this work, finite sums were calculated to confirm the convergence of infinite sums and measure the coverage of the integers by the predecessor tree.

formula -- Used in these pages to denote an
algebraic expression of the form *dn*+*c* or
2^*a**3^*b***n*+*c* or {c[d]} which characterizes a
residue set, a unique subset in the abstract predecessor tree.

general tree -- A tree in which a node may bear any number (zero or more) of children. In this work, the general form of the predecessor tree shows the smallest child and all its extensions as the infinite set of children of each parental node.

generation tree -- A tree depicting the effects of some directed transition whose results are shown as parents and whose sources are shown as children. In this context, the generation trees are usually called predecessor trees (which see, below) (all three forms).

graph -- A graph is a set of points (

infinite sum -- A summation performed over an infinite number of terms. In this work, the infinite summations of the densities of integers in various disjoint subsets converge to finite values which measure various aspects of the coverage of the integers by the predecessor tree.

instance, instantiation --
A reference to a particular value of a left descent assembly in
which a particular value of *n* is used in n*d+c across the
formulas of all the elements of a left descent. (The two words are
used almost interchangeably here.) For example, 5[24], 29[24],
63[24], ... are the 0th, 1st, and 2nd instantiations of {5[24]}. The term
is borrowed from object oriented programming.

l.d.a. -- Abbreviation for left descent assembly; see definition herein below.

leaf node -- A node in a tree which bears no children. In this work, predecessor tree nodes are leaf nodes when they contain integers which are multiples of 3 (i.e., in the abstract tree, a set of integers congruent to 0 modulo 3).

left descent -- The sequence of nodes, every one a left child in the binary tree view of the predecessor tree, appearing below a header extension node {5[8]}, created by use of either 1 or 2 as the value of p(k) in the descendant rules, and terminating in a leaf node {0[3]}. See also some context. See also the definition of "sequence vector" later in this glossary.

left descent assembly -- The recurring structural unit, consisting of a left descent including both its header extension and its terminating leaf node, whose infinite instantiations provide a certain fraction of the odd integers present in the predecessor tree. (This is often abbreviated as l.d.a.) L.d.a.s are a restricted subset of sequence vectors. (Occasionally, "assemblage" slips out in place of "assembly").

Maple -- The Symbolic Algebra software without which this work could not conceivably have ever left the ground.

mod -- The arithmetic operator whose result is the remainder of an integer division. For example, 5 modulo 3 is 2, and 55 modulo 24 is 7. Equivalently, 5[3]=2 and 55[24]=7.

node -- In this work, a node is a vertex in a tree. The general and the binary predecessor tree nodes contain odd integer values, but the abstract tree nodes contain sets of odd integers. (More generally, a node is a vertex in any graph and may contain any sort of value.)

o -- A variable denoting the integer
whose placement in the abstract predecessor tree is the *o*bject of
any particular execution of the placement algorithm.

Pascal triangle -- A presentation of the
successive sets of the binomial coefficients in the form of a
triangle. Since the abstract predecessor tree traces out the
various combination of *s* and *b* steps, the number of
ways to reach paths with *c* *s*'s and *d* *b*'s in
it is given by C(*c*,*d*), equal to the binomial
coefficient. This pictorial representation enables a quick
visualization of the reason the Fibonacci series describes the number of
ways to reach any particular power-of-2 depth in left descents.

phantom node -- When the predecessor tree is pictured as a general tree, a path up through the tree from an integer to the root node is faithfully representative of the Collatz path. However, when the binary tree representation is used, such an upward path visits all the extensions encountered during the transition from l.d.a. to l.d.a. even though they do not appear in the The extra entries are useful to underscore the construction of the trees from l.d.a.s and extensions, but are "phantoms" in that they do not appear in the calculated Collatz trajectory.

predecessor tree -- A predecessor tree gives the result of an operation as a parent and the source(s) as the child(ren). In our case, the Collatz successor appears as a parent, and the predecessor(s) appear(s) as child(ren) in the tree. Any Collatz trajectory can be followed as a path from deep in the general predecessor tree upwards to its final destination at 1.

recursion -- A repetitive process in which calculation of each new value in a series uses values appearing earlier in the series. Both calculation of successive extensions and successive elements of the Collatz trajectory are recursive processes. The Fibonacci series is a classical example of recursion.

residue set -- An infinite set of integers with a common remainder when divided by another integer, for example: the integers {5 mod 8}, also sometimes represented here as {8n+5} or {5[8]}. This particular set is the header of all the l.d.a.s in the abstract predecessor tree.

right descent -- The
infinite sequence of nodes, appearing as right children below
every node in the binary tree, and each having a value determined
recursively from its parent, *n*, as
4**n*+1. Also referred to as *extensions*.

root -- The distinguished node in a graphical
structure known as a tree which is parental to the entire graphical
structure. In the Collatz 3n+1 problem, the value in the root
node in the integer version is 1,. and in the abstract predecessor tree
the value in the root node is *{c[d]}*.

*s*-descendant -- The kind of
descendant in a left descent in the binary predecessor tree
*s*maller than its parent, or the set at some level in the
abstract predecessor tree containing all those descendants smaller than
their immediate parents. These children arise when the parent
(set) is congruent to 2 modulo 3.

sequence vector -- A more general notation for representing a trajectory in a Collatz iteration inclusive of paths which include arbitrary numbers of steps which involve arbitrary numbers of division by 2 at each step. I quote liberally from email from Mensanator (May 10, 2006) whose definition is more complete and precise than any I would have produced.

(3n+1) (n/2) (3n+1) (n/2) (n/2)". Thank you, Mensanator.

Crudely put, a sequence vector is an l.d.a. gone wild; it is not not constrained to start at an integer in {5[8]}, nor to end in an integer in {0[3]}, nor limited to only one or two divisions by 2. (These 3 criteria do apply to l.d.a.s.)

*s*-step -- The steps in an l.d.a. are labeled *s* steps
when they connect a parent to an *s*-descendant, allowing the
letter *s* to be used as an element in the *e*{*s*|*b*}*t* notation for
l.d.a.s.

sieve -- A process by which a set (here, the odd integers) may be repeatedly scanned to mark those satisfying a certain property (here, inclusion in one of the infinite instantiations of a left descent assembly) and identify new scanning elements (here a new left descent assembly) for use in repetition of the process. Compare the Sieve of Eratosthenes, which scans for composites to identify primes and eventually assigns all integers as either prime or composite. If the Collatz conjecture is correct, all odd integers will be sieved.

state transition diagram -- A directed graph which shows states of a system as its nodes and the transitions which may occur between them as its edges. The state of a system is given by the values of some characteristic variable(s) of the system. State changes are indicated by arrows indicating allowed transitions, with an annotation on each arrow indicating the circumstance under which the particular transition occurs. The state transition diagram offers a compact and understandable overview of potential system dynamics.

t -- The symbol used in the string
characterizing each kind of left descent to denote that the left descent
has been terminated in a leaf node. Note that the *t* does NOT
correspond to an element in the descent (unlike the *e*, *s*,
and *b* characters which DO correspond to elements in the descent).

T -- The conventional symbol used to
indicate Collatz *T*rajectory elements. T_{p} and
T_{s} represent the predecesor element and the successor
element, respectively.

trajectory -- The sequence of integers visited by successive Collatz steps from some starting integer (presumably) on the way to 1. We limit our discussion to the odd integers.

My Collatz Home Page