CS Paper Radar

Frobenius Profiles of Polynomial-Multiple MRD Codes

Yangcheng Li, Pingzhi Yuan

cs.IT math.NT ·submitted 2026-10-19 03:22 UTC · v1
theoryhot direction

Abstract

We study Frobenius intersection profiles of maximum rank distance (MRD) codes arising from ordinary polynomial multiples over finite fields. We prove that every numerically admissible profile is realized within this family over every sufficiently large extension, using a root-exponent pattern independent of the extension degree. A factor-orbit gap formula provides the underlying structural description, while effective extension-degree bounds guarantee realization. We also establish a lower bound valid for all polynomial generators and show that the upper and lower bounds differ by only $O_q(\log n)$ along an infinite family of parameters. Finally, we characterize the generalized Gabidulin members and obtain non-generalized-Gabidulin realizations of every profile with initial loss at least two over infinitely many extensions.

Comment
30 pages

Closest papers

Nearest neighbours by meaning across the whole index.

Maximum-Likelihood Decoding of Gabidulin Codes Is NP-Hard Even in Dimension One

cs.CR cs.IT ·2026-10-25 ·Philippe Gaborit
theoryhot direction similarity 0.66
Abstract · in submission

Fix a prime power q. We prove that deciding whether a received word y in Fnqm lies at rank distance at most n-2 from the one-dimensional Gabidulin code {{λ.g : λ in Fqm } is NP-complete. Thus maximum-likelihood decoding of Gabidulin codes is NP-hard even for k = 1, an analogue of the Guruswami-Vardy theorem for Reed-Solomon codes. In the Hamming metric, by contrast, hardness at this radius requires the dimension to grow with the length, as in the Guruswami-Vardy theorem. The reduction is deterministic; consequently Rank Syndrome Decoding (RSD) and Rank Minimum Distance (RMD) for Fqm -linear codes are NP-complete under deterministic polynomial reductions, whereas the previously known reduction was randomized. The proof goes through a pivot problem that we introduce, Twisted Square Membership (TSM): given Fq-subspaces U, W in FqN , decide whether some non-zero a in U satisfies a^(q+1) in W . Quadratic systems in d unknowns are encoded into TSM, then TSM into Gabidulin decoding. The last step views the received word as an Fq-linear map and decoding at radius n - 2 as the search for an Fq-plane on which it acts as a scalar. With support U + τ W in a cubic extension and map a + τ b to a^(q^2) + τ bq^q , two Frobenius twists force solution planes to encode the relation a^(q+1) in W . All constructions are explicit and polynomial, with N = O(qd^2 ), n less than N + d, and m = 3N .

0.50

Length Bounds for Irreducible Cyclic MDS Codes

cs.IT ·2026-10-20 ·Guanghui Zhang
theoryhot direction similarity 0.65
Abstract · 35 pages

We prove the MDS length bound for nontrivial irreducible cyclic codes of every composite length. The classical trace realization turns the MDS property into independence of elements of a multiplicative subgroup. Every nonidentity subgroup must have the full extension degree. This restriction yields length congruences, and the Frobenius-orbit description of the coefficient field gives an exact descent obstruction. A cyclotomic argument reduces each fixed dimension to finitely many parameters. For dimensions at most thirty, established geometric bounds reduce the alphabet to a small finite range; the remaining twelve parameter triples are excluded by explicit products of at most three determinant factors and a low-degree multiplier argument. An independent argument proves the composite-length theorem in arbitrary dimension. The standardness conclusion is stated separately as a conditional consequence of the classification statement of Feng, Hollmann, Li, and Xiang; the correct extension-field reduction retains a semilinear quotient. The general prime-length problem is not settled here. Neither length proof uses the automorphism classification or the recent odd-characteristic range announced by Fan.

0.34

Support periods of polynomials and support-primitive decomposition of constacyclic codes over Galois rings

cs.IT math.NT ·2026-10-21 ·Li Zhu, Hongfeng Wu
similarity 0.63
Abstract

Let \(A=\GR(p^e,r)\) have residue field \(\F_q\), and let \(λ\in A^\times\). We relate coefficient compression of monic divisors of \(X^N-λ\) to support-primitive decomposition of constacyclic codes. At a simple-root length, the support period of every nonconstant monic divisor is preserved at each coefficient precision and equals the order of the multiplicative stabilizer of its root set. For a cyclic Frobenius-orbit polynomial, the multiple equal-difference structure determines its support period, core degree, and least relative degree of an unramified extension over which all its basic-irreducible factors are binomials. Coordinate projections give every constacyclic code over a finite commutative ring a unique maximal interleaving into copies of one support-primitive code. At simple-root lengths over \(A\), the intrinsic period of a code is the greatest common divisor of the periods of its torsion codes. The decomposition yields distance and duality formulas and the arithmetic Singleton bound for free codes. At every length, a nonzero code over \(A\) has the same minimum Hamming distance as its highest torsion code, which gives a refined bound. At repeated-root lengths, identical torsion filtrations can occur with different intrinsic periods, while a class of nonzero codes obtained by substitution from simple-root generators retains the same core and minimum distance. Trace matrices recover the coefficients of basic-irreducible cores using unit pivots, and local Hensel corrections lift compressed factors directly. For \(X^n-1\) with \(p\nmid n\), lifting and output have quasi-linear bit cost in the compressed representation when the arithmetic data and residue factorizations are given.

0.25

Finite Fields: Root Sets, Frobenius, and Algebraic Structure

cs.IT math.NT ·2026-10-27 ·Hongfeng Wu, Li Zhu
theory similarity 0.63
Abstract

This monograph develops finite field theory through root sets, Frobenius orbits, trace duality, and cyclic modules, with applications to polynomial constructions and algebraic coding theory. Root-set descent and linearized polynomials connect field extensions, normal bases, invariant subspaces, and linear recurrences. Cyclotomic cosets link additive symmetries and local phase data with polynomial composition, factorization, and compatible lifting. Low-degree subfield representations and relative traces lead to root-block recovery, while return maps on root fibers organize constructions of irreducible polynomials. Coding applications include duality, distance bounds, Fourier support, and syndrome decoding. Character sums yield trace-norm distributions, the primitive normal basis theorem, and recurrences for extension-field sums and curve point counts. The final chapter constructs finite fields as residue fields of unramified p-adic extensions and relates Teichmuller representatives and Hensel lifting to cyclotomic orbits, periodic digit expansions, Witt carries, coefficient valuations, and Newton slopes. The emphasis throughout is on explicit proofs and reusable connections between field structure, orbit structure, and linear dependence.

0.21

Equal Hamming Weights at Fixed Root Order and Applications to Constacyclic MDS Codes

cs.IT ·2026-10-31 ·Li Zhu, Hongfeng Wu
theory similarity 0.62
Abstract

For a fixed positive integer $n>1$, we study the prime powers $q$ coprime to $n$ for which all monic irreducible factors of $Φ_n$ over $\F_q$ have the same coefficient Hamming weight. Cyclotomic orbit coefficients give a finite, effective classification of these fields. Outside finitely many computable characteristics, every factor has the support of its characteristic-zero orbit polynomial; the uniform condition $p>2^{\varphi(n)}$ suffices. In each remaining characteristic, extension exponents reduce to divisors of $\ord_n(p)$, and an integer variance identity expressed by polynomial gcd degrees decides equal weight. The same coefficient data determine the full weight distribution. As an application, we prove that an MDS constacyclic code with an irreducible generator forces every irreducible polynomial of the same root order to have full support, including factors associated with different constacyclic constants. This yields a uniform gcd and norm obstruction. We develop its short-multiplier extension, give a prime-order cubic family, and establish an explicit quadratic-residue exclusion without a prime-square alphabet or a near-square length hypothesis.

0.20

Evasive subspaces, minimal rank-metric codes and subspace designs via auxiliary fields

cs.IT math.CO ·2026-11-05 ·Alessandro Giannoni
similarity 0.62
Abstract · 33 pages

We extend the auxiliary-field method for scattered subspaces to evasive subspaces and subspace designs. For $1\le h\le k<hn$ and coprime $h,k+1$ with $n(k-h+1)\ge k+1$, we construct spanning $(h,k)$-evasive $\mathbb{F}_q$-subspaces of $\mathbb{F}_{q^n}^r$ of dimension $rn(k-h+1)/(k+1)$ in every sufficiently large admissible ambient dimension, with a threshold independent of $q$. When $k<n$, this dimension is maximum. The proof combines an intersection lemma, a rank-support density inequality, scalar orbit counting, and a profile preserved by direct sums. The coding consequences include, for every fixed odd extension degree $m\ge3$ and every sufficiently large $K$, minimal rank-metric codes of optimal length $2K$ with first two generalized weights $(m+1)/2$ and $m+1$. For these codes the stable profile is equivalent to minimality with the largest possible minimum distance; for even $m$ the analogous class consists of minimal MRD codes. More generally, for $1\leτ\le m-2$ and $\gcd(m,τ+1)=1$, we obtain nondegenerate $τ$-minimal codes of length $(τ+1)K$ for every sufficiently large $K$, uniformly in $q$. We also construct maximum $h$-designs whose number of members grows exponentially with the ambient dimension at fixed $q,n,h$, and the associated maximum sum-rank distance (MSRD) codes with a growing number of equal long blocks. In extension degree five, the ordinary and $2$-minimal constructions hold for every $q$ and every $K\ge32$ and $K\ge59$, respectively.

0.09

On MRD constacyclic codes over inseparable field extensions

cs.IT ·2026-10-16 ·Grégory Berhuy
similarity 0.62
Abstract

In this paper, we construct MRD constacyclic codes of length $p$ over an inseparable field extension $L/K$, where $K$ has characteristic $p$. In particular, these codes cannot be obtained from known constructions.

0.26

Proximity Gaps for Gabidulin Codes and Applications

cs.IT cs.CR ·2026-09-09 ·Songsong Li, Chaoping Xing, Chen Yuan, Ruiqi Zhu
theory similarity 0.62
Abstract · 40 pages

Proximity gaps are central to the soundness of interactive oracle proofs of proximity (IOPPs) and polynomial commitment schemes (PCSs). An $[n,k,d]$ linear code $C\subseteq\mathbb F^n$ has a $δ$-proximity gap with error $ε$ if, for every $u_0,u_1\in\mathbb F^n$, either all points on $\ell_{u_0,u_1}=\{u_0+αu_1:α\in\mathbb F\}$ are $δ$-close to $C$, or at most an $ε$ fraction are. Although proximity gaps for Hamming-metric codes are well understood, their rank-metric counterparts remain largely unexplored despite their applications in coding theory and cryptography. In this work, we study proximity gaps for linear rank-metric codes and their cryptographic applications. First, we show that every $[n,k,d]$ linear rank-metric code $C$ over $\mathbb F_{q^m}$ admits a proximity gap for every $δ\le(d-1)/(3n)$, with error at most $q^{e+1}/q^m$, where $e=\lfloorδn\rfloor$. For Gabidulin codes, we improve the gap to $(d-1)/(2n)$ with error $10q^{n-1}/q^m$. These two proximity gaps match those for general linear Hamming-metric codes and Reed--Solomon (RS) codes, respectively. We prove the $(d-1)/(2n)$ bound is tight by constructing an infinite family of constant-rate Gabidulin codes and affine lines $\ell_{u_0,u_1}$ on which a $1-o(1)$ fraction of points are $d/(2n)$-close to the code, while $u_1$ is at least $3d/(4n)$-far from it. At $δ=(d-1)/(2n)$, a further counterexample gives a lower bound of order $q^{n-1}/q^m$ on $\varepsilon$, matching our upper bound up to a constant factor. As applications, we construct an IOPP for interleaved Gabidulin codes by adapting the Ligero IOPP for interleaved RS codes. We then adapt the Ligero-based PCS for ordinary polynomials to obtain a $q$-linearized polynomial commitment scheme. To our knowledge, this is the first PCS framework based on rank-metric error-correcting codes.

0.47