The gate-bounded uniform-seed distribution class
DefinitionAutoregressiveCompression_Main_Supplement_CircuitClassFor the fixed finite alphabet , the size slice consists exactly of laws of finite deterministic sampler circuits with at most gates and at most output symbols:
The sampler's distribution is constructed by evaluating its actual Boolean circuit on a uniform finite seed. Gate count is the length of the gate list in the referenced general Boolean-circuit representation; input and output wires are not gates. Gates use constants, NOT, AND and OR with fan-in at most two and unbounded fan-out. The fixed one-hot alphabet encoding agrees with the base interface. Deleting trailing output symbols changes no gate list.
A class is polynomial-size circuit samplable if some polynomial satisfies for every . This predicate records the surrounding source definition; Theorem 7.1 concerns the particular class and Theorem 7.3 imposes no such condition on its existential classes. No gate-basis comparison or reindexing reduction is assumed as a field.
import Mathlib
import Definitions.Def_AutoregressiveCompression_Main_Supplement_Representations
noncomputable section
namespace AutoregressiveCompression.Main.Supplement
/-- Section 7, printed pp.36–37 / PDF pp.38–39: precisely the uniform-seed
pushforwards of sampler circuits with at most n gates and at most n output
symbols. Input and output wires are not gates. No arbitrary size label is used. -/
def Ccirc (Sym : Type) [Fintype Sym] : DistributionClass Sym where
members n := {D | ∃ (G : SamplerCode) (h : G.IsGenerator Sym),
G.circuit.size ≤ n ∧ G.length ≤ n ∧ D = G.source h}
length_le n D hD := by
obtain ⟨G, h, _, hlen, rfl⟩ := hD
exact hlen
/-- Section 7's polynomial-size samplability. This property is not an extra
hypothesis on arbitrary classes in the separation theorem. -/
def PolynomialCircuitSamplable {Sym : Type} [Fintype Sym]
(𝒟 : DistributionClass Sym) : Prop :=
∃ p : Polynomial ℕ, ∀ n, 𝒟.members n ⊆ (Ccirc Sym).members (p.eval n)
end AutoregressiveCompression.Main.Supplement