Skip to content

Can We Solve It?

October 23, 2020


It is a Friday

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 {d}, there are infinitely many prime numbers that do not have {d} 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 {1}‘s must be of the form:

\displaystyle  2^{p} - 1 = 111\dots 1,

where {p} must be a prime.

These are the famous Mersenne primes named for Marin Mersenne. The largest prime is {2^{82,589,933} - 1} 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 {70} 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 {\dots} 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 {F(n)} be the set of all {f(x)} degree {n} polynomials, with coefficients {-1,0,+1}. Let {\epsilon>0} be a constant. Our hypothesis H{(\epsilon)} is: For every polynomial {f(x)} in {F(n)}, there is some prime {p \le Cn^{\epsilon}}, so that for some {1 \le k \le n}

\displaystyle  f(k) \not\equiv 0 \bmod p.

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

Open Problems

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

6 Comments leave one →
  1. Igor permalink
    October 23, 2020 5:02 pm

    This is probably a naive question, but is this related to fractions that don’t have certain digits in their decimal expansion? The more general question is to find fractions such that the density of each digit in the decimal expansion doesn’t converge to 1/10.

  2. PandaItchpress permalink
    October 23, 2020 6:27 pm

    I don’t like his friday rule. It just looks like another very famous mathematician who wants to take lunch breaks for hard problems. Bunch of jokers.

    • PandaItchpress permalink
      October 25, 2020 11:33 pm

      Why even try if they know they cant solve this way? What kind of moral compass does this hold? Isn’t it funny?

  3. Frank Vega permalink
    October 23, 2020 7:00 pm

    People who think they can are the one who really can!!! I have had rough week due to COVID-19. Right now, my mind and heart are in this:

    Sometimes praying, sometimes with bad mood because of my situation, but most of the time with hope in the near future!!!

    Best,
    Frank

  4. PandaItchpress permalink
    October 23, 2020 11:41 pm

    Nice trick to censor and repost comments at a later date that does not show up in sidebar.

  5. October 24, 2020 5:12 am

    “Can we should that they are not enough” -> Can we show that there are not enough

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 )

Google photo

You are commenting using your Google 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 )

Connecting to %s