Misplaced Pages

3x + 1 semigroup

Article snapshot taken from Wikipedia with creative commons attribution-sharealike license. Give it a read and then ask your questions in the chat. We can research this topic together.
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 } ∪ { 2 k + 1 3 k + 2 : k ≥ 0 } = { 2 , 1 2 , 3 5 , 5 8 , 7 11 , … } . {\displaystyle \{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 {\displaystyle T:\mathbb {Z} \to \mathbb {Z} } as defined below is used in the "shortcut" definition of the Collatz conjecture:

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

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

{ n T ( n ) : n > 0 } . {\displaystyle \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:

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

{ 1 2 } ∪ { 3 k + 2 2 k + 1 : k ≥ 0 } , {\displaystyle \left\{{\frac {1}{2}}\right\}\cup \left\{{\frac {3k+2}{2k+1}}:k\geq 0\right\},}

which is also generated by the set

{ T ( n ) n : n > 0 } , {\displaystyle \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).

See also

References

  1. ^ 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.
Categories: