friedman at math.ohio-state.edu
Wed Sep 16 15:19:39 EDT 1998
Reply to Cook 6:13PM 9/16/PM:
>The first question concerns use of a physical source, such as noise
>from background radiation, as a source of random bits for the test.
>Should we be totally convinced by the result of a test using such
>a source? It seems to me that this is more a question of physics than
>of mathematics. One would have to see a clear and convincing
>physical model for such a source, and a proof (assuming the model)
>that the resulting bits were truly random. Even given this, there
>would be important questions of implementation (e.g. was the source
>contaminated by earth-generated radiation?).
But would you agree that one does not need the physically generated bits to
be perfectly random? One needs them only to be approximately random - in
>Finally, Harvey asks
>>"There are issues connected with "why should I believe a computer?" at the
>>hardware and software level, and how good "independent verification" is. Do
>>you regard such issues as nonissues?"
>The answer is that I certainly agree that there are such issues, and some
>of them have been discussed on fom, by Shipman and others. There are
>also issues (pointed out on fom) about believing lengthy proofs not
I am intending to take up both of these issues in detail as a followup to
my posting 10:42AM 9/1/8/98. This is where I think there is some real
interesting new science to do. I.e., to what extent can we or should we
maximize our beliefs in mathematical assertions, and how should we go about
I did raise the issue of whether the belief levels we are talking about
here - also with conventional pseudo-random number generators - are
incomprehensibly close to certain, and (implicitly) how they compare to
beliefs of other kinds. After all, I think we both have been known to cross
busy streets, relying on our perceptions of the cars and the traffic
lights. We know that a serious error is going to end our life. This is more
serious than if a serious error ends our academic reputations. Yet we do
cross those streets. How does the degree of belief involved that gets us to
cross those streets compare to the beliefs we are discussing here in
connection with primality testing?
For an alternative formulation, I asked previously: Which is more certain -
a) that p is prime via a current application of Rabin's test with current
pseudo random number generators? and
b) it is false that the whole of California will fall into the ocean on
Jan. 1, 2000?
Perhaps several people on FOM will weigh in on this question.
There is a practical betting test that is useful for gauging the level of
belief connected with a). Let us suppose that p is a big prime and the
Rabin test comes out (under various reasonable implementations) positive
for being a prime. You then publish the following offer:
Upon the deposit by anyone (challenger) of $1000 in a specified formal
escrow account on or before Jan. 1, 2000, you agree to deposit $n in that
same escrow account. These funds are disposed of on Jan. 1, 2005 as
follows. If a factoring of p is presented to the bank officials on or
before Jan. 1, 2005 then all funds are payed to the challenger. Otherwise,
all funds are payed to you. How large an $n are you going to use when you
publish the offer? What fraction will n be of your net worth at the time of
publication of the offer? Will you borrow against your holdings and future
To avoid issues of lack of opportunity use of the money tied up in the
escrow account, each party maintains total investment control over their
funds while they are tied up in the escrow account.
There are more complicated variants of this protocol that are perhaps
better - such as involving an appropriate *auction*. Which brings up the
general question: what financial protocols appropriately gauge comparisons
between degrees of beliefs, or measure absolute degrees of belief? How is
the problem of marginal utility handled? How does U.S. and International
Tax Law complicate the picture (contest winnings may be taxable)? Etcetera.
This is surely an issue which has been addressed appropriately - say in
sophisticated Bayesian theory and decision theory. A nice application of it
would be to see what actual numbers we get when we apply it to various
Perhaps Steve will have to hire a lawyer specializing in (international)
contract law on behalf of the FOM for this purpose. And then we may have to
charge dues for the FOM .... (I'd better stop here).
More information about the FOM