3x + 1 semigroup

In algebra, the semigroup is a special subsemigroup of the multiplicative semigroup of all positive rational numbers.

Uses your system voice; voice and rate in settings.

Snapshot

≈ 3 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

In algebra, the 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 \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 : \mathbb{Z} \to \mathbb{Z} as defined below is used in the "shortcut" definition of the Collatz conjecture: T(n)=\begin{cases} \frac{n}{2} & \text{if } n \text{ is even}\\[4px] \frac{3n+1}{2} & \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 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 \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 proven 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 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 consist of all integers m such that m ≢ 0 (mod 3).

See also

Wild number

Text derived from https://en.wikipedia.org/w/index.php?oldid=1378035326 under CC BY-SA 4.0; modifications have been made.

Sources cited in this revision

2 named source(s) extracted from the cited revision. A source with no author is shown by its publication; nothing is invented.