##
A Mathematical Bet between Peter Alfeld and Nick Trefethen

The note
(click to get a full picture) documents a bet
Peter Alfeld
made with
Nick Trefethen
on June 25, 1985. It reads:
** 25 June 1985**

** L.N. Trefethen hereby bets Peter Alfeld that by
December 31, 1994, a method will have been found to solve
Ax=b (n x n linear system of eqs) in O(n**(2+epsilon))
operations for any epsilon > 0. Numerical Stability is
not required.**

** The winner gets $100.- from the loser.**
** signed: Peter Alfeld, Lloyd N. Trefethen**
** Witnesses: Per Erik Koch, S.P. Norsett.**
Norsett added the note *(This is an A-stable problem)
*.

Nick paid up in February 1996. ** We renewed the bet for
another 10 years,** and another $100 will change hands on
January 1, 2006. On February 13, 1996, we amended the bet
as follows: ** If one of the contestants settles the matter
prior to January 1, 2006 (by Peter Alfeld showing that no
O(n^2) method exists, or Nick Trefethen constructing an
O(n^2) method) the loser will pay the winner $200 at that
time.**

The best known exponent for linear algebra problems is
currently 2.376, thanks to an algorithm due to
Coppersmith and Winograd
in 1987.

** [16-Aug-1996]**