Euclid Strikes Back
An application of Euclid’s famous proof there are an infinite number of primes
Euclid of Alexandria, Euclid for short, composed one of the most influential books ever written on mathematics. His Elements served as the textbook for geometry for almost two thousand years. Elements also included basic theorems on what we call number theory today. His proof that there are arbitrarily large primes is a gem.
Today I plan to use Euclid’s gem to solve a “puzzle” that I think you may like.
The puzzle arose in work that I have been doing on another problem, but it seems interesting in its own right. So here is the puzzle, and I will sketch the solution. There may be a much simpler solution, and I welcome any of you who have better ideas.
Alice’s Puzzle
Suppose Alice gives Bob two boxes labelled respectively and . Box contains some positive integer , and as you might guess, box contains some positive integer . Bob cannot open either box to see what integer it holds. Bob can shake the boxes, or hold them up to a bright light, but there is no way he can discover what they contain.
Alice says to Bob: The integers in the boxes are both less than . I want you to make the integers in the boxes relatively prime. Bob looks confused and says: But if I cannot see them, how can I make them relatively prime? Why, they could both be the same number—? Alice smiles and adds: Of course. I will allow you to do one thing to each box. You may Alice explains that each box has some special hidden knobs, and these allow Bob to change the value in the box by any linear map. She shows Bob how to use the knobs—we will skip those mechanical details. Mathematically: if a box contains , Bob can pick any positive he wishes and manipulate the box so that becomes . Of course he cannot see what the box now contains—its value remains hidden from him. But he knows that no matter what was, it is now .
Alice adds one more condition: I want your solution to be deterministic. No random coins. I must know the strategy that you will use. Good luck, she adds with a smile.
Bob’s Answer
Bob looks at one of the boxes carefully:
Then he soon smiles himself. Alice, thanks for the puzzle, but it is impossible. There is no solution, and I can prove it.
He explains why the problem is impossible. Bob is right. Suppose that his strategy replaced by and by . Then Alice could select and so that and are not relatively prime. So the problem is impossible. If he had some randomness, he thinks, then perhaps But Alice wants him to have a fixed strategy, so her puzzle is impossible.
Alice Relents
Alice nods and says that Bob is exactly right. Then she weakens what Bob must do. Alice gives Bob not two boxes labelled and , but a whole collection of pairs of boxes
Each contains the same secret , and each contains the same . Now Bob’s task is to apply linear maps to each box, allowing different maps for different boxes, so that for of the respective box pairs they are relatively prime. That is, for most the integers in the boxes
must be relatively prime. Again Bob’s strategy must be known to Alice, no randomness allowed.
Bob Wins
After some thinking, Bob smiles and sees that he can use Euclid’s old argument to solve Alice’s puzzle. In particular, he notices that the following is easy to prove:
Lemma: Let be an integer, let , and take
Then any prime divisor of is at least .
Do you see the rest of the solution?
Bob’s Solution
Lemma: Let be an arithmetic progression : to , and let be a prime that does not divide . Then at most members of are multiples of
Note that the case defines an interval.
Proof: Suppose and are multiples of with . Then there are integers with such that and . Then . But this is impossible since does not divide , and cannot divide since . It follows that for any value such that is a multiple of , the preceding members of and the following members of (if they exist) cannot be multiples of . This proves the lemma.
Theorem: Let be distinct positive integers bounded by . Let
Then for sufficiently large , and are relatively prime for most pairs in the interval .
Proof: It suffices to fix any —indeed, Bob can win by taking and mapping in each box to the same value . We need to count how many are “bad.” Here `bad’ means that there is a prime that divides both and .
By Euclid’s lemma, all prime divisors of must be at least . So there are at most
of them. This follows since if there are such primes then clearly
and the claim follows by taking logarithms.
Let these primes be . As varies we want to count how many times one of these primes divides . Regardless of what is, it is fixed, so with we have the arithmetic progression
It follows by Bob’s lemma that divides for at most
values of . So the total number of bad values is at most
This is upper-bounded by
Thus only a small fraction of the interval gives bad values, and so most pairs are relatively prime. Note also that the number of pairs needed is linear in the number of digits in the bound on the values.
Open Problems
This idea can be extended to triples of boxes. Now Bob must make them pairwise relatively prime. I had an application to a complexity theory problem, in which it was needed to avoid randomness. In my application, the solution is being done by a deterministic machine. Perhaps there are other uses of this simple trick. I note that it is quite close to the “W-trick” described by Terence Tao in relation to Yitang Zhang’s advance on the twin-prime conjecture, and sketched by Ben Green in a comment here.
I don’t see why you think the deterministic version is impossible. There exist arbitrarily long arithmetic progressions of primes. Choose $a$ and $b$ so that the map $ax+b$ takes $x=0,1,\dots L-1$ to one progression, and choose $c$ and $d$ so that the map $cy+d$ takes $y=0,1,\dots L-1$ to a different progression. Then $ax+b$ and $cx+d$ are different prime numbers, so they are necessarily relatively prime.
D. Eppstein
But Alice wants MOST of the pairs to co-prime? No.
How is getting all of the pairs co-prime a failure to get most of them co-prime?
Take:
ax+b = L! x + 1
cy+d = y
since x and y are both at most L, y and L! x + 1 cannot have a common factor (if this factor is r <= y then it divides L! and so does not divide L! x + 1).
I agree with David and mmmmm that the original problem already has a solution, in fact, you gave a huge hint by Euclid, just multiply x with all the primes at most L and add 1, leaving y unchanged works. Maybe you missed this as the multiplier would be exponentially large in L, while in your application I assume you need it to be poly(L) or so.
YES
I needed the values to remain small. Sorry for that missing point. Thanks for all the comments. But with the limit on size i think the puzzle is okay. Or?
If p does not divide a, then there is a value of x from [1,p] for which ax+b is divisible by p. This means that if Bob makes ax+b and cy+d, then ac must be divisible by every prime which is less than L to ensure that they are relatively primes. So yes, either a or c must be big in the original puzzle.