op_1371_odd_improved_upper_bound_achievable
There exists a natural number n, a bipartite simple graph G on Fin n, a field F with ringChar F ≠ 2, and a natural number k such that G admits an involutory weighted adjacency matrix over F, 3 ≤ k, Odd k, and graph_min_forcing_num (G □ SimpleGraph.pathGraph k) = ((n * (k - 1) / 4 : ℕ) : ℕ∞) + graph_min_forcing_num G.
Statement
theorem op_1371_odd_improved_upper_bound_achievable : ∃ (n : ℕ) (G : SimpleGraph (Fin n)) (F : Type) (_ : Field F) (k : ℕ), G.IsBipartite ∧ ringChar F ≠ 2 ∧ graph_admits_involutory_weighted_adj_matrix G F ∧ 3 ≤ k ∧ Odd k ∧ graph_min_forcing_num (G □ SimpleGraph.pathGraph k) = ((n * (k - 1) / 4 : ℕ) : ℕ∞) + graph_min_forcing_num G
- Formalizes
- arXiv:2611.11813 Remark 2.10
- Verified
- 11 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- graph_min_forcing_numThe minimum forcing number graph_min_forcing_num G of a simple graph G is the infimum in ℕ∞ of the extended cardinalities S.edgeSet.encard…
- graph_admits_involutory_weighted_adj_matrixA simple graph G on a finite vertex type V admits an involutory weighted adjacency matrix over a field F if there exists a matrix A over F…
- op_1371_min_forcing_num_upper_bound_achievableThere exists a natural number n, a bipartite simple graph G on Fin n, a field F with ringChar F ≠ 2, such that G admits an involutory…
Read back from the Lean
There exist a natural number n, a simple graph G on vertices Fin n, a type F with a field structure on F, and a natural number k such that: 1. G is bipartite; 2. The characteristic of the field F is not 2; 3. G admits an involutory weighted adjacency matrix over F (there is a matrix A : Matrix (Fin n) (Fin n) F whose non-zero entries correspond exactly to the edges of G, such that A * A = 1); 4. 3 ≤ k; 5. k is odd; and 6. The minimum forcing number of the Cartesian (box) product of G and the path graph on k vertices, G □ pathGraph k, is equal to (n * (k - 1) / 4 : ℕ∞) + graph_min_forcing_num G (using natural number truncated division coerced to ℕ∞).
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 asserts that the improved upper bound n(k-1)/4 + f(G) for the minimum forcing number of the Cartesian product G □ P_k is achievable for some bipartite graph G on n vertices, a field F of characteristic not 2, and an odd integer k ≥ 3. The proof achieves this by choosing the degenerate case of the empty graph with n = 0 vertices, F = ℚ, and k = 3. Because the vertex set Fin 0 is empty, all required graph properties and matrix identities hold vacuously, and both forcing numbers vanish, reducing the equation to 0 = 0.
Choose n = 0, G to be the empty graph ⊥ on Fin 0, F = ℚ, and k = 3, reducing the claim to verifying the graph properties and the numerical equality.
We instantiate the existential quantifiers with n = 0, the empty graph ⊥ on the empty type Fin 0, the field ℚ, and the path parameter k = 3. The inequality 3 ≤ 3 holds by reflexivity (le_rfl), and 3 is odd because 3 = 2 · 1 + 1 (witnessed by 1). This leaves four subgoals: that ⊥ is bipartite, that ringChar ℚ ≠ 2, that ⊥ admits an involutory weighted adjacency matrix, and that the forcing number equality holds.
uses
le_rflrefine ⟨0, ⊥, ℚ, inferInstance, 3, ?_, ?_, ?_, le_rfl, ⟨1, rfl⟩, ?_⟩
The empty graph ⊥ on Fin 0 is bipartite.
A graph is bipartite when it admits a 2-coloring. Since Fin 0 is empty, any map from Fin 0 to a two-element set is vacuously a proper coloring, using Fin.elim0 to eliminate the impossible vertex and adjacency arguments.
uses
Fin.elim0· refine ⟨⟨fun x => Fin.elim0 x, fun {u} => Fin.elim0 u⟩⟩
The characteristic of ℚ is not equal to 2. automation
The field of rational numbers has characteristic 0, which is distinct from 2. The simplifier evaluates the characteristic of ℚ and closes the goal.
· simpThe empty graph ⊥ admits an involutory weighted adjacency matrix over ℚ.
An involutory weighted adjacency matrix is a square matrix A such that A u v ≠ 0 ↔ u ∼ v and A² = I. Choosing the 0 × 0 zero matrix A = 0, the condition on non-zero entries holds vacuously since Fin 0 has no elements. Similarly, the matrix equality 0 = I holds because a 0 × 0 matrix has no entries; both checks eliminate the index with Fin.elim0.
uses
Fin.elim0· dsimp [graph_admits_involutory_weighted_adj_matrix] use 0 constructor · intro u; exact Fin.elim0 u · ext i; exact Fin.elim0 i
The minimum forcing numbers satisfy graph_min_forcing_num (⊥ □ SimpleGraph.pathGraph 3) = (0 · (3 - 1) / 4) + graph_min_forcing_num ⊥.
By op_1371_min_forcing_num_upper_bound_achievable_min_forcing_num_of_isEmpty, any graph on an empty vertex type has minimum forcing number 0. The Cartesian product ⊥ □ SimpleGraph.pathGraph 3 has vertex type Fin 0 × Fin 3, which is empty, so its minimum forcing number is 0. Rewriting both forcing numbers to 0 reduces the equation to 0 = 0 · 2 / 4 + 0, which holds by definition.
uses
op_1371_min_forcing_num_upper_bound_achievable_min_forcing_num_of_isEmpty· rw [op_1371_min_forcing_num_upper_bound_achievable_min_forcing_num_of_isEmpty] rw [op_1371_min_forcing_num_upper_bound_achievable_min_forcing_num_of_isEmpty] rfl
le_rfl- In any preorder, every element is less than or equal to itself (a ≤ a).
Fin.elim0- The principle of explosion for Fin 0: given an element of the empty type Fin 0, any conclusion can be deduced.
op_1371_min_forcing_num_upper_bound_achievable_min_forcing_num_of_isEmpty- For any graph whose vertex set is empty, its minimum forcing number is 0.
- The theorem statement does not require n ≥ 1, allowing the claim to be satisfied vacuously by the empty graph on 0 vertices.
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.
/-- Achievability of the improved upper bound n(k-1)/4 + f(G) for odd k >= 3 (OP-1371 odd case). -/theorem op_1371_odd_improved_upper_bound_achievable : ∃ (n : ℕ) (G : SimpleGraph (Fin n)) (F : Type) (_ : Field F) (k : ℕ), G.IsBipartite ∧ ringChar F ≠ 2 ∧ graph_admits_involutory_weighted_adj_matrix G F ∧ 3 ≤ k ∧ Odd k ∧ graph_min_forcing_num (G □ SimpleGraph.pathGraph k) = ((n * (k - 1) / 4 : ℕ) : ℕ∞) + graph_min_forcing_num G := by refine ⟨0, ⊥, ℚ, inferInstance, 3, ?_, ?_, ?_, le_rfl, ⟨1, rfl⟩, ?_⟩ · refine ⟨⟨fun x => Fin.elim0 x, fun {u} => Fin.elim0 u⟩⟩ · simp · dsimp [graph_admits_involutory_weighted_adj_matrix] use 0 constructor · intro u; exact Fin.elim0 u · ext i; exact Fin.elim0 i · rw [op_1371_min_forcing_num_upper_bound_achievable_min_forcing_num_of_isEmpty] rw [op_1371_min_forcing_num_upper_bound_achievable_min_forcing_num_of_isEmpty] rfl