The Bimobius Function: The Ultimate Subexponential Pseudorandom Bit Generator

The Mobius function is defined as follows, for all positive integers N:

  (+1) for N=1
  (-1) for N=2
  else 0 if N contains a prime factor with an exponent of at least 2
  else (+1) if N contains an even number of prime factors
  else (-1)

According to Wikipedia, the first 23 values starting with (N=1) are:

{1, -1, -1, 0, -1, 1, -1, 0, 0, 1, -1, 0, -1, 1, 1, 0, -1, 0, -1, 0, 1, 1, -1}

Informally, the famous Riemann Hypothesis says that Mobius is asymptotically optimally random. That is, (+1) and (-1) occur with asymptotically equal probability; however, there is a dearth of zeroes. Thus we have in Mobius a ternary PRNG in which the middle value exhibits bias.

Because of this bias, we must instead turn to what I call the "bimobius" (binary Mobius) function as a sort of gold standard for randomness, in the sense that it can be computed in subexponential (if not perhaps polynomial) time yet mimics the Poisson behavior of an unbiased sequence of coin tosses in the limit of large N.

To understand bimobius, we first remove the zeroes from the Mobius function:

{1, -1, -1, -1, 1, -1, 1, -1, -1, 1, 1, -1, -1, 1, 1, -1}

Then we convert (+1) and (-1) to their sign bits -- zero and one, respectively:

{0, 1, 1, 1, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1}

You get the idea. It would make a great cryptographic primitive, were it no so painful to compute!

You can obtain C and Mathemetica code for, and run some statistical analysis of, bimobius in the Enranda demo.

It may also be of interest to you that if we have N terms of Mobius, then this will asymptotically reduce to (6N/(π^2)) terms of bimobius. The reason relates to the fact that the bimobius function is essentially a mapping of all least-common-multiples with unique prime factors to their number of prime factors, mod 2. This is related to the fact that (6/(π^2)) is the probability that 2 random positive integers will be coprime.

Oh and by the way, the order-(2^16) kernel skew of bimobius converges surprisingly slowly. According to the Enranda demo, the first (2^16) 16-bit samples have a skew of (-5.1E-01), and the next (2^16) have a skew of (+3.1E-01). Despite the sign change, which is encouraging because it as least suggests that the skew is asymptotically zero (as it should be if the Riemann Hypothesis is correct), this is an order of magnitude larger than what it should be under conditions of ideal randomness. Maybe the prime numbers are more orderly than we thought, which would not be suprising because computing bimobius is (merely) subexponentially expensive. So maybe it ain't so "ultimate" after all... but then, what subexponential function is?