# Which ζ-function controls the density of base=2 Miller–Rabin pseudoprimes?

Background: the density d (≈ inverse distance between elements of the set) of primes is “controlled by zeros of ζ-function” in the sense that $$(d(x) - T(x))·\log(x)/√x$$ is an almost periodic function of $$\log(x)$$ with the frequencies given by the imaginary parts¹⁾ of the zeros of Riemann’s ζ-function. Here $$T(x)$$ is “the trend” of the density.

¹⁾ The real part is already taken into account by the factor √x above. The amplitudes are determined by frequencies via a simple formula. (This²⁾ fact is called Riemann–Weil formula.)

²⁾ To be honest, this is 100%-correct only when applied not to the density of primes, but to a (Chebyshyov’s) “weighted” density Ψ of powers of primes. Reading Riemann “between the lines”, it is clear that he thought a similar fact holds for the density of primes too — but so far such a conjecture is not verified.

This is very easy to see³⁾ on the plot of d: one can immediately guess the main term $$1/\log(x)$$ of T (as well as the form of the factor $$\log(x)/√x$$ above). Then log-Gaussian averaging of the plot immediately exposes sine-waves, and it is easy to fit them to the graph. (This way, it is not hard to expose the first 8 sine-waves contributing to Ψ — and recognize the corresponding waves contributing to d.)

³⁾ I cannot stop myself mentioning the fact that the first zero “can be seen by a smart first-grader”: the small prime numbers 2, 3, 5, 7, 11 form “an approximate geometric progression”. Extending this progression to ∼100 and comparing it to the places where primes are “clumped together” on the log-scale shows that the match continues. This allows to estimate the first zero up to precision of a few percents. (Going above ∼300 requires intelligent averaging “above the level of skills of a first-grader”! 😅)

On the plot below the “centers of visible clusters of primes” (these centers are “only approximately defined”) are marked by blue arrow, and the corresponding terms of a geometric progression by orange arrows. To keep the things in perspective, the range [2,11] above gives the denominator of the matching geometric progression as $$\sqrt[4]{5½}≈1.531≈\exp 2π/14.74$$. The range [2,104] gives $$\sqrt[9]{52}≈1.511≈\exp 2π/14.312$$. Note that “the correct denominator” is $$≈\exp 2π/14.134725142$$; hence the former way estimates the first zero of ζ-function with error of 4.3%, and the latter way errors by 1¼ %):

Forward to the question: I do the same for the density d of base=2 Miller–Rabin pseudo-primes:⁴⁾ Here I tried to quickly fit a suitable “trend” T (and the corresponding factor) — just to make the picture presentable. (The concrete form of these is very preliminary!)

⁴⁾ Please ignore the ticks on the graph. I had been trying to report this bug for many years…

(Update: the plots and comments are significantly improved w.r.t. the original version. Update²: colors corrected to match.) These plots are log-Gaussian-averaged⁵⁾ with ½-widths of log(1.03) and log(1.7).

⁵⁾ The Gaussians are cut-off at 13σ and 6σ correspondingly. On the blue graph one can clearly distinguish the peaks at the first 10 pseudo-primes.

In view of the background above, the chain of repeating hills at regular increments may appear suspicious! Here is the sine-wave (with a suitable factor) “visually fitting” these hills: From my experience with plots for “density of ‘usual’ primes” I know that the match as on the picture above a very good indicator of “a correctly guessed component of a discrete spectrum”. For people still in doubt, this plot filters out low frequencies (to get rid of the major component of the trend T); the sine-wave is shifted in phase a bit w.r.t. the picture above to get a better fit: This plot shows the density and “the residual”⁶⁾ (after the subtraction of the wave above):

⁶⁾ The residual indicates that the sine wave above gives a very good match on the left and on the right. However, it seems that the amplitude of the subtracted wave should be decreased a bit in the range 10⁹–10¹³. I could not find a better fit with a simple formula… So it might be just “a beat between other present frequencies”!

Question: I think it is a pretty convincing evidence that the presence of discrete spectrum (= that fit between the graphs above) is not a piece of my imagination. So: is there a reason for such an oscillating term?

• On the captures on plots, $2 is the averaged$d(x)\sqrt{x}$with$x=$$1. (This removes the main term of “variability” of $d$ — which makes the averaging much simpler. But maybe we should have averaged $d(x)\sqrt{x}\log²x$ instead…) May 12 at 13:22
• I was hoping to learn something from your question but I'm having problems understanding it from your word description. Could you please define your formulas for $d(x)$ and $T(x)$ for both the prime (or prime-power) case and the base-$2$ Miller–Rabin pseudo-prime case? May 12 at 17:07
• @StevenClark: The known-to-be-covered (Chebyshyov’s) $d$ is $\log(x)∑_{p,k}\frac 1kδ(x-p^k)$. For the Riemann case “remove $k$” and the factor $\log x$. For any sequence (such as strong PSP), replace $p$ by elements of the sequence (“averaging this [= ‘convolving with a suitable kernel’] gives inverse to “the average step’”). (Did it help?) May 13 at 10:53
• @StevenClark: Correction I need to be a bit more precise. The formula for $d$ in the preceding comment is for the “non-logarithmic scale”. When one recalculates this (“considered as a measure”) to $X≔\log x$, this becomes $D(X) ≔ X∑_{p,k} \frac 1kδ(X-k\log p)$; to make this almost periodic, one should consider $(D(X)-T(X))/\sqrt X$ with the trend $T(X) ≈ \mathrm{e}^X = x$ (with ≈ hiding extra terms decaying in $X$). For strong pseudo-primes, $2 above is pre-divided by$\sqrt{x} = \mathrm{e}^{X/2}$— which would be an analogue of dividing by$T(X)\$ in the Chebyshyov’s case. May 14 at 10:23
• Thanks, your clarification and correction provide considerable insight. I can see formulas in the top of your plots, but I'm not familiar with the tool you're using to generate the plots. At the beginning of your formulas there appears to be a reference to a file name, so perhaps your visible formulas are acting on data contained within these files, and other formulas were used to generate the data within these files. May 15 at 17:04