Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 3 (companion theorem; not used in the proof of the goal) — approximate counting of set packings

Open
KoanaKPaths.Main.Supplement.set_packing_counting

by mikedeng1 · Nov 15, 2026 · Mathlib 0df444a (Lean v4.33.1)

approximate-countingbit-complexityp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1set-packing

Let d,k≥1d,k\ge1d,k≥1 and let E=(E0,…,Em−1)E=(E_0,\ldots,E_{m-1})E=(E0​,…,Em−1​) be an explicitly given family of m≥km\ge km≥k distinct ddd-element sets. Write N=packingCount⁡(E,k)N=\operatorname{packingCount}(E,k)N=packingCount(E,k) for the number of unordered kkk-element pairwise-disjoint subfamilies. For every real 0<ε,δ<10<\varepsilon,\delta<10<ε,δ<1, a single uniform randomized algorithm returns a rational N^\widehat NN satisfying

Pr⁡[∣N^−N∣≤εN]≥1−δ\Pr\bigl[|\widehat N-N|\le\varepsilon N\bigr]\ge1-\deltaPr[∣N−N∣≤εN]≥1−δ

in O∗(2dkε−2log⁡(1/δ))O^*(2^{dk}\varepsilon^{-2}\log(1/\delta))O∗(2dkε−2log(1/δ)) bit time, with the inherited rounded confidence convention described below. Zero counts are included: the success event then requires an exactly zero estimate. Neither ddd nor kkk is fixed, and there is no promise of a packing.

More explicitly, there are circuit and packing machines A,MA,MA,M and positive constants K,c,K0,c0K,c,K_0,c_0K,c,K0​,c0​, fixed before all data. Put L=∣familyCode⁡(E)∣L=|\operatorname{familyCode}(E)|L=∣familyCode(E)∣, a=ctrl⁡(ε)a=\operatorname{ctrl}(\varepsilon)a=ctrl(ε), b=ctrl⁡(δ)b=\operatorname{ctrl}(\delta)b=ctrl(δ) and

B=K 2dk(1+dk+L)c4a(b+1).B=K\,2^{dk}(1+dk+L)^c4^a(b+1).B=K2dk(1+dk+L)c4a(b+1).

For every fair-bit tape length T>BT>BT>B, on every tape both machines halt within BBB bit steps using at most BBB tape bits and write the same fraction with positive denominator: AAA takes the compiled circuit input and MMM takes the family input. The probability bound concerns this same fraction and these same bounded executions. The composition relation additionally bounds deterministic prefix work by a polynomial in dk,Ldk,Ldk,L, control copying by its binary length, and simulation of AAA by constant slowdown.

The statement includes uniform polynomial-bit computation of the compiler and, for every valid family, well-formedness, homogeneity and coefficient-one at every gate, output degree dkdkdk, the exact identity

N(packingCircuit⁡(E,k))=packingCount⁡(E,k),N\bigl(\operatorname{packingCircuit}(E,k)\bigr)=\operatorname{packingCount}(E,k),N(packingCircuit(E,k))=packingCount(E,k),

and gate bound 1+mk(d+1)1+mk(d+1)1+mk(d+1) and encoded-length bound K0(1+dk+L)c0K_0(1+dk+L)^{c_0}K0​(1+dk+L)c0​. These are conclusions, not hypotheses. The gate numeral is a direct bound for the implementation of the recurrence in the proof on printed p.10 (PDF p.11): each of at most mkmkmk positive-degree states adds ddd right-product gates and at most one addition, beyond a shared constant-one gate. This result adds the paper's set-packing application as a companion theorem to the path-counting goal; its existing reduction target is Theorem 2.

Formalization Note Every label length and output bit is charged by the published finite-stack model. No oracle or tolerance control occurs in the polynomial size factor. The source supplies no numerical constant for that polynomial, so constants and degrees are existential and uniform. The published ceiling controls satisfy 4a<4ε−24^a<4\varepsilon^{-2}4a<4ε−2 and b+1=O(1+log⁡(1/δ))b+1=O(1+\log(1/\delta))b+1=O(1+log(1/δ)) on the whole interval; for δ≤1/2\delta\le1/2δ≤1/2, b+1≤3log⁡2(1/δ)b+1\le3\log_2(1/\delta)b+1≤3log2​(1/δ). This is the base mission's declared rounding reading of the printed logarithm, while accuracy covers all real 0<δ<10<\delta<10<δ<1.

Differences from the source:

  • encoding: a family of distinct d-element sets and its k-element disjoint subfamilies → a duplicate-free list of finite sets of natural labels and unordered index subsets; reason: injective numbering of the finite ground union and ordering of the family preserve every source instance and packing
  • encoding: the Section 4.2 circuit construction and application of Theorem 2 → an actual shared-gate compiler, its validity/count/size/bit-computability conclusions and a constant-slowdown composition with a circuit machine; reason: records the source construction with charged deterministic preprocessing and identical rational outputs on the same fair-bit tape; no proven fact is assumed as input
  • encoding: uniform randomized O*(2^(dk) epsilon^(-2) log(1/delta)) time → positive universal natural constants and degrees before every input, finite fair-bit runs and rational output with explicit timeBudget at degree d*k; reason: makes uniform bit time, random-bit use, input-label lengths and every source tolerance explicit
  • reading: log(1/delta) for every real 0<delta<1 → the published rounded confidence factor ctrl(delta)+1, hence O(1+log(1/delta)) throughout the full accuracy domain; reason: inherits the base operational convention near delta=1; for delta<=1/2 it is at most 3 log_2(1/delta), and accuracy is never restricted
Preamble
import Mathlib
import Definitions.Def_HypergraphUnreliability_FPRAS_Machine
import Definitions.Def_KoanaKPaths_Main_Circuits
import Definitions.Def_KoanaKPaths_Main_Inputs
import Definitions.Def_KoanaKPaths_Main_Supplement_Packings
import Definitions.Def_KoanaKPaths_Main_Supplement_Reduction

open HypergraphUnreliability.FPRAS
Formal statement
namespace KoanaKPaths.Main.Supplement

/-- Theorem 3, printed pp.3,10 / PDF pp.4,11. A companion theorem to the published path goal.
The compiler and both machines are uniform. Compiler validity, the exact count correspondence,
and polynomial bit cost are conclusions, as are total bounded rational output and multiplicative
accuracy. The circuit machine and composite machine write the same fraction on the same tape.
The confidence ceiling convention is inherited from the published circuit interface. -/
theorem set_packing_counting :
    ∃ (A M : CoinMachine) (K c Kpre cpre : ℕ),
      0 < K ∧ 0 < c ∧ 0 < Kpre ∧ 0 < cpre ∧
      CompilesThenRuns M A Kpre cpre ∧
      PolyComputesIn
        (fun x : ℕ × ℕ × List (Finset ℕ) => ValidFamily x.2.2 x.1 x.2.1)
        (fun x => packingData x.2.2 x.1 x.2.1)
        (fun x => circuitCode (packingCircuit x.2.2 x.2.1))
        (fun x => 1 + x.1 * x.2.1 + (familyCode x.2.2).length) ∧
      ∀ (E : List (Finset ℕ)) (d k : ℕ), ValidFamily E d k →
        (packingCircuit E k).IsHomZeroOne (d * k) ∧
        numMultilinear (packingCircuit E k).outputPoly = (packingCount E k : ℤ) ∧
        (packingCircuit E k).gates.length ≤ 1 + E.length * k * (d + 1) ∧
        (circuitCode (packingCircuit E k)).length ≤ Kpre * (1 + d * k + (familyCode E).length) ^ cpre ∧
        ∀ ε δ : ℝ, 0 < ε → ε < 1 → 0 < δ → δ < 1 →
        ∀ T : ℕ, timeBudget K c (d * k) (familyCode E).length (ctrl ε) (ctrl δ) < T →
          (∀ ω : Fin T → Bool, ∃ Nhat : Frac, 0 < Nhat.den ∧
            M.RunsWithin (packingInput E d k ε δ) (tapeList ω)
              (timeBudget K c (d * k) (familyCode E).length (ctrl ε) (ctrl δ)) (fracCode Nhat) ∧
            A.RunsWithin (circuitInput (packingCircuit E k) ε δ) (tapeList ω)
              (timeBudget K c (d * k) (familyCode E).length (ctrl ε) (ctrl δ)) (fracCode Nhat)) ∧
          1 - δ ≤ fairProb T (fun ω => ∃ Nhat : Frac, 0 < Nhat.den ∧
            M.RunsWithin (packingInput E d k ε δ) (tapeList ω)
              (timeBudget K c (d * k) (familyCode E).length (ctrl ε) (ctrl δ)) (fracCode Nhat) ∧
            A.RunsWithin (circuitInput (packingCircuit E k) ε δ) (tapeList ω)
              (timeBudget K c (d * k) (familyCode E).length (ctrl ε) (ctrl δ)) (fracCode Nhat) ∧
            |((Nhat.val : ℚ) : ℝ) - (packingCount E k : ℝ)| ≤ ε * (packingCount E k : ℝ)) := by sorry

end KoanaKPaths.Main.Supplement
Source
Tomohiro Koana, STOC 2027 submission #953 (October 2026), p. 3 (PDF p. 4), Theorem 3; repeated and proved p. 10 (PDF p. 11), Section 4.2; inherited bit-time analysis p. 9 (PDF p. 10), Section 3.2

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me