Talk:Collatz conjecture

Different formulations as rewriting systems

Under the section "Other formulations of the conjecture", include some formulations of the Collatz conjecture as termination problems for rewriting systems. These formulations enable automated approaches to the Collatz conjecture by using methods that are developed for automatically proving termination of rewriting.

For this change, please add the following after the section "As a tag system" under "Other formulations of the conjecture".

As string rewriting systems

For this section, assume that the Collatz function is defined in the slightly modified form:

$f(n)={\begin{cases}{\frac {n}{2}}&{\text{if }}n\equiv 0\\[4px]{\frac {3n+1}{2}}&{\text{if }}n\equiv 1\end{cases}}{\pmod {2}}$

The termination of the following string rewriting system is equivalent to the Collatz conjecture:

${\begin{array}{rcl}{\mathtt {h}}{\mathtt {1}}{\mathtt {1}}&\to &{\mathtt {1}}{\mathtt {h}}\end{array}}\qquad {\begin{array}{rcl}{\mathtt {1}}{\mathtt {1}}{\mathtt {h}}{\mathtt {b}}&\to &{\mathtt {1}}{\mathtt {1}}{\mathtt {s}}{\mathtt {b}}\\{\mathtt {1}}{\mathtt {s}}&\to &{\mathtt {s}}{\mathtt {1}}\\{\mathtt {b}}{\mathtt {s}}&\to &{\mathtt {b}}{\mathtt {h}}\end{array}}\qquad {\begin{array}{rcl}{\mathtt {h}}{\mathtt {1}}{\mathtt {b}}&\to &{\mathtt {t}}{\mathtt {1}}{\mathtt {1}}{\mathtt {b}}\\{\mathtt {1}}{\mathtt {t}}&\to &{\mathtt {t}}{\mathtt {1}}{\mathtt {1}}{\mathtt {1}}\\{\mathtt {b}}{\mathtt {t}}&\to &{\mathtt {b}}{\mathtt {h}}\end{array}}$

The above rewriting system represents each number in unary, and applications of its rules in any order to such a representation simulates the iterated applications of the Collatz function. Roughly speaking, this system simulates the execution of a Turing machine with cells that can be contracted or expanded, where ${\mathtt {h}}$, ${\mathtt {s}}$, ${\mathtt {t}}$ indicate the position of the head along with the state, ${\mathtt {b}}$ stands for the blank characters on the tape, and the symbol ${\mathtt {1}}$ is the unary digit.

An alternative string rewriting system that uses mixed binary–ternary representations of numbers is as follows:

${\begin{array}{rcl}{\mathtt {f}}\triangleright &\to &\triangleright \\{\mathtt {t}}\triangleright &\to &{\mathtt {2}}\triangleright \end{array}}\qquad {\begin{array}{rcl}{\mathtt {f}}{\mathtt {0}}&\to &{\mathtt {0}}{\mathtt {f}}\\{\mathtt {f}}{\mathtt {1}}&\to &{\mathtt {0}}{\mathtt {t}}\\{\mathtt {f}}{\mathtt {2}}&\to &{\mathtt {1}}{\mathtt {f}}\end{array}}\qquad {\begin{array}{rcl}{\mathtt {t}}{\mathtt {0}}&\to &{\mathtt {1}}{\mathtt {t}}\\{\mathtt {t}}{\mathtt {1}}&\to &{\mathtt {2}}{\mathtt {f}}\\{\mathtt {t}}{\mathtt {2}}&\to &{\mathtt {2}}{\mathtt {t}}\end{array}}\qquad {\begin{array}{rcl}\triangleleft {\mathtt {0}}&\to &\triangleleft {\mathtt {t}}\\\triangleleft {\mathtt {1}}&\to &\triangleleft {\mathtt {f}}{\mathtt {f}}\\\triangleleft {\mathtt {2}}&\to &\triangleleft {\mathtt {f}}{\mathtt {t}}\end{array}}$

In the above system, the symbols ${\mathtt {f}}$ and ${\mathtt {t}}$ represent the binary digits (0 and 1), while the symbols ${\mathtt {0}}$, ${\mathtt {1}}$, ${\mathtt {2}}$ represent the ternary digits. The symbols $\triangleleft$ and $\triangleright$ act as delimiters. The rules in the first column apply the Collatz function to a number represented in mixed base as long as the rightmost digit is binary. The remaining rules rewrite the representation (while preserving the value it represents) such that the rightmost digit is binary.

Rephrasing the Collatz conjecture as termination of string rewriting enables, at least in principle, using automated approaches to try to prove the conjecture thanks to the methods developed for automatically proving termination of rewriting.

46.196.80.203 (talk) 13:49, 17 June 2024 (UTC)

 Not done: This seems a bit WP:TOOSOON to me. It's based on a paper that's less than a year old with few citations. PianoDan (talk) 22:32, 18 June 2024 (UTC)

The paper by Zantema is from 2005, so it is ~19 years old. The other paper by Yolcu, Aaronson, and Heule is actually ~3 years old; the conference version of their paper is here: https://doi.org/10.1007/978-3-030-79876-5_27. The latter work was also featured in 2021 in popular science magazines, for instance: https://www.technologyreview.com/2021/07/02/1027475/computers-ready-solve-this-notorious-math-problem. 46.196.80.203 (talk) 09:52, 24 June 2024 (UTC)

 Not done for now: please establish a consensus for this alteration before using the {{Edit semi-protected}} template. I still don't think it's warranted based on the level of citations it has received. Given that there is disagreement from at least one editor that this material should be included in the article, the "Edit request template" procedure no longer applies, since it's only for non-controversial edits. Instead, you can attempt to build a consensus on this page that the material should be included. PianoDan (talk) 16:29, 24 June 2024 (UTC)

I fail to see why the citation count of the source material should be a significant basis for the decision of whether to include some content on the page, but let's assume it should be: Arguably the most similar content currently visible on the page is Liesbeth De Mol's 2-tag system from the 2008 paper. According to Google Scholar, that paper has 36 citations since 2008. Zantema's paper has 64 citations since 2005, and YAH's (conference) paper has 12 citations since 2021. To my understanding, the edit decision should be made based on the significance of the content and whether it is interesting enough. I think those rewriting systems are somewhat more interesting than the tag system since they enable an entirely new approach (at least in principle) towards a proof of the conjecture. 46.196.80.203 (talk) 11:09, 25 June 2024 (UTC)

Binary number of trailing ones equals number of following increases

The chapter Collatz_conjecture#As_an_abstract_machine_that_computes_in_base_two

1. already states that the number of trailing binary zeroes equals the number of next repeated divisions (/2). That is obvious.
2. but it does not yet state that the number of trailing binary ones equals the next number of increments, (*3+1)/2, as the number of trailing ones decreases by one with each increment.

Example:

• 19: 10011 (2 next increments)
• 29 : 11101 (1 next increment)
• 44: 101100 (no immediate increment) The trailing 1100 indicates: after two decrements (22, 11), two increments will follow (17, 26).

The source (BOM - Beauty Of Mathematics) claims at https://www.youtube.com/watch?v=UZH3P8Ey_C8

• not to be a mathematician just working on it as a hobby, so a primary source.
• this does not proof the conjecture, but it might lead to one.

Any mathematician known to have picked this up? Any secondary source known?

The graph already shows the total number of binary ones in brackets.

Is there any graph available that shows the number of trailing ones? Uwappa (talk) 07:46, 25 June 2024 (UTC)

There does not seem to be a graph yet that shows how a Collatz sequence impacts trailing bits of binary numbers.

Created a graph for Collatz_conjecture#As_an_abstract_machine_that_computes_in_base_two showing how the Collatz conjecture 'nibbles' on trailing bits, binary ones and zeroes:

Uwappa (talk) 13:28, 14 July 2024 (UTC)

I am proposing a major edit to this page.

The following discussion is closed. Please do not modify it. Subsequent comments should be made on the appropriate discussion page. No further edits should be made to this discussion.

---

The added text is in ALL CAPS (will be changed to sentence structure once officially added to text). The added text is from the recently published paper “Hahn, Kirk O., 2024, Analysis of Collatz Conjecture Rules, Theoretical Mathematics & Applications, Volume 14, Issue 1, 1 – 76.” I am the author of this paper, so I tried to maintain a neutral “voice” with the information. No hype or exaggeration. We are all scientists or scientists-in-training when it comes to evaluating the changes to the page, so we must adhere to the “scientific method”. Which means in this case that all disclosed information in the paper is assumed to be true, since the paper has been published in a peer-reviewed, AMS registered journal. The journal is not the most prestigious but it is good enough to be included in the thousands of mathematical journals. The disclosure is assumed true unless someone with facts or evidence shows a mistake or error in the calculations or conclusions. Opinions, beliefs or feelings have no place in science. I encourage all commenters, whether positive or negative, to read the paper first [1]. We can only have an informed discussion with everybody knowing the facts. I will answer any questions that the commenters may have for me.

--------------------------------------------

Paul Erdős said about the Collatz conjecture: "Mathematics may not be ready for such problems."[7] Jeffrey Lagarias stated in 2010 that the Collatz conjecture "is an extraordinarily difficult problem, completely out of reach of present day mathematics".[8] FORTUNATELY, THEY WERE NOT CORRECT.

IN 2024, KIRK HAHN DISCLOSED THAT THE COLLATZ CONJECTURE WAS TRUE FOR ALL POSITIVE INTEGERS.[40] THE PAPER SHOWED WITH FORMAL MATHEMATICAL PROOFS THAT THE SOLUTION INCLUDES ALL POSITIVE INTEGERS, ALL POSITIVE INTEGERS EVENTUALLY GO TO “1” WHEN THE COLLATZ RULES ARE USED TO ITERATE THE NUMBERS, IT IS MATHEMATICAL IMPOSSIBLE TO FORM LOOPS, EXCEPT FOR THE 4-2-1 MINOR LOOP AND NO POSITIVE INTEGER CONTINUOUSLY GOES UP TOWARD INFINITY WITHOUT EVENTUALLY DECREASING TO “1”.

ADDITIONALLY, THE POSITIVE INTEGERS FORM A SIMPLE AND PREDICTABLE DENDRITIC (TREE-LIKE) PATTERN WHEN APPROPRIATELY GRAPHED.

[INSERT FIGURE OF DENDRITIC PATTERN]

THIS OBSERVATION LEAD TO THE PRODUCTION OF A GENERAL EQUATION FOR THE COLLATZ CONJECTURE THAT IS ABLE TO CALCULATE ALL THE PARAMETERS. THE EQUATION IS ABLE TO CALCULATE THE NUMBER OF STEPS FROM THE INITIAL POSITIVE INTEGER TO REACHING “1”, THE INTERMEDIATE VALUES DURING ITERATION AND THEIR PRECISE LOCATION ON THE DENDRITIC PATTERN AND SHOWS ALL POSITIVE INTEGERS GOES TO “1”. IT CAN EVEN CALCULATE THE ENTIRE ITERATION WITH ONLY KNOWING THE INITIAL POSITIVE INTEGER.

[INSERT FIGURE OF GENERAL EQUATION]

------------------------------------------

Since 3n + 1 is even whenever n is odd, one may instead use the "shortcut" form of the Collatz function:

Figure of equation

This definition yields smaller values for the stopping time and total stopping time without changing the overall dynamics of the process. HOWEVER, IT SHOULD BE REMEMBERED THAT THE RULE FOR ODD NUMBERS IS NOT THIS “SHORTCUT”, BUT JUST 3N+1. COMBINING THE ODD AND EVEN STEPS MAY SHORTENED THE NUMBER OF STEPS, But IT ALSO OBSCURES THE TRUE RELATIONSHIP OF THE NUMBERS WHEN DEVELOPING A PROOF OF THE CONJECTURE.

40. HAHN, KIRK O., 2024, ANALYSIS OF COLLATZ CONJECTURE RULES, THEORETICAL MATHEMATICS & APPLICATIONS, VOLUME 14 ISSUE 1, 1 – 76 45.50.231.56 (talk) 17:20, 13 August 2024 (UTC)

Sorry, Wikipedia is not the right place to promote your own original research.

See above: Collatz 2nd loop proven impossible in 5 stepsof easy logic. Uwappa (talk) 17:45, 13 August 2024 (UTC)

This is not "original research" as defined by Wikipedia. It is research that has been published in a peer-reviewed journal, as such, it is no different than any other published paper. It is true I have proposed the edit but it is from a published paper. 45.50.231.56 (talk) 19:35, 13 August 2024 (UTC)

It is from a journal never deemed worthy of indexing in MathSciNet, and removed from indexing in zbMATH in 2017. These are indexes that aim to include all respectable mathematics journals, from which I conclude that their deliberate exclusion means they think it is not a respectable mathematics journal. —David Eppstein (talk) 21:21, 13 August 2024 (UTC)

Unsurprisingly, the publisher (Scienpress Ltd) was on Beall's List. --JBL

For some reason its doi prefix, 10.47260, does not appear to be marked as predatory by User:Headbomb's script for that. Maybe it should be? —David Eppstein (talk) 17:48, 14 August 2024 (UTC)

Added. Headbomb {t · c · p · b} 18:18, 14 August 2024 (UTC)

This is your opinion, but it is not a requirement of either Wikipedia’s policy or rules. As I mentioned, TMA is not the most prestigious Math journal; however, it meets the minimum qualifications for a reliable source for Wikipedia. Wikipedia defines a “reliable source” has being “published” [yes], peer-reviewed [yes], and not a predatory journal [yes]. Additionally, TMA is listed in the AMS Digital Mathematics Registry, the journal is deposited with the National Librarian of the National Library of New Zealand, it is published in both online and print versions, it is 1 of 14 journals in four general categories published by Scientific Press International Limited and has ISSN numbers for both print (1792-9687) and online (1792-9709). TMA is not a “predatory journal”. It only has a modest publication fee, compared to other journals that charge thousands of dollars ($3,370 for J. Number Theory). The Beall's List is just one man’s opinion of potential predatory journals and publishers. The reason for a reliable source is the conclusion that the papers in this type of journal will also have higher probability of being reliable. In this case, all the information in the published paper is self-verifiable. Any reader of the paper can determine for themselves if the information is true by repeating the disclosed math. The level of math in the paper is high school level, which most people reading this page can do without any advance math knowledge. If the information is unreliable, then point out the errors in the calculations or conclusions. Therefore, let us discuss the disclosed mathematics. Is it true or false? 45.50.231.56 (talk) 19:33, 14 August 2024 (UTC)

"it meets the minimum qualifications for a reliable source for Wikipedia"

As a predatory journal, it does not meet WP:RS. See WP:VANPRED in particular. Headbomb {t · c · p · b} 19:41, 14 August 2024 (UTC)

It's largely irrelevant to our discussion here of whether we can include this material, but if you must know, I believe the arguments in the paper to be invalid. The reason is that, although the paper assumes that the arguments to the Collatz iteration are positive, it never uses that assumption. Therefore, if it provided a valid argument, that argument would apply equally well to the application of the Collatz iteration to negative integers. But we know from Collatz conjecture § Iterating on all integers that for negative integers there are at least four different Collatz cycles. —David Eppstein (talk) 19:48, 14 August 2024 (UTC)

The conjecture only pertains to positive integers, so negative numbers are not included in the analysis of the conjecture. 45.50.231.56 (talk) 05:45, 15 August 2024 (UTC)

[...] it meets the minimum qualifications for a reliable source for Wikipedia. No, it really doesn't.

Therefore, let us discuss the disclosed mathematics. That's not what we're here for. Like, at all. XOR'easter (talk) 22:51, 14 August 2024 (UTC)

The discussion above is closed. Please do not modify it. Subsequent comments should be made on the appropriate discussion page. No further edits should be made to this discussion.

only integers

The definition says: "If the previous term is even, the next term is one half of the previous term. If the previous term is odd, the next term is 3 times the previous term plus 1.". So, you can not choose non-integers for the Collatz conjecture and the sections Iterating on rationals with odd denominators, 2-adic extension and Iterating on real or complex numbers need to be removed. 94.31.89.138 (talk) 18:01, 20 August 2024 (UTC)

And the section talks about it being an extension of the map.Naraht (talk) 18:03, 23 September 2024 (UTC)

All of these sections define clearly and properly what they mean and are adequately sourced. —David Eppstein (talk) 18:39, 23 September 2024 (UTC)

References

What is/are the references/citations that disclose the information in paragraph "Iterating on all integers"? 45.50.231.56 (talk) 15:11, 23 September 2024 (UTC)

I think much of this can be found in Lagarias 1985 section 2.6 and its references. —David Eppstein (talk) 17:26, 23 September 2024 (UTC)