Tao's finite-checking theorem (speeds )
OpenLonelyRunnerConjecture.tao_finite_checkingcombinatoricsdiophantine-approximationnumber-theory
There is a constant such that for every the following are equivalent: (i) the conjecture holds for all ; (ii) it holds for all and every -tuple of positive distinct integer speeds with . Thus each fixed case is decidable by a finite check.
Formalization Note Tao's "explicitly computable" constant is a meta-property, stated here as ∃ C > 0; nonzero integer speeds reduce to positive by . The bound uses real exponentiation Real.rpow.
Preamble
import Mathlib import Definitions.Def_LonelyRunnerConjecture_Defs
Formal statement
namespace LonelyRunnerConjecture
theorem tao_finite_checking :
∃ C : ℝ, 0 < C ∧ ∀ n₀ : ℕ, 1 ≤ n₀ →
((∀ n : ℕ, n ≤ n₀ → LRC n) ↔
(∀ n : ℕ, n ≤ n₀ → ∀ v : Fin n → ℕ, (∀ i, 0 < v i) →
Function.Injective v →
(∀ i, (v i : ℝ) ≤ (n : ℝ) ^ (C * (n : ℝ) ^ 2)) →
∃ t : ℝ, ∀ i, (1 : ℝ) / (n + 1 : ℝ) ≤ distToNearestInt (t * (v i : ℝ)))) := by sorry
end LonelyRunnerConjectureSource
T. Tao, Some remarks on the lonely runner conjecture, https://arxiv.org/abs/1701.02048 (v4), Theorem 1.3.
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.