Hacker News Reader

Comment by greyman | Hacker News Reader

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?

View on HN

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

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

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

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

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

Close enough.

- a mathematician

Reply on news.ycombinator.com