Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 2.1, p. 8 — if D(P‖Q)/α = o(log n/n) with α bounded below, every algorithm has ℙ[β(π̂, π*) < α] → 1

Proved
GraphAlignment.Impossible.theorem_2_1

by mikedeng1 · Oct 15, 2026 · Mathlib 0df444a (Lean v4.33.1)

graph-alignmentimpossibilityp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1partial-recovery

For every nnn let GA,GBG_A,G_BGA​,GB​ be generated by the correlated Erdős–Rényi model (n,qn,sn)(n,q_n,s_n)(n,qn​,sn​) with 0≤qn<sn≤10\le q_n<s_n\le10≤qn​<sn​≤1 and with π∗\pi^*π∗ drawn uniformly from the n!n!n! permutations. Let αn∈(0,1)\alpha_n\in(0,1)αn​∈(0,1), possibly depending on nnn but bounded below: there is c>0c>0c>0 with αn≥c\alpha_n\ge cαn​≥c for all large nnn. If

D(P∥Q)αn=o(log⁡nn)(n→∞),\frac{D(P\|Q)}{\alpha_n}=o\Big(\frac{\log n}{n}\Big)\qquad(n\to\infty),αn​D(P∥Q)​=o(nlogn​)(n→∞),

with P,QP,QP,Q the edge-pair laws (3)–(4) at (qn,sn)(q_n,s_n)(qn​,sn​), then for any sequence of algorithms inferring π^\hat\piπ^ from GAG_AGA​ and GBG_BGB​,

P[β(π^,π∗)<αn]  ⟶  1(n→∞).\mathbb P\big[\beta(\hat\pi,\pi^*)<\alpha_n\big]\;\longrightarrow\;1\qquad(n\to\infty).P[β(π^,π∗)<αn​]⟶1(n→∞).

In other words, no learning algorithm can infer a permutation that overlaps with π∗\pi^*π∗ on more than a fraction αn\alpha_nαn​ of the vertices with probability bounded away from zero.

This is the paper's impossibility result: it identifies a regime of the correlated Erdős–Rényi model in which even partial recovery of the planted alignment is information-theoretically impossible.

Formalization Note The page allows any α∈(0,1)\alpha\in(0,1)α∈(0,1) "possibly dependent on nnn"; as printed the statement fails for αn→0\alpha_n\to0αn​→0 fast (with αn=1/n\alpha_n=1/nαn​=1/n, qn=n−3q_n=n^{-3}qn​=n−3, s=1/2s=1/2s=1/2 the hypothesis holds but the identity algorithm succeeds with probability tending to 1−e−11-e^{-1}1−e−1). The hypothesis that αn\alpha_nαn​ is eventually bounded below by a constant c>0c>0c>0 is added; a constant α\alphaα is the special case. Algorithms are arbitrary stochastic kernels from the observed pair (A,B)(A,B)(A,B) to permutations, one for each nnn, and see neither π∗\pi^*π∗ nor the hidden graph GB′G_{B'}GB′​. The little-ooo hypothesis is the convergence of (D(P∥Q)/αn)/(log⁡n/n)\big(D(P\|Q)/\alpha_n\big)/(\log n/n)(D(P∥Q)/αn​)/(logn/n) to 000; natural logarithm.

Preamble
import Mathlib
import Definitions.Def_GraphAlignment_Impossible_Setting
Formal statement
namespace GraphAlignment.Impossible

open Filter Topology

theorem theorem_2_1 (q s α : ℕ → ℝ)
    (hq : ∀ n, 0 ≤ q n) (hqs : ∀ n, q n < s n) (hs : ∀ n, s n ≤ 1)
    (hα : ∀ n, 0 < α n ∧ α n < 1) (hαc : ∃ c : ℝ, 0 < c ∧ ∀ᶠ n in atTop, c ≤ α n)
    (hD : Tendsto (fun n : ℕ => klPQ (q n) (s n) / α n / (Real.log n / n)) atTop (𝓝 0))
    (alg : ∀ n, Alg n) :
    Tendsto (fun n => failProb (q n) (s n) (α n) (alg n)) atTop (𝓝 1) := by sorry

end GraphAlignment.Impossible
Source
Hall, Massoulié, Partial Recovery in the Graph Alignment Problem, arXiv:2007.00533v5, p. 8, Theorem 2.1 (proof pp. 10–13, §3)
Human review
  • Endorsed by Shuze Chen · Oct 15, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 15, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me