Hacker News Reader

Comment by bmc7505 | Hacker News Reader

What are some other problems that appear deceptively simple, but are extremely difficult to solve?

Let n be a positive integer.

Let s(n) be the sum of all positive divisors of n. E.g., s(2) = 1 + 2, s(4) = 1 + 2 + 4, s(20) = 1 + 2 + 4 + 5 + 10 + 20.

Let H(n) = 1 + 1/2 + 1/3 + 1/4 + ... + 1/n.

Question: is it true that s(n) < H(n) + log(H(n)) exp(H(n)) for all n > 1?

(log is natural logarithm)

It turns out that this simple looking problem is equivalent to the Riemann Hypothesis, which is perhaps the most important unsolved problem in pure mathematics. Many of the best minds in mathematics have attempted it in the approximately 160 years since Riemann posed it.

What equivalent means in this context is that if the Riemann Hypothesis is true, than the inequality above is also true, and if the inequality above is true, then the Riemann hypothesis is true.

Maybe just me, but that problem does not look very simple at all. One reason OP's problem is appealing, is because the solution can be easily checked. The solution is a kind of "proof of work". You could never guess the solution without a deep understanding of the problem. But once found, the solution is immediately verifiable.

For many problems one can easily guess the solution, without necessarily knowing the proof (like Fermat did). The answer is almost certainly negative, and a complete solution requires a very long and tedious proof that cannot be checked without a deep understanding of the field and many years of collective effort.

I am specifically interested in problems which can be understood by a child, have hard solutions which cannot be easily guessed, but are easily verified (ex. factoring the product of two large primes). It seems like these problems would make good candidates for one-way-functions, like the diophantine equations and ECC. But elliptic curve cryptology is too difficult to describe to a child.

Quite easy to explain given a few graphs. The explanation boils down on how hard is to accurately draw a curve of such an elliptic function at big x (P3) and then figure out which two other points intersect with a given line near. You can even show it on a big whiteboard.

You can even show how easy out would be for a simple curve where the left part is an easy equation.

The hard part is what makes an equation easy to solve. (And how some elliptic are broken.) It takes at least some high school math to hint at this.

Try this, find the cubic root of 27 by hand. No computer!

Speaking of divisors, there are infinite numbers n such that n and n+1 have the same number of divisors. AFAIK we do not have a way to find such an n > N for any given N without calculating an infinitely growing sequence.

Is there a number which can be written in base 2,3,4,5,6 using only 0 and 1?

What's mind blowing here is that if you ask for base 2, 3, 4 the answers are trivial but for bases 2,3,4,5 somehow you get 82000 and we do not know whether there is another and for 6 it's unknown.

Am I missing something? the number 1 is 1 in all of those bases and therefore can be written using 0 (0 times) and 1 (1 time).

Sometimes mathematicians forget to say "non-trivial", that's what you're missing.

Often in mathematics, we look for the nontrivial solutions to questions like this.

In general, number theory is notorious for containing many questions that are accessible to a layperson but whose proofs rely on arguments that are so difficult that even the basic idea of how the argument works takes many years of study.

Fermat's last theorem is an example, because it can be shown to be equivalent to, among other things, a very deep statement about elliptic curves (yep, the same thing The Fine Answer is about!) that Andrew Wiles proved.

https://en.wikipedia.org/wiki/Modularity_theorem

From the past, we had Fermat's Last Theorem. Looking for ones that are not solved yet? How about "Collatz conjecture "? I think there are more complex ones, but yeah, not so simple to explain.

from everything I've read, collatz has not merely resisted proof, but anything resembling progress. Erdos said that mathematics is not yet ready for such problems.

Conway showed that the generalized Collatz conjecture (recurrences with arbitrary cases dependent on the modulus) is computationally undecidable (halting problem reduces to it). The choice of modulus doesn't even need to be that big to get this result, only ~6500 or so. As far as I know, this is the only substantial result in either direction for this problem.

I suspect it is due to the lack of application for the solution.

I analyzed the problem for a while and theorized ways to collaboratively contribute to the solution. I settled on submitting an integer sequence to OEIS.

http://oeis.org/A261393

True. And there could be many more ridiculously simple problems with hard or no applications (at least for now) we may not be able to solve or progress at all. Math as we know and practice might still fall short. I, for one, be happy that simple to state but solved, Godel's Incompleteness theorem, about the imperfection of the tools, had set the things firmly on stone.

Solving them or progress? May be I don't care, but these little problem, simple ones does encourage one to start thinking about solving problems, they make math accessible to masses.

My favorite example are a few simple-seeming polynomials with integer solutions. (Equations that we want to solve for integers are called "Diophantene equations".)

Here's one that's genuinely easy:

  x^3 + y^3 + z^3 = 29

The solution is x = 1, y = 1, z = 3 (or any permutation thereof).

So how about this one?

  x^3 + y^3 + z^3 = 30

Play around a bit.

Not so easy.

But it does have a solution!

Here it is:

  x = -283059965	

  y = -2218888517	

  z = 2220422932

And what about x^3 + y^3 + z^3 = 33? There is no known solution. It's an open problem!

This is a great visceral demonstration that Diophantene equations are hard: there can exist no algorithm that solves all of them. Diophantene equations, like the Halting Problem, are undecidable.

Can you find (possibly negative) integers x, y, and z, such that x ^ 3 + y ^ 3 + z ^ 3 == 33? If so, it's publication-worthy.

Is the constant 33 important (ie. would it be any less significant if it were 42, or 74 instead) and if so, why?

I was replying that the constants in question include 33, 42 and 74... and realized that I'm late :-) In a more recent survey, though, it is now known that:

> 74 = −284650292555885^3 + 66229832190556^3 + 283450105697727^3 [1] [2].

[1] https://arxiv.org/pdf/1604.07746v1.pdf

[2] https://mathoverflow.net/a/223121

what if I can prove there is no integer solution for it? Is it still publication-worthy?

Even more so!

Another one is Goldbach's Conjecture, which has been verified upto 4E18, but is still unproved.

I would say the collatz conjecture is up there. It's been an entry point for many people into the computational side of mathematics.

Take any positive whole number, n.

If it is even, divide it by 2. (n = 2n)

If it odd, multiply it by 3 and add one. (n = 3n + 1)

Repeat. If n = 1, stop.

Does this process always lead to 1? It seems to, but who knows.

https://en.wikipedia.org/wiki/Collatz_conjecture

Fermat's last theorem is probably the most obvious one.

On an infinite square grid where lines are 1 unit apart, if a circle of radius "r" is centered on an intersection, how many intersections lie within the circle? Answer in terms of "r".

Does n^pi = m have any nontrivial integer solutions?

Does the fractional part of e^n tend to zero?

Reply on news.ycombinator.com