Result 4.6 — Delsarte's Singleton-like bound |C| ≤ q^{m(n − d + 1)} for rank distance codes
ProvedHScattered.Bound.result_4_6Let and be -vector spaces with and , where . A rank distance code of is a set of -linear maps , with the rank distance . Suppose and any two distinct elements of have rank distance at least . Then
Codes attaining this bound are the maximum rank distance (MRD) codes. The bound is due to Delsarte (1978); in the paper it is the counting step of the case of Theorem 2.3.
Formalization Note The paper's hypothesis is that is the minimum distance . The Lean statement only asks that be a lower bound for the distances, which implies the minimum-distance version and is how the paper applies it. The range (automatic for a minimum distance of a code with two or more elements) keeps free of natural-number truncation. is a Finset of linear maps, is Fintype.card F, and the rank of is the dimension of its range.
import Mathlib
namespace HScattered.Bound
/-- Result 4.6 (Delsarte's Singleton-like bound, as stated in arXiv:1906.10590v2, p. 14).
A rank distance code `C` of `𝔽_q^{n×m}`, `n ≤ m`, is a set of `𝔽_q`-linear maps `X → Y` with
`dim X = m`, `dim Y = n`; the distance of `f, g` is `rk(f − g)`. If any two distinct elements of
`C` are at rank distance at least `d` (`1 ≤ d ≤ n`), then `|C| ≤ q^{m(n − d + 1)}`. -/
theorem result_4_6 {F X Y : Type*} [Field F] [Fintype F]
[AddCommGroup X] [Module F X] [FiniteDimensional F X]
[AddCommGroup Y] [Module F Y] [FiniteDimensional F Y]
(m n d : ℕ) (hm : Module.finrank F X = m) (hn : Module.finrank F Y = n) (hnm : n ≤ m)
(C : Finset (X →ₗ[F] Y)) (hd1 : 1 ≤ d) (hdn : d ≤ n)
(hC : ∀ f ∈ C, ∀ g ∈ C, f ≠ g → d ≤ Module.finrank F (LinearMap.range (f - g))) :
C.card ≤ Fintype.card F ^ (m * (n - d + 1)) := by sorry
end HScattered.Bound
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.