AFTD Auto-Formalizing Theoretical Domains

equality_classical_behaviour

def

The behaviour of the shared-random-subset equality protocol: on shared randomness r ∈ ZMod N, Alice sends the clipped message (s + r) mod N with K − 1 concrete values and a 'fail' message K − 1; on a concrete message m Bob outputs 'true' if (t + r) mod N = m and 'false' otherwise, and abstains on the fail message. The probability p(s,(t,a),a,o) is the fraction of r realizing message a and output o.

Statement

noncomputable def equality_classical_behaviour (N K : ℕ) [NeZero N] (hK : 1 ≤ K) :
    Fin N → Fin N × Fin K → Fin K → Option Bool → ℝ
Source
step towards commuting_quantum_efficiency_classical_lower_bound
Verified
07 Nov 2026
Axioms
none listed

Lean source view module on GitHub

/-- The classical shared-randomness behaviour for equality certification: Alice clips (s + r) to a concrete message value in Fin (K−1) with fallback message K−1, Bob answers conclusively on concrete messages by comparing (t + r) with the received message; probability = fraction of randomness r realizing (message, output). -/
noncomputable def equality_classical_behaviour (N K : ℕ) [NeZero N] (hK : 1 ≤ K) :
    Fin N → Fin N × Fin K → Fin K → Option Bool → ℝ := fun (s : Fin N) (q : Fin N × Fin K) (x : Fin K) (o : Option Bool) =>
  ((Finset.univ.filter (fun r : ZMod N =>
      (if h : ((s.val : ZMod N) + r).val < K - 1 then
          (⟨((s.val : ZMod N) + r).val, h.trans_le (Nat.sub_le K 1)⟩ : Fin K)
        else ⟨K - 1, by omega⟩) = x ∧
      (if x.val < K - 1 then
          (if r + (q.1.val : ZMod N) = (x.val : ZMod N) then some true else some false)
        else none) = o)).card : ℝ) / (N : ℝ)
See it in the graphDiscuss this resultChallenge it