AFTD Auto-Formalizing Theoretical Domains

hypercube_max_coil_disjoint_squares_pos

theoremverified

For n ≥ 13, if S is a maximum coil in Q_n with degree count y_0 > 0, then the number F_5 of squares disjoint from S is strictly positive.

Statement

open scoped Classical in
theorem hypercube_max_coil_disjoint_squares_pos (n : ℕ) (hn : 13 ≤ n) (S : Finset (Fin n → Bool))
    (hS : is_max_hypercube_coil n S) (hy0 : 0 < hypercube_degree_count n S 0) :
    0 < hypercube_disjoint_squares_count n S
Source
arXiv:2610.36461 Corollary 3
Verified
30 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 7
  • is_max_hypercube_coilA coil S in Q_n is a maximum coil if its cardinality is at least that of any other coil in Q_n.
  • hypercube_degree_countThe degree count y_m is the number of vertices x in the complement of S having exactly m neighbors in S.
  • hypercube_disjoint_squares_countThe count F_5 is the number of squares in Q_n that contain no vertex of S.
  • is_hypercube_squareA subset of 4 vertices in the hypercube Q_n is a square if its induced subgraph is isomorphic to the 4-cycle C_4.
  • hypercube_coilA subset S of vertices in the hypercube Q_n is a coil if it has size at least 4 and its induced subgraph is isomorphic to a cycle graph of…
  • simple_graph_hypercubeThe hypercube graph Q_n on vertex set Fin n → Bool, where two vertices are adjacent if and only if they differ at exactly one coordinate.
  • g$g(S,M) = \dim_{\mathbb{F}_p}(S^{\perp}_M) - \dim_{\mathbb{F}_p}(S_M)$.

Read back from the Lean

For any natural number $n \ge 13$ and any subset $S$ of vertices of the $n$-dimensional hypercube $\{0, 1\}^n$, if $S$ is a maximum-cardinality coil (that is, $S$ induces a cycle graph of length at least 4 in the hypercube graph, and no other coil in the hypercube has strictly greater cardinality than $S$) and there is at least one vertex in $\{0, 1\}^n \setminus S$ that has zero neighbors in $S$, then there exists at least one 4-cycle (square) in the hypercube that is disjoint from $S$ (meaning the count of such disjoint squares is strictly positive).

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

To show that any maximum coil S in Q_n (with n ≥ 13) having y_0 > 0 has at least one disjoint square, we argue by contradiction and suppose no square is disjoint from S. The condition y_0 > 0 gives a vertex x with no neighbors in S. For any two distinct coordinates i and j, the 4-cycle formed by x, x^{{i}}, x^{{j}}, and x^{{i,j}} must intersect S; since the first three vertices lie outside S, every double flip x^{{i,j}} must belong to S. Picking two distinct coordinates 0 and 1, the vertex x^{{0,1}} ∈ S has a neighbor z in S, which must be a single flip along a third coordinate k ∉ {0, 1}. But then z has three distinct neighbors in S—namely the double flips on {0,1}, {1,k}, and {0,k}—contradicting the fact that every vertex in a cycle has at most two neighbors.

  1. Flipping the same coordinate twice is the identity operation

    At coordinate i the boolean is negated twice, which simplifies to the original value, while all other coordinates are unchanged.

    line 4

    uses Function.update_apply

      funext t; simp only [hmc363_flip, Function.update_apply]; split_ifs <;> simp_all
  2. Flipping two coordinates commutes

    If the two indices are equal, the operations are identical. If they are distinct, evaluating at any coordinate t affects only bit i or bit j independently, so the order of flipping does not matter.

    lines 8–16

    uses Function.update_apply, Ne.symm

      by_cases hij : i = j
      · subst hij; rfl
      funext t
      simp only [hmc363_flip, Function.update_apply]
      by_cases hti : t = i
      · subst hti; simp [hij]
      · by_cases htj : t = j
        · subst htj; simp [hti, Ne.symm hij]
        · simp [hti, htj]
  3. Two vertices in Q_n are adjacent if and only if they differ in exactly one coordinate

    By definition, Q_n is the graph from the relation of differing at a unique index. Since differing at an index is symmetric, the relation holds symmetrically between distinct vertices.

    lines 20–27

    uses SimpleGraph.fromRel_adj, Or.inl

      unfold simple_graph_hypercube
      rw [SimpleGraph.fromRel_adj]
      constructor
      · rintro ⟨hne, h | h⟩
        · exact ⟨hne, h⟩
        · obtain ⟨k, hk, hu⟩ := h
          exact ⟨hne, k, fun e => hk e.symm, fun t ht => hu t (fun e => ht e.symm)⟩
      · rintro ⟨hne, h⟩; exact ⟨hne, Or.inl h⟩
  4. Flipping a single coordinate produces an adjacent vertex

    The vertex x and flip(x, i) differ at coordinate i and agree everywhere else, which matches the characterization of hypercube adjacency.

    lines 31–34

    uses hmc363_adj_iff, congrFun, Function.update_apply

      rw [hmc363_adj_iff]
      refine ⟨fun e => ?_, i, by simp [hmc363_flip], fun t ht => ?_⟩
      · have := congrFun e i; simp [hmc363_flip] at this
      · by_contra hti; exact ht (by simp [hmc363_flip, Function.update_apply, hti])
  5. Flipping two distinct coordinates produces a non-adjacent vertex

    The vertex x and the double flip flip(flip(x, i), j) differ at both coordinate i and coordinate j. Since i ≠ j, they cannot differ at a unique coordinate, so they are not adjacent.

    lines 38–42

    uses hmc363_adj_iff, Function.update_apply, Ne.symm

      rw [hmc363_adj_iff]
      rintro ⟨-, k, -, hu⟩
      have hi := hu i (by simp [hmc363_flip, Function.update_apply, hij])
      have hj := hu j (by simp [hmc363_flip, Function.update_apply, hij, Ne.symm hij])
      exact hij (hi.trans hj.symm)
  6. Every neighbor of x in Q_n is obtained by flipping a unique coordinate

    Adjacency implies x and y differ at a unique coordinate k. Thus y(k) is the negation of x(k) while agreeing with x at all other coordinates, so y = flip(x, k).

    lines 46–53

    uses hmc363_adj_iff, Function.update_self, Function.update_apply, if_false, Ne.symm

      rw [hmc363_adj_iff] at h
      obtain ⟨-, k, hk, hu⟩ := h
      refine ⟨k, funext fun t => ?_⟩
      by_cases htk : t = k
      · subst htk; simp only [hmc363_flip, Function.update_self]
        cases hx : x t <;> cases hy : y t <;> simp_all
      · simp only [hmc363_flip, Function.update_apply, htk, if_false]
        by_contra hne; exact htk (hu t (Ne.symm hne))
  7. Every vertex in a cycle graph of length at least 3 has a neighbor, and has at most two neighbors

    Via the graph isomorphism f to a standard cycle graph, neighbors of f(v) are f(v) - 1 and f(v) + 1. Thus f^{-1}(f(v) + 1) is a neighbor of v. By the pigeonhole principle, any three neighbors must send at least two vertices to the same neighbor in the cycle, which forces those two vertices to be equal by injectivity.

    lines 58–72

    uses SimpleGraph.cycleGraph_neighborSet, RelIso.apply_symm_apply, SimpleGraph.cycleGraph_adj, Or.inl, Or.inr

      have key : ∀ a, H.Adj v a → f a = f v - 1 ∨ f a = f v + 1 := by
        intro a ha
        have h' : (SimpleGraph.cycleGraph (m + 1 + 2)).Adj (f v) (f a) := f.map_adj_iff.mpr ha
        have : f a ∈ (SimpleGraph.cycleGraph (m + 1 + 2)).neighborSet (f v) := h'
        rw [SimpleGraph.cycleGraph_neighborSet] at this
        simpa using this
      refine ⟨⟨f.symm (f v + 1), ?_⟩, fun a b c ha hb hc => ?_⟩
      · rw [← f.map_adj_iff, RelIso.apply_symm_apply]
        show (SimpleGraph.cycleGraph (m + 1 + 2)).Adj _ _
        rw [SimpleGraph.cycleGraph_adj]; right; simp
      · rcases key a ha with h1 | h1 <;> rcases key b hb with h2 | h2 <;> rcases key c hc with h3 | h3
        all_goals first
          | exact Or.inl (f.injective (h1.trans h2.symm))
          | exact Or.inr (Or.inl (f.injective (h1.trans h3.symm)))
          | exact Or.inr (Or.inr (f.injective (h2.trans h3.symm)))
  8. Every vertex in a coil S has a neighbor in S, and no vertex has three pairwise distinct neighbors in S

    A coil S induces a cycle graph of size at least 4. Transferring the cycle neighbor property to S shows that every vertex has a neighbor in S and cannot have three pairwise distinct neighbors in S.

    lines 79–87

    uses hmc363_cycle_nbrs, Or.inl, congrArg, Subtype.val, Or.inr

      obtain ⟨h4, ⟨f⟩⟩ := hcoil
      have hm : S.card = (S.card - 3) + 3 := by omega
      rw [hm] at f
      obtain ⟨⟨⟨y, hy⟩, hxy⟩, h2⟩ := hmc363_cycle_nbrs _ _ f ⟨x, hx⟩
      refine ⟨⟨y, hy, hxy⟩, fun a b c ha hb hc hxa hxb hxc => ?_⟩
      rcases h2 ⟨a, ha⟩ ⟨b, hb⟩ ⟨c, hc⟩ hxa hxb hxc with h | h | h
      · exact Or.inl (congrArg Subtype.val h)
      · exact Or.inr (Or.inl (congrArg Subtype.val h))
      · exact Or.inr (Or.inr (congrArg Subtype.val h))
  9. Flipping distinct coordinates produces distinct vertices

    Evaluating flip(z, p) and flip(z, q) at coordinate p shows that the former flips z(p) while the latter keeps z(p), so they cannot be equal.

    lines 91–93

    uses congrFun, Function.update_apply

      intro h
      have := congrFun h p
      simp [hmc363_flip, Function.update_apply, hpq] at this
  10. The four vertices formed by flipping coordinates i and j form an induced 4-cycle in Q_n

    Consecutive pairs differ in one coordinate and are adjacent, while opposite pairs differ in two distinct coordinates and are not adjacent. Exhaustive verification across all pairs in Fin 4 confirms it is an induced C_4.

    lines 101–117

    uses hmc363_adj_flip, hmc363_flip_comm, hmc363_not_adj_double, hmc363_flip_flip

      have h01 := hmc363_adj_flip v i
      have h12 := hmc363_adj_flip (hmc363_flip v i) j
      have h23 : (simple_graph_hypercube n).Adj (hmc363_flip (hmc363_flip v i) j) (hmc363_flip v j) := by
        rw [hmc363_flip_comm]; exact (hmc363_adj_flip (hmc363_flip v j) i).symm
      have h30 := (hmc363_adj_flip v j).symm
      have h02 := hmc363_not_adj_double v hij
      have h13 : ¬ (simple_graph_hypercube n).Adj (hmc363_flip v i) (hmc363_flip v j) := by
        have := hmc363_not_adj_double (hmc363_flip v i) hij
        rwa [hmc363_flip_flip] at this
      have h10 := h01.symm
      have h21 := h12.symm
      have h32 := h23.symm
      have h03 := h30.symm
      have h20 : ¬ (simple_graph_hypercube n).Adj _ _ := fun h => h02 h.symm
      have h31 : ¬ (simple_graph_hypercube n).Adj _ _ := fun h => h13 h.symm
      fin_cases a <;> fin_cases b <;>
        simp [hmc363_pt, SimpleGraph.cycleGraph_adj', h01, h12, h23, h30, h02, h13, h10, h21, h32, h03, h20, h31] <;> decide
  11. Assume for contradiction that there are no squares disjoint from S

    We assume the negation of the goal, namely that the count of disjoint squares is not strictly positive.

    line 124

      by_contra hF
  12. There exists a vertex x not in S with no neighbors in S

    Since the degree count y_0 is strictly positive, there exists at least one vertex x outside S whose hypercube neighborhood is completely disjoint from S.

    lines 125–133

    uses Finset.card_pos, Finset.mem_filter, Finset.mem_sdiff, Finset.card_eq_zero, Finset.eq_empty_iff_forall_notMem

      unfold hypercube_degree_count at hy0
      obtain ⟨x, hx⟩ := Finset.card_pos.mp hy0
      rw [Finset.mem_filter, Finset.mem_sdiff] at hx
      have hxS : x ∉ S := hx.1.2
      have hN : ∀ y, (simple_graph_hypercube n).Adj x y → y ∉ S := by
        intro y hy hyS
        have h0 := Finset.card_eq_zero.mp hx.2
        rw [Finset.eq_empty_iff_forall_notMem] at h0
        exact h0 y (by simp [hy, hyS])
  13. For any two distinct coordinates i and j, flipping both coordinates of x gives a vertex in S

    If flipping coordinates i and j gave a vertex outside S, then the four vertices x, flip(x, i), flip(flip(x, i), j), and flip(x, j) would form an induced 4-cycle in Q_n disjoint from S (since x has no neighbors in S and the double flip is assumed outside S), contradicting the assumption that no such squares exist.

    lines 134–165

    uses Function.Injective, congrFun, Ne.symm, Function.update_apply, Finset.card_pos, Finset.mem_filter, Finset.mem_powerset, Finset.subset_univ, true_and, Finset.card_image_of_injective, Equiv.ofBijective, congrArg, Subtype.val, Finset.coe_image, Finset.coe_univ, Set.image_univ, Set.mem_range, hmc363_pt_adj_iff, Finset.disjoint_left, Finset.mem_image, hmc363_adj_flip

      have step2 : ∀ i j : Fin n, i ≠ j → hmc363_flip (hmc363_flip x i) j ∈ S := by
        intro i j hij
        by_contra hnot
        apply hF
        have hinj : Function.Injective (hmc363_pt x i j) := by
          intro a b hab
          have hi := congrFun hab i
          have hj := congrFun hab j
          fin_cases a <;> fin_cases b <;>
            simp [hmc363_pt, hmc363_flip, Function.update_apply, hij, Ne.symm hij] at hi hj ⊢
        unfold hypercube_disjoint_squares_count
        apply Finset.card_pos.mpr
        refine ⟨Finset.univ.image (hmc363_pt x i j), ?_⟩
        simp only [Finset.mem_filter, Finset.mem_powerset, Finset.subset_univ, true_and]
        refine ⟨⟨?_, ?_⟩, ?_⟩
        · rw [Finset.card_image_of_injective _ hinj]; simp
        · let e : Fin 4 ≃ ↥((Finset.univ.image (hmc363_pt x i j) : Finset _) : Set (Fin n → Bool)) :=
            Equiv.ofBijective (fun k => ⟨hmc363_pt x i j k, by simp⟩)
              ⟨fun a b hab => hinj (congrArg Subtype.val hab), fun ⟨y, hy⟩ => by
                simp only [Finset.coe_image, Finset.coe_univ, Set.image_univ, Set.mem_range] at hy
                obtain ⟨k, rfl⟩ := hy
                exact ⟨k, rfl⟩⟩
          exact ⟨(⟨e, fun {a b} => hmc363_pt_adj_iff x hij a b⟩ :
            SimpleGraph.cycleGraph 4 ≃g (simple_graph_hypercube n).induce _).symm⟩
        · rw [Finset.disjoint_left]
          intro a ha
          obtain ⟨k, -, rfl⟩ := Finset.mem_image.mp ha
          fin_cases k
          · exact hxS
          · exact hN _ (hmc363_adj_flip x i)
          · exact hnot
          · exact hN _ (hmc363_adj_flip x j)
  14. A neighbor z of the double flip along coordinates 0 and 1 in S must differ in a third coordinate k distinct from 0 and 1

    Since n ≥ 13, coordinates 0 and 1 are distinct. The double flip y at 0 and 1 lies in S, and since S is a coil, y has a neighbor z in S, which must be obtained by flipping some coordinate k of y. If k were 0 or 1, z would be a single flip of x, which cannot belong to S because x has no neighbors in S. Hence k is distinct from both 0 and 1.

    lines 166–178

    uses hmc363_coil_nbrs, hmc363_eq_flip_of_adj, hmc363_adj_flip, hmc363_flip_comm, hmc363_flip_flip

      have hi0 : (⟨0, by omega⟩ : Fin n) ≠ ⟨1, by omega⟩ := by simp
      set i : Fin n := ⟨0, by omega⟩
      set j : Fin n := ⟨1, by omega⟩
      obtain ⟨z, hzS, hyz⟩ := (hmc363_coil_nbrs hS.1 (step2 i j hi0)).1
      obtain ⟨k, rfl⟩ := hmc363_eq_flip_of_adj hyz
      have hki : k ≠ i := by
        rintro rfl
        apply hN _ (hmc363_adj_flip x j)
        rwa [hmc363_flip_comm (hmc363_flip x i) j i, hmc363_flip_flip] at hzS
      have hkj : k ≠ j := by
        rintro rfl
        apply hN _ (hmc363_adj_flip x i)
        rwa [hmc363_flip_flip] at hzS
  15. The vertex z has three distinct neighbors in S, contradicting that S is a cycle

    The vertex z = flip(flip(flip(x, 0), 1), k) has three neighbors obtained by flipping k, 0, or 1, which evaluate to the double flips at {0, 1}, {1, k}, and {0, k}. By the double-flip property, all three neighbors lie in S. However, every vertex in a coil has at most two neighbors in S, so two of these three neighbors must coincide. But since 0, 1, and k are pairwise distinct, flipping different coordinates produces distinct vertices, giving a contradiction in all three cases.

    lines 179–192

    uses hmc363_flip_flip, hmc363_flip_comm, Ne.symm, hmc363_coil_nbrs, hmc363_adj_flip, hmc363_flip_ne

      set z := hmc363_flip (hmc363_flip (hmc363_flip x i) j) k with hz
      have ha : hmc363_flip z k ∈ S := by rw [hz, hmc363_flip_flip]; exact step2 i j hi0
      have hb : hmc363_flip z i ∈ S := by
        rw [hz, hmc363_flip_comm (hmc363_flip (hmc363_flip x i) j) k i,
          hmc363_flip_comm (hmc363_flip x i) j i, hmc363_flip_flip]
        exact step2 j k (Ne.symm hkj)
      have hc : hmc363_flip z j ∈ S := by
        rw [hz, hmc363_flip_comm (hmc363_flip (hmc363_flip x i) j) k j, hmc363_flip_flip]
        exact step2 i k (Ne.symm hki)
      rcases (hmc363_coil_nbrs hS.1 hzS).2 _ _ _ ha hb hc (hmc363_adj_flip z k) (hmc363_adj_flip z i)
          (hmc363_adj_flip z j) with h | h | h
      · exact hmc363_flip_ne z hki h
      · exact hmc363_flip_ne z hkj h
      · exact hmc363_flip_ne z hi0 h
Function.update_apply
Evaluation of Function.update f a' b at a equals b if a = a' and f(a) otherwise
Ne.symm
Inequality is symmetric: if a ≠ b then b ≠ a
SimpleGraph.fromRel_adj
Two vertices v and w are adjacent in SimpleGraph.fromRel r iff v ≠ w and either r v w or r w v holds
Or.inl
A disjunction a ∨ b holds if its left disjunct a holds
hmc363_adj_iff
Two vertices in the hypercube Q_n are adjacent if and only if they are distinct and differ in exactly one coordinate
congrFun
Equal functions take equal values at any argument
Function.update_self
Updating a function at argument a with value v and then evaluating at a yields v
if_false
An if-then-else whose condition is False simplifies to the else branch
SimpleGraph.cycleGraph_neighborSet
The neighbor set of a vertex v in the cycle graph C_{n+2} consists of v - 1 and v + 1
RelIso.apply_symm_apply
Applying a relational isomorphism to the image of an element under its inverse yields the element
SimpleGraph.cycleGraph_adj
Two vertices u and v are adjacent in the cycle graph C_{n+2} iff u - v = 1 or v - u = 1
Or.inr
A disjunction a ∨ b holds if its right disjunct b holds
hmc363_cycle_nbrs
Every vertex in a cycle graph of length at least 3 has a neighbor, and any three neighbors must contain a duplicate
congrArg
A function applied to equal arguments yields equal results
Subtype.val
The projection from a subtype element to its underlying value
hmc363_adj_flip
A vertex in Q_n is adjacent to the vertex obtained by flipping any single coordinate
hmc363_flip_comm
Flipping coordinate i then coordinate j gives the same vertex as flipping j then i
hmc363_not_adj_double
Flipping two distinct coordinates of a vertex produces a vertex not adjacent to the original vertex
hmc363_flip_flip
Flipping the same coordinate twice returns the original vertex
Finset.card_pos
A finite set has positive cardinality if and only if it is nonempty
Finset.mem_filter
An element belongs to a filtered finset iff it belongs to the base set and satisfies the predicate
Finset.mem_sdiff
An element belongs to the difference s \\ t iff it belongs to s and does not belong to t
Finset.card_eq_zero
A finite set has cardinality zero if and only if it is empty
Finset.eq_empty_iff_forall_notMem
A finite set is empty if and only if none of its elements belong to it
Function.Injective
A function is injective if distinct arguments have distinct values
Finset.mem_powerset
A finset belongs to the powerset of s iff it is a subset of s
Finset.subset_univ
Every finset of elements of a finite type is a subset of the universal finset
true_and
The conjunction of True and p is equivalent to p
Finset.card_image_of_injective
The image of a finset under an injective map has the same cardinality as the finset
Equiv.ofBijective
A bijective function gives an equivalence (bijection) between types
Finset.coe_image
Coercing the image of a finset to a set equals the set image of the coerced finset
Finset.coe_univ
Coercing the universal finset to a set yields the universal set
Set.image_univ
The image of the universal set under a function is the range of the function
Set.mem_range
An element is in the range of f iff it equals f(k) for some k
hmc363_pt_adj_iff
The four vertices generated by flipping coordinates i and j form an induced 4-cycle in Q_n
Finset.disjoint_left
Two finsets are disjoint iff no element of the first belongs to the second
Finset.mem_image
An element is in the image of a finset under f iff it equals f(x) for some x in the finset
hmc363_coil_nbrs
Every vertex in a coil S has a neighbor in S and cannot have three pairwise distinct neighbors in S
hmc363_eq_flip_of_adj
If two vertices in Q_n are adjacent, one is obtained from the other by flipping a coordinate
hmc363_flip_ne
Flipping two distinct coordinates of a vertex yields two distinct vertices

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

def hmc363_flip {n : ℕ} (x : Fin n → Bool) (i : Fin n) : Fin n → Bool := Function.update x i (!x i)theorem hmc363_flip_flip {n : ℕ} (x : Fin n → Bool) (i : Fin n) : hmc363_flip (hmc363_flip x i) i = x := by  funext t; simp only [hmc363_flip, Function.update_apply]; split_ifs <;> simp_alltheorem hmc363_flip_comm {n : ℕ} (x : Fin n → Bool) (i j : Fin n) :    hmc363_flip (hmc363_flip x i) j = hmc363_flip (hmc363_flip x j) i := by  by_cases hij : i = j  · subst hij; rfl  funext t  simp only [hmc363_flip, Function.update_apply]  by_cases hti : t = i  · subst hti; simp [hij]  · by_cases htj : t = j    · subst htj; simp [hti, Ne.symm hij]    · simp [hti, htj]theorem hmc363_adj_iff {n : ℕ} (x y : Fin n → Bool) :    (simple_graph_hypercube n).Adj x y ↔ x ≠ y ∧ ∃! k, x k ≠ y k := by  unfold simple_graph_hypercube  rw [SimpleGraph.fromRel_adj]  constructor  · rintro ⟨hne, h | h⟩    · exact ⟨hne, h⟩    · obtain ⟨k, hk, hu⟩ := h      exact ⟨hne, k, fun e => hk e.symm, fun t ht => hu t (fun e => ht e.symm)⟩  · rintro ⟨hne, h⟩; exact ⟨hne, Or.inl h⟩theorem hmc363_adj_flip {n : ℕ} (x : Fin n → Bool) (i : Fin n) :    (simple_graph_hypercube n).Adj x (hmc363_flip x i) := by  rw [hmc363_adj_iff]  refine ⟨fun e => ?_, i, by simp [hmc363_flip], fun t ht => ?_⟩  · have := congrFun e i; simp [hmc363_flip] at this  · by_contra hti; exact ht (by simp [hmc363_flip, Function.update_apply, hti])theorem hmc363_not_adj_double {n : ℕ} (x : Fin n → Bool) {i j : Fin n} (hij : i ≠ j) :    ¬ (simple_graph_hypercube n).Adj x (hmc363_flip (hmc363_flip x i) j) := by  rw [hmc363_adj_iff]  rintro ⟨-, k, -, hu⟩  have hi := hu i (by simp [hmc363_flip, Function.update_apply, hij])  have hj := hu j (by simp [hmc363_flip, Function.update_apply, hij, Ne.symm hij])  exact hij (hi.trans hj.symm)theorem hmc363_eq_flip_of_adj {n : ℕ} {x y : Fin n → Bool} (h : (simple_graph_hypercube n).Adj x y) :    ∃ k, y = hmc363_flip x k := by  rw [hmc363_adj_iff] at h  obtain ⟨-, k, hk, hu⟩ := h  refine ⟨k, funext fun t => ?_⟩  by_cases htk : t = k  · subst htk; simp only [hmc363_flip, Function.update_self]    cases hx : x t <;> cases hy : y t <;> simp_all  · simp only [hmc363_flip, Function.update_apply, htk, if_false]    by_contra hne; exact htk (hu t (Ne.symm hne))/-- A vertex of a cycle has a neighbour, and no three distinct neighbours. -/theorem hmc363_cycle_nbrs {α : Type*} (H : SimpleGraph α) (m : ℕ) (f : H ≃g SimpleGraph.cycleGraph (m + 3))    (v : α) : (∃ w, H.Adj v w) ∧ ∀ a b c, H.Adj v a → H.Adj v b → H.Adj v c → a = b ∨ a = c ∨ b = c := by  have key : ∀ a, H.Adj v a → f a = f v - 1 ∨ f a = f v + 1 := by    intro a ha    have h' : (SimpleGraph.cycleGraph (m + 1 + 2)).Adj (f v) (f a) := f.map_adj_iff.mpr ha    have : f a ∈ (SimpleGraph.cycleGraph (m + 1 + 2)).neighborSet (f v) := h'    rw [SimpleGraph.cycleGraph_neighborSet] at this    simpa using this  refine ⟨⟨f.symm (f v + 1), ?_⟩, fun a b c ha hb hc => ?_⟩  · rw [← f.map_adj_iff, RelIso.apply_symm_apply]    show (SimpleGraph.cycleGraph (m + 1 + 2)).Adj _ _    rw [SimpleGraph.cycleGraph_adj]; right; simp  · rcases key a ha with h1 | h1 <;> rcases key b hb with h2 | h2 <;> rcases key c hc with h3 | h3    all_goals first      | exact Or.inl (f.injective (h1.trans h2.symm))      | exact Or.inr (Or.inl (f.injective (h1.trans h3.symm)))      | exact Or.inr (Or.inr (f.injective (h2.trans h3.symm)))theorem hmc363_coil_nbrs {n : ℕ} {S : Finset (Fin n → Bool)} (hcoil : hypercube_coil n S)    {x : Fin n → Bool} (hx : x ∈ S) :    (∃ y ∈ S, (simple_graph_hypercube n).Adj x y) ∧      ∀ a b c, a ∈ S → b ∈ S → c ∈ S → (simple_graph_hypercube n).Adj x a →        (simple_graph_hypercube n).Adj x b → (simple_graph_hypercube n).Adj x c → a = b ∨ a = c ∨ b = c := by  obtain ⟨h4, ⟨f⟩⟩ := hcoil  have hm : S.card = (S.card - 3) + 3 := by omega  rw [hm] at f  obtain ⟨⟨⟨y, hy⟩, hxy⟩, h2⟩ := hmc363_cycle_nbrs _ _ f ⟨x, hx⟩  refine ⟨⟨y, hy, hxy⟩, fun a b c ha hb hc hxa hxb hxc => ?_⟩  rcases h2 ⟨a, ha⟩ ⟨b, hb⟩ ⟨c, hc⟩ hxa hxb hxc with h | h | h  · exact Or.inl (congrArg Subtype.val h)  · exact Or.inr (Or.inl (congrArg Subtype.val h))  · exact Or.inr (Or.inr (congrArg Subtype.val h))theorem hmc363_flip_ne {n : ℕ} (z : Fin n → Bool) {p q : Fin n} (hpq : p ≠ q) :    hmc363_flip z p ≠ hmc363_flip z q := by  intro h  have := congrFun h p  simp [hmc363_flip, Function.update_apply, hpq] at thisdef hmc363_pt {n : ℕ} (v : Fin n → Bool) (i j : Fin n) : Fin 4 → (Fin n → Bool) :=  ![v, hmc363_flip v i, hmc363_flip (hmc363_flip v i) j, hmc363_flip v j]theorem hmc363_pt_adj_iff {n : ℕ} (v : Fin n → Bool) {i j : Fin n} (hij : i ≠ j) (a b : Fin 4) :    (simple_graph_hypercube n).Adj (hmc363_pt v i j a) (hmc363_pt v i j b) ↔      (SimpleGraph.cycleGraph 4).Adj a b := by  have h01 := hmc363_adj_flip v i  have h12 := hmc363_adj_flip (hmc363_flip v i) j  have h23 : (simple_graph_hypercube n).Adj (hmc363_flip (hmc363_flip v i) j) (hmc363_flip v j) := by    rw [hmc363_flip_comm]; exact (hmc363_adj_flip (hmc363_flip v j) i).symm  have h30 := (hmc363_adj_flip v j).symm  have h02 := hmc363_not_adj_double v hij  have h13 : ¬ (simple_graph_hypercube n).Adj (hmc363_flip v i) (hmc363_flip v j) := by    have := hmc363_not_adj_double (hmc363_flip v i) hij    rwa [hmc363_flip_flip] at this  have h10 := h01.symm  have h21 := h12.symm  have h32 := h23.symm  have h03 := h30.symm  have h20 : ¬ (simple_graph_hypercube n).Adj _ _ := fun h => h02 h.symm  have h31 : ¬ (simple_graph_hypercube n).Adj _ _ := fun h => h13 h.symm  fin_cases a <;> fin_cases b <;>    simp [hmc363_pt, SimpleGraph.cycleGraph_adj', h01, h12, h23, h30, h02, h13, h10, h21, h32, h03, h20, h31] <;> decideopen scoped Classical in/-- A maximum coil with y_0 > 0 has at least one disjoint square. -/theorem hypercube_max_coil_disjoint_squares_pos (n : ℕ) (hn : 13 ≤ n) (S : Finset (Fin n → Bool))    (hS : is_max_hypercube_coil n S) (hy0 : 0 < hypercube_degree_count n S 0) :    0 < hypercube_disjoint_squares_count n S := by  by_contra hF  unfold hypercube_degree_count at hy0  obtain ⟨x, hx⟩ := Finset.card_pos.mp hy0  rw [Finset.mem_filter, Finset.mem_sdiff] at hx  have hxS : x ∉ S := hx.1.2  have hN : ∀ y, (simple_graph_hypercube n).Adj x y → y ∉ S := by    intro y hy hyS    have h0 := Finset.card_eq_zero.mp hx.2    rw [Finset.eq_empty_iff_forall_notMem] at h0    exact h0 y (by simp [hy, hyS])  have step2 : ∀ i j : Fin n, i ≠ j → hmc363_flip (hmc363_flip x i) j ∈ S := by    intro i j hij    by_contra hnot    apply hF    have hinj : Function.Injective (hmc363_pt x i j) := by      intro a b hab      have hi := congrFun hab i      have hj := congrFun hab j      fin_cases a <;> fin_cases b <;>        simp [hmc363_pt, hmc363_flip, Function.update_apply, hij, Ne.symm hij] at hi hj ⊢    unfold hypercube_disjoint_squares_count    apply Finset.card_pos.mpr    refine ⟨Finset.univ.image (hmc363_pt x i j), ?_⟩    simp only [Finset.mem_filter, Finset.mem_powerset, Finset.subset_univ, true_and]    refine ⟨⟨?_, ?_⟩, ?_⟩    · rw [Finset.card_image_of_injective _ hinj]; simp    · let e : Fin 4 ≃ ↥((Finset.univ.image (hmc363_pt x i j) : Finset _) : Set (Fin n → Bool)) :=        Equiv.ofBijective (fun k => ⟨hmc363_pt x i j k, by simp⟩)          ⟨fun a b hab => hinj (congrArg Subtype.val hab), fun ⟨y, hy⟩ => by            simp only [Finset.coe_image, Finset.coe_univ, Set.image_univ, Set.mem_range] at hy            obtain ⟨k, rfl⟩ := hy            exact ⟨k, rfl⟩⟩      exact ⟨(⟨e, fun {a b} => hmc363_pt_adj_iff x hij a b⟩ :        SimpleGraph.cycleGraph 4 ≃g (simple_graph_hypercube n).induce _).symm⟩    · rw [Finset.disjoint_left]      intro a ha      obtain ⟨k, -, rfl⟩ := Finset.mem_image.mp ha      fin_cases k      · exact hxS      · exact hN _ (hmc363_adj_flip x i)      · exact hnot      · exact hN _ (hmc363_adj_flip x j)  have hi0 : (⟨0, by omega⟩ : Fin n) ≠ ⟨1, by omega⟩ := by simp  set i : Fin n := ⟨0, by omega⟩  set j : Fin n := ⟨1, by omega⟩  obtain ⟨z, hzS, hyz⟩ := (hmc363_coil_nbrs hS.1 (step2 i j hi0)).1  obtain ⟨k, rfl⟩ := hmc363_eq_flip_of_adj hyz  have hki : k ≠ i := by    rintro rfl    apply hN _ (hmc363_adj_flip x j)    rwa [hmc363_flip_comm (hmc363_flip x i) j i, hmc363_flip_flip] at hzS  have hkj : k ≠ j := by    rintro rfl    apply hN _ (hmc363_adj_flip x i)    rwa [hmc363_flip_flip] at hzS  set z := hmc363_flip (hmc363_flip (hmc363_flip x i) j) k with hz  have ha : hmc363_flip z k ∈ S := by rw [hz, hmc363_flip_flip]; exact step2 i j hi0  have hb : hmc363_flip z i ∈ S := by    rw [hz, hmc363_flip_comm (hmc363_flip (hmc363_flip x i) j) k i,      hmc363_flip_comm (hmc363_flip x i) j i, hmc363_flip_flip]    exact step2 j k (Ne.symm hkj)  have hc : hmc363_flip z j ∈ S := by    rw [hz, hmc363_flip_comm (hmc363_flip (hmc363_flip x i) j) k j, hmc363_flip_flip]    exact step2 i k (Ne.symm hki)  rcases (hmc363_coil_nbrs hS.1 hzS).2 _ _ _ ha hb hc (hmc363_adj_flip z k) (hmc363_adj_flip z i)      (hmc363_adj_flip z j) with h | h | h  · exact hmc363_flip_ne z hki h  · exact hmc363_flip_ne z hkj h  · exact hmc363_flip_ne z hi0 h
See it in the graphDiscuss this resultChallenge it