A typical attained fiber is large under the pushforward law
OpenQAlgorithms.Papers.Independent.Intakenext100.P30.arbitrary_preimage_sizesLet and be finite nonempty sets, let be arbitrary, and let . Draw uniformly from and set . Then
The probability is taken under the pushforward of the uniform input law, not under a uniform draw from the codomain. This provides the large-fiber estimate relevant to nonlinear compression.
All alphabets are finite and nonempty, and output Hilbert spaces are finite dimensional and nonzero. A classical–quantum channel assigns a positive semidefinite, trace-one matrix to each input. Encoders may use private randomness; decoders are normalized POVMs. Codes are fixed independently of the message, with no supplied shared key or entanglement. Logarithms and entropies are in bits.
import Definitions.Def_QAlgorithms_Papers_Independent_Intakenext100_P30
noncomputable section
open scoped BigOperators ComplexConjugate Matrix ComplexOrder
open Filter
namespace QAlgorithms.Papers.Independent.Intakenext100.P30
variable {X Y Z M U V A B C : Type*}
variable [Fintype X] [DecidableEq X] [Fintype Y] [DecidableEq Y]
variable [Fintype Z] [DecidableEq Z] [Fintype M] [DecidableEq M]
variable [Fintype U] [DecidableEq U] [Fintype V] [DecidableEq V]
variable [Fintype A] [DecidableEq A] [Fintype B] [DecidableEq B]
variable [Fintype C] [DecidableEq C]
attribute [local instance] Classical.propDecidable
/-- Lemma 4, PDF p.7: first draw x uniformly and then use y=f(x). The
codomain is not sampled uniformly; empty fibers have mass zero. -/
theorem arbitrary_preimage_sizes [Nonempty X] [Nonempty Y]
(f : X → Y) (epsilon : ℝ) (he0 : 0 ≤ epsilon) (he1 : epsilon ≤ 1) :
1 - epsilon ≤ (Fintype.card X : ℝ)⁻¹ *
∑ x : X, if epsilon * (Fintype.card X : ℝ) / (Fintype.card Y : ℝ) ≤
(Fintype.card {a : X // f a = f x} : ℝ) then 1 else 0 := by sorry
end QAlgorithms.Papers.Independent.Intakenext100.P30
end
Read-back
What the Lean code literally says, in plain math · gpt-6.1-sol
For every pair of finite nonempty types , with the finite-type and equality structures needed to count fibers, every function , and every real ,
Thus the displayed fraction counts inputs whose own fiber has size at least ; no surjectivity assumption is made. Cardinalities are interpreted as real numbers, both denominators are positive by nonemptiness, and both endpoints and are included.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.