> A meeting on how to extend the GPY method was immediately organized at the American Institute of Mathematics in San Jose, California. As a bright-eyed and bushy-tailed grad student, I felt extraordinarily lucky to be there among the world’s top experts. By the end of the week, the experts agreed that it was basically impossible to improve the GPY method to get bounded prime gaps. Fortunately, Yitang Zhang did not attend this meeting. Almost a decade later, after years of incredibly hard work in relative isolation, he found a way around the impasse and proved the experts wrong. I guess the moral of my story is that when people organize meetings on how not to solve the Riemann hypothesis (as they do from time to time), don’t go!
Distantly related question. It was claimed that Alpha Zero taught itself to play incredibly high level chess from the very basic point of playing with itself millions of times after having been fed the basic building block rules of chess and nothing else.
Now I'm wondering if something like this can be made to work for discovering new mathematical relationships or solving existing hypothesis by training a neural network with what we know of maths so far and then letting it "play" with the equations?
There is a sense in which that is a great idea, and a sense in which it is a not so great idea. If AlphaProof could prove theorems as superhumanly as AlphaGo wins at Go, that would really be something, they might be able to claim all of the millennium prizes. However, the longterm usefulness to mathematics may be somewhat limited. Mathematicians are interested in proofs not so much because of the statements, but because of what those proofs add to our knowledge of the way math fits together. It isn't just about "true" or "false," it's about why. If AlphaProof generated a long and unreadable proof with no discernible structure, it would not be such a large contribution to mathematics as if a human figured out "why" and wrote it in a way other humans could understand.
Of course, it is possible that clever users could tease useful information out of the black box truth oracle. Perhaps by modifying the statement of the conjecture and checking each modification, they could discover some parts of the structure of the problem, which would help inspire a useful proof. Furthermore, it would be helpful to never again waste time trying to prove a false conjecture.
Your comment inspired an interesting (to me at least) thought. I'm imagining a world where mathematics becomes too advanced for even the brightest human being, but progress is preserved by proof-generating programs running in data centers. The data centers churn out exabytes of mathematical proofs, and humanity employs an army of what are effectively philologists/semioticians to dissect, mine, and excavate these proofs for meaning.
And when your surpassing creations find the answers you asked for, you can’t understand their analysis and you can’t verify their answers. You have to take their word on faith—Or you use information theory to flatten it for you, to squash the tesseract into two dimensions and the Klein bottle into three, to simplify reality and pray to whatever Gods survived the millennium that your honorable twisting of the truth hasn’t ruptured any of its load-bearing pylons. You hire people like me; the crossbred progeny of profilers and proof assistants and information theorists…
True, and important. However, I suppose it could be argued that if the only results AlphaProof could obtain were long and unreadable proof(s) with no discernible structure, it might suggest something about the epistemic assumptions we tend to make about Occam's Razor and the (so-called) beauty and parsimony.
On that angle, it could be further argued that humans are biased towards 'readable' proofs and that there are many undiscovered 'unreadable' proofs that we simply have no way of obtaining without automation of some kind.
Anyway I assume there are volumes already written on this subject...
Maybe that'll be time to bring in AlphaProofReductor or AlphaProofCanonizer. I'm finding this worry a bit strange. I'm guessing tools evolve together depending on need, so as long as humans want to know 'why and how' there'll be some effort in reduction?
>the epistemic assumptions we tend to make about Occam's Razor and the (so-called) beauty and parsimony.
The vast majority of ways to write a program are unreadable messes. The shortest way to write a program is sometimes an unreadable mess, mainly when it's been code golfed. The longest ways to write a program are always unreadable. Proofs work the same way - and if Alpha Go selects randomly from all of the ways to write a reasonable-length proof, it is virtually guaranteed to pick an unreadable one.
A long unreadable proof would not mean a small proof doesn't exist.
I feel like a unreadable proof would be useful to simply know something is true while a small proof would be more useful to perhaps gain some sort of insight.
A successful AlphaProof would be trained to favor shorter proofs. It would be fast enough to prove RH myriad different ways, and not be finished until its proof cannot be shortened any more, just as AlphaGo isn't finished until no version of it can beat it.
Whether humans could understand the shortest possible proof is another question. It might take generations of study just to understand its outline, and many more to extract all the lemmas implied.
Or, it might turn out to be a trivial trick, and not reveal anything new and substantial.
If AlphaProof generated a long and unreadable proof with no discernible structure, it would not be such a large contribution to mathematics as if a human figured out "why" and wrote it in a way other humans could understand.
Maybe not directly. But if AlphaProof managed to prove the Riemann hypothesis, I bet it wouldn't be long before human mathematicians had managed to decipher the proof and explain it in a way that other mathematicians found useful. It's just a lot easier to re-explain something that other people have already proved, rather than proving it yourself.
Gödel's incompleteness theorem doesn't fill me with the same confidence as you that "a true theorem should have a useful explanation".
In fact, looking at chess engines tells us that sometimes (though not always) brute-force calculation of many possibilities gives us better moves. In the same way some true statements might just be an exhaustive calculation.
Perhaps the four color theorem is the most famous example of a proof that has lacked (still lacks) a lot of useful lemmas in relation to its length: https://en.wikipedia.org/wiki/Four_color_theorem
Yeah, it certainly isn't true that a true theorem should have a useful explanation. I only have my human intuition to go on, but I bet the Riemann hypothesis would not be like the four-color problem. Graph-type problems just seem to lend themselves to exhaustively checking a zillion cases in a boring way, whereas in fields like number theory or analysis that sort of proof hardly ever seems to exist.
I hope we do get some famous theorems proved by computers so that we can see whether it's enlightening to humans. I am quite curious whether my intuition is correct and it is a shame to think I might never know....
We already have machine-assisted proofs which are structured by people but executed by machines. AlphaProof would be that but structured by machine. As with the machine-assisted proofs, there's value in knowing and building upon the result even if the methods themselves can't be adapted for other use.
> If AlphaProof generated a long and unreadable proof...
Then how would anyone be sure it isn't wrong?
It was great that while Goldston and Yıldırım were wrong, their work proved to be useful. A lot of people are glad that Riemann (and Fermat) didn't their problems!
We have automated proof checkers like CoQ. A proof machine would be designed to output proofs in a syntax that could be mechanically checked by an existing verifier.
I don't think so, but I think the trick will be how to score a new mathematical relationship as "interesting". Basically, a fitness metric. With Chess, you have the obvious win/loss metric, and also number of turns and possibly time. With math, how do you quantify the level of interestingness between 2+2=4 and p=np?
This isn't a snarky question, by the way. I'm genuinely interested in how this might be done.
Indeed, existing automated theorem provers do spend a lot of time discarding true statements as "insufficiently interesting". In general, the longer a statement the less interesting it is. The easier it is to prove with simpler statements, the less interesting it is. And if it's superceded by a more general rule it is less interesting.
For example, an automated theorem prover can easily prove many statements of the form "A or not-A or (any long statement)". Those are all uninteresting tautologies that should be discarded.
It's interesting to theorize about improving these heuristics with AI methods, there is some work along these lines like ENIGMA-NG.
It would be sufficiently amazing for AlphaProof to simply answer the questions posed to it. The training data would be pairs of theorems and proofs as already existing in the CoQ and other proof checker literature.
Unless you have a prover that can answer "is this actually a correct proof", your fitness function is essentially "does this look like a proof"
And if you have a prover that can answer that question, you don't need to train a neural network to give you the answer.
Proving maths demands 100% precision and recall, at which point employing ML doesn't make sense - the point of ML is (horribly simplified) stochastic reasoning, not finding truths.
But ML could in theory accelerate the process. For example, AlphaZero uses ML to highlight the correct paths in search algorithms. The same search algorithms exist for stockfish and both can reach the same conclusions, but, AlphaZero ends up looking up much shorter distance than stockfish, yet it wins. If anything, it is significantly more human-like than stockfish.
The search space for proofs is far bigger and less structured than a Go game. A lot of proofs also require creativity, in the sense that they aren't just "find the set of logical steps from 'initial condition' to 'proof'", but they require auxiliary theorems, definitions and constructions that help make the problem manageable.
Another problem is that a lot of proofs starts by exploration. For example, certain bounds for functions or convergence rates are proved without knowing what will be the end result.
Of all the problems that ML could be applied to, I find mathematical proofs one of the least promising. One, I don't see enough similarity between proofs that would allow any algorithm to learn useful patterns; and two, I don't think most mathematicians would trust a proof that cannot be understood (even if the output is a set of steps for a formal system, I imagine translating that to human language could be quite difficult).
I would like to bring up Gödel and his idea that you could construct theorems by multiplying equivalent numbers that represent theorems but I am sure you are well aware of it.
My argument is that it all happens through the application of operators and abstractions i.e. other numbers going through Gödel's approach.
In the same vein, we "should" in theory produce something similar. In RL, we have agents that learn to 'imagine' goals and then achieve them. Given the correct representation of such 'dreams' the models 'could' in theory learn to achieve such auxiliary theorems.
Yes. My formulation was sloppy - I didn't mean "unless" to imply that there can't be a prover. My argument was that without a full prover, you won't have a useful fitness function at all.
And even then recall/precision need to be 100%. And even if you could achieve that, you still end up with something that... generates statements that are provably true. Mild yay.
But that's not the problem. We can generate plenty of those. You want to identify the ones that actually advance the state of knowledge usefully.
Adding an extra point, one thing that makes this difficult is that a lot of this kind of research is not about applying existing ideas but coming up with something that has never been done before, and neutral networks are a lot worse with creativity than with pattern matching. It's also hard to get enough training examples, especially since you'd either want these to be in strict logical language or train a system to recognize whether a hundred page proof in natural language is rigorous or not. So it's like a very long maze where noody knows if you're getting closer to the exit or not, and in most rooms you have to come up with something original or discover a new dimension. And there's the aspect whereby a lot of significant research is: create a new abstraction, realize and convince others that this abstraction is useful and gives you new intuition that lets you solve new problems.
The trick is coming up with a reward function that drives exploration when "played" against itself. Chess has an easy one, win the game. General mathematics doesn't have anything so easily specified.
There is the "prove this conjecture I have" part, which I think will be taken over by machines rather soon (say, within my lifetime). I cannot imagine there is something extra-ordinarily hard that mathematicians do, that is somehow not captured by how a Go player approaches the game.
There is also the "come up with an interesting conjecture" part, which I think is a lot harder. It is extra-ordinarily hard to specify what exactly makes some conjectures more interesting than others. So I reckon this part of math will be much harder to automate in the long run. It will probably require a lot of cross-contamination from AI that manage to write interesting books for example.
> I cannot imagine there is something extra-ordinarily hard that mathematicians do, that is somehow not captured by how a Go player approaches the game.
It's not "extraordinarily hard" but the issue is that math does not have a well-defined search space. A lot of times, proving statements requires quite a lot of intermediate results, additional tools and definitions... There is more creativity in math proofs that people think, and I don't think ML algorithms will be able to reproduce that. At most I see specific algorithms for limited purposes.
Your comment reminds me of Gödel's proof of his incompleteness theorem. Basically, he said that if you treat a mathematical statement as a sequence of tokens, and then assign a number to each token, then you can transform the statement into a big number. Then, going one step further, if a mathematical proof is a sequence of statements then it can be too transformed into a really long number. Then you can come up with rules to manipulate these numbers to create new valid statements and proofs.
I don't know if there was much work done on this idea beyond Gödel's proof, but I think it's a really neat idea that gives a way to manipulate mathematical proofs as objects and create new ones from a very high level view.
you might be able to do something like "predict the next prime number" or "predict the next zero of the Riemann zeta function".
you could try something like this for statements in a formal axiomatic system, but know that you're running up against things like the halting problem / entscheidungsproblem / godel incompleteness. so it may be possible to train a neural net to decide the veracity of a statement and do so more quickly than a human might, but you would inevitably be running up against things that are truly undecidable in nature. which is not like go or chess where although they are difficult, they are decidable.
Yes, but it isn't useful. A conversation also has three outcomes (neutral, you like the person more, or less) and yet it doesn't make conversations similar to chess.
It takes O(n) to check if a chess game follows the rules, and to check who wins. Same for checking a proof written in CoQ. What do you mean by "check?"
But it fails on two counts. One is that it doesn't say what the title claims. We know now what the Rieman Hypothesis is, but how did the author learned to love, and more importantly to "fear" the RH? What's there to fear? The name of the famous movie (with the bomb) doesn't even have "fear" in it, so the author had something in mind with "fear", but after watching the video, I have no clue what.
Second is the promise in the beginning of the video to give us a hint why the RH is important. What we learn is that somehow each zeta zero adds another harmonic to some type of series approximation of the (cousin of the) prime counting function. Which is great; if we add enough harmonics we get to approximate this function as precisely as we want. But why is it important that these zeros are on the vertical line Im z = 0.5 ? I have absolutely no clue.
Don't get me wrong, I find that watching this video was a very good investment of 16 minutes of my life. But there is no need to overpromise, especially since the video delivers a lot as is.
> But why is it important that these zeros are on the vertical line Im z = 0.5
Great question.
The formula works whether or not the zeros have real part 0.5, but its implications are different.
If you're counting primes up to x you will get the main term (roughly x/log x) and each zero p will give an oscillating error term ~ x^p/p. If the real part is always 0.5 then these error terms are all on sqrt(x) scale, which is what you would expect from random variation. If on the other hand you have a single zero right of the line, say at real part 3/4 (and mirror image one at real part 1/4) then now you get a secondary error term of size x^(3/4) that dominates all of the other error terms, giving some extra structure to the primes: they're no longer random, you can predict where they are more or less likely.
> but how did the author learned to love, and more importantly to "fear" the RH? What's there to fear?
It's made abundantly clear: they learned to love it through the course they were fortunate enough to take as an undergraduate, and they learned to fear it later, as a researcher, when they realised that what there was to fear was wasting their career attacking something that was probably just too big and too hard to be sensible for them to attack.
I understand that the real proof of the RH is the friendships we make along the way, but what would happen if we just acted with the assumption that it is true?
There's been a lot of research that has assumed it to be true and built on top of it to find deeper implications.
Still, a number of people who've worked most closely with the Riemann zeta function, even the ones who led the computations and numerical verifications, have expressed doubts on whether the Riemann Hypothesis is actually true: https://arxiv.org/abs/math/0311162
This is the difference between a scientist and a mathematician. A scientist would consider the empirical evidence more than sufficient to consider RH to be true.
Of course there is hope that a proof of RH would reveal some deeper understanding -- not merely a conformation.
I'm not so sure a scientist would consider RH true at this point. Math has a rich history of conjectures appearing true for the first n dimensions, the first k inputs, the first z partial/tangential proofs, etc. The evidence for RH isn't any stronger than that for a plethora of eventually-proven-false conjectures.
Do you know if anyone has tabulated stats on conjecture proofs? That could be a fun dataset to examine.
If one could predict with pinpoint accuracy all the prime numbers approaching infinity with certainty and with trivial resources (without having to test each one for prime-ness), would it have any impact on modern day cryptography?
Not an expert, but the key thing is usually factoring, e.g. finding which prime numbers multiplied together make a certain composite number. The hard part is finding which are the right prime numbers (there are lots of prime numbers). Finding numbers that are prime,just generally,is a very quick operation already.
On RSA-style prime-based crypto potentially but barring a much stronger result than merely being able to cheaply find primes things like ECC would probably still be safe.
If so much technology is built around a hypothesis, it is essentially building a large house of cards if the hypothesis turns out to be incorrect.
Imagine if the world set up a monetary system and what would happen after 100 years if suddenly everyone could print money when a fatal flaw in a system was discovered.
The vertical scaling of the counting function with log(p) went a little quick, does someone know an easy to digest resource to this?
also what would be the logic for now including the p^n of primes, p ??
I felt that way about most of the video. I never took advanced math theory classes, but I have enough background that those classes would probably have been the next step for me if I had continued on.
Seemed like every time I felt like he was about to explain something in a way that would click for me, then all the sudden he left out the last two sentences and moved on.
Some of my lecturers throughout Uni, always glanced across the entire auditorium to see if anyone needed clarity of what was said before switching slide/erasing the blackboard.
Having those extra seconds after something has been said, while being able to watch graphics/text/figures helped the information sink in for me.
This moment to digest what was said is not really available in this video, but I guess youtube is different from a lecture in the sense that the whole thing can be set on pause.
I think I have the impression that the visual explanation here appeared and sometimes even disappeared before him mentioning the "take-home-message".
I am still very impressed with the explainer and the visual assistance though.
Off topic, but does anyone know where one gets started on making motion graphics like in that video? This combination of cool maths and animated visuals is so interesting to me, but I wouldn't even know where to begin. What kind of software is used to generate this kind of visualisation? Are there free or affordable online courses? Is there a job market for someone with this ability and also with software development chops?
3Blue1Brown on YouTube has a number of great videos into math that help give a visual understanding without needing to sit down and do the pure number crunching. I'm not sure he has one on the Riemann Hypothesis in particular, but he does cover a number of items that would be somewhat related and help build a level of comfort with being exposed to the math, even if you can't do the pure number crunching.
Mathologer would be my second recommendation. Once again not sure he has touched the Riemann Hypothesis, but he does a number of great videos where you can start expanding being comfortable with often untouched fields of math (like modular arithematic) while introducing a how seemingly unrelated fields end up having connections.
Videos can go between 20 minutes to an hour and I often enjoy watching one every few days.
Depends on your level of {experience, intended engagement, patience for pedantics, intended outcomes}.
I've found that 3Blue1Brown (youtube) gives a great starting point for many topics. Provided you actively participate in them, the videos will build up some intuition so you know what questions to ask (and why they're worth asking).
The author usually links to followup resources so you know where to go next. I've found his resources a bit hit-or-miss, but they give me enough to know if I want to continue exploring. If I do, I usually check out a good textbook (I refer to https://news.ycombinator.com/item?id=17617825 often).
The accompanying video popped up on my YouTube recommendation list last night and it is really good. Like, you married a numberphile video with 3blue1brown, good.
Still nice of the video in the original post to give a bit more of a historical context, instead of focusing entirely on the mathematics. It could have done without the building analogy around the beginning though, that didn't come up later and was just distracting.
+1 for the 3blue1brown recommendation. Between the two, a non-mathematician can acquire a layperson's comprehension of the Riemann Hypothesis. Additionally, John Derbyshire (of the unfortunate views regarding race) wrote a very good book "Prime Obsession: Bernhard Riemann and the Greatest Unsolved Problem in Mathematics" that covered both historical and mathematical aspects of the Riemann Hypothesis [0].
That was a fantastic video. I was left wondering a bit about the difference between the Riemann Zeta function and the original Zeta function, but I found this 3Blue1Brown video which explains exactly that: https://youtu.be/sD0NjbwqlYw
Matt Haig's "The Humans" talks about humanity finding the answer to the Riemann Hypothesis being feared universally - it's simultaneously very important to the plot, and a convenient MacGuffin.
It's also one of the verses that inspired Voltaire's character Dr. Pangloss to declare that "All is for the best in this, the best of all possible worlds."
"Complex Analysis: An Introduction to the Theory of Analytic Functions of One Complex Variable" By Lars Ahlfors was very enjoyable to me. However, I read it after I already knew Complex Analysis.
i second tristan needham's visual complex analysis.
some other good ones:
* the one we used in my undergrad course was fisher's complex variables which is great if you're learning for the purposes of applications. it's a cheap dover book.
* rudin's real and complex analysis (if theory is your thing. note that rudin's books, while great, do require a good background in math).
* as the article mentions, eli stein has a series of books on the four main branches of analysis. i believe the second book is on complex analysis.
> A meeting on how to extend the GPY method was immediately organized at the American Institute of Mathematics in San Jose, California. As a bright-eyed and bushy-tailed grad student, I felt extraordinarily lucky to be there among the world’s top experts. By the end of the week, the experts agreed that it was basically impossible to improve the GPY method to get bounded prime gaps. Fortunately, Yitang Zhang did not attend this meeting. Almost a decade later, after years of incredibly hard work in relative isolation, he found a way around the impasse and proved the experts wrong. I guess the moral of my story is that when people organize meetings on how not to solve the Riemann hypothesis (as they do from time to time), don’t go!