# Why problem with simple formulation is so hard?

If you ever heard about Collatz conjecture, you know that it is understandable even for middle school students, but no one has solved it yet. The problem is to prove or to disprove that starting with any natural number $$a_0$$ and going $$a_{n+1} = f(a_n)$$, eventually you will always get $$a_m = 1$$ for some $$m$$.

$$f(n)=\begin{cases}n/2&{\text{if }}n\equiv 0{\pmod {2}}\\(3n+1)/2&{\text{if }}n\equiv 1{\pmod {2}}.\end{cases}$$

There a lot of other "simple" problems in mathematics that are still unsolved. For example, Goldbach's conjecture that states:

Every even integer greater than 2 can be expressed as the sum of two primes.

Do you have any intuitive explanation as to why modern advanced mathematics cannot solve such seemingly simple problems?

• I think this has been asked here already. Another astonishing unsolved problem : $(1)$ Is $e+\pi$ irrational ? $(2)$ Is $e\cdot \pi$ irrational ? Although we know that at least one of them must be transcendental, we do not know of either number whether it is irrational. This phenomenon (easy formulation, hard solution) occurs much more often than we would expect. In particular, many easy seeming questions about primes numbers are unsolved. – Peter Aug 26 '19 at 10:37
• Incredible that we do NOT know whether there are infinite many NON-Wieferich-primes ! – Peter Aug 26 '19 at 10:41
• @EeveeTrainer I even do not understand the proof of Dirichtlet's theorem about prime numbers in arithmetic progressions. And the problem is very easy to understand. – Peter Aug 26 '19 at 10:42
• One of the reasons the Goldbach Conjecture is this tough is because it‘s an additive statement but primes are “multiplicative objects“, so there aren‘t many powerful tools relating primes to additive statemenets. – Qi Zhu Aug 26 '19 at 10:45
• What I observed on this site : The Collatz conjecture seems to have the most claimed proofs of all the famous conjectures, apparently the difficulty to solve it is massively underestimated by many people. – Peter Aug 26 '19 at 10:58

Simple problems may be hard to solve because they are really hard problems underneath the surface. Let me explain a little bit of why I think this is so. The reason it may look simple is the way the problem is stated in words and simple arithmetics in the first place. Our traditional understanding of simple number theory and counting like adding, multiplying and dividing numbers we learn very early and is part of some human culture.

The problem of stating problems this simple way is that the underlying mechanics of the problem is hidden from the observer. Numbers in base $$10$$ may look simple because we are used to count and we learn simple rules. However when we iterate those rules they become more and more complex as the numbers change. The $$3n+1$$ problem is a very good example of this. If you study the complexity in base $$2$$ you start to see some features that is difficult to see in base $$10$$, you could also find simple rules that produce the complexity that we see. See ref. The 3x+1 Problem: A Quasi Cellular Automaton by Thomas Cloney, Eric Goles and Gérard Y. Vichniac.

A quote from the paper:

Base 2 is a natural choice because of the control role of the parity of each iterate under eqn.(1) and because it lends itself to detailed high-resolution graphic display. The bit representation displays the "insides" of the iterates, in contrast with number theory approaches that focus only on iterate size, a more limited form of information represented by the envelope of the binary evolution.

If you're not familiar with Cellular Automata, I suggest reading a few tutorials or explanations from Stephen Wolfram or if you have access to the book NKS - before reading this paper. I suggest learning or get an intuition on how simple Automaton rules produce complex output then you can start to connect the dots, atleast get an idea or a sense of what might be going on.

Cloney, Thomas; Goles, Eric; Vichniac, Gérard Y., The (3x+1) problem: A quasi cellular automaton, Complex Syst. 1, No. 2, 349-360 (1987). ZBL0662.10010.

Simple to state, could also mean too many trivial conditions to easily hit a contradiction. That makes it hard to disprove, but combined with abnormal use of defined objects, it makes it nearly impossible until we find more theory.

You can change a conjecture into collaries, or necessary conditions, etc. , but that doesn't easily let us induce it necessarily.

A necessary condition in itself, is not usually a sufficient condition. It takes a big enough set of them to ensnare the problem.

One condition on Collatz is that any nontrivial cycle has a lowest element, with an odd number of prime factors of form $$4k+3$$ when counted with multiplicity if odd.

You can partially induce Goldbach, via Collatz map and https://oeis.org/A158709 but only partially. Even if the sequence is infinite.

Our two main proof types currently seem implausible to reach a conclusion.

• examples of already proven results required for goldbach to be true include a prime between $n$ and $2n-2$ and infinitely many arithmetic progressions of odd primes of length 3. – user645636 Aug 26 '19 at 12:24
• Yes there are sufficient conditions, but they are as hard to prove as the conjecture itself most likely. – user645636 Aug 26 '19 at 13:40
• in fact a lot of open conjectures can be turned into base specific arithmetic, or geometry, but it doesn't prove always. – user645636 Oct 15 '19 at 12:55