Theorem 4 — Exact average correlation
OpenAddXnor.Supplement.theorem_4add-xnorcryptographyp2o-gran-per-chapterp2o-plan-paperp2o-v1probability
For every and , the signed correlation averaged uniformly over all operator bits is exactly
The average is signed; no absolute value or planted distribution is involved.
Differences from the source:
- encoding: uniform operator string → exact finite average over
Fin (N-1) → Bool; reason: finite-type encoding with identical uniform weights
Preamble
import Mathlib import Definitions.Def_AddXnor_Supplement_core set_option autoImplicit false
Formal statement
namespace AddXnor.Supplement
/-- **Theorem 4 (Exact average correlation)** (Wang, Lv, Shen, Zhang,
*Add/XNOR Chains*, manuscript, sha256 405d6dda..., Theorem 4, p.16 (PDF p.16)).
This is the signed average of `Cor(x)`, not the average absolute correlation. -/
theorem theorem_4 (N m : ℕ) (hN : 2 ≤ N) (hm : 2 ≤ m) :
uniformMean (fun x : Fin (N - 1) → Bool => correlation (m := m) x) =
(N + 1 : ℝ) * Real.rpow 2 (-(N : ℝ)) := by sorry
end AddXnor.Supplement
Source
Wang, Lv, Shen, Zhang, manuscript (sha256 405d6dda…), Theorem 4, p.16 (PDF p.16)