Proof of Theorem 4.1 —
ProvedNondetConn.f_closed_formcommunication-complexitygraph-connectivitylower-boundsp2o-gran-per-chapterp2o-plan-paperp2o-v1permutations
For define
Then .
The coefficient is what the recurrence of Lemma 4.3 accumulates when unrolled down to ; its closed form gives the constant in the bound on .
Differences from the source: none.
Preamble
import Mathlib
Formal statement
namespace NondetConn
/-- **Proof of Theorem 4.1, `f_n = 4n/5`** (Zhang, *Settling Nondeterministic Communication Complexity of Graph Connectivity*, arXiv:2610.32346 (held version, sha256 1d4f00d1…4e7ac), p.10).
For `n ≥ 1`, `f_n = ∑_{i ∈ [n]} ∏_{j ∈ [i, n]} 4j/(4j + 1) = 4n/5`. -/
theorem f_closed_form (n : ℕ) (hn : 1 ≤ n) :
∑ i ∈ Finset.Icc 1 n, ∏ j ∈ Finset.Icc i n, (4 * (j : ℝ)) / (4 * j + 1) = 4 * n / 5 := by sorry
end NondetConn
Source
Zhang, Settling Nondeterministic Communication Complexity of Graph Connectivity, arXiv:2610.32346 (held version, sha256 1d4f00d1…4e7ac), proof of Theorem 4.1, p.10 (PDF p.12)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.