complete_order_graph_dim_six_upper_bound
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
- complete_order_graph_dim_six_min_sizeThe minimum size of a complete order graph of dimension 6 is exactly 40: every complete order graph of dimension 6 has at least 40 edges,…
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.
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`.
else ⟨[0, 1, 2, 3, 4, 5], by decide, by decide⟩
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`).
edge_src := by decide edge_tgt := by decide
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`.
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
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`.
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
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$.
uses
List.head?_eq_some_head,Option.some_injrefine ⟨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]
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$.
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]
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`.
decideThe 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.
refine ⟨complete_order_graph_dim_six_upper_bound_G, ?_, by decide⟩
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.
uses
complete_order_graph_dim_six_upper_bound_check,complete_order_graph_dim_six_upper_bound_serves_of_path_goodintro 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)$.
- The completeness of the graph is established computationally: theorem `complete_order_graph_dim_six_upper_bound_check` verifies all 192 valid pairs $(S, x)$ by exhaustive finite evaluation (`decide`) over precomputed candidate paths.
- The definition `path_good` serves as a computationally decidable version of `order_graph_serves`, replacing partial list access functions (`head`, `getLast`) with option-valued functions (`head?`, `getLast?`) to avoid proof obligations during computation.
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 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