Corollary 3.5 — ‖Aᴺ‖ = (1 + o(1))·2√(2d−1) with high probability, for any d = d(N)
ProvedStrongConv.tendsto_prob_norm_adjPerp_div_sub_one_leLet be any function with . For every ,
where is the adjacency matrix of the random -regular graph on vertices (permutation model) restricted to . That is, with probability . The paper does not restrict beyond "arbitrary"; excludes the empty tuple, for which is not defined.
import Mathlib import Definitions.Def_StrongConv open Filter Topology
namespace StrongConv
theorem tendsto_prob_norm_adjPerp_div_sub_one_le (d : ℕ → ℕ) (hd : ∀ N, 1 ≤ d N) (δ : ℝ)
(hδ : 0 < δ) :
Tendsto (fun N : ℕ => uniformProb (fun σ : Fin (d N) → Equiv.Perm (Fin N) =>
|‖adjPerp σ‖ / (2 * Real.sqrt (2 * d N - 1)) - 1| ≤ δ)) atTop (𝓝 1) := by
sorry
end StrongConvRead-back
What the Lean code literally says, in plain math · claude-opus-5-5
What the statement asserts
Let be any sequence of natural numbers with for every , and let be a real number. Then
where for each the probability is over , a -tuple of permutations of the -element set .
Spelled out: for every there is such that for all the probability above lies within of . The limit is the ordinary limit of a real sequence as through the natural numbers. The sequence and the number are fixed before the limit is taken; nothing restricts how grows with (it may be constant, bounded, or grow arbitrarily fast), beyond .
Here is read as a real number and is ordinary real subtraction; since , and the denominator is positive. is the real absolute value, and the event uses the non-strict inequality . Equivalently, the event is
The probability
For each , is the uniform probability on the finite set of all tuples : the number of tuples for which the event holds divided by . Equivalently, the are independent uniformly random permutations.
The operator and its norm
Give the standard Euclidean (Hilbert) norm and let
the orthogonal complement of the all-ones vector , with the inherited norm.
For a permutation , let be the operator on with (so ). It fixes and preserves inner products, hence maps into itself; let be its restriction and the Hilbert-space adjoint of as an operator on (equal to the restriction of ). Then
and is its operator norm on :
Edge cases
- Only large matter for the limit. The sequence is nonetheless defined for every , including and : there , so and the event becomes .
- may be any positive real; for the lower half of the two-sided event, , is automatic.
- The hypothesis is required for every , not only for large .
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.