Can We Solve It?

James Maynard is a number theorist. He attended Cambridge as an undergrad and then moved to do his grad work at Oxford at Balliol College. He is now a professor at Oxford. He is one of the world experts on prime density type theorems.

Today, since it is Friday, I thought we would discuss a timely idea of Maynard. Not an idea about time complexity or time in physics, but involving the use of time.

Decimal Digits

No it’s not a technical idea of his. He has had many ideas, for instance, that shed light on the beautiful structure of primes. For example, he proved in 2016 that

Theorem 1 For each decimal digit , there are infinitely many prime numbers that do not have in their decimal expansion.

This is not known for all digit systems: For binary, our favorite system as complexity theorists, this is still an open problem. Of course a binary prime with only ‘s must be of the form:

where must be a prime.

These are the famous Mersenne primes named for Marin Mersenne. The largest prime is as of today—at least I believe this is true. For further discussion, see a 2001 paper by Samuel Wagstaff titled, “Prime Numbers with a Fixed Number of One Bits or Zero Bits in Their Binary Representation.”

Maynard’s Friday Rule

Maynard’s idea is based on his quest to understand whether known techniques can solve some problem. Of course the best way to understand this is to solve the problem. His above theorem is a perfect example of this. In the abstract he says:

The proof is an application of the Hardy-Littlewood circle method to a binary problem, and rests on obtaining suitable `Type I’ and `Type II’ arithmetic information for use in Harman’s sieve to control the minor arcs.

The proof may be based on known techniques, but is still very hard. He needs pages to make it work.

Maynard’s idea is to set aside time to remind himself why existing techniques have not worked against math’s biggest open problems.

I often spend Friday afternoons just thinking about trying to directly attack some famous problem. This is much less because I think there’s a realistic way of solving the problem, but more because I think it’s important for me to understand where plausible techniques fail.

One can imagine that he had a Friday afternoon think. During it he asked himself:

Suppose I try to show that there are primes without some particular digit. This is a density type theorem. Well could I use the Hardy-Littlewood method. But it cannot work because Wait here is a possible way around the roadblock. Hmmm.

Maybe he looked at Terence Tao’s blog post on this very issue. It helped that Maynard is an expert on the Hardy-Littlewood method, but perhaps thinking why it could not work helped him figure out how it could work.

Our Friday Rule

Today is Friday, so I though what should I think about? What problems and what techniques? Here is a possible example. Let’s look at the On Lower Bounds for the Separating Word Problem.

An approach is based on the following. Let be the set of all degree polynomials, with coefficients . Let be a constant. Our hypothesis H is: For every polynomial in , there is some prime , so that for some

How small can be so that H is true? What are the methods that we should think about? What methods can we see that cannot prove H? Can we, for example, show that we can use a random argument? Can we should that they are not enough primes in the range? Hmmm

Open Problems

Do you like Maynard’s Friday rule? What problems and what techniques would you think about?