On Not Generating Pseudorandom Primes

This post is related to the ongoing Polymath 4 project [Blog, Wiki] which looks at the problem of deterministically generating primes of a given size. Many interesting approaches have been discussed. One that I found particularly interesting was Albert Asterias‘s derandomization approach based on Nisan-Wigderson Pseudorandom Generators. I will not explain Asterias’s idea here, but it should be clear how it inspired this post.

As the title suggests, this post is not about the problem of designing pseudorandom generators for the purpose of finding primes. This post is about the completely opposite question:

How hard is it for a pseudorandom generator to avoid producing primes?

I will show that if a pseudorandom generator fails to generate primes in reasonable quantity then this must be partly explained by some specific types of irregularities in the distribution of primes. It is not at all surprising that such irregularities prevent some pseudorandom generators from generating primes. However, it is not immediately clear that all failures lead to such irregularities. A heuristic analysis of these irregularities suggests that it is quite difficult for a reasonable pseudorandom generator to avoid producing primes, but I also argue that these irregularities cannot explain all ways that a pseudorandom generator can fail to produce primes.

The irregularities in question are of two specific types. Let $t_{n-1}\cdots t_0$ be the binary representation of some $n$ -bit number $t.$ For $0 \leq i \leq n-1,$ I define $\Delta_{i,n}(t)$ and $\nabla_{i,n}(t)$ as follows:

$\Delta_{i,n}(t)$ is the (possibly negative) excess of $n$ -bit primes whose lower order bits are $(1-t_i)t_{i-1}\cdots t_0$ versus those $n$ -bit primes whose lower order bits are $t_it_{i-1}\cdots t_0.$
$\nabla_{i,n}(t)$ is the (possibly negative) excess of $n$ -bit primes whose higher order bits are $t_{n-1}\cdots t_{i+1}(1-t_i)$ versus those $n$ -bit primes whose higher order bits are $t_{n-1}\cdots t_{i+1}t_i.$

Thus $\nabla_{i,n}(t)$ measures the difference in the number of $n$ -bit primes in two adjacent intervals of length $2^i,$ and dually $\Delta_{i,n}(t)$ measures the difference in the number of $n$ -bit primes in two “adjacent” arithmetic progressions with step $2^{i+1}.$ Since this is unusual in certain contexts, let me warn you that the sign of the difference is important.

Irregularity Lemma. Let $T$ be a random variable that takes values in the set $\{0,1,\dots,2^{n}-1\}$ of $n$ -bit integers. Suppose that $T$ is rather bad at generating primes, more precisely suppose that

$\mathbf{P}[T \in \mathrm{Prime}] \leq \mathbf{P}[U \in \mathrm{Prime}] - \varepsilon$

for some $\varepsilon > 0,$ where $U$ is uniformly distributed in $\{0,1,\dots,2^{n}-1\}.$ Then

$\mathbf{E}[\Delta_{i,n}(T)] \geq 2^{n-i}\varepsilon/n$ must hold for some $0 \leq i \leq n-1.$
$\mathbf{E}[\nabla_{j,n}(T)] \geq 2^j\varepsilon/n$ must hold for some $0 \leq j \leq n-1.$

Before I turn to the proof of the Irregularity Lemma, I’ll discuss what the conclusion of the lemma says.

Understanding the Irregularities

The condition $\mathbf{E}[\Delta_{0,n}(T)] \geq 2^n\varepsilon/(n-1)$ is perhaps most striking. The arithmetic progression $0 \pmod{2}$ contains only one prime, whereas the arithmetic progression $1 \pmod{2}$ contains $\pi(2^n) - 1 \sim 2^n/n$ primes. Therefore,

$\displaystyle \Delta_{0,n}(t) = \begin{cases} \pi(2^n)-2 & \text{when\ }t \equiv 0 \pmod{2}, \\ 2-\pi(2^n) & \text{when\ }t \equiv 1 \pmod{2}. \end{cases}$

So $\mathbf{E}[\Delta_{0,n}(T)] \geq 2^n\varepsilon/n$ only when $T$ is even more often than it is odd, which is clearly a bad idea for generating primes. (Though the special case when $T = 2$ is instructive.)

The condition $\mathbf{E}[\Delta_{1,n}(T)] \geq 2^{n-1}\varepsilon/n$ is very different. When $t$ is even, then $\Delta_{1,n}(t) = \pm1$ and so the even contribution to the expectation is negligible. When $t$ is odd, then $\Delta_{1,n}(t)$ is the excess of the number of $n$ -bit primes that are $3 \pmod{4}$ versus the number of $n$ -bit primes that are $1 \pmod{4},$ or vice versa. For large enough $n,$ we expect to have roughly the same number of primes in these two congruence classes. Indeed, the Siegel-Walfisz Theorem guarantees that $|\Delta_{1,n}(t)| = o(2^n/n)$ which means that this type of irregularity cannot possibly occur for large enough $n.$ In fact, assuming the Generalized Riemann Hypothesis, we have $|\Delta_{i,n}(t)| = O(2^{n/2}n^2)$ for $i \geq 1$ and so the condition $\mathbf{E}[\Delta_{i,n}(T)] \geq 2^{n-i}\varepsilon/n$ cannot hold for $i \leq n/2-O(\log n).$

When $i$ is close enough to $n,$ the expectation $\mathbf{E}[\Delta_{i,n}(T)]$ can be large enough. However, this situation can still have a very unusual feel to it. The extreme case $i = n-1$ is enlightening. Let $T'$ be the random variable that differs from $T$ only in the most significant bit (i.e., $T' = T + 2^{n-1} \mathop{\mathrm{mod}} 2^n$ ). Then

$\mathbf{E}[\Delta_{n-1,n}(T)] = \mathbf{P}[T' \in \mathrm{Prime}] - \mathbf{P}[T \in \mathrm{Prime}].$

So a large $\mathbf{E}[\Delta_{n-1,n}(T)]$ means that while $T$ is not often prime, the closely related random variable $T'$ is prime more often. In general, $\mathbf{E}[\Delta_{i,n}(T)] \geq 2^{n-i}\varepsilon/n$ for large $i$ means that while $T$ may not be prime, it is close to many primes in the dyadic metric.

The situation with $\nabla_{j,n}(T)$ is similar, but has a slightly different feel. Again, when $j$ is close to $n,$ the inequality $\mathrm{E}[\nabla_{j,n}(T)] \geq 2^j\varepsilon/n$ is unlikely since we expect two intervals of length $2^j$ to contain roughly the same number of primes. Indeed, assuming the Riemann Hypothesis, we have the bound $|\nabla_{j,n}(t)| = O(n2^{n/2})$ which means that $\mathbf{E}[\nabla_{j,n}(T)] \geq 2^j\varepsilon/n$ cannot hold for $j \geq n/2 + O(\log n).$

When $j$ is small enough, the expectation $\mathbf{E}[\nabla_{j,n}(T)]$ can be large enough. Again, this situation can have a very unusual feel. For example, a large value of $\mathbf{E}[\nabla_{0,n}(T)]$ means that $T\pm1$ is often prime. In general, $\mathbf{E}[\nabla_{j,n}(T)] \geq 2^j\varepsilon/n$ for small $j$ means that while $T$ may not be prime, it is close to many primes (in the usual metric).

When $i,j \sim n/2,$ neither the inequality $\mathbf{E}[\Delta_{i,n}(T)] \geq 2^{n-i}\varepsilon/n$ nor the inequality $\mathbf{E}[\nabla_{j,n}(T)] \geq 2^j\varepsilon/n$ is very surprising. However, it is unusual for both inequalities to hold simultaneously. Indeed, arithmetic progressions with step $2^{i+1}$ and intervals of length $2^j$ are somewhat orthogonal to each other so it would seem that the two types of irregularities would tend to interfere and cancel each other out. Such a $T$ should take a somewhat sparse set of values. This is not very restrictive, so this is likely where most irregularities can be found.

Seeing that many of these irregularities are either impossible, unlikely, or very visible, it is tempting to conclude that any reasonable looking pseudorandom generator will inevitably generate a decent amount of primes. This is overly optimistic as the irregularities are relatively blind to some more global properties that can prevent $T$ from generating primes. For example, if $T$ is such that

$0 = T_0 - T_1 + T_2 + \cdots \pm T_{n-1}.$

(In other words, $T$ has equally many $1$ bits in even position as it has $1$ bits in odd positions.) Then $T$ is always a multiple of $3.$ However, it is not at all clear how to explain this global property in terms of irregularities as described above.

Proof of the Irregularity Lemma

I will only prove the first conclusion that

$\mathbf{E}[\Delta_{i,n}(T)] \geq 2^{n-i}\varepsilon/n$

for some $i \in \{0,\dots,n-1\}.$ The proof of the second conclusion is symmetric.

Let’s write

$T = T_0 + 2 T_1 + \cdots + 2^{n-1} T_{n-1}$

where $T_0,\dots,T_{n-1}$ are (usually not independent nor uniform) binary random variables. Similarly, let’s write

$U = U_0 + 2 U_1 + \cdots + 2^{n-1} U_{n-1}$

where $U_0,\dots,U_{n-1}$ are independent uniform binary random variables.

Consider the hybrid random variables

$V_i = T_0 + \cdots + 2^{i-1} T_{i-1} + 2^i U_i + \cdots + 2^{n-1} U_{n-1}$

for $i = 0,\dots,n$ (so $V_0 = U$ and $V_n = T$ ). Since

$\displaystyle \mathbf{P}[U \in \mathrm{Prime}] - \mathbf{P}[T \in \mathrm{Prime}] = \sum_{i=0}^{n-1} \mathbf{P}[V_{i} \in \mathrm{Prime}] - \mathbf{P}[V_{i+1} \in \mathrm{Prime}],$

there must be an $i \in \{0,\dots,n-1\}$ such that

$(*) \quad \mathbf{P}[V_{i} \in \mathrm{Prime}] \geq \mathbf{P}[V_{i+1} \in \mathrm{Prime}] + \varepsilon/n.$

Note that $\mathbf{P}[V_i \in \mathrm{Prime}]$ equals

$\mathbf{P}[U_i = T_i \land V_{i+1} \in \mathrm{Prime}] + \mathbf{P}[U_i \neq T_i \land W_{i+1} \in \mathrm{Prime}]$

where $W_{i+1}$ is the random variable

$W_{i+1} = T_0 + \cdots + 2^{i-1} T_{i-1} + 2^i (1 - T_i) + 2^{i+1} U_{i+1} \cdots + 2^{n-1} U_{n-1}.$

(So $W_{i+1}$ differs from $V_{i+1}$ only in the $i$ -th bit.) Since $U_i$ is independent of $T_i, V_{i+1}, W_{i+1},$ we have

$\mathbf{P}[U_i \neq T_i \land V_{i+1} \in \mathrm{Prime}] = \frac{1}{2}\mathbf{P}[V_{i+1} \in \mathrm{Prime}],$

$\mathbf{P}[U_i \neq T_i \land W_{i+1} \in \mathrm{Prime}] = \frac{1}{2}\mathbf{P}[W_{i+1} \in \mathrm{Prime}].$

Thus,

$\mathbf{P}[V_i \in \mathrm{Prime}] = \frac{1}{2}\mathbf{P}[V_{i+1} \in \mathrm{Prime}] + \frac{1}{2}\mathbf{P}[W_{i+1} \in \mathrm{Prime}]$

and, from $(*),$ we obtain

$\frac{1}{2}\mathbf{P}[W_{i+1} \in \mathrm{Prime}] - \frac{1}{2}\mathbf{P}[V_{i+1} \in \mathrm{Prime}] \geq \varepsilon/n.$

On the other hand,

$\mathbf{E}[\Delta_{i,n}(T)] = 2^{n-i-1}\mathbf{P}[W_{i+1} \in \mathrm{Prime}] - 2^{n-i-1}\mathbf{P}[V_{i+1} \in \mathrm{Prime}].$

So $\mathbf{E}[\Delta_{i,n}(T)] \geq 2^{n-i}\varepsilon/n.$ QED

About these ads

On Not Generating Pseudorandom Primes

Understanding the Irregularities

Proof of the Irregularity Lemma

Like this:

Leave a Reply Cancel reply

Recent Posts

Categories

Blogroll

Comics

Meta

Follow “Mathemata”