The Riemann Hypothesis
golem.ph.utexas.edu
golem.ph.utexas.edu
> Let’s elaborate now on the connection (explained on the cover of this issue) of the Riemann Hypothesis to pseudorandomness. Consider long sequences of the letters L, R, S, such as
> S S R S L L L L L S L R R L S R R R R R S L S L S L L . . .
> Such a sequence can be thought of as a set of instructions (L for Left, R for Right, S for Stay) for a person or robot walking in a straight line. Each time the next instruction moves it one unit of length Left or Right or makes it Stay. If such a sequence is chosen at random (this is sometimes called a random walk or a drunkard’s walk), then the moving object would stay relatively close to the origin with high probability: if the sequence was of n steps, almost surely its distance from the starting point would be close to √n. For the Riemann Hypothesis, the explicit sequence of instructions called the Möbius function is determined as follows for each step t. If t is divisible by any prime more than once then the instruction is Stay (e.g., t=18, which is divisible by 32). Otherwise, if t is divisible by an even number of distinct primes, then the instruction is Right, and if by an odd number of distinct primes, the instruction is Left (e.g., for t=21=3x7 it is Right, and for t=30=2x3x5 it is Left). This explicit sequence of instructions, which is determined by the prime numbers, causes a robot to look drunk, if and only if the Riemann Hypothesis is true!
Oh hey, I did my undergrad thesis on that! It generates neat looking graphics:
Did they mean 3x3x2 instead of 32? There is no way 18 is divisible by 32 in any common sense of divisible.
> This explicit sequence of instructions, which is determined by the prime numbers, causes a robot to look drunk, if and only if the Riemann Hypothesis is true!
So, do they look drunk for large walks? That sounds like something that is easily computed for tens of thousands of steps.
> if the sequence was of n steps, almost surely its distance from the starting point would be close to √n.
Of course that raises the question "What is close?"
Most fascinating to me is that many theories are effectively 1-way functions. Entire branches of mathematics have been developed to prove otherwise trivially stated claims. It is something to marvel at, if from a safe distance.
You just got used to it because you learned it very young. I'm pretty sure it wasn't that obvious when you learned it.
Repeated addition is an algorithm that works when you have a non-negative integer argument. Imagining that the algorithm defines the operation limits conception.
Consider 3 x 2. If we take that approach, it seems ok - we understand it to mean "add together 3 2's" - 2 + 2 + 2, which gives the correct answer of 6.
What about -3 * -2? What does it mean to add a negative number of times?
What about pi * pi? What does it mean to add something pi times?
What about the matrix M * the matrix N?
etc. The parent's point is that this repeated addition thing is just an algorithm one can use to calculate a multiplication for some operands, specifically whole numbers, not a general definition of the operation of multiplication.
For example if we want to know π^2 to about 3 decimal digits (~9.87), we can start by using an approximation of π to about 4 decimal places (~3.142) and then multiplying the two decimals.
For rational numbers, multiplication algorithms are usually built on breaking a number down into constituent pieces, multiplying every pair of pieces from the two multiplicands, and then adding up all of the partial products.
Matrix multiplication has the additional complication that the elementary terms involved (entries in different places in the matrix) cannot be added to each-other. But the basic procedure is still the same: break the two multiplicands down into basic units which we already know a multiplication table for, compute all of the partial products, then sum them up.
We can treat π purely symbolically if we like, but as soon as we want to do anything useful with it we need some kind of approximation or algorithm.
For example, if someone asks you to explain Euclid's proof of the infinitude of the primes, and you say that Euclid did not provide any such proof and nothing more, I think it's quite disingenuous. It would be more proper to say, from a constructivist view, the argument Euclid made isn't a valid proof, and then either explain the proof in the logical context in which it was made or decline to.
In this case, the point of discussion was separating the definition of multiplication from an algorithm implementing it. It's quite unfair to silently take a position that a mathematical definition without an algorithm isn't valid or meaningful and then on that basis argue that only numerical approximations to transcendentals have meaning.
So many common mathematical concepts such as "the integers" have no meaning in a constructivist approach that it's not sensible to engage in mathematical discussion without establishing that one's fundamental basis of approach varies so widely from the common one.
-3 x -2, multiply signs first: +, remainder: 3x2 repeat 2 3 times and add; 2 + 2 + 2 = 3, remainder: 0
3.141 * 3.141, multiply signs first: +, remainder 3x2 repeat 3.141 3 times and add; 3.141 + 3.141 + 3.141 = 9,432, remainder: 3.141 * 0.141
shift decimal: 3.141 * 1.41, remainder: 3.141 * 1.41
3.141 * 1.41, repeat 3.141 1 times and add: 3.141 = 3.141, remainder: 3.141 * 0.41
shift onto result: 9.432 + 0.3141 = 9.7461, remainder: 3.141 * 0.41
shift decimal: 3.141 * 4.1
repeat 3.141 4 times and add; 12.564, remainder: 3.1410.1
shift onto result: 9.87174
shift decimal: 3.141 1
shift onto result: 10,053764
result: 9,875881
check back with calculator: 3.141 * 3.141 = 9,875881
Multiplication can be represented as a number of additions and shifting the results of substeps over the decimal point
My son actually asked me that a while back (or rather, “why does a negative times a negative make a positive?”), and I honestly didn’t have a very satisfying answer. The best I could come up with was to go back to the definition of multiplication as repeated addition and then start with multiplying/repeated-adding a negative number by a positive number: that would work backward on the number line and give you a negative number. Then, since multiplication is commutative, a positive number multiplied by a negative number must behave the same way: multiplying a positive by a negative causes the negative to move backwards. So, if multiplying a positive by a negative moves it the “other way”, multiplying a negative by a negative must move the first number to the right.
It works, but it’s not as intuitive as I would have liked - I did better with why negative exponents are 1/x^n and why the angles in a triangle add up to 90 degrees.
- multiplication as function composition, eg the product of two matrices is the linear transform obtained by applying the right matrix and then the left (onto a column vector)
- multiplication as “the operation that distributes over addition” — in the theory of rings and algebras, if you have one operator “+” which forms an abelian group, then any operator “•” such that (a+b)•(c+d) = ac+ad+bc+bd for all a,b,c,d then you have a ring (if • is associative) or an algebra (otherwise) and you can apply all kinds of structure theorems.
This is very oversimplified but it’s important to remember that you can multiply lots of things which don’t look like integers at all.
Incidentally, "exponentiation is just repeated multiplication", right? Try using iteration to solve 0^0.
lim{x -> 0} (0^x) = 0
lim{x -> 0} (x^0) = 1
E.g. (10^0.001) = (1.00230524...)
Exponentiation is not like multiplication because it's not associative.
(2^3)^4 != 2^(3^4)
Similar extensions happened with negative arguments. At a certain point, pure intuition vanishes, and instead you are left with the task of simply creating a set of rules that define a consistent mathematics. Often times, the approach you take is limited by this very requirement; our mathematics is only consistent if a negative multiplied by a negative results in a positive, for instance.
This topic hints at the gap between applied mathematics rooted in concrete reality, as it were, and theoretical mathematics, which of course deals purely with abstract structures.
This seems like an exaggeration.
I have seen little evidence that people who become interested in mathematics have an unusually difficult time “overcoming” this viewpoint.
Turned out you can do whatever you want... It just that usually you want addition to be commutative and usually want to use an infinite set of symbols called numbers.
For example, if we apply the same pair of 3-dimensional rotations in opposite orders, we generally get different results.
Scaling and planar rotation (in combination, a.k.a. “complex numbers”) are conveniently among the types of commutative multiplication.
> multiplication is really just addition
This is a misleading summary. That multiplication of integers per se can be re-expressed as addition (or if you like, as counting) depends on the basic parts involved being very simple and uniform. The basic multiplication table for integers is just
× | -1 0 1
–––––––––––––
-1 | 1 0 -1
0 | 0 0 0
1 | -1 0 1
But other kinds of numbers have richer structure based on a richer multiplication table of basic elements.
Multiplying the sides gives you the area because multiplication was invented/discovered to do that.
2x3 = 3 + 3
...
...
3x2 = 2 + 2 + 2
..
..
..
since rotation doesn't change the number of dots, we expect 2x3 and 3x2 grid of dots to contain the same number of dots, which proves that multiplication is commutative.
In his book on the topic, William Stein did not get around to the connection to the product of primes until page 121.
Then I think, “My hair is already falling out. Do I need something like this to accelerate the process?”
But there’s no way at all that “most mathematicians find the Riemann Hypothesis frightening” as you suggest.
So with respect to the original comment I was replying to, there are other areas of mathematics that one can study that are well understood and not so opaque as the Riemann hypothesis.
> Every now and then I try to delve into the frightening world of math.
To want to understand is to be human. :)
Going into undergrad I was briefly discouraged from going into mathematics because this was the impression I got. They're interesting to think about, but I didn't want my future to be firmly situated in inapplicable theory.
I say this knowing there is plenty of work to be done in the applied mathematics, especially in trying to simplifying the understanding of complex problems. I'd like to see more of the glorification of moderately hard problems which take more time to explain but are well within the grasp of people who start working on it, than easy to explain problems which will likely never be in the grasp of anyone.
“Tinkering” with mathematical concepts is fundamentally different from the kind of tinkering I can do, but looking from the outside in.. I’ll probably pick up a calculus textbook one day :)
There could be beautiful stuff concealed by a layer of ugly than mathematics never breaches.
And hence a well-known suggestion is that when tackling a hard problem, is to try finding a proof on even days, and a counterexample on odd days...
And indeed, lots of people tried (and still try) to find counterexamples to, or otherwise disprove, the Riemann Hypothesis. However, there are indeed many, many results and heuristics that give a strong suggestion that the RH might be true -- far more than mere numerical results computing zeroes of the Zeta function. Of course none of them constitute a proof; but this really goes far beyond a simple hope for "beauty" in the theory.
In practice it may not change much, but more philosophically speaking, it's dangerous to take something as granted without a proof. If we then have many ideas building off this unproven idea, and it's later shown to be false, a lot of those theorems would be based off a false premise. This doesn't necessarily mean they the proposition is incorrect, but it would mean that they are unproven.
It's more to satisfy the rigour in maths, and also pose as a challenge to mathematicians. In the journey to proving RH a lot of new ideas could be found that could prove useful, too.
A silly example (from memory) using another rather non-obvious proof.
1. Assume 2^(1/4) = X/Y for integers X/Y (Assume the quartic root of 2 is rational)
2. Raise both sides to the 4th power: 2 = X^4 / Y^4
3. Multiply both sides by Y^4: Y^4 + Y^4 = X^4
4. QED, quartic root of 2 is irrational, by contradiction with Fermat's last theorem.
2. I'm getting the impression from this article that solving the Riemann Hypothesis is similar to solving P=NP in that a solution can be used to attack RSA encryption.
Note that 1) P=NP does not necessarily give raise to any polynomial algorithm that solves a NP problem. The proof would prove the existence of one such algorithm, but it might well never be found (which is the current status quo) 2) even if it would be polynomial, it could still run longer than the heat of the universe. O(n) = n^10000000 would still be a polynomial runtime for example. The second reason is why Donald Knuth does think that P=NP might be possible.
I thought we knew an algorithm that, if P=NP, would solve NP problems in P time, (but with absurd constants), and otherwise solves the problems is worse than polytime.
But I could be remembering this totally wrong.
Forget everything practical - we are in deep theoretic waters here! There are thousands of algorithm with even a polynomial solution where you still go for the heuristic because the polynomial version is way to slow.
> Isn’t there some (highly impractical) algorithm which dovetails through different Turing machines, in a way that has an asymptotically optimal runtime for a given problem, just with really terrible constants?
Optimal might be, as long as optimal does not mean polynomial. Otherwise you would read about it in the newspapers ;) I don't know of such algorithm, but "trying out different turing machines" gives me a strong gut feeling of "not polynomial".
> I thought we knew an algorithm that, if P=NP, would solve NP problems in P time, (but with absurd constants), and otherwise solves the problems is worse than polytime.
Is that the algorithm you are refering to? Sounds like what Turing proposed once. The interesting branch is the P=NP, since then you could answer really really interesting things in P. Theoretically - and if indeed P=NP ;)
People tend to treat P as Omega(n^4) because all the P algorithms they know are. But that's not because P is everywhere that small, it's because larger P algorithms are just as infeasible as O(e^n) in practical computers will ever be for human timespans, as long as you choose a reasonably large N, so they aren't studied much in practice.
The article is spot on. I've had so many moments where the math looks so fishy that it seems like R has to equal 1/2 (ie hypothesis is true), but I just don't have the facts to prove it. In particular, it's really hard to evaluate the infinite sums you find working thru the problem. I actually believe that there's a good chance the hypothesis is false but we'll see someday.
Well, like Prof Baez says, unless you've solved other major open problems before, it's probably unwise to believe you'll be the one to crack it. You are likely to gain more by sharing your leads and seeing what mathematicians have to say.
Impressively, almost every sentence in your comment was already addressed by the OP linked Twitter thread of warnings.