Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Harvard mathematician answers 150-year-old chess problem

news.harvard.edu

Post reply on HN
Print view View original

11–20 of 28 posts

Re: Harvard mathematician answers 150-year-old chess problem

#11

Post by knuthsat »

edflsafoiewq wrote: post #10
readthenotes1 wrote: post #8

Earlier quoted context omitted.

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.

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).

Re: Harvard mathematician answers 150-year-old chess problem

#12

Post by dwohnitmok »

knuthsat wrote: post #11
edflsafoiewq wrote: post #10

Earlier quoted context omitted.

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).

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).

Re: Harvard mathematician answers 150-year-old chess problem

#13

Post by tromp »

greyman wrote: post #3

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?

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

Re: Harvard mathematician answers 150-year-old chess problem

#14

Post by PinguTS »

greyman wrote: post #3

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?

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.

Re: Harvard mathematician answers 150-year-old chess problem

#15

Post by edflsafoiewq »

PinguTS wrote: post #14
greyman wrote: post #3

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?

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 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.

Re: Harvard mathematician answers 150-year-old chess problem

#17

Post by dmch-1 »

fjfaase wrote: post #16

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.

Re: Harvard mathematician answers 150-year-old chess problem

#18

Post by Traster »

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.
Post reply on HN