op_1355_center_violation_of_partition_bounds
A center-only observable violates the weighted local variance bound whenever the center activity is one, its partition weight is between 0 and 17/16, the partition function is at least 1331, and the positive closed-neighborhood denominator is at most 33.
Statement
open scoped Classical BigOperators in theorem op_1355_center_violation_of_partition_bounds {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (lam : V → ℝ) (c : V) (hcent : lam c = 1) (hZ : (1331 : ℝ) ≤ ∑ I ∈ (Finset.univ.filter fun I : Finset V => G.IsIndepSet (I : Set V)), ∏ x ∈ I, lam x) (hP : 0 ≤ ∑ I ∈ (Finset.univ.filter fun I : Finset V => G.IsIndepSet (I : Set V) ∧ c ∈ I), ∏ x ∈ I, lam x) (hPmax : (∑ I ∈ (Finset.univ.filter fun I : Finset V => G.IsIndepSet (I : Set V) ∧ c ∈ I), ∏ x ∈ I, lam x) ≤ (17 : ℝ)/16) (hD : 0 < 1 + ∑ x ∈ insert c (G.neighborFinset c), lam x) (hDmax : 1 + (∑ x ∈ insert c (G.neighborFinset c), lam x) ≤ 33) : hardCoreWeightedVar G lam (fun x => if x = c then 1 else 0) < hardCoreWeightedClosedNeighborhoodBound G lam (fun x => if x = c then 1 else 0)
- Source
- OP-1355, explicit induced-claw witness for necessity
- Verified
- 15 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- hardCoreWeightedVarGiven a finite graph G on a type V with decidable equality, vertex fugacities lam, and observable weights a, hardCoreWeightedVar G lam a…
- hardCoreWeightedClosedNeighborhoodBoundGiven a finite graph G on a type V with decidable equality, vertex fugacities lam, and observable weights a,…
- Used by 1
- op_1355_claw_free_of_weighted_boundIf a finite simple graph G on a finite type V with decidable equality satisfies the weighted hard-core closed-neighborhood variance bound…
The proof, explained
The proof evaluates both the hard-core weighted variance and the closed-neighborhood bound for an indicator observable supported at the center vertex $c$, reducing the strict inequality to numerical arithmetic. Because the indicator takes values in $\{0, 1\}$, its expectation and second moment both equal the center-to-total partition ratio $P/Z$, so the variance simplifies to $P/Z - (P/Z)^2$, while the closed-neighborhood bound collapses to $1/D^2$ for the neighborhood denominator $D$. Using the assumptions $P \le 17/16$ and $Z \ge 1331$, the variance is at most $17/21296$, which is strictly less than $1/33^2 \le 1/D^2$ since $D \le 33$.
The ratio $P / Z$ is at most $17 / 21296$.
From the bounds $P \le 17/16$ and $Z \ge 1331$ together with positivity of the denominators and bounds, `div_le_div₀` gives $P / Z \le (17/16) / 1331$. Arithmetic evaluation via `norm_num` simplifies the right-hand side to $17 / 21296$.
uses
div_le_div₀have hquot : P / Z ≤ (17 : ℝ) / 21296 := by calc P / Z ≤ ((17 : ℝ)/16) / 1331 := div_le_div₀ (by norm_num) hPmax (by norm_num) hZ _ = (17 : ℝ)/21296 := by norm_num
The algebraic expression $P/Z - (P/Z)^2$ is strictly less than $1/D^2$. automation
From $0 < D \le 33$, squaring yields $D^2 \le 33^2$, so taking reciprocals gives $1/33^2 \le 1/D^2$ via `one_div_le_one_div_of_le` and `sq_pos_of_pos`. Since $17/21296 < 1/33^2$ numerically and $P/Z \le 17/21296$, non-linear arithmetic using $(P/Z)^2 \ge 0$ (`sq_nonneg`) deduces $P/Z - (P/Z)^2 \le P/Z < 1/33^2 \le 1/D^2$.
uses
one_div_le_one_div_of_le,sq_pos_of_pos,sq_nonneghave hDsq : D^2 ≤ (33 : ℝ)^2 := by nlinarith have hinv : 1 / (33 : ℝ)^2 ≤ 1 / D^2 := one_div_le_one_div_of_le (sq_pos_of_pos hD) hDsq have hnumeric : (17 : ℝ)/21296 < 1/(33 : ℝ)^2 := by norm_num nlinarith [sq_nonneg (P/Z)]
The numerator of the second moment of the center indicator observable simplifies to the center partition weight $P$.
Unfolding `hardCoreWeightedVar`, the observable $a(x) = \mathbf{1}_{x = c}$ sums to $1$ over an independent set $I$ if $c \in I$ and $0$ otherwise by `Finset.sum_ite_eq'`. An auxiliary lemma `hsum` proves that for any power $k > 0$, the weighted sum $\sum_{I \in \mathrm{Indep}} w(I) (\mathbf{1}_{c \in I})^k$ equals the center partition sum $P = \sum_{I \in \mathrm{Indep}, c \in I} w(I)$, by rewriting through `Finset.sum_filter` and checking set-by-set via `Finset.sum_congr` that $1^k = 1$ and $0^k = 0$. Applying `hsum` with $k = 2$ replaces the numerator of the second moment with $P$.
uses
Finset.sum_ite_eq',Finset.sum_filter,Finset.sum_congrclassical dsimp only unfold hardCoreWeightedVar simp only [Finset.sum_ite_eq'] have hsum (k : ℕ) (hk : 0 < k) : (∑ I ∈ (Finset.univ.filter fun I : Finset V => G.IsIndepSet (I : Set V)), (∏ v ∈ I, lam v) * (if c ∈ I then (1 : ℝ) else 0)^k) = ∑ I ∈ ((Finset.univ.filter fun I : Finset V => G.IsIndepSet (I : Set V)).filter (fun I => c ∈ I)), ∏ v ∈ I, lam v := by simp only [Finset.sum_filter] apply Finset.sum_congr rfl intro I hI by_cases hp : G.IsIndepSet (I : Set V) <;> by_cases hc : c ∈ I <;> simp [hp, hc, hk.ne'] rw [hsum 2 (by omega)]
The hard-core weighted variance of the center indicator observable equals $P/Z - (P/Z)^2$.
Specializing `hsum` to $k = 1$ shows that the numerator of the first moment also equals $P$. Substituting both moments into the variance formula $E_2 - E_1^2$ yields $P/Z - (P/Z)^2$.
have h1 : (∑ I ∈ (Finset.univ.filter fun I : Finset V => G.IsIndepSet (I : Set V)), (∏ v ∈ I, lam v) * (if c ∈ I then (1 : ℝ) else 0)) = ∑ I ∈ ((Finset.univ.filter fun I : Finset V => G.IsIndepSet (I : Set V)).filter (fun I => c ∈ I)), ∏ v ∈ I, lam v := by simpa using hsum 1 (by omega) rw [h1]
The weighted closed-neighborhood bound for the indicator observable at $c$ simplifies to $\lambda(c) / (1 + \sum_{u \in N[c]} \lambda(u))^2$. automation
Unfolding `hardCoreWeightedClosedNeighborhoodBound`, each vertex $v$ contributes $(a(v)^2 \lambda(v)) / (1 + \sum_{u \in N[v]} \lambda(u))^2$. For $v \neq c$, $a(v) = 0$, so the term vanishes since $0^2 = 0$ and $0 \cdot \lambda(v) = 0$. For $v = c$, $a(c)^2 = 1^2 = 1$, leaving the single term for $c$.
uses
hardCoreWeightedClosedNeighborhoodBound,ite_pow,one_pow,zero_pow,ite_mul,one_mul,zero_mul,ite_div,zero_div,Finset.sum_ite_eq',Finset.mem_univ,if_trueclassical simp only [hardCoreWeightedClosedNeighborhoodBound, ite_pow, one_pow, zero_pow (by decide : (2 : ℕ) ≠ 0), ite_mul, one_mul, zero_mul, ite_div, zero_div, Finset.sum_ite_eq', Finset.mem_univ, if_true]
The variance comparison reduces to the numerical hypotheses of the algebraic lemma.
Rewriting the variance via `op1355_center_variance_scratch` and the neighborhood bound via `op1355_center_bound_scratch`, and substituting $\lambda(c) = 1$ from `hcent`, transforms the target inequality into $P/Z - (P/Z)^2 < 1/D^2$ with $D = 1 + \sum_{u \in N[c]} \lambda(u)$. Applying `op1355_witness_algebra_scratch` leaves five hypothesis goals: $1331 \le Z$, $0 \le P$, $P \le 17/16$, $0 < D$, and $D \le 33$.
uses
op1355_center_variance_scratch,op1355_center_bound_scratch,op1355_witness_algebra_scratchclassical rw [op1355_center_variance_scratch, op1355_center_bound_scratch, hcent] apply op1355_witness_algebra_scratch
All premises of the algebraic lemma are satisfied, completing the proof.
The lower bound $1331 \le Z$ and the neighborhood denominator bounds $0 < D \le 33$ match hypotheses `hZ`, `hD`, and `hDmax` directly. The bounds $0 \le P$ and $P \le 17/16$ match `hP` and `hPmax` after combining filter predicates (`Finset.filter_filter`) and commuting conjunction (`and_comm`).
uses
Finset.filter_filter,and_comm· exact hZ · simpa [Finset.filter_filter, and_comm] using hP · simpa [Finset.filter_filter, and_comm] using hPmax · exact hD · exact hDmax
div_le_div₀- in an ordered group with zero, if $0 \le c$, $a \le c$, $0 < d$, and $d \le b$, then $a/b \le c/d$
one_div_le_one_div_of_le- if $0 < a \le b$ in a semifield, then $1/b \le 1/a$
sq_pos_of_pos- the square of a strictly positive element is strictly positive
sq_nonneg- the square of any element in a linearly ordered semiring is non-negative
Finset.sum_ite_eq'- summing a conditional term that is $b(x)$ when $x = a$ and $0$ otherwise over a finset yields $b(a)$ if $a$ belongs to the set and $0$ otherwise
Finset.sum_filter- summing over elements of a finset satisfying a predicate is equivalent to summing the function multiplied by the indicator of the predicate
Finset.sum_congr- two sums over finsets are equal if the index sets are equal and the summands agree pointwise on all elements
hardCoreWeightedClosedNeighborhoodBound- the definition of the weighted closed-neighborhood bound: $\sum_v (a(v)^2 \lambda(v)) / (1 + \sum_{u \in N[v]} \lambda(u))^2$
ite_pow- raising an if-then-else conditional expression to a power distributes the exponent into both branches
one_pow- one raised to any natural power is one
zero_pow- zero raised to any non-zero natural power is zero
ite_mul- multiplying an if-then-else conditional expression distributes the multiplication into both branches
one_mul- one is the left identity for multiplication
zero_mul- zero multiplied by any element on the left is zero
ite_div- dividing an if-then-else conditional expression distributes division into both branches
zero_div- zero divided by any element is zero
Finset.mem_univ- every element of a finite type belongs to the universal finset `Finset.univ`
if_true- a conditional whose condition is true simplifies to the true branch
op1355_center_variance_scratch- for the indicator observable at a vertex $c$, the hard-core weighted variance equals $P/Z - (P/Z)^2$, where $Z$ is the partition function and $P$ is the weight of independent sets containing $c$
op1355_center_bound_scratch- for the indicator observable at vertex $c$, the weighted closed-neighborhood bound reduces to $\lambda(c) / (1 + \sum_{u \in N[c]} \lambda(u))^2$
op1355_witness_algebra_scratch- if $1331 \le Z$, $0 \le P \le 17/16$, and $0 < D \le 33$, then $P/Z - (P/Z)^2 < 1/D^2$
Finset.filter_filter- iterated filtering of a finset by two predicates retains exactly those elements satisfying their logical conjunction
and_comm- logical conjunction is commutative: $a \land b \iff b \land a$
- Step 2 uses non-linear arithmetic automation (`nlinarith`) to deduce $P/Z - (P/Z)^2 < 1/D^2$ from the upper bound on $P/Z$, the lower bound on $1/D^2$, and the non-negativity of $(P/Z)^2$.
- Step 5 collapses the sum defining the neighborhood bound in a single automated simplification call (`simp only`), evaluating powers and multiplications by zero for all vertices other than $c$.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
open scoped BigOperatorslemma op1355_witness_algebra_scratch (Z P D : ℝ) (hZ : (1331 : ℝ) ≤ Z) (hP : 0 ≤ P) (hPmax : P ≤ (17 : ℝ)/16) (hD : 0 < D) (hDmax : D ≤ 33) : P / Z - (P / Z)^2 < 1 / D^2 := by have hquot : P / Z ≤ (17 : ℝ) / 21296 := by calc P / Z ≤ ((17 : ℝ)/16) / 1331 := div_le_div₀ (by norm_num) hPmax (by norm_num) hZ _ = (17 : ℝ)/21296 := by norm_num have hDsq : D^2 ≤ (33 : ℝ)^2 := by nlinarith have hinv : 1 / (33 : ℝ)^2 ≤ 1 / D^2 := one_div_le_one_div_of_le (sq_pos_of_pos hD) hDsq have hnumeric : (17 : ℝ)/21296 < 1/(33 : ℝ)^2 := by norm_num nlinarith [sq_nonneg (P/Z)]lemma op1355_center_variance_scratch {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (lam : V → ℝ) (c : V) : let fam : Finset (Finset V) := Finset.univ.filter fun I => G.IsIndepSet (I : Set V) let Z : ℝ := ∑ I ∈ fam, ∏ v ∈ I, lam v let P : ℝ := ∑ I ∈ fam.filter (fun I => c ∈ I), ∏ v ∈ I, lam v hardCoreWeightedVar G lam (fun x => if x = c then 1 else 0) = P/Z - (P/Z)^2 := by classical dsimp only unfold hardCoreWeightedVar simp only [Finset.sum_ite_eq'] have hsum (k : ℕ) (hk : 0 < k) : (∑ I ∈ (Finset.univ.filter fun I : Finset V => G.IsIndepSet (I : Set V)), (∏ v ∈ I, lam v) * (if c ∈ I then (1 : ℝ) else 0)^k) = ∑ I ∈ ((Finset.univ.filter fun I : Finset V => G.IsIndepSet (I : Set V)).filter (fun I => c ∈ I)), ∏ v ∈ I, lam v := by simp only [Finset.sum_filter] apply Finset.sum_congr rfl intro I hI by_cases hp : G.IsIndepSet (I : Set V) <;> by_cases hc : c ∈ I <;> simp [hp, hc, hk.ne'] rw [hsum 2 (by omega)] have h1 : (∑ I ∈ (Finset.univ.filter fun I : Finset V => G.IsIndepSet (I : Set V)), (∏ v ∈ I, lam v) * (if c ∈ I then (1 : ℝ) else 0)) = ∑ I ∈ ((Finset.univ.filter fun I : Finset V => G.IsIndepSet (I : Set V)).filter (fun I => c ∈ I)), ∏ v ∈ I, lam v := by simpa using hsum 1 (by omega) rw [h1]lemma op1355_center_bound_scratch {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (lam : V → ℝ) (c : V) : hardCoreWeightedClosedNeighborhoodBound G lam (fun x => if x = c then 1 else 0) = lam c / (1 + ∑ u ∈ insert c (G.neighborFinset c), lam u)^2 := by classical simp only [hardCoreWeightedClosedNeighborhoodBound, ite_pow, one_pow, zero_pow (by decide : (2 : ℕ) ≠ 0), ite_mul, one_mul, zero_mul, ite_div, zero_div, Finset.sum_ite_eq', Finset.mem_univ, if_true]open scoped Classical BigOperators intheorem op_1355_center_violation_of_partition_bounds {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (lam : V → ℝ) (c : V) (hcent : lam c = 1) (hZ : (1331 : ℝ) ≤ ∑ I ∈ (Finset.univ.filter fun I : Finset V => G.IsIndepSet (I : Set V)), ∏ x ∈ I, lam x) (hP : 0 ≤ ∑ I ∈ (Finset.univ.filter fun I : Finset V => G.IsIndepSet (I : Set V) ∧ c ∈ I), ∏ x ∈ I, lam x) (hPmax : (∑ I ∈ (Finset.univ.filter fun I : Finset V => G.IsIndepSet (I : Set V) ∧ c ∈ I), ∏ x ∈ I, lam x) ≤ (17 : ℝ)/16) (hD : 0 < 1 + ∑ x ∈ insert c (G.neighborFinset c), lam x) (hDmax : 1 + (∑ x ∈ insert c (G.neighborFinset c), lam x) ≤ 33) : hardCoreWeightedVar G lam (fun x => if x = c then 1 else 0) < hardCoreWeightedClosedNeighborhoodBound G lam (fun x => if x = c then 1 else 0) := by classical rw [op1355_center_variance_scratch, op1355_center_bound_scratch, hcent] apply op1355_witness_algebra_scratch · exact hZ · simpa [Finset.filter_filter, and_comm] using hP · simpa [Finset.filter_filter, and_comm] using hPmax · exact hD · exact hDmax