3x + 1 semigroup

Short description: Special semigroup of positive rational numbers

In algebra, the 3x + 1 semigroup is a special subsemigroup of the multiplicative semigroup of all positive rational numbers. The elements of a generating set of this semigroup are related to the sequence of numbers involved in the still open Collatz conjecture or the "3x + 1 problem". The 3x + 1 semigroup has been used to prove a weaker form of the Collatz conjecture. In fact, it was in such context the concept of the 3x + 1 semigroup was introduced by H. Farkas in 2005. Various generalizations of the 3x + 1 semigroup have been constructed and their properties have been investigated.

Definition

The 3x + 1 semigroup is the multiplicative semigroup of positive rational numbers generated by the set

$\{2\}\cup \{\frac{2k+1}{3k+2}:k\ge 0\}=\{2,\frac{1}{2},\frac{3}{5},\frac{5}{8},\frac{7}{11},\dots \}.$

The function $T:\mathbb{\mathbb{Z}}\to \mathbb{\mathbb{Z}}$ as defined below is used in the "shortcut" definition of the Collatz conjecture:

$T(n)=\{\begin{array}{ll}\frac{n}{2}& \text{if }n\text{ is even}\\ [4px]\frac{3n+1}{2}& \text{if }n\text{ is odd}\end{array}$

The Collatz conjecture asserts that for each positive integer $n$, there is some iterate of $T$ with itself which maps $n$ to 1, that is, there is some integer $k$ such that $T^{(k)}(n)=1$. For example if $n=7$ then the values of $T^{(k)}(n)$ for $k=1,2,3,...$ are 11, 17, 26, 13, 20, 10, 5, 8, 4, 2, 1 and $T^{(11)}(7)=1$.

The relation between the 3x + 1 semigroup and the Collatz conjecture is that the 3x + 1 semigroup is also generated by the set

$\{\frac{n}{T(n)}:n>0\}.$

The weak Collatz conjecture

The weak Collatz conjecture asserts the following: "The 3x + 1 semigroup contains every positive integer." This was formulated by Farkas and it has been proved to be true as a consequence of the following property of the 3x + 1 semigroup:

The 3x + 1 semigroup S equals the set of all positive rationals a/b in lowest terms having the property that b ≠ 0 (mod 3). In particular, S contains every positive integer.

The wild semigroup

The semigroup generated by the set

$\left\{\frac{1}{2}\right\}\cup \{\frac{3k+2}{2k+1}:k\ge 0\},$

which is also generated by the set

$\{\frac{T(n)}{n}:n>0\},$

is called the wild semigroup. The integers in the wild semigroup consists of all integers m such that m ≠ 0 (mod 3).

See also

• Wild number