AFTD Auto-Formalizing Theoretical Domains

op_1239_at_most_two_nonzero_coeffs_log_concave

theoremverifiedformalization

Every simple graph G on a finite type V with decidable equality and decidable adjacency for which the number of k in the range from 0 to Fintype.card V + 1 with petrial_coeff G k ≠ 0 is at most 2 satisfies petrial_log_concave G.

Statement

theorem op_1239_at_most_two_nonzero_coeffs_log_concave
    {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj]
    (h : ((Finset.range (Fintype.card V + 1)).filter (fun k => petrial_coeff G k ≠ 0)).card ≤ 2) :
    petrial_log_concave G
Formalizes
arXiv:2611.07503, Section 2
Verified
07 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
  • petrial_log_concaveA simple graph G on a finite type V with decidable equality and decidable adjacency has a log-concave partial Petrial polynomial if for…
  • petrial_coeffGiven a finite type V with decidable equality, a simple graph G on V with decidable adjacency, and k : ℕ, petrial_coeff G k is the…
  • petrial_matrixGiven a finite type V with decidable equality, a simple graph G on V with decidable adjacency, and a finite subset F : Finset V,…

Read back from the Lean

Let $V$ be a finite type with decidable equality, and let $G$ be a simple graph on $V$ with decidable adjacency. Suppose that the number of natural numbers $k \in \{0, 1, \dots, |V|\}$ such that $\operatorname{petrial\_coeff}(G, k) \neq 0$ is at most $2$. Then $G$ is $\operatorname{petrial\_log\_concave}$, meaning that for every $k \in \mathbb{N}$, if there exists $i < k$ with $\operatorname{petrial\_coeff}(G, i) \neq 0$ and there exists $j > k$ with $\operatorname{petrial\_coeff}(G, j) \neq 0$, then $\operatorname{petrial\_coeff}(G, k - 1) \cdot \operatorname{petrial\_coeff}(G, k + 1) \le (\operatorname{petrial\_coeff}(G, k))^2$.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

The proof shows that any graph with at most two non-zero Petrial coefficients satisfies the log-concavity condition vacuously, because the condition's premise can never be met. By induction on the symmetric difference between vertex subsets, the rank of the Petrial matrix over ℤ/2ℤ satisfies an intermediate value theorem: adding or deleting a single vertex changes the rank by at most 1, so every integer between two realizable ranks is also realized by some subset. Therefore, having non-zero coefficients at indices i < k and j > k forces the intermediate coefficient at k to be non-zero as well. This would yield at least three distinct non-zero coefficients, directly contradicting the hypothesis that at most two coefficients are non-zero.

  1. The rank of the sum of two matrices is at most the sum of their ranks: (A + B).rank ≤ A.rank + B.rank.

    Unfolding the definition of rank as the dimension of the range of the corresponding linear map, the range of A + B is contained in the sum of the ranges of A and B. Monotonicity of submodule dimension and subadditivity of the dimension of a submodule sum bound the rank of A + B by the sum of the ranks.

    lines 5–11

    uses Matrix.mulVecLin_add, LinearMap.range_add_le, Submodule.finrank_mono, Submodule.finrank_add_le_finrank_add_finrank

      unfold Matrix.rank
      rw [Matrix.mulVecLin_add]
      have hle : LinearMap.range (A.mulVecLin + B.mulVecLin) ≤ LinearMap.range A.mulVecLin ⊔ LinearMap.range B.mulVecLin :=
        LinearMap.range_add_le _ _
      have h1 := Submodule.finrank_mono hle
      have h2 := Submodule.finrank_add_le_finrank_add_finrank (LinearMap.range A.mulVecLin) (LinearMap.range B.mulVecLin)
      omega
  2. A diagonal matrix over ℤ/2ℤ with at most one non-zero entry on the diagonal has rank at most 1.

    The rank of a diagonal matrix equals the number of non-zero diagonal entries. Since the entries are 0 everywhere except possibly at index v, the set of non-zero entries is contained in the singleton {v}, whose cardinality is 1.

    lines 16–26

    uses Matrix.rank_diagonal, Fintype.card_subtype, Finset.card_le_card, Finset.card_singleton

      rw [Matrix.rank_diagonal]
      rw [Fintype.card_subtype]
      have : (Finset.univ.filter (fun w => (if w = v then (1 : ZMod 2) else 0) ≠ 0)) ⊆ {v} := by
        intro w hw
        simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hw
        split_ifs at hw with h
        · exact Finset.mem_singleton.mpr h
        · contradiction
      have hsub := Finset.card_le_card this
      simp only [Finset.card_singleton] at hsub
      exact hsub
  3. For any vertex subset F and vertex v ∉ F, the Petrial matrix of F ∪ {v} equals the Petrial matrix of F plus the diagonal matrix with 1 at entry (v, v).

    The Petrial matrix adds a diagonal indicator of the subset to the adjacency matrix. Inserting v into F changes only the diagonal entry at (v, v) from 0 to 1, which equals adding the single-entry diagonal matrix for v.

    lines 33–42

    uses Matrix.add_apply, Matrix.diagonal_apply, Finset.mem_insert

      unfold petrial_matrix
      ext i j
      simp only [Matrix.add_apply, Matrix.diagonal_apply, Finset.mem_insert]
      by_cases hij : i = j
      · subst hij
        by_cases hiv : i = v
        · subst hiv
          simp [hv]
        · simp [hiv]
      · simp [hij]
  4. For any vertex subset F and vertex v ∉ F, the Petrial matrix of F equals the Petrial matrix of F ∪ {v} plus the diagonal matrix with 1 at entry (v, v).

    Over the field ℤ/2ℤ, addition and subtraction coincide since 1 + 1 = 0. Adding the diagonal matrix at v to the Petrial matrix of F ∪ {v} resets the (v, v) entry from 1 to 0 while leaving all other entries unchanged, recovering the Petrial matrix of F.

    lines 49–59

    uses Matrix.add_apply, Matrix.diagonal_apply, Finset.mem_insert

      unfold petrial_matrix
      ext i j
      simp only [Matrix.add_apply, Matrix.diagonal_apply, Finset.mem_insert]
      by_cases hij : i = j
      · subst hij
        by_cases hiv : i = v
        · subst hiv
          have : (1 : ZMod 2) + 1 = 0 := rfl
          simp [hv, this]
        · simp [hiv]
      · simp [hij]
  5. Inserting a vertex v ∉ F increases the Petrial matrix rank by at most 1: (petrial_matrix G (insert v F)).rank ≤ (petrial_matrix G F).rank + 1.

    Rewriting the Petrial matrix of F ∪ {v} as the sum of the Petrial matrix of F and the single-entry diagonal matrix at v, the claim follows from rank subadditivity and the fact that the single-entry diagonal matrix has rank at most 1.

    lines 65–69

    uses op_1239_at_most_two_nonzero_coeffs_log_concave_petrial_matrix_insert, op_1239_at_most_two_nonzero_coeffs_log_concave_matrix_rank_add_le, op_1239_at_most_two_nonzero_coeffs_log_concave_rank_single_diag_le

      rw [op_1239_at_most_two_nonzero_coeffs_log_concave_petrial_matrix_insert G F v hv]
      have := op_1239_at_most_two_nonzero_coeffs_log_concave_matrix_rank_add_le (petrial_matrix G F)
        (Matrix.diagonal (fun w => if w = v then (1 : ZMod 2) else 0))
      have h1 := op_1239_at_most_two_nonzero_coeffs_log_concave_rank_single_diag_le v
      omega
  6. Removing a vertex v from F ∪ {v} changes the Petrial matrix rank by at most 1: (petrial_matrix G F).rank ≤ (petrial_matrix G (insert v F)).rank + 1.

    Expressing the Petrial matrix of F as the Petrial matrix of F ∪ {v} plus the single-entry diagonal matrix at v over ℤ/2ℤ, subadditivity of rank bounds the rank of F by that of F ∪ {v} plus 1.

    lines 75–79

    uses op_1239_at_most_two_nonzero_coeffs_log_concave_petrial_matrix_remove, op_1239_at_most_two_nonzero_coeffs_log_concave_matrix_rank_add_le, op_1239_at_most_two_nonzero_coeffs_log_concave_rank_single_diag_le

      rw [op_1239_at_most_two_nonzero_coeffs_log_concave_petrial_matrix_remove G F v hv]
      have := op_1239_at_most_two_nonzero_coeffs_log_concave_matrix_rank_add_le (petrial_matrix G (insert v F))
        (Matrix.diagonal (fun w => if w = v then (1 : ZMod 2) else 0))
      have h1 := op_1239_at_most_two_nonzero_coeffs_log_concave_rank_single_diag_le v
      omega
  7. For any v ∈ A, erasing v from A increases the Petrial matrix rank by at most 1: (petrial_matrix G (A.erase v)).rank ≤ (petrial_matrix G A).rank + 1.

    Setting F = A \ {v}, the element v is not in F and insert v F = A. Applying the previous lemma with F immediately yields the bound.

    lines 85–88

    uses Finset.insert_erase, op_1239_at_most_two_nonzero_coeffs_log_concave_petrial_matrix_rank_erase_le

      have hnot : v ∉ A.erase v := by simp
      have hins : insert v (A.erase v) = A := Finset.insert_erase hv
      have := op_1239_at_most_two_nonzero_coeffs_log_concave_petrial_matrix_rank_erase_le G (A.erase v) v hnot
      rwa [hins] at this
  8. The intermediate rank theorem holds in the base case where A = B.

    We proceed by strong induction on the size of the symmetric difference n = |A \ B| + |B \ A|. When both differences have cardinality 0, mutual subset inclusion forces A = B. The given bounds rank(A) ≤ k ≤ rank(B) = rank(A) imply rank(A) = k, so A itself is the witness.

    lines 96–105

    uses Nat.strong_induction_on, Finset.card_eq_zero, Finset.sdiff_eq_empty_iff_subset, Finset.Subset.antisymm

      intro n
      induction' n using Nat.strong_induction_on with n ih
      intro A B hn k hA hB
      by_cases hAB_sdiff : (A \ B).card = 0
      · by_cases hBA_sdiff : (B \ A).card = 0
        · have h_eq : A = B := by
            rw [Finset.card_eq_zero, Finset.sdiff_eq_empty_iff_subset] at hAB_sdiff hBA_sdiff
            exact Finset.Subset.antisymm hAB_sdiff hBA_sdiff
          subst h_eq
          exact ⟨A, by omega⟩
  9. When A ⊊ B, there exists a vertex subset C with Petrial matrix rank exactly k.

    Pick v ∈ B \ A and set A' = A ∪ {v}. Adding v decreases the symmetric difference size |A' \ B| + |B \ A'| by 1, so the induction hypothesis applies. Since rank(A') ≤ rank(A) + 1, either rank(A') ≤ k, in which case the induction hypothesis on (A', B) provides the witness, or rank(A') > k ≥ rank(A), in which case rank(A) must equal k, making A the witness.

    lines 106–132

    uses Finset.card_erase_of_mem, op_1239_at_most_two_nonzero_coeffs_log_concave_petrial_matrix_rank_insert_le

        · obtain ⟨v, hv⟩ := Finset.card_pos.mp (Nat.pos_of_ne_zero hBA_sdiff)
          have hvB : v ∈ B := (Finset.mem_sdiff.mp hv).1
          have hvA : v ∉ A := (Finset.mem_sdiff.mp hv).2
          have hstep : ((insert v A) \ B).card + (B \ (insert v A)).card + 1 = (A \ B).card + (B \ A).card := by
            have h1 : (insert v A) \ B = A \ B := by
              ext x
              simp only [Finset.mem_sdiff, Finset.mem_insert]
              constructor
              · rintro ⟨h1 | h1, h2⟩
                · subst h1; contradiction
                · exact ⟨h1, h2⟩
              · rintro ⟨h1, h2⟩
                exact ⟨Or.inr h1, h2⟩
            have h2 : B \ (insert v A) = (B \ A).erase v := by
              ext x
              simp only [Finset.mem_sdiff, Finset.mem_insert, Finset.mem_erase]
              tauto
            rw [h1, h2]
            have hcard := Finset.card_erase_of_mem hv
            have hpos : 1 ≤ (B \ A).card := Finset.card_pos.mpr ⟨v, hv⟩
            omega
          have hlt : ((insert v A) \ B).card + (B \ (insert v A)).card < n := by omega
          have hle_ins := op_1239_at_most_two_nonzero_coeffs_log_concave_petrial_matrix_rank_insert_le G A v hvA
          by_cases hk_ins : (petrial_matrix G (insert v A)).rank ≤ k
          · exact ih _ hlt (insert v A) B rfl k hk_ins hB
          · have : (petrial_matrix G A).rank = k := by omega
            exact ⟨A, this⟩
  10. When A \ B is non-empty, there exists a vertex subset C with Petrial matrix rank exactly k.

    Pick v ∈ A \ B and set A' = A \ {v}. Erasing v decreases the symmetric difference size by 1. Since rank(A') ≤ rank(A) + 1, either rank(A') ≤ k and the induction hypothesis on (A', B) yields the witness, or rank(A) = k and A is the witness.

    lines 133–160

    uses Finset.card_erase_of_mem, op_1239_at_most_two_nonzero_coeffs_log_concave_petrial_matrix_rank_erase_le'

      · obtain ⟨v, hv⟩ := Finset.card_pos.mp (Nat.pos_of_ne_zero hAB_sdiff)
        have hvA : v ∈ A := (Finset.mem_sdiff.mp hv).1
        have hvB : v ∉ B := (Finset.mem_sdiff.mp hv).2
        have hstep : ((A.erase v) \ B).card + (B \ (A.erase v)).card + 1 = (A \ B).card + (B \ A).card := by
          have h1 : (A.erase v) \ B = (A \ B).erase v := by
            ext x
            simp only [Finset.mem_sdiff, Finset.mem_erase]
            tauto
          have h2 : B \ (A.erase v) = B \ A := by
            ext x
            simp only [Finset.mem_sdiff, Finset.mem_erase]
            constructor
            · rintro ⟨hxB, hx⟩
              refine ⟨hxB, ?_⟩
              rintro hxA
              exact hx ⟨fun hxv => hvB (hxv ▸ hxB), hxA⟩
            · rintro ⟨hxB, hxA⟩
              exact ⟨hxB, fun ⟨_, h⟩ => hxA h⟩
          rw [h1, h2]
          have hcard := Finset.card_erase_of_mem hv
          have hpos : 1 ≤ (A \ B).card := Finset.card_pos.mpr ⟨v, hv⟩
          omega
        have hlt : ((A.erase v) \ B).card + (B \ (A.erase v)).card < n := by omega
        have hle_erase := op_1239_at_most_two_nonzero_coeffs_log_concave_petrial_matrix_rank_erase_le' G A v hvA
        by_cases hk_erase : (petrial_matrix G (A.erase v)).rank ≤ k
        · exact ih _ hlt (A.erase v) B rfl k hk_erase hB
        · have : (petrial_matrix G A).rank = k := by omega
          exact ⟨A, this⟩
  11. If there exist i < k and j > k with non-zero Petrial coefficients, then the k-th Petrial coefficient is also non-zero.

    Non-vanishing of the i-th and j-th coefficients yields subsets Fi and Fj with Petrial matrix ranks i and j. By the intermediate rank theorem, there exists a subset Fk whose Petrial matrix rank is exactly k. Hence the set of subsets with Petrial rank k is non-empty, so petrial_coeff G k ≠ 0.

    lines 167–185

    uses op_1239_at_most_two_nonzero_coeffs_log_concave_exists_intermediate_rank

      intro k hi hj
      obtain ⟨i, hik, hic⟩ := hi
      obtain ⟨j, hkj, hjc⟩ := hj
      obtain ⟨Fi, hFi⟩ := Finset.card_ne_zero.mp hic
      simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hFi
      obtain ⟨Fj, hFj⟩ := Finset.card_ne_zero.mp hjc
      simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hFj
      have hFi_rank : (petrial_matrix G Fi).rank ≤ k := by rw [hFi]; omega
      have hFj_rank : k ≤ (petrial_matrix G Fj).rank := by rw [hFj]; omega
      obtain ⟨Fk, hFk⟩ := op_1239_at_most_two_nonzero_coeffs_log_concave_exists_intermediate_rank
        G ((Fi \ Fj).card + (Fj \ Fi).card) Fi Fj rfl k hFi_rank hFj_rank
      have hkc : petrial_coeff G k ≠ 0 := by
        unfold petrial_coeff
        intro h0
        have hmem : Fk ∈ (Finset.univ : Finset (Finset V)).filter (fun F' => (petrial_matrix G F').rank = k) := by
          simp [hFk]
        have : (Finset.univ.filter (fun F' => (petrial_matrix G F').rank = k)).card ≠ 0 :=
          Finset.card_ne_zero.mpr ⟨Fk, hmem⟩
        exact this h0
  12. Graph G satisfies petrial_log_concave G because the premise of the log-concavity condition is vacuous.

    The matrix ranks are bounded by the number of vertices. If there were indices i < k < j with non-zero coefficients, then all three would belong to the support S of the Petrial polynomial. Since i < k < j, the set {i, k, j} has cardinality 3, so |S| ≥ 3, contradicting the hypothesis |S| ≤ 2. Hence no such indices can exist and the implication holds vacuously.

    lines 186–219

    uses Matrix.rank_le_card_width, Finset.card_insert_of_notMem, Finset.card_singleton, Finset.card_le_card

      have hi_le : i ≤ Fintype.card V := by
        have := Matrix.rank_le_card_width (petrial_matrix G Fi)
        omega
      have hj_le : j ≤ Fintype.card V := by
        have := Matrix.rank_le_card_width (petrial_matrix G Fj)
        omega
      let S := (Finset.range (Fintype.card V + 1)).filter (fun m => petrial_coeff G m ≠ 0)
      have hi_in : i ∈ S := by
        simp only [Finset.mem_filter, Finset.mem_range, S]
        exact ⟨by omega, hic⟩
      have hj_in : j ∈ S := by
        simp only [Finset.mem_filter, Finset.mem_range, S]
        exact ⟨by omega, hjc⟩
      have hk_in : k ∈ S := by
        simp only [Finset.mem_filter, Finset.mem_range, S]
        exact ⟨by omega, hkc⟩
      have h_sub : {i, k, j} ⊆ S := by
        intro x hx
        simp only [Finset.mem_insert, Finset.mem_singleton] at hx
        rcases hx with rfl | rfl | rfl
        · exact hi_in
        · exact hk_in
        · exact hj_in
      have h_card_three : ({i, k, j} : Finset ℕ).card = 3 := by
        rw [Finset.card_insert_of_notMem, Finset.card_insert_of_notMem, Finset.card_singleton]
        · simp only [Finset.mem_singleton]
          omega
        · simp only [Finset.mem_insert, Finset.mem_singleton]
          rintro (rfl | rfl) <;> omega
      have h_le := Finset.card_le_card h_sub
      rw [h_card_three] at h_le
      change S.card ≤ 2 at h
      exfalso
      omega
Matrix.mulVecLin_add
The linear map associated with the sum of two matrices is the sum of their individual linear maps.
LinearMap.range_add_le
The range of the sum of two linear maps is contained in the supremum (span) of their individual ranges.
Submodule.finrank_mono
If one submodule is contained in another, its dimension (finrank) is at most the dimension of the containing submodule.
Submodule.finrank_add_le_finrank_add_finrank
The dimension of the sum (supremum) of two submodules is at most the sum of their individual dimensions.
Matrix.rank_diagonal
The rank of a diagonal matrix equals the number of non-zero entries on its diagonal.
Fintype.card_subtype
The cardinality of a subtype defined by a predicate equals the cardinality of the finset of elements satisfying the predicate.
Finset.card_le_card
If one finite set is a subset of another, its cardinality is at most the cardinality of the superset.
Finset.card_singleton
A singleton set has cardinality 1.
Matrix.add_apply
The (i, j)-th entry of the sum of two matrices is the sum of their (i, j)-th entries.
Matrix.diagonal_apply
The (i, j)-th entry of a diagonal matrix is the diagonal element if i = j and 0 otherwise.
Finset.mem_insert
An element belongs to the insertion of an element into a set if and only if it equals the inserted element or belongs to the original set.
op_1239_at_most_two_nonzero_coeffs_log_concave_petrial_matrix_insert
Adding a vertex v ∉ F to F changes the Petrial matrix by adding a diagonal matrix with 1 at (v, v) and 0 elsewhere.
op_1239_at_most_two_nonzero_coeffs_log_concave_matrix_rank_add_le
The rank of the sum of two matrices is at most the sum of their individual ranks.
op_1239_at_most_two_nonzero_coeffs_log_concave_rank_single_diag_le
A diagonal matrix with at most one non-zero entry on the diagonal has rank at most 1.
op_1239_at_most_two_nonzero_coeffs_log_concave_petrial_matrix_remove
Over ℤ/2ℤ, the Petrial matrix of F equals the Petrial matrix of F ∪ {v} plus the diagonal matrix with 1 at (v, v).
Finset.insert_erase
Inserting an element into a finite set from which it was removed recovers the original set.
op_1239_at_most_two_nonzero_coeffs_log_concave_petrial_matrix_rank_erase_le
Removing a vertex from F ∪ {v} changes the rank of the Petrial matrix by at most 1.
Nat.strong_induction_on
The principle of strong mathematical induction on ℕ.
Finset.card_eq_zero
A finite set has cardinality zero if and only if it is empty.
Finset.sdiff_eq_empty_iff_subset
The difference of two sets is empty if and only if the first is a subset of the second.
Finset.Subset.antisymm
If two finite sets are subsets of each other, they are equal.
Finset.card_erase_of_mem
Removing an element from a finite set containing it decreases its cardinality by 1.
op_1239_at_most_two_nonzero_coeffs_log_concave_petrial_matrix_rank_insert_le
Inserting a vertex into a vertex subset increases the rank of the Petrial matrix by at most 1.
op_1239_at_most_two_nonzero_coeffs_log_concave_petrial_matrix_rank_erase_le'
Erasing a vertex from a vertex subset increases the rank of the Petrial matrix by at most 1.
op_1239_at_most_two_nonzero_coeffs_log_concave_exists_intermediate_rank
For any two vertex subsets, every integer between their Petrial matrix ranks is realized as the rank of some intermediate vertex subset.
Matrix.rank_le_card_width
The rank of a matrix is at most the number of its columns.
Finset.card_insert_of_notMem
Inserting an element into a finite set that does not contain it increases its cardinality by 1.

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

lemma op_1239_at_most_two_nonzero_coeffs_log_concave_matrix_rank_add_le    {m n : Type*} [Fintype m] [Fintype n] [DecidableEq m] [DecidableEq n]    {K : Type*} [Field K] (A B : Matrix m n K) :    (A + B).rank ≤ A.rank + B.rank := by  unfold Matrix.rank  rw [Matrix.mulVecLin_add]  have hle : LinearMap.range (A.mulVecLin + B.mulVecLin) ≤ LinearMap.range A.mulVecLin ⊔ LinearMap.range B.mulVecLin :=    LinearMap.range_add_le _ _  have h1 := Submodule.finrank_mono hle  have h2 := Submodule.finrank_add_le_finrank_add_finrank (LinearMap.range A.mulVecLin) (LinearMap.range B.mulVecLin)  omegalemma op_1239_at_most_two_nonzero_coeffs_log_concave_rank_single_diag_le    {V : Type*} [Fintype V] [DecidableEq V] (v : V) :    (Matrix.diagonal (fun w => if w = v then (1 : ZMod 2) else 0)).rank ≤ 1 := by  rw [Matrix.rank_diagonal]  rw [Fintype.card_subtype]  have : (Finset.univ.filter (fun w => (if w = v then (1 : ZMod 2) else 0) ≠ 0)) ⊆ {v} := by    intro w hw    simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hw    split_ifs at hw with h    · exact Finset.mem_singleton.mpr h    · contradiction  have hsub := Finset.card_le_card this  simp only [Finset.card_singleton] at hsub  exact hsublemma op_1239_at_most_two_nonzero_coeffs_log_concave_petrial_matrix_insert    {V : Type*} [Fintype V] [DecidableEq V]    (G : SimpleGraph V) [DecidableRel G.Adj] (F : Finset V) (v : V) (hv : v ∉ F) :    petrial_matrix G (insert v F) =      petrial_matrix G F + Matrix.diagonal (fun w => if w = v then (1 : ZMod 2) else 0) := by  unfold petrial_matrix  ext i j  simp only [Matrix.add_apply, Matrix.diagonal_apply, Finset.mem_insert]  by_cases hij : i = j  · subst hij    by_cases hiv : i = v    · subst hiv      simp [hv]    · simp [hiv]  · simp [hij]lemma op_1239_at_most_two_nonzero_coeffs_log_concave_petrial_matrix_remove    {V : Type*} [Fintype V] [DecidableEq V]    (G : SimpleGraph V) [DecidableRel G.Adj] (F : Finset V) (v : V) (hv : v ∉ F) :    petrial_matrix G F =      petrial_matrix G (insert v F) + Matrix.diagonal (fun w => if w = v then (1 : ZMod 2) else 0) := by  unfold petrial_matrix  ext i j  simp only [Matrix.add_apply, Matrix.diagonal_apply, Finset.mem_insert]  by_cases hij : i = j  · subst hij    by_cases hiv : i = v    · subst hiv      have : (1 : ZMod 2) + 1 = 0 := rfl      simp [hv, this]    · simp [hiv]  · simp [hij]lemma op_1239_at_most_two_nonzero_coeffs_log_concave_petrial_matrix_rank_insert_le    {V : Type*} [Fintype V] [DecidableEq V]    (G : SimpleGraph V) [DecidableRel G.Adj] (F : Finset V) (v : V) (hv : v ∉ F) :    (petrial_matrix G (insert v F)).rank ≤ (petrial_matrix G F).rank + 1 := by  rw [op_1239_at_most_two_nonzero_coeffs_log_concave_petrial_matrix_insert G F v hv]  have := op_1239_at_most_two_nonzero_coeffs_log_concave_matrix_rank_add_le (petrial_matrix G F)    (Matrix.diagonal (fun w => if w = v then (1 : ZMod 2) else 0))  have h1 := op_1239_at_most_two_nonzero_coeffs_log_concave_rank_single_diag_le v  omegalemma op_1239_at_most_two_nonzero_coeffs_log_concave_petrial_matrix_rank_erase_le    {V : Type*} [Fintype V] [DecidableEq V]    (G : SimpleGraph V) [DecidableRel G.Adj] (F : Finset V) (v : V) (hv : v ∉ F) :    (petrial_matrix G F).rank ≤ (petrial_matrix G (insert v F)).rank + 1 := by  rw [op_1239_at_most_two_nonzero_coeffs_log_concave_petrial_matrix_remove G F v hv]  have := op_1239_at_most_two_nonzero_coeffs_log_concave_matrix_rank_add_le (petrial_matrix G (insert v F))    (Matrix.diagonal (fun w => if w = v then (1 : ZMod 2) else 0))  have h1 := op_1239_at_most_two_nonzero_coeffs_log_concave_rank_single_diag_le v  omegalemma op_1239_at_most_two_nonzero_coeffs_log_concave_petrial_matrix_rank_erase_le'    {V : Type*} [Fintype V] [DecidableEq V]    (G : SimpleGraph V) [DecidableRel G.Adj] (A : Finset V) (v : V) (hv : v ∈ A) :    (petrial_matrix G (A.erase v)).rank ≤ (petrial_matrix G A).rank + 1 := by  have hnot : v ∉ A.erase v := by simp  have hins : insert v (A.erase v) = A := Finset.insert_erase hv  have := op_1239_at_most_two_nonzero_coeffs_log_concave_petrial_matrix_rank_erase_le G (A.erase v) v hnot  rwa [hins] at thislemma op_1239_at_most_two_nonzero_coeffs_log_concave_exists_intermediate_rank    {V : Type*} [Fintype V] [DecidableEq V]    (G : SimpleGraph V) [DecidableRel G.Adj] :    ∀ (n : ℕ) (A B : Finset V), (A \ B).card + (B \ A).card = n →      ∀ k : ℕ, (petrial_matrix G A).rank ≤ k → k ≤ (petrial_matrix G B).rank →      ∃ C : Finset V, (petrial_matrix G C).rank = k := by  intro n  induction' n using Nat.strong_induction_on with n ih  intro A B hn k hA hB  by_cases hAB_sdiff : (A \ B).card = 0  · by_cases hBA_sdiff : (B \ A).card = 0    · have h_eq : A = B := by        rw [Finset.card_eq_zero, Finset.sdiff_eq_empty_iff_subset] at hAB_sdiff hBA_sdiff        exact Finset.Subset.antisymm hAB_sdiff hBA_sdiff      subst h_eq      exact ⟨A, by omega⟩    · obtain ⟨v, hv⟩ := Finset.card_pos.mp (Nat.pos_of_ne_zero hBA_sdiff)      have hvB : v ∈ B := (Finset.mem_sdiff.mp hv).1      have hvA : v ∉ A := (Finset.mem_sdiff.mp hv).2      have hstep : ((insert v A) \ B).card + (B \ (insert v A)).card + 1 = (A \ B).card + (B \ A).card := by        have h1 : (insert v A) \ B = A \ B := by          ext x          simp only [Finset.mem_sdiff, Finset.mem_insert]          constructor          · rintro ⟨h1 | h1, h2⟩            · subst h1; contradiction            · exact ⟨h1, h2⟩          · rintro ⟨h1, h2⟩            exact ⟨Or.inr h1, h2⟩        have h2 : B \ (insert v A) = (B \ A).erase v := by          ext x          simp only [Finset.mem_sdiff, Finset.mem_insert, Finset.mem_erase]          tauto        rw [h1, h2]        have hcard := Finset.card_erase_of_mem hv        have hpos : 1 ≤ (B \ A).card := Finset.card_pos.mpr ⟨v, hv⟩        omega      have hlt : ((insert v A) \ B).card + (B \ (insert v A)).card < n := by omega      have hle_ins := op_1239_at_most_two_nonzero_coeffs_log_concave_petrial_matrix_rank_insert_le G A v hvA      by_cases hk_ins : (petrial_matrix G (insert v A)).rank ≤ k      · exact ih _ hlt (insert v A) B rfl k hk_ins hB      · have : (petrial_matrix G A).rank = k := by omega        exact ⟨A, this⟩  · obtain ⟨v, hv⟩ := Finset.card_pos.mp (Nat.pos_of_ne_zero hAB_sdiff)    have hvA : v ∈ A := (Finset.mem_sdiff.mp hv).1    have hvB : v ∉ B := (Finset.mem_sdiff.mp hv).2    have hstep : ((A.erase v) \ B).card + (B \ (A.erase v)).card + 1 = (A \ B).card + (B \ A).card := by      have h1 : (A.erase v) \ B = (A \ B).erase v := by        ext x        simp only [Finset.mem_sdiff, Finset.mem_erase]        tauto      have h2 : B \ (A.erase v) = B \ A := by        ext x        simp only [Finset.mem_sdiff, Finset.mem_erase]        constructor        · rintro ⟨hxB, hx⟩          refine ⟨hxB, ?_⟩          rintro hxA          exact hx ⟨fun hxv => hvB (hxv ▸ hxB), hxA⟩        · rintro ⟨hxB, hxA⟩          exact ⟨hxB, fun ⟨_, h⟩ => hxA h⟩      rw [h1, h2]      have hcard := Finset.card_erase_of_mem hv      have hpos : 1 ≤ (A \ B).card := Finset.card_pos.mpr ⟨v, hv⟩      omega    have hlt : ((A.erase v) \ B).card + (B \ (A.erase v)).card < n := by omega    have hle_erase := op_1239_at_most_two_nonzero_coeffs_log_concave_petrial_matrix_rank_erase_le' G A v hvA    by_cases hk_erase : (petrial_matrix G (A.erase v)).rank ≤ k    · exact ih _ hlt (A.erase v) B rfl k hk_erase hB    · have : (petrial_matrix G A).rank = k := by omega      exact ⟨A, this⟩/-- Graphs with at most two nonzero Petrial coefficients have log-concave partial Petrial polynomials. -/theorem op_1239_at_most_two_nonzero_coeffs_log_concave    {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj]    (h : ((Finset.range (Fintype.card V + 1)).filter (fun k => petrial_coeff G k ≠ 0)).card ≤ 2) :    petrial_log_concave G := by  intro k hi hj  obtain ⟨i, hik, hic⟩ := hi  obtain ⟨j, hkj, hjc⟩ := hj  obtain ⟨Fi, hFi⟩ := Finset.card_ne_zero.mp hic  simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hFi  obtain ⟨Fj, hFj⟩ := Finset.card_ne_zero.mp hjc  simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hFj  have hFi_rank : (petrial_matrix G Fi).rank ≤ k := by rw [hFi]; omega  have hFj_rank : k ≤ (petrial_matrix G Fj).rank := by rw [hFj]; omega  obtain ⟨Fk, hFk⟩ := op_1239_at_most_two_nonzero_coeffs_log_concave_exists_intermediate_rank    G ((Fi \ Fj).card + (Fj \ Fi).card) Fi Fj rfl k hFi_rank hFj_rank  have hkc : petrial_coeff G k ≠ 0 := by    unfold petrial_coeff    intro h0    have hmem : Fk ∈ (Finset.univ : Finset (Finset V)).filter (fun F' => (petrial_matrix G F').rank = k) := by      simp [hFk]    have : (Finset.univ.filter (fun F' => (petrial_matrix G F').rank = k)).card ≠ 0 :=      Finset.card_ne_zero.mpr ⟨Fk, hmem⟩    exact this h0  have hi_le : i ≤ Fintype.card V := by    have := Matrix.rank_le_card_width (petrial_matrix G Fi)    omega  have hj_le : j ≤ Fintype.card V := by    have := Matrix.rank_le_card_width (petrial_matrix G Fj)    omega  let S := (Finset.range (Fintype.card V + 1)).filter (fun m => petrial_coeff G m ≠ 0)  have hi_in : i ∈ S := by    simp only [Finset.mem_filter, Finset.mem_range, S]    exact ⟨by omega, hic⟩  have hj_in : j ∈ S := by    simp only [Finset.mem_filter, Finset.mem_range, S]    exact ⟨by omega, hjc⟩  have hk_in : k ∈ S := by    simp only [Finset.mem_filter, Finset.mem_range, S]    exact ⟨by omega, hkc⟩  have h_sub : {i, k, j} ⊆ S := by    intro x hx    simp only [Finset.mem_insert, Finset.mem_singleton] at hx    rcases hx with rfl | rfl | rfl    · exact hi_in    · exact hk_in    · exact hj_in  have h_card_three : ({i, k, j} : Finset ℕ).card = 3 := by    rw [Finset.card_insert_of_notMem, Finset.card_insert_of_notMem, Finset.card_singleton]    · simp only [Finset.mem_singleton]      omega    · simp only [Finset.mem_insert, Finset.mem_singleton]      rintro (rfl | rfl) <;> omega  have h_le := Finset.card_le_card h_sub  rw [h_card_three] at h_le  change S.card ≤ 2 at h  exfalso  omega
See it in the graphDiscuss this resultChallenge it