Claim B.1.2, p. A:44 — the admitting a good number at most
ProvedObfImpossibility.PseudoOracle.claim_B_1_2There is such that for every there are and with the following property. Let , , let make at most oracle queries, and let have elements. Let be the number of injective functions . Then the number of injective for which some satisfies Properties (1)–(3) of Claim B.1.1 (with this and ) is at most
The paper states this as a description length: every such "can be uniquely described by bits given ". A set whose members each have a distinct description of at most bits has at most members, so the counting form is equivalent up to the constant . It is the compression step of the Gennaro–Trevisan style argument: the set , the values of off , one sign bit and the image , which inequality (9) confines to a small fraction of the candidates, determine .
Formalization Note The paper states the claim for the set of Claim B.1.1; since every admits a good , the bound here covers . The existence of renders the paper's "for a sufficiently small , whose value is implicit in the proof"; depends only on and only on and . Property (1) is read as .
import Mathlib import Definitions.Def_ObfImpossibility_PseudoOracle_Setting
namespace ObfImpossibility.PseudoOracle
open Classical in
/-- Claim B.1.2, p. A:44, counting form: for every sufficiently small `δ > 0` there is
`c > 0` such that for all large `K`, all `L ≥ K²`, every `D` making at most `K^δ` queries
and every `S ⊆ [K]` of size `⌊K^{1-5δ}⌋`, the injective `G : [K] → [L]` that admit a set
`S_G ⊆ S` with Properties (1)–(3) of Claim B.1.1 number at most `B · 2^{-c K^{1-7δ}}`,
where `B` is the number of injective functions `[K] → [L]` ("each such `G` is described by
`log B - Ω(K^{1-7δ})` bits given `D`"). -/
theorem claim_B_1_2 :
∃ δ₀ : ℝ, 0 < δ₀ ∧ ∀ δ : ℝ, 0 < δ → δ ≤ δ₀ → ∃ c : ℝ, 0 < c ∧ ∃ K₀ : ℕ,
∀ K L : ℕ, K₀ ≤ K → K ^ 2 ≤ L →
∀ D : Fin L → QTree K L, (∀ y, ((D y).depth : ℝ) ≤ (K : ℝ) ^ δ) →
∀ S : Finset (Fin K), S.card = ⌊(K : ℝ) ^ (1 - 5 * δ)⌋₊ →
((Finset.univ.filter fun G : Fin K ↪ Fin L =>
∃ SG : Finset (Fin K), GoodSubset D δ S G SG).card : ℝ) ≤
(Fintype.card (Fin K ↪ Fin L) : ℝ) *
(2 : ℝ) ^ (-(c * (K : ℝ) ^ (1 - 7 * δ))) := by sorry
end ObfImpossibility.PseudoOracle
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.