Squares in arithmetic progressions: , , , , and index-set equivalence
DefinitionRudinSquares_Defsarithmetic-progressionsdefinitionsnumber-theorysquares
Foundational definitions for the formalization of González-Jiménez–Xarles on Rudin's conjecture. For integers with , the arithmetic progression is , . Write and . Then counts the squares among the first terms, and is the maximum over non-trivial progressions. The generalized pentagonal numbers are () and the triangular numbers (). For a finite index set , and (an extended natural, when infinite). Two finite index sets are equivalent, , when related by a chain of integer translations and nonzero rational dilations preserving integrality. These notions are shared by every theorem of the mission.
Definition code
import Mathlib
set_option autoImplicit false
namespace RudinSquares
/-- `IsSq x` means that the integer `x` is a perfect square, i.e. `x = k*k` for some `k : ℤ`.
In particular `0` is a square and negative integers are not. -/
def IsSq (x : ℤ) : Prop := ∃ k : ℤ, x = k * k
/-- `S q a` is the set of positions `n : ℕ` at which the arithmetic progression `q*n + a`
takes a square value. -/
def S (q a : ℤ) : Set ℕ := {n : ℕ | IsSq (q * (n : ℤ) + a)}
/-- `SN N q a` is the set of square positions of `q*n + a` among `n = 0, …, N-1`. -/
def SN (N : ℕ) (q a : ℤ) : Set ℕ := S q a ∩ {n : ℕ | n < N}
/-- `Qap N q a`, written `Q(N; q, a)` in the source, is the number of squares among
`q*n + a` for `n = 0, …, N-1`. -/
noncomputable def Qap (N : ℕ) (q a : ℤ) : ℕ := (SN N q a).ncard
/-- `Q N`, written `Q(N)` in the source, is the maximum of `Q(N; q, a)` over all
non-trivial arithmetic progressions (`q ≠ 0`). -/
noncomputable def Q (N : ℕ) : ℕ := sSup {c : ℕ | ∃ q a : ℤ, q ≠ 0 ∧ Qap N q a = c}
/-- `GP k = k(3k-1)/2` is the `k`-th generalized pentagonal number (`k : ℤ`). -/
def GP (k : ℤ) : ℤ := k * (3 * k - 1) / 2
/-- `T k = k(k+1)/2` is the `k`-th triangular number (`k : ℕ`). -/
def T (k : ℕ) : ℕ := k * (k + 1) / 2
/-- `Zset I`, written `Z_I` in the source, is the set of pairs `(q, a)` of integers with
squarefree `gcd(q, a)`, `q ≠ 0`, such that `q*i + a` is a square for every `i ∈ I`. -/
def Zset (I : Finset ℤ) : Set (ℤ × ℤ) :=
{p : ℤ × ℤ | Squarefree (Int.gcd p.1 p.2) ∧ p.1 ≠ 0 ∧ ∀ i ∈ I, IsSq (p.1 * i + p.2)}
/-- `z I`, written `z_I` in the source, is the cardinality of `Z_I` as an extended natural
number (`⊤` when `Z_I` is infinite). -/
noncomputable def z (I : Finset ℤ) : ℕ∞ := (Zset I).encard
/-- `GenEq I J` is the equivalence relation on finite subsets of `ℤ` generated by
integer translation and by dilation by a nonzero rational that keeps every element integral.
It is the relation `I ∼ J` of the source. -/
inductive GenEq : Finset ℤ → Finset ℤ → Prop
| refl (I : Finset ℤ) : GenEq I I
| symm {I J : Finset ℤ} : GenEq I J → GenEq J I
| trans {I J K : Finset ℤ} : GenEq I J → GenEq J K → GenEq I K
| translate (I : Finset ℤ) (j : ℤ) : GenEq I (I.image (fun x => x + j))
| dilate {I J : Finset ℤ} (r : ℚ) (hr : r ≠ 0)
(hIJ : ∀ i ∈ I, ∃ j ∈ J, (j : ℚ) = r * (i : ℚ))
(hJI : ∀ j ∈ J, ∃ i ∈ I, (j : ℚ) = r * (i : ℚ)) : GenEq I J
end RudinSquaresSource
E. González-Jiménez and X. Xarles, 'On a conjecture of Rudin on squares in arithmetic progressions', LMS J. Comput. Math. 17(1) (2014) 58–76, doi:10.1112/S1461157013000259, §1.1 (Notation), p. 59; §2, p. 59–60.
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.