The author advocates two specific mathematical notations from his popular course and joint textbook, "Concrete Mathematics". The first of these, extending an idea of Iverson, is the notation "[P]" for the function which is 1 when the Boolean condition P is true and 0 otherwise. This notation can encourage and clarify the use of characteristic functions and Kronecker deltas in sums and integrals. The second notation puts Stirling numbers on the same footing as binomial coefficients. Since binomial coefficients are written on two lines in parentheses and read "n choose k", Stirling numbers of the first kind should be written on two lines in brackets and read "n cycle k", while Stirling numbers of the second kind should be written in braces and read "n subset k". (I might say "n partition k".) The written form was first suggested by Imanuel Marx. The virtues of this notation are that Stirling partition numbers frequently appear in combinatorics, and that it more clearly presents functional relations similar to those satisfied by binomial coefficients.
Metadata: arXiv. Abstracts retain their original authors’ rights.
In the conversation
Original HN comments, with labels from simple text rules. A label describes the whole comment and may miss context or irony. Read the discussion to make up your own mind. About the labels
Note that the abstract at https://arxiv.org/abs/math/9205211 is not by Knuth (it says "Abstract added by Greg Kuperberg" in small print).
Anyway, the "two notes" of the title are about:
1. Iverson bracket notation: writing say "[x ≥ 5]" to mean "1 if x ≥ 5, and 0 otherwise" (casting the boolean condition to a 0–1 integer, in programming terms). He has good examples of how it seems unnecessary or innocuous at first (one starts out writing "1" for an indicator function, or putting it in subscripts), but as you do more and more manipulations of sums it grows on you and you realize how useful the convention is. (IMO you can work through the book Concrete Mathematics, to…
Read the full comment
experience this for yourself.) Incidentally, using square brackets seems to be something Knuth introduced; Iverson himself had used regular parentheses.
1a. There's a historical sidenote on the expression 0^0, with an impassioned defence of defining it to be 1. (It's undefined as a limiting form, but for the value itself it makes a lot of sense to define it as 1. Some people don't seem to like this. Boo.)
2. Stirling numbers. Here, Knuth and co-authors did away with the ever-confusing "Stirling numbers of the first kind" and notations like "S(n, k)", and promoted the names "Stirling subset numbers" and "Stirling cycle numbers" (with the interpretation in terms of set partitions and permutation cycles respectively), and the notation that is slowly catching on (thankfully). (See the paper or, again, read Concrete Mathematics for more fun.)
2a. There's also another sidenote about rising and falling factorial powers; again this notation is also slowly catching on.
There's also a video on YouTube of him giving a talk on notation from October 2003, where covers much of this (and more): https://www.youtube.com/watch?v=KjbuyB4dQa0 (Someone's notes about this video: https://crypto.stanford.edu/pbc/notes/misc/notation.html)
Knuth [0] discusses in more detail some advantages of indicator notation, in particular that, when you eliminate the limits on summations, it makes it much easier to do algebra on summations.
[0] https://arxiv.org/abs/math/9205211
I don't know if Knuth popularized it, but it's somewhat common in combinatorics. Similar idea to using indicator functions when doing change of variables in calculus.
https://arxiv.org/abs/math/9205211
This seems almost exactly backwards to me.
“Geometric” proofs (i.e. based on spatial reasoning) are fast and fluid, relying on an imagined spatial configuration which can be seen all at once.
“Algebraic” proofs (i.e. based on symbol manipulation) are serialized and low-bandwidth, and working them out takes a significant amount of laborious fiddling with symbols on paper, and is almost impossible to work out mentally except in nearly trivial cases.
The benefit of the “algebraic” version is often that putting in that labor can often yield a result even when the prover has no special insight. That is, the method can be more reliably carried out by non-geniuses (assuming that…
Read the full comment
the prover has sufficient patience and stamina), because the work can be broken into small individually opaque steps and written down on paper instead of needing to be seen all at once.
To the extent algebraic proofs are fast/elegant/obvious, they generally rely on a clear 2-dimensional notation on paper where it is easy to see how to simplify the parts based on visual patterns known via extensive past experience. Cf. https://arxiv.org/abs/math/9205211
This is a great example. Wikipedia has the same one with isolines demonstrating this point in the 0^0 subsection of the exponentiation article, here:
https://en.m.wikipedia.org/wiki/Exponentiation#Continuous_ex...
With the caveat:
"However, under certain conditions, such as when f and g are both analytic functions and f is positive on the open interval (0, b) for some positive b, the limit approaching from the right is always 1.[26][27][28]"
Also, definitely take note of Knuth's argument, because while you might feel strongly that indeterminate is the right answer right now, there are big implications for allowing other choices. (And NB: indeterminate vs undefined)
"The…
Read the full comment
debate stopped there, apparently with the conclusion that 0^0 should be undefined.
But no, no, ten thousand times no! Anybody who wants the binomial theorem to hold for at least one nonnegative integer n must believe that 0^0 = 1, for we can plug in x = 0
and y=1 to get 1 on the left and 0^0 on the right.
The number of mappings from the empty set to the empty set is 0^0. It has to be 1."
http://arxiv.org/pdf/math/9205211v1.pdf
Here's Knuth's opinion on 0^0: http://arxiv.org/pdf/math/9205211v1.pdf (on page 6)
He makes a few pretty convincing points about why it's useful to define it equal to 1, while admitting that in some sense, it's not quite as well defined as say 0+0.
Defining 0^0 = 1 is just as important in analysis as it is in combinatorics, even though analysis texts aren’t always clear that they’re making use of this fact.
• If p(x) = ∑[n=0..∞] a_n x^n is a power series, then p(0) = a_0 is its constant term, but it makes no sense to write this unless 0^0 = 1.
• The power rule d/dx [x^n] = n x^(n−1) holds for n = 1 and x = 0, but this requires 0^0 = 1.
The reason that some people believe it’s important to undefine 0^0 in analysis is that the limiting expression
lim[x → a] f(x)^g(x)
does not necessarily exist when lim[x → a] f(x) = lim[x → a] g(x) = 0. But all this means is that we have to draw a distinction between the _value_ 0^0,…
Read the full comment
which equals 1, and the indeterminate _limiting form_ 0^0, which is an abbreviation for the above type of limit.
It is not uncommon for values to evaluate differently from the corresponding limiting forms. For example, the value floor(0) equals 0, but the limiting form floor(0) is indeterminate. It may seem surprising that such a discrepancy arises for exponentiation, but all it means is that exponentiation is discontinuous at (0, 0), as it must be.
(Note however that the above limit _does_ exist with mild conditions on f and g: if f, g are complex analytic functions with f not identically zero, then the limit equals 1.)
See also Donald Knuth’s _Two notes on notation_: http://arxiv.org/abs/math/9205211.
Why link to the PDF? Better to just link to the abstract: http://arxiv.org/abs/math/9205211
Edit: To be clear, this is good practice when linking to arXiv in general. From the abstract, one can easily click through to the PDF; not so the reverse. And the abstract allows one to do things like see different versions of the paper, search for other things by the same authors, etc.
My point was that the notation should be optimized for the people using it, not for the technology used to typeset it. If the notation is suboptimal for the people then it can definitely be changed, but that's a different reason.
Note that some of these notational improvements may actually make it harder to typeset. For example, the second part of Knuth's paper "Two Notes on Notation" (https://arxiv.org/abs/math/9205211) introduced improved notation for the Stirling numbers "of the first kind" and "second kind", replacing easier-to-typeset but less informative notation like S(n,k). This notation has gained a good degree of acceptance, the paper won a writing award…
Read the full comment
(https://www.maa.org/programs/maa-awards/writing-awards/paul-...), and another paper citing it calls this “The best thing that has happened to the Stirling numbers during their 400 years of chequered history” (https://www.jstor.org/stable/2974533?seq=1). (See also a talk of his on Notation https://www.youtube.com/watch?v=KjbuyB4dQa0&list=PLoROMvodv4... for which someone has taken notes: https://crypto.stanford.edu/pbc/notes/misc/notation.html)
I think there are valid questions to be raised on which people to optimize for: whether the students encountering the notation for the first time, or the people who use it every day for years. In either case (to make my point again) it's a question about people, and not about the technology — a programming-like notation isn't better unless that's how the people who use it think (or want to think).
In response to Jaffe and Quinn [math.HO/9307227], the author discusses forms of progress in mathematics that are not captured by formal proofs of theorems, especially in his own work in the theory of foliations and geometrization of 3-manifolds and dynamical systems.
Artificial intelligence (AI) researchers have been developing and refining large language models (LLMs) that exhibit remarkable capabilities across a variety of domains and tasks, challenging our understanding of learning and cognition.