Lessons from a puzzle about prime numbers

 [ Wikipedia ]

Doron Zeilberger is a famous combinatorial mathematician based at Rutgers. He is noted for actively using computers in research. His computers even get co-authorship credit under the name “Shalosh B. Ekhad,” which is Hebrew for 3B1—a computer that came from building 3, corridor B, room 1 of AT&T Bell Labs.

Today I thought we would talk about a recent joint paper of Zeilberger on Covering Systems.

This paper has one co-author who is human, Anthony Zaleski, also of Rutgers. It starts with a puzzle about beetles on a circular track. The puzzle does not need a computer to solve—though a computerized visualization would make it more enjoyable. It makes several interesting points, points that are distinctly human, and I hope you might enjoy it.

## The Puzzle

They ascribe the puzzle to Jean-Paul Delahaye, who modified Peter Winkler’s writeup of a folk puzzle that Winkler stated about ants.

One places nine beetles on a circular track, where the nine arc distances, measured in meters, between two consecutive beetles are the first nine prime numbers, ${2,3,5,7,11,13,17,19,23}$. The order is arbitrary, and each number appears exactly once as a distance.

At the starting time, each beetle decides randomly whether she would go, traveling at a speed of 1 meter per minute, clockwise or counter-clockwise. When two beetles bump into each other, they immediately do a “U-turn”, i.e. reverse direction. We assume that the size of the beetles is negligible. At the end of ${50}$ minutes, after many collisions, one notices the distances between the new positions of the beetles.

Note that there are two levels of probability: the initial order of the vector of distances and the initial direction of each beetle. Yet after ${50}$ minutes there is a high probability of the distances being exactly the same: the first nine prime numbers. Is this a miracle? What is the probability?

## The Lessons

The point is we have deliberately stated the puzzle to make it harder. The way we stated it is misleading and the following lessons are hints to help solve the puzzle.

• That the arc lengths are prime numbers is unimportant. The puzzle works whether or not the distances between the beetles are prime numbers.

• The probability is ${1}$ that the beetles are at the given positions. There is no chance that they will not arrive at the antipode points. None.

## The Solution

The first observation is that the circular track’s length is

$\displaystyle 2+3+5+7+11+13+17+19+23=100.$

The second is that the probability is ${1}$ that the distances are the same after ${50}$ minutes. Imagine that each beetle carries a flag. Instead of reversing direction when they collide, let the beetles exchange their flags and continue moving as before. Now the flags always are moving in the same direction at the same speed. This means that after ${50}$ minutes the flags are at the antipode position. But the beetles are located at the same places as flags, and so the distances are the same as before. Note, the beetles are each located at the position of some unique flag, but which flag can change many times.

The only constraint is that the distance traveled in ${50}$ minutes divides the length of the circular track. The fact that the distances are primes is never used.

## Open Problems

Zaleski and Zeilberger say:

We point out that very often primes are red herrings. This is definitely the case for covering system, and who knows, perhaps also for the Riemann Hypothesis.

I assume this is a bit tongue in cheek, but their point is valid. Do we miss solutions to problems when we use information that is not really important? How do we decide which information is key and which is redundant? This why I like this puzzle.

February 16, 2020 4:13 pm

On the one hand, the Goldbach’s conjecture has been described as the most difficult problem in the history of Mathematics. This conjecture states that every even integer greater than 2 can be written as the sum of two primes. This is known as the strong Goldbach’s conjecture. The conjecture that all odd numbers greater than 7 are the sum of three odd primes is known today as the weak Goldbach conjecture. A major complexity class is NSPACE(S(n)) for some S(n). We show if the weak Goldbach’s conjecture is true, then the problem PRIMES is not in NSPACE(S(n)) for all S(n) = o(log n). However, if PRIMES is not in NSPACE(S(n)) for all S(n) = o(log n), then the strong Goldbach’s conjecture is true or this has an infinite number of counterexamples. Since Harald Helfgott proved that the weak Goldbach’s conjecture is true, then the strong Goldbach’s conjecture is true or this has an infinite number of counterexamples, where the case of infinite number of counterexamples statistically seems to be unlikely. On the other hand, we have the functional problem FACTORIZATION is not in NSPACE(S(n)) for all S(n) = o(log n), since this uses the decision problem PRIMES as subroutine. However, this implies that the Beal’s conjecture is true. Since the Beal’s conjecture is a generalizations of Fermat’s Last Theorem, then this is also a simple and short proof for that Theorem.

https://zenodo.org/record/3669259

2. February 16, 2020 8:51 pm

On the one hand, the Goldbach’s conjecture has been described as the most difficult problem in the history of Mathematics. This conjecture states that every even integer greater than 2 can be written as the sum of two primes. This is known as the strong Goldbach’s conjecture. The conjecture that all odd numbers greater than 7 are the sum of three odd primes is known today as the weak Goldbach conjecture. A major complexity class is NSPACE(S(n)) for some S(n). We show if the weak Goldbach’s conjecture is true, then the problem PRIMES is not in NSPACE(S(n)) for all S(n) = o(log n). However, if PRIMES is not in NSPACE(S(n)) for all S(n) = o(log n), then the strong Goldbach’s conjecture is true or this has an infinite number of counterexamples. Since Harald Helfgott proved that the weak Goldbach’s conjecture is true, then the strong Goldbach’s conjecture is true or this has an infinite number of counterexamples, where the case of infinite number of counterexamples statistically seems to be unlikely. On the other hand, we have the functional problem FACTORIZATION is not in NSPACE(S(n)) for all S(n) = o(log n), since this uses the decision problem PRIMES as subroutine. However, this implies that the Beal’s conjecture is true. Since the Beal’s conjecture is a generalization of Fermat’s Last Theorem, then this is also a simple and short proof for that Theorem.

https://zenodo.org/record/3669402

3. February 17, 2020 4:49 am

I do believe all these problems in number theory and additive combinatorics should be amenable to an overarching theory. I have no evidence though. Not even a small intuition.

February 17, 2020 9:11 am

“This means that after 50 minutes the flags are at the antipode position”

How does this follow from anything? This is very confusing.

• February 18, 2020 12:18 pm

Another way to picture it is that when two beetles collide, instead of turning around, one climbs over the other and they keep going. As far as having a beetle in position X goes, it makes no difference. Thus after 50 timesteps each beetle has gone halfway around the track. You could get the same relative effect by rotating the track 180 degrees underneath them. So their distances relative to each other are the same at that instant.

5. February 17, 2020 4:25 pm

The Goldbach’s conjecture has been described as the most difficult problem in the history of Mathematics. This conjecture states that every even integer greater than 2 can be written as the sum of two primes. This is known as the strong Goldbach’s conjecture. The conjecture that all odd numbers greater than 7 are the sum of three odd primes is known today as the weak Goldbach conjecture. A major complexity class is NSPACE(S(n)) for some S(n). We show if the weak Goldbach’s conjecture is true, then the problem PRIMES is not in NSPACE(S(n)) for all S(n) = o(log n). However, if PRIMES is not in NSPACE(S(n)) for all S(n) = o(log n), then the strong Goldbach’s conjecture is true or this has an infinite number of counterexamples. Since Harald Helfgott proved that the weak Goldbach’s conjecture is true, then the strong Goldbach’s conjecture is true or this has an infinite number of counterexamples, where the case of infinite number of counterexamples statistically seems to be unlikely. In addition, if PRIMES is not in NSPACE(S(n)) for all S(n) = o(log n), then the Beal’s conjecture is true. Since the Beal’s conjecture is a generalization of Fermat’s Last Theorem, then this is also a simple and short proof for that Theorem.

https://zenodo.org/record/3672036

6. February 17, 2020 6:45 pm

The Goldbach’s conjecture has been described as the most difficult problem in the history of Mathematics. This conjecture states that every even integer greater than 2 can be written as the sum of two primes. This is known as the strong Goldbach’s conjecture. The conjecture that all odd numbers greater than 7 are the sum of three odd primes is known today as the weak Goldbach conjecture. A major complexity class is NSPACE(S(n)) for some S(n). We show if the weak Goldbach’s conjecture is true, then the problem PRIMES is not in NSPACE(S(n)) for all S(n) = o(log n). However, if PRIMES is not in NSPACE(S(n)) for all S(n) = o(log n), then the strong Goldbach’s conjecture is true or this has an infinite number of counterexamples. Since Harald Helfgott proved that the weak Goldbach’s conjecture is true, then the strong Goldbach’s conjecture is true or this has an infinite number of counterexamples, where the case of infinite number of counterexamples statistically seems to be unlikely. In addition, if PRIMES is not in NSPACE(S(n)) for all S(n) = o(log n), then the Beal’s conjecture is true. Since the Beal’s conjecture is a generalization of Fermat’s Last Theorem, then this is also a simple and short proof for that Theorem.

https://zenodo.org/record/3672101

7. February 17, 2020 8:36 pm

Remarkable proofs on Zenodo:

1- Beal’s conjecture proof (this proof is also a partial Goldbach’s conjecture proof):

https://zenodo.org/record/3672135

2- P versus NP proof (this proof is also a L versus NL proof):

https://zenodo.org/record/3660774

Stay hungry, stay foolish…

8. February 21, 2020 11:27 pm

The Goldbach’s conjecture has been described as the most difficult problem in the history of Mathematics. This conjecture states that every even integer greater than 2 can be written as the sum of two primes. This is known as the strong Goldbach’s conjecture. The conjecture that all odd numbers greater than 7 are the sum of three odd primes is known today as the weak Goldbach conjecture. A major complexity class is NSPACE(S(n)) for some S(n). We show if the weak Goldbach’s conjecture is true, then the problem PRIMES is not in NSPACE(S(n)) for all S(n) = o(log n). However, if PRIMES is not in NSPACE(S(n)) for all S(n) = o(log n), then the strong Goldbach’s conjecture is true or this has an infinite number of counterexamples. Since Harald Helfgott proved that the weak Goldbach’s conjecture is true, then the strong Goldbach’s conjecture is true or this has an infinite number of counterexamples, where the case of infinite number of counterexamples statistically seems to be unlikely. In addition, if PRIMES is not in NSPACE(S(n)) for all S(n) = o(log n), then the Beal’s conjecture is true. Since the Beal’s conjecture is a generalization of Fermat’s Last Theorem, then this is also a simple and short proof for that Theorem.

https://zenodo.org/record/3679010