6 ms·
Harvard mathematician answers 150-year-old chess problem
- dfan 5y agoI was very surprised to see a headline involving "Harvard mathematician" and "chess problem" and find that the article was not about Noam Elkies.
- alisonkisk 5y ago
- ThinBold 5y agoNote that the preprint on arXiv dated back to July 2021.
- greyman 5y agoI 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?
- jdlqpdo 5y agoI noticed the same :-) Knowing mathematics though, it's quite likely that this result is valid only for some regimes of N, for example assymptotically
- keymone 5y agoClose enough. - a mathematician
- pfortuny 5y agoThere is the always elided “constant coefficient”, which the press release does not even mention.
- deleted 5y ago[deleted]
- kevinventullo 5y agoLooking 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.
- readthenotes1 5y agoFrom 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.
- edflsafoiewq 5y agoo(1) is some term that goes to 0 as n goes to infinity.
- knuthsat 5y agoIt'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).
- dwohnitmok 5y agoWhen 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).
- omegalulw 5y agoI 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.
- PinguTS 5y agoAlso 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.
- edflsafoiewq 5y agoThe 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.
- tromp 5y agoThe (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 https://tromp.github.io/go/gostate.pdf
- sohkamyung 5y agoAlso featured in this Quanta Magazine article [1] [1] https://www.quantamagazine.org/mathematician-answers-chess-problem-about-attacking-queens-20210921/ https://www.quantamagazine.org/mathematician-answers-chess-p...
- fjfaase 5y agoThe related OEIS sequence is https://oeis.org/A000170 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 https://github.com/preusser/q27
- dmch-1 5y agoThanks 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.
- Traster 5y agoIt 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.
- sockpuppet69 5y ago
- alisonkisk 5y ago
- mauricioc 5y agoYou 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.
- random314 5y agoGiven 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.
- OJFord 5y agoPreviously (4 months ago): https://news.ycombinator.com/item?id=28605220 https://news.ycombinator.com/item?id=28605220 Related (N-Queens is NP-hard, 4 years ago): https://news.ycombinator.com/item?id=15168867 https://news.ycombinator.com/item?id=15168867
- mauricioc 5y agoIt's worth pointing out that Bowtell and Keevash proved a similarly impressive result for the toroidal case: https://arxiv.org/abs/2109.08083 https://arxiv.org/abs/2109.08083