Lemma 3.2 — random linear hashing
ProvedPermInvCC.lemma_3_2communication-complexityp2o-gran-per-chapterp2o-plan-paperp2o-v1permutation-invariancequantum-communication
Let and be integers, and let have independent uniform binary entries. For every fixed pair of distinct vectors ,
This collision bound of Carter and Wegman drives the batch recovery of Lemma 3.4.
Differences from the source:
- encoding: H with independent uniform binary entries → uniform distribution on Matrix (Fin m) (Fin n) (ZMod 2), probability as a fraction of matrices; reason: the product of uniform bits is the uniform law on matrices
Preamble
import Mathlib
Formal statement
namespace PermInvCC
/-- **Lemma 3.2 (Random Linear Hashing, [CW79])** (Y. Huang and Z. Ye, arXiv:2609.40116, held
version sha256 fe1797dd…, p.11). Let `m ≥ 1` be an integer, and let `H ∈ F₂^{m×n}` have
independent uniform binary entries. For every fixed pair of distinct vectors `u, v ∈ F₂ⁿ`,
`P[Hu = Hv] = 2^{−m}`.
**Formalization Note.** Independent uniform entries is the uniform distribution on the finite set
of `m × n` matrices over `ZMod 2`; the probability is the fraction of matrices with `Hu = Hv`.
`n ≥ 2` is the paper's standing assumption (p.9). -/
theorem lemma_3_2 (m n : ℕ) (hm : 1 ≤ m) (hn : 2 ≤ n) (u v : Fin n → ZMod 2) (huv : u ≠ v) :
((Finset.univ.filter fun H : Matrix (Fin m) (Fin n) (ZMod 2) =>
H.mulVec u = H.mulVec v).card : ℝ) /
(Fintype.card (Matrix (Fin m) (Fin n) (ZMod 2)) : ℝ) = 1 / 2 ^ m := by sorry
end PermInvCC
Source
Huang and Ye, Quantum Advantage of Permutation-Invariant Functions in Communication Complexity, arXiv:2609.40116 (held version, sha256 fe1797dd…), Lemma 3.2, p.11
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.