Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Periodic multidimensional Costas arrays (Rubio–Torres)

Definition
PeriodicCostasArray

by shivm · Oct 4, 2026 · Mathlib 0df444a (Lean v4.33.1)

combinatoricscostas-arrays

Multidimensional (periodic) Costas arrays in the sense of Rubio–Torres, Definitions 2–4. Write [n]={1,…,n}[n]=\{1,\dots,n\}[n]={1,…,n}, X=[a1]×⋯×[ak]X=[a_1]\times\cdots\times[a_k]X=[a1​]×⋯×[ak​], Y=[b1]×⋯×[bl]Y=[b_1]\times\cdots\times[b_l]Y=[b1​]×⋯×[bl​], Λ=X×Y\Lambda=X\times YΛ=X×Y.

  • IsPermutationArray a b φ: k,l≥1k,l\ge1k,l≥1, all sides ≥2\ge2≥2, and φ\varphiφ is a bijection X→YX\to YX→Y.
  • dots: points (x,y)∈Λ(x,y)\in\Lambda(x,y)∈Λ with φ(x)=y\varphi(x)=yφ(x)=y.
  • periodicDots: points p∈Zk+lp\in\mathbb Z^{k+l}p∈Zk+l whose coordinatewise reduction ((pi−1) mod ni)+1((p_i-1)\bmod n_i)+1((pi​−1)modni​)+1 is a dot.
  • window a b t: the translate t+Λt+\Lambdat+Λ.
  • NoRepeatedDifferences D: for distinct α,ω∈D\alpha,\omega\in Dα,ω∈D, the vector ω−α\omega-\alphaω−α determines the pair.
  • IsCostas: a permutation array whose dots have no repeated differences.
  • IsPeriodicCostas: Costas, and for every ttt the periodic dots in window a b t have no repeated differences.

A point is a pair (x,y)(x,y)(x,y) of integer vectors; φ\varphiφ is a total function whose values off XXX are unused. Differences are not reduced modulo the sides.

Definition code
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
Source
I. Rubio and J. Torres, Multidimensional Costas Arrays and Their Periodicity, IEEE Trans. Inf. Theory 69(8) (2023) 5032-5040, https://arxiv.org/abs/2208.02378, doi:10.1109/TIT.2023.3264951; Section 2 (pp. 3-4) and Definitions 2-4 (pp. 6, 8)
Read-back

What the Lean code literally says, in plain math · claude-opus-5-5

This item (namespace PeriodicCostas) introduces seven definitions. Throughout, k,l,rk, l, rk,l,r are natural numbers, points of Zr\mathbb{Z}^rZr are integer vectors x=(x1,…,xr)x = (x_1,\dots,x_r)x=(x1​,…,xr​), and a point of Zm\mathbb{Z}^mZm with m=k+lm = k + lm=k+l is written as a pair (x,y)∈Zk×Zl(x, y) \in \mathbb{Z}^k \times \mathbb{Z}^l(x,y)∈Zk×Zl.

1. Box. For n=(n1,…,nr)∈Nrn = (n_1,\dots,n_r) \in \mathbb{N}^rn=(n1​,…,nr​)∈Nr,

box⁡(n)={x∈Zr:1≤xi≤ni for every i}=[n1]×⋯×[nr],[n]={1,…,n}.\operatorname{box}(n) = \{x \in \mathbb{Z}^r : 1 \le x_i \le n_i \text{ for every } i\} = [n_1]\times\cdots\times[n_r],\qquad [n] = \{1,\dots,n\}.box(n)={x∈Zr:1≤xi​≤ni​ for every i}=[n1​]×⋯×[nr​],[n]={1,…,n}.

If some ni=0n_i = 0ni​=0 the box is empty; if r=0r = 0r=0 the box is the one-point set Z0\mathbb{Z}^0Z0.

2. Reduction. For n∈Nrn \in \mathbb{N}^rn∈Nr and x∈Zrx \in \mathbb{Z}^rx∈Zr, reduce⁡n(x)=xΛ\operatorname{reduce}_n(x) = x_\Lambdareducen​(x)=xΛ​ is the vector with coordinates

(xΛ)i=((xi−1) mod ni)+1,(x_\Lambda)_i = \big((x_i - 1) \bmod n_i\big) + 1,(xΛ​)i​=((xi​−1)modni​)+1,

where  mod \bmodmod is the integer remainder that is non-negative (Euclidean remainder) when ni≠0n_i \ne 0ni​=0. For ni≥1n_i \ge 1ni​≥1 this is the unique element of [ni][n_i][ni​] congruent to xix_ixi​ mod nin_ini​. Junk case: when ni=0n_i = 0ni​=0, the remainder modulo 000 is xi−1x_i - 1xi​−1 itself, so (xΛ)i=xi(x_\Lambda)_i = x_i(xΛ​)i​=xi​ (no reduction).

3. Permutation array. Given a=(a1,…,ak)∈Nka = (a_1,\dots,a_k) \in \mathbb{N}^ka=(a1​,…,ak​)∈Nk, b=(b1,…,bl)∈Nlb = (b_1,\dots,b_l)\in\mathbb{N}^lb=(b1​,…,bl​)∈Nl and an arbitrary function φ:Zk→Zl\varphi : \mathbb{Z}^k \to \mathbb{Z}^lφ:Zk→Zl (defined on all of Zk\mathbb{Z}^kZk; only its values on box⁡(a)\operatorname{box}(a)box(a) matter below), IsPermutationArray⁡(a,b,φ)\operatorname{IsPermutationArray}(a,b,\varphi)IsPermutationArray(a,b,φ) holds iff all of:

  • k≥1k \ge 1k≥1 and l≥1l \ge 1l≥1;
  • ai≥2a_i \ge 2ai​≥2 for every iii and bj≥2b_j \ge 2bj​≥2 for every jjj;
  • φ\varphiφ is a bijection from box⁡(a)\operatorname{box}(a)box(a) onto box⁡(b)\operatorname{box}(b)box(b): it maps box⁡(a)\operatorname{box}(a)box(a) into box⁡(b)\operatorname{box}(b)box(b), is injective on box⁡(a)\operatorname{box}(a)box(a), and every point of box⁡(b)\operatorname{box}(b)box(b) is the image of some point of box⁡(a)\operatorname{box}(a)box(a). (In particular this forces a1⋯ak=b1⋯bla_1\cdots a_k = b_1\cdots b_la1​⋯ak​=b1​⋯bl​.)

4. Dots. dots⁡(a,b,φ)={(x,y)∈Zk×Zl:x∈box⁡(a), y∈box⁡(b), φ(x)=y}\operatorname{dots}(a,b,\varphi) = \{(x,y) \in \mathbb{Z}^k\times\mathbb{Z}^l : x \in \operatorname{box}(a),\ y \in \operatorname{box}(b),\ \varphi(x) = y\}dots(a,b,φ)={(x,y)∈Zk×Zl:x∈box(a), y∈box(b), φ(x)=y}, i.e. the graph of φ\varphiφ restricted to box⁡(a)\operatorname{box}(a)box(a) (and to values in box⁡(b)\operatorname{box}(b)box(b)).

5. Periodic dots. periodicDots⁡(a,b,φ)={(x,y):(xΛ,yΛ)∈dots⁡(a,b,φ)}\operatorname{periodicDots}(a,b,\varphi) = \{(x,y) : (x_\Lambda, y_\Lambda) \in \operatorname{dots}(a,b,\varphi)\}periodicDots(a,b,φ)={(x,y):(xΛ​,yΛ​)∈dots(a,b,φ)}, where xΛ=reduce⁡a(x)x_\Lambda = \operatorname{reduce}_a(x)xΛ​=reducea​(x) and yΛ=reduce⁡b(y)y_\Lambda = \operatorname{reduce}_b(y)yΛ​=reduceb​(y). When all ai,bj≥1a_i, b_j \ge 1ai​,bj​≥1 the reduced points automatically lie in the boxes, so this is the set of (x,y)(x,y)(x,y) with φ(xΛ)=yΛ\varphi(x_\Lambda) = y_\Lambdaφ(xΛ​)=yΛ​. (If some side is 000, the box is empty and so is this set.)

6. Window. For an offset t=(t(1),t(2))∈Zk×Zlt = (t^{(1)}, t^{(2)}) \in \mathbb{Z}^k\times\mathbb{Z}^lt=(t(1),t(2))∈Zk×Zl,

window⁡(a,b,t)={(x,y):x−t(1)∈box⁡(a), y−t(2)∈box⁡(b)}=t+box⁡(a)×box⁡(b).\operatorname{window}(a,b,t) = \{(x,y) : x - t^{(1)} \in \operatorname{box}(a),\ y - t^{(2)} \in \operatorname{box}(b)\} = t + \operatorname{box}(a)\times\operatorname{box}(b).window(a,b,t)={(x,y):x−t(1)∈box(a), y−t(2)∈box(b)}=t+box(a)×box(b).

7. No repeated differences. For a set DDD in an additive group VVV, NoRepeatedDifferences⁡(D)\operatorname{NoRepeatedDifferences}(D)NoRepeatedDifferences(D) means: for all α,ω,α′,ω′∈D\alpha, \omega, \alpha', \omega' \in Dα,ω,α′,ω′∈D with α≠ω\alpha \ne \omegaα=ω and α′≠ω′\alpha' \ne \omega'α′=ω′,

ω−α=ω′−α′  ⟹  α=α′ and ω=ω′.\omega - \alpha = \omega' - \alpha' \implies \alpha = \alpha' \text{ and } \omega = \omega'.ω−α=ω′−α′⟹α=α′ and ω=ω′.

That is, the map (α,ω)↦ω−α(\alpha,\omega) \mapsto \omega - \alpha(α,ω)↦ω−α is injective on ordered pairs of distinct points of DDD. Empty sets and singletons satisfy it vacuously.

8. Costas array. IsCostas⁡(a,b,φ)\operatorname{IsCostas}(a,b,\varphi)IsCostas(a,b,φ) holds iff IsPermutationArray⁡(a,b,φ)\operatorname{IsPermutationArray}(a,b,\varphi)IsPermutationArray(a,b,φ) holds and NoRepeatedDifferences⁡(dots⁡(a,b,φ))\operatorname{NoRepeatedDifferences}(\operatorname{dots}(a,b,\varphi))NoRepeatedDifferences(dots(a,b,φ)) holds in the group Zk×Zl\mathbb{Z}^k\times\mathbb{Z}^lZk×Zl (componentwise subtraction).

9. Periodic Costas array. IsPeriodicCostas⁡(a,b,φ)\operatorname{IsPeriodicCostas}(a,b,\varphi)IsPeriodicCostas(a,b,φ) holds iff IsCostas⁡(a,b,φ)\operatorname{IsCostas}(a,b,\varphi)IsCostas(a,b,φ) holds and, for every offset t∈Zk×Zlt \in \mathbb{Z}^k\times\mathbb{Z}^lt∈Zk×Zl,

NoRepeatedDifferences⁡(periodicDots⁡(a,b,φ)∩window⁡(a,b,t)).\operatorname{NoRepeatedDifferences}\big(\operatorname{periodicDots}(a,b,\varphi) \cap \operatorname{window}(a,b,t)\big).NoRepeatedDifferences(periodicDots(a,b,φ)∩window(a,b,t)).

So every translate of the a1×⋯×ak×b1×⋯×bla_1\times\cdots\times a_k\times b_1\times\cdots\times b_la1​×⋯×ak​×b1​×⋯×bl​ box, intersected with the periodic extension of the dot set (period aia_iai​ in the iii-th xxx-coordinate and bjb_jbj​ in the jjj-th yyy-coordinate), must have pairwise distinct difference vectors. The condition ranges over all integer offsets ttt, including t=0t = 0t=0 (which recovers the dots of the original array).

Human review
  • Endorsed by Shuze Chen · Oct 4, 2026

    Confirmed by the moderator at approval.

  • Endorsed by shivm · Oct 4, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me