Skip to content

Summing Up the Primes

April 18, 2021
tags: , , , , , , ,


Given the millennia that people have contemplated prime numbers, our continuing ignorance concerning the primes is stultifying—Richard Crandall and Carl Pomerance

Sources: her site, Oberlin interview

Lola Thompson is an Associate Professor of Mathematics at Utrecht University. She did her 2012 PhD thesis, Products of Distinct Cyclotomic Polynomials, under Pomerance at Dartmouth. Of course, she works in number theory. Her thesis is numbered {0} on her publications page.

Today we thought we would highlight a recent result of hers and its connections to complexity theory—indeed, to the realm of {\mathsf{P}} vs. {\mathsf{NP}} and beyond.

The interview linked below her photo at right includes these words:

Even [as an undergrad math major], I didn’t see myself having a future as a mathematician. I think that part of the issue was that I had never seen a female mathematician (none of my math professors at UChicago were women). A major turning point came when my department sent me to the Nebraska Conference for Undergraduate Women In Mathematics (NCUWM). While at NCUWM, I received a huge amount of encouragement. The idea of going to graduate school and becoming a mathematics professor had never occurred to me. It was also extremely helpful for me to see examples of female mathematicians. For the first time, I could imagine myself as a mathematician!

She is paying that forward in mentoring women. See this poster for Utrecht’s hosting of next year’s 4th Women in Numbers – Europe conference, which is affiliated to the Women in Number Theory network. I also like her comments on undergraduate education here.

The paper is joint with Harald Helfgott. The key “players” are the Möbius function and the Mertens function—named for August Möbius and for Franz Mertens.

The Key Players

The Möbius function was invented by Möbius in 1832. It is an important function throughout number theory. It is denoted by {\mu(n)}:

  • {\mu(n) = 1} if n is a square-free positive integer with an even number of prime factors.
  • {\mu(n) = -1} if n is a square-free positive integer with an odd number of prime factors.
  • {\mu(n) = 0} if n has a squared prime factor.

It is multiplicative:

\displaystyle \mu(1) = 1

and

\displaystyle \mu(ab) = \mu(a)\mu(b)

when {a} and {b} are co-prime.

Think of {\mu(n)} as a function that returns {-1,0,+1}, which reveals important information about {n}. The {M(x)} part is the Mertens function, which gives average-like information on the value of {\mu(n)} for {0 \le n \le x}:

\displaystyle M(x) = \sum_{n \le x} \mu(n).

Of course {M(x)/x} is exactly the average value.

A key property of the Möbius function is:

\displaystyle \sum_{d | n} \mu(d) = 0

unless {n=1} then the sum is {1}.

Computing {M(x)}—the easy way

Computing {\mu(n)} for one value {n} seems to rely on the factorization of {n}. Thus even computing it at a single value could be hard. That is it could require super-polynomial time in worst case. Clearly computing {M(x)} is even harder:

\displaystyle M(x+1)-M(x) = \mu(x+1).

One way to compute {M(x)} is via complexity theory. This is not what Thompson does.

Theorem 1 Suppose that {\mathsf{P = \#P}}. Then we can compute {M(x)} in time polynomial in {\log(x)}.

This would be an exponential improvement over Thompson’s result. It probably shows how unlikely it is to get this collapse. But this is still open.

Recall a set {S} is in {P} provided given {x} one can decide whether {x} is in the set {S} in time polynomial in {\log x}. Recall {\mathsf{\#P}} given {N} computes the function that counts how many {x \le N} are in {S} also in time polynomial in {\log x}. Certainly counting is at least as hard as deciding membership in {S}. We believe that in general it is much harder. Assuming they are equal means that any predicate that can be computed in polynomial time can also be exactly counted. For example:

  1. Given a graph: One can count the number of spanning trees.
  2. Given a graph: One can count the number of three colorings of the graph.
  3. Given a polynomial equation: One can count the number of solutions.
  4. And so on.

The conjecture is that {\mathsf{P}} is not equal to {\mathsf{\#P}}. If {\mathsf{P = \#P}}, then {\mathsf{P=NP}} and more. Thus it probably is the case that they are not equal. But like much of complexity theory, this is wide open.

Computing {M(x)}—the hard way

Another way to compute {M(x)} is via number theory not via complexity theory. This is what Thompson does—with no unproved assumption about {P} and {\#P}.

She proves this main result in her paper—this is the paper we previously cited.

Theorem 2 There is an algorithm that computes {M(x)} in time

\displaystyle O_{\epsilon}(x^{\delta} \log^{\delta+\epsilon} x).

Here {\delta=3/5} and the constant in {O_{\epsilon}} depends on {\epsilon>0}.

Note the time used is {x} to some power. Before on the assumption that {P=\#P} we get that the time is polynomial in {\log x}.

The proof is non-trivial. In order to give some idea we will give a few comments. Standard identities allow one to write,

\displaystyle M(x) = 2M(\sqrt{x}) - \sum \mu(m_1)\mu(m_2),

over

\displaystyle m_1,m_2 \le \sqrt{x}.

The insight is to look hardest at those values

\displaystyle m_1,m_2 \le x^{2/5}.

Their summary of what happens next:

Our approach in Section 4 roughly amounts to analyzing the difference between reality and a model that we obtain via Diophantine approximation, in that we show that this difference has a simple description in terms of congruence classes and segments. This description allows us to compute the difference quickly, in part by means of table lookups.

As often, we say to see the full paper for the details. Or you can follow her talk either in Spanish or in English:


The proof is clever and there seems to be no way to improve it to anything near what we get via complexity theory. Of course we can only do that in the presence of a very strong conjecture:

\displaystyle \mathsf{P = \#P}.

But what she could do was to implement the algorithm in her joint paper. The computation ran on a many-core machine for weeks. It gets {M(x)} for {x \le 10^{22}}.

This is one advantage of algorithms that do not rely on unproved conjectures. They can actually be implemented and executed.

Open Problems

Is there a richer fount for open problems than number theory?

from → Ideas, P=NP, People, primes, Proofs
3 Comments leave one →
  1. KC permalink
    April 18, 2021 11:11 am

    Thanks for this post! Small clarification question: I think in the defn of M(x) you might have intended µ(n) instead of µ(x)?

    Reply
    • rjlipton permalink*
      April 18, 2021 11:55 am

      Dear KC:

      I fixed the error. Thanks for the comment.

      Best

      Dick

      Reply
  2. GT permalink
    April 18, 2021 4:16 pm

    The video of her talk in spanish is here: http://www.cmat.edu.uy/~tornaria/LATeN/2021/

    Reply

Leave a Reply to GTCancel reply

Discover more from Gödel's Lost Letter and P=NP

Subscribe now to keep reading and get access to the full archive.

Continue reading