AFTD Auto-Formalizing Theoretical Domains

op_1400_counterexample_order_le_eighty

theoremverifiedformalization

Open Problem OP-1400: there exists a natural number n ≤ 80 and a simple graph G on Fin n with decidable adjacency whose zero forcing polynomial is not unimodal.

Statement

theorem op_1400_counterexample_order_le_eighty :
    ∃ (n : ℕ) (_ : n ≤ 80) (G : SimpleGraph (Fin n)) (_ : DecidableRel G.Adj),
      ¬ polynomial_is_unimodal (zero_forcing_poly G)
Formalizes
arXiv:2611.11352 Sec. 3, Question 2
Verified
11 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4
  • ZeroForcedThe zero forcing closure of an initial set S of blue vertices in G under the color change rule.
  • polynomial_is_unimodalA polynomial with natural coefficients is unimodal if its coefficient sequence is weakly increasing up to some index and weakly decreasing…
  • is_zero_forcing_setA set of vertices S is a zero forcing set of G if its zero forcing closure contains all vertices of G.
  • zero_forcing_polyGiven a finite type V and a simple graph G on V, zero_forcing_poly G is the polynomial in Polynomial ℕ defined as the sum over all subsets…

Read back from the Lean

There exists a natural number $n$ such that $n \le 80$, a simple graph $G$ with vertex set $\mathrm{Fin}(n)$, and a decidability instance for adjacency in $G$, such that the zero forcing polynomial of $G$ is not unimodal.

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 disprove Open Problem OP-1400 (which asked if all zero forcing polynomials are unimodal), an explicit 20-vertex graph G is constructed via a 400-bit adjacency integer. Two certified functions, Zf and Vf, compute verifiable lower and upper bounds on whether a vertex subset is a zero forcing set by simulating the forcing process. Evaluating these certificates by kernel computation shows that the 15th, 16th, and 17th coefficients of the zero forcing polynomial satisfy coeff 15 ≥ 932, coeff 16 ≤ 909, and coeff 17 ≥ 939. This dip at coefficient 16 violates unimodality, yielding a counterexample of order 20 ≤ 80.

  1. Bit testing on integers matches Nat.testBit.

    By unfolding tb and Nat.testBit, a case analysis on whether the masked bit equals 0 confirms that the boolean test agrees with testBit.

    lines 44–53

      unfold tb Nat.testBit
      cases h : Nat.beq (Nat.land 1 (Nat.shiftRight m i)) 0
      · have : Nat.land 1 (Nat.shiftRight m i) ≠ 0 := fun h' => by
          rw [h'] at h; exact absurd h (by decide)
        simp only [Bool.not_false]
        exact (bne_iff_ne.2 this).symm
      · have := Nat.eq_of_beq_eq_true h
        simp only [Bool.not_true]
        exact (bne_eq_false_iff_eq.2 this).symm
    
  2. The singleton predicate isS holds if and only if the input is a power of 2.

    Unfolding isS and inspecting whether s is zero shows that isS holds precisely when s equals 2^(log2 s). The converse holds by computing log2 (2^y) = y.

    lines 54–69

    theorem isS_spec {s : ℕ} (h : isS s = true) : ∃ x, s = 2 ^ x := by
      unfold isS at h
      cases h0 : Nat.beq s 0 <;> rw [h0] at h
      · exact ⟨Nat.log2 s, Nat.eq_of_beq_eq_true h⟩
      · simp at h
    
    theorem isS_two_pow (y : ℕ) : isS (2 ^ y) = true := by
      unfold isS
      have h1 : Nat.beq (2 ^ y) 0 = false := by
        cases h : Nat.beq (2 ^ y) 0
        · rfl
        · exact absurd (Nat.eq_of_beq_eq_true h) (by positivity)
      rw [h1]
      show Nat.beq (2 ^ y) (2 ^ Nat.log2 (2 ^ y)) = true
      rw [Nat.log2_two_pow]; exact Nat.beq_refl _
    
  3. Membership in the vertex list VL is equivalent to being less than 20. automation

    Expanding the list membership into a disjunction over 0 through 19 and applying linear integer arithmetic (omega) closes the equivalence.

    lines 70–72

    theorem mem_VL {v : ℕ} : v ∈ VL ↔ v < 20 := by
      simp only [VL, List.mem_cons, List.not_mem_nil, or_false]; omega
    
  4. The graph relation defined by adjOf on Fin 20 is symmetric, irreflexive, and supported on indices below 20. automation

    Symmetry and irreflexivity across all pairs in Fin 20 are verified by the kernel decision procedure. The adjacency bitmasks are bounded by 2^20 by modulo reduction, so bits at index 20 or higher are false.

    lines 73–81

    theorem adj_symm : ∀ u v : Fin 20, (adjOf u.val).testBit v.val = true →
        (adjOf v.val).testBit u.val = true := by decide +kernel
    theorem adj_irrefl : ∀ u : Fin 20, (adjOf u.val).testBit u.val = false := by decide +kernel
    
    theorem adjOf_lt (v : ℕ) : adjOf v < 2 ^ 20 := Nat.mod_lt _ (by norm_num)
    
    theorem testBit_adjOf_ge {v i : ℕ} (h : 20 ≤ i) : (adjOf v).testBit i = false :=
      Nat.testBit_lt_two_pow (lt_of_lt_of_le (adjOf_lt v) (Nat.pow_le_pow_right (by norm_num) h))
    
  5. Linear search on a vertex list correctly identifies a valid forcing vertex or establishes that none exists.

    Structural induction on the list of vertices shows that fsL returns some vertex x only when x is unforced and has a unique unforced neighbour, and returns none only when every vertex in the list fails one of these conditions. Specializing to VL yields fs0_some and fs0_none.

    lines 82–126

    theorem fsL_some (w : ℕ) : ∀ (l : List ℕ) {x : ℕ}, fsL w l = some x →
        x ∈ l ∧ w.testBit x = false ∧ isS (adjOf x &&& w) = true
      | [], x, h => by simp [fsL] at h
      | v :: l, x, h => by
        change cond (tb w v) (fsL w l) (cond (isS (Nat.land (adjOf v) w)) (some v) (fsL w l)) = some x at h
        cases h1 : tb w v
        · cases h2 : isS (Nat.land (adjOf v) w)
          · simp only [h1, h2, cond_false] at h
            obtain ⟨a, b, c⟩ := fsL_some w l h; exact ⟨List.mem_cons_of_mem _ a, b, c⟩
          · simp only [h1, h2, cond_false, cond_true, Option.some.injEq] at h; subst h
            exact ⟨List.mem_cons_self, by rw [← tb_eq]; exact h1, h2⟩
        · simp only [h1, cond_true] at h
          obtain ⟨a, b, c⟩ := fsL_some w l h; exact ⟨List.mem_cons_of_mem _ a, b, c⟩
    
    theorem fsL_none (w : ℕ) : ∀ (l : List ℕ), fsL w l = none →
        ∀ v ∈ l, w.testBit v = true ∨ isS (adjOf v &&& w) = false
      | [], _, v, hv => by simp at hv
      | u :: l, h, v, hv => by
        change cond (tb w u) (fsL w l) (cond (isS (Nat.land (adjOf u) w)) (some u) (fsL w l)) = none at h
        have hl : fsL w l = none := by
          cases h1 : tb w u
          · cases h2 : isS (Nat.land (adjOf u) w)
            · simpa only [h1, h2, cond_false] using h
            · simp only [h1, h2, cond_false, cond_true] at h; exact absurd h (by simp)
          · simpa only [h1, cond_true] using h
        rcases List.mem_cons.1 hv with rfl | hv
        · cases h1 : tb w v
          · cases h2 : isS (Nat.land (adjOf v) w)
            · exact Or.inr (by first | rfl | exact h2)
            · simp only [h1, h2, cond_false, cond_true] at h; exact absurd h (by simp)
          · left; rw [← tb_eq]; exact h1
        · exact fsL_none w l hl v hv
    
    theorem fs0_some {w v : ℕ} (h : fs0 w = some v) :
        v < 20 ∧ w.testBit v = false ∧ ∃ x, adjOf v &&& w = 2 ^ x := by
      obtain ⟨a, b, c⟩ := fsL_some w VL h
      exact ⟨mem_VL.1 a, b, isS_spec c⟩
    
    theorem fs0_none {w : ℕ} (h : fs0 w = none) (v : ℕ) (hv : v < 20) (hb : w.testBit v = false)
        (y : ℕ) : adjOf v &&& w ≠ 2 ^ y := by
      intro he
      rcases fsL_none w VL h v (mem_VL.2 hv) with h1 | h1
      · rw [hb] at h1; exact absurd h1 (by simp)
      · rw [he, isS_two_pow] at h1; exact absurd h1 (by simp)
    
  6. The adjacency table integer is bounded by 2^400 and vanishes for vertices at index 20 or above. automation

    Kernel evaluation shows AT < 2^400. Shifting AT right by 20 * y for y ≥ 20 results in 0, so adjOf y = 0.

    lines 127–137

    theorem AT_lt : AT < 2 ^ 400 := by decide +kernel
    
    theorem adjOf_ge {y : ℕ} (hy : 20 ≤ y) : adjOf y = 0 := by
      unfold adjOf
      have : Nat.shiftRight AT (Nat.mul 20 y) = 0 := by
        show AT >>> (20 * y) = 0
        rw [Nat.shiftRight_eq_div_pow]
        apply Nat.div_eq_of_lt
        exact lt_of_lt_of_le AT_lt (Nat.pow_le_pow_right (by norm_num) (by omega))
      rw [this]
    
  7. The loop invariant Inv is preserved throughout the fast search loop uLoop.

    The loop invariant tracks the union of white neighbourhoods and vertices with multiple white neighbours. Induction on the step count f and analyzing the bitwise updates shows Inv is preserved from the initial state where all white vertices are unprocessed.

    lines 138–208

    def Inv (w rem u1 u2 : ℕ) : Prop :=
      (∀ i, rem.testBit i = true → w.testBit i = true) ∧
      (∀ y v, w.testBit y = true → rem.testBit y = false → (adjOf y).testBit v = true →
        u1.testBit v = true) ∧
      (∀ v, u1.testBit v = true →
        ∃ y, w.testBit y = true ∧ rem.testBit y = false ∧ (adjOf y).testBit v = true) ∧
      (∀ v, u2.testBit v = true → ∃ y1 y2, y1 ≠ y2 ∧ w.testBit y1 = true ∧ w.testBit y2 = true ∧
        (adjOf y1).testBit v = true ∧ (adjOf y2).testBit v = true)
    
    theorem uLoop_succ (f rem u1 u2 : ℕ) : uLoop (f + 1) rem u1 u2 =
        cond (Nat.beq rem 0) (u1, u2, rem)
          (uLoop f (rem ^^^ 2 ^ Nat.log2 rem) (u1 ||| adjOf (Nat.log2 rem))
            (u2 ||| (u1 &&& adjOf (Nat.log2 rem)))) := rfl
    
    theorem inv_step {w rem u1 u2 : ℕ} (hrem : rem ≠ 0) (h : Inv w rem u1 u2) :
        Inv w (rem ^^^ 2 ^ Nat.log2 rem) (u1 ||| adjOf (Nat.log2 rem))
          (u2 ||| (u1 &&& adjOf (Nat.log2 rem))) := by
      obtain ⟨h1, h2, h3, h4⟩ := h
      have hy0 : rem.testBit (Nat.log2 rem) = true := Nat.testBit_log2 hrem
      have hr : ∀ i, (rem ^^^ 2 ^ Nat.log2 rem).testBit i = (rem.testBit i ^^ decide (Nat.log2 rem = i)) := by
        intro i; rw [Nat.testBit_xor, Nat.testBit_two_pow]
      refine ⟨?_, ?_, ?_, ?_⟩
      · intro i hi
        rw [hr] at hi
        by_cases hiy : Nat.log2 rem = i
        · subst hiy; simp [hy0] at hi
        · simp [hiy] at hi; exact h1 i hi
      · intro y v hw hry ha
        rw [Nat.testBit_or]
        by_cases hyy : Nat.log2 rem = y
        · subst hyy; simp [ha]
        · rw [hr] at hry; simp [hyy] at hry
          simp [h2 y v hw hry ha]
      · intro v hv
        rw [Nat.testBit_or] at hv
        cases hu : u1.testBit v
        · rw [hu] at hv
          simp only [Bool.false_or] at hv
          refine ⟨Nat.log2 rem, h1 _ hy0, ?_, hv⟩
          rw [hr]; simp [hy0]
        · obtain ⟨y, hwy, hry, hay⟩ := h3 v hu
          refine ⟨y, hwy, ?_, hay⟩
          rw [hr]
          have : Nat.log2 rem ≠ y := fun e => by rw [e] at hy0; rw [hy0] at hry; exact absurd hry (by simp)
          simp [this, hry]
      · intro v hv
        rw [Nat.testBit_or, Nat.testBit_and] at hv
        cases hu2 : u2.testBit v
        · rw [hu2] at hv
          simp only [Bool.false_or, Bool.and_eq_true] at hv
          obtain ⟨y, hwy, hry, hay⟩ := h3 v hv.1
          have : y ≠ Nat.log2 rem := fun e => by rw [← e] at hy0; rw [hy0] at hry; exact absurd hry (by simp)
          exact ⟨y, Nat.log2 rem, this, hwy, h1 _ hy0, hay, hv.2⟩
        · exact h4 v hu2
    
    theorem uLoop_inv (w : ℕ) : ∀ f rem u1 u2, Inv w rem u1 u2 →
        Inv w (uLoop f rem u1 u2).2.2 (uLoop f rem u1 u2).1 (uLoop f rem u1 u2).2.1
      | 0, rem, u1, u2, h => h
      | f + 1, rem, u1, u2, h => by
        rw [uLoop_succ]
        cases h0 : Nat.beq rem 0
        · simp only [cond_false]
          exact uLoop_inv w f _ _ _ (inv_step (Nat.ne_of_beq_eq_false h0) h)
        · simpa only [cond_true] using h
    
    theorem inv_init (w : ℕ) : Inv w w 0 0 := by
      refine ⟨fun i h => h, ?_, ?_, ?_⟩
      · intro y v hw hr; rw [hw] at hr; exact absurd hr (by simp)
      · intro v hv; simp at hv
      · intro v hv; simp at hv
    
  8. Fast stall detection correctly identifies when no forcing step is possible.

    If uLoop processes all white vertices and finds no candidate vertex with exactly one white neighbour, the loop invariant implies that any hypothetical forcing vertex would have two distinct witnesses in the neighborhood, contradicting uniqueness.

    lines 209–244

    theorem fast_stall {w : ℕ} (hrem : (uLoop 6 w 0 0).2.2 = 0) (hE : eSet w = 0) (v : ℕ) (hv : v < 20)
        (hb : w.testBit v = false) (x : ℕ) : adjOf v &&& w ≠ 2 ^ x := by
      intro hs
      have hI := uLoop_inv w 6 w 0 0 (inv_init w)
      rw [hrem] at hI
      obtain ⟨_, h2, _, h4⟩ := hI
      have hbit : ∀ i, (adjOf v &&& w).testBit i = decide (x = i) := by
        intro i; rw [hs, Nat.testBit_two_pow]
      have hx := hbit x
      simp only [Nat.testBit_and, decide_true, Bool.and_eq_true] at hx
      have hx20 : x < 20 := by
        by_contra hc; rw [testBit_adjOf_ge (by omega)] at hx; exact absurd hx.1 (by simp)
      have hxv : (adjOf x).testBit v = true := adj_symm ⟨v, hv⟩ ⟨x, hx20⟩ hx.1
      have hu1 := h2 x v hx.2 (by simp) hxv
      have hEv : (eSet w).testBit v = false := by rw [hE]; simp
      unfold eSet at hEv
      simp only [show ∀ a b : ℕ, Nat.xor a b = a ^^^ b from fun _ _ => rfl,
        show ∀ a b : ℕ, Nat.land a b = a &&& b from fun _ _ => rfl,
        show ∀ a b : ℕ, Nat.lor a b = a ||| b from fun _ _ => rfl,
        Nat.testBit_xor, Nat.testBit_and, Nat.testBit_or, hu1, hb] at hEv
      have hu2 : (uLoop 6 w 0 0).2.1.testBit v = true := by
        cases h : (uLoop 6 w 0 0).2.1.testBit v
        · rw [h] at hEv; simp at hEv
        · rfl
      obtain ⟨y1, y2, hne, hw1, hw2, ha1, ha2⟩ := h4 v hu2
      have hy1 : y1 < 20 := by
        by_contra hc; rw [adjOf_ge (by omega)] at ha1; simp at ha1
      have hy2 : y2 < 20 := by
        by_contra hc; rw [adjOf_ge (by omega)] at ha2; simp at ha2
      have e1 := hbit y1
      have e2 := hbit y2
      rw [Nat.testBit_and, adj_symm ⟨y1, hy1⟩ ⟨v, hv⟩ ha1, hw1] at e1
      rw [Nat.testBit_and, adj_symm ⟨y2, hy2⟩ ⟨v, hv⟩ ha2, hw2] at e2
      simp only [Bool.and_self, Bool.true_eq, decide_eq_true_eq] at e1 e2
      exact hne (e1.symm.trans e2)
    
  9. The accelerated forcing function fs is sound and complete for detecting forcing steps.

    Case analysis on the fast search check shows that fs returns some vertex only when it is a valid forcing vertex, and returns none only when neither the fast check nor the fallback linear search finds a forcing step.

    lines 245–277

    theorem forceStep_some {w v : ℕ} (h : fs w = some v) :
        v < 20 ∧ w.testBit v = false ∧ ∃ x, adjOf v &&& w = 2 ^ x := by
      unfold fs at h
      cases h0 : Nat.beq w 0
      · cases hr : Nat.beq (uLoop 6 w 0 0).2.2 0
        · simp only [h0, hr, cond_false] at h; exact fs0_some h
        · cases h1 : Nat.beq (eSet w) 0
          · cases h2 : chk w (Nat.log2 (eSet w))
            · simp only [h0, hr, h1, h2, cond_false, cond_true] at h; exact fs0_some h
            · simp only [h0, hr, h1, h2, cond_false, cond_true, Option.some.injEq] at h
              subst h
              simp only [chk, Bool.and_eq_true, Bool.not_eq_true'] at h2
              obtain ⟨ha, hb, hc⟩ := h2
              exact ⟨Nat.le_of_ble_eq_true ha, by rw [← tb_eq]; exact hb, isS_spec hc⟩
          · simp only [h0, hr, h1, cond_false, cond_true] at h; exact absurd h (by simp)
      · simp only [h0, cond_true] at h; exact absurd h (by simp)
    
    theorem forceStep_none {w : ℕ} (h : fs w = none) (v : ℕ) (hv : v < 20) (hb : w.testBit v = false)
        (y : ℕ) : adjOf v &&& w ≠ 2 ^ y := by
      unfold fs at h
      cases h0 : Nat.beq w 0
      · cases hr : Nat.beq (uLoop 6 w 0 0).2.2 0
        · apply fs0_none _ v hv hb y
          simpa only [h0, hr, cond_false] using h
        · cases h1 : Nat.beq (eSet w) 0
          · apply fs0_none _ v hv hb y
            cases h2 : chk w (Nat.log2 (eSet w))
            · simpa only [h0, hr, h1, h2, cond_false, cond_true] using h
            · simp only [h0, hr, h1, h2, cond_false, cond_true] at h; exact absurd h (by simp)
          · exact fast_stall (Nat.eq_of_beq_eq_true hr) (Nat.eq_of_beq_eq_true h1) v hv hb y
      · rw [Nat.eq_of_beq_eq_true h0, Nat.and_zero]
        exact (Nat.two_pow_pos y).ne
    
  10. The relation on Fin 20 defines a simple graph G with decidable adjacency.

    The simple graph G is defined from the relation given by adjOf, and symmetry and irreflexivity establish that G.Adj u v holds exactly when bit v of adjOf u is set.

    lines 278–293

    theorem run_succ (f w : ℕ) : run (f + 1) w = Option.rec w (fun v => run f (w ^^^ (adjOf v &&& w))) (fs w) := rfl
    
    def G : SimpleGraph (Fin 20) := SimpleGraph.fromRel (fun u v => (adjOf u.val).testBit v.val = true)
    
    theorem adj_iff {u v : Fin 20} : G.Adj u v ↔ (adjOf u.val).testBit v.val = true := by
      simp only [G, SimpleGraph.fromRel_adj]
      constructor
      · rintro ⟨_, h | h⟩
        · exact h
        · exact adj_symm _ _ h
      · intro h
        refine ⟨?_, Or.inl h⟩
        rintro rfl; rw [adj_irrefl] at h; exact absurd h (by simp)
    
    instance : DecidableRel G.Adj := fun _ _ => decidable_of_iff _ adj_iff.symm
    
  11. The simulation run is sound with respect to the mathematical zero forcing process.

    Induction on the number of simulation steps shows that run only clears white bits, and any vertex forced to blue corresponds to a valid ZeroForced step in G from the initial set S.

    lines 294–338

    theorem run_sub : ∀ f w i, (run f w).testBit i = true → w.testBit i = true
      | 0, w, i, h => h
      | f + 1, w, i, h => by
        rw [run_succ] at h
        cases hx : fs w with
        | none => rw [hx] at h; exact h
        | some x =>
          rw [hx] at h
          have := run_sub f _ i h
          simp [Nat.testBit_xor, Nat.testBit_and] at this
          by_cases hw : w.testBit i <;> simp_all
    
    theorem run_sound (S : Set (Fin 20)) : ∀ f w, (∀ v : Fin 20, w.testBit v.val = false → ZeroForced G S v) →
        ∀ v : Fin 20, (run f w).testBit v.val = false → ZeroForced G S v
      | 0, w, hw => hw
      | f + 1, w, hw => by
        rw [run_succ]
        cases hu : fs w with
        | none => exact hw
        | some u =>
          obtain ⟨hu24, hub, x, hsx⟩ := forceStep_some hu
          apply run_sound S f
          have hbit : ∀ i, ((adjOf u &&& w).testBit i = true ↔ i = x) := by
            intro i; rw [hsx, Nat.testBit_two_pow]; simp [eq_comm]
          have hxa : (adjOf u).testBit x = true := by
            have := (hbit x).2 rfl; simp [Nat.testBit_and] at this; exact this.1
          have hx24 : x < 20 := by
            by_contra hc; rw [testBit_adjOf_ge (by omega)] at hxa; exact absurd hxa (by simp)
          have hfu : ZeroForced G S ⟨u, hu24⟩ := hw ⟨u, hu24⟩ hub
          intro v hv
          by_cases hvw : w.testBit v.val = true
          · have hva : (adjOf u).testBit v.val = true := by
              simp [Nat.testBit_xor, Nat.testBit_and, hvw] at hv; exact hv
            have hvx : v.val = x := (hbit v.val).1 (by simp [Nat.testBit_and, hva, hvw])
            have : v = ⟨x, hx24⟩ := Fin.ext hvx
            subst this
            refine ZeroForced.step _ _ hfu (adj_iff.2 hxa) ?_
            intro y hy hyx
            apply hw
            by_contra hyw
            simp only [Bool.not_eq_false] at hyw
            have := (hbit y.val).1 (by simp [Nat.testBit_and, hyw]; exact adj_iff.1 hy)
            exact hyx (Fin.ext this)
          · exact hw v (by simpa using hvw)
    
  12. A stall in the simulation certifies that no further vertices can be zero forced.

    Induction on the derivation of ZeroForced shows that if fs stalls with none, any vertex forced from S must already have been blue in the state r.

    lines 339–363

    theorem stall_not_forced (S : Set (Fin 20)) (r : ℕ) (hr : fs r = none)
        (hS : ∀ v ∈ S, r.testBit v.val = false) : ∀ y, ZeroForced G S y → r.testBit y.val = false := by
      intro y hy
      induction hy with
      | init v hv => exact hS v hv
      | step u y hu huy hall ihu ihall =>
        by_contra hry
        simp only [Bool.not_eq_false] at hry
        have hs : adjOf u.val &&& r = 2 ^ y.val := by
          apply Nat.eq_of_testBit_eq
          intro i
          rw [Nat.testBit_two_pow, Nat.testBit_and]
          by_cases hi : i < 20
          · by_cases hiy : i = y.val
            · subst hiy; simp [hry]; exact adj_iff.1 huy
            · have : (adjOf u.val).testBit i = true → r.testBit i = false := fun ha =>
                ihall ⟨i, hi⟩ (adj_iff.2 ha) (fun h => hiy (by rw [← h]))
              have hne : decide (y.val = i) = false := by simp; omega
              rw [hne]
              cases ha : (adjOf u.val).testBit i
              · simp
              · simp [this ha]
          · rw [testBit_adjOf_ge (by omega)]; simp; omega
        exact forceStep_none hr u.val u.isLt ihu y.val hs
    
  13. Bitmasks faithfully represent subsets, and cntN computes subset sums.

    Induction on finite sets confirms that msk correctly sets bits for members, and induction on n and k shows that cntN evaluates the sum of f over all k-element subsets of range n.

    lines 364–406

    def msk (s : Finset ℕ) : ℕ := s.fold (· ||| ·) 0 (fun i => 2 ^ i)
    
    theorem testBit_msk (s : Finset ℕ) (i : ℕ) : (msk s).testBit i = decide (i ∈ s) := by
      induction s using Finset.induction_on with
      | empty => simp [msk]
      | insert a s ha ih =>
        unfold msk at *
        rw [Finset.fold_insert ha, Nat.testBit_or, ih, Nat.testBit_two_pow]
        by_cases h : i = a <;> simp [h, eq_comm]
    
    theorem cntN_eq (f : ℕ → ℕ) : ∀ n k acc,
        cntN f n k acc = ∑ s ∈ (Finset.range n).powersetCard k, f (acc ||| msk s)
      | n, 0, acc => by simp [cntN, msk]
      | 0, k + 1, acc => by
        rw [Finset.range_zero, Finset.powersetCard_eq_empty.2 (by simp)]; rfl
      | n + 1, k + 1, acc => by
        rw [cntN, cntN_eq f n (k + 1) acc, cntN_eq f n k (acc ||| 2 ^ n), Finset.range_add_one,
          Finset.powersetCard_succ_insert Finset.notMem_range_self, Finset.sum_union, Finset.sum_image]
        · congr 1
          apply Finset.sum_congr rfl
          intro s hs
          have hn : n ∉ s := fun h => by
            have := (Finset.mem_powersetCard.1 hs).1 h; simp at this
          unfold msk
          rw [Finset.fold_insert hn]
          simp [Nat.or_assoc]
        · intro s hs t ht hst
          have hns : n ∉ s := fun h => by have := (Finset.mem_powersetCard.1 hs).1 h; simp at this
          have hnt : n ∉ t := fun h => by have := (Finset.mem_powersetCard.1 ht).1 h; simp at this
          have := congrArg (fun u => u.erase n) hst
          simpa [Finset.erase_insert hns, Finset.erase_insert hnt] using this
        · rw [Finset.disjoint_left]
          intro s hs hs'
          obtain ⟨t, ht, rfl⟩ := Finset.mem_image.1 hs'
          have := (Finset.mem_powersetCard.1 hs).1 (Finset.mem_insert_self n t)
          simp at this
    
    theorem cntN_top (f : ℕ → ℕ) : ∀ n k acc,
        cntN f n (k + 1) acc = ∑ m ∈ Finset.range n, cntN f m k (acc ||| 2 ^ m)
      | 0, k, acc => by simp [cntN]
      | n + 1, k, acc => by
        rw [cntN, cntN_top f n k acc, Finset.sum_range_succ]
    
  14. The zero forcing polynomial coefficients equal sums over complement subsets of white vertices.

    A zero forcing set S of size j corresponds bijectively via complementation to a (20 - j)-element subset of white vertices. The coefficient of X^j in the zero forcing polynomial is therefore the sum of forcing indicators over (20 - j)-subsets.

    lines 407–455

    open scoped Classical in
    theorem coeff_zfp (j : ℕ) : (zero_forcing_poly G).coeff j =
        (Finset.univ.filter (fun S : Finset (Fin 20) => S.card = j ∧ is_zero_forcing_set G (S : Set (Fin 20)))).card := by
      unfold zero_forcing_poly
      rw [Polynomial.finsetSum_coeff, Finset.card_filter]
      apply Finset.sum_congr rfl
      intro S _
      by_cases h : is_zero_forcing_set G (S : Set (Fin 20))
      · by_cases hj : S.card = j
        · simp [h, hj, Polynomial.coeff_X_pow]
        · simp [h, hj, Polynomial.coeff_X_pow, Ne.symm hj]
      · simp [h]
    
    /-- decode a subset of range 20 -/
    def dec (s : Finset ℕ) : Finset (Fin 20) := Finset.univ.filter (fun v : Fin 20 => v.val ∈ s)
    
    theorem map_dec {s : Finset ℕ} (hs : s ⊆ Finset.range 20) : (dec s).map Fin.valEmbedding = s := by
      ext x; simp only [dec, Finset.mem_map, Finset.mem_filter, Finset.mem_univ, true_and,
        Fin.valEmbedding_apply]
      constructor
      · rintro ⟨a, ha, rfl⟩; exact ha
      · intro hx; exact ⟨⟨x, by simpa using hs hx⟩, hx, rfl⟩
    
    open scoped Classical in
    /-- the j-th coefficient as a sum over the (20 - j)-subsets of range 20 of white vertices -/
    theorem coeff_sum (j : ℕ) (hj : j ≤ 20) : (zero_forcing_poly G).coeff j =
        ∑ s ∈ (Finset.range 20).powersetCard (20 - j),
          if is_zero_forcing_set G (((dec s)ᶜ : Finset (Fin 20)) : Set (Fin 20)) then 1 else 0 := by
      rw [coeff_zfp, ← Finset.card_filter]
      apply Finset.card_nbij' (fun S => Sᶜ.map Fin.valEmbedding) (fun s => (dec s)ᶜ)
      · intro S hS
        simp only [Finset.coe_filter, Finset.mem_univ, true_and, Set.mem_ofPred_eq] at hS
        simp only [Finset.coe_filter, Finset.mem_powersetCard, Set.mem_ofPred_eq]
        have hsub : Sᶜ.map Fin.valEmbedding ⊆ Finset.range 20 := by
          intro x hx; simp at hx; obtain ⟨a, _, rfl⟩ := hx; simp
        refine ⟨⟨hsub, by rw [Finset.card_map, Finset.card_compl, hS.1]; simp⟩, ?_⟩
        have : (dec (Sᶜ.map Fin.valEmbedding))ᶜ = S := by ext v; simp [dec, Fin.val_inj]
        rw [this]; exact hS.2
      · intro s hs
        simp only [Finset.coe_filter, Finset.mem_powersetCard, Set.mem_ofPred_eq] at hs
        simp only [Finset.coe_filter, Finset.mem_univ, true_and, Set.mem_ofPred_eq]
        refine ⟨?_, hs.2⟩
        rw [Finset.card_compl, ← Finset.card_map Fin.valEmbedding, map_dec hs.1.1, hs.1.2]
        simp; omega
      · intro S _; ext v; simp [dec, Fin.val_inj]
      · intro s hs
        simp only [Finset.coe_filter, Finset.mem_powersetCard, Set.mem_ofPred_eq] at hs
        simp [map_dec hs.1.1]
    
  15. All 20 vertices are forced if and only if the state bitmask is 0 modulo 2^20.

    The bitmask modulo 2^20 masks out all bits above index 19; it vanishes if and only if all 20 low bits are false, indicating no white vertices remain.

    lines 456–475

    theorem testBit_msk_dec {s : Finset ℕ} (hs : s ⊆ Finset.range 20) (v : Fin 20) :
        (msk s).testBit v.val = decide (v ∉ (dec s)ᶜ) := by
      rw [testBit_msk]; simp [dec]
    
    theorem run_mod_zero {r : ℕ} (h : r % 1048576 = 0) (v : ℕ) (hv : v < 20) : r.testBit v = false := by
      have := congrArg (fun r => r.testBit v) h
      simp only [show (1048576 : ℕ) = 2 ^ 20 by norm_num, Nat.testBit_mod_two_pow, Nat.zero_testBit] at this
      simpa [hv] using this
    
    theorem run_mod_ne {r : ℕ} (h : r % 1048576 ≠ 0) : ∃ v < 20, r.testBit v = true := by
      by_contra hc
      push Not at hc
      apply h
      apply Nat.eq_of_testBit_eq
      intro i
      rw [show (1048576 : ℕ) = 2 ^ 20 by norm_num, Nat.testBit_mod_two_pow, Nat.zero_testBit]
      by_cases hi : i < 20
      · simp [hi, hc i hi]
      · simp [hi]
    
  16. Zf and Vf provide certified lower and upper bounds on zero forcing polynomial coefficients.

    If run reaches 0 mod 2^20, Zf outputs 1, certifying a forcing set. Conversely, any genuine zero forcing set cannot stall before completion, so Vf outputs at least 1. Summing via cntN yields lower and upper bounds for each coefficient.

    lines 476–542

    /-- lower bound side: a positive Zf certifies a zero forcing set -/
    theorem Zf_le {s : Finset ℕ} (hs : s ⊆ Finset.range 20) :
        Zf (msk s) ≤ (open scoped Classical in
          if is_zero_forcing_set G (((dec s)ᶜ : Finset (Fin 20)) : Set (Fin 20)) then 1 else 0) := by
      classical
      unfold Zf zR
      cases h0 : Nat.beq (Nat.mod (run 6 (msk s)) 1048576) 0
      · simp
      · have h0' := Nat.eq_of_beq_eq_true h0
        have hzf : is_zero_forcing_set G (((dec s)ᶜ : Finset (Fin 20)) : Set (Fin 20)) := by
          intro v
          apply run_sound _ 6 (msk s)
          · intro u hu
            apply ZeroForced.init
            rw [testBit_msk_dec hs] at hu
            simpa using hu
          · exact run_mod_zero h0' v.val v.isLt
        rw [if_pos hzf]; simp
    
    /-- upper bound side: a zero forcing set has Vf ≥ 1 -/
    theorem le_Vf {s : Finset ℕ} (hs : s ⊆ Finset.range 20) :
        (open scoped Classical in
          if is_zero_forcing_set G (((dec s)ᶜ : Finset (Fin 20)) : Set (Fin 20)) then 1 else 0) ≤ Vf (msk s) := by
      classical
      by_cases hzf : is_zero_forcing_set G (((dec s)ᶜ : Finset (Fin 20)) : Set (Fin 20))
      · rw [if_pos hzf]
        unfold Vf vR
        cases h0 : Nat.beq (Nat.mod (run 6 (msk s)) 1048576) 0
        · have h0' : run 6 (msk s) % 1048576 ≠ 0 := fun h => by
            have : Nat.beq (Nat.mod (run 6 (msk s)) 1048576) 0 = true := by
              show Nat.beq (run 6 (msk s) % 1048576) 0 = true
              rw [h]; rfl
            rw [this] at h0; exact absurd h0 (by simp)
          cases hf : fs (run 6 (msk s))
          · exfalso
            obtain ⟨v, hv, hb⟩ := run_mod_ne h0'
            have hS : ∀ y ∈ (((dec s)ᶜ : Finset (Fin 20)) : Set (Fin 20)), (run 6 (msk s)).testBit y.val = false := by
              intro y hy
              cases hr : (run 6 (msk s)).testBit y.val
              · rfl
              · have := run_sub 6 (msk s) y.val hr
                rw [testBit_msk_dec hs] at this
                simp at hy this; exact absurd this hy
            have := stall_not_forced _ _ hf hS ⟨v, hv⟩ (hzf ⟨v, hv⟩)
            simp [this] at hb
          · simp
        · simp
      · rw [if_neg hzf]; exact Nat.zero_le _
    
    theorem coeff_ge (j : ℕ) (hj : j ≤ 20) :
        cntN Zf 20 (20 - j) 0 ≤ (zero_forcing_poly G).coeff j := by
      classical
      rw [coeff_sum j hj, cntN_eq]
      apply Finset.sum_le_sum
      intro s hs
      rw [Nat.zero_or]
      exact Zf_le (Finset.mem_powersetCard.1 hs).1
    
    theorem coeff_le (j : ℕ) (hj : j ≤ 20) :
        (zero_forcing_poly G).coeff j ≤ cntN Vf 20 (20 - j) 0 := by
      classical
      rw [coeff_sum j hj, cntN_eq]
      apply Finset.sum_le_sum
      intro s hs
      rw [Nat.zero_or]
      exact le_Vf (Finset.mem_powersetCard.1 hs).1
    
  17. A polynomial with a valley between three points is not unimodal.

    If a polynomial is unimodal with peak m, the coefficients are non-decreasing up to m and non-increasing after m. Having p(b) < p(a) and p(b) < p(c) for a < b < c contradicts the existence of such a peak.

    lines 543–549

    theorem not_unimodal_of {p : Polynomial ℕ} {a b c : ℕ} (hab : a < b) (hbc : b < c)
        (h1 : p.coeff b < p.coeff a) (h2 : p.coeff b < p.coeff c) : ¬ polynomial_is_unimodal p := by
      rintro ⟨m, hup, hdown⟩
      by_cases hbm : b ≤ m
      · exact absurd (hup hab.le hbm) (not_le.2 h1)
      · exact absurd (hdown (by omega) hbc.le) (not_le.2 h2)
    
  18. Kernel computation evaluates the certificate sums for coefficients 15, 16, and 17. automation

    Decide by kernel evaluates the recursive sums: cntN Zf 20 3 0 = 939, twenty sub-cases sum to cntN Vf 20 4 0 = 909, and sub-cases for cntN Zf 20 5 0 sum to at least 932.

    lines 550–656

    set_option maxRecDepth 100000 in
    theorem cz3 : cntN Zf 20 3 0 = 939 := by decide +kernel
    
    set_option maxRecDepth 100000 in
    theorem cv4_0 : cntN Vf 0 3 (0 ||| 2 ^ 0) = 0 := by decide +kernel
    
    set_option maxRecDepth 100000 in
    theorem cv4_1 : cntN Vf 1 3 (0 ||| 2 ^ 1) = 0 := by decide +kernel
    
    set_option maxRecDepth 100000 in
    theorem cv4_2 : cntN Vf 2 3 (0 ||| 2 ^ 2) = 0 := by decide +kernel
    
    set_option maxRecDepth 100000 in
    theorem cv4_3 : cntN Vf 3 3 (0 ||| 2 ^ 3) = 0 := by decide +kernel
    
    set_option maxRecDepth 100000 in
    theorem cv4_4 : cntN Vf 4 3 (0 ||| 2 ^ 4) = 0 := by decide +kernel
    
    set_option maxRecDepth 100000 in
    theorem cv4_5 : cntN Vf 5 3 (0 ||| 2 ^ 5) = 0 := by decide +kernel
    
    set_option maxRecDepth 100000 in
    theorem cv4_6 : cntN Vf 6 3 (0 ||| 2 ^ 6) = 0 := by decide +kernel
    
    set_option maxRecDepth 100000 in
    theorem cv4_7 : cntN Vf 7 3 (0 ||| 2 ^ 7) = 0 := by decide +kernel
    
    set_option maxRecDepth 100000 in
    theorem cv4_8 : cntN Vf 8 3 (0 ||| 2 ^ 8) = 0 := by decide +kernel
    
    set_option maxRecDepth 100000 in
    theorem cv4_9 : cntN Vf 9 3 (0 ||| 2 ^ 9) = 0 := by decide +kernel
    
    set_option maxRecDepth 100000 in
    theorem cv4_10 : cntN Vf 10 3 (0 ||| 2 ^ 10) = 0 := by decide +kernel
    
    set_option maxRecDepth 100000 in
    theorem cv4_11 : cntN Vf 11 3 (0 ||| 2 ^ 11) = 0 := by decide +kernel
    
    set_option maxRecDepth 100000 in
    theorem cv4_12 : cntN Vf 12 3 (0 ||| 2 ^ 12) = 0 := by decide +kernel
    
    set_option maxRecDepth 100000 in
    theorem cv4_13 : cntN Vf 13 3 (0 ||| 2 ^ 13) = 0 := by decide +kernel
    
    set_option maxRecDepth 100000 in
    theorem cv4_14 : cntN Vf 14 3 (0 ||| 2 ^ 14) = 0 := by decide +kernel
    
    set_option maxRecDepth 100000 in
    theorem cv4_15 : cntN Vf 15 3 (0 ||| 2 ^ 15) = 60 := by decide +kernel
    
    set_option maxRecDepth 100000 in
    theorem cv4_16 : cntN Vf 16 3 (0 ||| 2 ^ 16) = 60 := by decide +kernel
    
    set_option maxRecDepth 100000 in
    theorem cv4_17 : cntN Vf 17 3 (0 ||| 2 ^ 17) = 172 := by decide +kernel
    
    set_option maxRecDepth 100000 in
    theorem cv4_18 : cntN Vf 18 3 (0 ||| 2 ^ 18) = 258 := by decide +kernel
    
    set_option maxRecDepth 100000 in
    theorem cv4_19 : cntN Vf 19 3 (0 ||| 2 ^ 19) = 359 := by decide +kernel
    
    set_option maxRecDepth 100000 in
    theorem cz5_17_15 : cntN Zf 15 3 (0 ||| 2 ^ 17 ||| 2 ^ 15) = 60 := by decide +kernel
    
    set_option maxRecDepth 100000 in
    theorem cz5_17_16 : cntN Zf 16 3 (0 ||| 2 ^ 17 ||| 2 ^ 16) = 60 := by decide +kernel
    
    set_option maxRecDepth 100000 in
    theorem cz5_18_15 : cntN Zf 15 3 (0 ||| 2 ^ 18 ||| 2 ^ 15) = 60 := by decide +kernel
    
    set_option maxRecDepth 100000 in
    theorem cz5_18_16 : cntN Zf 16 3 (0 ||| 2 ^ 18 ||| 2 ^ 16) = 60 := by decide +kernel
    
    set_option maxRecDepth 100000 in
    theorem cz5_18_17 : cntN Zf 17 3 (0 ||| 2 ^ 18 ||| 2 ^ 17) = 172 := by decide +kernel
    
    set_option maxRecDepth 100000 in
    theorem cz5_19_15 : cntN Zf 15 3 (0 ||| 2 ^ 19 ||| 2 ^ 15) = 60 := by decide +kernel
    
    set_option maxRecDepth 100000 in
    theorem cz5_19_16 : cntN Zf 16 3 (0 ||| 2 ^ 19 ||| 2 ^ 16) = 60 := by decide +kernel
    
    set_option maxRecDepth 100000 in
    theorem cz5_19_17 : cntN Zf 17 3 (0 ||| 2 ^ 19 ||| 2 ^ 17) = 172 := by decide +kernel
    
    set_option maxRecDepth 100000 in
    theorem cz5_19_18 : cntN Zf 18 3 (0 ||| 2 ^ 19 ||| 2 ^ 18) = 228 := by decide +kernel
    
    theorem v4 : cntN Vf 20 4 0 = 909 := by
      have e : cntN Vf 20 4 0 = ∑ m ∈ Finset.range 20, cntN Vf m 3 (0 ||| 2 ^ m) := cntN_top Vf 20 3 0
      simp only [Finset.sum_range_succ, Finset.sum_range_zero] at e
      rw [e, cv4_0, cv4_1, cv4_2, cv4_3, cv4_4, cv4_5, cv4_6, cv4_7, cv4_8, cv4_9, cv4_10, cv4_11, cv4_12, cv4_13, cv4_14, cv4_15, cv4_16, cv4_17, cv4_18, cv4_19]
    
    theorem z5 : 932 ≤ cntN Zf 20 5 0 := by
      have e : cntN Zf 20 5 0 = ∑ m ∈ Finset.range 20, cntN Zf m 4 (0 ||| 2 ^ m) := cntN_top Zf 20 4 0
      simp only [Finset.sum_range_succ, Finset.sum_range_zero] at e
      have e17 : cntN Zf 17 4 (0 ||| 2 ^ 17) = ∑ m' ∈ Finset.range 17, cntN Zf m' 3 (0 ||| 2 ^ 17 ||| 2 ^ m') := cntN_top Zf 17 3 _
      simp only [Finset.sum_range_succ, Finset.sum_range_zero] at e17
      have e18 : cntN Zf 18 4 (0 ||| 2 ^ 18) = ∑ m' ∈ Finset.range 18, cntN Zf m' 3 (0 ||| 2 ^ 18 ||| 2 ^ m') := cntN_top Zf 18 3 _
      simp only [Finset.sum_range_succ, Finset.sum_range_zero] at e18
      have e19 : cntN Zf 19 4 (0 ||| 2 ^ 19) = ∑ m' ∈ Finset.range 19, cntN Zf m' 3 (0 ||| 2 ^ 19 ||| 2 ^ m') := cntN_top Zf 19 3 _
      simp only [Finset.sum_range_succ, Finset.sum_range_zero] at e19
      have := cz5_17_15; have := cz5_17_16; have := cz5_18_15; have := cz5_18_16; have := cz5_18_17; have := cz5_19_15; have := cz5_19_16; have := cz5_19_17; have := cz5_19_18
      omega
    
  19. The zero forcing polynomial of G is not unimodal, providing a counterexample of order 20 ≤ 80.

    Combining the bounds yields coeff 15 ≥ 932, coeff 16 ≤ 909, and coeff 17 ≥ 939. Since coeff 16 is strictly less than both coeff 15 and coeff 17, the zero forcing polynomial is not unimodal. Since G has order 20 ≤ 80, this disproves OP-1400.

    lines 660–673

    theorem op_1400_counterexample_order_le_eighty :
        ∃ (n : ℕ) (_ : n ≤ 80) (G : SimpleGraph (Fin n)) (_ : DecidableRel G.Adj),
          ¬ polynomial_is_unimodal (zero_forcing_poly G) := by
      have h15 : Op1400Cex.cntN Op1400Cex.Zf 20 5 0 ≤ (zero_forcing_poly Op1400Cex.G).coeff 15 :=
        Op1400Cex.coeff_ge 15 (by norm_num)
      have h16 : (zero_forcing_poly Op1400Cex.G).coeff 16 ≤ Op1400Cex.cntN Op1400Cex.Vf 20 4 0 :=
        Op1400Cex.coeff_le 16 (by norm_num)
      have h17 : Op1400Cex.cntN Op1400Cex.Zf 20 3 0 ≤ (zero_forcing_poly Op1400Cex.G).coeff 17 :=
        Op1400Cex.coeff_ge 17 (by norm_num)
      rw [Op1400Cex.cz3] at h17
      rw [Op1400Cex.v4] at h16
      have := Op1400Cex.z5
      exact ⟨20, by norm_num, Op1400Cex.G, inferInstance,
        Op1400Cex.not_unimodal_of (a := 15) (b := 16) (c := 17) (by norm_num) (by norm_num) (by omega) (by omega)⟩

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

Lean’s trace was cut to the first 400 of 558 tactics.

namespace Op1400Cexdef AT : ℕ := 988516377098322429452817833896824765222276111927724320404473748599943602605291889595179374535843122736987115705005505676def adjOf (v : ℕ) : ℕ := Nat.mod (Nat.shiftRight AT (Nat.mul 20 v)) 1048576def tb (m i : ℕ) : Bool := !(Nat.beq (Nat.land 1 (Nat.shiftRight m i)) 0)def isS (s : ℕ) : Bool := cond (Nat.beq s 0) false (Nat.beq s (Nat.pow 2 (Nat.log2 s)))def VL : List ℕ := [0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19]def fsL (w : ℕ) (l : List ℕ) : Option ℕ :=  List.rec none (fun v _ r => cond (tb w v) r (cond (isS (Nat.land (adjOf v) w)) (some v) r)) ldef fs0 (w : ℕ) : Option ℕ := fsL w VL/-- union u1 of the white vertices' neighbourhoods, u2 of the vertices with two white neighbours,and the unprocessed white vertices -/def uLoop (f : ℕ) : ℕ → ℕ → ℕ → ℕ × ℕ × ℕ :=  Nat.rec (motive := fun _ => ℕ → ℕ → ℕ → ℕ × ℕ × ℕ) (fun rem u1 u2 => (u1, u2, rem))    (fun _ ih rem u1 u2 => cond (Nat.beq rem 0) (u1, u2, rem)      (ih (Nat.xor rem (Nat.pow 2 (Nat.log2 rem))) (Nat.lor u1 (adjOf (Nat.log2 rem)))        (Nat.lor u2 (Nat.land u1 (adjOf (Nat.log2 rem)))))) fdef eSet (w : ℕ) : ℕ :=  Nat.xor (uLoop 6 w 0 0).1 (Nat.land (uLoop 6 w 0 0).1 (Nat.lor (uLoop 6 w 0 0).2.1 w))def chk (w v : ℕ) : Bool := Nat.blt v 20 && (!(tb w v) && isS (Nat.land (adjOf v) w))def fs (w : ℕ) : Option ℕ :=  cond (Nat.beq w 0) none    (cond (Nat.beq (uLoop 6 w 0 0).2.2 0)      (cond (Nat.beq (eSet w) 0) none        (cond (chk w (Nat.log2 (eSet w))) (some (Nat.log2 (eSet w))) (fs0 w)))      (fs0 w))def run (f : ℕ) : ℕ → ℕ :=  Nat.rec (motive := fun _ => ℕ → ℕ) (fun w => w)    (fun _ ih w => Option.rec w (fun v => ih (Nat.xor w (Nat.land (adjOf v) w))) (fs w)) fdef vR (r : ℕ) : ℕ := cond (Nat.beq (Nat.mod r 1048576) 0) 1 (Option.rec 0 (fun _ => 100000) (fs r))def zR (r : ℕ) : ℕ := cond (Nat.beq (Nat.mod r 1048576) 0) 1 0def Vf (w : ℕ) : ℕ := vR (run 6 w)def Zf (w : ℕ) : ℕ := zR (run 6 w)/-- sum of f (acc ||| msk s) over the k-subsets s of range n -/def cntN (f : ℕ → ℕ) : ℕ → ℕ → ℕ → ℕ  | _, 0, acc => f acc  | 0, _ + 1, _ => 0  | n + 1, k + 1, acc => cntN f n (k + 1) acc + cntN f n k (acc ||| 2 ^ n)theorem tb_eq (m i : ℕ) : tb m i = m.testBit i := by  unfold tb Nat.testBit  cases h : Nat.beq (Nat.land 1 (Nat.shiftRight m i)) 0  · have : Nat.land 1 (Nat.shiftRight m i) ≠ 0 := fun h' => by      rw [h'] at h; exact absurd h (by decide)    simp only [Bool.not_false]    exact (bne_iff_ne.2 this).symm  · have := Nat.eq_of_beq_eq_true h    simp only [Bool.not_true]    exact (bne_eq_false_iff_eq.2 this).symmtheorem isS_spec {s : ℕ} (h : isS s = true) : ∃ x, s = 2 ^ x := by  unfold isS at h  cases h0 : Nat.beq s 0 <;> rw [h0] at h  · exact ⟨Nat.log2 s, Nat.eq_of_beq_eq_true h⟩  · simp at htheorem isS_two_pow (y : ℕ) : isS (2 ^ y) = true := by  unfold isS  have h1 : Nat.beq (2 ^ y) 0 = false := by    cases h : Nat.beq (2 ^ y) 0    · rfl    · exact absurd (Nat.eq_of_beq_eq_true h) (by positivity)  rw [h1]  show Nat.beq (2 ^ y) (2 ^ Nat.log2 (2 ^ y)) = true  rw [Nat.log2_two_pow]; exact Nat.beq_refl _theorem mem_VL {v : ℕ} : v ∈ VL ↔ v < 20 := by  simp only [VL, List.mem_cons, List.not_mem_nil, or_false]; omegatheorem adj_symm : ∀ u v : Fin 20, (adjOf u.val).testBit v.val = true →    (adjOf v.val).testBit u.val = true := by decide +kerneltheorem adj_irrefl : ∀ u : Fin 20, (adjOf u.val).testBit u.val = false := by decide +kerneltheorem adjOf_lt (v : ℕ) : adjOf v < 2 ^ 20 := Nat.mod_lt _ (by norm_num)theorem testBit_adjOf_ge {v i : ℕ} (h : 20 ≤ i) : (adjOf v).testBit i = false :=  Nat.testBit_lt_two_pow (lt_of_lt_of_le (adjOf_lt v) (Nat.pow_le_pow_right (by norm_num) h))theorem fsL_some (w : ℕ) : ∀ (l : List ℕ) {x : ℕ}, fsL w l = some x →    x ∈ l ∧ w.testBit x = false ∧ isS (adjOf x &&& w) = true  | [], x, h => by simp [fsL] at h  | v :: l, x, h => by    change cond (tb w v) (fsL w l) (cond (isS (Nat.land (adjOf v) w)) (some v) (fsL w l)) = some x at h    cases h1 : tb w v    · cases h2 : isS (Nat.land (adjOf v) w)      · simp only [h1, h2, cond_false] at h        obtain ⟨a, b, c⟩ := fsL_some w l h; exact ⟨List.mem_cons_of_mem _ a, b, c⟩      · simp only [h1, h2, cond_false, cond_true, Option.some.injEq] at h; subst h        exact ⟨List.mem_cons_self, by rw [← tb_eq]; exact h1, h2⟩    · simp only [h1, cond_true] at h      obtain ⟨a, b, c⟩ := fsL_some w l h; exact ⟨List.mem_cons_of_mem _ a, b, c⟩theorem fsL_none (w : ℕ) : ∀ (l : List ℕ), fsL w l = none →    ∀ v ∈ l, w.testBit v = true ∨ isS (adjOf v &&& w) = false  | [], _, v, hv => by simp at hv  | u :: l, h, v, hv => by    change cond (tb w u) (fsL w l) (cond (isS (Nat.land (adjOf u) w)) (some u) (fsL w l)) = none at h    have hl : fsL w l = none := by      cases h1 : tb w u      · cases h2 : isS (Nat.land (adjOf u) w)        · simpa only [h1, h2, cond_false] using h        · simp only [h1, h2, cond_false, cond_true] at h; exact absurd h (by simp)      · simpa only [h1, cond_true] using h    rcases List.mem_cons.1 hv with rfl | hv    · cases h1 : tb w v      · cases h2 : isS (Nat.land (adjOf v) w)        · exact Or.inr (by first | rfl | exact h2)        · simp only [h1, h2, cond_false, cond_true] at h; exact absurd h (by simp)      · left; rw [← tb_eq]; exact h1    · exact fsL_none w l hl v hvtheorem fs0_some {w v : ℕ} (h : fs0 w = some v) :    v < 20 ∧ w.testBit v = false ∧ ∃ x, adjOf v &&& w = 2 ^ x := by  obtain ⟨a, b, c⟩ := fsL_some w VL h  exact ⟨mem_VL.1 a, b, isS_spec c⟩theorem fs0_none {w : ℕ} (h : fs0 w = none) (v : ℕ) (hv : v < 20) (hb : w.testBit v = false)    (y : ℕ) : adjOf v &&& w ≠ 2 ^ y := by  intro he  rcases fsL_none w VL h v (mem_VL.2 hv) with h1 | h1  · rw [hb] at h1; exact absurd h1 (by simp)  · rw [he, isS_two_pow] at h1; exact absurd h1 (by simp)theorem AT_lt : AT < 2 ^ 400 := by decide +kerneltheorem adjOf_ge {y : ℕ} (hy : 20 ≤ y) : adjOf y = 0 := by  unfold adjOf  have : Nat.shiftRight AT (Nat.mul 20 y) = 0 := by    show AT >>> (20 * y) = 0    rw [Nat.shiftRight_eq_div_pow]    apply Nat.div_eq_of_lt    exact lt_of_lt_of_le AT_lt (Nat.pow_le_pow_right (by norm_num) (by omega))  rw [this]def Inv (w rem u1 u2 : ℕ) : Prop :=  (∀ i, rem.testBit i = true → w.testBit i = true) ∧  (∀ y v, w.testBit y = true → rem.testBit y = false → (adjOf y).testBit v = true →    u1.testBit v = true) ∧  (∀ v, u1.testBit v = true →    ∃ y, w.testBit y = true ∧ rem.testBit y = false ∧ (adjOf y).testBit v = true) ∧  (∀ v, u2.testBit v = true → ∃ y1 y2, y1 ≠ y2 ∧ w.testBit y1 = true ∧ w.testBit y2 = true ∧    (adjOf y1).testBit v = true ∧ (adjOf y2).testBit v = true)theorem uLoop_succ (f rem u1 u2 : ℕ) : uLoop (f + 1) rem u1 u2 =    cond (Nat.beq rem 0) (u1, u2, rem)      (uLoop f (rem ^^^ 2 ^ Nat.log2 rem) (u1 ||| adjOf (Nat.log2 rem))        (u2 ||| (u1 &&& adjOf (Nat.log2 rem)))) := rfltheorem inv_step {w rem u1 u2 : ℕ} (hrem : rem ≠ 0) (h : Inv w rem u1 u2) :    Inv w (rem ^^^ 2 ^ Nat.log2 rem) (u1 ||| adjOf (Nat.log2 rem))      (u2 ||| (u1 &&& adjOf (Nat.log2 rem))) := by  obtain ⟨h1, h2, h3, h4⟩ := h  have hy0 : rem.testBit (Nat.log2 rem) = true := Nat.testBit_log2 hrem  have hr : ∀ i, (rem ^^^ 2 ^ Nat.log2 rem).testBit i = (rem.testBit i ^^ decide (Nat.log2 rem = i)) := by    intro i; rw [Nat.testBit_xor, Nat.testBit_two_pow]  refine ⟨?_, ?_, ?_, ?_⟩  · intro i hi    rw [hr] at hi    by_cases hiy : Nat.log2 rem = i    · subst hiy; simp [hy0] at hi    · simp [hiy] at hi; exact h1 i hi  · intro y v hw hry ha    rw [Nat.testBit_or]    by_cases hyy : Nat.log2 rem = y    · subst hyy; simp [ha]    · rw [hr] at hry; simp [hyy] at hry      simp [h2 y v hw hry ha]  · intro v hv    rw [Nat.testBit_or] at hv    cases hu : u1.testBit v    · rw [hu] at hv      simp only [Bool.false_or] at hv      refine ⟨Nat.log2 rem, h1 _ hy0, ?_, hv⟩      rw [hr]; simp [hy0]    · obtain ⟨y, hwy, hry, hay⟩ := h3 v hu      refine ⟨y, hwy, ?_, hay⟩      rw [hr]      have : Nat.log2 rem ≠ y := fun e => by rw [e] at hy0; rw [hy0] at hry; exact absurd hry (by simp)      simp [this, hry]  · intro v hv    rw [Nat.testBit_or, Nat.testBit_and] at hv    cases hu2 : u2.testBit v    · rw [hu2] at hv      simp only [Bool.false_or, Bool.and_eq_true] at hv      obtain ⟨y, hwy, hry, hay⟩ := h3 v hv.1      have : y ≠ Nat.log2 rem := fun e => by rw [← e] at hy0; rw [hy0] at hry; exact absurd hry (by simp)      exact ⟨y, Nat.log2 rem, this, hwy, h1 _ hy0, hay, hv.2⟩    · exact h4 v hu2theorem uLoop_inv (w : ℕ) : ∀ f rem u1 u2, Inv w rem u1 u2 →    Inv w (uLoop f rem u1 u2).2.2 (uLoop f rem u1 u2).1 (uLoop f rem u1 u2).2.1  | 0, rem, u1, u2, h => h  | f + 1, rem, u1, u2, h => by    rw [uLoop_succ]    cases h0 : Nat.beq rem 0    · simp only [cond_false]      exact uLoop_inv w f _ _ _ (inv_step (Nat.ne_of_beq_eq_false h0) h)    · simpa only [cond_true] using htheorem inv_init (w : ℕ) : Inv w w 0 0 := by  refine ⟨fun i h => h, ?_, ?_, ?_⟩  · intro y v hw hr; rw [hw] at hr; exact absurd hr (by simp)  · intro v hv; simp at hv  · intro v hv; simp at hvtheorem fast_stall {w : ℕ} (hrem : (uLoop 6 w 0 0).2.2 = 0) (hE : eSet w = 0) (v : ℕ) (hv : v < 20)    (hb : w.testBit v = false) (x : ℕ) : adjOf v &&& w ≠ 2 ^ x := by  intro hs  have hI := uLoop_inv w 6 w 0 0 (inv_init w)  rw [hrem] at hI  obtain ⟨_, h2, _, h4⟩ := hI  have hbit : ∀ i, (adjOf v &&& w).testBit i = decide (x = i) := by    intro i; rw [hs, Nat.testBit_two_pow]  have hx := hbit x  simp only [Nat.testBit_and, decide_true, Bool.and_eq_true] at hx  have hx20 : x < 20 := by    by_contra hc; rw [testBit_adjOf_ge (by omega)] at hx; exact absurd hx.1 (by simp)  have hxv : (adjOf x).testBit v = true := adj_symm ⟨v, hv⟩ ⟨x, hx20⟩ hx.1  have hu1 := h2 x v hx.2 (by simp) hxv  have hEv : (eSet w).testBit v = false := by rw [hE]; simp  unfold eSet at hEv  simp only [show ∀ a b : ℕ, Nat.xor a b = a ^^^ b from fun _ _ => rfl,    show ∀ a b : ℕ, Nat.land a b = a &&& b from fun _ _ => rfl,    show ∀ a b : ℕ, Nat.lor a b = a ||| b from fun _ _ => rfl,    Nat.testBit_xor, Nat.testBit_and, Nat.testBit_or, hu1, hb] at hEv  have hu2 : (uLoop 6 w 0 0).2.1.testBit v = true := by    cases h : (uLoop 6 w 0 0).2.1.testBit v    · rw [h] at hEv; simp at hEv    · rfl  obtain ⟨y1, y2, hne, hw1, hw2, ha1, ha2⟩ := h4 v hu2  have hy1 : y1 < 20 := by    by_contra hc; rw [adjOf_ge (by omega)] at ha1; simp at ha1  have hy2 : y2 < 20 := by    by_contra hc; rw [adjOf_ge (by omega)] at ha2; simp at ha2  have e1 := hbit y1  have e2 := hbit y2  rw [Nat.testBit_and, adj_symm ⟨y1, hy1⟩ ⟨v, hv⟩ ha1, hw1] at e1  rw [Nat.testBit_and, adj_symm ⟨y2, hy2⟩ ⟨v, hv⟩ ha2, hw2] at e2  simp only [Bool.and_self, Bool.true_eq, decide_eq_true_eq] at e1 e2  exact hne (e1.symm.trans e2)theorem forceStep_some {w v : ℕ} (h : fs w = some v) :    v < 20 ∧ w.testBit v = false ∧ ∃ x, adjOf v &&& w = 2 ^ x := by  unfold fs at h  cases h0 : Nat.beq w 0  · cases hr : Nat.beq (uLoop 6 w 0 0).2.2 0    · simp only [h0, hr, cond_false] at h; exact fs0_some h    · cases h1 : Nat.beq (eSet w) 0      · cases h2 : chk w (Nat.log2 (eSet w))        · simp only [h0, hr, h1, h2, cond_false, cond_true] at h; exact fs0_some h        · simp only [h0, hr, h1, h2, cond_false, cond_true, Option.some.injEq] at h          subst h          simp only [chk, Bool.and_eq_true, Bool.not_eq_true'] at h2          obtain ⟨ha, hb, hc⟩ := h2          exact ⟨Nat.le_of_ble_eq_true ha, by rw [← tb_eq]; exact hb, isS_spec hc⟩      · simp only [h0, hr, h1, cond_false, cond_true] at h; exact absurd h (by simp)  · simp only [h0, cond_true] at h; exact absurd h (by simp)theorem forceStep_none {w : ℕ} (h : fs w = none) (v : ℕ) (hv : v < 20) (hb : w.testBit v = false)    (y : ℕ) : adjOf v &&& w ≠ 2 ^ y := by  unfold fs at h  cases h0 : Nat.beq w 0  · cases hr : Nat.beq (uLoop 6 w 0 0).2.2 0    · apply fs0_none _ v hv hb y      simpa only [h0, hr, cond_false] using h    · cases h1 : Nat.beq (eSet w) 0      · apply fs0_none _ v hv hb y        cases h2 : chk w (Nat.log2 (eSet w))        · simpa only [h0, hr, h1, h2, cond_false, cond_true] using h        · simp only [h0, hr, h1, h2, cond_false, cond_true] at h; exact absurd h (by simp)      · exact fast_stall (Nat.eq_of_beq_eq_true hr) (Nat.eq_of_beq_eq_true h1) v hv hb y  · rw [Nat.eq_of_beq_eq_true h0, Nat.and_zero]    exact (Nat.two_pow_pos y).netheorem run_succ (f w : ℕ) : run (f + 1) w = Option.rec w (fun v => run f (w ^^^ (adjOf v &&& w))) (fs w) := rfldef G : SimpleGraph (Fin 20) := SimpleGraph.fromRel (fun u v => (adjOf u.val).testBit v.val = true)theorem adj_iff {u v : Fin 20} : G.Adj u v ↔ (adjOf u.val).testBit v.val = true := by  simp only [G, SimpleGraph.fromRel_adj]  constructor  · rintro ⟨_, h | h⟩    · exact h    · exact adj_symm _ _ h  · intro h    refine ⟨?_, Or.inl h⟩    rintro rfl; rw [adj_irrefl] at h; exact absurd h (by simp)instance : DecidableRel G.Adj := fun _ _ => decidable_of_iff _ adj_iff.symmtheorem run_sub : ∀ f w i, (run f w).testBit i = true → w.testBit i = true  | 0, w, i, h => h  | f + 1, w, i, h => by    rw [run_succ] at h    cases hx : fs w with    | none => rw [hx] at h; exact h    | some x =>      rw [hx] at h      have := run_sub f _ i h      simp [Nat.testBit_xor, Nat.testBit_and] at this      by_cases hw : w.testBit i <;> simp_alltheorem run_sound (S : Set (Fin 20)) : ∀ f w, (∀ v : Fin 20, w.testBit v.val = false → ZeroForced G S v) →    ∀ v : Fin 20, (run f w).testBit v.val = false → ZeroForced G S v  | 0, w, hw => hw  | f + 1, w, hw => by    rw [run_succ]    cases hu : fs w with    | none => exact hw    | some u =>      obtain ⟨hu24, hub, x, hsx⟩ := forceStep_some hu      apply run_sound S f      have hbit : ∀ i, ((adjOf u &&& w).testBit i = true ↔ i = x) := by        intro i; rw [hsx, Nat.testBit_two_pow]; simp [eq_comm]      have hxa : (adjOf u).testBit x = true := by        have := (hbit x).2 rfl; simp [Nat.testBit_and] at this; exact this.1      have hx24 : x < 20 := by        by_contra hc; rw [testBit_adjOf_ge (by omega)] at hxa; exact absurd hxa (by simp)      have hfu : ZeroForced G S ⟨u, hu24⟩ := hw ⟨u, hu24⟩ hub      intro v hv      by_cases hvw : w.testBit v.val = true      · have hva : (adjOf u).testBit v.val = true := by          simp [Nat.testBit_xor, Nat.testBit_and, hvw] at hv; exact hv        have hvx : v.val = x := (hbit v.val).1 (by simp [Nat.testBit_and, hva, hvw])        have : v = ⟨x, hx24⟩ := Fin.ext hvx        subst this        refine ZeroForced.step _ _ hfu (adj_iff.2 hxa) ?_        intro y hy hyx        apply hw        by_contra hyw        simp only [Bool.not_eq_false] at hyw        have := (hbit y.val).1 (by simp [Nat.testBit_and, hyw]; exact adj_iff.1 hy)        exact hyx (Fin.ext this)      · exact hw v (by simpa using hvw)theorem stall_not_forced (S : Set (Fin 20)) (r : ℕ) (hr : fs r = none)    (hS : ∀ v ∈ S, r.testBit v.val = false) : ∀ y, ZeroForced G S y → r.testBit y.val = false := by  intro y hy  induction hy with  | init v hv => exact hS v hv  | step u y hu huy hall ihu ihall =>    by_contra hry    simp only [Bool.not_eq_false] at hry    have hs : adjOf u.val &&& r = 2 ^ y.val := by      apply Nat.eq_of_testBit_eq      intro i      rw [Nat.testBit_two_pow, Nat.testBit_and]      by_cases hi : i < 20      · by_cases hiy : i = y.val        · subst hiy; simp [hry]; exact adj_iff.1 huy        · have : (adjOf u.val).testBit i = true → r.testBit i = false := fun ha =>            ihall ⟨i, hi⟩ (adj_iff.2 ha) (fun h => hiy (by rw [← h]))          have hne : decide (y.val = i) = false := by simp; omega          rw [hne]          cases ha : (adjOf u.val).testBit i          · simp          · simp [this ha]      · rw [testBit_adjOf_ge (by omega)]; simp; omega    exact forceStep_none hr u.val u.isLt ihu y.val hsdef msk (s : Finset ℕ) : ℕ := s.fold (· ||| ·) 0 (fun i => 2 ^ i)theorem testBit_msk (s : Finset ℕ) (i : ℕ) : (msk s).testBit i = decide (i ∈ s) := by  induction s using Finset.induction_on with  | empty => simp [msk]  | insert a s ha ih =>    unfold msk at *    rw [Finset.fold_insert ha, Nat.testBit_or, ih, Nat.testBit_two_pow]    by_cases h : i = a <;> simp [h, eq_comm]theorem cntN_eq (f : ℕ → ℕ) : ∀ n k acc,    cntN f n k acc = ∑ s ∈ (Finset.range n).powersetCard k, f (acc ||| msk s)  | n, 0, acc => by simp [cntN, msk]  | 0, k + 1, acc => by    rw [Finset.range_zero, Finset.powersetCard_eq_empty.2 (by simp)]; rfl  | n + 1, k + 1, acc => by    rw [cntN, cntN_eq f n (k + 1) acc, cntN_eq f n k (acc ||| 2 ^ n), Finset.range_add_one,      Finset.powersetCard_succ_insert Finset.notMem_range_self, Finset.sum_union, Finset.sum_image]    · congr 1      apply Finset.sum_congr rfl      intro s hs      have hn : n ∉ s := fun h => by        have := (Finset.mem_powersetCard.1 hs).1 h; simp at this      unfold msk      rw [Finset.fold_insert hn]      simp [Nat.or_assoc]    · intro s hs t ht hst      have hns : n ∉ s := fun h => by have := (Finset.mem_powersetCard.1 hs).1 h; simp at this      have hnt : n ∉ t := fun h => by have := (Finset.mem_powersetCard.1 ht).1 h; simp at this      have := congrArg (fun u => u.erase n) hst      simpa [Finset.erase_insert hns, Finset.erase_insert hnt] using this    · rw [Finset.disjoint_left]      intro s hs hs'      obtain ⟨t, ht, rfl⟩ := Finset.mem_image.1 hs'      have := (Finset.mem_powersetCard.1 hs).1 (Finset.mem_insert_self n t)      simp at thistheorem cntN_top (f : ℕ → ℕ) : ∀ n k acc,    cntN f n (k + 1) acc = ∑ m ∈ Finset.range n, cntN f m k (acc ||| 2 ^ m)  | 0, k, acc => by simp [cntN]  | n + 1, k, acc => by    rw [cntN, cntN_top f n k acc, Finset.sum_range_succ]open scoped Classical intheorem coeff_zfp (j : ℕ) : (zero_forcing_poly G).coeff j =    (Finset.univ.filter (fun S : Finset (Fin 20) => S.card = j ∧ is_zero_forcing_set G (S : Set (Fin 20)))).card := by  unfold zero_forcing_poly  rw [Polynomial.finsetSum_coeff, Finset.card_filter]  apply Finset.sum_congr rfl  intro S _  by_cases h : is_zero_forcing_set G (S : Set (Fin 20))  · by_cases hj : S.card = j    · simp [h, hj, Polynomial.coeff_X_pow]    · simp [h, hj, Polynomial.coeff_X_pow, Ne.symm hj]  · simp [h]/-- decode a subset of range 20 -/def dec (s : Finset ℕ) : Finset (Fin 20) := Finset.univ.filter (fun v : Fin 20 => v.val ∈ s)theorem map_dec {s : Finset ℕ} (hs : s ⊆ Finset.range 20) : (dec s).map Fin.valEmbedding = s := by  ext x; simp only [dec, Finset.mem_map, Finset.mem_filter, Finset.mem_univ, true_and,    Fin.valEmbedding_apply]  constructor  · rintro ⟨a, ha, rfl⟩; exact ha  · intro hx; exact ⟨⟨x, by simpa using hs hx⟩, hx, rfl⟩open scoped Classical in/-- the j-th coefficient as a sum over the (20 - j)-subsets of range 20 of white vertices -/theorem coeff_sum (j : ℕ) (hj : j ≤ 20) : (zero_forcing_poly G).coeff j =    ∑ s ∈ (Finset.range 20).powersetCard (20 - j),      if is_zero_forcing_set G (((dec s)ᶜ : Finset (Fin 20)) : Set (Fin 20)) then 1 else 0 := by  rw [coeff_zfp, ← Finset.card_filter]  apply Finset.card_nbij' (fun S => Sᶜ.map Fin.valEmbedding) (fun s => (dec s)ᶜ)  · intro S hS    simp only [Finset.coe_filter, Finset.mem_univ, true_and, Set.mem_ofPred_eq] at hS    simp only [Finset.coe_filter, Finset.mem_powersetCard, Set.mem_ofPred_eq]    have hsub : Sᶜ.map Fin.valEmbedding ⊆ Finset.range 20 := by      intro x hx; simp at hx; obtain ⟨a, _, rfl⟩ := hx; simp    refine ⟨⟨hsub, by rw [Finset.card_map, Finset.card_compl, hS.1]; simp⟩, ?_⟩    have : (dec (Sᶜ.map Fin.valEmbedding))ᶜ = S := by ext v; simp [dec, Fin.val_inj]    rw [this]; exact hS.2  · intro s hs    simp only [Finset.coe_filter, Finset.mem_powersetCard, Set.mem_ofPred_eq] at hs    simp only [Finset.coe_filter, Finset.mem_univ, true_and, Set.mem_ofPred_eq]    refine ⟨?_, hs.2⟩    rw [Finset.card_compl, ← Finset.card_map Fin.valEmbedding, map_dec hs.1.1, hs.1.2]    simp; omega  · intro S _; ext v; simp [dec, Fin.val_inj]  · intro s hs    simp only [Finset.coe_filter, Finset.mem_powersetCard, Set.mem_ofPred_eq] at hs    simp [map_dec hs.1.1]theorem testBit_msk_dec {s : Finset ℕ} (hs : s ⊆ Finset.range 20) (v : Fin 20) :    (msk s).testBit v.val = decide (v ∉ (dec s)ᶜ) := by  rw [testBit_msk]; simp [dec]theorem run_mod_zero {r : ℕ} (h : r % 1048576 = 0) (v : ℕ) (hv : v < 20) : r.testBit v = false := by  have := congrArg (fun r => r.testBit v) h  simp only [show (1048576 : ℕ) = 2 ^ 20 by norm_num, Nat.testBit_mod_two_pow, Nat.zero_testBit] at this  simpa [hv] using thistheorem run_mod_ne {r : ℕ} (h : r % 1048576 ≠ 0) : ∃ v < 20, r.testBit v = true := by  by_contra hc  push Not at hc  apply h  apply Nat.eq_of_testBit_eq  intro i  rw [show (1048576 : ℕ) = 2 ^ 20 by norm_num, Nat.testBit_mod_two_pow, Nat.zero_testBit]  by_cases hi : i < 20  · simp [hi, hc i hi]  · simp [hi]/-- lower bound side: a positive Zf certifies a zero forcing set -/theorem Zf_le {s : Finset ℕ} (hs : s ⊆ Finset.range 20) :    Zf (msk s) ≤ (open scoped Classical in      if is_zero_forcing_set G (((dec s)ᶜ : Finset (Fin 20)) : Set (Fin 20)) then 1 else 0) := by  classical  unfold Zf zR  cases h0 : Nat.beq (Nat.mod (run 6 (msk s)) 1048576) 0  · simp  · have h0' := Nat.eq_of_beq_eq_true h0    have hzf : is_zero_forcing_set G (((dec s)ᶜ : Finset (Fin 20)) : Set (Fin 20)) := by      intro v      apply run_sound _ 6 (msk s)      · intro u hu        apply ZeroForced.init        rw [testBit_msk_dec hs] at hu        simpa using hu      · exact run_mod_zero h0' v.val v.isLt    rw [if_pos hzf]; simp/-- upper bound side: a zero forcing set has Vf ≥ 1 -/theorem le_Vf {s : Finset ℕ} (hs : s ⊆ Finset.range 20) :    (open scoped Classical in      if is_zero_forcing_set G (((dec s)ᶜ : Finset (Fin 20)) : Set (Fin 20)) then 1 else 0) ≤ Vf (msk s) := by  classical  by_cases hzf : is_zero_forcing_set G (((dec s)ᶜ : Finset (Fin 20)) : Set (Fin 20))  · rw [if_pos hzf]    unfold Vf vR    cases h0 : Nat.beq (Nat.mod (run 6 (msk s)) 1048576) 0    · have h0' : run 6 (msk s) % 1048576 ≠ 0 := fun h => by        have : Nat.beq (Nat.mod (run 6 (msk s)) 1048576) 0 = true := by          show Nat.beq (run 6 (msk s) % 1048576) 0 = true          rw [h]; rfl        rw [this] at h0; exact absurd h0 (by simp)      cases hf : fs (run 6 (msk s))      · exfalso        obtain ⟨v, hv, hb⟩ := run_mod_ne h0'        have hS : ∀ y ∈ (((dec s)ᶜ : Finset (Fin 20)) : Set (Fin 20)), (run 6 (msk s)).testBit y.val = false := by          intro y hy          cases hr : (run 6 (msk s)).testBit y.val          · rfl          · have := run_sub 6 (msk s) y.val hr            rw [testBit_msk_dec hs] at this            simp at hy this; exact absurd this hy        have := stall_not_forced _ _ hf hS ⟨v, hv⟩ (hzf ⟨v, hv⟩)        simp [this] at hb      · simp    · simp  · rw [if_neg hzf]; exact Nat.zero_le _theorem coeff_ge (j : ℕ) (hj : j ≤ 20) :    cntN Zf 20 (20 - j) 0 ≤ (zero_forcing_poly G).coeff j := by  classical  rw [coeff_sum j hj, cntN_eq]  apply Finset.sum_le_sum  intro s hs  rw [Nat.zero_or]  exact Zf_le (Finset.mem_powersetCard.1 hs).1theorem coeff_le (j : ℕ) (hj : j ≤ 20) :    (zero_forcing_poly G).coeff j ≤ cntN Vf 20 (20 - j) 0 := by  classical  rw [coeff_sum j hj, cntN_eq]  apply Finset.sum_le_sum  intro s hs  rw [Nat.zero_or]  exact le_Vf (Finset.mem_powersetCard.1 hs).1theorem not_unimodal_of {p : Polynomial ℕ} {a b c : ℕ} (hab : a < b) (hbc : b < c)    (h1 : p.coeff b < p.coeff a) (h2 : p.coeff b < p.coeff c) : ¬ polynomial_is_unimodal p := by  rintro ⟨m, hup, hdown⟩  by_cases hbm : b ≤ m  · exact absurd (hup hab.le hbm) (not_le.2 h1)  · exact absurd (hdown (by omega) hbc.le) (not_le.2 h2)set_option maxRecDepth 100000 intheorem cz3 : cntN Zf 20 3 0 = 939 := by decide +kernelset_option maxRecDepth 100000 intheorem cv4_0 : cntN Vf 0 3 (0 ||| 2 ^ 0) = 0 := by decide +kernelset_option maxRecDepth 100000 intheorem cv4_1 : cntN Vf 1 3 (0 ||| 2 ^ 1) = 0 := by decide +kernelset_option maxRecDepth 100000 intheorem cv4_2 : cntN Vf 2 3 (0 ||| 2 ^ 2) = 0 := by decide +kernelset_option maxRecDepth 100000 intheorem cv4_3 : cntN Vf 3 3 (0 ||| 2 ^ 3) = 0 := by decide +kernelset_option maxRecDepth 100000 intheorem cv4_4 : cntN Vf 4 3 (0 ||| 2 ^ 4) = 0 := by decide +kernelset_option maxRecDepth 100000 intheorem cv4_5 : cntN Vf 5 3 (0 ||| 2 ^ 5) = 0 := by decide +kernelset_option maxRecDepth 100000 intheorem cv4_6 : cntN Vf 6 3 (0 ||| 2 ^ 6) = 0 := by decide +kernelset_option maxRecDepth 100000 intheorem cv4_7 : cntN Vf 7 3 (0 ||| 2 ^ 7) = 0 := by decide +kernelset_option maxRecDepth 100000 intheorem cv4_8 : cntN Vf 8 3 (0 ||| 2 ^ 8) = 0 := by decide +kernelset_option maxRecDepth 100000 intheorem cv4_9 : cntN Vf 9 3 (0 ||| 2 ^ 9) = 0 := by decide +kernelset_option maxRecDepth 100000 intheorem cv4_10 : cntN Vf 10 3 (0 ||| 2 ^ 10) = 0 := by decide +kernelset_option maxRecDepth 100000 intheorem cv4_11 : cntN Vf 11 3 (0 ||| 2 ^ 11) = 0 := by decide +kernelset_option maxRecDepth 100000 intheorem cv4_12 : cntN Vf 12 3 (0 ||| 2 ^ 12) = 0 := by decide +kernelset_option maxRecDepth 100000 intheorem cv4_13 : cntN Vf 13 3 (0 ||| 2 ^ 13) = 0 := by decide +kernelset_option maxRecDepth 100000 intheorem cv4_14 : cntN Vf 14 3 (0 ||| 2 ^ 14) = 0 := by decide +kernelset_option maxRecDepth 100000 intheorem cv4_15 : cntN Vf 15 3 (0 ||| 2 ^ 15) = 60 := by decide +kernelset_option maxRecDepth 100000 intheorem cv4_16 : cntN Vf 16 3 (0 ||| 2 ^ 16) = 60 := by decide +kernelset_option maxRecDepth 100000 intheorem cv4_17 : cntN Vf 17 3 (0 ||| 2 ^ 17) = 172 := by decide +kernelset_option maxRecDepth 100000 intheorem cv4_18 : cntN Vf 18 3 (0 ||| 2 ^ 18) = 258 := by decide +kernelset_option maxRecDepth 100000 intheorem cv4_19 : cntN Vf 19 3 (0 ||| 2 ^ 19) = 359 := by decide +kernelset_option maxRecDepth 100000 intheorem cz5_17_15 : cntN Zf 15 3 (0 ||| 2 ^ 17 ||| 2 ^ 15) = 60 := by decide +kernelset_option maxRecDepth 100000 intheorem cz5_17_16 : cntN Zf 16 3 (0 ||| 2 ^ 17 ||| 2 ^ 16) = 60 := by decide +kernelset_option maxRecDepth 100000 intheorem cz5_18_15 : cntN Zf 15 3 (0 ||| 2 ^ 18 ||| 2 ^ 15) = 60 := by decide +kernelset_option maxRecDepth 100000 intheorem cz5_18_16 : cntN Zf 16 3 (0 ||| 2 ^ 18 ||| 2 ^ 16) = 60 := by decide +kernelset_option maxRecDepth 100000 intheorem cz5_18_17 : cntN Zf 17 3 (0 ||| 2 ^ 18 ||| 2 ^ 17) = 172 := by decide +kernelset_option maxRecDepth 100000 intheorem cz5_19_15 : cntN Zf 15 3 (0 ||| 2 ^ 19 ||| 2 ^ 15) = 60 := by decide +kernelset_option maxRecDepth 100000 intheorem cz5_19_16 : cntN Zf 16 3 (0 ||| 2 ^ 19 ||| 2 ^ 16) = 60 := by decide +kernelset_option maxRecDepth 100000 intheorem cz5_19_17 : cntN Zf 17 3 (0 ||| 2 ^ 19 ||| 2 ^ 17) = 172 := by decide +kernelset_option maxRecDepth 100000 intheorem cz5_19_18 : cntN Zf 18 3 (0 ||| 2 ^ 19 ||| 2 ^ 18) = 228 := by decide +kerneltheorem v4 : cntN Vf 20 4 0 = 909 := by  have e : cntN Vf 20 4 0 = ∑ m ∈ Finset.range 20, cntN Vf m 3 (0 ||| 2 ^ m) := cntN_top Vf 20 3 0  simp only [Finset.sum_range_succ, Finset.sum_range_zero] at e  rw [e, cv4_0, cv4_1, cv4_2, cv4_3, cv4_4, cv4_5, cv4_6, cv4_7, cv4_8, cv4_9, cv4_10, cv4_11, cv4_12, cv4_13, cv4_14, cv4_15, cv4_16, cv4_17, cv4_18, cv4_19]theorem z5 : 932 ≤ cntN Zf 20 5 0 := by  have e : cntN Zf 20 5 0 = ∑ m ∈ Finset.range 20, cntN Zf m 4 (0 ||| 2 ^ m) := cntN_top Zf 20 4 0  simp only [Finset.sum_range_succ, Finset.sum_range_zero] at e  have e17 : cntN Zf 17 4 (0 ||| 2 ^ 17) = ∑ m' ∈ Finset.range 17, cntN Zf m' 3 (0 ||| 2 ^ 17 ||| 2 ^ m') := cntN_top Zf 17 3 _  simp only [Finset.sum_range_succ, Finset.sum_range_zero] at e17  have e18 : cntN Zf 18 4 (0 ||| 2 ^ 18) = ∑ m' ∈ Finset.range 18, cntN Zf m' 3 (0 ||| 2 ^ 18 ||| 2 ^ m') := cntN_top Zf 18 3 _  simp only [Finset.sum_range_succ, Finset.sum_range_zero] at e18  have e19 : cntN Zf 19 4 (0 ||| 2 ^ 19) = ∑ m' ∈ Finset.range 19, cntN Zf m' 3 (0 ||| 2 ^ 19 ||| 2 ^ m') := cntN_top Zf 19 3 _  simp only [Finset.sum_range_succ, Finset.sum_range_zero] at e19  have := cz5_17_15; have := cz5_17_16; have := cz5_18_15; have := cz5_18_16; have := cz5_18_17; have := cz5_19_15; have := cz5_19_16; have := cz5_19_17; have := cz5_19_18  omegaend Op1400Cex/-- Open Problem OP-1400: there exists a simple graph of order at most 80 with a non-unimodal zero forcing polynomial. -/theorem op_1400_counterexample_order_le_eighty :    ∃ (n : ℕ) (_ : n ≤ 80) (G : SimpleGraph (Fin n)) (_ : DecidableRel G.Adj),      ¬ polynomial_is_unimodal (zero_forcing_poly G) := by  have h15 : Op1400Cex.cntN Op1400Cex.Zf 20 5 0 ≤ (zero_forcing_poly Op1400Cex.G).coeff 15 :=    Op1400Cex.coeff_ge 15 (by norm_num)  have h16 : (zero_forcing_poly Op1400Cex.G).coeff 16 ≤ Op1400Cex.cntN Op1400Cex.Vf 20 4 0 :=    Op1400Cex.coeff_le 16 (by norm_num)  have h17 : Op1400Cex.cntN Op1400Cex.Zf 20 3 0 ≤ (zero_forcing_poly Op1400Cex.G).coeff 17 :=    Op1400Cex.coeff_ge 17 (by norm_num)  rw [Op1400Cex.cz3] at h17  rw [Op1400Cex.v4] at h16  have := Op1400Cex.z5  exact ⟨20, by norm_num, Op1400Cex.G, inferInstance,    Op1400Cex.not_unimodal_of (a := 15) (b := 16) (c := 17) (by norm_num) (by norm_num) (by omega) (by omega)⟩
See it in the graphDiscuss this resultChallenge it