Euclid Strikes Back

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.