Reduced residue representatives and residue fibres
DefinitionGreenTaoPort_Wikipedia_GreenTao_Primes_ReducedResiduesarithmetic-progressionsgreen-tao-port-8822number-theory
For a natural modulus , the reduced residue representatives are the integers with and . In particular this set is empty when .
For a finite set and natural parameters , the residue fibre is
Applications use a positive modulus and its standard representatives. The formal definition is total: at modulus zero the natural-number remainder convention is .
Definition code
import Mathlib.Combinatorics.Pigeonhole
import Mathlib.Data.Nat.Totient
import Mathlib.Data.ZMod.Basic
import Mathlib.NumberTheory.Primorial
import Lean
set_option autoImplicit true
set_option relaxedAutoImplicit false
set_option maxSynthPendingDepth 3
namespace Wikipedia.SzemeredisTheorem
open Finset
/-- The reduced residue system modulo `W`, represented by its standard
natural-number representatives in `[0, W)`. -/
def reducedResidues (W : ℕ) : Finset ℕ :=
{b ∈ Finset.range W | W.Coprime b}
/-- The elements of `S` lying in the standard residue class `b` modulo
`W`. -/
def residueFiber (S : Finset ℕ) (W b : ℕ) : Finset ℕ :=
{n ∈ S | n % W = b}
end Wikipedia.SzemeredisTheorem
/- Materialize compiler-generated declarations promised by this bundle. -/
run_meta do
for requiredName in #[
`Wikipedia.SzemeredisTheorem.reducedResidues.eq_1,
`Wikipedia.SzemeredisTheorem.residueFiber.eq_1
] do
let actualName ← Lean.realizeGlobalConstNoOverloadCore requiredName
unless actualName == requiredName do
throwError "Generated companion resolved to an unexpected name"
Source