AFTD Auto-Formalizing Theoretical Domains

temporal_path_many_targets_one_frame_trap

theoremverifiedoriginal

For every k ≥ 2 there is a temporal graph on N = k² + k vertices, all of whose snapshots are spanning paths, together with k designated targets and a start vertex, such that every walk from that start visits at most one target by time N − 1. This is an obstruction to a prescribed-start one-frame coverage principle considered while working on OP-80; the asymptotic exploration bound remains open.

Statement

theorem temporal_path_many_targets_one_frame_trap (k : ℕ) (hk : 2 ≤ k) :
    ∃ (G : ℕ → SimpleGraph (Fin (k * k + k)))
      (U : Finset (Fin (k * k + k))) (s : Fin (k * k + k)),
      U.card = k ∧ (∀ t, is_spanning_path_graph (G t)) ∧
      ∀ w : ℕ → Fin (k * k + k), w 0 = s → is_temporal_walk G w →
        ∀ a < k * k + k, ∀ b < k * k + k,
          w a ∈ U → w b ∈ U → w a = w b
Related work
OP-80, arXiv:2610.06228 Sec. 7. A relocation construction developed in the deep session to test an auxiliary prescribed-start constant-fraction coverage principle. The construction is a diagnostic for that proof route and is not an asymptotic lower-bound advance.
Verified
25 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • is_temporal_walkA temporal walk in a temporal graph (G_t)_t: at every time step t the agent either waits or traverses one edge of the snapshot G_t.
  • is_spanning_path_graphA graph on n vertices is a spanning path if its vertices can be ordered so that exactly consecutive vertices are adjacent.

The proof, explained

The proof constructs a temporal graph on N = k² + k vertices where every snapshot is a spanning path defined by dynamically ordering the vertices. Initially, k targets occupy coordinates k², …, k² + k - 1 while grid vertices occupy coordinates 0, …, k² - 1. At time t = k² + j, target j swaps with grid vertex (j, 0), moving down to coordinate k * j. A walk starting at coordinate 0 cannot reach any target before its activation because the walker's coordinate at time t is at most t. Once target q is visited at time a ≥ k² + q, the remaining time before N is strictly less than k, which traps the walker within distance k of k * q where no further swaps occur, preventing it from reaching any other target.

  1. At each time step, any vertex's coordinate increases to at most max(coordinate(t, v), t + 1).

    Case analysis on whether v is a grid vertex (j, r) or a target j. If v = (j, r) with r = 0, its coordinate can only swap from k * j to k² + j when t + 1 ≥ k² + j, which is at most t + 1. If r ≠ 0, its coordinate is static. If v is a target j, its coordinate can only drop from k² + j to k * j < k² ≤ t + 1. In all cases, the coordinate at t + 1 is bounded by max(coordinate(t, v), t + 1).

    lines 11–30

    uses Nat.zero_add, le_trans, Nat.le_max_right, Nat.mul_lt_mul_of_pos_left

        coordinate (t + 1) v ≤ max (coordinate t v) (t + 1) := by
      rcases v with ⟨j, r⟩ | j
      · by_cases hr : r.val = 0
        · simp only [coordinate, hr, true_and, Nat.zero_add]
          by_cases h0 : k * k + j.val ≤ t
          · have h1 : k * k + j.val ≤ t + 1 := by omega
            simp [h0, h1]
          · by_cases h1 : k * k + j.val ≤ t + 1
            · simpa [h0, h1] using
                le_trans h1 (Nat.le_max_right (k * j.val) (t + 1))
            · simp [h0, h1]
        · simp [coordinate, hr]
      · have hj : k * j.val < k * k := Nat.mul_lt_mul_of_pos_left j.isLt hk
        by_cases h0 : k * k + j.val ≤ t
        · have h1 : k * k + j.val ≤ t + 1 := by omega
          simp [coordinate, h0, h1]
        · by_cases h1 : k * k + j.val ≤ t + 1
          · simp only [coordinate, h0, h1, if_true, if_false]
            exact le_trans (by omega) (Nat.le_max_right _ _)
          · simp [coordinate, h0, h1]
  2. Coordinates below k * (q + 1) remain frozen after time k² + q.

    Since t ≥ k² + q, any swap that occurs at time t + 1 corresponds to some index j with k² + j = t + 1 > k² + q, meaning j ≥ q + 1. The vertices swapped at time t + 1 have coordinates k * j ≥ k * (q + 1) and k² + j > k * (q + 1). Thus, any vertex with coordinate strictly less than k * (q + 1) is untouched by swaps at time t + 1 and keeps its coordinate.

    lines 35–55

    uses Nat.mul_le_mul_left, Nat.succ_le_of_lt, Nat.zero_add

        coordinate (t + 1) v = coordinate t v := by
      have hq : k * (q.val + 1) ≤ k * k :=
        Nat.mul_le_mul_left k (Nat.succ_le_of_lt q.isLt)
      rcases v with ⟨j, r⟩ | j
      · by_cases hr : r.val = 0
        · simp only [coordinate, hr, true_and, Nat.zero_add] at hv ⊢
          by_cases h0 : k * k + j.val ≤ t
          · have h1 : k * k + j.val ≤ t + 1 := by omega
            simp [h0, h1]
          · by_cases h1 : k * k + j.val ≤ t + 1
            · have hj : q.val + 1 ≤ j.val := by omega
              have hmul := Nat.mul_le_mul_left k hj
              simp only [h0, if_false] at hv
              omega
            · simp [h0, h1]
        · simp [coordinate, hr]
      · by_cases h0 : k * k + j.val ≤ t
        · have h1 : k * k + j.val ≤ t + 1 := by omega
          simp [coordinate, h0, h1]
        · simp only [coordinate, h0, if_false] at hv
          omega
  3. In any coordinate walk, the coordinate at time t changes by at most 1 in a single step.

    By definition of a coordinate walk, the walker at time t either stays at the same vertex or moves to a vertex whose coordinate differs by ±1. In all cases, the coordinate difference is at most 1.

    lines 65–69

          coordinate t (v t) ≤ coordinate t (v (t + 1)) + 1 := by
      rcases hv t with he | he | he
      · simp [he]
      · omega
      · omega
  4. A coordinate walk starting at coordinate 0 satisfies coordinate(t, v(t)) ≤ t for all t.

    By induction on t. The base case t = 0 holds because the initial coordinate is 0. In the induction step, the walk moves to v(t + 1) whose coordinate at time t is at most coordinate(t, v(t)) + 1 ≤ t + 1 by `coordinate_walk_bounds`. By `coordinate_step_bound`, coordinate(t + 1, v(t + 1)) ≤ max(coordinate(t, v(t + 1)), t + 1) ≤ t + 1.

    lines 74–81

    uses coordinate_walk_bounds, coordinate_step_bound

        ∀ t, coordinate t (v t) ≤ t := by
      intro t
      induction t with
      | zero => omega
      | succ t ih =>
        have hm := (coordinate_walk_bounds v hv t).1
        have hs := coordinate_step_bound hk t (v (t + 1))
        omega
  5. Target q cannot be visited before its activation time k² + q.

    Suppose v(a) = Sum.inr q. If a < k² + q, the target has not swapped yet, so its coordinate at time a is k² + q > a. But coordinate(a, v(a)) ≤ a by the global position bound, yielding a contradiction. Hence k² + q ≤ a.

    lines 85–90

        (ha : v a = Sum.inr q) : k * k + q.val ≤ a := by
      have hp := hpos a
      rw [ha] at hp
      by_cases h : k * k + q.val ≤ a
      · exact h
      · simp [coordinate, h] at hp
  6. Once target q is visited at time a, the walker remains within distance d of k * q at time a + d.

    By induction on d. At d = 0, the target has swapped to coordinate k * q. For d + 1 < k, the walker's coordinate at time a + d is strictly less than k * (q + 1). By `coordinate_step_fixed`, the coordinate of v(a + d + 1) does not change between time a + d and a + d + 1. Combined with the one-step walk bound, the coordinate remains within distance d + 1 of k * q.

    lines 98–115

    uses coordinate_target_active, coordinate_walk_bounds, Nat.mul_add, Nat.mul_one, coordinate_step_fixed

          k * q.val ≤ coordinate (a + d) (v (a + d)) + d := by
      have hactive := coordinate_target_active v hpos a q ha
      intro d
      induction d with
      | zero => simp [ha, coordinate, hactive]
      | succ d ih =>
        intro hd
        have hi := ih (by omega)
        have hm := coordinate_walk_bounds v hv (a + d)
        have hdlt : d + 1 < k := by omega
        have hp : coordinate (a + d) (v (a + d + 1)) < k * (q.val + 1) := by
          rw [Nat.mul_add, Nat.mul_one]
          omega
        have hfixed := coordinate_step_fixed hk q (a + d) (by omega)
          (v (a + d + 1)) hp
        have he : a + (d + 1) = a + d + 1 := by omega
        rw [he, hfixed]
        omega
  7. Any two targets visited before time k² + k must be identical.

    If targets q and r are visited at times a ≤ b < k² + k, the coordinate trapping property at d = b - a implies |k * r - k * q| ≤ b - a. Since a ≥ k² + q ≥ k² and b < k² + k, we have b - a < k. The only multiple of k strictly bounded by k in absolute value is 0, so k * q = k * r, which implies q = r.

    lines 121–138

    uses coordinate_after_target, coordinate_target_active, Fin.ext, lt_trichotomy, Nat.mul_le_mul_left, Nat.mul_add, Nat.mul_one

        (q r : Fin k) (ha : v a = Sum.inr q) (hbr : v b = Sum.inr r) : q = r := by
      have he : a + (b - a) = b := by omega
      have hh := coordinate_after_target hk v hv hpos a q ha (b - a) (by omega)
      rw [he, hbr] at hh
      have hractive := coordinate_target_active v hpos b r hbr
      simp only [coordinate, hractive, if_true] at hh
      have hd : b - a < k := by
        have := coordinate_target_active v hpos a q ha
        omega
      apply Fin.ext
      rcases lt_trichotomy q.val r.val with h | h | h
      · have hm : k * (q.val + 1) ≤ k * r.val := Nat.mul_le_mul_left k (by omega)
        rw [Nat.mul_add, Nat.mul_one] at hm
        omega
      · exact h
      · have hm : k * (r.val + 1) ≤ k * q.val := Nat.mul_le_mul_left k (by omega)
        rw [Nat.mul_add, Nat.mul_one] at hm
        omega
  8. The coordinate swap operation swap_at is an involution on vertices.

    Case analysis on the vertex: if v = (j, r) with r = 0, applying swap_at twice exchanges (j, 0) and Sum.inr j when k² + j ≤ t and restores them; if r ≠ 0 or k² + j > t, swap_at acts as the identity.

    lines 157–165

    uses Fin.ext

        Function.Involutive (swap_at hk t) := by
      intro v
      rcases v with ⟨j, r⟩ | j
      · by_cases hr : r.val = 0
        · have he : r = (⟨0, hk⟩ : Fin k) := Fin.ext hr
          subst r
          by_cases h : k * k + j.val ≤ t <;> simp [swap_at, h]
        · simp [swap_at, hr]
      · by_cases h : k * k + j.val ≤ t <;> simp [swap_at, h]
  9. The rank permutation value of a vertex at time t equals its coordinate at time t.

    Unfolding rank_equiv into swap_at followed by index_equiv, the definition matches the coordinate function in every case.

    lines 174–179

        (rank_equiv hk t v).val = coordinate t v := by
      change ((index_equiv k) (swap_at hk t v)).val = coordinate t v
      rcases v with ⟨j, r⟩ | j
      · by_cases h : r.val = 0 ∧ k * k + j.val ≤ t <;>
          simp [swap_at, coordinate, h]
      · by_cases h : k * k + j.val ≤ t <;> simp [swap_at, coordinate, h]
  10. Every temporal walk on the graph sequence lifts to a coordinate walk.

    At each step t, either the walk stays at the same vertex or moves along an edge of G(t). By definition of G(t) via pullback from pathGraph, adjacency means the rank coordinates differ by 1, which equals the coordinate difference at time t.

    lines 193–200

    uses congrArg, SimpleGraph.comap_adj, SimpleGraph.pathGraph_adj, Equiv.trans_apply, rank_coordinate

        coordinate_walk (fun t => (index_equiv k).symm (w t)) := by
      intro t
      rcases hw t with he | he
      · left
        exact congrArg (index_equiv k).symm he
      · right
        simpa only [graph, SimpleGraph.comap_adj, SimpleGraph.pathGraph_adj,
          order_fin, Equiv.trans_apply, rank_coordinate] using he
  11. Construction of the temporal graph, target set U, and start vertex s, verifying U has size k and all snapshots are spanning paths.

    The snapshot graphs G(t) are defined via order permutations, the target set U is the image of Fin k under the right injection into the vertex index, and s is the vertex (0, 0). Since the embedding is injective, |U| = k. Each snapshot graph is a spanning path by construction.

    lines 211–223

    uses Sum.inr.inj, Finset.card_image_of_injective, TemporalPathTargetTrap.graph_path

      classical
      have hkpos : 0 < k := by omega
      let z : Fin k := ⟨0, hkpos⟩
      let f : Fin k → Fin (k * k + k) := fun j =>
        (TemporalPathTargetTrap.index_equiv k) (Sum.inr j)
      let U : Finset (Fin (k * k + k)) := Finset.univ.image f
      let s := (TemporalPathTargetTrap.index_equiv k) (Sum.inl (z, z))
      have hinj : Function.Injective f := by
        intro i j hij
        exact Sum.inr.inj ((TemporalPathTargetTrap.index_equiv k).injective hij)
      refine ⟨TemporalPathTargetTrap.graph hkpos, U, s, ?_,
        TemporalPathTargetTrap.graph_path hkpos, ?_⟩
      · simp [U, Finset.card_image_of_injective _ hinj]
  12. Any walk from s lifts to a coordinate walk starting at coordinate 0, bounded by t at time t.

    Lifting w via index_equiv gives a coordinate walk v starting at coordinate 0. By `TemporalPathTargetTrap.coordinate_walk_position`, coordinate(t, v(t)) ≤ t for all t.

    lines 224–231

    uses TemporalPathTargetTrap.lifted_walk, Nat.mul_pos, TemporalPathTargetTrap.coordinate_walk_position

      · intro w hw0 hw
        let v : ℕ → TemporalPathTargetTrap.vertex k := fun t =>
          (TemporalPathTargetTrap.index_equiv k).symm (w t)
        have hv : TemporalPathTargetTrap.coordinate_walk v := TemporalPathTargetTrap.lifted_walk hkpos w hw
        have hv0 : TemporalPathTargetTrap.coordinate 0 (v 0) = 0 := by
          have hsq : 0 < k * k := Nat.mul_pos hkpos hkpos
          simp [v, hw0, s, z, TemporalPathTargetTrap.coordinate, show ¬ k * k ≤ 0 by omega]
        have hpos := TemporalPathTargetTrap.coordinate_walk_position hkpos v hv hv0
  13. Every temporal walk starting at s visits at most one target before time k² + k.

    If the walk visits target q at time a and target r at time b with a, b < k² + k, we apply `coordinate_two_targets_equal` to deduce q = r. Hence the visited vertices w(a) and w(b) must be identical.

    lines 232–247

    uses Finset.mem_image.mp, Equiv.symm_apply_apply, le_total, TemporalPathTargetTrap.coordinate_two_targets_equal, congrArg

        intro a ha b hb haU hbU
        obtain ⟨q, -, hq⟩ := Finset.mem_image.mp haU
        obtain ⟨r, -, hr⟩ := Finset.mem_image.mp hbU
        have hqa : v a = Sum.inr q := by
          dsimp [v]
          rw [← hq]
          exact (TemporalPathTargetTrap.index_equiv k).symm_apply_apply _
        have hrb : v b = Sum.inr r := by
          dsimp [v]
          rw [← hr]
          exact (TemporalPathTargetTrap.index_equiv k).symm_apply_apply _
        have hqr : q = r := by
          rcases le_total a b with hab | hba
          · exact TemporalPathTargetTrap.coordinate_two_targets_equal hkpos v hv hpos a b hab hb q r hqa hrb
          · exact (TemporalPathTargetTrap.coordinate_two_targets_equal hkpos v hv hpos b a hba ha r q hrb hqa).symm
        exact hq.symm.trans ((congrArg f hqr).trans hr)
Nat.zero_add
0 + n = n for any natural number n.
le_trans
Transitivity of the preorder: if a ≤ b and b ≤ c then a ≤ c.
Nat.le_max_right
For any natural numbers a and b, b ≤ max a b.
Nat.mul_lt_mul_of_pos_left
Multiplying both sides of a strict inequality by a strictly positive number preserves the strict inequality.
Nat.mul_le_mul_left
Multiplying both sides of an inequality by a natural number preserves the inequality.
Nat.succ_le_of_lt
If n < m, then n + 1 ≤ m.
Nat.mul_add
Multiplication distributes over addition on the right: n * (m + k) = n * m + n * k.
Nat.mul_one
Multiplying a natural number by one leaves it unchanged: n * 1 = n.
Fin.ext
Two elements of Fin n are equal if and only if their underlying natural values are equal.
lt_trichotomy
In a linear order, exactly one of a < b, a = b, or b < a holds.
congrArg
Applying a function to equal arguments yields equal results.
SimpleGraph.comap_adj
Two vertices are adjacent in a comap graph SimpleGraph.comap f G if and only if their images under f are adjacent in G.
SimpleGraph.pathGraph_adj
In the canonical path graph on Fin n, two vertices are adjacent if and only if their values differ by 1.
Equiv.trans_apply
Applying a composed equivalence (e₁ .trans e₂) is equivalent to applying e₁ and then e₂.
Sum.inr.inj
The right injection into a sum type is injective.
Finset.card_image_of_injective
The image of a finite set under an injective map has the same cardinality as the original set.
Nat.mul_pos
The product of two strictly positive natural numbers is strictly positive.
Equiv.symm_apply_apply
Applying an equivalence after its inverse yields the identity.
le_total
In a linear order, any two elements satisfy a ≤ b or b ≤ a.
coordinate_walk_bounds
In a coordinate walk, the walker's coordinate at time t changes by at most 1 between step t and step t + 1.
coordinate_step_bound
The coordinate of any vertex at time t + 1 is bounded by the maximum of its coordinate at time t and t + 1.
coordinate_step_fixed
If t ≥ k² + q and the coordinate of v at time t is strictly less than k * (q + 1), then the coordinate of v does not change from t to t + 1.
coordinate_target_active
If a walk visits target q at time a, then k² + q ≤ a.
coordinate_after_target
After visiting target q at time a, the walker's coordinate remains within distance d of k * q at time a + d, provided a + d < k² + k.
TemporalPathTargetTrap.coordinate_two_targets_equal
If a walk visits target q at time a and target r at time b with a ≤ b < k² + k, then q = r.
rank_coordinate
The rank equivalence assigns each vertex its coordinate at time t.
TemporalPathTargetTrap.graph_path
Each snapshot graph G(t) is a spanning path graph.
TemporalPathTargetTrap.lifted_walk
Every temporal walk on the graph sequence lifts to a coordinate walk on the vertex set.
TemporalPathTargetTrap.coordinate_walk_position
A coordinate walk starting at coordinate 0 stays bounded by t at time t.

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

namespace TemporalPathTargetTrapprivate abbrev vertex (k : ℕ) := (Fin k × Fin k) ⊕ Fin kprivate def coordinate {k : ℕ} (t : ℕ) : vertex k → ℕ  | Sum.inl (j, r) =>      if r.val = 0 ∧ k * k + j.val ≤ t then k * k + j.val else r.val + k * j.val  | Sum.inr j => if k * k + j.val ≤ t then k * j.val else k * k + j.valprivate theorem coordinate_step_bound {k : ℕ} (hk : 0 < k) (t : ℕ) (v : vertex k) :    coordinate (t + 1) v ≤ max (coordinate t v) (t + 1) := by  rcases v with ⟨j, r⟩ | j  · by_cases hr : r.val = 0    · simp only [coordinate, hr, true_and, Nat.zero_add]      by_cases h0 : k * k + j.val ≤ t      · have h1 : k * k + j.val ≤ t + 1 := by omega        simp [h0, h1]      · by_cases h1 : k * k + j.val ≤ t + 1        · simpa [h0, h1] using            le_trans h1 (Nat.le_max_right (k * j.val) (t + 1))        · simp [h0, h1]    · simp [coordinate, hr]  · have hj : k * j.val < k * k := Nat.mul_lt_mul_of_pos_left j.isLt hk    by_cases h0 : k * k + j.val ≤ t    · have h1 : k * k + j.val ≤ t + 1 := by omega      simp [coordinate, h0, h1]    · by_cases h1 : k * k + j.val ≤ t + 1      · simp only [coordinate, h0, h1, if_true, if_false]        exact le_trans (by omega) (Nat.le_max_right _ _)      · simp [coordinate, h0, h1]private theorem coordinate_step_fixed {k : ℕ} (hk : 0 < k) (q : Fin k)    (t : ℕ) (ht : k * k + q.val ≤ t) (v : vertex k)    (hv : coordinate t v < k * (q.val + 1)) :    coordinate (t + 1) v = coordinate t v := by  have hq : k * (q.val + 1) ≤ k * k :=    Nat.mul_le_mul_left k (Nat.succ_le_of_lt q.isLt)  rcases v with ⟨j, r⟩ | j  · by_cases hr : r.val = 0    · simp only [coordinate, hr, true_and, Nat.zero_add] at hv ⊢      by_cases h0 : k * k + j.val ≤ t      · have h1 : k * k + j.val ≤ t + 1 := by omega        simp [h0, h1]      · by_cases h1 : k * k + j.val ≤ t + 1        · have hj : q.val + 1 ≤ j.val := by omega          have hmul := Nat.mul_le_mul_left k hj          simp only [h0, if_false] at hv          omega        · simp [h0, h1]    · simp [coordinate, hr]  · by_cases h0 : k * k + j.val ≤ t    · have h1 : k * k + j.val ≤ t + 1 := by omega      simp [coordinate, h0, h1]    · simp only [coordinate, h0, if_false] at hv      omegaprivate def coordinate_walk {k : ℕ} (v : ℕ → vertex k) : Prop :=  ∀ t, v (t + 1) = v t ∨    coordinate t (v t) + 1 = coordinate t (v (t + 1)) ∨    coordinate t (v (t + 1)) + 1 = coordinate t (v t)private theorem coordinate_walk_bounds {k : ℕ} (v : ℕ → vertex k)    (hv : coordinate_walk v) (t : ℕ) :    coordinate t (v (t + 1)) ≤ coordinate t (v t) + 1 ∧      coordinate t (v t) ≤ coordinate t (v (t + 1)) + 1 := by  rcases hv t with he | he | he  · simp [he]  · omega  · omegaprivate theorem coordinate_walk_position {k : ℕ} (hk : 0 < k)    (v : ℕ → vertex k) (hv : coordinate_walk v)    (hv0 : coordinate 0 (v 0) = 0) :    ∀ t, coordinate t (v t) ≤ t := by  intro t  induction t with  | zero => omega  | succ t ih =>    have hm := (coordinate_walk_bounds v hv t).1    have hs := coordinate_step_bound hk t (v (t + 1))    omegaprivate theorem coordinate_target_active {k : ℕ} (v : ℕ → vertex k)    (hpos : ∀ t, coordinate t (v t) ≤ t) (a : ℕ) (q : Fin k)    (ha : v a = Sum.inr q) : k * k + q.val ≤ a := by  have hp := hpos a  rw [ha] at hp  by_cases h : k * k + q.val ≤ a  · exact h  · simp [coordinate, h] at hpprivate theorem coordinate_after_target {k : ℕ} (hk : 0 < k)    (v : ℕ → vertex k) (hv : coordinate_walk v)    (hpos : ∀ t, coordinate t (v t) ≤ t) (a : ℕ) (q : Fin k)    (ha : v a = Sum.inr q) :    ∀ d, a + d < k * k + k →      coordinate (a + d) (v (a + d)) ≤ k * q.val + d ∧      k * q.val ≤ coordinate (a + d) (v (a + d)) + d := by  have hactive := coordinate_target_active v hpos a q ha  intro d  induction d with  | zero => simp [ha, coordinate, hactive]  | succ d ih =>    intro hd    have hi := ih (by omega)    have hm := coordinate_walk_bounds v hv (a + d)    have hdlt : d + 1 < k := by omega    have hp : coordinate (a + d) (v (a + d + 1)) < k * (q.val + 1) := by      rw [Nat.mul_add, Nat.mul_one]      omega    have hfixed := coordinate_step_fixed hk q (a + d) (by omega)      (v (a + d + 1)) hp    have he : a + (d + 1) = a + d + 1 := by omega    rw [he, hfixed]    omegaprivate theorem coordinate_two_targets_equal {k : ℕ} (hk : 0 < k)    (v : ℕ → vertex k) (hv : coordinate_walk v)    (hpos : ∀ t, coordinate t (v t) ≤ t)    (a b : ℕ) (hab : a ≤ b) (hb : b < k * k + k)    (q r : Fin k) (ha : v a = Sum.inr q) (hbr : v b = Sum.inr r) : q = r := by  have he : a + (b - a) = b := by omega  have hh := coordinate_after_target hk v hv hpos a q ha (b - a) (by omega)  rw [he, hbr] at hh  have hractive := coordinate_target_active v hpos b r hbr  simp only [coordinate, hractive, if_true] at hh  have hd : b - a < k := by    have := coordinate_target_active v hpos a q ha    omega  apply Fin.ext  rcases lt_trichotomy q.val r.val with h | h | h  · have hm : k * (q.val + 1) ≤ k * r.val := Nat.mul_le_mul_left k (by omega)    rw [Nat.mul_add, Nat.mul_one] at hm    omega  · exact h  · have hm : k * (r.val + 1) ≤ k * q.val := Nat.mul_le_mul_left k (by omega)    rw [Nat.mul_add, Nat.mul_one] at hm    omegaprivate def index_equiv (k : ℕ) : vertex k ≃ Fin (k * k + k) :=  (Equiv.sumCongr (finProdFinEquiv : Fin k × Fin k ≃ Fin (k * k))    (Equiv.refl (Fin k))).trans finSumFinEquiv@[simp] private theorem index_inl {k : ℕ} (j r : Fin k) :    ((index_equiv k) (Sum.inl (j, r))).val = r.val + k * j.val := rfl@[simp] private theorem index_inr {k : ℕ} (j : Fin k) :    ((index_equiv k) (Sum.inr j)).val = k * k + j.val := rflprivate def swap_at {k : ℕ} (hk : 0 < k) (t : ℕ) : vertex k → vertex k  | Sum.inl (j, r) =>      if r.val = 0 ∧ k * k + j.val ≤ t then Sum.inr j else Sum.inl (j, r)  | Sum.inr j =>      if k * k + j.val ≤ t then Sum.inl (j, ⟨0, hk⟩) else Sum.inr jprivate theorem swap_at_involutive {k : ℕ} (hk : 0 < k) (t : ℕ) :    Function.Involutive (swap_at hk t) := by  intro v  rcases v with ⟨j, r⟩ | j  · by_cases hr : r.val = 0    · have he : r = (⟨0, hk⟩ : Fin k) := Fin.ext hr      subst r      by_cases h : k * k + j.val ≤ t <;> simp [swap_at, h]    · simp [swap_at, hr]  · by_cases h : k * k + j.val ≤ t <;> simp [swap_at, h]private def swap_equiv {k : ℕ} (hk : 0 < k) (t : ℕ) : vertex k ≃ vertex k :=  ⟨swap_at hk t, swap_at hk t, swap_at_involutive hk t, swap_at_involutive hk t⟩private def rank_equiv {k : ℕ} (hk : 0 < k) (t : ℕ) : vertex k ≃ Fin (k * k + k) :=  (swap_equiv hk t).trans (index_equiv k)@[simp] private theorem rank_coordinate {k : ℕ} (hk : 0 < k) (t : ℕ) (v : vertex k) :    (rank_equiv hk t v).val = coordinate t v := by  change ((index_equiv k) (swap_at hk t v)).val = coordinate t v  rcases v with ⟨j, r⟩ | j  · by_cases h : r.val = 0 ∧ k * k + j.val ≤ t <;>      simp [swap_at, coordinate, h]  · by_cases h : k * k + j.val ≤ t <;> simp [swap_at, coordinate, h]private def order_fin {k : ℕ} (hk : 0 < k) (t : ℕ) : Equiv.Perm (Fin (k * k + k)) :=  (index_equiv k).symm.trans (rank_equiv hk t)private def graph {k : ℕ} (hk : 0 < k) (t : ℕ) : SimpleGraph (Fin (k * k + k)) :=  (SimpleGraph.pathGraph (k * k + k)).comap (order_fin hk t)private theorem graph_path {k : ℕ} (hk : 0 < k) (t : ℕ) :    is_spanning_path_graph (graph hk t) :=  ⟨order_fin hk t, fun _ _ => SimpleGraph.pathGraph_adj⟩private theorem lifted_walk {k : ℕ} (hk : 0 < k)    (w : ℕ → Fin (k * k + k)) (hw : is_temporal_walk (graph hk) w) :    coordinate_walk (fun t => (index_equiv k).symm (w t)) := by  intro t  rcases hw t with he | he  · left    exact congrArg (index_equiv k).symm he  · right    simpa only [graph, SimpleGraph.comap_adj, SimpleGraph.pathGraph_adj,      order_fin, Equiv.trans_apply, rank_coordinate] using heend TemporalPathTargetTraptheorem temporal_path_many_targets_one_frame_trap (k : ℕ) (hk : 2 ≤ k) :    ∃ (G : ℕ → SimpleGraph (Fin (k * k + k)))      (U : Finset (Fin (k * k + k))) (s : Fin (k * k + k)),      U.card = k ∧ (∀ t, is_spanning_path_graph (G t)) ∧      ∀ w : ℕ → Fin (k * k + k), w 0 = s → is_temporal_walk G w →        ∀ a < k * k + k, ∀ b < k * k + k,          w a ∈ U → w b ∈ U → w a = w b := by  classical  have hkpos : 0 < k := by omega  let z : Fin k := ⟨0, hkpos⟩  let f : Fin k → Fin (k * k + k) := fun j =>    (TemporalPathTargetTrap.index_equiv k) (Sum.inr j)  let U : Finset (Fin (k * k + k)) := Finset.univ.image f  let s := (TemporalPathTargetTrap.index_equiv k) (Sum.inl (z, z))  have hinj : Function.Injective f := by    intro i j hij    exact Sum.inr.inj ((TemporalPathTargetTrap.index_equiv k).injective hij)  refine ⟨TemporalPathTargetTrap.graph hkpos, U, s, ?_,    TemporalPathTargetTrap.graph_path hkpos, ?_⟩  · simp [U, Finset.card_image_of_injective _ hinj]  · intro w hw0 hw    let v : ℕ → TemporalPathTargetTrap.vertex k := fun t =>      (TemporalPathTargetTrap.index_equiv k).symm (w t)    have hv : TemporalPathTargetTrap.coordinate_walk v := TemporalPathTargetTrap.lifted_walk hkpos w hw    have hv0 : TemporalPathTargetTrap.coordinate 0 (v 0) = 0 := by      have hsq : 0 < k * k := Nat.mul_pos hkpos hkpos      simp [v, hw0, s, z, TemporalPathTargetTrap.coordinate, show ¬ k * k ≤ 0 by omega]    have hpos := TemporalPathTargetTrap.coordinate_walk_position hkpos v hv hv0    intro a ha b hb haU hbU    obtain ⟨q, -, hq⟩ := Finset.mem_image.mp haU    obtain ⟨r, -, hr⟩ := Finset.mem_image.mp hbU    have hqa : v a = Sum.inr q := by      dsimp [v]      rw [← hq]      exact (TemporalPathTargetTrap.index_equiv k).symm_apply_apply _    have hrb : v b = Sum.inr r := by      dsimp [v]      rw [← hr]      exact (TemporalPathTargetTrap.index_equiv k).symm_apply_apply _    have hqr : q = r := by      rcases le_total a b with hab | hba      · exact TemporalPathTargetTrap.coordinate_two_targets_equal hkpos v hv hpos a b hab hb q r hqa hrb      · exact (TemporalPathTargetTrap.coordinate_two_targets_equal hkpos v hv hpos b a hba ha r q hrb hqa).symm    exact hq.symm.trans ((congrArg f hqr).trans hr)
See it in the graphDiscuss this resultChallenge it