Proof of Theorem 6, §C.3.1, pp. 41–43 — formal expressions that are not identically equal collide with probability
ProvedGGHRSW.ColoredMatrix.theorem_6_collision_boundLet be a prime, a branching program of length over input bits, and a partial assignment. Let be two formal query expressions over the handles of that have the same shape (same dimensions and colours) and are not identically equal, i.e. their values differ for at least one sample of . Then
where is an absolute constant, independent of , , , and .
This is the per-query estimate of the proof of Theorem 6 (§C.3.1). In every colour case, partial evaluations with or as well as full evaluations from colour to colour , a new matrix coincides with an earlier one only with probability , unless the two expressions agree for every sample. Summed over the at most pairs of handles of an execution, this gives the of Theorem 6.
Formalization Note. Expressions, shapes, values and identical equality are those of Definitions.Def_GGHRSW_ColoredMatrix_Simulator. The probability is over the uniform sample of the finite sample space. The bound is written with so that it also covers programs with no steps, where only the bookend vectors are available. The constant is quantified first.
Formalization credit: Wentao Li (Victor), under the Prove2Me account Victorized, with assistance from Claude (Anthropic).
import Mathlib import Definitions.Def_GGHRSW_ColoredMatrix_Model import Definitions.Def_GGHRSW_ColoredMatrix_Simulator
namespace GGHRSW.ColoredMatrix
open Classical in
theorem theorem_6_collision_bound : ∃ C : ℝ, ∀ (p : ℕ) [Fact p.Prime] (bp : BP)
(J : Finset (Fin bp.ℓ)) (σ : Fin bp.ℓ → Bool) (e e' : QExpr p) (s : Shape),
e.shape bp J = some s → e'.shape bp J = some s → ¬ IdenticallyEqual bp J σ e e' →
((Finset.univ.filter fun ω : Sample p bp =>
e.eval (initDB bp J σ ω) = e'.eval (initDB bp J σ ω)).card : ℝ) /
Fintype.card (Sample p bp) ≤ C * (bp.n + 1) / p := by sorry
end GGHRSW.ColoredMatrix