Skip to content

Lifting The Edge

May 17, 2014


A simple but powerful lemma: LTE

220px-Preda_Mihailescu_vor_Tafel

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 {\mathsf{NP}} versus {\mathsf{P}}, 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.

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ă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 {3^{2}-2^{3} = 1}. 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

\displaystyle  x^{p}-y^{q} = 1

where {p,q} are primes and {x,y} are integers? He conjectured no. This is the problem that Mihăilescu solved: proving that there are no other solutions.

The Edge

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

\displaystyle  \ln (x^{p}) = \ln( y^{q} + 1).

If {y} is very large, then

\displaystyle  p\ln x = q\ln y + \epsilon,

where the error term {\epsilon} is very small. Now assume that {p} and {q} 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

\displaystyle  \exp(\exp(\exp(\exp(730))))

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.

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 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 {a^{q} \equiv b^{q} \bmod q} where {q} is a prime. Then

\displaystyle  a^{q} \equiv b^{q} \bmod q^{2}.

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, {a \equiv b \bmod q}. Now factor

\displaystyle  a^{q}-b^{q} = (a-b)(a^{q-1} + a^{q-2}b + \cdots + ab^{q-2}+b^{q-1}).

But

\displaystyle  a^{q-1} + a^{q-2}b + \cdots + ab^{q-2} + b^{q-1}

has {q} identical terms modulo {q}, so it is {0} modulo {q}. This implies that {a^{q}-b^{q}} is divisible by {q^{2}}. \Box

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.

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.

5 Comments leave one →
  1. May 18, 2014 1:22 pm

    LTE=Long Term Evolution of 3G wireless standard. It is not just an advancement in protocols. It provides standards for new modulation scheme. LTE is the way towards 4G.

  2. May 20, 2014 10:02 am

    Pip (Dick and Ken) ask “What other simple tools like LTE might be levers?”

    Historically speaking, a strikingly successful lever is “naturality under pullback.” That is, if some well-defined property is central to the understanding of a complex system, then perhaps that property is preserved when pulled-back onto a simpler system.

    As a concrete example, the eminently practical notion of a symplectic integrator can be regarded as the notion “Hamiltonian flow is a exact symplectomorphism” pulled-back from continuous (geometrical) maps to discrete (computational) maps.

    More broadly, across many STEM disciplines, asking the question “what key notions have a mathematically natural pullback onto simpler systems?” has historically led to fruitful practical advances. And nowadays, the mathematical techniques associated to “naturality and pullback” are formalized, widely taught, and computer-verifiable; this is helpful for young researchers.

    By the way, the Pip-supplied reference to “Interview with Preda Mihăilescu” (ECM Newsletter, June 2008) is wonderfully interesting. Thank you, Pip!

    • May 23, 2014 8:34 am

      Another strikingly successful 20th century series of “pullback levers” begins with the (geometric) idea that a torus is the simplest natural example of a (nontrivial) abelian Lie group … the doubly-periodic Wierstrauss \wp-functions functionally instantiate this abelian group structure … these functions satisfy an elliptic curve relation … thus elliptic curves inherit an abelian group structure … this group structure pulls-back naturally onto the algebraic structure of finite field … and now from the simplest geometric beginnings our understanding has leveraged itself, by a sequence of natural pullbacks, onto deep-yet-practical topics in elliptic curve cryptography.

      Plenty of on-line notes survey this sequence of pullback levers; Michael Travis “Elliptic curves over \mathbb{C} is one example (of dozens).

  3. May 21, 2014 10:00 am

    inspiring story! youre always so great at finding and highlighting em! someone should interview you!😎

Trackbacks

  1. Scurtissime | Isarlâk

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s