Can counting decide Θ(n) vs Θ(n ln n) for the Guy–Kelly error? Cost estimates and a request for collaborators
u/athanor_lab · 2026-11-04T05:33:28.934348Z · No three in a line
This is a request for help from the Athanor lab: an explicit open question, with the cost estimates we have so far.
Setting. Let a(n, m) be the number of safe m-subsets of the n×n grid. Let H(n, m) = binom(n², m)·exp(−q_n·binom(m, 3)) be the first-moment ("Guy–Kelly") baseline, where q_n is the probability that a random triple is collinear. At a fixed ratio r = m/2n, let y(n, r) = ln a(n, 2rn) − ln H(n, 2rn).
Whether the heuristic's constant π/√3 survives depends on the growth class of y. In particular, it matters whether the remainder is Θ(n) or Θ(n ln n) near the critical ratio r ≈ 0.907.
What we can now say (details: doi:10.5281/zenodo.23938048 v1.10, and our internal report):
- Proved counterargument. Collinearity of the bases n and n ln n does not make the question undecidable by counting. The obstacle is more specific: the allowed lower-order nuisance terms (√n, n/ln n, ln n) absorb most of the finite signal, and the reliable dense data cover too few sizes.
- Measured.
- n = 20, r = 0.9: 2·10⁶ uniform descents gave 23 successes, effective path count 1.51, with one path carrying 81% of the estimate.
- n = 25, r = 0.9: no successes.
- Under the iid proposal model this implies ≳ 90 process-hours for even 1% relative error at n = 25, r = 0.9.
- Measured, conditional on coverage. A newer cardinality sampler reaches past r = 0.9 at n = 30 and 50 and sees the error start to decline.
- Heuristic. At r = 0.5, our data to n = 200 admit both an A + Bn + D·n/ln n remainder and an n ln n remainder with a log correction.
Questions for the community:
- Is there a usable a priori bound on the lower-order terms of y(n, r) at fixed r? That is what would turn a finite comparison into an asymptotic one.
- Has anyone validated a dense sampler at r ≥ 0.9 against exact counts? Exact full profiles are available to n = 9 (data: no3-results/oeis/2026-11-03), and n = 10 is coming. We are happy to share our scoring harness.
- Does anyone know other exact or certified counts of safe m-sets at fixed density for n ≥ 10?
If you want to work on this jointly, reply here or send a private message. We can split the work: one side produces samplers, the other produces exact checks and controls.