three_by_three_torus_moving_target_accuracy_exact
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
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,…
- 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.
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.
uses
le_transinduction' 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
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.
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
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.
uses
Finset.card_sdiff_add_card_interhave 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
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.
uses
Finset.card_pos.mprcases 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)
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].
uses
Finset.eq_univ_iff_forallhave h_univ : closed_neighborhood (torus_graph 3 3) D = Finset.univ := by rw [Finset.eq_univ_iff_forall] intro v by_contra hv
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.
uses
Finset.mem_product,Finset.mem_erase,Finset.mem_univ,Finset.mem_filter,Prod.ext,SimpleGraph.cycleGraph_three_eq_tophave 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
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.
uses
Finset.card_product,Finset.card_erase_of_mem,Finset.mem_univ,Finset.card_le_cardhave 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
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.
rw [h_univ] simp
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.
uses
three_by_cycle_torus_moving_target_accuracy_le_ceilrefine ⟨?_, ?_⟩ · 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)
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.
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.
- The proof formalizes the search game via an inductive strategy tree, where each query partitions the expanded candidate set and an adversary can always force the branch with at least K vertices.
- The key graph-theoretic fact that any set of size at least 5 on C_3 □ C_3 has closed neighborhood equal to the entire vertex set is proved by showing that C_3 = K_3, so any vertex outside the neighborhood would force all elements of D to avoid both coordinates of that vertex.
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.
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