AFTD Auto-Formalizing Theoretical Domains

complete_order_graph_dim_six_upper_bound

theoremverified

There exists a complete order graph of dimension 6 with exactly 40 edges.

Statement

theorem complete_order_graph_dim_six_upper_bound :
    ∃ G : OrderGraph 6, order_graph_is_complete G ∧ G.E.card = 40
Source
arXiv:2610.39311 Corollary 8 -- Tight Asymptotic Bounds on the Size of Order Graphs
Verified
08 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 6
  • order_move_to_frontThe order obtained by moving attribute a to the front of order π, preserving the relative order of the remaining attributes.
  • OrderGraphAn order graph of dimension d is a structure consisting of a finite set V of orders of Fin d and a finite set E of edges (π, a) where π :…
  • OrderAn order of dimension d is a permutation of the attribute set {0, ..., d-1}, represented as a list without duplicates containing all…
  • order_graph_servesAn order graph G serves requirement (S, x) where S is a finite set of Fin d and x : Fin d if there exists a nonempty list of edges p all…
  • order_graph_is_completeAn order graph G is complete in the bidirectional model if for every subset S ⊆ Fin d and every element x : Fin d with x ∉ S, G serves…
  • VThe ambient space $V = \mathbb{F}_p^n \times \mathbb{F}_p^n$ of pairs of coordinate vectors.
Used by 1

Read back from the Lean

There exists an OrderGraph of dimension 6, G, such that: 1. G is complete (order_graph_is_complete G), meaning that for every subset $S \subseteq \text{Fin } 6$ and every $x \in \text{Fin } 6$ with $x \notin S$, $G$ serves $(S, x)$ (i.e., there exists a directed path of edges in $G$ of length $|S| + 1$ such that the set of edge labels along the path is exactly $S \cup \{x\}$, and either the first edge or the last edge of the path has label $x$); and 2. The number of edges in $G$ (G.E.card) is exactly 40.

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 explicitly constructing an order graph $G$ on dimension 6 with 40 vertices (permutations) and 40 edges corresponding to prefix move operations. To prove that $G$ is complete, the proof defines a decidable predicate `path_good` certifying that a path serves a given subset $S$ and element $x \notin S$, and proves that any such path indeed satisfies the serving condition. Completeness is then verified by an exhaustive finite computation (`decide`) searching over a precomputed set of candidate paths for all 192 valid pairs $(S, x)$, while the edge count $|G.E| = 40$ is verified by direct calculation.

  1. The fallback list $[0, 1, 2, 3, 4, 5]$ is a valid total order of dimension 6.

    In the conversion function `listToOrder`, any input list not satisfying the order conditions falls back to $[0, 1, 2, 3, 4, 5]$. Both properties (`Nodup` and length 6) for this concrete list are verified by `decide`.

    line 5

      else ⟨[0, 1, 2, 3, 4, 5], by decide, by decide⟩
  2. All edges in the graph $G$ have valid sources and targets in the vertex set.

    To construct the `OrderGraph 6` structure $G$, we must check that every edge $(\pi, a) \in G.E$ has source $\pi \in G.V$ and target $\operatorname{order\_move\_to\_front}(a, \pi) \in G.V$. Both conditions are verified across all 40 edges by finite evaluation (`decide`).

    lines 55–56

      edge_src := by decide
      edge_tgt := by decide
  3. The serving-path condition `path_good` and the existence of a serving path among candidate paths are decidable.

    The predicate `path_good` expresses the serving condition via decidable operations on lists and finite sets. Unfolding `path_good` allows Lean to automatically infer its decidability (`infer_instance`). Decidability of the bounded existential search $\exists p \in candidates, \dots$ is then synthesized directly from the decidability of `path_good`.

    lines 68–75

      dsimp [complete_order_graph_dim_six_upper_bound_path_good]
      infer_instance
    
    instance (G : OrderGraph 6) (candidates : List (List (Order 6 × Fin 6)))
        (S : Finset (Fin 6)) (x : Fin 6) :
        Decidable (∃ p ∈ candidates, complete_order_graph_dim_six_upper_bound_path_good G S x p) := by
      have : DecidablePred (complete_order_graph_dim_six_upper_bound_path_good G S x) := inferInstance
      infer_instance
  4. A path satisfying `path_good` cannot be empty.

    We decompose the hypothesis that $p$ is good into its properties: edge validity, chaining, length $|S|+1$, label set $S \cup \{x\}$, and endpoint condition `hend`. If $p$ were the empty list, both `p.head?` and `p.getLast?` would evaluate to `none`, contradicting `hend` which asserts that one of them is `some e`.

    lines 80–83

    uses List.head?, List.getLast?

      rcases h with ⟨he, hchain, hlen, hset, hend⟩
      have hp_ne : p ≠ [] := by
        rintro rfl
        simp [List.head?, List.getLast?] at hend
  5. If the first edge of $p$ is labeled by $x$, then $p$ witnesses that $G$ serves $(S, x)$.

    We provide $p$, its nonemptiness proof `hp_ne`, and its chaining and set properties to establish `order_graph_serves G S x`. In the first case of `hend`, the head edge is some $e$ with label $x$. Using `List.head?_eq_some_head` and injectivity of `some` (`Option.some_inj`), we identify $e$ with `p.head hp_ne`, showing $(p\text{.head } hp\_ne).2 = x$.

    lines 84–88

    uses List.head?_eq_some_head, Option.some_inj

      refine ⟨p, hp_ne, he, hchain, hlen, hset, ?_⟩
      rcases hend with (⟨e, heq, he2⟩ | ⟨e, heq, he2⟩)
      · left
        rw [List.head?_eq_some_head hp_ne, Option.some_inj] at heq
        rw [← he2, ← heq]
  6. If the last edge of $p$ is labeled by $x$, then $p$ witnesses that $G$ serves $(S, x)$.

    In the second case of `hend`, the last edge is some $e$ with label $x$. Using `List.getLast?_eq_some_getLast` and `Option.some_inj`, we identify $e$ with `p.getLast hp_ne`, showing $(p\text{.getLast } hp\_ne).2 = x$.

    lines 89–91

    uses List.getLast?_eq_some_getLast, Option.some_inj

      · right
        rw [List.getLast?_eq_some_getLast hp_ne, Option.some_inj] at heq
        rw [← he2, ← heq]
  7. For every subset $S \subseteq \{0,\dots,5\}$ and element $x \notin S$, there is a candidate path satisfying `path_good`. automation

    Because $\{0,\dots,5\}$ has only $2^6 = 64$ subsets and 6 elements, checking all pairs $(S, x)$ with $x \notin S$ is a finite problem ($6 \times 2^5 = 192$ instances). For each pair, an exhaustive search through the precomputed list `allCandidatePaths` finds a path satisfying `path_good`, fully verified by `decide`.

    line 97

      decide
  8. The graph $G$ has exactly 40 edges, reducing the goal to showing completeness of $G$.

    We witness the existential with the explicitly constructed graph $G$. The conjunct $|G.E| = 40$ is verified by finite evaluation (`decide`), leaving only the completeness of $G$ to be proved.

    line 102

      refine ⟨complete_order_graph_dim_six_upper_bound_G, ?_, by decide⟩
  9. The graph $G$ is complete, establishing the theorem.

    Given any subset $S$ and element $x \notin S$, we invoke `complete_order_graph_dim_six_upper_bound_check` to obtain a candidate path $p$ satisfying `path_good G S x p`. Applying lemma `complete_order_graph_dim_six_upper_bound_serves_of_path_good` to $p$ shows that $G$ serves $(S, x)$. Since $S$ and $x \notin S$ were arbitrary, $G$ is complete.

    lines 103–106

    uses complete_order_graph_dim_six_upper_bound_check, complete_order_graph_dim_six_upper_bound_serves_of_path_good

      intro S x hx
      have h := complete_order_graph_dim_six_upper_bound_check S x hx
      rcases h with ⟨p, -, hp⟩
      exact complete_order_graph_dim_six_upper_bound_serves_of_path_good hp
List.head?
Returns the first element of a list wrapped in `some`, or `none` if the list is empty.
List.getLast?
Returns the last element of a list wrapped in `some`, or `none` if the list is empty.
List.head?_eq_some_head
For any nonempty list, its optional head `head?` equals `some` of its actual head element.
Option.some_inj
The `some` constructor of `Option` is injective: `some a = some b` if and only if `a = b`.
List.getLast?_eq_some_getLast
For any nonempty list, its optional last element `getLast?` equals `some` of its actual last element.
complete_order_graph_dim_six_upper_bound_check
Every subset $S \subseteq \{0,\dots,5\}$ and element $x \notin S$ has a candidate path in $G$ satisfying `path_good`.
complete_order_graph_dim_six_upper_bound_serves_of_path_good
If a path in an order graph satisfies `path_good` for $(S, x)$, then the graph serves $(S, x)$.

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

set_option maxHeartbeats 4000000def complete_order_graph_dim_six_upper_bound_listToOrder (l : List (Fin 6)) : Order 6 :=  if h : l.Nodup ∧ l.length = 6 then ⟨l, h.1, h.2⟩  else ⟨[0, 1, 2, 3, 4, 5], by decide, by decide⟩def complete_order_graph_dim_six_upper_bound_rawOrders : List (List (Fin 6)) := [  [5, 1, 0, 4, 2, 3], [4, 3, 2, 1, 0, 5], [3, 2, 1, 0, 4, 5], [4, 5, 1, 2, 0, 3],  [5, 1, 2, 4, 0, 3], [1, 2, 4, 0, 5, 3], [2, 4, 0, 5, 1, 3], [3, 4, 0, 5, 2, 1],  [4, 0, 5, 2, 1, 3], [0, 5, 2, 1, 4, 3], [0, 1, 3, 5, 2, 4], [5, 2, 4, 1, 3, 0],  [2, 4, 1, 3, 5, 0], [4, 1, 3, 5, 2, 0], [1, 3, 5, 2, 0, 4], [1, 4, 3, 0, 2, 5],  [4, 3, 0, 2, 5, 1], [3, 0, 2, 4, 5, 1], [2, 3, 1, 5, 0, 4], [3, 1, 5, 0, 2, 4],  [1, 5, 0, 2, 4, 3], [3, 5, 0, 2, 4, 1], [5, 0, 2, 4, 3, 1], [0, 2, 4, 3, 5, 1],  [2, 4, 3, 5, 1, 0], [4, 3, 5, 2, 1, 0], [3, 5, 2, 1, 0, 4], [5, 2, 1, 0, 4, 3],  [2, 1, 0, 4, 5, 3], [1, 0, 4, 5, 2, 3], [0, 4, 5, 2, 3, 1], [4, 5, 2, 3, 0, 1],  [5, 2, 3, 0, 1, 4], [2, 3, 0, 1, 4, 5], [3, 0, 1, 4, 5, 2], [5, 3, 0, 1, 4, 2],  [4, 5, 3, 0, 1, 2], [1, 4, 5, 3, 0, 2], [0, 1, 4, 5, 3, 2], [2, 0, 1, 4, 5, 3]]def complete_order_graph_dim_six_upper_bound_theOrders : List (Order 6) :=  complete_order_graph_dim_six_upper_bound_rawOrders.map complete_order_graph_dim_six_upper_bound_listToOrderdef complete_order_graph_dim_six_upper_bound_findParent (pi : Order 6) (orders : List (Order 6)) : Option (Order 6 × Fin 6) :=  match pi.elems with  | [] => none  | a :: _ =>    (orders.filter (fun nu => nu ≠ pi && order_move_to_front a nu == pi)).head? |>.map (fun nu => (nu, a))def complete_order_graph_dim_six_upper_bound_theEdges : List (Order 6 × Fin 6) :=  complete_order_graph_dim_six_upper_bound_theOrders.filterMap    (fun pi => complete_order_graph_dim_six_upper_bound_findParent pi complete_order_graph_dim_six_upper_bound_theOrders)def complete_order_graph_dim_six_upper_bound_stepPaths    (edges : List (Order 6 × Fin 6)) (paths : List (List (Order 6 × Fin 6))) : List (List (Order 6 × Fin 6)) :=  paths.flatMap (fun p =>    match p.getLast? with    | none => []    | some last =>      let target := order_move_to_front last.2 last.1      let labels := p.map Prod.snd      (edges.filter (fun e => e.1 == target && !labels.contains e.2)).map (fun e => p ++ [e]))def complete_order_graph_dim_six_upper_bound_allCandidatePaths : List (List (Order 6 × Fin 6)) :=  let p1 := complete_order_graph_dim_six_upper_bound_theEdges.map (fun e => [e])  let p2 := complete_order_graph_dim_six_upper_bound_stepPaths complete_order_graph_dim_six_upper_bound_theEdges p1  let p3 := complete_order_graph_dim_six_upper_bound_stepPaths complete_order_graph_dim_six_upper_bound_theEdges p2  let p4 := complete_order_graph_dim_six_upper_bound_stepPaths complete_order_graph_dim_six_upper_bound_theEdges p3  let p5 := complete_order_graph_dim_six_upper_bound_stepPaths complete_order_graph_dim_six_upper_bound_theEdges p4  let p6 := complete_order_graph_dim_six_upper_bound_stepPaths complete_order_graph_dim_six_upper_bound_theEdges p5  p1 ++ p2 ++ p3 ++ p4 ++ p5 ++ p6def complete_order_graph_dim_six_upper_bound_G : OrderGraph 6 where  V := complete_order_graph_dim_six_upper_bound_theOrders.toFinset  E := complete_order_graph_dim_six_upper_bound_theEdges.toFinset  edge_src := by decide  edge_tgt := by decidedef complete_order_graph_dim_six_upper_bound_path_good    (G : OrderGraph 6) (S : Finset (Fin 6)) (x : Fin 6) (p : List (Order 6 × Fin 6)) : Prop :=  (∀ e ∈ p, e ∈ G.E) ∧  p.IsChain (fun e1 e2 => e2.1 = order_move_to_front e1.2 e1.1) ∧  p.length = S.card + 1 ∧  (p.map Prod.snd).toFinset = insert x S ∧  ((∃ e, p.head? = some e ∧ e.2 = x) ∨ (∃ e, p.getLast? = some e ∧ e.2 = x))instance (G : OrderGraph 6) (S : Finset (Fin 6)) (x : Fin 6) (p : List (Order 6 × Fin 6)) :    Decidable (complete_order_graph_dim_six_upper_bound_path_good G S x p) := by  dsimp [complete_order_graph_dim_six_upper_bound_path_good]  infer_instanceinstance (G : OrderGraph 6) (candidates : List (List (Order 6 × Fin 6)))    (S : Finset (Fin 6)) (x : Fin 6) :    Decidable (∃ p ∈ candidates, complete_order_graph_dim_six_upper_bound_path_good G S x p) := by  have : DecidablePred (complete_order_graph_dim_six_upper_bound_path_good G S x) := inferInstance  infer_instancelemma complete_order_graph_dim_six_upper_bound_serves_of_path_good    {G : OrderGraph 6} {S : Finset (Fin 6)} {x : Fin 6} {p : List (Order 6 × Fin 6)}    (h : complete_order_graph_dim_six_upper_bound_path_good G S x p) : order_graph_serves G S x := by  rcases h with ⟨he, hchain, hlen, hset, hend⟩  have hp_ne : p ≠ [] := by    rintro rfl    simp [List.head?, List.getLast?] at hend  refine ⟨p, hp_ne, he, hchain, hlen, hset, ?_⟩  rcases hend with (⟨e, heq, he2⟩ | ⟨e, heq, he2⟩)  · left    rw [List.head?_eq_some_head hp_ne, Option.some_inj] at heq    rw [← he2, ← heq]  · right    rw [List.getLast?_eq_some_getLast hp_ne, Option.some_inj] at heq    rw [← he2, ← heq]theorem complete_order_graph_dim_six_upper_bound_check :    ∀ (S : Finset (Fin 6)) (x : Fin 6), x ∉ S →      ∃ p ∈ complete_order_graph_dim_six_upper_bound_allCandidatePaths,        complete_order_graph_dim_six_upper_bound_path_good complete_order_graph_dim_six_upper_bound_G S x p := by  decide/-- Upper bound showing existence of a 40-edge complete order graph of dimension 6. -/theorem complete_order_graph_dim_six_upper_bound :    ∃ G : OrderGraph 6, order_graph_is_complete G ∧ G.E.card = 40 := by  refine ⟨complete_order_graph_dim_six_upper_bound_G, ?_, by decide⟩  intro S x hx  have h := complete_order_graph_dim_six_upper_bound_check S x hx  rcases h with ⟨p, -, hp⟩  exact complete_order_graph_dim_six_upper_bound_serves_of_path_good hp
See it in the graphDiscuss this resultChallenge it