§2 binomial bound — every coefficient is bounded by entropy
ProvedBipHamCount.Deterministic.binomial_entropycountingexact-algorithmsgraph-theorylinear-algebrap2o-batch-stoc27ap2o-gran-per-chapterp2o-plan-paperp2o-v1
For every pair of natural numbers with , write , with . Then
At , the quotient is interpreted as zero and both sides equal one. The bound covers the entire range, including . The published choose_sum_le_exp_mul_binEntropy bounds a partial sum only when , so it does not replace this statement. This estimate controls subset layers in the running-time analysis.
Differences from the source:
- encoding: binary entropy H in base two → Real.binEntropy in nats with exp replacing 2 raised to H; reason: exp(m·binEntropy x)=2^(m·H(x)), including x=0,1
- encoding: m=n/2 is a side size → an arbitrary natural side size m, including zero; reason: every balanced bipartite input has this size; at m=q=0 both sides are one under the stated total-division convention
Preamble
import Mathlib import Definitions.Def_BipHamCount_Deterministic_Core open scoped BigOperators
Formal statement
namespace BipHamCount.Deterministic
/-- §2 binomial bound, p.5, for the entire range q≤m. Entropy is in nats.
For m=q=0 the quotient is 0 and both sides are 1. -/
theorem binomial_entropy (m q : ℕ) (hq : q ≤ m) :
(m.choose q : ℝ) ≤ Real.exp ((m : ℝ) * Real.binEntropy ((q : ℝ) / m)) := by sorry
end BipHamCount.Deterministic
Source
Koana, Kumabe, Counting Hamiltonian Cycles in Bipartite Digraphs Deterministically in O(1.9526^n) Time, STOC 2027 submission #814 (October 2026), §2 binomial bound, p. 5. https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/814.pdf
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.