Relaxing the Primes

Finnish Scientific Courage Award source

Kaisa Matomäki is a Finnish mathematician working in number theory. She has some terrific results on prime numbers—results that have won several important prizes including the 2021 Ruth Lyttle Satter Prize: It is presented to a woman who has made an outstanding contribution to mathematics research. The prize citation specifically mentions a 2015 paper with Maksym Radziwill that contributed to Terence Tao’s resolution of the Erdős discrepancy problem—and indeed we highlighted Tao’s followup work with her and Radziwill in our 2015 post on this.

Today, Ken and I thought we would combine one of her new deep theorems with some shallow observations.

The set of primes is denoted by , as usual. As complexity theorists we have known that for decades that the Boolean circuit complexity of is polynomial. This follows from the existence of a polynomial random algorithm for due to Robert Solovay and Volker Strassen, and then applying Len Adleman’s connection between such algorithms and Boolean circuit complexity.

Matomäki views in a different way. As an analytic number theorist she is concerned with the density and structure of primes, not so much the complexity of recognizing or generating a prime.

Relaxations

Exact results on the set of primes are hard to come by.

Twin Primes: We know that there are infinitely many such that and are prime. But not proved.

Goldbach: We know that every even number from onward is the sum of two primes. But not proved.

Density of Primes: We known that the gap between consecutive primes is at most But not proved.

The Riemann Hypothesis attempts to say more about density of the primes than the Prime Number Theorem does. It has been proved equivalent to some statements about approximate growth rates, yet even these forms have not been touched.

Instead of trying for better approximate results about primes, can we learn more by relaxing the notion of “prime” itself? For each , define to be the set of numbers that are products of at most primes. Then is the set of primes (not the prime powers) and is the set of products of two primes—which include the Blum integers of special interest to cryptography. Collectively the sets represent different levels of being “almost prime.” The motivating question is:

How well and in what ways does the structure of the sets of almost-primes model the structure of the primes?

In 2010, John Friedlander and Henryk Iwaniec wrote a monograph titled Opera de Cribro, which is Latin for “Works of the Sieve.” They proved certain results about and speculated whether their methods improve them to work at least for . Then they say, “It would be interesting to get integers with at most two prime divisors.” This is where Matomäki comes in—with a second kind of relaxing, one applying to “almost all” members of .

New Result

Matomäki has a brand new paper (revised two weeks ago from a December original) titled, “Almost primes in almost all very short intervals.” It follows on from a paper by one of her students, Joni Teräväinen, titled “Almost all primes in almost all short intervals.”

Her main result is the following theorem.

Theorem 1 Suppose as and put . Then for almost all and , the interval contains a .

Roger Heath-Brown had established the corresponding result for primes (that is, for ) but only assuming simultaneously the Riemann hypothesis and the pair correlation conjecture for the zeros of the Riemann zeta function. With no hypotheses, the presence of primes in almost all intervals is known only when the intervals have length —concretely, is known. Thus, Matomäki has traded off the use of conjectures for the relaxed notion of prime.

The “almost call” is in the sense of average density of whose short interval is populated. This average instead of worst case mirrors our difficulties with circuit lower bounds. We can easily show that on average Boolean function have huge circuit lower bounds. But worst case bounds for specific functions is beyond reach. Hmmm.

Lower Bounds

We previously proved:

Theorem 2 (Lower Bound) For any , the depth of a DeMorgan boolean circuit for is at least .

Recall a DeMorgan formula on variables is a binary tree whose leaves are labeled with variables or their negations, and whose internal nodes are labeled with either for OR and for AND gates.

Here is a high level view of this result. See here for details.

Assume there is a DeMorgan Boolean circuit for is at most depth. We can use the random restriction method to set lots of the inputs to random values .

We claim that with high probability the input looks like

The right-most bits

are left unset, and the other bits to the left have some bits randomly set. Moreover, the number of bits in the above right is order .

Now set all the bits in the left group that are unset also to random values . Leave the right group unset.

The point of this is that if we assume that the formula had size at most order , then we have that the formula is likely to be constant. But this contradicts the density of primes and composites.

Open Problems

Can Matomäki’s theorem be used to get stronger lower bounds on the complexity of ? Can it go beyond the quadratic limit?