Is there a number of repetitions for which the Miller-Rabin primality test might succeed on all numbers?
1
50Ṁ100
2028
10%
chance

This came up in a discussion on the Lean Zulip. Stated formally, the question is as follows:

For a natural number n > 4 which is composite but not a prime power, let $m_n$ be the probability that a single repetition of the Miller-Rabin test on $n$ gets the wrong result. That is, $m_n$ is the proportion of numbers in $\mathbb{Z}_n$ which are not Miller-Rabin witnesses of the compositeness of n.

This market asks: Does there exist an $a > 1$, such that the series $\sum_{n>4, n composite, n not a prime power}^\infty m_n^a$ diverges?

It is known that $m_n \le 1/4$. If there is some $k>0$ such that there are infinitely many $m_n > k$, then this is false.

This market will be extended until the question is resolved.

Get
Ṁ1,000
to start trading!
© Manifold Markets, Inc.TermsPrivacy