13
$\begingroup$

I (David Speyer) took the liberty of doing a fairly major rewrite of this question. I hope I haven't gone too far, but I think there is an interesting question hiding here.


Sierpinski proved that there are infinitely many positive integers $k$ such that $k 2^n+1$ is composite for all positive $n$. Such a $k$ is called a "Sierpinski number of the second kind", which I'll shorten to "Sierpinski number" for the rest of this question. The smallest $k$ which has been proved to be a Sierpinski number is $78557$. However, there are no known primes of the form $10223 \cdot 2^n+1$, so $10223$ could be a Sierpinski number.

If you were to bet that $10223$ was a Sierpinski number, with the bet refereed by a perfectly honest, omniscient alien being, what odds would you accept?

This is particularly interesting, because a naive model suggests that there are no Sierpinski numbers. A naive model would be: for each $n$, independently pick a random integer uniformly between $10223 \cdot 2^n+1$ and $10223 \cdot 2^n (1.001)$. What is the probabilities that these are all composite?

Using the prime number theorem, we wind up looking at $\prod_{n=1}^{\infty} \left( 1- \frac{1}{\ln(10223 \cdot 2^n)} \right)$ and this product diverges to $0$. But this product also diverges to $0$ if we replace $10223$ by $78557$, contradicting Sierpinski's theorem.

So the challenge is to give a better probabilistic model, and calculate what result it gives. In one sense, the answers are subjective -- you will not be able to rigorously prove one model is better than another. But there are certainly arguments to be made for and against various models. And, if a perfectly honest, omiscient, alien bookie shows up at your door, don't you want to know how to bet?

  • 0
    You might interested in this paper:[Heuristics](http://www.utm.edu/staff/caldwell/preprints/Heuristics.pdf) by Chris Caldwell. I think it gives good hints to answer your question how to calculate the probilities and also wraps up the issues brought up by Didier/Joriki in a *Warning about Heuristics*.2012-05-22

1 Answers 1

4

First, regarding Didier's question about how to assign a probability to something which is either true or false, I highly recommend Towards a Philosophy of Real Mathematics by David Corfield.

In the present context, we can ask: If we had some way of determining whether there is at least one prime in this set, what would be the maximal price at which a rational self-interested actor would buy a bet to receive $€1$ in case it turns out that there is one?

This will depend in a complicated way on the actor's knowledge of the history of the Sierpinski problem: How far this set has been probed so far; how far the corresponding sets for other numbers that didn't turn out to be Sierpinski numbers had to be probed to find primes, etc.

But I'm guessing that your question isn't intended to take all this into account, and rather aims at a hypothetical rational self-interested actor who has no specific knowledge of the Sierpinski problem, but is aware of more general facts about primes, including density results related to the prime number theorem. Such an actor might calculate the "probability" of all numbers in this set being composite on the basis of an independence assumption roughly as

$p=\prod_n\left(1-\frac1{\log\left(10223\cdot2^n+1\right)}\right)\approx\prod_n\left(1-\frac1{\log10223+n\log2}\right)$

and thus

$\log p\approx\sum_n\log\left(1-\frac1{\log\left(10223\cdot2^n+1\right)}\right)\approx-\sum_n\frac1{\log10223+n\log2}\;.$

This logarithm diverges to $-\infty$, so our hypothetical self-interested actor would buy the bet at any price below $€1$.

Given that this model predicts that there shouldn't be any Sierpinski numbers at all but we know that there are, the independence assumption is unwarranted and it would be unwise to base any bets on it. To arrive at a more sound assessment of the value of such a bet would require an in-depth analysis of the history of the Sierpinski problem.

[Edit in response to the comments:]

It was rightly pointed out that I glossed over the possibility that there might be Sierpinski numbers despite the "probability" for this being $0$. However, my conclusion that a rational self-interested actor would abandon the naive model based on the independence assumption upon learning of the existence of Sierpinski numbers was correct.

Let's denote by $I$ the applicability of the independence assumption, by $S$ the existence of a Sierpinski number and by $A$ the existence of at least one prime in the set under consideration. Let's say the actor originally had degree $P(I)$ of belief in the applicability of the independence assumption and didn't know the first thing about Sierpinski numbers. Then the value of the bet to her would be $P(A)=P(I)P(A|I)+P(\neg I)P(A|\neg I)$, where $P(A|I)=1$ is the probability calculated above and $P(A|\neg I)$ is the probability she would ascribe to $A$ if the independence assumption were found not to apply. If her original degree of belief in the independence assumption is very high, that is, nearly $1$, the value of the bet is nearly $€1$.

Now upon learning that there are in fact Sierpinski numbers, assuming that this would influence her determination of $P(A)$ only via $P(I)$, she would perform a Bayesian update as follows:

$ \begin{eqnarray} P(A|S) &=& P(I|S)P(A|I)+P(\neg I|S)P(A|\neg I) \\ &=&\frac{P(I\cap S)}{P(S)}P(A|I)+\frac{P(\neg I\cap S)}{P(S)}P(A|\neg I)\\ &=& P(A|\neg I)\; \end{eqnarray} $

since $P(I\cap S)=0$, as the probability for $S$ under the independence assumption is zero. Thus $P(A|S) = P(A|\neg I)$, that is, learning of the existence of Sierpinski numbers has the effect of abandoning the independence assumption.

  • 1
    @joriki, let me signal [this](http://math.stackexchange.com/questions/77210/probabilistic-proof-of-existence-of-an-integer/77224#77224) to your attention.2011-11-01