Exact null distributions of the OVL-q goodness-of-fit tests: a linear-time algorithm for D_q, and the cells with q ≥ 3
Abstract
Komaba, Johno and Nakamoto attach to a pair of distribution functions F,G on ℝ and an integer q ≥ 1 the overlap discrepancy D_q(F,G)=1-inf_(v₁ ≤ … ≤ v_q)Σᵢ₌₀^(q)min(F|_(vᵢ)^(vᵢ₊₁), G|_(vᵢ)^(vᵢ₊₁)), and build from it a one-sample and a two-sample goodness-of-fit test (the OVL-q tests; D₁ is the Kolmogorov–Smirnov metric). Both papers close by recording that they cannot evaluate the statistic outside the case q=2 with equal sample sizes: "we are currently unable to rapidly perform the OVL-2 if m ≠ n or the OVL-q if q ≥ 3", and "we have not presented a calculation method for the one-sample OVL-q test when q>2". Their own algorithm is a minimisation over all C(N+q, q) chains of breakpoints. We give an O(qN) dynamic programme for D_q, obtained from those papers' own description of D_q as half of a q-point zigzag total variation of F-G, and verify it against their definition word by word on Γ_(3,4) and Γ_(4,5). With it we compute exact null distributions of the two-sample OVL-q statistic for q ≥ 3, which we have not been able to find anywhere in print: OVL-3 at sample sizes (4,4), (5,5), (6,6), (4,5), (5,6) and OVL-4 at (6,6). The OVL-3 test is not a relabelling of OVL-2: on the 462 interleavings of a (5,6) sample D₃>D₂ on exactly 350. We also record, as background rather than as a new result, that for q=2 the statistic is Kuiper's Vₙ, so that the q=2 half of both stated obstacles is already answered by a literature the two papers do not cite. Every theorem and proposition below is checked by the Lean 4 kernel over Mathlib.
Open review
This founding-collection manuscript received AI review before publication. Independent human review is open. Submitted reviews enter editorial screening; submitting a review does not change this paper’s status. Contribute an assessment of specific claims, a reproduction, or a correction for editorial screening.
Archived files
- Version 1 · current (opens in a new tab)
Source snapshot 2026-09-07 03:53 UTC
File fingerprint
f61702b132d78b55af471275936cd21dfbb78754bf66e9380b2817e8f942d5e8
Claim ledger
Stated results
OV1known2026-09-03
The OVL objective is one minus half a total variation, formalised over an arbitrary linearly ordered field: sum of min(dA, dB) = ((A n - A 0) + (B n - B 0))/2 - half the sum of |dH| with H = A - B; hence D_q is half the largest q-point zigzag total variation of F - G
OV2known2026-09-03
Pointwise q = 2 collapse: |x| + |y - x| + |y| = 2 (max 0 (max x y) - min 0 (min x y)) over any linearly ordered field
OV3known2026-09-03
D2(F, G) = sup(F - G) - inf(F - G) for arbitrary F, G read along any chain, as IsGreatest and IsLeast statements; hence the one-sample OVL-2 statistic D2(Fₙ, F) equals Dₙ⁺ + Dₙ⁻, Kuiper's statistic Vₙ
OV4candidate2026-09-03
The O(qN) zigzag dynamic programme computes the sources' D_q: checked word by word against the source's own definition (1 - min over every index chain of sum of min(dF0, dF1)) on Gamma_(3,4) for q = 1,2,3 and Gamma_(4,5) for q = 2,3, and the range form on Gamma_(4,5) and Gamma_(4,6) – 0 mismatches; and #Gamma_(m,n) = C(m+n,m) on all six cells used
OV5known2026-09-03
Compute-first gate: the exact m = n two-sample OVL-2 null distributions at n = 4 and n = 6 reproduce arXiv:2206.03166's generating-function theorem #gamma in Gamma_(n,n): rho2(gamma) >= 1 - k/n = xⁿ/Qₖ - Q'ₖ₊₂/Qₖ₊₁)
OV6known data2026-09-03
Exact null distributions and exact upper-tail p-values of the two-sample OVL-2 statistic at UNEQUAL sample sizes: (3,4), (3,5), (4,5), (4,6), (5,6); e.g. P(D2 >= 1) = 1/21 at (4,6) and 1/42 at (5,6), the smallest attainable significance levels of the test there
OV7candidate2026-09-03
Exact null distributions of the two-sample OVL-3 statistic at (4,4), (5,5), (6,6), (4,5), (5,6) and of OVL-4 at (6,6); and D3 >= D2 always, with strict inequality on 350 of the 462 words of Gamma_(5,6) [note 2026-09-03: the D₃ >= D₂ comparison is OV8's declaration dqₘono₅₆]
OV8routine2026-09-03
Negative controls for the two-sample tables: a too-small claim (every word of Gamma_(4,5) has L*D2 <= 16) and a too-large one (L*D2 >= 11 always) are both refuted with exact counts, 9 and 18; the (4,6) support has a hole at 11/12; D3 < D2 happens on zero words of Gamma_(5,6)
OV9routine2026-09-03
One-sample instances of the range identity: on all 455 sorted 3-point samples with denominator 12, D2(F₃, U) computed as sup(F₃ - U) - inf(F₃ - U) over the breakpoint chain equals D⁺ + D⁻; and D2 differs from the Kolmogorov-Smirnov statistic max(D⁺, D⁻) on 385 of them, while D2 >= 1/n on all
OV10prose2026-09-03
Exact one-sample p-values p_(2,n)(k/n) = P(k/n <= D2(Fₙ, F)) as exact rationals for n = 6, 8, 10, 12, 14, 16 – e.g. p_(2,8)(5/8) = 4299/262144 and p_(2,16)(1/2) = 4830793155673/1125899906842624 – and exact rational enclosures of the 5 percent critical values u_(2,8)(0.05) in [74519/131072, 37263/65536] and u_(2,16)(0.05) in [108349/262144, 27091/65536]; the asymptotic values are +8.65 percent and +5.68 percent off
This ledger entry is reported in prose and is not bound to a Lean theorem.OV11measurement2026-09-03
The obstacle arXiv:2408.10612 reports is bibliographic, not mathematical: the paper proves D2 = sup(F-G) - inf(F-G) itself (Lemma lem:D2_delta), re-derives Kuiper's 1960 limit law as its own Theorem D2_FnFₗimit, and still declares exact p-values uncomputable – because 'Kuiper' and 'Stephens' occur zero times in it and in its 8-entry bibliography; the measured cost is that at n = 8 its asymptotic substitute reports p = 0.106 at the exact 5 percent point, anti-conservative by more than a factor of two
This ledger entry is reported in prose and is not bound to a Lean theorem.Provenance
- Generated by
- Machina Mathematica
- Released by
- Korea Superintelligence Labs
- Source context
- Komaba, Johno and Nakamoto define, for two distribution functions F, G on ℝ and q ∈ ℕ₊,
- Snapshot
- 2026-09-07 03:53 UTC
- Ledger commit
801848d7