Easy to guess, hard to prove

Suppose you’re waiting for a friend and you have nothing to do. After a few minutes of boredom you pick up a pencil and some scrap paper. You start listing the prime numbers.

2, 3, 5, 7, 11, 13, 17,19, 23, 29, 31, …

Next you write down the forward differences, subtracting each number in the sequence from the one that follows it.

1, 2, 2, 4, 2, 4, 2, 4, …

Your friend is running late and so you repeat the process starting with the sequence you just created.

1, 0, 2, -2, 2, -2, 2, 2, 4, …

Hmm. That time you got a negative number in the list. You’re just doodling and you don’t want to think too hard, so you decide you’ll ignore signs and just write down the absolute values of the differences. So you erase the negative sign and take differences again.

1, 2, 0, 0, 0, 0, 0, 2, …

Your friend is quite late, so you keep doing this some more. After a while you notice that every new sequence has started with 1. Will every sequence start with 1? That’s Gilbreath’s conjecture, named after Norman Gilbreath who asked the question in 1958. I ran across the conjecture in The Math Book by Clifford Pickover. Gilbreath wasn’t the first to notice this pattern. François Proth noticed it in 1878 and published an incorrect proof of the conjecture.

Gilbreath’s conjecture has been verified for the first several billion sequences, but nobody has proved that every sequence will start with 1. Paul Erdős speculated that Gilbreath’s conjecture is true but it would be 200 years before anyone could prove it. I find Erdős’s conjecture more interesting than Gilbreath’s conjecture.

Here’s what I imagine that Erdős had in mind. While the process Gilbreath created is very simple, it is also a strange thing to study. It’s not the kind of thing that people have proven theorems about. No one knows how to approach the problem. There are far more complicated problems in the mainstream of mathematics that will probably be resolved sooner because they are related to previously solved problems and researchers have some idea where to start working on them.

Other posts on number theory:

Other posts on proofs:

8 thoughts on “Easy to guess, hard to prove

  1. Yes, “a strange thing to study”, indeed. Hard to prove, but who cares?

    I usually have a great deal of interest in mathematical curiosities. This one… nah. There are far more complicated problems in the mainstream of mathematics that will probably be resolved sooner, not just because they are related to previously solved problems, but also because they matter more.

  2. Its easy to disregard problems like this a curiosities, but you never know if techniques developed while attempting to prove this could be useful for more “important” problems.

  3. As for “who cares”, it’s tied to primes, so it might be yet another potential handle on the Riemann Hypothesis… which is one of those million-dollar questions from the Clay Institute. (Heck, DARPA will even give you a grant to look into the RH if you think you have an interesting handle on it; it’s on their list of 23 big problems, too.)

  4. Slight error in (the transcription of) your calculation:
    where you say “Hmm. That time you got a negative number in the list”, there should be at least another negative number there– 2,4,2,4,2… differences would be 2,-2,2,-2,…

Leave a Reply

Your email address will not be published. Required fields are marked *