Skip to content

Euclid Strikes Back

August 16, 2013


An application of Euclid’s famous proof there are an infinite number of primes

Unknown

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 {X} and {Y}. Box {X} contains some positive integer {x}, and as you might guess, box {Y} contains some positive integer {y}. 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 {L}. 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 {\dots} 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 {x}, Bob can pick any positive {a,b} he wishes and manipulate the box so that {x} becomes {ax+b}. Of course he cannot see what the box now contains—its value remains hidden from him. But he knows that no matter what {x} was, it is now {ax+b}.

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:

box

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 {x} by {ax+b} and {y} by {cy+d}. Then Alice could select {x} and {y} so that {ax+b} and {cy+d} are not relatively prime. So the problem is impossible. If he had some randomness, he thinks, then perhaps {\dots} 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 {X} and {Y}, but a whole collection of pairs of boxes

\displaystyle  X_{1},Y_{1}, \dots, X_{m},Y_{m}.

Each {X_{i}} contains the same secret {x}, and each {Y_{i}} contains the same {y}. Now Bob’s task is to apply linear maps to each box, allowing different maps for different boxes, so that for {99\%} of the respective box pairs they are relatively prime. That is, for most {i} the integers in the boxes

\displaystyle  X_{i},Y_{i}

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 {x} be an integer, let {t>0}, and take

\displaystyle  M = \Pi_{p < t} \ p.

Then any prime divisor of {Mx + 1} is at least {t}.

Do you see the rest of the solution?

Bob’s Solution

Lemma: Let {I} be an arithmetic progression {a + ib}: {i = 0} to {k-1}, and let {p} be a prime that does not divide {b}. Then at most {1 + \left\lfloor\frac{k}{p} \right\rfloor} members of {I} are multiples of {p}

Note that the case {b = 1} defines an interval.

Proof: Suppose {a+ib} and {a+jb} are multiples of {p} with {j - i < p}. Then there are integers {u,v} with {u < v} such that {up = a+ib} and {vp = a+jb}. Then {(v-u)p = (j-i)b}. But this is impossible since {p} does not divide {b}, and {p} cannot divide {j - i} since {j - i < p}. It follows that for any value {j} such that {a+jb} is a multiple of {p}, the {p-1} preceding members of {I} and the {p-1} following members of {I} (if they exist) cannot be multiples of {p}. This proves the lemma. \Box

Theorem: Let {x,y} be distinct positive integers bounded by {L}. Let

\displaystyle  M = \Pi_{p < \log L} \ p.

Then for sufficiently large {c > 0}, {M(x+\alpha) + 1} and {M(y+\beta) + 1} are relatively prime for most pairs {\alpha,\beta} in the interval {[\log L, c\log L]}.

Proof: It suffices to fix any {\alpha}—indeed, Bob can win by taking {\alpha = 0} and mapping {x} in each {X_i} box to the same value {Mx + 1}. We need to count how many {\beta} are “bad.” Here `bad’ means that there is a prime that divides both {M(x+\alpha) + 1} and {M(y+\beta) + 1}.

By Euclid’s lemma, all prime divisors of {w = M(x+\alpha)+1} must be at least {\log L}. So there are at most

\displaystyle  r = \log L/\log\log L

of them. This follows since if there are {r} such primes then clearly

\displaystyle  (\log x)^{r} \le x \le L,

and the claim follows by taking logarithms.

Let these primes be {p_{1},\dots,p_{r}}. As {\beta} varies we want to count how many times one of these primes divides {M(y+\beta)+1}. Regardless of what {y} is, it is fixed, so with {a = My + 1} we have the arithmetic progression

\displaystyle  I = a + M\beta: \log L \leq \beta \leq c\log L.

It follows by Bob’s lemma that {p_{i}} divides {M(y+\beta)+1} for at most

\displaystyle  \lceil \frac{| I |}{p_{i}} \rceil

values of {\beta}. So the total number of bad {\beta} values is at most

\displaystyle  \sum_{i} 1 + \frac{| I |}{p_{i}}.

This is upper-bounded by

\displaystyle  r + | I | \frac {r}{\log L} \le r + cr \le (c+1)\frac{\log L}{\log\log L} = o(|I|).

Thus only a small fraction of the interval {I} gives bad {\beta} values, and so most pairs are relatively prime. Note also that the number {m \sim c\log L} of pairs needed is linear in the number of digits in the bound on the values. \Box

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.

About these ads
10 Comments leave one →
  1. August 16, 2013 11:14 am

    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.

    • rjlipton permalink*
      August 16, 2013 11:18 am

      D. Eppstein

      But Alice wants MOST of the pairs to co-prime? No.

      • August 16, 2013 2:41 pm

        How is getting all of the pairs co-prime a failure to get most of them co-prime?

  2. mmmmm permalink
    August 16, 2013 5:59 pm

    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).

  3. August 17, 2013 3:24 am

    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.

    • rjlipton permalink*
      August 17, 2013 9:40 am

      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?

      • August 18, 2013 10:40 am

        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.

Trackbacks

  1. From Proofs to Prime Numbers: Math Blogs on WordPress.com — Blog — WordPress.com
  2. math | electericity
  3. Math Blog Snippet | the Cyclic Grizzly

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 1,562 other followers