three_by_cycle_torus_moving_target_accuracy_le_ceil
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
MovingTargetStrategyparameterized by a typeV : 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
- three_by_three_torus_moving_target_accuracy_exactOn the 3-by-3 torus C_3 □ C_3, the minimum achievable moving-target localization accuracy starting from the candidate set of all vertices…
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.
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.
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
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.
uses
Finset.exists_subset_card_eqobtain ⟨Q, hQsub, hQcard⟩ := Finset.exists_subset_card_eq (s := (Finset.univ : Finset (Fin 3 × Fin n))) (n := (3 * n + 1) / 2) hs_leIt 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.
refine ⟨MovingTargetStrategy.query Q MovingTargetStrategy.stop MovingTargetStrategy.stop, ?_⟩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.
simp only [moving_target_strategy_successful] simp only [closed_neighborhood] simp constructor
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.
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
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.
· 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|.
- The theorem statement is specialized to the 3-by-n torus C_3 □ C_n, but the proof does not rely on any structural properties of the torus graph other than reflexivity of the closed neighborhood (every vertex is in its own closed neighborhood). Because the initial candidate set is the entire vertex set, its closed neighborhood is also the entire vertex set, so a single query of size ⌈3n / 2⌉ achieves the accuracy bound in one step without any multi-round search.
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
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]