"Embarrassing" open problems in maths | Hacker News Reader

"Embarrassing" open problems in maths

angryfaic.wordpress.com

90 pointsColinWright24 comments

Here's an open problem that is not hard to understand (high school math is sufficient), but whose solution would be one of the most important advances in mathematics in the last 100 years, easily:

    Let H_n = 1 + 1/2 + 1/3 + ... + 1/n

So, H_1 = 1, H_2 = 1 + 1/2, and so on.

    Let divsum(n) = the sum of the divisors of n

For example, divsum(10) = 1 + 2 + 5 + 10 = 18, and divsum(8) = 1 + 2 + 4 + 8 = 15.

Here's the problem:

    Prove that for n > 1,
      divsum(n) < H_n + exp(H_n)*log(H_n)

It turns out that this is equivalent to the Riemann hypothesis. Their equivalence is shown here: http://arxiv.org/pdf/math/0008177v2

The problem makes enough sense in what it's trying to prove, I can't really understand it though without knowing what it would be used for.

Used for?

Many problems in math have no intended practical uses (although uses, funnily enough, tend to turn up in time.)

Knowing what it might be used for really doesn't usually offer any special insight into the nature of the problem, nor how to solve it.

Say it this way then: why that particular equation? Something must have prompted the formulation of the question - what was it?

The questions are answered in the article. The equivalence is not supposed to be obvious even to other number theorists. Most of the article is devoted to explaining "why" it works since the actual proof is two paragraphs.

Don't know what you're talking about. The article is about unproved theorems. They are described as being simple or obvious, but there's nothing obvious about

Prove that for n > 1, divsum(n) < H_n + exp(H_n)log(H_n)

why exp log? That's the question.

I believe that hyperbovine was referring to the article linked by tzs that explains the relation.

http://arxiv.org/pdf/math/0008177v2

See the entire field of number theory for something that didn't have applications when it was conceived. Gauss, Euler and the other early number theorists were essentially just amusing themselves with stuff like the phi function. Then cryptography became a serious open problem, and boom.

Interestingly enough this is most often the case with pure mathemetics: their proofs are pursued purely in the interest of understanding & attaining them - the implications & applications of which are sometimes unrealized for decades (a great example is Evariste Galois: his number theory and symmetry/group work was decades-later applied by physicists to define many of the laws physics appear to obey - check out the wiki).

Not to mention the application of number theory to cryptography.

Or a certain obscure piece of algebra discovered by one G. Boole.

(Edit: During his time, Boole's results were practically unknown except to other logicians, and certainly nobody expected to find any practical use for them. It wasn't until the 1930s when Claude Shannon realized that the algebra that now carries Boole's name could be used to analyze digital electric cirquits.)

wow awsome

A novel proof involves making novel connections, rigorously showing how different parts of mathematics can be made to work together in ways that haven't been thought of. When you look at it that way it's not hard to imagine the value in solving puzzles like this, even if it's impossible to know the specifics ahead of time (which are by nature unknown).

http://en.wikipedia.org/wiki/Riemann_hypothesis#Consequences...

For the first problem, he goes to the trouble of defining "graph" and "tree", as though his audience has no math background, but doesn't bother defining "labeled". For those wondering WTF an "unlabeled tree" is: http://mathworld.wolfram.com/LabeledGraph.html

I'm reminded of two other "embarrassing" open problems.

A perfect number is a number whose divisors sum to return the original number. Thus, 6 is a perfect number since 1 + 2 + 3 = 6. 28 is also a perfect number since 1 + 2 + 4 + 7 + 14 = 28. But 8 is not a perfect number since 1 + 2 + 4 = 7.

1. Are there an infinite number of perfect numbers?

2. Are there any odd perfect numbers?

A slight nitpick. Your definition should be a number whose proper divisors sum to the original number. Or it should be whose divisors sum to twice the original number.

Point taken, good catch.

A slight typo in the author's bit (which is fascinating), the Collatz sequence doesn't terminate in a series of 1's. By its definition, once 1 is reached, the series repeats {1,4,2,1,4....}. Thus, the number of steps required to reach 1 is called the "stopping time" of the sequence. See the Wikipedia article on the Collatz conjecture for some great visualizations of low seed value termination trajectories for the Collatz sequence:

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

These are not simple problems.

If we consider labelled trees then this question has any easy solution: there are labelled trees on n vertices. Counting the total number of graphs on n vertices is even easier. However, no closed form solution is known for unlabelled trees and this problem has been open for well over a century.

Hmm, any node can be a root node which is tricky, but not show stopper. A root node can have 1 to N-1 branches not so bad. You can order them by some sort of weight with each leaf being (depth * 2N)^N so they are strictly ordered, still looking good. But, how do you count mirror images. AKA a simple star with a center point and N edges just counts as 1.

I have just found and entry on OEIS for the general formula for the first problem. http://oeis.org/A000055

G.f.: A(x) = 1 + T(x)-T^2(x)/2+T(x^2)/2, where T(x) = x + x^2 + 2*x^3 + … is g.f. for A000081

I havent checked it, I presume its wrong tho?

The original article asks for a closed-form solution. "Closed-form" is not precisely defined (http://en.wikipedia.org/wiki/Closed-form_expression, http://...), but I do not think anybody would call that a closed-form solution.

Related post: Mathematical Embarassments http://rjlipton.wordpress.com/2009/12/26/mathematical-embarr...

Obviously e and pi are irrational. But it has not yet been proved that e + pi is irrational.

Reply on news.ycombinator.com