Deferring or avoiding randomization
|
| Great Discoveries in STEM source |
Claude Bachet de Méziriac was a French mathematician of the early 1600s. He is the first person we know to have posed and solved the problem, given relatively prime (also called coprime) integers 
and 
, of finding integers 
and 
such that 
.
Today we revisit some questions about generating coprime pairs deterministically.
Étienne Bézout later observed that for all cases of 
there are integers 
such that 
. The convention of naming this identity for Bézout now extends to the 
case, so that and are called the Bézout coefficients of and . If we count 
and 
as being coprime with every integer (including zero) then 
are coprime if and only if making exist.
Bachet de Méziriac is known mostly for two books. One in 1612 was a compilation whose title translates to Pleasant and Delectable Problems Fashioned By Numbers and which inspired subsequent books on mathematical recreations. The other was his translation of the Arithmetica of Diophantus from Greek into Latin. It made a marginal contribution to number theory: it contributed the margin in which Pierre Fermat wrote the statement of his famous theorem.
Coprime Pairs
Say we are given a fairly large integer 
and wish to find coprime pairs near it. It is of course easier to find them by random guessing than to find primes. The primes up to have density only about 
but the chance of finding a coprime pair approaches about 61%. More exactly it approaches 
which is the reciprocal of 
.
The connection extends to other values of the zeta function. Let us take the naturally-extended Bachet condition to be the definition of 
integers 
being relatively prime: there exist integers 
such that 
. The probability that drawing each 
from ![{[N]}](https://s0.wp.com/latex.php?latex=%7B%5BN%5D%7D&bg=ffffff&fg=000000&s=0&c=20201002)
uniformly at random (with replacement) satisfies this condition approaches 
as 
.
We can use Bachet’s condition to extend the logic for 
. We might have no idea what it should mean for one number 
to be “coprime” but 
is satisfiable for integer 
only when 
and 
. The probability of drawing from goes to zero, which is consonant with the series for 
diverging to 
.
For 
it is less clear whether to apply the convention that an empty sum is zero. This would be consonant with the literal reading of “
” as 
but not with the analytic continuation 
. The latter would give 
as a “probability.” We wonder idly whether Bachet’s condition helps toward a liberalized interpretation that would further give a sensible relation to 
for fractional real values of 
and then to complex ones.
But we digress. We want to generate coprime pairs efficiently and deterministically without any guessing.
Finding Primes and Coprime Pairs
The PolyMath8 project on “Bounded gaps between primes” generated many interesting sub-projects. Some of them address the issue that if is in the middle of a large gap between primes then simple search up or down will fail. We have blogged about the discovery that searches for primes to use in RSA keys follow the same trajectory to find the same primes so often that simple 
calls break many keys.
There are various ways to weaken the problem. We can ask to find an integer near that is a prime power. We can ask to find, say, a set 
of 100 numbers near such that at least 67 of them are prime. Note that we do not allow randomness in the solution to find .
In general we want to improve randomized assertions of the form, “there is probability at least 
of finding 
with property 
” to “we build a relatively small set of which at least 
of the members have property .” We can then decide whether drawing randomly from or searching through is a better policy, informed by factors such as the relative cost of testing .
We have before talked about the W-trick of number theory. It maps 
where 
is the product of all primes below a small threshold 
and is coprime to (often just 
). The inverse image of the primes under 
is free of biases modulo 
.
This comment by Ben Green neatly expresses the analytical motivation, as does section 4 of this paper. The freedom from bias simplifies reasoning about the distribution of primes while 
preserves arithmetic progressions. We are interested in using it and similar tricks to create sets as above—or sets with many coprime pairs—in conjunction with other assumptions.
Making Numbers Coprime Again
Here is our first new situation and problem. Suppose that we have two boxes that contain the numbers and secretly. We want to make them into co-prime numbers. We are allowed to map to 
and map to 
. But we cannot see the values of and .
This is not easy it seems. We can weaken the goal a bit: Give a series of translations 
and 
so that for most of them the numbers map to co-prime numbers. Note we do not allow randomness in the solution.
However, suppose that we can compute the sum 
exactly. Then there is a method for solving this problem that is quite simple:
Pick a prime 
that is fixed. Then find 
so that 
. Add 
to 
and add 
to 
. This makes them co-prime.
The reason is simple. Note the two numbers are now
Let 
divide both of these numbers. Since both are positive must be a prime—the original and could have been both zero. Now must divide 
. This implies that is equal to 
. And so must have originally divided both and . So we can see now that if we move and to 
and it is the case that for most 
in say ![{[1,10]}](https://s0.wp.com/latex.php?latex=%7B%5B1%2C10%5D%7D&bg=ffffff&fg=000000&s=0&c=20201002)
the numbers are co-prime if we select 
.
Modeling Two-of-Three Coprimality
In our second situation, we are implicitly given a pair of numbers 
for which we cannot determine their values. We can, however, get some partial information about them and can change them to 
in a certain controlled fashion. This still may not be enough to guarantee that and 
are coprime.
So we apply our weakened goal: We want to generate a set of pairs 
such that at least two-thirds of the pairs in are co-prime. We want the method of generating the pairs to be easy to compute and deterministic. We will do this with 
but hint at what is needed to expand to larger sets .
Definition 1 The “2-of-3 model” problem is the following. We assume that we have two natural numbers 
and 
, but we have no idea what their values are. We do know the following:
-
The value of an even number
which is fixed.
-
The value of the sum
.
-
There is
so that 
and a 
so that 
.
Finally we can replace 
by 
for 
. The goal is to find
for 
so that for at least two values of 
the values
are co-prime. Moreover, we want to be able to find the values 
in polynomial time.
We’ve chosen some specific constants and terms but the pattern is meant to be generalizable. For the above settings we prove:
Theorem 2 There is a polynomial time algorithm that solves the 2-of-3 model problem.
Proof: Find a prime so that 
and 
is divisible by 
. This is possible since there are primes in such an arithmetic progression. Now we claim that there is a so that
Moreover we can find this in polynomial time. Note that exists since
which is equivalent to
But 
is divisible by since divides . Thus exists and is easy to compute. Now let 
and 
be so that
Suppose that 
and 
have a prime that divides both. Clearly must be odd and thus it must divide and so 
. But for most splits of we get that this is impossible. 
Open Problems
What more can be said about these weaker problems of generating primes and coprime pairs?
The above results are by Dick and this post marks his return after the heart surgery six weeks ago.
The upcoming “Golden STOC” in Los Angeles will be wrapped in a 5-day TheoryFest along lines of last year’s. It will include an inaugural meeting of the TCS Women initiative. Information on travel scholarships to the TheoryFest for female graduate students. We have noticed some recent revived interest in our post a year ago on gender bias, and there is also our theme that CS has seen over its history numerous “Absolute Firsts” for women: “first X” rather than “first woman X.”
Like this:
Like Loading...
Related
Note that Bézout’s identity is (usually) called [Théorème de Bachet-Bézout](https://fr.wikipedia.org/wiki/Th%C3%A9or%C3%A8me_de_Bachet-B%C3%A9zout) in French.
I think that the problem of finding solutions to ax+by=1 and its solution goes back at least to Qin Jiushao’s “Mathematical Treatise in Nine Chapters” (1247). From Encyclopedia Britannica (https://www.britannica.com/science/East-Asian-mathematics): “His solution is known today as the Chinese remainder theorem. He dealt with the case when moduli are relatively prime, and he then reduced the case when they are not by first eliminating common factors. The first case is easily solved when x can be found that satisfies the congruence xa ≡ 1 (mod b), a and b being two given relatively prime numbers (suppose a < b). Qin gave an algorithm for this, using a sequence of quotients in searching for the greatest common divisor of a and b, which is also the sequence of convergents for the continued fraction for b/a. Having them, he was then able to compute x."
This was a very interesting post. Best wishes to Prof. Lipton.
In fact, the problem of finding solutions to ax + by = c goes back at least to Aryabhata in the 5th century, who posed and solved it. Many later Indian mathematicians elaborated, extended and refined this method (called kuṭṭaka). You can read more about it here: https://en.wikipedia.org/w/index.php?title=Ku%E1%B9%AD%E1%B9%ADaka&oldid=836706571
There’s an entire robust mathematical tradition of over a 1000 years before the early 1600s that this post starts with; it would be nice if history of mathematics did not ignore Indian / Chinese / other mathematical cultures around the world.