109
$\begingroup$

Since the old days, many mathematicians have been attaching monetary rewards to problems they admit are difficult. Their reasons could be to draw other mathematicians' attention, to express their belief in the magnitude of the difficulty of the problem, to challenge others, "to elevate in the consciousness of the general public the fact that in mathematics, the frontier is still open and abounds in important unsolved problems.1", etc.

Current major instances are

Other problems with money rewards

Question: What others are there? To put some order into the answers, let's put a threshold prize money of 100 USD. I expect there are more mathematicians who have tucked problems in their web-pages with some prizes.

What this question does not intend to achieve:

  • once offered but then collected or withdrawn offers

  • new pledges of sums of money just here

P.S. Some may be interested in the psychological aspects of money rewards. However, to keep the question focused, I hope this topic won't be ignited here. One more, I understand that mathematicians do not work merely for money.

$\endgroup$
13
  • 10
    $\begingroup$ I see some votes to close this post. I have started a meta asking why here: tea.mathoverflow.net/discussion/1055/… So, please all discussion concerning this should happen there. $\endgroup$
    – Unknown
    May 27, 2011 at 9:08
  • 14
    $\begingroup$ @Thierry -- I've often felt that even for the Clay million-dollar problems, that's got to be one of the hardest ways to earn a million dollars! I should think just the glory of solving such a problem would be, by far, a greater motivation. (BTW: I think it is small.) $\endgroup$
    – Todd Trimble
    May 27, 2011 at 9:40
  • 22
    $\begingroup$ Well, this question already has 4 votes to close. To whoever is thinking of pulling the plug: I also thought of voting to close at first, but since the question has already generated a couple of useful answers (including some problems I would probably never have heard of otherwise), I think it should stay open. $\endgroup$
    – algori
    May 28, 2011 at 1:57
  • 21
    $\begingroup$ I agree, I think that four votes to close is four too many. $\endgroup$ May 29, 2011 at 13:42
  • 8
    $\begingroup$ Besides solving open question, finding errors in D. Knuth's books is wort a check of 2.56 US dollar (one hexadecimal dollar) . $\endgroup$ May 7, 2012 at 13:31

29 Answers 29

72
$\begingroup$

Two which are for food rather than cash:

Let $f = t^{2d} + f_1 t^{2d-1} + f_2 t^{2d-2}+ \cdots f_d t^d + \cdots+ f_2 t^2 +f_1 t + 1$ be a palindromic polynomial, so the roots of $f$ are of the form $\lambda_1$, $\lambda_2$, ..., $\lambda_d$, $\lambda_1^{-1}$, $\lambda_2^{-1}$, ..., $\lambda_d^{-1}$. Set $r_k = \prod_{j=1}^d (\lambda_j^k-1)(\lambda_j^{-k} -1)$.

Conjecture: The coefficients of $f$ are uniquely determined by the values of $r_1$, $r_2$, ... $r_{d+1}$.

Motivation: When computing the zeta function of a genus $d$ curve over $\mathbb{F}_q$, the numerator is essentially of the form $f$. (More precisely, it is of the form $q^d f(t/\sqrt{q})$ for $f$ of this form.) Certain algorithms proceed by computing the $r_k$ and recovering the coefficients of $f$ from them. Note that you have to recover $d$ numbers, so you need at least $r_1$ through $r_d$; it is known that you need at least one more and the conjecture is that exactly one more is enough.

Reward: Sturmfels and Zworski will buy you dinner at Chez Panisse if you solve it.


Consider the following probabilistic model: We choose an infinite string, call it $\mathcal{A}$, of $A$'s, $C$'s, $G$'s and $T$'s. Each letter of the string is chosen independently at random, with probabilities $p_A$, $p_C$, $p_G$ and $p_T$.

Next, we copy the string $\mathcal{A}$ to form a new string $\mathcal{D}_1$. In the copying process, for each pair $(X, Y)$ of symbols in $\{ A, C, G, T \}$, there is some probability $p_1(X \to Y)$ that we will miscopy an $X$ as a $Y$. (The $16$ probabilities stay constant for the entire copying procedure.)

We repeat the procedure to form two more strings $\mathcal{D}_2$ and $\mathcal{D}_3$, using new probability matrices $p_2(X \to Y)$ and $p_3(X \to Y)$.

We then forget the ancestral string $\mathcal{A}$ and measure the $64$ frequencies with which the various possible joint distributions of $\{ A, C, G, T \}$ occur in the descendant strings $(\mathcal{D}_1, \mathcal{D}_2, \mathcal{D}_3)$.

Our procedure depended on $4+3 \times 16$ inputs: the $(p_A, p_C, p_G, p_T)$ and the $p_i(X \to Y)$. When you remember that probabilities should add up to $1$, there are actually only $39$ independent parameters here, and we are getting $63$ measurements (one less than $64$ because probabilities add up to $1$). So the set of possible outputs is a semialgeraic set of codimension $24$.

Conjecture: Elizabeth Allman has a conjectured list of generators for the Zariski closure of the set of possible measurements.

Motivation: Obviously, this is a model of evolution, and one which (some) biologists actually use. Allman and Rhodes have shown that, if you know generators for the ideal for this particular case, then they can tell you generators for every possible evolutionary history. (More descendants, known sequence of branching, etc.) There are techniques in statistics where knowing this Zariski closure would be helpful progress.

Reward: Elizabeth Allman will personally catch, clean, smoke and ship an Alaskan Salmon to you if you find the generators. (Or serve it to you fresh, if you visit her in Alaska.)

$\endgroup$
4
  • $\begingroup$ Is there some genericity condition on the $\lambda_i$ in the first conjecture? For instance if $\lambda_1 = 1$ then all the $r_k$ are zero, and that's obviously not enough information to reconstruct $f$? $\endgroup$ Jul 26, 2012 at 21:19
  • $\begingroup$ Yes, the conjecture is for generic $\lambda_i$. I can't seem to find an original print source for it, but you can find it restated as Conjecture 1.2 in arxiv.org/abs/math.AG/0411414 $\endgroup$ Jul 27, 2012 at 1:02
  • 3
    $\begingroup$ I'm not entirely sure of the details, but I believe that Oeding was awarded a salmon for a partial solution: auburn.edu/~lao0004/Salmon_Talk_SIAM_ag.pdf . I'm not sure if further progress will be rewarded with further fish. :-) $\endgroup$
    – LSpice
    Mar 2, 2015 at 23:24
  • 6
    $\begingroup$ Shmuel Friedland received a salmon (or half a salmon?) for a set-theoretic version of the conjecture, ie., showing that the conjectured generators do generate the ideal up to radical. homepages.math.uic.edu/~friedlan/IMGP2990.JPG Bates--Oeding got the same or similar result after Friedland. I don't think they got a salmon. I believe the original conjecture is still open (showing that the conjectured generators in fact generate the ideal, not just up to radical). $\endgroup$ May 2, 2017 at 13:42
58
$\begingroup$

Addendum: There is a paper by Fan Chung similar to this book by Chung and Graham, Open problems of Paul Erdős in graph theory. She says there, "In November 1996, a committee of Erdős' friends decided no more such awards will be given in Erdős' name." But the same article says that Chung and Graham decided to still sponsor questions in graph theory, and this article in Science Magazine implies that they are still sponsoring the Erdős problems in general.


Some 19 years ago I collected a list of Erdős prize problems and posted them to Usenet. The problems were from "A Tribute to Paul Erdős" (1990) and "Paths, Flows, and VLSI Layout" (1980). I can repeat the problems here, although I have no idea which ones may have been solved.

$\$10000$. (T4N) Consecutive primes are often far apart. Conjecture: For every real number $C$, the difference between the $n$'th prime and n+1'st prime exceeds

$$C \log(n) \log(\log(n))\log(\log(\log(\log(n))))/\log(\log(\log(n)))^2$$

infinitely often. (The wording in the source does not clearly indicate that the money will be awarded if the conjecture is disproved, only if it is proved.) [Answered: By Kevin Ford, Ben Green, Sergei Konyagin, and Terence Tao, and independently by James Maynard, both groups in August 2014.]

$\$3000$. (T3N) Divergence implies arithmetic progressions. If the sum of the reciprocals of a set of positive integers is infinite, must the set contain arbitrarily long finite arithmetic progressions?

$\$1000$. (T2N) Unavoidable sets of congruences. A set of congruences $n = a_1 \bmod b_1$, $n = a_2 \bmod b_2$,... is unavoidable if each $n$ satisfies at least one of them. Is there an $N$ such that every unavoidable set of congruences either has two equal moduli $b_i$ and $b_j$ or some modulus $b_i$ less than $N$? [Answered: By Bob Hough in July 2013.]

$\$1000$. (T1C) Three-petal sunflowers. Is there an integer $C$ such that among $C^n$ sets with $n$ elements, there are always three whose mutual intersection is the same as each pairwise intersection? (Problem P2 is the same, except that Erdos asks about $k$-petal sunflowers for every $k$ but then says he would be satisfied with $k=3$.)

$\$500$. (T7N) Asymptotic bases of order 2 (I). Consider an infinite set of positive integers such that every sufficiently large integer is the sum of two members of the set. Can there be an $N$ such that no positive integer is the sum of two members of the set in more than $N$ ways?

$\$500$. (T8N) Asymptotic bases of order 2 (II). In the context of the previous problem, let $f(n)$ be the number of ways that n is the sum of two members of the set. Can $f(n)/\log(n)$ converge to a finite number as $n$ goes to infinity?

$\$500$. (T9N) Evenly distributed two-colorings. Given a black-white coloring of the positive integers, let $A(n,k)$ be the number of blacks minus the number of whites among the first $n$ multiples of $k$. Can the range of $A$ be bounded on both sides?

$\$500$. (T4C) Friendly collections of half-sized subsets. Given $1+(\binom{4n}{2n} - \binom{2n}{n}^2)/2$ distinct, half-sized subsets of a set with $4n$ elements, must there be two subsets which intersect only in one element? (As problem P1, 250 pounds is offered.)

$\$500$. (T1G) Uniformity of distance in the plane (I). Is there a real number $c$ such that n points in the plane always determine at least $cn/\sqrt{\log(n)}$ distinct distances?

$\$500$. (T1G) Uniformity of distance in the plane (II). Is there a real number $c$ such that given n points in the plane, no more than $n^{(1+c/\log(\log(n)))}$ pairs can be unit distance apart?

$\$500$. (P2) Sets with distinct subset sums. Is there a real number $c$ such that, given a set of n positive integers whose subsets all have distinct sums, the largest element is at least $c2^n$? (As in problem T1N, no prize is mentioned.)

$\$250$. (P4) Collections of sets not represented by smaller sets. Is there a real number $c$ such that for infinitely many positive integers $n$, there exists $cn$ or fewer sets with n elements, no two of which are disjoint, and every $(n-1)$-element set is disjoint from at least one of them?

$\$250/\$100$. (P15) Slowly increasing Turan numbers. If H is a (simple) graph, the Turan number $T(n,H)$ is the largest number of edges a graph with $n$ vertices can have without containing a copy of $H$. Conjecture: the function $f(n) = T(n,H)/n^{3/2}$ is bounded above if and only if every connected subgraph of $H$ has a vertex of valence 1 or 2. The larger award would be granted for a proof.

$\$100/\$25000$. (T6N) Consecutive early primes. An early prime is one which is less than the arithmetic mean of the prime before and the prime after. Conjecture: There are infinitely many consecutive pairs of early primes. The larger award would be granted for a disproof.

$\$100$. (T8G) Quadrisecants in the plane. Given an infinite sequence of points in the plane, no five of which are collinear, let $r(n)$ be the number of lines that pass through four points among the first $n$. Can it happen that $r(n)/n^2$ does not converge to zero?

$\endgroup$
2
  • 1
    $\begingroup$ @Greg, thank you very much. Your collection of the Erdos prize problems were linked to previously but this organized answer makes the question really interesting. $\endgroup$
    – Unknown
    May 28, 2011 at 5:47
  • $\begingroup$ What does "there are infinitely many consecutive pairs of early primes" mean, exactly? I'm having trouble seeing which adjective modifies what -- is this a stronger version of the twin prime conjecture? $\endgroup$ Feb 24, 2016 at 8:00
45
$\begingroup$

Of course mathematicians do not work merely for money! They are motivated by higher things like access to moderation tools at 10000 reputation level on Mathoverflow!

I've heard from Ron Graham that the bookkeeping for Erdos rewards is difficult because many people frame the check and never cash it.

There is always the chance of earning $327.68 from Donald Knuth. It is stretching things more than a bit to include that in and of itself, but the linked article is amusing and the general considerations are pertinent.

The EFF offers large rewards for large primes.

$\endgroup$
3
  • 18
    $\begingroup$ I've heard that the cleverer people who win Erdos money photocopy the check, frame the copy, and keep the original. $\endgroup$ May 27, 2011 at 5:37
  • 24
    $\begingroup$ Knuth says his cheques are much more often cached than cashed. $\endgroup$
    – Max
    Jun 21, 2011 at 19:09
  • 5
    $\begingroup$ As of 2008, Knuth no longer sends out checks in real money. Instead, he will credit your account at the fictitious Bank of San Serriffe. $\endgroup$ Jan 11, 2015 at 23:27
37
$\begingroup$

It was pointed out by Randall Munroe that by proving the inconsistency of logic you can earn quite a lot of money:

alt text

(Source)

$\endgroup$
3
  • 4
    $\begingroup$ Ex falso quodlibet! So, I doubt this creates that many errors. $\endgroup$
    – user9072
    Jul 26, 2012 at 12:00
  • 57
    $\begingroup$ I should have mentioned that the hidden text is : "Dear Reader: Enclosed is a check for ninety-eight cents. Using your work, I have proven that this equals the amount you requested." $\endgroup$
    – Adrien
    Jul 26, 2012 at 12:21
  • 1
    $\begingroup$ Oh, so you suggest to prove just this, and then cash in essentially all the things mentioned so far. Nice plan ;D $\endgroup$
    – user9072
    Jul 26, 2012 at 15:07
36
$\begingroup$

Paul Erdős was famous for offering money for solutions to math problems. My understanding is that those prizes are still being administered by Ron Graham, even though Erdős passed away several years ago.

One of his most famous (and biggest money) problems is the following:

Conjecture: If $S$ is a set of positive integers such that the series $\sum_{s \in S} \frac{1}{s}$ diverges, then $S$ contains arbitrarily large arithmetic progressions.

I believe that $3000 is offered for a proof.

Several graph theory related problems, with prize money listed for many of them, are collected in Erdős on graphs, by Chung and Graham.

$\endgroup$
8
  • 19
    $\begingroup$ With a solution of that problem a Field medal would also come, unless you are over 40. $\endgroup$ May 26, 2011 at 18:48
  • 2
    $\begingroup$ See "Does there exist a comprehensive compilation of Erdos open problems?" mathoverflow.net/questions/27716 $\endgroup$ May 26, 2011 at 20:52
  • 3
    $\begingroup$ A partial list of problems with monetary awards is available at: math.niu.edu/~rusin/known-math/93_back/prizes.erd $\endgroup$
    – user1073
    May 27, 2011 at 1:16
  • 17
    $\begingroup$ @Maurizio: I'm wondering what makes you so sure of that? $\endgroup$
    – Todd Trimble
    May 27, 2011 at 21:47
  • 7
    $\begingroup$ @Todd: Presumably the fact that this is stronger than the Green-Tao theorem (though I have no idea how it compares in strength to what's in the guts of Green and Tao's proof). $\endgroup$ Jul 13, 2013 at 0:11
25
$\begingroup$

John Conway has prize money out for various problems, such as $1000 for the thrackle conjecture.

John Conway's list of five $1000 problems can be found in this oeis document; the document was recently updated on June 12, 2017. The problems are restated below:

  1. Who wins in Sylver Coinage after player one names 16?

  2. Is there a coloring of the edges of $K_{99}$ red or blue in which every red edge belongs to a unique red triangle and every blue edge to a unique blue quadrilateral?

  3. Can a thrackle have more edges than vertices?

  4. If a set of points in the plane contains one point in every convex region of area 1, then must it have pairs of points at arbitrarily small distances?

  5. [Solved] Does the "climb to a prime" operation always end at a prime? Answer: no, the number 13532385396179 is a non-prime fixed point.

$\endgroup$
3
  • 3
    $\begingroup$ I added a description of Conway's five problems, including thrackle and the others, one (the silliest) of which was recently solved. I hope this is helpful to someone else. $\endgroup$ Jun 19, 2017 at 20:49
  • $\begingroup$ Problem 2 also has a different interpretation ("every blue edge is the diagonal of a unique red quadrilateral"), considered here: mathoverflow.net/a/162592/61197 $\endgroup$ Feb 24, 2018 at 13:04
  • 1
    $\begingroup$ $13532385396179 = 13\cdot 53^2\cdot 3853\cdot 96179$. $\endgroup$ Jan 27, 2020 at 22:32
21
$\begingroup$

The $3n+1$ Conjecture has some money assigned to it.

Define $T(n) = n/2$ when $n$ is even and $3n+1$ when $n$ is odd.

For any positive integer $n$ does there exist a positive integer $N$, such that $T^N(n) = 1$?

The origin of this precise question seems to be obscure, although Lothar Collatz made similar conjectures during the 1930s1. For example, Bryan Thwaites claims to have been the first to make this conjecture in 19522, and this does not seem to have been decisively refuted. (The 1937 dates in the Wikipedia and Mathworld articles are missing citations - the Wikipedia edit dates to 7 September 2004.)

Rewards offered to date include 1000 UK pounds from Bryan Thwaites, 500 US dollars from Paul Erdos, and 50 dollars (Canadian?) from H.S.M. Coxeter1.

Update: In July 2021, a Japanese firm offered 120 million yen for a proof.

  1. Lagarias, The $3x+1$ problem and its generalizations Am. Math. Monthly 92 (1985) 3-23.
  2. Bryan Thwaites, Two conjectures or how to win £1100. Math. Gazette 80 (1996) 35-36.
$\endgroup$
9
  • 3
    $\begingroup$ The statement is not correct as $N$ must be allowed to depend on $n$. Is there documentation for Halmos' offer? Did the offer expire with the professor? Not that I expect anyone to collect on it any time soon.... $\endgroup$ May 27, 2011 at 5:41
  • 1
    $\begingroup$ As the conjecture is stated, False as $\forall N$, $T^N(2^{N+1}) = 2 \neq 1$ but I doubt I'll get \$500 for stating that. $\endgroup$
    – Mark Bell
    May 27, 2011 at 9:45
  • 4
    $\begingroup$ 500 double dollars. I feel like I just walked into a trigun episode. $\endgroup$ May 27, 2011 at 14:09
  • 2
    $\begingroup$ @Daniel, ordinarily I'd say, if Lagarias says so, it must be true, but I'm disappointed that he doesn't give any reference. $\endgroup$ May 28, 2011 at 5:49
  • 1
    $\begingroup$ Zeilberger recently put $500 in a donation to the OEIS if a part of Collatz conjecture is solved, see arxiv.org/abs/1401.1532 $\endgroup$ Jan 24, 2014 at 13:31
19
$\begingroup$

See http://michel.talagrand.net/prizes/ for a total of $\$7000$ offered by Michel Talagrand for a solution of three problems. In particular $\$5000$ for the "Bernoulli conjecture". You may also be interested in the following picture of Mazur awarding Per Enflo a live goose as promised for the solution of the approximation problem. http://en.wikipedia.org/wiki/File:MazurGes.jpg

$\endgroup$
1
  • 1
    $\begingroup$ A quote from the link on "Bernoulli conjecture": You are too late: W. Bednorz and R. Latala solved t he problem at the end of 2012, just in time so that it can be included in my forthcoming book ‘’Upper and lower bounds...’’ Their proof is simply stunningly beautiful. $\endgroup$
    – Michael
    Oct 24, 2019 at 16:19
18
$\begingroup$

Yesterday, Terence Tao offered a 10.000$ prize to answer a question on large gaps in prime numbers. In particular, it's on improving their recent findings - and Terence Tao says that "this appears to be the limit of current technology". As far as I know it's the first kind of such a prize he offers.

$\endgroup$
13
$\begingroup$

J.-B. Zuber offered respectively 1, 2 and 3 bottles of Champagne for the classification of finite quantum subgroups of $SU_q(3)$, $SU_q(4)$, and $SU_q(5)$, respectively.

Ocneanu solved the first two cases, but as far as I know the problem for $SU_q(5)$ is still open.

$\endgroup$
13
$\begingroup$

Gerard Cornuejols offers $5000 for the first proof (or refutation) of each of the 18 conjectures in his 2001 book "Combinatorial Optimization: Packing and Covering". Six of the conjectures have been resolved so far, five - by Maria Chudnovsky, Paul Seymour and coauthors.

$\endgroup$
1
  • 1
    $\begingroup$ The reward has a time limit of 2020, so it is now expired. $\endgroup$ Oct 31, 2022 at 22:48
12
$\begingroup$

I am not sure if he would still be willing to pay out, but Vaughan Pratt offers 2000 smackers for the solution to the following:

http://thue.stanford.edu/puzzle.html

Let D be a set of subsets of a set A with the following three properties.

(i) D contains A and the empty set.

(ii) Let C be any set of pairs (a,b), a,b in A, such that for all a in A, the sets {b | (a,b) is in C} and {b | (b,a) is in C} are in D. Then {b | (b,b) is in C} is in D.

(iii) (T1) For any two distinct elements a,b of A, D contains a set containing a but not b, and another containing b but not a.

The set D consisting of all subsets of A evidently satisfies (i)-(iii). Does any other set of subsets of A do so?

$\endgroup$
9
  • 4
    $\begingroup$ If smackers is a synonym for kisses, I'm not so sure I want to work in the same field as this problem. Gerhard "Choosy About Who He Kisses" Paseman, 2011.05.26 $\endgroup$ May 27, 2011 at 0:05
  • 2
    $\begingroup$ According to thefreedictionary.com, smacker = $1 or £1. Which is a relief, 'cos my first thought was that it had something to do with smack. Which would be scandalous, of course. ;) $\endgroup$ May 27, 2011 at 1:25
  • 7
    $\begingroup$ Just so people are aware, this problem has been solved (in the negative). $\endgroup$ May 2, 2017 at 18:45
  • 4
    $\begingroup$ @PaceNielsen Ah, I see it is solved in your note math.berkeley.edu/~gbergman/papers/crossword.pdf. Did Vaughan give you your reward? $\endgroup$ May 2, 2017 at 21:54
  • 3
    $\begingroup$ While I admit that I started working on the problem only after first reading this post and seeing the large prize amount, after solving it that was reward enough. $\endgroup$ May 2, 2017 at 22:00
10
$\begingroup$

A. Bressan has advertised two monetary rewards of $500 each for solutions to problems on mixing flows and blocking problems.

The first problem was unsolved as of Jan. 15, 2011, although progress in relevant directions is noted in the linked announcement. The second problem was announced on Jan. 19, 2011.

$\endgroup$
10
$\begingroup$

I remember reading in Havil's book Gamma that supposidly Hardy was willing to offer his Savilian Chair at Oxford University to anyone who could prove that the Euler Mascheroni constant is irrational. I wonder if this offer still stands?

$\endgroup$
1
  • 7
    $\begingroup$ Page 52 of Havil's book, but no reference given there. Did Hardy really make this offer, even in jest? $\endgroup$ May 30, 2011 at 0:28
9
$\begingroup$

Guy, Unsolved Problems In Number Theory, 3rd edition, A12 (page 45) says "Selfridge, Wagstaff & Pomerance offer 500.00 + 100.00 + 20.00 for a composite $n\equiv3{\rm\ or\ }7\pmod{10}$ which divides both $2^n-2$ and the Fibonacci number $u_{n+1}$ or 20.00 + 100.00 + 500.00 for a proof that there is no such $n$." John Selfridge having left us, I do not know whether his part of the offer still applies.

$\endgroup$
1
  • 5
    $\begingroup$ "John Selfridge having left us..." Oh dear, I didn't know that. He was my office-mate for a while when I was at Macquarie, and we had a lot of fun together. RIP... $\endgroup$
    – Todd Trimble
    May 28, 2011 at 11:11
8
$\begingroup$

As it is pointed out in a footnote in A. Zorich's survey "Flat surfaces", Anatole Katok promised (on behalf of the Center for Dynamics and Geometry of Penn State University) a prize of 10,000 euros for the solution of the problem of finding periodic orbits and describing the behavior of generic orbits of billiards in (all/almost all) triangular tables. See page 13 of the ArXiv version of the survey for more comments.

$\endgroup$
8
$\begingroup$

(Both these prizes have since been claimed, sorry!)

Scott Aaaronson offered \$200 for an oracle relative to which BQP is not contained in PH, or $100 for an oracle relative to which BQP is not contained in AM. (Now claimed.)

Bill Gasarch offered $289 for a 4-coloring of a 17-by-17 grid such that there is no rectangle with all four corners the same color. (Now claimed; and in fact this problem, of 4-coloring grids, has since been solved completely; see the comments for the 12x21 case.)

$\endgroup$
2
  • $\begingroup$ Was not the first one settled by Raz and Tal? See shtetl-optimized $\endgroup$
    – Mark S
    Oct 19, 2019 at 12:16
  • $\begingroup$ Good point, it was! Will edit. $\endgroup$ Oct 24, 2019 at 5:52
8
$\begingroup$

Domokos and Várkonyi offer $\\\$\frac{1,000,000}{F + E + V − 2}$ for the polyhedral Gömböc with the minimal number of flat faces, where $F,E,V$ are the number of faces, edges and vertices of the polyhedron.

$\endgroup$
7
$\begingroup$

Edit: This problem has since been solved (and generalized) by Aleksi Saarela.

Stepan Holub is offering €200 for a solution to the following problem:

Do there exist $n\ge 2$ and nonempty words $u_1,\ldots,u_n$ such that

$(u_1 \ldots u_n)^2 = u_1^2 \ldots u_n^2$ and

$(u_1 \ldots u_n)^3 = u_1^3 \ldots u_n^3$

but the $u_i$ don't all commute with one another?

(I guess the $n\ge 2$ and nonemptiness requirement are technically redundant.)

Source: https://www.student.cs.uwaterloo.ca/~cs462/openproblems.html

New problem from the same page:

Jeffrey Shallit offers \$100 for any significantly improved bounds on the distinguishing strings problem. Which is: Given two words of length at most $n$, what is the size of the smallest DFA that accepts one and rejects the other? Current bounds are that $\Omega(\log n)$ states are needed and $O(n^{2/5} (\log n)^{3/5})$ are sufficient.

(That page also lists a third problem with a monetary award but it has since been claimed so I won't bother listing it here! It was problem 24 there, though.)

$\endgroup$
1
  • $\begingroup$ Note that n should be $\ge 3$ then, because else the first equation reduces to $u_2 u_1 = u_1 u_2$ $\endgroup$ Feb 7, 2017 at 14:48
6
$\begingroup$

Jeff Shallit recently offered, in a question on this website, 200 dollars for improving bounds for Pierce expansions.

$\endgroup$
6
$\begingroup$

Since the thread has been just bumped to the front page, I take it as an opportunity to add a link to Zhi-Wei Sun's homepage, where several problems with monetary rewards are listed. Most notably, Zhi-Wei Sun is offering 2400 \$ for his "24-Conjecture" (that any natural number can be written as the sum of squares of four nonnegative integers $x$, $y$, $z$, and $w$ such that both $x$ and $x+24y$ are squares) and 1350 \$ for his "1-3-5-Conjecture" (that any natural number can be written as the sum of squares of four nonnegative integers $x$, $y$, $z$, and $w$ such that $x+3y+5z$ is also a square).

$\endgroup$
1
  • $\begingroup$ The 1-3-5 Conjecture is not listed on the page anymore. There is a Little 1-3-5 Conjecture (with a \$$135$ prize). The 24-Conjecture is still on the list. $\endgroup$ Feb 6, 2021 at 14:37
5
$\begingroup$

Recently Ian Morrison issued a 100 dollar prize for the construction of an effective divisor on $\overline M_g$ with slope less than 6 (See the recent preprint of Chen, Farkas and Morrison).

$\endgroup$
5
$\begingroup$

In this paper of Foreman, there are some problems with interesting reward formulae.

Question(Steel) Working in $\rm ZFC$, either
(a) show that if $\rm ZFC$ plus “there is a singular strong limit $\kappa$ such that $\neg \square_\kappa$” is consistent, then so is $\rm ZFC$ plus “there is a superstrong cardinal”, or
(b) show that if there is a superstrong cardinal, then $\rm ZFC$ plus “there is a singular strong limit κ such that $\neg \square_\kappa$” is consistent.

Reward: For (b), $\\\$300$. For (a), $\\\$4000−500x$, where $x$ is the time in years from May 1, 2004 to the submission of a manuscript with a correct, complete proof. UC Berkeley faculty are not eligible for the reward!

Question (Woodin) Suppose that there is an extendible cardinal. Must $\rm HOD$ compute the successor correctly for some (uncountable) cardinal?

Prize: $$\\\$1000\times[{\rm max(min}(n, 10 − n), 1)]$$ where $$n = (\text{calender year of submission}) − 2004$$.
Terms: Collect if a correct proof is given for either “yes”, or if a correct proof is given that the failure implies the consistency with $\rm ZFC$ of the large cardinal $I0$ of Kanamori’s book. (Details: Clay rules)

$\endgroup$
2
  • 7
    $\begingroup$ Jeez, if anyone nowadays proved (a) in that question of Steel, they'd be in for a big fine. $\endgroup$ Feb 5, 2021 at 15:02
  • 1
    $\begingroup$ @SamHopkins maybe this is a way to keep people far from the problem! $\endgroup$
    – Rahman. M
    Feb 5, 2021 at 15:06
4
$\begingroup$

$\textbf{Prize Problem in Coding Theory}$

This is the title of the paper by $\textit{Jon-Lark Kim}$. This paper is about a long standing open problem in coding theory that is related to some other fields in mathematics.

The question is:

$\text{Is there Type II binary linear codes with parameters $[72,36,16]$?}$

This was officially suggested by Sloane in 1973. If it exists, then the codewords of weight 16 form a $5-(72,16,78)$ design whose existence is unknown.

The writer of the paper say that: It is the only coding problem with monetary prizes. The detail can be found from $$\text{http://academic.scranton.edu/faculty/doughertys1/}.$$

The prizes are as follows:

1) N.J.A. Sloane offers $10 (1973) - still valid (confirmed in 2006).

It is also valid, I think.

2) F.J. MacWilliams offered $10 (1977) - invalid now.

I do not know why it is invalid?

3) S.T. Dougherty offers $100 for the existence of this code.

4) M. Harada offers $200 for the nonexistence of this code.

I hope someone can win this prize until I am alive.

$\endgroup$
2
  • $\begingroup$ As for why 2) is no longer valid, I suspect it's because MacWilliams died in 1990. en.wikipedia.org/wiki/Jessie_MacWilliams $\endgroup$ Dec 17, 2014 at 20:42
  • $\begingroup$ Dear Voloch, I think you are right. But it is a little strange for me, why mathematicians should forget the heritage of the great mathematician like MacWiliams? It is just $10$ dollar, and I think someone must accept it and pay it in the future. If I can pay, I will accept it, maybe a good news. $\endgroup$
    – Shahrooz
    Dec 18, 2014 at 10:48
3
$\begingroup$

I'm a computer scientist by trade, but I really just enjoy working on open mathematical problems in my free time. Kimberling's page is pretty nice as you mentioned, I was able to knock one of them out (a minor one, the Swappage Problem), and always look forward to when new ones are posted.

One of the best places I have found for open problems is probably open problem garden. The site is frequently updated with new problems ranging from graph theory, theoretical computer science, algebra, etc. The nice thing is that the problems are also ranked by relative difficulty.

As for cash: A number of the problems DO offer some type of cash bounty (as clearly indicated in the summary section for the problem next to "Prize" text if it exists). Problems such as The Erdos-Turan conjecture on additive bases offer cash incentives for solving.

There are also other problems listed that offer monetary compensation and are posted periodically throughout the site. However, sifting through the problems can be time consuming as many of them do not offer cash incentives.

$\endgroup$
2
  • 5
    $\begingroup$ If you can edit the answer so that it properly answers the question, please do so. Other MathOverflow questions talk about open problem lists; this one talks about those with a cash bounty (historical or present). Gerhard "Email Me About System Design" Paseman, 2011.06.20 $\endgroup$ Jun 21, 2011 at 4:29
  • $\begingroup$ While not all the problems listed here offer cash bounty, a number of them do. I'll rephrase the post accordingly. $\endgroup$ Jun 21, 2011 at 16:54
3
$\begingroup$

The website multimagie.com run by Christian Boyer offers prizes on multiple seemingly elementary problems on magic squares. See the page enigmas for the full list.

I believe the oldest (with a €100 reward offered in 1996 by Martin Gardner) is the following:

Question. Does there exist a $3\times 3$ magic square whose entries are pairwise distinct square integers?

The variant where only 8 of the entries are squares, or 7 are squares but disallowing a single known solution, is offered an additional €1000 by Boyer.

This seems like an innocuous question, but the Diophantine equation for the question above is equivalent to finding rational points on a general type complete intersection surface $X \subseteq \mathbf P^8$ of degree $(2,2,2,2,2,2)$, away from a union of rational curves $C \subseteq X$ (the loci where two or more coordinates coincide). This falls within the scope of the Bombieri–Lang conjecture. As far as I'm aware, there is not a single known example where we know this conjecture for $X$ simply connected with $X(\mathbf Q)\neq \varnothing$, so a solution to the above problem appears out of reach with current methods in arithmetic geometry.

$\endgroup$
2
$\begingroup$

$$50000 - each year around the New Year - there is a challenge on combinatorial optimization problems on Kaggle.

For example ongoing (December 2023 - January 2024: "Santa 2023 - The Polytope Permutation Puzzle") is challenge to propose algorithms/solutions for Rubik's cube like puzzles for a given list of configurations. Mathematically speaking it means - we are asked to find the shortest path(s) between two given nodes of the Cayley graph of the Rubik's cube group (or coset, or some of its modifications). For puzzles of large size - optimal algorithms are - unknown - so the solutions are potentially contributing to the resolving that open problem. About 390 pairs of nodes are given. Participants are evaluated how short paths they propose - the shorter the better - sum of lengths over all pairs is a score. Some relevant papers are: https://www.arxiv.org/abs/1906.04062, https://arxiv.org/abs/2106.03157, etc...

PS

Kaggle - is a platform which organizers data science related challenge - currently belongs to Google. It is in a sense the greatest place to learn (about data science/optimization) because participants share a lot their ideas/codes/... in some sense each competition is in part a kind of "Polymath" ("Poly-data-science") project for the community. Moreover there is "gamification" system to promote sharing of knowledge/ideas/code - if you share code/idea(post on Kaggle forum) which is valuable for the community - you gain upvotes and become "expert/master/grandmaster" - titles appreciated in "real world" (for example for hiring on data science positions). There is new grant program for researches - Kaggle can sponsor some research related competitions - may be some Mathoverflow colleagues can apply for that !

PSPS

2022 - https://www.kaggle.com/competitions/santa-2022

2021 - https://www.kaggle.com/competitions/santa-2021

2020 - https://www.kaggle.com/competitions/santa-2020

2019 - https://www.kaggle.com/competitions/santa-2019-revenge-of-the-accountants

2018 - https://www.kaggle.com/competitions/traveling-santa-2018-prime-paths

PSPSPS

For the particular Santa 2023 challenge - here are some my posts: one is related to mathoverflow question: "Growth of wreath group puzzles", and another "Task reformulation - everyone can understand" - might help someone to get in, (would be happy to discuss if someone is interested in).

$\endgroup$
2
  • 1
    $\begingroup$ I think this is not really an answer to the question. In these challenges, the rewards are not for solutions to an open problem, but only for best attempts. $\endgroup$ Jan 6 at 16:05
  • $\begingroup$ @R.vanDobbendeBruyn So those who find solution to that open problem - will get the prize - so it fits the question. If no one finds optimal algorithm - other people get prize - but there was no such restriction in the question formulation. In general that is quite an interesting activity and Mathoverlow community I think should be informed about that. Setting subjective borders on what fits the question what is not - not a good policy . "Assume a good will". $\endgroup$ Jan 6 at 18:38
1
$\begingroup$

Recently, I have offered 100 € cash prize for a proof of the conjectured primality test which is formulated in this post.

$\endgroup$
1
  • 2
    $\begingroup$ The OP explicitly states not being interested in "new pledges of sums of money just here". $\endgroup$
    – Alex M.
    Jul 31, 2021 at 15:22
1
$\begingroup$

Mario Krenn is offering $€3,000$ (roughly $3,300) for the answer of a question on graph colorings, which are derived from the perfect matchings of the graph. It was recently described by Dustin Mixon.

The specific question deals with the existence of monochromatic colorings of edge-colored weighted graphs. The question has been asked here at MathOverflow a year ago, and the link to the reward was added recently.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.