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 that
and
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 .
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.
having finitely many real solutions, all of them irrational)
(take
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