3x + 1 semigroup

In algebra, the 3x + 1 semigroup is a special subsemigroup of the multiplicative semigroup of all positive rational numbers.^[1] The elements of a generating set of this semigroup are related to the sequence of numbers involved in the yet to be proved conjecture known as the 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.^[2] Various generalizations of the 3x + 1 semigroup have been constructed and their properties have been investigated.^[3]

Definition

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

$\{2\}\cup \left\{\frac{2k+1}{3k+2} : k\geq 0\right\}=\left\{ 2, \frac{1}{2}, \frac{3}{5}, \frac{5}{8}, \frac{7}{11},\ldots \right\}.$

The function T : Z → Z, where Z is the set of all integers, as defined below is used in the Collatz conjecture:

$T(n)=\begin{cases} \frac{n}{2} & \text{if } n \text{ is even}\\ 3n+1 & \text{if } n \text{ is odd}\end{cases}$

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 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1 and T⁽¹⁶⁾(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 $\left\{ \dfrac{n}{T(n)} : n>0 \right\}$.

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.^[1] "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 \left\{\frac{3k+2}{2k+1}:k\geq 0\right\}$, which is also generated by the set $\left\{\frac{T(n)}{n}: n>0\right\}$, is called the wild semigroup. The integers in the wild semigroup consists of all integers m such that m ≠ 0 (mod 3).^[4]

See also

• Wild number

References

1. D. Applegate and J. C. Lagarias (2006). "The 3 x +1 semigroup". Journal of number Theory 117 (1): 146 –– 159. Retrieved 17 March 2016.
2. H. Farkas (2005). "Variants of the 3 N + 1 problem and multiplicative semigroups", Geometry, Spectral Theory, Groups and Dynamics: Proceedings in Memor y of Robert Brooks. Springer.
3. Ana Caraiani. "Multiplicative Semigroups Related to the 3x+1 Problem" (PDF). Princeton University. Retrieved 17 March 2016.
4. J.C. Lagarias (2006). "Wild and Wooley numbers" (PDF). American Mathematical Monthly 113. Retrieved 18 March 2016.