Harvard mathematician answers 150-year-old chess problem(news.harvard.edu)
news.harvard.edu
Harvard mathematician answers 150-year-old chess problem
https://news.harvard.edu/gazette/story/2022/01/harvard-mathematician-answers-150-year-old-chess-problem/
27 comments
It does make me chuckle the way this is reported. We answered this problem! Ok what's the answer "well about (0.143n)^n". I've figured out the value of Pi! It's about 3. Firstly, that's not an answer that's's an approximate answer, and secondly, it's wrong for a practical values of n. I really don't have the mentality of a mathematician.
You say "practical values of n", but the answer to n = 27 is already known and I would be very surprised if the final result had any practical application. The point of these problems is rarely the numerical answer, but the development of new techniques: The problem of determining the asymptotic growth of this number is studied because it is a good playground for sharpening mathematical tools and methods.
In this sense, the asymptotic problem is an interesting one, and it was solved. Now that the main term is characterized, people can investigate sharper estimates.
The problem of determining an efficient algorithm for every n, on the other hand, is just hopeless, which means that it is not interesting for the purpose I described above. Studying "small" n (up to 40, say) is not useless, though, if it leads to algorithmic breakthroughs (in SAT solving, for example). It is, however, an "orthogonal" problem, in the sense that it requires a completely different set of techniques.
To illustrate my point: If the answer for n = 50 appeared out of nowhere, would people care about the number itself? I bet people would be much more interested in how it was done.
The problem of determining an efficient algorithm for every n, on the other hand, is just hopeless, which means that it is not interesting for the purpose I described above. Studying "small" n (up to 40, say) is not useless, though, if it leads to algorithmic breakthroughs (in SAT solving, for example). It is, however, an "orthogonal" problem, in the sense that it requires a completely different set of techniques.
To illustrate my point: If the answer for n = 50 appeared out of nowhere, would people care about the number itself? I bet people would be much more interested in how it was done.
Given the number of significant digits, the answer is closer to stating that pi is approximately equal to 3.14
I agree, you don't have the mentality of a mathematician.
I agree, you don't have the mentality of a mathematician.
Also featured in this Quanta Magazine article [1]
[1] https://www.quantamagazine.org/mathematician-answers-chess-p...
[1] https://www.quantamagazine.org/mathematician-answers-chess-p...
The related OEIS sequence is https://oeis.org/A000170. It only gives exact values for n up to and including 27. The value for n = 27 was calculated with the help of an FPGA. See: https://github.com/preusser/q27
Thanks to this I know that there is exactly 1 way of positioning 0 queens on 0x0 chessboard without any two of them attacking each other.
Previously (4 months ago): https://news.ycombinator.com/item?id=28605220
Related (N-Queens is NP-hard, 4 years ago): https://news.ycombinator.com/item?id=15168867
Related (N-Queens is NP-hard, 4 years ago): https://news.ycombinator.com/item?id=15168867
I must be missing something, but when I take the formula (0.143n)^n, for n=8 the result is 2.933, while it should be around 92?
I noticed the same :-)
Knowing mathematics though, it's quite likely that this result is valid only for some regimes of N, for example assymptotically
Knowing mathematics though, it's quite likely that this result is valid only for some regimes of N, for example assymptotically
From the paper
We show that there exists a constant α = 1.942±3×10−3 such that Q(n) = ((1 ± o(1))ne^−α)^n
Dunno what o(1) is.
We show that there exists a constant α = 1.942±3×10−3 such that Q(n) = ((1 ± o(1))ne^−α)^n
Dunno what o(1) is.
o(1) is some term that goes to 0 as n goes to infinity.
It's little o notation. It does not depend on n.
For example x^2 is in O(x^2) but is not in o(x^2).
For example x^2 is in O(x^2) but is not in o(x^2).
When used in that equation it's meant to implicitly depend on n as edflsafoiewq points out. o(1) stands for o(f(n)) where f(n) = 1. Hence any function g(x) in the family of functions represented by o(1) must be less than c * f(x) for every positive c and all x greater than some m. This is exactly the statement that any function in the family of functions o(1) must tend to zero.
Whenever you see big-O/little-O/theta notation there is always an implied dependent variable, even for o(1)/O(1)/Theta(1).
Whenever you see big-O/little-O/theta notation there is always an implied dependent variable, even for o(1)/O(1)/Theta(1).
I think a nuance people are missing is that for big O, it is sufficient for the existence of any positive C and x, but for small o there must always exist an x for every c.
The (0.143n)^n leaves out some smaller order factors that would help to give more accurate results. The situation is very similar to the number of legal Go positions on an nxn board [1], which Theorem 6 in that paper states as
L(m, n) ~ A * B^{m+n} * L^{mn(1 + O(mφm))}
[1] https://tromp.github.io/go/gostate.pdf
L(m, n) ~ A * B^{m+n} * L^{mn(1 + O(mφm))}
[1] https://tromp.github.io/go/gostate.pdf
Looking at the actual result, you can really only expect that (92^(1/8))/8 should be close to 0.143. It works out to about 0.22, which is less than double. The result actually says this ratio tends to 1 as n tends to infinity.
Also wondering where the authors of the article got this formula from. Because it is not in the paper. At least not that obvious.
The paper discusses an upper bound and a lower bound, but not a singular formula.
The paper discusses an upper bound and a lower bound, but not a singular formula.
The paper gives Q(n) = ( (1+o(1)) e^(-α) n )^n. (1+o(1)) is about 1 for large n. e^(-α) is about e^(-1.942) = 0.143. Inserting gives (0.143 n)^n.
There is the always elided “constant coefficient”, which the press release does not even mention.
[deleted]
Close enough.
- a mathematician
- a mathematician
It's worth pointing out that Bowtell and Keevash proved a similarly impressive result for the toroidal case: https://arxiv.org/abs/2109.08083
I was very surprised to see a headline involving "Harvard mathematician" and "chess problem" and find that the article was not about Noam Elkies.
Note that the preprint on arXiv dated back to July 2021.