AFTD Auto-Formalizing Theoretical Domains

op_1355_center_violation_of_partition_bounds

theoremverified

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$.

  1. 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$.

    lines 7–10

    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
  2. 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$.

    lines 11–15

    uses one_div_le_one_div_of_le, sq_pos_of_pos, sq_nonneg

      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)]
  3. 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$.

    lines 25–37

    uses Finset.sum_ite_eq', Finset.sum_filter, Finset.sum_congr

      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)]
  4. 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$.

    lines 38–43

      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]
  5. 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$.

    lines 49–50

    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_true

      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]
  6. 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$.

    lines 63–65

    uses op1355_center_variance_scratch, op1355_center_bound_scratch, op1355_witness_algebra_scratch

      classical
      rw [op1355_center_variance_scratch, op1355_center_bound_scratch, hcent]
      apply op1355_witness_algebra_scratch
  7. 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`).

    lines 66–70

    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$

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

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
See it in the graphDiscuss this resultChallenge it