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
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 that
We first need a classic lemma:
Lemma: Let the polynomial equal
where , 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 .
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
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?
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.