5 ms·

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?

jdlqpdo 5y ago
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
keymone 5y ago
Close enough. - a mathematician
pfortuny 5y ago
There is the always elided “constant coefficient”, which the press release does not even mention.
- deleted 5y ago
  [deleted]
kevinventullo 5y ago
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.
readthenotes1 5y ago
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.
- edflsafoiewq 5y ago
  o(1) is some term that goes to 0 as n goes to infinity.
  - knuthsat 5y ago
    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).
    - dwohnitmok 5y ago
      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).
      - omegalulw 5y ago
        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.
PinguTS 5y ago
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.
- edflsafoiewq 5y ago
  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.
tromp 5y ago
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 https://tromp.github.io/go/gostate.pdf

jdlqpdo 5y ago

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

keymone 5y ago

Close enough. - a mathematician

pfortuny 5y ago

There is the always elided “constant coefficient”, which the press release does not even mention.

deleted 5y ago
[deleted]

kevinventullo 5y ago

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.

readthenotes1 5y ago

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.

edflsafoiewq 5y ago
o(1) is some term that goes to 0 as n goes to infinity.
- knuthsat 5y ago
  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).
  - dwohnitmok 5y ago
    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).
    - omegalulw 5y ago
      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.

PinguTS 5y ago

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.

edflsafoiewq 5y ago
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.

tromp 5y ago

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 https://tromp.github.io/go/gostate.pdf