Theorem 3 — Run-product formula
OpenAddXnor.Supplement.theorem_3add-xnorcryptographyp2o-gran-per-chapterp2o-plan-paperp2o-v1probability
Let , , and let have maximal addition-run lengths . The signed bit- correlation satisfies
Furthermore, , exactly when , and
Thus the correlation loses exactly half a bit of its envelope per addition. The all-XNOR string has the empty run profile and empty product .
Differences from the source:
- encoding: -bit words and operator strings →
BitVec moperands and functionsFin (N-1) → Bool; reason: finite-type encoding with the same instances, withfalse= addition andtrue= XNOR
Preamble
import Mathlib import Definitions.Def_AddXnor_Supplement_core set_option autoImplicit false
Formal statement
namespace AddXnor.Supplement
/-- **Theorem 3 (Run-product formula)** (Wang, Lv, Shen, Zhang, *Add/XNOR Chains*,
manuscript, sha256 405d6dda..., Theorem 3, pp.15--16 (PDF pp.15--16)).
For every admissible chain, the signed bit-1 correlation factors over the maximal addition runs.
The remaining clauses give the exact closed form, its zeros, and the half-bit-per-addition bound.
The all-XNOR string has an empty run profile, so its product is `1`. -/
theorem theorem_3 (N m : ℕ) (hN : 2 ≤ N) (hm : 2 ≤ m)
(x : Fin (N - 1) → Bool) :
correlation (m := m) x = ((additionRuns x).map runCorrelation).prod ∧
(∀ z : ℕ,
|runCorrelation z| ≤ Real.rpow 2 (-(z : ℝ) / 2) ∧
(runCorrelation z = 0 ↔ z % 4 = 2)) ∧
|correlation (m := m) x| ≤
Real.rpow 2 (-((additionRuns x).sum : ℝ) / 2) ∧
Real.rpow 2 (-((additionRuns x).sum : ℝ) / 2) =
Real.rpow 2 (-((N - 1 - weight x : ℕ) : ℝ) / 2) := by sorry
end AddXnor.Supplement
Source
Wang, Lv, Shen, Zhang, manuscript (sha256 405d6dda…), Theorem 3, pp.15–16 (PDF pp.15–16)