Theorem 3 (companion theorem; not used in the proof of the goal) — approximate counting of set packings
OpenKoanaKPaths.Main.Supplement.set_packing_countingLet and let be an explicitly given family of distinct -element sets. Write for the number of unordered -element pairwise-disjoint subfamilies. For every real , a single uniform randomized algorithm returns a rational satisfying
in bit time, with the inherited rounded confidence convention described below. Zero counts are included: the success event then requires an exactly zero estimate. Neither nor is fixed, and there is no promise of a packing.
More explicitly, there are circuit and packing machines and positive constants , fixed before all data. Put , , and
For every fair-bit tape length , on every tape both machines halt within bit steps using at most tape bits and write the same fraction with positive denominator: takes the compiled circuit input and 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 , control copying by its binary length, and simulation of 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 , the exact identity
and gate bound and encoded-length bound . 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 positive-degree states adds 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 and on the whole interval; for , . This is the base mission's declared rounding reading of the printed logarithm, while accuracy covers all real .
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
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
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