op_1239_path_graph_petrial_log_concave
For every n : ℕ, the path graph pathGraph n has a log-concave partial Petrial polynomial (petrial_log_concave (SimpleGraph.pathGraph n)).
Statement
theorem op_1239_path_graph_petrial_log_concave (n : ℕ) :
petrial_log_concave (SimpleGraph.pathGraph n)- Formalizes
- arXiv:2611.07503, Section 6
- Verified
- 07 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- 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…
- inst_decidableRel_pathGraphAdjacency in the path graph
pathGraph nis decidable. - 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
For every natural number $n$, the path graph on $n$ vertices SimpleGraph.pathGraph n has a log-concave petrial rank distribution (petrial_log_concave). That is, for every $k \in \mathbb{N}$, if there exists $i < k$ such that petrial_coeff (SimpleGraph.pathGraph n) i ≠ 0 and there exists $j > k$ such that petrial_coeff (SimpleGraph.pathGraph n) j ≠ 0, then petrial_coeff (SimpleGraph.pathGraph n) (k - 1) * petrial_coeff (SimpleGraph.pathGraph n) (k + 1) ≤ petrial_coeff (SimpleGraph.pathGraph n) 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 theorem states that path graphs have log-concave partial Petrial polynomials. This is shown by proving that the rank of the Petrial matrix for any subset of vertices is always either n - 1 or n, so non-zero Petrial coefficients only occur at indices n - 1 and n. Consequently, the condition for log-concavity holds vacuously because there can never exist two non-zero coefficients strictly on opposite sides of any index k.
helper 1
recurrence relation
private lemma op_1239_path_graph_petrial_log_concave_rec_i {n : ℕ} (F : Finset (Fin n)) (z : Fin n → ZMod 2) (hz : ∀ i, (petrial_matrix (SimpleGraph.pathGraph n) F).mulVec z i = 0) (i : Fin n) (hi : i.val + 1 < n) : z ⟨i.val + 1, hi⟩ + (if h : i.val = 0 then 0 else z ⟨i.val - 1, by omega⟩) + (if i ∈ F then (1:ZMod 2) else 0) * z i = 0 := by classical have hmain := hz i rw [petrial_matrix, Matrix.add_mulVec, Pi.add_apply] at hmain rw [SimpleGraph.adjMatrix_mulVec_apply, Matrix.mulVec_diagonal] at hmain have hsum : ∑ u ∈ (SimpleGraph.pathGraph n).neighborFinset i, z u = z ⟨i.val + 1, hi⟩ + (if h : i.val = 0 then 0 else z ⟨i.val - 1, by omega⟩) := by have hset : (SimpleGraph.pathGraph n).neighborFinset i = ({⟨i.val + 1, hi⟩} : Finset (Fin n)) ∪ (if h : i.val = 0 then ∅ else {⟨i.val - 1, by omega⟩}) := by ext u rw [SimpleGraph.mem_neighborFinset, SimpleGraph.pathGraph_adj] simp only [Finset.mem_union, Finset.mem_singleton] constructor · rintro (h | h) · left; apply Fin.ext; simp only [Fin.val_mk]; omega · right have hiz : ¬ (i.val = 0) := by omega simp only [dif_neg hiz, Finset.mem_singleton] apply Fin.ext; simp only [Fin.val_mk]; omega · rintro (h | h) · left; rw [h] · split_ifs at h with h0 · simp at h · right rw [Finset.mem_singleton] at h rw [h]; simp only [Fin.val_mk]; omega rw [hset, Finset.sum_union] · rw [Finset.sum_singleton] split_ifs with h0 · simp · rw [Finset.sum_singleton] · refine Finset.disjoint_left.mpr ?_ intro a ha ha' simp only [Finset.mem_singleton] at ha subst ha split_ifs at ha' with h0 · simp at ha' · simp only [Finset.mem_singleton, Fin.ext_iff] at ha' omega rw [← hsum] exact hmain
helper 2
kernel is zero
private lemma op_1239_path_graph_petrial_log_concave_kernel_zero {n : ℕ} (F : Finset (Fin n)) (z : Fin n → ZMod 2) (hz : ∀ i, (petrial_matrix (SimpleGraph.pathGraph n) F).mulVec z i = 0) (hn : 0 < n) (hz0 : z ⟨0, hn⟩ = 0) : z = 0 := by classical funext j have key : ∀ (k : ℕ) (hk : k < n), z ⟨k, hk⟩ = 0 := by intro k refine Nat.strong_induction_on k (fun k ih => ?_) intro hk rcases Nat.eq_zero_or_pos k with hk0 | hkpos · subst hk0 exact hz0 · obtain ⟨k', rfl⟩ := Nat.exists_eq_succ_of_ne_zero (by omega : k ≠ 0) have hk' : k' < n := by omega have hi : k' + 1 < n := hk have hrec := op_1239_path_graph_petrial_log_concave_rec_i F z hz ⟨k', hk'⟩ hi have hz1 : z ⟨k', hk'⟩ = 0 := ih k' (by omega) hk' have hz2 : (if h : k' = 0 then (0:ZMod 2) else z ⟨k' - 1, by omega⟩) = 0 := by split_ifs with h0 · rfl · exact ih (k' - 1) (by omega) (by omega) have hz3 : z ⟨k' + 1, hi⟩ = z ⟨k' + 1, hk⟩ := by congr 1 rw [hz2, hz1, mul_zero, add_zero, add_zero] at hrec rw [← hz3] exact hrec exact key j.val j.isLt
helper 3
kernel finrank
private lemma op_1239_path_graph_petrial_log_concave_kernel_finrank {n : ℕ} (F : Finset (Fin n)) (hn : 0 < n) : Module.finrank (ZMod 2) (petrial_matrix (SimpleGraph.pathGraph n) F).mulVecLin.ker ≤ 1 := by classical let M := petrial_matrix (SimpleGraph.pathGraph n) F change Module.finrank (ZMod 2) M.mulVecLin.ker ≤ 1 let e : (Fin n → ZMod 2) →ₗ[ZMod 2] ZMod 2 := LinearMap.proj (φ := fun _ : Fin n => ZMod 2) ⟨0, hn⟩ let φ : M.mulVecLin.ker →ₗ[ZMod 2] ZMod 2 := e.comp (Submodule.subtype M.mulVecLin.ker) have hinj : Function.Injective φ := by intro x y hxy have hxy' : x.val ⟨0, hn⟩ = y.val ⟨0, hn⟩ := hxy apply Subtype.ext have hmem0 : M.mulVec (x.val - y.val) = 0 := by have h1 := (LinearMap.mem_ker).mp (x - y).2 have h2 : M.mulVecLin ((x : Fin n → ZMod 2) - (y : Fin n → ZMod 2)) = 0 := by rwa [Submodule.coe_sub] at h1 simpa only [Matrix.mulVecLin_apply] using h2 have hz0 : (x.val - y.val) ⟨0, hn⟩ = 0 := by rw [Pi.sub_apply, hxy', sub_self] have hfinal := op_1239_path_graph_petrial_log_concave_kernel_zero F (x.val - y.val) (fun i => by rw [hmem0]; rfl) hn hz0 exact sub_eq_zero.mp hfinal have hle := LinearMap.finrank_le_finrank_of_injective (f := φ) hinj rwa [Module.finrank_self] at hle
helper 4
rank ge
private lemma op_1239_path_graph_petrial_log_concave_rank_ge (n : ℕ) (F : Finset (Fin n)) : n - 1 ≤ (petrial_matrix (SimpleGraph.pathGraph n) F).rank := by rcases Nat.eq_zero_or_pos n with h | h · subst h; simp · set M := petrial_matrix (SimpleGraph.pathGraph n) F have hker : Module.finrank (ZMod 2) M.mulVecLin.ker ≤ 1 := op_1239_path_graph_petrial_log_concave_kernel_finrank F h have hM := LinearMap.finrank_range_add_finrank_ker M.mulVecLin have hfin : Module.finrank (ZMod 2) (Fin n → ZMod 2) = n := by rw [Module.finrank_fintype_fun_eq_card, Fintype.card_fin] rw [hfin] at hM have hrank : M.rank = Module.finrank (ZMod 2) M.mulVecLin.range := rfl have hgoal : n - 1 ≤ Module.finrank (ZMod 2) M.mulVecLin.range := by omega rwa [hrank]
helper 5
rank le
private lemma op_1239_path_graph_petrial_log_concave_rank_le (n : ℕ) (F : Finset (Fin n)) : (petrial_matrix (SimpleGraph.pathGraph n) F).rank ≤ n := by have h := Matrix.rank_le_card_height (petrial_matrix (SimpleGraph.pathGraph n) F) simpa using h
main theorem
main theorem
theorem op_1239_path_graph_petrial_log_concave (n : ℕ) : petrial_log_concave (SimpleGraph.pathGraph n) := by intro k hi hj obtain ⟨i, hik, hic⟩ := hi obtain ⟨j, hkj, hjc⟩ := hj have hni : n - 1 ≤ i := by obtain ⟨F, hF⟩ := Finset.card_ne_zero.mp hic simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hF rw [← hF] exact op_1239_path_graph_petrial_log_concave_rank_ge n F have hnj : j ≤ n := by obtain ⟨F, hF⟩ := Finset.card_ne_zero.mp hjc simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hF rw [← hF] exact op_1239_path_graph_petrial_log_concave_rank_le n F exfalso omega
- Unresolved check: step 6's explanation only repeats its claim: say how it is shown
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.
set_option linter.unusedSimpArgs false inprivate lemma op_1239_path_graph_petrial_log_concave_rec_i {n : ℕ} (F : Finset (Fin n)) (z : Fin n → ZMod 2) (hz : ∀ i, (petrial_matrix (SimpleGraph.pathGraph n) F).mulVec z i = 0) (i : Fin n) (hi : i.val + 1 < n) : z ⟨i.val + 1, hi⟩ + (if h : i.val = 0 then 0 else z ⟨i.val - 1, by omega⟩) + (if i ∈ F then (1:ZMod 2) else 0) * z i = 0 := by classical have hmain := hz i rw [petrial_matrix, Matrix.add_mulVec, Pi.add_apply] at hmain rw [SimpleGraph.adjMatrix_mulVec_apply, Matrix.mulVec_diagonal] at hmain have hsum : ∑ u ∈ (SimpleGraph.pathGraph n).neighborFinset i, z u = z ⟨i.val + 1, hi⟩ + (if h : i.val = 0 then 0 else z ⟨i.val - 1, by omega⟩) := by have hset : (SimpleGraph.pathGraph n).neighborFinset i = ({⟨i.val + 1, hi⟩} : Finset (Fin n)) ∪ (if h : i.val = 0 then ∅ else {⟨i.val - 1, by omega⟩}) := by ext u rw [SimpleGraph.mem_neighborFinset, SimpleGraph.pathGraph_adj] simp only [Finset.mem_union, Finset.mem_singleton] constructor · rintro (h | h) · left; apply Fin.ext; simp only [Fin.val_mk]; omega · right have hiz : ¬ (i.val = 0) := by omega simp only [dif_neg hiz, Finset.mem_singleton] apply Fin.ext; simp only [Fin.val_mk]; omega · rintro (h | h) · left; rw [h] · split_ifs at h with h0 · simp at h · right rw [Finset.mem_singleton] at h rw [h]; simp only [Fin.val_mk]; omega rw [hset, Finset.sum_union] · rw [Finset.sum_singleton] split_ifs with h0 · simp · rw [Finset.sum_singleton] · refine Finset.disjoint_left.mpr ?_ intro a ha ha' simp only [Finset.mem_singleton] at ha subst ha split_ifs at ha' with h0 · simp at ha' · simp only [Finset.mem_singleton, Fin.ext_iff] at ha' omega rw [← hsum] exact hmainset_option linter.unusedSimpArgs false inprivate lemma op_1239_path_graph_petrial_log_concave_kernel_zero {n : ℕ} (F : Finset (Fin n)) (z : Fin n → ZMod 2) (hz : ∀ i, (petrial_matrix (SimpleGraph.pathGraph n) F).mulVec z i = 0) (hn : 0 < n) (hz0 : z ⟨0, hn⟩ = 0) : z = 0 := by classical funext j have key : ∀ (k : ℕ) (hk : k < n), z ⟨k, hk⟩ = 0 := by intro k refine Nat.strong_induction_on k (fun k ih => ?_) intro hk rcases Nat.eq_zero_or_pos k with hk0 | hkpos · subst hk0 exact hz0 · obtain ⟨k', rfl⟩ := Nat.exists_eq_succ_of_ne_zero (by omega : k ≠ 0) have hk' : k' < n := by omega have hi : k' + 1 < n := hk have hrec := op_1239_path_graph_petrial_log_concave_rec_i F z hz ⟨k', hk'⟩ hi have hz1 : z ⟨k', hk'⟩ = 0 := ih k' (by omega) hk' have hz2 : (if h : k' = 0 then (0:ZMod 2) else z ⟨k' - 1, by omega⟩) = 0 := by split_ifs with h0 · rfl · exact ih (k' - 1) (by omega) (by omega) have hz3 : z ⟨k' + 1, hi⟩ = z ⟨k' + 1, hk⟩ := by congr 1 rw [hz2, hz1, mul_zero, add_zero, add_zero] at hrec rw [← hz3] exact hrec exact key j.val j.isLtset_option linter.unusedSimpArgs false inprivate lemma op_1239_path_graph_petrial_log_concave_kernel_finrank {n : ℕ} (F : Finset (Fin n)) (hn : 0 < n) : Module.finrank (ZMod 2) (petrial_matrix (SimpleGraph.pathGraph n) F).mulVecLin.ker ≤ 1 := by classical let M := petrial_matrix (SimpleGraph.pathGraph n) F change Module.finrank (ZMod 2) M.mulVecLin.ker ≤ 1 let e : (Fin n → ZMod 2) →ₗ[ZMod 2] ZMod 2 := LinearMap.proj (φ := fun _ : Fin n => ZMod 2) ⟨0, hn⟩ let φ : M.mulVecLin.ker →ₗ[ZMod 2] ZMod 2 := e.comp (Submodule.subtype M.mulVecLin.ker) have hinj : Function.Injective φ := by intro x y hxy have hxy' : x.val ⟨0, hn⟩ = y.val ⟨0, hn⟩ := hxy apply Subtype.ext have hmem0 : M.mulVec (x.val - y.val) = 0 := by have h1 := (LinearMap.mem_ker).mp (x - y).2 have h2 : M.mulVecLin ((x : Fin n → ZMod 2) - (y : Fin n → ZMod 2)) = 0 := by rwa [Submodule.coe_sub] at h1 simpa only [Matrix.mulVecLin_apply] using h2 have hz0 : (x.val - y.val) ⟨0, hn⟩ = 0 := by rw [Pi.sub_apply, hxy', sub_self] have hfinal := op_1239_path_graph_petrial_log_concave_kernel_zero F (x.val - y.val) (fun i => by rw [hmem0]; rfl) hn hz0 exact sub_eq_zero.mp hfinal have hle := LinearMap.finrank_le_finrank_of_injective (f := φ) hinj rwa [Module.finrank_self] at hleset_option linter.unusedSimpArgs false inprivate lemma op_1239_path_graph_petrial_log_concave_rank_ge (n : ℕ) (F : Finset (Fin n)) : n - 1 ≤ (petrial_matrix (SimpleGraph.pathGraph n) F).rank := by rcases Nat.eq_zero_or_pos n with h | h · subst h; simp · set M := petrial_matrix (SimpleGraph.pathGraph n) F have hker : Module.finrank (ZMod 2) M.mulVecLin.ker ≤ 1 := op_1239_path_graph_petrial_log_concave_kernel_finrank F h have hM := LinearMap.finrank_range_add_finrank_ker M.mulVecLin have hfin : Module.finrank (ZMod 2) (Fin n → ZMod 2) = n := by rw [Module.finrank_fintype_fun_eq_card, Fintype.card_fin] rw [hfin] at hM have hrank : M.rank = Module.finrank (ZMod 2) M.mulVecLin.range := rfl have hgoal : n - 1 ≤ Module.finrank (ZMod 2) M.mulVecLin.range := by omega rwa [hrank]private lemma op_1239_path_graph_petrial_log_concave_rank_le (n : ℕ) (F : Finset (Fin n)) : (petrial_matrix (SimpleGraph.pathGraph n) F).rank ≤ n := by have h := Matrix.rank_le_card_height (petrial_matrix (SimpleGraph.pathGraph n) F) simpa using h/-- Path graphs have log-concave partial Petrial polynomials. -/theorem op_1239_path_graph_petrial_log_concave (n : ℕ) : petrial_log_concave (SimpleGraph.pathGraph n) := by intro k hi hj obtain ⟨i, hik, hic⟩ := hi obtain ⟨j, hkj, hjc⟩ := hj have hni : n - 1 ≤ i := by obtain ⟨F, hF⟩ := Finset.card_ne_zero.mp hic simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hF rw [← hF] exact op_1239_path_graph_petrial_log_concave_rank_ge n F have hnj : j ≤ n := by obtain ⟨F, hF⟩ := Finset.card_ne_zero.mp hjc simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hF rw [← hF] exact op_1239_path_graph_petrial_log_concave_rank_le n F exfalso omega