circulant_mixed_graph_valid_and_regular
For z ≥ 1 and g ≥ 3, the circulant mixed graph on N = N(z, g) vertices with antipodal edges of jump m = N/2 and arc jumps 1..⌈z/2⌉ and m+1..m+⌊z/2⌋ is valid and (1, z)-regular.
Statement
theorem circulant_mixed_graph_valid_and_regular (z g : ℕ) (hz : 1 ≤ z) (hg : 3 ≤ g) : let N := if Even z then z * (g - 1) + 2 else (z + 1) * (g - 1) let m := N / 2 let E := SimpleGraph.fromRel fun (x y : Fin N) => (y - x).val = m let A : Fin N → Fin N → Prop := fun x y => (1 ≤ (y - x).val ∧ (y - x).val ≤ (z + 1) / 2) ∨ (m + 1 ≤ (y - x).val ∧ (y - x).val ≤ m + z / 2) mixed_graph_is_valid E A ∧ mixed_graph_is_regular E A 1 z
- Source
- step towards mixed_cage_order_one_le
- Verified
- 23 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- mixed_graph_is_validA mixed graph on V: undirected edges E (a simple graph) and arcs A, with no loops and at most one edge or arc between two vertices (no…
- mixed_graph_is_regularA mixed graph is (r, z)-regular when every vertex has r neighbours along edges, z out-neighbours and z in-neighbours along arcs.
- LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder. - TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or…
- Used by 1
- mixed_cage_order_one_leFor z ≥ 1 and g ≥ 3, n(1, z, g) ≤ N(z, g), where N(z, g) = z(g − 1) + 2 for even z and (z + 1)(g − 1) for odd z: the circulant M(z, g) on…
The proof, explained
The theorem verifies that the circulant mixed graph on $N = N(z, g)$ vertices constructed with antipodal edges of jump $m = N/2$ and directed arc jumps in $1..\lceil z/2 \rceil$ and $m+1..m+\lfloor z/2 \rfloor$ is valid and $(1, z)$-regular. The proof first establishes a general theorem for any $N = 2m$ with $m > z$: validity holds because the arc jump set $T$ avoids 0, is disjoint from its additive inverse (using $(y-x).val + (x-y).val = N$), and avoids the antipodal jump $m$; regularity holds because every vertex has edge degree $|\{m\}| = 1$ and in/out-degree $|T| = \lceil z/2 \rceil + \lfloor z/2 \rfloor = z$ by translation invariance in `Fin N`. Finally, for the specific formula $N(z, g)$ with $z \ge 1$ and $g \ge 3$, a case analysis on the parity of $z$ confirms that $N$ is even and $N \ge 2(z+1)$, which guarantees $z < N/2 = m$.
Modular subtraction followed by addition satisfies $(a + (n - a + z) \bmod n) \bmod n = z$ for $a, z < n$.
We split into cases on whether $z < a$ or $z \ge a$. If $z < a$, the inner sum $n - a + z$ is strictly less than $n$, so the modulo operation is the identity; adding $a$ yields $z + n$, which reduces to $z$ modulo $n$. If $z \ge a$, we rewrite $n - a + z$ as $(z - a) + n$, which reduces modulo $n$ to $z - a < n$, and adding $a$ produces $z$.
uses
Nat.lt_or_ge,Nat.mod_eq_of_lt,Nat.add_mod_righttheorem circulant_mixed_graph_valid_and_regular_nat_add_mod_sub (n a z : ℕ) (ha : a < n) (hz : z < n) : (a + (n - a + z) % n) % n = z := by rcases Nat.lt_or_ge z a with h | h · have hmod : (n - a + z) % n = n - a + z := Nat.mod_eq_of_lt (by omega) rw [hmod]; have : a + (n - a + z) = z + n := by omega rw [this, Nat.add_mod_right, Nat.mod_eq_of_lt hz] · have h1 : n - a + z = (z - a) + n := by omega rw [h1, Nat.add_mod_right]; have h2 : z - a < n := by omega rw [Nat.mod_eq_of_lt h2]; have : a + (z - a) = z := by omega rw [this, Nat.mod_eq_of_lt hz]
Modular addition followed by subtraction satisfies $(n - a + (a + d) \bmod n) \bmod n = d$ for $a, d < n$.
We split on whether $a + d < n$ or $a + d \ge n$. In the first case, $(a + d) \bmod n = a + d$, and $n - a + (a + d) = n + d \equiv d \pmod n$. In the second case, $(a + d) \bmod n = a + d - n$, and $n - a + (a + d - n) = d < n$, so the outer modulo leaves $d$.
uses
Nat.lt_or_ge,Nat.mod_eq_of_lt,Nat.add_mod_left,Nat.mod_eq_sub_modtheorem circulant_mixed_graph_valid_and_regular_nat_sub_add_mod (n a d : ℕ) (ha : a < n) (hd : d < n) : (n - a + (a + d) % n) % n = d := by rcases Nat.lt_or_ge (a + d) n with h | h · rw [Nat.mod_eq_of_lt h]; have : n - a + (a + d) = n + d := by omega rw [this, Nat.add_mod_left, Nat.mod_eq_of_lt hd] · have h2 : (a + d) % n = a + d - n := by rw [Nat.mod_eq_sub_mod h, Nat.mod_eq_of_lt (by omega)] rw [h2]; have : n - a + (a + d - n) = d := by omega rw [this, Nat.mod_eq_of_lt hd]
The cancellation identities $x + (y - x) = y$, $(x + d) - x = d$, $(x - d) + d = x$, and $x - (x - d) = d$ hold in `Fin n`.
By extensionality on `Fin n`, the equality of elements reduces to the equality of their values modulo $n$, which are given by the previous two modular arithmetic lemmas. The remaining two identities follow by commutativity of addition and rewriting $x$ as $(x - d) + d$.
uses
Fin.val_add,Fin.val_sub,circulant_mixed_graph_valid_and_regular_nat_add_mod_sub,circulant_mixed_graph_valid_and_regular_nat_sub_add_mod,add_comm,circulant_mixed_graph_valid_and_regular_fin_add_sub_cancel,circulant_mixed_graph_valid_and_regular_fin_sub_add_cancel,circulant_mixed_graph_valid_and_regular_fin_add_sub_self_righttheorem circulant_mixed_graph_valid_and_regular_fin_add_sub_cancel {n : ℕ} (x y : Fin n) : x + (y - x) = y := by ext; rw [Fin.val_add, Fin.val_sub]; exact circulant_mixed_graph_valid_and_regular_nat_add_mod_sub n x.val y.val x.isLt y.isLt theorem circulant_mixed_graph_valid_and_regular_fin_add_sub_self_right {n : ℕ} (x d : Fin n) : (x + d) - x = d := by ext; rw [Fin.val_sub, Fin.val_add]; exact circulant_mixed_graph_valid_and_regular_nat_sub_add_mod n x.val d.val x.isLt d.isLt theorem circulant_mixed_graph_valid_and_regular_fin_sub_add_cancel {n : ℕ} (x d : Fin n) : (x - d) + d = x := by rw [add_comm]; exact circulant_mixed_graph_valid_and_regular_fin_add_sub_cancel d x theorem circulant_mixed_graph_valid_and_regular_fin_sub_sub_self {n : ℕ} (x d : Fin n) : x - (x - d) = d := by have hx : x = (x - d) + d := (circulant_mixed_graph_valid_and_regular_fin_sub_add_cancel x d).symm nth_rewrite 1 [hx]; exact circulant_mixed_graph_valid_and_regular_fin_add_sub_self_right (x - d) d
For distinct elements $x \ne y$ in `Fin n`, the values of their opposite differences sum to the modulus: $(y - x).val + (x - y).val = n$.
Using the integer representation of difference in `Fin n`, $(y - x).val$ equals $y.val - x.val + (\text{if } x \le y \text{ then } 0 \text{ else } n)$. Because $x \ne y$, exactly one of $x \le y$ or $y \le x$ holds. In either case, the terms $x.val$ and $y.val$ cancel out algebraically, leaving $n$, which is then cast back to natural numbers.
uses
Fin.intCast_val_sub_eq_sub_add_ite,le_antisymm,if_pos,if_neg,le_of_lt,lt_of_not_getheorem circulant_mixed_graph_valid_and_regular_fin_val_sub_add_sub {n : ℕ} (x y : Fin n) (hne : x ≠ y) : (y - x).val + (x - y).val = n := by have h1 := Fin.intCast_val_sub_eq_sub_add_ite y x have h2 := Fin.intCast_val_sub_eq_sub_add_ite x y have key : ((y - x).val : ℤ) + ((x - y).val : ℤ) = n := by rw [h1, h2] by_cases hxy : x ≤ y · have hyx : ¬ (y ≤ x) := by intro h; exact hne (le_antisymm hxy h) rw [if_pos hxy, if_neg hyx]; ring · have hyx : y ≤ x := le_of_lt (lt_of_not_ge hxy) rw [if_neg hxy, if_pos hyx]; ring have key' : ((y - x).val + (x - y).val : ℤ) = n := by exact key exact_mod_cast key'
The cardinality of a coordinate interval $\{d : \text{Fin } N \mid a \le d.val \le b\}$ with $b < N$ is $b + 1 - a$.
The valuation map $d \mapsto d.val$ defines a bijection between this subset of `Fin N` and the integer interval $[a, b] \subseteq \mathbb{N}$, established using `Set.ncard_congr`. The cardinality then matches the standard formula $b + 1 - a$ for the size of an interval of natural numbers.
uses
Set.ncard_congr,Fin.ext,Set.ncard_eq_toFinset_card',Set.toFinset_Icc,Nat.card_Icctheorem circulant_mixed_graph_valid_and_regular_ncard_fin_val_Icc (N a b : ℕ) (hb : b < N) : ({d : Fin N | a ≤ d.val ∧ d.val ≤ b} : Set (Fin N)).ncard = b + 1 - a := by have hmain : ({d : Fin N | a ≤ d.val ∧ d.val ≤ b} : Set (Fin N)).ncard = (Set.Icc a b : Set ℕ).ncard := by apply Set.ncard_congr (f := fun (d : Fin N) (_ : d ∈ {d : Fin N | a ≤ d.val ∧ d.val ≤ b}) => d.val) · intro d hd; simp only [Set.mem_setOf_eq, Set.mem_Icc] at hd ⊢; exact hd · intro d1 d2 hd1 hd2 heq; exact Fin.ext heq · intro k hk; simp only [Set.mem_Icc] at hk refine ⟨⟨k, by omega⟩, ?_, rfl⟩; simp only [Set.mem_setOf_eq]; exact hk rw [hmain, Set.ncard_eq_toFinset_card', Set.toFinset_Icc, Nat.card_Icc]
Left and right translations in `Fin N` preserve set cardinality: $|\{y \mid y - x \in S\}| = |S|$ and $|\{y \mid x - y \in S\}| = |S|$.
For right translation, $d \mapsto x + d$ provides a bijection between $S$ and $\{y \mid y - x \in S\}$ with inverse $y \mapsto y - x$, using the cancellation identities. For left reflection/translation, $d \mapsto x - d$ is an involution providing a bijection between $S$ and $\{y \mid x - y \in S\}$.
uses
Set.ncard_congr,circulant_mixed_graph_valid_and_regular_fin_add_sub_self_right,circulant_mixed_graph_valid_and_regular_fin_add_sub_cancel,circulant_mixed_graph_valid_and_regular_fin_sub_sub_selftheorem circulant_mixed_graph_valid_and_regular_ncard_translate_right (N : ℕ) (x : Fin N) (S : Set (Fin N)) : ({y : Fin N | (y - x) ∈ S} : Set (Fin N)).ncard = S.ncard := by symm apply Set.ncard_congr (f := fun (d : Fin N) (_ : d ∈ S) => x + d) · intro d hd; show (x + d - x) ∈ S; rw [circulant_mixed_graph_valid_and_regular_fin_add_sub_self_right]; exact hd · intro a b ha hb heq calc a = (x + a) - x := (circulant_mixed_graph_valid_and_regular_fin_add_sub_self_right x a).symm _ = (x + b) - x := by rw [heq] _ = b := circulant_mixed_graph_valid_and_regular_fin_add_sub_self_right x b · intro y hy; exact ⟨y - x, hy, circulant_mixed_graph_valid_and_regular_fin_add_sub_cancel x y⟩ theorem circulant_mixed_graph_valid_and_regular_ncard_sub_left (N : ℕ) (x : Fin N) (S : Set (Fin N)) : ({y : Fin N | (x - y) ∈ S} : Set (Fin N)).ncard = S.ncard := by symm apply Set.ncard_congr (f := fun (d : Fin N) (_ : d ∈ S) => x - d) · intro d hd; show (x - (x - d)) ∈ S; rw [circulant_mixed_graph_valid_and_regular_fin_sub_sub_self]; exact hd · intro a b ha hb heq calc a = x - (x - a) := (circulant_mixed_graph_valid_and_regular_fin_sub_sub_self x a).symm _ = x - (x - b) := by rw [heq] _ = b := circulant_mixed_graph_valid_and_regular_fin_sub_sub_self x b · intro y hy; exact ⟨x - y, hy, circulant_mixed_graph_valid_and_regular_fin_sub_sub_self x y⟩
In the general circulant graph with $N = 2m$ and $z < m$, the arc jump set $T = [1, c_1] \cup [m+1, m+c_2]$ has cardinality $z$.
Setting $c_1 = \lfloor (z+1)/2 \rfloor$ and $c_2 = \lfloor z/2 \rfloor$, we have $c_1 + c_2 = z$. The two intervals $[1, c_1]$ and $[m+1, m+c_2]$ are disjoint because $c_1 \le z < m < m+1$, and their upper bound satisfies $m + c_2 \le m + z < 2m = N$. Since $T$ is the disjoint union of these two intervals, its cardinality is $c_1 + c_2 = z$.
uses
Fin.val_sub,Nat.mod_self,Set.disjoint_left,Set.ncard_union_eq,Set.toFinite,circulant_mixed_graph_valid_and_regular_ncard_fin_val_Icctheorem circulant_mixed_graph_valid_and_regular_general (N m z : ℕ) (hz : 1 ≤ z) (hm : z < m) (hNm : N = 2 * m) : mixed_graph_is_valid (SimpleGraph.fromRel fun (x y : Fin N) => (y - x).val = m) (fun x y => (1 ≤ (y - x).val ∧ (y - x).val ≤ (z + 1) / 2) ∨ (m + 1 ≤ (y - x).val ∧ (y - x).val ≤ m + z / 2)) ∧ mixed_graph_is_regular (SimpleGraph.fromRel fun (x y : Fin N) => (y - x).val = m) (fun x y => (1 ≤ (y - x).val ∧ (y - x).val ≤ (z + 1) / 2) ∨ (m + 1 ≤ (y - x).val ∧ (y - x).val ≤ m + z / 2)) 1 z := by set c1 := (z + 1) / 2 with hc1 set c2 := z / 2 with hc2 set E : SimpleGraph (Fin N) := SimpleGraph.fromRel (fun (x y : Fin N) => (y - x).val = m) with hE set T : Set (Fin N) := {d : Fin N | 1 ≤ d.val ∧ d.val ≤ c1 ∨ m + 1 ≤ d.val ∧ d.val ≤ m + c2} with hT set A : Fin N → Fin N → Prop := (fun x y => (1 ≤ (y - x).val ∧ (y - x).val ≤ c1) ∨ (m + 1 ≤ (y - x).val ∧ (y - x).val ≤ m + c2)) with hA have hc12 : c1 + c2 = z := by omega have hmpos : 0 < m := by omega have hmN : m < N := by omega have hc1z : c1 ≤ z := by omega have hc2z : c2 ≤ z := by omega have hmc2N : m + c2 < N := by omega have hval_self : ∀ w : Fin N, (w - w).val = 0 := by intro w rw [Fin.val_sub] have h : N - w.val + w.val = N := by omega rw [h, Nat.mod_self] have hTncard : T.ncard = z := by have hT_eq : T = {d : Fin N | 1 ≤ d.val ∧ d.val ≤ c1} ∪ {d : Fin N | m + 1 ≤ d.val ∧ d.val ≤ m + c2} := by rw [hT]; ext d; simp only [Set.mem_setOf_eq, Set.mem_union] have hdisj : Disjoint ({d : Fin N | 1 ≤ d.val ∧ d.val ≤ c1} : Set (Fin N)) {d : Fin N | m + 1 ≤ d.val ∧ d.val ≤ m + c2} := by rw [Set.disjoint_left]; intro d h1 h2 simp only [Set.mem_setOf_eq] at h1 h2; omega rw [hT_eq, Set.ncard_union_eq hdisj (Set.toFinite _) (Set.toFinite _)] have hn1 : ({d : Fin N | 1 ≤ d.val ∧ d.val ≤ c1} : Set (Fin N)).ncard = c1 := by rw [circulant_mixed_graph_valid_and_regular_ncard_fin_val_Icc N 1 c1 (by omega)]; omega have hn2 : ({d : Fin N | m + 1 ≤ d.val ∧ d.val ≤ m + c2} : Set (Fin N)).ncard = c2 := by rw [circulant_mixed_graph_valid_and_regular_ncard_fin_val_Icc N (m + 1) (m + c2) (by omega)]; omega rw [hn1, hn2, hc12]
The circulant mixed graph is valid: it has no self-loops, arcs are asymmetric, and edges and arcs are disjoint.
Vertices have no self-loops because $(x - x).val = 0$, but all jumps in $T$ are at least 1. For asymmetry, if $y - x \in T$, then $x \ne y$, so $(x - y).val = N - (y - x).val = 2m - (y - x).val$. If $(y - x).val \in [1, c_1]$, then $(x - y).val \in [2m - c_1, 2m - 1]$, which is strictly greater than $m + c_2$ (since $c_1 + c_2 = z < m$), so $x - y \notin T$; the case $(y - x).val \in [m+1, m+c_2]$ is symmetric. Finally, an undirected edge requires $(y - x).val = m$, but $m$ lies strictly between $c_1 \le z < m$ and $m + 1$, so it belongs to neither interval of $T$.
uses
circulant_mixed_graph_valid_and_regular_fin_val_sub_add_sub,SimpleGraph.fromRel_adjconstructor · refine ⟨?_, ?_, ?_⟩ · intro x simp only [hA] have h0 := hval_self x omega · intro x y hAxy simp only [hA] at hAxy ⊢ rcases hAxy with ⟨hp1, hp2⟩ | ⟨hp1, hp2⟩ · have hxy : x ≠ y := by intro h; subst h; rw [hval_self x] at hp1; omega have hsum := circulant_mixed_graph_valid_and_regular_fin_val_sub_add_sub x y hxy have hq : (x - y).val = N - (y - x).val := by omega rw [hq]; omega · have hxy : x ≠ y := by intro h; subst h; rw [hval_self x] at hp1; omega have hsum := circulant_mixed_graph_valid_and_regular_fin_val_sub_add_sub x y hxy have hq : (x - y).val = N - (y - x).val := by omega rw [hq]; omega · intro x y hExy rw [hE, SimpleGraph.fromRel_adj] at hExy simp only [hA] rcases hExy with ⟨hne, hp | hp⟩ · rw [hp]; omega · have hsum := circulant_mixed_graph_valid_and_regular_fin_val_sub_add_sub x y hne have hq : (y - x).val = m := by omega rw [hq]; omega
The circulant mixed graph is $(1, z)$-regular: each vertex has undirected degree 1, out-degree $z$, and in-degree $z$.
An edge incident to $x$ is equivalent to $(y - x).val = m$ because $N = 2m$ implies $(x - y).val = m$ whenever $(y - x).val = m$. The set of neighbors $\{y \mid (y - x).val = m\}$ is a translation of the singleton $\{m\}$, having cardinality $m + 1 - m = 1$. The out-neighborhood $\{y \mid y - x \in T\}$ and in-neighborhood $\{y \mid x - y \in T\}$ are right and left translates of $T$, both having cardinality $|T| = z$.
uses
SimpleGraph.fromRel_adj,circulant_mixed_graph_valid_and_regular_fin_val_sub_add_sub,Or.inl,circulant_mixed_graph_valid_and_regular_ncard_translate_right,circulant_mixed_graph_valid_and_regular_ncard_fin_val_Icc,circulant_mixed_graph_valid_and_regular_ncard_sub_left· intro x have hEadj : ∀ y : Fin N, E.Adj x y ↔ (y - x).val = m := by intro y rw [hE, SimpleGraph.fromRel_adj] constructor · rintro ⟨hne, hp | hp⟩ · exact hp · have hsum := circulant_mixed_graph_valid_and_regular_fin_val_sub_add_sub x y hne; omega · intro hp refine ⟨?_, Or.inl hp⟩ intro hxy; rw [hxy] at hp have hv := hval_self y; omega refine ⟨?_, ?_, ?_⟩ · have hset : {y : Fin N | E.Adj x y} = {y : Fin N | (y - x) ∈ ({d : Fin N | d.val = m} : Set (Fin N))} := by ext y; simp only [Set.mem_setOf_eq]; exact hEadj y rw [hset, circulant_mixed_graph_valid_and_regular_ncard_translate_right N x {d : Fin N | d.val = m}] have he : ({d : Fin N | d.val = m} : Set (Fin N)) = {d : Fin N | m ≤ d.val ∧ d.val ≤ m} := by ext d; simp only [Set.mem_setOf_eq]; omega rw [he, circulant_mixed_graph_valid_and_regular_ncard_fin_val_Icc N m m hmN]; omega · have hset : {y : Fin N | A x y} = {y : Fin N | (y - x) ∈ T} := by ext y; simp only [hA, hT, Set.mem_setOf_eq] rw [hset, circulant_mixed_graph_valid_and_regular_ncard_translate_right N x T]; exact hTncard · have hset : {y : Fin N | A y x} = {y : Fin N | (x - y) ∈ T} := by ext y; simp only [hA, hT, Set.mem_setOf_eq] rw [hset, circulant_mixed_graph_valid_and_regular_ncard_sub_left N x T]; exact hTncard
For $z \ge 1$ and $g \ge 3$, the vertex count $N(z, g)$ is even and satisfies $N \ge 2(z+1)$, which implies $z < N/2$ and $N = 2(N/2)$.
Since $g \ge 3$, $g - 1 \ge 2$. If $z$ is even, $N = z(g-1) + 2$ is the sum of an even product and 2, hence even, and $N \ge 2z + 2 = 2(z+1)$. If $z$ is odd, $z+1$ is even, so $N = (z+1)(g-1)$ is even, and $N \ge 2(z+1)$. In both cases, $N = 2(N/2)$, and dividing $2(z+1) \le N$ by 2 yields $z < z+1 \le N/2$.
uses
if_true,Even.add,even_two,if_false,Nat.mul_le_mul_left,Nat.div_two_mul_two_of_even,Nat.div_le_div_right,Nat.mul_div_righttheorem circulant_mixed_graph_valid_and_regular (z g : ℕ) (hz : 1 ≤ z) (hg : 3 ≤ g) : let N := if Even z then z * (g - 1) + 2 else (z + 1) * (g - 1) let m := N / 2 let E := SimpleGraph.fromRel fun (x y : Fin N) => (y - x).val = m let A : Fin N → Fin N → Prop := fun x y => (1 ≤ (y - x).val ∧ (y - x).val ≤ (z + 1) / 2) ∨ (m + 1 ≤ (y - x).val ∧ (y - x).val ≤ m + z / 2) mixed_graph_is_valid E A ∧ mixed_graph_is_regular E A 1 z := by dsimp only set N := (if Even z then z * (g - 1) + 2 else (z + 1) * (g - 1)) with hN have hg1 : 2 ≤ g - 1 := by omega have hN_even : Even N := by by_cases hze : Even z · rw [hN]; simp only [hze, if_true] exact Even.add (hze.mul_right (g - 1)) even_two · rw [hN]; simp only [hze, if_false] have hodd : Odd z := Nat.not_even_iff_odd.mp hze exact (hodd.add_one).mul_right (g - 1) have hN_ge : 2 * (z + 1) ≤ N := by by_cases hze : Even z · rw [hN]; simp only [hze, if_true] have h2 : z * 2 ≤ z * (g - 1) := Nat.mul_le_mul_left z hg1 omega · rw [hN]; simp only [hze, if_false] have h2 : (z + 1) * 2 ≤ (z + 1) * (g - 1) := Nat.mul_le_mul_left (z + 1) hg1 omega have hNm : N = 2 * (N / 2) := by have h := Nat.div_two_mul_two_of_even hN_even omega have hm : z < N / 2 := by have h1 : (2 * (z + 1)) / 2 ≤ N / 2 := Nat.div_le_div_right hN_ge rw [Nat.mul_div_right (z + 1) (by norm_num : 0 < 2)] at h1 omega
The circulant mixed graph on $N(z, g)$ vertices is valid and $(1, z)$-regular.
We invoke the general circulant graph theorem with $m = N/2$, using the established bounds $1 \le z$, $z < m$, and $N = 2m$.
uses
circulant_mixed_graph_valid_and_regular_generalexact circulant_mixed_graph_valid_and_regular_general N (N / 2) z hz hm hNm
Nat.lt_or_ge- For any two natural numbers $n$ and $m$, either $n < m$ or $n \ge m$.
Nat.mod_eq_of_lt- If $a < b$, then $a \bmod b = a$.
Nat.add_mod_right- For any $x$ and $z$, $(x + z) \bmod z = x \bmod z$.
Nat.add_mod_left- For any $x$ and $z$, $(x + z) \bmod x = z \bmod x$.
Nat.mod_eq_sub_mod- If $a \ge b$, then $a \bmod b = (a - b) \bmod b$.
Fin.val_add- In `Fin n`, the underlying value of $a + b$ is $(a.val + b.val) \bmod n$.
Fin.val_sub- In `Fin n`, the underlying value of $a - b$ is $(n - b.val + a.val) \bmod n$.
circulant_mixed_graph_valid_and_regular_nat_add_mod_sub- For $a, z < n$, $(a + (n - a + z) \bmod n) \bmod n = z$.
circulant_mixed_graph_valid_and_regular_nat_sub_add_mod- For $a, d < n$, $(n - a + (a + d) \bmod n) \bmod n = d$.
add_comm- Addition is commutative: $a + b = b + a$.
circulant_mixed_graph_valid_and_regular_fin_add_sub_cancel- In `Fin n`, $x + (y - x) = y$.
circulant_mixed_graph_valid_and_regular_fin_sub_add_cancel- In `Fin n`, $(x - d) + d = x$.
circulant_mixed_graph_valid_and_regular_fin_add_sub_self_right- In `Fin n`, $(x + d) - x = d$.
circulant_mixed_graph_valid_and_regular_fin_sub_sub_self- In `Fin n`, $x - (x - d) = d$.
Fin.intCast_val_sub_eq_sub_add_ite- In $\mathbb{Z}$, the difference $(a - b).val$ in `Fin n` is $a.val - b.val + (\text{if } b \le a \text{ then } 0 \text{ else } n)$.
le_antisymm- If $a \le b$ and $b \le a$, then $a = b$.
if_pos- If $c$ holds, then $(\text{if } c \text{ then } t \text{ else } e) = t$.
if_neg- If $c$ does not hold, then $(\text{if } c \text{ then } t \text{ else } e) = e$.
le_of_lt- If $a < b$, then $a \le b$.
lt_of_not_ge- If not $b \le a$, then $a < b$.
circulant_mixed_graph_valid_and_regular_fin_val_sub_add_sub- For distinct elements $x \ne y$ in `Fin n`, $(y - x).val + (x - y).val = n$.
Set.ncard_congr- If there is a bijection between subsets $s$ and $t$, then their cardinalities are equal.
Fin.ext- Two elements of `Fin n` are equal if and only if their underlying values are equal.
Set.ncard_eq_toFinset_card'- The cardinality of a finite set equals the cardinality of its coerced finset.
Set.toFinset_Icc- The finset of an interval of integers is the interval Finset.Icc.
Nat.card_Icc- The number of integers in the closed interval $[a, b]$ is $b + 1 - a$.
circulant_mixed_graph_valid_and_regular_ncard_fin_val_Icc- For $b < N$, the number of elements in `Fin N` with values in $[a, b]$ is $b + 1 - a$.
circulant_mixed_graph_valid_and_regular_ncard_translate_right- Right translation preserves subset cardinality in `Fin N`: $|\{y \mid y - x \in S\}| = |S|$.
circulant_mixed_graph_valid_and_regular_ncard_sub_left- Left reflection and translation preserves subset cardinality in `Fin N`: $|\{y \mid x - y \in S\}| = |S|$.
Nat.mod_self- For any $n$, $n \bmod n = 0$.
Set.disjoint_left- Two sets are disjoint if no element of the first belongs to the second.
Set.ncard_union_eq- The cardinality of the union of two disjoint finite sets is the sum of their cardinalities.
Set.toFinite- Any set in a finite type is finite.
SimpleGraph.fromRel_adj- Two vertices are adjacent in a graph induced by a relation iff they are distinct and the relation holds in at least one direction.
Or.inl- From $a$, infer $a \lor b$.
if_true- Evaluating an `if-then-else` on `True` yields the `then` branch.
Even.add- The sum of two even numbers is even.
even_two- The number 2 is even.
if_false- Evaluating an `if-then-else` on `False` yields the `else` branch.
Nat.mul_le_mul_left- If $n \le m$, then $k \cdot n \le k \cdot m$.
Nat.div_two_mul_two_of_even- If $n$ is even, then $(n / 2) \cdot 2 = n$.
Nat.div_le_div_right- If $a \le b$, then $a / c \le b / c$.
Nat.mul_div_right- For $m > 0$, $(m \cdot n) / m = n$.
circulant_mixed_graph_valid_and_regular_general- The circulant mixed graph with antipodal jump $m$ and arc jumps in $1..\lceil z/2 \rceil$ and $m+1..m+\lfloor z/2 \rfloor$ is valid and $(1, z)$-regular whenever $1 \le z < m$ and $N = 2m$.
- The vertices of the circulant graph are formalized as elements of `Fin N`, which requires several explicit algebraic cancellation and difference identities for modular arithmetic that are standard and taken for granted when working informally in $\mathbb{Z}/N\mathbb{Z}$.
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.
theorem circulant_mixed_graph_valid_and_regular_nat_add_mod_sub (n a z : ℕ) (ha : a < n) (hz : z < n) : (a + (n - a + z) % n) % n = z := by rcases Nat.lt_or_ge z a with h | h · have hmod : (n - a + z) % n = n - a + z := Nat.mod_eq_of_lt (by omega) rw [hmod]; have : a + (n - a + z) = z + n := by omega rw [this, Nat.add_mod_right, Nat.mod_eq_of_lt hz] · have h1 : n - a + z = (z - a) + n := by omega rw [h1, Nat.add_mod_right]; have h2 : z - a < n := by omega rw [Nat.mod_eq_of_lt h2]; have : a + (z - a) = z := by omega rw [this, Nat.mod_eq_of_lt hz]theorem circulant_mixed_graph_valid_and_regular_nat_sub_add_mod (n a d : ℕ) (ha : a < n) (hd : d < n) : (n - a + (a + d) % n) % n = d := by rcases Nat.lt_or_ge (a + d) n with h | h · rw [Nat.mod_eq_of_lt h]; have : n - a + (a + d) = n + d := by omega rw [this, Nat.add_mod_left, Nat.mod_eq_of_lt hd] · have h2 : (a + d) % n = a + d - n := by rw [Nat.mod_eq_sub_mod h, Nat.mod_eq_of_lt (by omega)] rw [h2]; have : n - a + (a + d - n) = d := by omega rw [this, Nat.mod_eq_of_lt hd]theorem circulant_mixed_graph_valid_and_regular_fin_add_sub_cancel {n : ℕ} (x y : Fin n) : x + (y - x) = y := by ext; rw [Fin.val_add, Fin.val_sub]; exact circulant_mixed_graph_valid_and_regular_nat_add_mod_sub n x.val y.val x.isLt y.isLttheorem circulant_mixed_graph_valid_and_regular_fin_add_sub_self_right {n : ℕ} (x d : Fin n) : (x + d) - x = d := by ext; rw [Fin.val_sub, Fin.val_add]; exact circulant_mixed_graph_valid_and_regular_nat_sub_add_mod n x.val d.val x.isLt d.isLttheorem circulant_mixed_graph_valid_and_regular_fin_sub_add_cancel {n : ℕ} (x d : Fin n) : (x - d) + d = x := by rw [add_comm]; exact circulant_mixed_graph_valid_and_regular_fin_add_sub_cancel d xtheorem circulant_mixed_graph_valid_and_regular_fin_sub_sub_self {n : ℕ} (x d : Fin n) : x - (x - d) = d := by have hx : x = (x - d) + d := (circulant_mixed_graph_valid_and_regular_fin_sub_add_cancel x d).symm nth_rewrite 1 [hx]; exact circulant_mixed_graph_valid_and_regular_fin_add_sub_self_right (x - d) dtheorem circulant_mixed_graph_valid_and_regular_fin_val_sub_add_sub {n : ℕ} (x y : Fin n) (hne : x ≠ y) : (y - x).val + (x - y).val = n := by have h1 := Fin.intCast_val_sub_eq_sub_add_ite y x have h2 := Fin.intCast_val_sub_eq_sub_add_ite x y have key : ((y - x).val : ℤ) + ((x - y).val : ℤ) = n := by rw [h1, h2] by_cases hxy : x ≤ y · have hyx : ¬ (y ≤ x) := by intro h; exact hne (le_antisymm hxy h) rw [if_pos hxy, if_neg hyx]; ring · have hyx : y ≤ x := le_of_lt (lt_of_not_ge hxy) rw [if_neg hxy, if_pos hyx]; ring have key' : ((y - x).val + (x - y).val : ℤ) = n := by exact key exact_mod_cast key'theorem circulant_mixed_graph_valid_and_regular_ncard_fin_val_Icc (N a b : ℕ) (hb : b < N) : ({d : Fin N | a ≤ d.val ∧ d.val ≤ b} : Set (Fin N)).ncard = b + 1 - a := by have hmain : ({d : Fin N | a ≤ d.val ∧ d.val ≤ b} : Set (Fin N)).ncard = (Set.Icc a b : Set ℕ).ncard := by apply Set.ncard_congr (f := fun (d : Fin N) (_ : d ∈ {d : Fin N | a ≤ d.val ∧ d.val ≤ b}) => d.val) · intro d hd; simp only [Set.mem_setOf_eq, Set.mem_Icc] at hd ⊢; exact hd · intro d1 d2 hd1 hd2 heq; exact Fin.ext heq · intro k hk; simp only [Set.mem_Icc] at hk refine ⟨⟨k, by omega⟩, ?_, rfl⟩; simp only [Set.mem_setOf_eq]; exact hk rw [hmain, Set.ncard_eq_toFinset_card', Set.toFinset_Icc, Nat.card_Icc]theorem circulant_mixed_graph_valid_and_regular_ncard_translate_right (N : ℕ) (x : Fin N) (S : Set (Fin N)) : ({y : Fin N | (y - x) ∈ S} : Set (Fin N)).ncard = S.ncard := by symm apply Set.ncard_congr (f := fun (d : Fin N) (_ : d ∈ S) => x + d) · intro d hd; show (x + d - x) ∈ S; rw [circulant_mixed_graph_valid_and_regular_fin_add_sub_self_right]; exact hd · intro a b ha hb heq calc a = (x + a) - x := (circulant_mixed_graph_valid_and_regular_fin_add_sub_self_right x a).symm _ = (x + b) - x := by rw [heq] _ = b := circulant_mixed_graph_valid_and_regular_fin_add_sub_self_right x b · intro y hy; exact ⟨y - x, hy, circulant_mixed_graph_valid_and_regular_fin_add_sub_cancel x y⟩theorem circulant_mixed_graph_valid_and_regular_ncard_sub_left (N : ℕ) (x : Fin N) (S : Set (Fin N)) : ({y : Fin N | (x - y) ∈ S} : Set (Fin N)).ncard = S.ncard := by symm apply Set.ncard_congr (f := fun (d : Fin N) (_ : d ∈ S) => x - d) · intro d hd; show (x - (x - d)) ∈ S; rw [circulant_mixed_graph_valid_and_regular_fin_sub_sub_self]; exact hd · intro a b ha hb heq calc a = x - (x - a) := (circulant_mixed_graph_valid_and_regular_fin_sub_sub_self x a).symm _ = x - (x - b) := by rw [heq] _ = b := circulant_mixed_graph_valid_and_regular_fin_sub_sub_self x b · intro y hy; exact ⟨x - y, hy, circulant_mixed_graph_valid_and_regular_fin_sub_sub_self x y⟩theorem circulant_mixed_graph_valid_and_regular_general (N m z : ℕ) (hz : 1 ≤ z) (hm : z < m) (hNm : N = 2 * m) : mixed_graph_is_valid (SimpleGraph.fromRel fun (x y : Fin N) => (y - x).val = m) (fun x y => (1 ≤ (y - x).val ∧ (y - x).val ≤ (z + 1) / 2) ∨ (m + 1 ≤ (y - x).val ∧ (y - x).val ≤ m + z / 2)) ∧ mixed_graph_is_regular (SimpleGraph.fromRel fun (x y : Fin N) => (y - x).val = m) (fun x y => (1 ≤ (y - x).val ∧ (y - x).val ≤ (z + 1) / 2) ∨ (m + 1 ≤ (y - x).val ∧ (y - x).val ≤ m + z / 2)) 1 z := by set c1 := (z + 1) / 2 with hc1 set c2 := z / 2 with hc2 set E : SimpleGraph (Fin N) := SimpleGraph.fromRel (fun (x y : Fin N) => (y - x).val = m) with hE set T : Set (Fin N) := {d : Fin N | 1 ≤ d.val ∧ d.val ≤ c1 ∨ m + 1 ≤ d.val ∧ d.val ≤ m + c2} with hT set A : Fin N → Fin N → Prop := (fun x y => (1 ≤ (y - x).val ∧ (y - x).val ≤ c1) ∨ (m + 1 ≤ (y - x).val ∧ (y - x).val ≤ m + c2)) with hA have hc12 : c1 + c2 = z := by omega have hmpos : 0 < m := by omega have hmN : m < N := by omega have hc1z : c1 ≤ z := by omega have hc2z : c2 ≤ z := by omega have hmc2N : m + c2 < N := by omega have hval_self : ∀ w : Fin N, (w - w).val = 0 := by intro w rw [Fin.val_sub] have h : N - w.val + w.val = N := by omega rw [h, Nat.mod_self] have hTncard : T.ncard = z := by have hT_eq : T = {d : Fin N | 1 ≤ d.val ∧ d.val ≤ c1} ∪ {d : Fin N | m + 1 ≤ d.val ∧ d.val ≤ m + c2} := by rw [hT]; ext d; simp only [Set.mem_setOf_eq, Set.mem_union] have hdisj : Disjoint ({d : Fin N | 1 ≤ d.val ∧ d.val ≤ c1} : Set (Fin N)) {d : Fin N | m + 1 ≤ d.val ∧ d.val ≤ m + c2} := by rw [Set.disjoint_left]; intro d h1 h2 simp only [Set.mem_setOf_eq] at h1 h2; omega rw [hT_eq, Set.ncard_union_eq hdisj (Set.toFinite _) (Set.toFinite _)] have hn1 : ({d : Fin N | 1 ≤ d.val ∧ d.val ≤ c1} : Set (Fin N)).ncard = c1 := by rw [circulant_mixed_graph_valid_and_regular_ncard_fin_val_Icc N 1 c1 (by omega)]; omega have hn2 : ({d : Fin N | m + 1 ≤ d.val ∧ d.val ≤ m + c2} : Set (Fin N)).ncard = c2 := by rw [circulant_mixed_graph_valid_and_regular_ncard_fin_val_Icc N (m + 1) (m + c2) (by omega)]; omega rw [hn1, hn2, hc12] constructor · refine ⟨?_, ?_, ?_⟩ · intro x simp only [hA] have h0 := hval_self x omega · intro x y hAxy simp only [hA] at hAxy ⊢ rcases hAxy with ⟨hp1, hp2⟩ | ⟨hp1, hp2⟩ · have hxy : x ≠ y := by intro h; subst h; rw [hval_self x] at hp1; omega have hsum := circulant_mixed_graph_valid_and_regular_fin_val_sub_add_sub x y hxy have hq : (x - y).val = N - (y - x).val := by omega rw [hq]; omega · have hxy : x ≠ y := by intro h; subst h; rw [hval_self x] at hp1; omega have hsum := circulant_mixed_graph_valid_and_regular_fin_val_sub_add_sub x y hxy have hq : (x - y).val = N - (y - x).val := by omega rw [hq]; omega · intro x y hExy rw [hE, SimpleGraph.fromRel_adj] at hExy simp only [hA] rcases hExy with ⟨hne, hp | hp⟩ · rw [hp]; omega · have hsum := circulant_mixed_graph_valid_and_regular_fin_val_sub_add_sub x y hne have hq : (y - x).val = m := by omega rw [hq]; omega · intro x have hEadj : ∀ y : Fin N, E.Adj x y ↔ (y - x).val = m := by intro y rw [hE, SimpleGraph.fromRel_adj] constructor · rintro ⟨hne, hp | hp⟩ · exact hp · have hsum := circulant_mixed_graph_valid_and_regular_fin_val_sub_add_sub x y hne; omega · intro hp refine ⟨?_, Or.inl hp⟩ intro hxy; rw [hxy] at hp have hv := hval_self y; omega refine ⟨?_, ?_, ?_⟩ · have hset : {y : Fin N | E.Adj x y} = {y : Fin N | (y - x) ∈ ({d : Fin N | d.val = m} : Set (Fin N))} := by ext y; simp only [Set.mem_setOf_eq]; exact hEadj y rw [hset, circulant_mixed_graph_valid_and_regular_ncard_translate_right N x {d : Fin N | d.val = m}] have he : ({d : Fin N | d.val = m} : Set (Fin N)) = {d : Fin N | m ≤ d.val ∧ d.val ≤ m} := by ext d; simp only [Set.mem_setOf_eq]; omega rw [he, circulant_mixed_graph_valid_and_regular_ncard_fin_val_Icc N m m hmN]; omega · have hset : {y : Fin N | A x y} = {y : Fin N | (y - x) ∈ T} := by ext y; simp only [hA, hT, Set.mem_setOf_eq] rw [hset, circulant_mixed_graph_valid_and_regular_ncard_translate_right N x T]; exact hTncard · have hset : {y : Fin N | A y x} = {y : Fin N | (x - y) ∈ T} := by ext y; simp only [hA, hT, Set.mem_setOf_eq] rw [hset, circulant_mixed_graph_valid_and_regular_ncard_sub_left N x T]; exact hTncard/-- The circulant mixed graph M(z, g) on N(z, g) vertices is valid (loopless, asymmetric arcs, disjoint edge and arc sets) and (1, z)-regular. -/theorem circulant_mixed_graph_valid_and_regular (z g : ℕ) (hz : 1 ≤ z) (hg : 3 ≤ g) : let N := if Even z then z * (g - 1) + 2 else (z + 1) * (g - 1) let m := N / 2 let E := SimpleGraph.fromRel fun (x y : Fin N) => (y - x).val = m let A : Fin N → Fin N → Prop := fun x y => (1 ≤ (y - x).val ∧ (y - x).val ≤ (z + 1) / 2) ∨ (m + 1 ≤ (y - x).val ∧ (y - x).val ≤ m + z / 2) mixed_graph_is_valid E A ∧ mixed_graph_is_regular E A 1 z := by dsimp only set N := (if Even z then z * (g - 1) + 2 else (z + 1) * (g - 1)) with hN have hg1 : 2 ≤ g - 1 := by omega have hN_even : Even N := by by_cases hze : Even z · rw [hN]; simp only [hze, if_true] exact Even.add (hze.mul_right (g - 1)) even_two · rw [hN]; simp only [hze, if_false] have hodd : Odd z := Nat.not_even_iff_odd.mp hze exact (hodd.add_one).mul_right (g - 1) have hN_ge : 2 * (z + 1) ≤ N := by by_cases hze : Even z · rw [hN]; simp only [hze, if_true] have h2 : z * 2 ≤ z * (g - 1) := Nat.mul_le_mul_left z hg1 omega · rw [hN]; simp only [hze, if_false] have h2 : (z + 1) * 2 ≤ (z + 1) * (g - 1) := Nat.mul_le_mul_left (z + 1) hg1 omega have hNm : N = 2 * (N / 2) := by have h := Nat.div_two_mul_two_of_even hN_even omega have hm : z < N / 2 := by have h1 : (2 * (z + 1)) / 2 ≤ N / 2 := Nat.div_le_div_right hN_ge rw [Nat.mul_div_right (z + 1) (by norm_num : 0 < 2)] at h1 omega exact circulant_mixed_graph_valid_and_regular_general N (N / 2) z hz hm hNm