AFTD Auto-Formalizing Theoretical Domains

three_by_cycle_torus_moving_target_accuracy_le_ceil

theoremverified

For 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 most (3 * n + 1) / 2 starting from the candidate set of all vertices.

Statement

theorem three_by_cycle_torus_moving_target_accuracy_le_ceil (n : ℕ) (hn : 3 ≤ n) :
    ∃ S : MovingTargetStrategy (Fin 3 × Fin n),
      moving_target_strategy_successful (torus_graph 3 n) ((3 * n + 1) / 2) S Finset.univ
Source
three_by_cycle_torus_moving_target_accuracy_exact
Verified
08 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4
  • 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,…
Used by 1

Read back from the Lean

For any natural number $n \ge 3$, there exists a moving target search strategy $S$ on the vertex set $\mathrm{Fin}(3) \times \mathrm{Fin}(n)$ that is successful for the 3-by-$n$ torus graph (the Cartesian product of cycle graphs $C_3 \mathbin{\square} C_n$) with target size bound $(3n + 1) / 2$ (i.e., $\lceil 3n/2 \rceil$) starting from the initial uncertainty set of all vertices ($\mathrm{Finset.univ}$).

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 proof constructs a simple one-query search strategy. Since the target is initially anywhere in the graph, its closed neighborhood after one step is still the entire vertex set of 3n vertices. The strategy queries an arbitrary vertex subset Q of size ⌈3n / 2⌉ = (3n + 1) / 2 and immediately stops: an affirmative answer leaves |Q| = (3n + 1) / 2 candidates, while a negative answer leaves 3n - (3n + 1) / 2 ≤ (3n + 1) / 2 candidates.

  1. The target bound (3 * n + 1) / 2 is at most the total vertex count of the torus, which is 3 * n.

    Under classical logic, the number of vertices in Fin 3 × Fin n simplifies to 3 * n. Substituting this cardinality into the bound inequality, linear integer arithmetic (`omega`) confirms that (3 * n + 1) / 2 ≤ 3 * n for all n.

    lines 8–13

      classical
      have hcard_univ : (Finset.univ : Finset (Fin 3 × Fin n)).card = 3 * n := by
        simp
      have hs_le : ((3 * n + 1) / 2) ≤ (Finset.univ : Finset (Fin 3 × Fin n)).card := by
        rw [hcard_univ]
        omega
  2. There exists a subset of vertices Q with cardinality exactly (3 * n + 1) / 2.

    Since (3 * n + 1) / 2 ≤ |Finset.univ|, `Finset.exists_subset_card_eq` guarantees the existence of a subset Q ⊆ Finset.univ with |Q| = (3 * n + 1) / 2.

    lines 14–16

    uses Finset.exists_subset_card_eq

      obtain ⟨Q, hQsub, hQcard⟩ :=
        Finset.exists_subset_card_eq (s := (Finset.univ : Finset (Fin 3 × Fin n)))
          (n := (3 * n + 1) / 2) hs_le
  3. It suffices to show success for the one-query strategy that queries Q and then halts.

    We provide an explicit search strategy: query membership in Q, and immediately stop searching in both the affirmative and negative branches.

    line 17

      refine ⟨MovingTargetStrategy.query Q MovingTargetStrategy.stop MovingTargetStrategy.stop, ?_⟩
  4. The success condition reduces to showing that both possible query outcomes leave at most (3 * n + 1) / 2 candidate vertices.

    Unfolding the definitions of strategy success and closed neighborhood, the candidate set after the target's move is the closed neighborhood of the entire vertex set, which is the entire vertex set itself. Querying Q partitions these candidates into Finset.univ \ Q (if the target is not in Q) and Finset.univ ∩ Q = Q (if the target is in Q). Splitting with `constructor`, we must check that whenever either outcome is non-empty, its cardinality is at most (3 * n + 1) / 2.

    lines 18–21

      simp only [moving_target_strategy_successful]
      simp only [closed_neighborhood]
      simp
      constructor
  5. If the target is not in Q, the remaining candidate set has size at most (3 * n + 1) / 2.

    Assuming Finset.univ \ Q is non-empty, `Finset.card_sdiff_add_card_eq_card` gives |Finset.univ \ Q| + |Q| = |Finset.univ|. Since |Finset.univ| = 3 * n and |Q| = (3 * n + 1) / 2, linear integer arithmetic (`omega`) shows |Finset.univ \ Q| = 3 * n - (3 * n + 1) / 2 ≤ (3 * n + 1) / 2.

    lines 22–25

    uses Finset.card_sdiff_add_card_eq_card

      · intro _
        have hdiff := Finset.card_sdiff_add_card_eq_card
          (s := Q) (t := (Finset.univ : Finset (Fin 3 × Fin n))) hQsub
        omega
  6. If the target is in Q, the remaining candidate set has size at most (3 * n + 1) / 2.

    Assuming Q is non-empty, rewriting by the definition of Q shows |Q| = (3 * n + 1) / 2 ≤ (3 * n + 1) / 2, which holds reflexively.

    lines 26–27

      · intro _
        rw [hQcard]
Finset.exists_subset_card_eq
A finite set contains a subset of any cardinality up to its own size.
Finset.card_sdiff_add_card_eq_card
For any subset s ⊆ t of a finite set t, the cardinalities satisfy |t \ s| + |s| = |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

noncomputable instance (priority := 10000) three_by_cycle_torus_moving_target_accuracy_le_ceil_decidableRel (n : ℕ) :    DecidableRel (torus_graph 3 n).Adj := Classical.decRel _/-- For every n ≥ 3, moving-target search on C_3 □ C_n achieves accuracy at most ceil(3n/2). -/theorem three_by_cycle_torus_moving_target_accuracy_le_ceil (n : ℕ) (hn : 3 ≤ n) :    ∃ S : MovingTargetStrategy (Fin 3 × Fin n),      moving_target_strategy_successful (torus_graph 3 n) ((3 * n + 1) / 2) S Finset.univ := by  classical  have hcard_univ : (Finset.univ : Finset (Fin 3 × Fin n)).card = 3 * n := by    simp  have hs_le : ((3 * n + 1) / 2) ≤ (Finset.univ : Finset (Fin 3 × Fin n)).card := by    rw [hcard_univ]    omega  obtain ⟨Q, hQsub, hQcard⟩ :=    Finset.exists_subset_card_eq (s := (Finset.univ : Finset (Fin 3 × Fin n)))      (n := (3 * n + 1) / 2) hs_le  refine ⟨MovingTargetStrategy.query Q MovingTargetStrategy.stop MovingTargetStrategy.stop, ?_⟩  simp only [moving_target_strategy_successful]  simp only [closed_neighborhood]  simp  constructor  · intro _    have hdiff := Finset.card_sdiff_add_card_eq_card      (s := Q) (t := (Finset.univ : Finset (Fin 3 × Fin n))) hQsub    omega  · intro _    rw [hQcard]
See it in the graphDiscuss this resultChallenge it