Periodic multidimensional Costas arrays (Rubio–Torres)
DefinitionPeriodicCostasArrayMultidimensional (periodic) Costas arrays in the sense of Rubio–Torres, Definitions 2–4. Write , , , .
IsPermutationArray a b φ: , all sides , and is a bijection .dots: points with .periodicDots: points whose coordinatewise reduction is a dot.window a b t: the translate .NoRepeatedDifferences D: for distinct , the vector determines the pair.IsCostas: a permutation array whose dots have no repeated differences.IsPeriodicCostas: Costas, and for every the periodic dots inwindow a b thave no repeated differences.
A point is a pair of integer vectors; is a total function whose values off are unused. Differences are not reduced modulo the sides.
import Mathlib
namespace PeriodicCostas
/-- The hyper-rectangle `[n_1] × ⋯ × [n_r] ⊆ ℤ^r`, where `[n] = {1, …, n}`. -/
def box {r : ℕ} (n : Fin r → ℕ) : Set (Fin r → ℤ) :=
{x | ∀ i, 1 ≤ x i ∧ x i ≤ (n i : ℤ)}
/-- `x ↦ x_Λ`: the unique point of `[n_1] × ⋯ × [n_r]` congruent to `x` modulo `n_i`
in every coordinate `i` (for `n_i ≥ 1`). -/
def reduce {r : ℕ} (n : Fin r → ℕ) (x : Fin r → ℤ) : Fin r → ℤ :=
fun i => (x i - 1) % (n i : ℤ) + 1
/-- The `m`-dimensional permutation array (Definition 2), with `m = k + l`, of size
`a_1 × ⋯ × a_k × b_1 × ⋯ × b_l` defined by `φ : [a_1] × ⋯ × [a_k] → [b_1] × ⋯ × [b_l]`:
every side length is at least `2` and `φ` is a bijection between the two boxes. -/
def IsPermutationArray {k l : ℕ} (a : Fin k → ℕ) (b : Fin l → ℕ)
(φ : (Fin k → ℤ) → (Fin l → ℤ)) : Prop :=
1 ≤ k ∧ 1 ≤ l ∧ (∀ i, 2 ≤ a i) ∧ (∀ j, 2 ≤ b j) ∧ Set.BijOn φ (box a) (box b)
/-- The dots of the array: the points `(x, y)` of the index set `Λ = [a] × [b]`
with `φ x = y`. A point of `ℤ^m` is written as a pair `(x, y) ∈ ℤ^k × ℤ^l`. -/
def dots {k l : ℕ} (a : Fin k → ℕ) (b : Fin l → ℕ) (φ : (Fin k → ℤ) → (Fin l → ℤ)) :
Set ((Fin k → ℤ) × (Fin l → ℤ)) :=
{p | p.1 ∈ box a ∧ p.2 ∈ box b ∧ φ p.1 = p.2}
/-- The dots of the periodic extension `Ã(α) = A(α_Λ)` to `ℤ^m`. -/
def periodicDots {k l : ℕ} (a : Fin k → ℕ) (b : Fin l → ℕ)
(φ : (Fin k → ℤ) → (Fin l → ℤ)) : Set ((Fin k → ℤ) × (Fin l → ℤ)) :=
{p | (reduce a p.1, reduce b p.2) ∈ dots a b φ}
/-- The window `t + Λ` of size `a_1 × ⋯ × a_k × b_1 × ⋯ × b_l` with corner offset `t ∈ ℤ^m`. -/
def window {k l : ℕ} (a : Fin k → ℕ) (b : Fin l → ℕ) (t : (Fin k → ℤ) × (Fin l → ℤ)) :
Set ((Fin k → ℤ) × (Fin l → ℤ)) :=
{p | p.1 - t.1 ∈ box a ∧ p.2 - t.2 ∈ box b}
/-- A set of points has no repeated difference vectors: the difference vectors `ω - α`
over ordered pairs `(α, ω)` of distinct points are pairwise distinct. -/
def NoRepeatedDifferences {V : Type*} [AddGroup V] (D : Set V) : Prop :=
∀ α ∈ D, ∀ ω ∈ D, ∀ α' ∈ D, ∀ ω' ∈ D,
α ≠ ω → α' ≠ ω' → ω - α = ω' - α' → α = α' ∧ ω = ω'
/-- Definition 3: an `m`-dimensional Costas array (a permutation array with no repeated
difference vectors). -/
def IsCostas {k l : ℕ} (a : Fin k → ℕ) (b : Fin l → ℕ)
(φ : (Fin k → ℤ) → (Fin l → ℤ)) : Prop :=
IsPermutationArray a b φ ∧ NoRepeatedDifferences (dots a b φ)
/-- Definition 4: a periodic Costas array — a Costas array such that every window
`t + Λ` (`t ∈ ℤ^m`) of its periodic extension has no repeated difference vectors. -/
def IsPeriodicCostas {k l : ℕ} (a : Fin k → ℕ) (b : Fin l → ℕ)
(φ : (Fin k → ℤ) → (Fin l → ℤ)) : Prop :=
IsCostas a b φ ∧
∀ t : (Fin k → ℤ) × (Fin l → ℤ), NoRepeatedDifferences (periodicDots a b φ ∩ window a b t)
end PeriodicCostas
Read-back
What the Lean code literally says, in plain math · claude-opus-5-5
This item (namespace PeriodicCostas) introduces seven definitions. Throughout, are natural numbers, points of are integer vectors , and a point of with is written as a pair .
1. Box. For ,
If some the box is empty; if the box is the one-point set .
2. Reduction. For and , is the vector with coordinates
where is the integer remainder that is non-negative (Euclidean remainder) when . For this is the unique element of congruent to mod . Junk case: when , the remainder modulo is itself, so (no reduction).
3. Permutation array. Given , and an arbitrary function (defined on all of ; only its values on matter below), holds iff all of:
- and ;
- for every and for every ;
- is a bijection from onto : it maps into , is injective on , and every point of is the image of some point of . (In particular this forces .)
4. Dots. , i.e. the graph of restricted to (and to values in ).
5. Periodic dots. , where and . When all the reduced points automatically lie in the boxes, so this is the set of with . (If some side is , the box is empty and so is this set.)
6. Window. For an offset ,
7. No repeated differences. For a set in an additive group , means: for all with and ,
That is, the map is injective on ordered pairs of distinct points of . Empty sets and singletons satisfy it vacuously.
8. Costas array. holds iff holds and holds in the group (componentwise subtraction).
9. Periodic Costas array. holds iff holds and, for every offset ,
So every translate of the box, intersected with the periodic extension of the dot set (period in the -th -coordinate and in the -th -coordinate), must have pairwise distinct difference vectors. The condition ranges over all integer offsets , including (which recovers the dots of the original array).
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.