{\huge Lifting The Edge}

A simple but powerful lemma: LTE \vspace{.5in}

Preda Mih\v{a}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 $latex {\mathsf{NP}}&fg=000000$ versus $latex {\mathsf{P}}&fg=000000$, 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\v{a}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.

The Facts

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\v{a}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 $latex {3^{2}-2^{3} = 1}&fg=000000$. 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

$latex \displaystyle x^{p}-y^{q} = 1 &fg=000000$

The Edge

The proof is very clever and uses powerful methods from the theory of cyclotomic integers. This was something that Mih\v{a}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\v{a}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

$latex \displaystyle \ln (x^{p}) = \ln( y^{q} + 1). &fg=000000$

$latex \displaystyle p\ln x = q\ln y + \epsilon &fg=000000$

$latex \displaystyle \exp(\exp(\exp(\exp(730)))) &fg=000000$

LTE

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 connection with Mih\v{a}ilescu's proof is that the LTE lemma is used several times as an essential step. 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, and so thought we might discuss it here.

Lemma 1 Let $latex {a^{q} \equiv b^{q} \bmod q}&fg=000000$ where $latex {q}&fg=000000$ is a prime. Then

$latex \displaystyle a^{q} \equiv b^{q} \bmod q^{2}. &fg=000000$

As pointed out here it 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, $latex {a \equiv b \bmod q}&fg=000000$. Now factor

$latex \displaystyle a^{q}-b^{q} = (a-b)(a^{q-1} + a^{q-2}b + \cdots + ab^{q-2}+b^{q-1}). &fg=000000$

$latex \displaystyle a^{q-1} + a^{q-2}b + \cdots + ab^{q-2} + b^{q-1} &fg=000000$

The above version 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.

Open Problems

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.