From Wikipedia, the free encyclopedia

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 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. [2] Various generalizations of the 3x + 1 semigroup have been constructed and their properties have been investigated. [3]


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

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

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

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

which is also generated by the set

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


  1. ^ a b Applegate, David; Lagarias, Jeffrey C. (2006). "The 3x + 1 semigroup". Journal of Number Theory. 117 (1): 146–159. doi: 10.1016/j.jnt.2005.06.010. MR  2204740.
  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 (2): 97–108. doi: 10.2307/27641862. JSTOR  27641862. Retrieved 18 March 2016.