AFTD Auto-Formalizing Theoretical Domains

three_by_three_torus_moving_target_accuracy_exact

theoremverified

On the 3-by-3 torus C_3 □ C_3, the minimum achievable moving-target localization accuracy starting from the candidate set of all vertices is exactly 5.

Statement

theorem three_by_three_torus_moving_target_accuracy_exact :
    IsLeast {s : ℕ | ∃ S : MovingTargetStrategy (Fin 3 × Fin 3),
      moving_target_strategy_successful (torus_graph 3 3) s S Finset.univ} 5
Source
three_by_cycle_torus_moving_target_accuracy_exact
Verified
08 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 5
  • torus_graphThe M-by-N torus grid graph is the Cartesian box product of the cycle graph of length M and the cycle graph of length N on vertex set Fin…
  • MovingTargetStrategyAn inductive datatype MovingTargetStrategy parameterized by a type V : Type*, with two constructors: stop : MovingTargetStrategy V…
  • moving_target_strategy_successfulGiven a finite type V with decidable equality, a simple graph G on V with decidable adjacency, an accuracy threshold s : ℕ, a strategy…
  • closed_neighborhoodGiven a finite type V with decidable equality, a simple graph G on V with decidable adjacency, and a finite subset A : Finset V,…
  • three_by_cycle_torus_moving_target_accuracy_le_ceilFor every integer n ≥ 3, there exists an adaptive search strategy for a moving target on the 3-by-n torus C_3 □ C_n achieving accuracy at…

Read back from the Lean

5 is the least natural number $s$ such that there exists a finite decision-tree strategy $S$ (of type MovingTargetStrategy (Fin 3 × Fin 3)) that successfully guarantees tracking a moving target to within at most $s$ candidate locations on the $3 \times 3$ torus graph $C_3 \square C_3$, starting with the entire vertex set Finset.univ as the initial candidate set. In this model: - The graph is the Cartesian product of two 3-cycles, SimpleGraph.cycleGraph 3 □ SimpleGraph.cycleGraph 3, on vertices $\text{Fin } 3 \times \text{Fin } 3$. - A strategy is an inductive tree whose leaves are .stop and whose internal nodes query a subset $Q$ of vertices, branching into on_false and on_true. - Success with accuracy parameter $s$ starting from a candidate set $D$: - At .stop, the candidate set $D$ must satisfy $|D| \le s$. - At .query Q on_false on_true, the target first moves to its closed neighborhood $C = N[D]$ (any vertex equal to or adjacent to a vertex in $D$). Then, if $C \setminus Q$ is nonempty, on_false must succeed on $C \setminus Q$; and if $C \cap Q$ is nonempty, on_true must succeed on $C \cap Q$.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

The theorem proves that the minimum achievable moving-target localization accuracy on the 3-by-3 torus C_3 □ C_3 starting from the full candidate set is exactly 5. For the upper bound, an existing general theorem for C_3 □ C_n gives a strategy achieving accuracy ⌊(3 · 3 + 1)/2⌋ = 5. For the lower bound, an expansion principle shows that whenever every candidate set of size at least K expands to |N[D]| ≥ 2K - 1, any successful strategy must have accuracy at least K because an adversary can always force the branch containing at least K vertices. On C_3 □ C_3, any set D of size at least 5 expands to the entire 9-vertex graph because an excluded vertex would constrain D to avoid both coordinates, bounding |D| ≤ (3 - 1)(3 - 1) = 4.

  1. When the strategy terminates immediately without querying, the target localization accuracy satisfies K ≤ s.

    By structural induction on the strategy S. In the base case where S is the stop strategy, success means that the candidate set D has cardinality at most s (|D| ≤ s). Since K ≤ |D| by assumption, transitivity of ≤ gives K ≤ s.

    lines 8–11

    uses le_trans

      induction' S with Q on_false on_true ih_false ih_true
      · intro D s hD hsucc
        simp only [moving_target_strategy_successful] at hsucc
        exact le_trans hD hsucc
  2. In the query case, if K = 0, the inequality K ≤ s holds vacuously.

    For the inductive step where S queries a set Q, unfolding the success definition yields success hypotheses for both the branch where the target is not in Q and the branch where it is. If K = 0, then K ≤ s is immediate since 0 ≤ s for any natural number s.

    lines 12–16

    uses Nat.zero_le

      · intro D s hD hsucc
        simp only [moving_target_strategy_successful] at hsucc
        rcases hsucc with ⟨h_false, h_true⟩
        by_cases hK : K = 0
        · subst hK; exact Nat.zero_le s
  3. Assuming K > 0, at least one of the two updated candidate sets, N[D] \ Q or N[D] ∩ Q, has size at least K. automation

    By the expansion hypothesis, |N[D]| ≥ 2K - 1. The query set Q partitions the closed neighborhood N[D] into N[D] \ Q and N[D] ∩ Q, so the sum of their sizes is |N[D]|. If both sets had size strictly less than K, their sum would be at most 2(K - 1) = 2K - 2, contradicting |N[D]| ≥ 2K - 1. Linear arithmetic (omega) closes the contradiction.

    lines 17–22

    uses Finset.card_sdiff_add_card_inter

        have hexp := h_exp D hD
        have hsum : (closed_neighborhood G D \ Q).card + (closed_neighborhood G D ∩ Q).card =
            (closed_neighborhood G D).card := Finset.card_sdiff_add_card_inter (closed_neighborhood G D) Q
        have hor : K ≤ (closed_neighborhood G D \ Q).card ∨ K ≤ (closed_neighborhood G D ∩ Q).card := by
          by_contra! h
          omega
  4. In the query case, the inductive hypothesis implies K ≤ s.

    An adversary chooses whichever branch has size at least K. Since K > 0, that branch is nonempty, so the corresponding continuation of the strategy must succeed. Applying the inductive hypothesis to that branch yields K ≤ s in either case.

    lines 23–27

    uses Finset.card_pos.mp

        rcases hor with hleft | hright
        · have hne : (closed_neighborhood G D \ Q).Nonempty := Finset.card_pos.mp (by omega)
          exact ih_false _ s hleft (h_false hne)
        · have hne : (closed_neighborhood G D ∩ Q).Nonempty := Finset.card_pos.mp (by omega)
          exact ih_true _ s hright (h_true hne)
  5. To establish the neighborhood expansion property, it suffices to derive a contradiction from the existence of a vertex not in the closed neighborhood N[D].

    We aim to prove that N[D] is the universal set Finset.univ. By extensionality, it suffices to show every vertex v belongs to N[D]. We proceed by contradiction, assuming some vertex v is not in N[D].

    lines 32–35

    uses Finset.eq_univ_iff_forall

      have h_univ : closed_neighborhood (torus_graph 3 3) D = Finset.univ := by
        rw [Finset.eq_univ_iff_forall]
        intro v
        by_contra hv
  6. If a vertex v is not in N[D], every element u ∈ D must differ from v in both coordinates, so D ⊆ (univ.erase v.1) ×ˢ (univ.erase v.2).

    Let u ∈ D. If u.1 = v.1, then either u.2 = v.2 (so u = v ∈ N[D]) or u.2 ≠ v.2. In the latter case, because the 3-cycle C_3 is the complete graph K_3, u.2 is adjacent to v.2, making u adjacent to v in the torus C_3 □ C_3, so again v ∈ N[D]. Contradiction; thus u.1 ≠ v.1. A completely symmetric argument shows u.2 ≠ v.2. Hence u lies in the product of the two punctured 3-element coordinate sets.

    lines 36–67

    uses Finset.mem_product, Finset.mem_erase, Finset.mem_univ, Finset.mem_filter, Prod.ext, SimpleGraph.cycleGraph_three_eq_top

        have h_sub : D ⊆ (Finset.univ.erase v.1) ×ˢ (Finset.univ.erase v.2) := by
          intro u hu
          rw [Finset.mem_product, Finset.mem_erase, Finset.mem_erase]
          refine ⟨⟨?_, Finset.mem_univ _⟩, ⟨?_, Finset.mem_univ _⟩⟩
          · intro hu1
            apply hv
            rw [closed_neighborhood, Finset.mem_filter]
            refine ⟨Finset.mem_univ _, ⟨u, hu, ?_⟩⟩
            by_cases h2 : u.2 = v.2
            · left
              exact Prod.ext hu1 h2
            · right
              change (SimpleGraph.cycleGraph 3).Adj u.1 v.1 ∧ u.2 = v.2 ∨
                     (SimpleGraph.cycleGraph 3).Adj u.2 v.2 ∧ u.1 = v.1
              right
              refine ⟨?_, hu1⟩
              rw [SimpleGraph.cycleGraph_three_eq_top]
              exact h2
          · intro hu2
            apply hv
            rw [closed_neighborhood, Finset.mem_filter]
            refine ⟨Finset.mem_univ _, ⟨u, hu, ?_⟩⟩
            by_cases h1 : u.1 = v.1
            · left
              exact Prod.ext h1 hu2
            · right
              change (SimpleGraph.cycleGraph 3).Adj u.1 v.1 ∧ u.2 = v.2 ∨
                     (SimpleGraph.cycleGraph 3).Adj u.2 v.2 ∧ u.1 = v.1
              left
              refine ⟨?_, hu2⟩
              rw [SimpleGraph.cycleGraph_three_eq_top]
              exact h1
  7. The closed neighborhood of D is the entire vertex set of the torus, N[D] = Finset.univ. automation

    The product set (univ.erase v.1) ×ˢ (univ.erase v.2) has size (3 - 1) * (3 - 1) = 4. Since D is a subset of this product, |D| ≤ 4, which contradicts the hypothesis 5 ≤ |D|. Thus no such excluded vertex v exists, proving N[D] = Finset.univ. Linear arithmetic (omega) finishes the contradiction.

    lines 68–74

    uses Finset.card_product, Finset.card_erase_of_mem, Finset.mem_univ, Finset.card_le_card

        have hcard : ((Finset.univ.erase v.1) ×ˢ (Finset.univ.erase v.2) : Finset (Fin 3 × Fin 3)).card = 4 := by
          rw [Finset.card_product, Finset.card_erase_of_mem (Finset.mem_univ _),
              Finset.card_erase_of_mem (Finset.mem_univ _)]
          simp
        have hle := Finset.card_le_card h_sub
        rw [hcard] at hle
        omega
  8. The expansion inequality 2 * 5 ≤ |N[D]| + 1 holds for any D with 5 ≤ |D|. automation

    Since N[D] is the full vertex set, its cardinality is 3 * 3 = 9. The inequality 2 * 5 ≤ 9 + 1 simplifies to 10 ≤ 10, which holds immediately.

    lines 75–76

      rw [h_univ]
      simp
  9. Accuracy 5 is achievable by a moving-target localization strategy on C_3 □ C_3.

    A general upper-bound theorem provides a successful strategy on C_3 □ C_n with accuracy ⌊(3n + 1)/2⌋. Evaluating this bound for n = 3 gives (3 * 3 + 1) / 2 = 5.

    lines 82–84

    uses three_by_cycle_torus_moving_target_accuracy_le_ceil

      refine ⟨?_, ?_⟩
      · change ∃ S, moving_target_strategy_successful (torus_graph 3 3) 5 S Finset.univ
        exact three_by_cycle_torus_moving_target_accuracy_le_ceil 3 (by norm_num)
  10. The minimum achievable moving-target localization accuracy on C_3 □ C_3 is exactly 5.

    The candidate set of all vertices has size 9, which is at least 5. Combining the expansion lower bound with the neighborhood expansion lemma shows that any successful strategy must have accuracy s ≥ 5. Since accuracy 5 is achievable, 5 is the least element of achievable accuracies.

    lines 85–91

    uses three_by_three_torus_moving_target_accuracy_exact_expansion_lower_bound, three_by_three_torus_moving_target_accuracy_exact_neighborhood_expansion

      · rintro s ⟨S, hS⟩
        have huniv_card : (Finset.univ : Finset (Fin 3 × Fin 3)).card = 9 := by simp
        have hK_le : 5 ≤ (Finset.univ : Finset (Fin 3 × Fin 3)).card := by
          rw [huniv_card]
          omega
        exact three_by_three_torus_moving_target_accuracy_exact_expansion_lower_bound (torus_graph 3 3) 5
          three_by_three_torus_moving_target_accuracy_exact_neighborhood_expansion S Finset.univ s hK_le hS
le_trans
Transitivity of inequality: if a ≤ b and b ≤ c, then a ≤ c.
Nat.zero_le
Zero is less than or equal to any natural number.
Finset.card_sdiff_add_card_inter
For any finite sets s and t, |s \ t| + |s ∩ t| = |s|.
Finset.card_pos.mp
A finite set with strictly positive cardinality is nonempty.
Finset.eq_univ_iff_forall
A subset of a finite type equals the universal set if and only if every element of the type belongs to it.
Finset.mem_product
An element belongs to a Cartesian product s ×ˢ t if and only if its first coordinate is in s and its second coordinate is in t.
Finset.mem_erase
An element belongs to s.erase b if and only if it belongs to s and is not equal to b.
Finset.mem_univ
Every element of a finite type belongs to the universal finset univ.
Finset.mem_filter
An element belongs to Finset.filter p s if and only if it belongs to s and satisfies the predicate p.
Prod.ext
Two ordered pairs are equal if and only if their first coordinates are equal and their second coordinates are equal.
SimpleGraph.cycleGraph_three_eq_top
The 3-cycle graph C_3 is equal to the complete graph on 3 vertices (every pair of distinct vertices is adjacent).
Finset.card_product
The cardinality of the Cartesian product of two finite sets is the product of their cardinalities.
Finset.card_erase_of_mem
Removing an element from a finite set containing it decreases its cardinality by 1.
Finset.card_le_card
If s ⊆ t for finite sets, then |s| ≤ |t|.
three_by_cycle_torus_moving_target_accuracy_le_ceil
On the torus C_3 □ C_n with n ≥ 3, there exists a successful moving-target strategy achieving accuracy at most ⌊(3n + 1)/2⌋.
three_by_three_torus_moving_target_accuracy_exact_expansion_lower_bound
If every candidate set of size at least K expands so that 2K ≤ |N[D]| + 1, then every successful moving-target strategy starting from a set of size at least K requires accuracy at least K.
three_by_three_torus_moving_target_accuracy_exact_neighborhood_expansion
On the 3-by-3 torus, every candidate set of size at least 5 has a closed neighborhood satisfying 2 * 5 ≤ |N[D]| + 1.

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

theorem three_by_three_torus_moving_target_accuracy_exact_expansion_lower_bound    {V : Type*} [Fintype V] [DecidableEq V]    (G : SimpleGraph V) [DecidableRel G.Adj] (K : ℕ)    (h_exp : ∀ D : Finset V, K ≤ D.card → 2 * K ≤ (closed_neighborhood G D).card + 1)    (S : MovingTargetStrategy V) :    ∀ (D : Finset V) (s : ℕ), K ≤ D.card →      moving_target_strategy_successful G s S D → K ≤ s := by  induction' S with Q on_false on_true ih_false ih_true  · intro D s hD hsucc    simp only [moving_target_strategy_successful] at hsucc    exact le_trans hD hsucc  · intro D s hD hsucc    simp only [moving_target_strategy_successful] at hsucc    rcases hsucc with ⟨h_false, h_true⟩    by_cases hK : K = 0    · subst hK; exact Nat.zero_le s    have hexp := h_exp D hD    have hsum : (closed_neighborhood G D \ Q).card + (closed_neighborhood G D ∩ Q).card =        (closed_neighborhood G D).card := Finset.card_sdiff_add_card_inter (closed_neighborhood G D) Q    have hor : K ≤ (closed_neighborhood G D \ Q).card ∨ K ≤ (closed_neighborhood G D ∩ Q).card := by      by_contra! h      omega    rcases hor with hleft | hright    · have hne : (closed_neighborhood G D \ Q).Nonempty := Finset.card_pos.mp (by omega)      exact ih_false _ s hleft (h_false hne)    · have hne : (closed_neighborhood G D ∩ Q).Nonempty := Finset.card_pos.mp (by omega)      exact ih_true _ s hright (h_true hne)theorem three_by_three_torus_moving_target_accuracy_exact_neighborhood_expansion    (D : Finset (Fin 3 × Fin 3)) (hD : 5 ≤ D.card) :    2 * 5 ≤ (closed_neighborhood (torus_graph 3 3) D).card + 1 := by  have h_univ : closed_neighborhood (torus_graph 3 3) D = Finset.univ := by    rw [Finset.eq_univ_iff_forall]    intro v    by_contra hv    have h_sub : D ⊆ (Finset.univ.erase v.1) ×ˢ (Finset.univ.erase v.2) := by      intro u hu      rw [Finset.mem_product, Finset.mem_erase, Finset.mem_erase]      refine ⟨⟨?_, Finset.mem_univ _⟩, ⟨?_, Finset.mem_univ _⟩⟩      · intro hu1        apply hv        rw [closed_neighborhood, Finset.mem_filter]        refine ⟨Finset.mem_univ _, ⟨u, hu, ?_⟩⟩        by_cases h2 : u.2 = v.2        · left          exact Prod.ext hu1 h2        · right          change (SimpleGraph.cycleGraph 3).Adj u.1 v.1 ∧ u.2 = v.2 ∨                 (SimpleGraph.cycleGraph 3).Adj u.2 v.2 ∧ u.1 = v.1          right          refine ⟨?_, hu1⟩          rw [SimpleGraph.cycleGraph_three_eq_top]          exact h2      · intro hu2        apply hv        rw [closed_neighborhood, Finset.mem_filter]        refine ⟨Finset.mem_univ _, ⟨u, hu, ?_⟩⟩        by_cases h1 : u.1 = v.1        · left          exact Prod.ext h1 hu2        · right          change (SimpleGraph.cycleGraph 3).Adj u.1 v.1 ∧ u.2 = v.2 ∨                 (SimpleGraph.cycleGraph 3).Adj u.2 v.2 ∧ u.1 = v.1          left          refine ⟨?_, hu2⟩          rw [SimpleGraph.cycleGraph_three_eq_top]          exact h1    have hcard : ((Finset.univ.erase v.1) ×ˢ (Finset.univ.erase v.2) : Finset (Fin 3 × Fin 3)).card = 4 := by      rw [Finset.card_product, Finset.card_erase_of_mem (Finset.mem_univ _),          Finset.card_erase_of_mem (Finset.mem_univ _)]      simp    have hle := Finset.card_le_card h_sub    rw [hcard] at hle    omega  rw [h_univ]  simp/-- The minimum achievable moving-target accuracy on C_3 □ C_3 is exactly 5. -/theorem three_by_three_torus_moving_target_accuracy_exact :    IsLeast {s : ℕ | ∃ S : MovingTargetStrategy (Fin 3 × Fin 3),      moving_target_strategy_successful (torus_graph 3 3) s S Finset.univ} 5 := by  refine ⟨?_, ?_⟩  · change ∃ S, moving_target_strategy_successful (torus_graph 3 3) 5 S Finset.univ    exact three_by_cycle_torus_moving_target_accuracy_le_ceil 3 (by norm_num)  · rintro s ⟨S, hS⟩    have huniv_card : (Finset.univ : Finset (Fin 3 × Fin 3)).card = 9 := by simp    have hK_le : 5 ≤ (Finset.univ : Finset (Fin 3 × Fin 3)).card := by      rw [huniv_card]      omega    exact three_by_three_torus_moving_target_accuracy_exact_expansion_lower_bound (torus_graph 3 3) 5      three_by_three_torus_moving_target_accuracy_exact_neighborhood_expansion S Finset.univ s hK_le hS
See it in the graphDiscuss this resultChallenge it