AFTD Auto-Formalizing Theoretical Domains

fano_free_local_forbidden

theoremverifiedformalization

In any 3-uniform Fano-free hypergraph H : Finset (Finset V), if {x, y, z} is an edge of H, then for all vertices a, b, c, d in V, the six triples {x, a, b}, {x, c, d}, {y, a, c}, {y, b, d}, {z, a, d}, and {z, b, c} cannot all belong to H.

Statement

theorem fano_free_local_forbidden {V : Type*} [DecidableEq V]
    (H : Finset (Finset V)) (hunif : is_three_uniform H) (hfree : is_fano_free H)
    (x y z a b c d : V) (hxyz : {x, y, z} ∈ H) :
    ¬ ({x, a, b} ∈ H ∧ {x, c, d} ∈ H ∧ {y, a, c} ∈ H ∧ {y, b, d} ∈ H ∧ {z, a, d} ∈ H ∧ {z, b, c} ∈ H)
Formalizes
arXiv:2610.01084 Lemma 3.1 inequality (3.1)
Verified
04 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
  • is_three_uniformA hypergraph F (a finite family of finite sets of vertices) is 3-uniform if every hyperedge e in F has cardinality 3.
  • is_fano_freeA hypergraph H (a Finset of finite subsets of V) is Fano-free if there does not exist an embedding f : Fin 7 ↪ V such that for every…
  • fano_planeThe Fano plane PG(2,2) is the 3-uniform hypergraph on Fin 7 whose hyperedges are the seven triples {0, 1, 2}, {0, 3, 4}, {0, 5, 6}, {1, 3,…

Read back from the Lean

Let V be a type with decidable equality. Let H be a finite family of finite subsets of V (Finset (Finset V)). Assume H is 3-uniform (is_three_uniform H) and Fano-free (is_fano_free H). For any vertices x, y, z, a, b, c, d : V, if {x, y, z} ∈ H, then it is not the case that all six of {x, a, b}, {x, c, d}, {y, a, c}, {y, b, d}, {z, a, d}, and {z, b, c} are also elements of H.

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 is proved by contradiction: we assume that an edge {x, y, z} and all six companion triples belong to the 3-uniform hypergraph H. By 3-uniformity, every such edge contains 3 distinct vertices, which implies that all 21 pairs formed by the seven vertices x, y, z, a, b, c, d are distinct. This pairwise distinctness ensures that the map sending the standard vertices 0, ..., 6 of the Fano plane to x, y, z, a, b, c, d is an injective embedding. Finally, we verify that the image of each of the seven lines of the Fano plane under this embedding is one of the assumed edges of H, which directly contradicts the assumption that H is Fano-free.

  1. If {p, q, r} has cardinality 3, then p, q, and r are pairwise distinct.

    We prove each of the inequalities p ≠ q, p ≠ r, and q ≠ r by contradiction. If any two vertices coincide, the set collapses to at most two elements, which has cardinality at most 2 by Finset.card_le_two. Since the cardinality is assumed to be 3, omega derives a contradiction in each case.

    lines 1–18

    uses Finset.card_le_two

    private lemma fano_free_local_forbidden_card_three {V : Type*} [DecidableEq V] {p q r : V}
        (h : ({p,q,r} : Finset V).card = 3) : p ≠ q ∧ p ≠ r ∧ q ≠ r := by
      refine ⟨?_, ?_, ?_⟩
      · intro heq
        have he : ({p,q,r} : Finset V) = {p,r} := by rw [heq]; simp
        have h1 : ({p,r} : Finset V).card = 3 := he ▸ h
        have h2 : ({p,r} : Finset V).card ≤ 2 := Finset.card_le_two
        omega
      · intro heq
        have he : ({p,q,r} : Finset V) = {q,r} := by rw [heq]; simp
        have h1 : ({q,r} : Finset V).card = 3 := he ▸ h
        have h2 : ({q,r} : Finset V).card ≤ 2 := Finset.card_le_two
        omega
      · intro heq
        have he : ({p,q,r} : Finset V) = {p,q} := by rw [heq]; simp
        have h1 : ({p,q} : Finset V).card = 3 := he ▸ h
        have h2 : ({p,q} : Finset V).card ≤ 2 := Finset.card_le_two
        omega
  2. The map from Fin 7 to V sending 0 through 6 to x, y, z, a, b, c, d is injective when all 21 pairs among them are distinct.

    Given indices i, j in Fin 7 with equal images, we perform exhaustive case analysis over all 49 pairs using fin_cases. When i = j, the indices are equal; when i ≠ j, the assumed equality of their images contradicts one of the 21 pairwise inequality hypotheses, which simp_all detects and closes using Fin.ext_iff.

    lines 20–33

    uses Fin.ext_iff

    private lemma fano_free_local_forbidden_injective {V : Type*} [DecidableEq V]
        (x y z a b c d : V)
        (hxy : x ≠ y) (hxz : x ≠ z) (hyz : y ≠ z)
        (hxa : x ≠ a) (hxb : x ≠ b) (hab : a ≠ b)
        (hxc : x ≠ c) (hxd : x ≠ d) (hcd : c ≠ d)
        (hya : y ≠ a) (hyc : y ≠ c) (hac : a ≠ c)
        (hyb : y ≠ b) (hyd : y ≠ d) (hbd : b ≠ d)
        (hza : z ≠ a) (hzd : z ≠ d) (had : a ≠ d)
        (hzb : z ≠ b) (hzc : z ≠ c) (hbc : b ≠ c) :
        Function.Injective (![x, y, z, a, b, c, d] : Fin 7 → V) := by
      intro i j hij
      fin_cases i <;> fin_cases j <;>
        simp_all [Fin.ext_iff]
    
  3. Each of the seven lines of the Fano plane maps under the 7-tuple embedding to the corresponding triple in V.

    For each of the seven blocks {0, 1, 2}, {0, 3, 4}, {0, 5, 6}, {1, 3, 5}, {1, 4, 6}, {2, 3, 6}, and {2, 4, 5}, we rewrite the finset map as an image using Finset.map_eq_image and evaluate the image definitionally using Finset.image.

    lines 34–68

    uses Finset.map_eq_image, Finset.image

    private lemma fano_free_local_forbidden_map_012 {V : Type*} [DecidableEq V] (x y z a b c d : V)
        (h : Function.Injective (![x,y,z,a,b,c,d] : Fin 7 → V)) :
        Finset.map ⟨![x,y,z,a,b,c,d], h⟩ ({0,1,2} : Finset (Fin 7)) = ({x,y,z} : Finset V) := by
      rw [Finset.map_eq_image]; simp [Finset.image]
    
    private lemma fano_free_local_forbidden_map_034 {V : Type*} [DecidableEq V] (x y z a b c d : V)
        (h : Function.Injective (![x,y,z,a,b,c,d] : Fin 7 → V)) :
        Finset.map ⟨![x,y,z,a,b,c,d], h⟩ ({0,3,4} : Finset (Fin 7)) = ({x,a,b} : Finset V) := by
      rw [Finset.map_eq_image]; simp [Finset.image]
    
    private lemma fano_free_local_forbidden_map_056 {V : Type*} [DecidableEq V] (x y z a b c d : V)
        (h : Function.Injective (![x,y,z,a,b,c,d] : Fin 7 → V)) :
        Finset.map ⟨![x,y,z,a,b,c,d], h⟩ ({0,5,6} : Finset (Fin 7)) = ({x,c,d} : Finset V) := by
      rw [Finset.map_eq_image]; simp [Finset.image]
    
    private lemma fano_free_local_forbidden_map_135 {V : Type*} [DecidableEq V] (x y z a b c d : V)
        (h : Function.Injective (![x,y,z,a,b,c,d] : Fin 7 → V)) :
        Finset.map ⟨![x,y,z,a,b,c,d], h⟩ ({1,3,5} : Finset (Fin 7)) = ({y,a,c} : Finset V) := by
      rw [Finset.map_eq_image]; simp [Finset.image]
    
    private lemma fano_free_local_forbidden_map_146 {V : Type*} [DecidableEq V] (x y z a b c d : V)
        (h : Function.Injective (![x,y,z,a,b,c,d] : Fin 7 → V)) :
        Finset.map ⟨![x,y,z,a,b,c,d], h⟩ ({1,4,6} : Finset (Fin 7)) = ({y,b,d} : Finset V) := by
      rw [Finset.map_eq_image]; simp [Finset.image]
    
    private lemma fano_free_local_forbidden_map_236 {V : Type*} [DecidableEq V] (x y z a b c d : V)
        (h : Function.Injective (![x,y,z,a,b,c,d] : Fin 7 → V)) :
        Finset.map ⟨![x,y,z,a,b,c,d], h⟩ ({2,3,6} : Finset (Fin 7)) = ({z,a,d} : Finset V) := by
      rw [Finset.map_eq_image]; simp [Finset.image]
    
    private lemma fano_free_local_forbidden_map_245 {V : Type*} [DecidableEq V] (x y z a b c d : V)
        (h : Function.Injective (![x,y,z,a,b,c,d] : Fin 7 → V)) :
        Finset.map ⟨![x,y,z,a,b,c,d], h⟩ ({2,4,5} : Finset (Fin 7)) = ({z,b,c} : Finset V) := by
      rw [Finset.map_eq_image]; simp [Finset.image]
    
  4. Assuming the six companion triples belong to H, all 21 pairs formed by x, y, z, a, b, c, d are distinct.

    We assume for contradiction that all six companion triples belong to H alongside {x, y, z}. By 3-uniformity (hunif), every edge in H has cardinality 3. Applying fano_free_local_forbidden_card_three to each of the seven edges yields that the three vertices of each edge are distinct, producing all 21 pairwise inequalities among x, y, z, a, b, c, d.

    lines 70–81

    uses fano_free_local_forbidden_card_three

    theorem fano_free_local_forbidden {V : Type*} [DecidableEq V]
        (H : Finset (Finset V)) (hunif : is_three_uniform H) (hfree : is_fano_free H)
        (x y z a b c d : V) (hxyz : {x, y, z} ∈ H) :
        ¬ ({x, a, b} ∈ H ∧ {x, c, d} ∈ H ∧ {y, a, c} ∈ H ∧ {y, b, d} ∈ H ∧ {z, a, d} ∈ H ∧ {z, b, c} ∈ H) := by
      rintro ⟨hxab, hxcd, hyac, hybd, hzad, hzbc⟩
      obtain ⟨hxy, hxz, hyz⟩ := fano_free_local_forbidden_card_three (hunif {x,y,z} hxyz)
      obtain ⟨hxa, hxb, hab⟩ := fano_free_local_forbidden_card_three (hunif {x,a,b} hxab)
      obtain ⟨hxc, hxd, hcd⟩ := fano_free_local_forbidden_card_three (hunif {x,c,d} hxcd)
      obtain ⟨hya, hyc, hac⟩ := fano_free_local_forbidden_card_three (hunif {y,a,c} hyac)
      obtain ⟨hyb, hyd, hbd⟩ := fano_free_local_forbidden_card_three (hunif {y,b,d} hybd)
      obtain ⟨hza, hzd, had⟩ := fano_free_local_forbidden_card_three (hunif {z,a,d} hzad)
      obtain ⟨hzb, hzc, hbc⟩ := fano_free_local_forbidden_card_three (hunif {z,b,c} hzbc)
  5. To contradict Fano-freeness, it suffices to show that the embedding of Fin 7 defined by x, y, z, a, b, c, d maps every Fano line into H.

    We invoke the Fano-free hypothesis hfree, which asserts that H contains no embedded copy of the Fano plane. It therefore suffices to exhibit an injective map from Fin 7 to V whose image on each Fano line lies in H. By fano_free_local_forbidden_injective applied to the 21 pairwise inequalities, the map sending 0 through 6 to x, y, z, a, b, c, d is injective, providing the required embedding.

    lines 82–86

    uses fano_free_local_forbidden_injective

      apply hfree
      have hinj : Function.Injective (![x,y,z,a,b,c,d] : Fin 7 → V) :=
        fano_free_local_forbidden_injective x y z a b c d
          hxy hxz hyz hxa hxb hab hxc hxd hcd hya hyc hac hyb hyd hbd hza hzd had hzb hzc hbc
      refine ⟨⟨![x,y,z,a,b,c,d], hinj⟩, ?_⟩
  6. Every line of the Fano plane maps to an edge in H under the embedding, completing the contradiction.

    Let e be an edge of the Fano plane. We unfold fano_plane using Finset.mem_insert and Finset.mem_singleton, splitting into seven cases. In each case, we rewrite the mapped edge using the corresponding helper lemma (fano_free_local_forbidden_map_012, fano_free_local_forbidden_map_034, fano_free_local_forbidden_map_056, fano_free_local_forbidden_map_135, fano_free_local_forbidden_map_146, fano_free_local_forbidden_map_236, fano_free_local_forbidden_map_245) to identify it with one of the seven triples, all of which are assumed to belong to H.

    lines 87–96

    uses fano_plane, Finset.mem_insert, Finset.mem_singleton, fano_free_local_forbidden_map_012, fano_free_local_forbidden_map_034, fano_free_local_forbidden_map_056, fano_free_local_forbidden_map_135, fano_free_local_forbidden_map_146, fano_free_local_forbidden_map_236, fano_free_local_forbidden_map_245

      intro e he
      simp only [fano_plane, Finset.mem_insert, Finset.mem_singleton] at he
      rcases he with rfl | rfl | rfl | rfl | rfl | rfl | rfl
      · rw [fano_free_local_forbidden_map_012 x y z a b c d hinj]; exact hxyz
      · rw [fano_free_local_forbidden_map_034 x y z a b c d hinj]; exact hxab
      · rw [fano_free_local_forbidden_map_056 x y z a b c d hinj]; exact hxcd
      · rw [fano_free_local_forbidden_map_135 x y z a b c d hinj]; exact hyac
      · rw [fano_free_local_forbidden_map_146 x y z a b c d hinj]; exact hybd
      · rw [fano_free_local_forbidden_map_236 x y z a b c d hinj]; exact hzad
      · rw [fano_free_local_forbidden_map_245 x y z a b c d hinj]; exact hzbc
Finset.card_le_two
A set with at most two elements has cardinality at most 2.
Fin.ext_iff
Two elements of Fin n are equal if and only if their underlying natural numbers are equal.
Finset.map_eq_image
Mapping a finite set under an embedding is equal to taking the image under the underlying function.
Finset.image
The image of a finite set under a function.
fano_free_local_forbidden_card_three
If a three-element set has cardinality 3, then its elements are pairwise distinct.
fano_free_local_forbidden_injective
The map from Fin 7 to V sending 0 through 6 to x, y, z, a, b, c, d is injective when all 21 pairs of elements are distinct.
fano_plane
The standard Fano plane on Fin 7, defined as the set of seven 3-element blocks.
Finset.mem_insert
An element belongs to insert b s if and only if it equals b or belongs to s.
Finset.mem_singleton
An element belongs to the singleton {a} if and only if it equals a.
fano_free_local_forbidden_map_012
The image of {0, 1, 2} under the 7-tuple embedding is {x, y, z}.
fano_free_local_forbidden_map_034
The image of {0, 3, 4} under the 7-tuple embedding is {x, a, b}.
fano_free_local_forbidden_map_056
The image of {0, 5, 6} under the 7-tuple embedding is {x, c, d}.
fano_free_local_forbidden_map_135
The image of {1, 3, 5} under the 7-tuple embedding is {y, a, c}.
fano_free_local_forbidden_map_146
The image of {1, 4, 6} under the 7-tuple embedding is {y, b, d}.
fano_free_local_forbidden_map_236
The image of {2, 3, 6} under the 7-tuple embedding is {z, a, d}.
fano_free_local_forbidden_map_245
The image of {2, 4, 5} under the 7-tuple embedding is {z, b, c}.

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

private lemma fano_free_local_forbidden_card_three {V : Type*} [DecidableEq V] {p q r : V}    (h : ({p,q,r} : Finset V).card = 3) : p ≠ q ∧ p ≠ r ∧ q ≠ r := by  refine ⟨?_, ?_, ?_⟩  · intro heq    have he : ({p,q,r} : Finset V) = {p,r} := by rw [heq]; simp    have h1 : ({p,r} : Finset V).card = 3 := he ▸ h    have h2 : ({p,r} : Finset V).card ≤ 2 := Finset.card_le_two    omega  · intro heq    have he : ({p,q,r} : Finset V) = {q,r} := by rw [heq]; simp    have h1 : ({q,r} : Finset V).card = 3 := he ▸ h    have h2 : ({q,r} : Finset V).card ≤ 2 := Finset.card_le_two    omega  · intro heq    have he : ({p,q,r} : Finset V) = {p,q} := by rw [heq]; simp    have h1 : ({p,q} : Finset V).card = 3 := he ▸ h    have h2 : ({p,q} : Finset V).card ≤ 2 := Finset.card_le_two    omegaprivate lemma fano_free_local_forbidden_injective {V : Type*} [DecidableEq V]    (x y z a b c d : V)    (hxy : x ≠ y) (hxz : x ≠ z) (hyz : y ≠ z)    (hxa : x ≠ a) (hxb : x ≠ b) (hab : a ≠ b)    (hxc : x ≠ c) (hxd : x ≠ d) (hcd : c ≠ d)    (hya : y ≠ a) (hyc : y ≠ c) (hac : a ≠ c)    (hyb : y ≠ b) (hyd : y ≠ d) (hbd : b ≠ d)    (hza : z ≠ a) (hzd : z ≠ d) (had : a ≠ d)    (hzb : z ≠ b) (hzc : z ≠ c) (hbc : b ≠ c) :    Function.Injective (![x, y, z, a, b, c, d] : Fin 7 → V) := by  intro i j hij  fin_cases i <;> fin_cases j <;>    simp_all [Fin.ext_iff]private lemma fano_free_local_forbidden_map_012 {V : Type*} [DecidableEq V] (x y z a b c d : V)    (h : Function.Injective (![x,y,z,a,b,c,d] : Fin 7 → V)) :    Finset.map ⟨![x,y,z,a,b,c,d], h⟩ ({0,1,2} : Finset (Fin 7)) = ({x,y,z} : Finset V) := by  rw [Finset.map_eq_image]; simp [Finset.image]private lemma fano_free_local_forbidden_map_034 {V : Type*} [DecidableEq V] (x y z a b c d : V)    (h : Function.Injective (![x,y,z,a,b,c,d] : Fin 7 → V)) :    Finset.map ⟨![x,y,z,a,b,c,d], h⟩ ({0,3,4} : Finset (Fin 7)) = ({x,a,b} : Finset V) := by  rw [Finset.map_eq_image]; simp [Finset.image]private lemma fano_free_local_forbidden_map_056 {V : Type*} [DecidableEq V] (x y z a b c d : V)    (h : Function.Injective (![x,y,z,a,b,c,d] : Fin 7 → V)) :    Finset.map ⟨![x,y,z,a,b,c,d], h⟩ ({0,5,6} : Finset (Fin 7)) = ({x,c,d} : Finset V) := by  rw [Finset.map_eq_image]; simp [Finset.image]private lemma fano_free_local_forbidden_map_135 {V : Type*} [DecidableEq V] (x y z a b c d : V)    (h : Function.Injective (![x,y,z,a,b,c,d] : Fin 7 → V)) :    Finset.map ⟨![x,y,z,a,b,c,d], h⟩ ({1,3,5} : Finset (Fin 7)) = ({y,a,c} : Finset V) := by  rw [Finset.map_eq_image]; simp [Finset.image]private lemma fano_free_local_forbidden_map_146 {V : Type*} [DecidableEq V] (x y z a b c d : V)    (h : Function.Injective (![x,y,z,a,b,c,d] : Fin 7 → V)) :    Finset.map ⟨![x,y,z,a,b,c,d], h⟩ ({1,4,6} : Finset (Fin 7)) = ({y,b,d} : Finset V) := by  rw [Finset.map_eq_image]; simp [Finset.image]private lemma fano_free_local_forbidden_map_236 {V : Type*} [DecidableEq V] (x y z a b c d : V)    (h : Function.Injective (![x,y,z,a,b,c,d] : Fin 7 → V)) :    Finset.map ⟨![x,y,z,a,b,c,d], h⟩ ({2,3,6} : Finset (Fin 7)) = ({z,a,d} : Finset V) := by  rw [Finset.map_eq_image]; simp [Finset.image]private lemma fano_free_local_forbidden_map_245 {V : Type*} [DecidableEq V] (x y z a b c d : V)    (h : Function.Injective (![x,y,z,a,b,c,d] : Fin 7 → V)) :    Finset.map ⟨![x,y,z,a,b,c,d], h⟩ ({2,4,5} : Finset (Fin 7)) = ({z,b,c} : Finset V) := by  rw [Finset.map_eq_image]; simp [Finset.image]/-- Local forbidden constraint for Fano-free 3-graphs: no edge {x,y,z} can have six companion edges forming a Fano plane. -/theorem fano_free_local_forbidden {V : Type*} [DecidableEq V]    (H : Finset (Finset V)) (hunif : is_three_uniform H) (hfree : is_fano_free H)    (x y z a b c d : V) (hxyz : {x, y, z} ∈ H) :    ¬ ({x, a, b} ∈ H ∧ {x, c, d} ∈ H ∧ {y, a, c} ∈ H ∧ {y, b, d} ∈ H ∧ {z, a, d} ∈ H ∧ {z, b, c} ∈ H) := by  rintro ⟨hxab, hxcd, hyac, hybd, hzad, hzbc⟩  obtain ⟨hxy, hxz, hyz⟩ := fano_free_local_forbidden_card_three (hunif {x,y,z} hxyz)  obtain ⟨hxa, hxb, hab⟩ := fano_free_local_forbidden_card_three (hunif {x,a,b} hxab)  obtain ⟨hxc, hxd, hcd⟩ := fano_free_local_forbidden_card_three (hunif {x,c,d} hxcd)  obtain ⟨hya, hyc, hac⟩ := fano_free_local_forbidden_card_three (hunif {y,a,c} hyac)  obtain ⟨hyb, hyd, hbd⟩ := fano_free_local_forbidden_card_three (hunif {y,b,d} hybd)  obtain ⟨hza, hzd, had⟩ := fano_free_local_forbidden_card_three (hunif {z,a,d} hzad)  obtain ⟨hzb, hzc, hbc⟩ := fano_free_local_forbidden_card_three (hunif {z,b,c} hzbc)  apply hfree  have hinj : Function.Injective (![x,y,z,a,b,c,d] : Fin 7 → V) :=    fano_free_local_forbidden_injective x y z a b c d      hxy hxz hyz hxa hxb hab hxc hxd hcd hya hyc hac hyb hyd hbd hza hzd had hzb hzc hbc  refine ⟨⟨![x,y,z,a,b,c,d], hinj⟩, ?_⟩  intro e he  simp only [fano_plane, Finset.mem_insert, Finset.mem_singleton] at he  rcases he with rfl | rfl | rfl | rfl | rfl | rfl | rfl  · rw [fano_free_local_forbidden_map_012 x y z a b c d hinj]; exact hxyz  · rw [fano_free_local_forbidden_map_034 x y z a b c d hinj]; exact hxab  · rw [fano_free_local_forbidden_map_056 x y z a b c d hinj]; exact hxcd  · rw [fano_free_local_forbidden_map_135 x y z a b c d hinj]; exact hyac  · rw [fano_free_local_forbidden_map_146 x y z a b c d hinj]; exact hybd  · rw [fano_free_local_forbidden_map_236 x y z a b c d hinj]; exact hzad  · rw [fano_free_local_forbidden_map_245 x y z a b c d hinj]; exact hzbc
See it in the graphDiscuss this resultChallenge it