20
$\begingroup$

Van der Waerden's conjecture (now a theorem of Egorychev and Falikman) states that the permanent of a doubly stochastic matrix is at least $n!/n^n$.

The Wikipedia article, as well as many other sources, provides the following citation:

B. L. van der Waerden, "Aufgabe 45", Jber. Deutsch. Math.-Verein., 35 (1926), 117.

However, I just went to the library to look up volume 35 of Jahresbericht der Deutschen Mathematiker-Vereinigung, and page 117 lies right smack in the middle of a paper by Karl Menger, "Bericht über die Dimensionstheorie." There is nothing remotely resembling Van der Waerden's conjecture on page 117.

In the book A Course in Combinatorics by J. H. van Lint and R. M. Wilson, there is a chapter on Van der Waerden's conjecture, and there is a footnote saying that Van der Waerden told one of the authors that he had never made any such conjecture.

So maybe Van der Waerden never made the conjecture? Or did he make the conjecture and then forget about it, with the citation getting garbled somewhere along the line? The earliest citation to "Aufgabe 45" in Google Scholar seems to be from 1960, so maybe that's when the error was introduced. But I don't know how to search for earlier citations to a possibly non-existent reference by Van der Waerden.

ADDENDUM (prompted by Mark Sapir's comments to Matt F.'s answer below): Here's what Van Lint and Wilson say (Chapter 12, 2nd edition):

In 1926, B. L. van der Waerden proposed as a problem to determine the minimal permanent among all doubly stochastic matrices. It was natural to assume that this minimum is per $J_n = n!\,n^{-n}$. … The assertion [that this minimum is uniquely achieved by the constant matrix] became known as the ‘Van der Waerden conjecture’ (although in 1969 he told one of the present authors that he had not heard this name before and that he had made no such conjecture).

So it sounds like Van der Waerden himself saw a distinction between asking for the minimum value, and conjecturing what the minimum value is (or conjecturing that the minimum value is uniquely attained by the constant matrix).

Improve this question
$\endgroup$
1
  • $\begingroup$ Obligatory mention of Stigler's Law and Boyer's Corollary. $\endgroup$
    – Nate Eldredge
    Commented Oct 10, 2019 at 23:24

1 Answer 1

Reset to default
16
$\begingroup$

Aufgabe 45 is in the second Abteilung of volume 35, indeed on page 117, as here. He was asking about permanents, but rather than asking for a proof about $n!/n^n$, he asked for the determination of a minimum.

enter image description here

Translation: "The Function $Q\cdots$ (summing over all permutations of the indices $1,\ldots,n$), under the conditions $a_{ik}\cdots$, can only take positive values (Dénes König, Graphs and their Applications #2, Math. Ann. 77, p. 47). The minimum of the function is (under the given conditions) to be determined."

Improve this answer
$\endgroup$
9
  • 4
    $\begingroup$ That site has an incomplete copy of the volume. It's also missing the volume's table of contents, which is available at the Gottingen site and which pointed me to the second Abteilung. $\endgroup$
    – user44143
    Commented Oct 10, 2019 at 23:09
  • 2
    $\begingroup$ So the answer is that v.d. Waerden did not formulate the conjecture? $\endgroup$
    – user6976
    Commented Oct 10, 2019 at 23:19
  • 2
    $\begingroup$ Strong evidence that he didn't wrote it down in a published paper? He died in 1996 so some living people might still witness if he made the conjecture explicit in public talks. Also, one can also track the first written references to this question/conjecture and when/ by who it was first referred to as conjecture. $\endgroup$
    – YCor
    Commented Oct 11, 2019 at 10:01
  • 1
    $\begingroup$ The paper he cites by König is also freely available online, digizeitschriften.de/dms/img/…, and says: "Wenn in einer Determinante aus nicht negativen [ganzen] Zahlen jede Reihe und jede Spalte dieselbe positive Summe ergibt, so ist wenigstens ein Glied der Determinante von Null verschieden", i.e. "if in a determinant with non-negative (whole) numbers every row and every column has the same positive sum, then at least one element of the determinant differs from zero". $\endgroup$
    – user44143
    Commented Oct 11, 2019 at 13:41
  • 3
    $\begingroup$ @MarkSapir, the two obvious candidates for extrema are the identity matrix and the matrix with all entries equal. So van der Waerden's novelty was asking about bounds for the permanent, and after that the conjecture is obvious -- the difference between the question and the conjecture is too small to give credit for the conjecture to anyone else. $\endgroup$
    – user44143
    Commented Oct 11, 2019 at 13:49

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .