AFTD Auto-Formalizing Theoretical Domains

op_1371_odd_improved_upper_bound_achievable

theoremverifiedformalization

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

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.

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

    line 8

    uses le_rfl

      refine ⟨0, ⊥, ℚ, inferInstance, 3, ?_, ?_, ?_, le_rfl, ⟨1, rfl⟩, ?_⟩
  2. 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.

    line 9

    uses Fin.elim0

      · refine ⟨⟨fun x => Fin.elim0 x, fun {u} => Fin.elim0 u⟩⟩
  3. 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.

    line 10

      · simp
  4. The 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.

    lines 11–15

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

    lines 16–18

    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.

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

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