Theorem 7 — Low-bit dissection
OpenAddXnor.Supplement.theorem_7add-xnoralgorithmscomplexity-theoryp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1
Let , , and . There is a deterministic algorithm that decides an Add/XNOR instance and returns a witness in worst-case time and space . It computes in time before the witness solver stores its lists.
For every fixed low-bit class on uniform instances,
At , both expectations are .
Differences from the source:
- encoding: deterministic algorithm with time and space → two deterministic multitape machines, one computing before the solver trace, with explicit polynomial factors and a trace-wide space bound; reason: makes the paper's bit-operation and preprocessing claims operational
- generalization: both expectations are at → both are explicitly bounded by ; reason: the exact formulas imply this uniform constant after splitting by
Preamble
import Mathlib import Definitions.Def_AddXnor_Supplement_algorithms set_option autoImplicit false
Formal statement
namespace AddXnor.Supplement
/-- **Theorem 7 (Low-bit dissection)** (Wang, Lv, Shen, Zhang, *Add/XNOR Chains*,
manuscript, sha256 405d6dda..., Theorem 7, p.22 (PDF p.22)).
The first conjunct is the uniform deterministic decision-and-witness algorithm, including its
preprocessing of `μ_p` before the solver runs and the `O*(2^(q/2))` time and
`O*(2^(q/4)+μ_p)` space traces. The next clauses are the two exact per-class expectations.
The final inequalities make the printed `O*(2^(q/4))` specialization at `p=k` explicit (factor
`8` absorbs the four possible residues of `q` modulo `4`). -/
theorem theorem_7 :
IsLowBitDissectionAlgorithm ∧
∀ (q m p : ℕ), 1 ≤ q → 1 ≤ m → p ≤ quarter q →
∀ g : Fin (2 ^ p),
uniformMean (fun A : Fin (q + 1) → BitVec m =>
(forwardClassCard A p g : ℝ)) = (2 : ℝ) ^ (2 * quarter q - p) ∧
uniformMean (fun A : Fin (q + 1) → BitVec m =>
(backwardClassCard A p g : ℝ)) = (2 : ℝ) ^ (q - 2 * quarter q - p) ∧
(p = quarter q →
uniformMean (fun A : Fin (q + 1) → BitVec m =>
(forwardClassCard A p g : ℝ)) ≤ 8 * quarterPow q ∧
uniformMean (fun A : Fin (q + 1) → BitVec m =>
(backwardClassCard A p g : ℝ)) ≤ 8 * quarterPow q) := by sorry
end AddXnor.Supplement
Source
Wang, Lv, Shen, Zhang, manuscript (sha256 405d6dda…), Theorem 7, p.22 (PDF p.22)