Lifting The Edge
A simple but powerful lemma: LTE
Preda Mihăilescu is a mathematician who solved a famous open problem. He was trained by some of the best mathematicians in the world, but spent his early career working on turbines and later on computer security. Yet he found time to solve a problem that had been open for over a century. Now he is a professor at Georg-August University in Göttingen.
Today Ken and I want to talk about solving hard open problems.
Hard open problems often seem glued down shut everywhere. In complexity theory we have all experienced this. Not just versus , we just cannot seem to get a nontrivial lower bound anywhere. Yet one feature of a sheer conundrum is that lifting an edge in just one place is often enough to pull the whole thing up. We have at least experienced this with household tasks, but how can we sense where to pry in theory?
While Mihăilescu is a professional mathematician by training, his solution of a famous Diophantine problem was a bit of a shock to the number theory community. Indeed a double shock: both the who and the how were not as expected. The answer was as expected: the Diophantine equation had no nontrivial solutions as almost everyone believed. We often argue here at GLL that beliefs are not proofs, but the community does indeed sometimes “guess” right.
First let’s tell who he was and what he did.
Who. He was certainly not an unknown or an amateur, since his Ph.D. thesis was on applied number theory. His proof was quickly understood and accepted by the number theory community. They realized it was not only correct, it was a brilliant piece of work—a beautiful argument.
How. He was also able to solve the problem in a manner that was a surprise. The problem was to show that a certain Diophantine equation has only the trivial known solutions. Using deep methods this had been reduced in principle to a finite search. Unfortunately the search was over an enormous range, so no one expected that to yield a solution. Many thought that a solution might be based on reducing the range of the search until it could be handled.
Mihăilescu’s proof went a completely different way. It avoided any search. Actually the initial proof did use a small known fact about the solution sizes that was based on computation, but later he removed even that mild use of search.
What. He solved what was known as Catalan’s Conjecture. Of course . In 1844 this raised an obvious question in the mind of Eugène Catalan: are there other solutions? More exactly, are there other solutions to
where are primes and are integers? He conjectured no. This is the problem that Mihăilescu solved: proving that there are no other solutions.
The proof is very clever and uses powerful methods from the theory of cyclotomic integers. This was something that Mihăilescu knew quite a bit about. But where to start?
There is a fascinating interview with him, with a passage about how he got his edge. He heard a talk by Guillaume Hanrot at a conference in Rome, and returned to Paris, where he was spending time doing research during the summer. He said:
It happened that within a week or two, I could do a step that was then considered to be non-negligible; I proved the so-called “double Wieferich conditions.” This was encouraging and may have strengthened my tenacity.
He goes on to describe in the interview that he used results from many people and many sources. But the basic point is this: He almost immediately made a little progress. He did not solve the problem instantly, but did get some new insight that gave a slight result. This progress convinced him that he was on the right track.
One of the key issues in solving open problems is to find some even small fissure in the problem—one that none before have noticed. This fires the researcher up and also suggests that perhaps, just perhaps, one is on a path that will lead to more progress, if not a complete uncovering of the problem.
Moving the Lump
If there is no fissure yet, there may still be a lump, an air pocket that can be shifted around. Perhaps the problem can be re-stated in other ways, which may suggest fresh ideas.
Something like this also helped in the proof of the Catalan conjecture. We will not delve into the details—the proof is very well surveyed in a paper by Tauno Metsänkylä, called “Catalan’s Conjecture: Another Old Diophantine Problem Solved.” He does a great job explaining both the history of attempts at the problem, early partial results, and how Mihăilescu proved his theorem. So go there to see the details or even just get a feel for how one solves such a beautiful conjecture.
But we can comment on the “lump,” which was well-noted in previous work on the conjecture. An obvious idea is to take logarithms and get
If is very large, then
where the error term is very small. Now assume that and are distinct primes, which is the main case, then such almost equations lead directly to deep results on Diophantine approximations. In particular they are close to inequalities of Alan Baker. Much of the work on this approach was done by Robert Tijdeman using Baker’s results. Michel Langevin computed a value of
for the bound of possible other solutions to the Catalan conjecture—clearly way beyond our ability to search. As we said, trying to compress the search itself turned out not to be the place to tug harder. It took a different approach and a different set of tools. The main lever for Mihăilescu, as related in the survey, was a way of translating back from relations involving ideals to relations on numbers. Metsänkylä also highlights a smaller tool, one known in the above work but applied several times by Mihăilescu, and we mention it because it may help loosen problems in other areas.
If you Google LTE you will find that its all about phone protocols. We are not interested in them. Well phone protocols are interesting, and we do use them everyday. But we are interested in a wonderful lemma that is often called LTE, for “Lifting The Exponent.”
The survey by Metsänkylä claims that we all should know this lemma, as it is quite useful in general. I did not know the lemma by this name, nor Ken, and so we thought we might discuss it here.
Lemma 1 Let where is a prime. Then
As pointed out here, this often arises in solving problems on math Olympiads. It is a simple, but powerful tool for attacking exponential Diophantine equations. It is easy to prove, with an unclear history—it is unknown who discovered it.
Proof: By Fermat’s Little Theorem, . Now factor
has identical terms modulo , so it is modulo . This implies that is divisible by .
The above is the simplest version of the LTE. There are more powerful ways to view the “trick,” and there is more to say about this type of argument. But that would require some discussion of valuations that I would prefer to avoid.
What other simple tools like LTE might be levers? I think we all need to know as many of these simple but powerful ones as possible. They clearly are extremely useful in everyday practice of solving problems, and even in solving hard open problems.