# Solving Diophantine Equations the Easy Way

* Solving Diophantine equations with mixed rationals and reals *

Derrick Lehmer was an early computational number theorist and, during his long career, both proved wonderful theorems and made amazing special purpose computers. He used his machines, for one, to factor the largest numbers possible at the time.

Today I planned to talk about an approach to integer factorization–a problem that Lehmer worked on his whole life. The method is a refinement of an idea I discussed in an earlier post. However, there is an issue that came up while writing that post, that I want to talk about first; I will post shortly on the whole factoring idea. The question concerns solving *mixed Diophantine equations*. More on these later.

I was honored to meet Lehmer, in 1979, when I was on the faculty at Berkeley. One day Manny Blum and I went up to Lehmer’s office, where we had a wonderful chat on a wide range of topics.

One topic we discussed at length was the production of random numbers. Lehmer had thought quite deeply about the issues involved in the creation of “truly” random numbers. The bottom line of the conversation was the claim–well argued by Lehmer–that it is extremely hard to generate truly random numbers, even with physical devices.

It was a long discussion, but here is one of his insights, which I still explain in my lectures to students, whenever we discuss randomized algorithms. Suppose we try to use the randomness that appears to be inherent in radioactive decay. We use a Geiger counter to count the number of beta and gamma particles emitted by a low-grade radioactive source. Every now and then we stop the counter and read off the low order bit. The claim, Manny and I believed, was that this bit would be random.

Derrick smiled and explained that our idea was flawed–in many ways. He pointed out that it is easy to make a counter, by design or by error, that when you stop it, tends to stop with an even count rather than an odd count. This is true, especially, if the counter is “spinning” at a high rate. Obviously, such a counter would give very biased bits. Our answer was to have the random process flip the counter at a much slower rate and, we stated, this would mean that when we stopped the counter it would likely be unchanging. However, Derrick said that then the rate of getting random bits would be very slow. And so on.

Before we talk about mixed Diophantine equations, I thought you might like to know about Lehmer’s machines. One of his most interesting special purpose machines was made of bicycle parts, an electric motor, a light, and a photodetector; all to solve Diophantine equations.

The machine had several wheels that rotated at different speeds and, holes had been cut into the wheels, allowing light to potentially shine through at special positions. As the wheels rotated, if all the holes were aligned, then the light got through to the photodetector–and this stopped the machine. The wheels would be turned back slowly, by hand, so that the exact point where they were all aligned was found.

Lehmer used his machine to solve certain sieve problems, which yielded solutions to Diophantine equations. The advantage of the machine was that the electric motor could turn the wheels at a high speed, which allowed a large number of combinations to be tried per second.

The device was relatively cheap, and Lehmer could run it day and night: after all it was his own machine. With this device he could vastly out perform computers of the day, both in speed and definitely in price-performance. There was a time when it was the state of the art in factoring.

** Mixed Diophantine Equations **

I have an approach to factoring based on finding certain special matrices. The properties that these matrices need to satisfy can be stated as finding the solution to Diophantine equations. I will discuss today, a relaxation that may make the required equations easier to solve. Also the questions that arise seem to have independent interest.

In general a Diophantine equation is

where are restricted to be integers (or sometimes rationals) and is a polynomial over the integers. Finding a solution over the integers is well known to be undecidable, and even special cases can be extremely difficult to resolve. Finding a solution over the rationals is a long-standing open problem, by the way.

We are interested in the following simpler question: Suppose that

has a solution over the complex numbers. When does that imply that there is another solution so that are rationals? Of course, the interesting case is when .

The question is: does such a solution always exist? If it does, then that has potential to greatly simplify the approach I have to factoring.

There is a simple counterexample: Consider the polynomial . Then, it clearly has solutions, but no solution is possible with rational.

** One Equation Case **

The problem with the simple counterexample, is that the polynomial does not depend on . A natural conjecture is the following: Suppose depends on . Then if it has a solution it has a solution with a rational.

Let’s examine this, by writing the equation in the following form:

for the case when has degree . Let’s assume that is not identically . For that, let’s simply select as an integer so that is not zero. Then, there is a so that .

Theorem:Suppose that depends on the variable . Then, there are integers and a so that

The proof is the same as the example we just went over. Note, this result is essentially just the Fundamental Theorem of Algebra.

** One Equation and One Inequation Case **

A much more interesting problem arises with multiple equations.

As usual is the absolute value of . Also for a vector , let denote the value

Note, .

The goal of this section is to prove the following theorem: (This is a joint result with Subrahmanyam Kalyanasundaram and Farbod Shokrieh.)

Theorem:Suppose that and are polynomials, and that depends on the variable . Also assume that there are reals so that and . Then, there are rationals and a so thatand

We first need a classic lemma:

Lemma:Let the polynomial equalwhere , and the polynomial equal

Suppose that . Then, for any , there is an so that if , then there exists a so that and .

Lemma:Suppose that the polynomial is equal to

where and each is a polynomial, and . Then, for any , there is an so that if and and , then there exists a so that and .

*Proof:* Since , this follows from the previous lemma, by dividing by the lead term.

Now we will prove the main theorem:

*Proof:* First, the function is such that for any there is an so that

This is, of course, just uniform continuity of the polynomial function.

Second, since is a polynomial that depends on , by the lemma, for any , there is an so that

Let . Select small enough so that (1) holds for . Now select so that it is smaller than , and (2) holds for .

Since the rationals are dense, for there is an all rationals so that . By (2) there is a so that and also . Note, that . Thus, by (1)

This implies that .

** General Case **

What we really would like is a generalization that could handle several equations and one inequation. Note, one inequation is the same as many. The condition

is the same as

The theorem we need to help solve the factoring problem would look like our theorem, but would allow several equations and one inequation.

Suppose that and . Let for and be polynomials. Also assume that for some real ,

Then, there are rationals and a so that

and

provided is true.

The key question is what is the property ? In the case of , was that the polynomial depended on the single variable . I would imagine that now the right property is a stronger notion of dependence? What is it?

** Open Problems **

The main open problem is to find the right statement of the general theorem and prove it. That what should be?

Are there some interesting applications of this ability to “almost” solve Diophantine in rationals? What about a similar result that holds over the complex numbers?

One potential application that comes to mind is the area of solutions to economic or game theoretic problems. In order to apply to these problems the value of the variable must be restricted to be real also. This does not seem possible with the technology that we have so far. Thus, an important additional direction is to try to prove a theorem, even with one equation and one inequation, that allows to stay real. I believe that such a theorem could be quite interesting.

The story about Lehmer’s machine is fascinating. Did he ever publish a paper? Sounds like he could have published something about the machine’s output…

I recall the machine was featured in Beiler’s “Recreations in the Theory of Numbers” (it’s online). I vaguely remember Beiler’s detailed story of visiting, along with his son, the machine for the purpose of factoring some large number. The description of the machine as it stands here is very similar to what Beiler tells, except Beiler refers to the machine to a “factoring machine”, so I may or may not be talking about the right machine. But it was Lehmer’s nonetheless.

In the context of Lehmer’s photo-mechanical device, Shamir’s TWINKLE and Shamir and Tromer’s TWIRL are worth mentioning.

Regarding your open problems, I suggest you talk to an algebraic geometer. You basically have an algebraic set defined by and an open subset of it defined by You want to know under which conditions the projection of to the first coordinates has a rational point. In such a generality this is probably hopeless, but probably when is much smaller than and some nondegeneracy conditions holding, you might have a chance…

In the case of reals, the situation is even harder, as you can encode any number of equations by just one equation (take the sum of squares), so it must be easy to construct counterexamples.

(take having finitely many real solutions, all of them irrational)

I’d like to point out that Lehmer’s mechanical methods of factoring were anticipated by the Frenchman Carissan, who not only built a similar machine before Lehmer, but also used it successfully to factor numbers. Strangely enough his work is hardly known.

See, for example,

http://www.cs.uwaterloo.ca/~shallit/Papers/carissan.html

http://www.cs.uwaterloo.ca/~shallit/Talks/ams.ps

http://www.springerlink.com/content/r2534661k1747253/

I have encountered two expresions in an equation which I am assured can only be solved via Diophantine linear equation methods. (Simultaneous equations do not) The expressions are :-

(3x + 43) – (5y +37) = 0

Can anyone show me how this is done step by step please?

(I happen to know that each expression = 67 and x = 8 and y = 6)

Harry at

harry.schneider@btinternet.com