The quarter observation for hypergeometric tails: the whole band 1<E H ≤ 2, the sharp constant, and the exact minimum for n ≤ 250
Abstract
Let H ∼ Hyp(n,i,k) count the black marbles in a sample without replacement of size k drawn from an urn holding i black and n-i white marbles, so that E H=ik/n. In a study of lower bounds for ℙ(H ≥ E H), Ai and Pelekis record a numerical observation: under the two hypotheses ik/n ≥ 1/2 and (n-i)(n-k)/n ≥ 1/2 one has ℙ(H ≥ E H) ≥ 1/4. They prove no case of it, and a later note of Ai, Kuželka and Pelekis states that the corresponding minimisation is not known below n=8k. Our main theorem proves the inequality on the whole band n<ik ≤ 2n, that is 1<E H ≤ 2, for all n, i and k and with neither hypothesis assumed; together with the bound 1/3 that we prove when E H ≤ 1, this settles every admissible triple with E H ≤ 2. The band is where the observation is tight: it contains the family k=2, n odd, i=frac(n+1)2, whose tail is exactly (n+1)/(4n), so no constant larger than 1/4 can be used, and 1/4 is the infimum there. The engine of the proof is a binomial inequality obtained from a five-term truncation of Vandermonde's convolution which, unlike the corresponding truncation of the elementary estimate binom aκ/binom bκ ≥ (a/b)^κ, leaves no exceptional pairs at all, so no finite table of cases enters. We prove the observation for every n also when min(i,k) ≤ 3 or min(n-i,n-k) ≤ 3, the second half through a complementation invariance T(n,i,k)=T(n,n-i,n-k) which exhibits the two hypotheses as the two halves of one symmetric pair; and we certify the whole admissible range n ≤ 250 by exhaustive exact computation, determining its exact minimum (125)/(498)=(249+1)/(4 · 249), attained at (249,125,2). Letting n → ∞ inside the band degenerates the main theorem to the part of the binomial theorem of Greenberg and Mohri in which the threshold is 2, which is published; what is new is the statement at finite n, for sampling without replacement, and its independence of the two hypotheses. What remains open is E H>2 with min(i,k) ≥ 4 and min(n-i,n-k) ≥ 4; we explain why the published routes to a constant 1/4 for this distribution cannot reach the band, and why the region that is left is no longer a question about the constant 1/4. Every statement below is machine-checked in Lean 4, and all of it by the kernel alone except the lower-bound half of the n ≤ 250 result, which additionally rests on six compiled evaluations.
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 2 · current (opens in a new tab)
Source snapshot 2026-09-07 03:53 UTC
File fingerprint
8ae4eedbe4cff7105c9b338488dc61c61f040eb442a93e594a92723645280a11
Claim ledger
Stated results
AP1known2026-09-03
The hypergeometric law: the pmf C(i,j)C(n-i,k-j)/C(n,k) sums to 1 (Vandermonde) and has mean i*k/n
AP2candidate2026-09-03
Ai-Pelekis regime 1/2 <= E H <= 1: P(H >= E H) >= 1/3 for every n, via the hypergeometric analogue (n + i*k) * C(n-i,k) <= n * C(n,k) of (1-p)ᵏ <= 1/(1+pk)
AP3candidate2026-09-03
The Ai-Pelekis observation is a theorem when k = 2, for every n: P(H >= E H) >= 1/4 whenever Hyp(n,i,2) satisfies the two hypotheses
AP4candidate2026-09-03
The extremal family and the sharpness of 1/4: at k = 2, odd n and i = (n+1)/2 the tail is exactly (n+1)/(4n), so no constant above 1/4 works and 1/4 is never attained
AP5routine2026-09-03
Controls: non-vacuity at (119,60,2) with tail 30/119, both hypotheses independently necessary ((5,1,1) and (5,4,4) each give 1/5), the 1/3 of AP2 does not extend, and the constant cannot be raised to 0.253
AP6candidate2026-09-03
The exact minimum of P(H >= E H) over the admissible window n <= 250 is 125/498 = (249+1)/(4*249), attained at (249,125,2)
AP7candidate2026-09-03
The Ai-Pelekis observation P(H >= E H) >= 1/4 verified, strictly, for every admissible (n,i,k) with n <= 250
AP8measurement2026-09-03
Cost of the certified window: the sweep grows like N⁴.3, six native_decide chunks cover n <= 250 in 18 CPU-minutes at 0.46 GB peak; the descending two-binomial recurrence is what makes it O(min(i,k)) per triple instead of O(min(i,k)²)
This ledger entry is reported in prose and is not bound to a Lean theorem.AP9routine2026-09-03
The transpose symmetry P(H_(n,i,k) >= E H) = P(H_(n,k,i) >= E H), with admissibility symmetric in i and k; hence the observation also holds for every n when i = 2
AP10candidate2026-09-03
The Ai-Pelekis observation is a theorem when k = 3, for every n (and, through the transpose symmetry AP9, when i = 3); packaged with AP2 and AP3 as quarterₒfₘinₗeₜhree, this settles every case with min(i,k) <= 3
AP11routine2026-09-03
The complement symmetry P(H_(n,i,k) >= E H) = P(H_(n,n-i,n-k) >= E H), with admissibility invariant under it; hence the observation also holds whenever min(n-i,n-k) <= 3, doubling the settled strip to min(i,k) <= 3 or min(n-i,n-k) <= 3
AP12candidate2026-09-03
Theorem A: P(H >= E H) >= 1/4 for every (n,i,k) with n < i*k <= 2*n – the band 1 < E H <= 2 – with NO admissibility hypothesis; packaged with the E H <= 1 regime this settles every admissible triple with i*k <= 2*n
AP13routine2026-09-03
The two-cell closed form P(H <= 1) = (n + (i-1)(k-1)) C(n-i,k-1) / (n C(n-1,k-1)), and the unconditional monotonicity of P(H <= 1) in n at fixed (i,k), whose cleared step is an identity with defect exactly i(i-1)k(k-1)
AP14candidate2026-09-03
The crux inequality 4*C(b,k-1)*(2ik-i-k) <= 3*(ik-1)*C(b+i-1,k-1) at b = ik-1-i, for all i >= k >= 2, and the truncation comparison that proves it: the five-term Vandermonde truncation leaves NO exceptional pairs where the five-term power bound C(a,K)/C(b,K) >= (a/b)^K leaves exactly 181 (all with i,k <= 26)
AP15routine2026-09-03
The telescoping identity Nₘ(n,i+1,k) - Nₘ(n,i,k) = C(i,m-1) C(n-i-1,k-m) with its two Pascal parents; hence Nₘ is nondecreasing in i at a fixed threshold, and C(n,k) P(H >= m) = sum_(a<i) C(a,m-1) C(n-1-a,k-m), i.e. P(H >= m) = P(Sₘ <= i) for the m-th order statistic of a uniform random k-subset of [n]
Provenance
- Generated by
- Machina Mathematica
- Released by
- Korea Superintelligence Labs
- Source context
- Let H Hyp(n, i, k) count the black marbles in a sample without replacement of size k drawn from an urn holding i black and n - i white marbles:
- Snapshot
- 2026-09-07 03:53 UTC
- Ledger commit
801848d7