WorksComputer Science
Linear Equivalence of Full Weight Spectrum Cyclic Orbit Codes
Abstract
We determine the linear-equivalence classes within the two families of full weight spectrum one-orbit cyclic subspace codes. This solves the second open problem posed by Castello, Polverino and Zullo [J. Combin. Theory Ser. A 212 (2025) 106005]. For the first family, the criterion is a fractional linear transformation over \F_q followed by a power of -Frobenius. For the second family, it is an affine transformation over \F_{q^2} together with a power of -Frobenius. We use polynomial spaces over finite fields, the linear-isometry theorem for cyclic orbit codes, and trace duality. The arguments include parameters belonging to proper subfields of the ambient field.
Introduction and main result
Subspace codes were introduced by Koetter and Kschischang [14] for error correction in random linear network coding. Cyclic codes in projective space were introduced by Etzion and Vardy [8], and orbit codes under cyclic subgroups of the general linear group were studied by Trautmann, Manganiello, Braun and Rosenthal [23]. Unions of cyclic orbit codes with large minimum distance were constructed by means of subspace polynomials in [3, 15, 16].
Let be a prime power, let be an integer, and put . For an -subspace of , write
This is the one-orbit cyclic subspace code, or cyclic orbit code, defined by . We say that and are linearly equivalent if
Thus the equivalence is induced by an invertible -linear map on the ambient field. In [6, 11] linearly equivalent codes are called linearly isometric. For two -dimensional subspaces, the subspace distance is
A one-orbit cyclic subspace code has full weight spectrum (FWS) if all the distances occur.
Roth, Raviv and Tamo [18] observed that, for , the code has elements and minimum distance if and only if is a Sidon space. The equivalence of Sidon spaces was studied in [4]. Multi-orbit cyclic subspace codes were related to linear sets in [24] and used to construct optical orthogonal codes in [17].
Since for , the distance distribution of is determined by the dimensions of the intersections with . Gluesing-Luerssen and Lehmann [10] studied this distribution, which is a finer invariant of cyclic orbit codes than the minimum distance. If , the distance between two distinct codewords lies in , and so has at most distinct nonzero distances. The FWS codes are those attaining this bound.
The analogous question in the Hamming metric is classical; see Delsarte [7]. Shi, Zhu, Solé and Cohen [20] proved that a linear code of dimension over has at most distinct nonzero weights, and codes attaining this bound exist for all and by [2, 20]. A linear code of length has at most distinct nonzero weights, and Alderson [1] determined the parameters of the codes attaining this bound, which are called full weight spectrum codes. The corresponding question for cyclic codes was studied by Shi, Li, Neri and Solé [19].
Castello, Polverino and Zullo [6], Theorem 1.2 classified the FWS one-orbit cyclic subspace codes into the following two families. When , the orbit is the set of all one-dimensional -subspaces of , so there is only one code. We therefore assume .
Family I. For , put
The admissible range is
Family II. Suppose is even and put . Let and . For an integer with , define
For a positive integer , put
Here the admissible range is
In particular, and .
Linear and semilinear isometries of subspace codes were studied by Trautmann [22]. For cyclic orbit codes, Gluesing-Luerssen and Lehmann [11] proved that if , $2 \le and is not contained in a proper subfield of , then every linear isometry from another cyclic orbit code onto is of the form with and . They also observed that cyclic orbit codes with the same distance distribution need not be linearly equivalent. For , Castello, Polverino and Zullo [5 Theorems III.6 and III.7] determined when two spaces with , or two spaces , are mapped onto each other by a map with and .
The question of determining the linear-equivalence classes of the codes in Families I and II was posed as the second open problem in the concluding remarks of [6]. In general, the classification of subspace codes up to equivalence is a difficult problem; see [13] and, for example, the classification of the optimal binary codes of length 8, constant dimension 4 and minimum distance 6 in [12]. The two families are already known to be inequivalent by [6 Corollary 4.12]. In this paper we determine the equivalence classes within each family for all , and hence we solve this open problem. Our main result is the following.
Theorem 1.1. Fix , , with .
(i) Let satisfy (1). The codes and are linearly equivalent if and only if
for some with and some integer .
(ii) Suppose is even, and . Let satisfy (2). The codes and are linearly equivalent if and only if
for some , and some integer .
In each part, the degrees of the fields generated by and over the indicated base field are then equal.
Since the two families are inequivalent and there is only one code for , Theorem 1.1 gives the linear-equivalence classes of all FWS one-orbit cyclic subspace codes.
Remark 1.2. Let be the minimal polynomial of over . Since fractional linear transformations over commute with the -Frobenius map, acts on the monic irreducible polynomials over of a fixed degree through its action on their roots; see [9, 21]. Part (i) of Theorem 1.1 says that and are linearly equivalent if and only if lies in the -orbit of . In particular, the criterion does not depend on . If is a prime not dividing , then this action is free on the polynomials of degree , since a nonidentity element fixing such a polynomial would act on its roots as a nontrivial power of the Frobenius map, and hence would have order . Hence, for each admissible , the codes with form exactly classes. For example, if and , then there are three classes for each , although for fixed these codes have the same distance distribution by [6 Corollary 4.6]; for see also [5 Remark III.9]. Part (ii) can be stated in a similar way with minimal polynomials over , using the substitutions with , and the nontrivial automorphism of acting on the coefficients.
Remark 1.3. Write with prime. Let be a semilinear bijection of , that is, is additive and for all and , where is an automorphism of . Then is the composition of an -linear map with for some . Since maps onto and onto , Theorem 1.1 also determines the equivalence of these codes under semilinear bijections if with is replaced by with . For this agrees with [5].
The rest of this paper is organized as follows. In Section 2, we first reduce to the smallest field containing the representative subspace (Lemma 2.1). This permits us to apply Theorem 2.2, the linear-isometry theorem of Gluesing-Luerssen and Lehmann [11]. We then determine the possible scalar equivalences by polynomial calculations (Lemmas 3.2 and 4.2). For Family I, the case is treated separately using the trace pairing (Lemma 3.3). We prove part (i) of Theorem 1.1 in Section 3 and part (ii) in Section 4. Section 5 concludes the paper.
Reduction to the generated field
In this section we show that if two cyclic orbit codes are linearly equivalent, then their representatives containing generate the same subfield of , and the equivalence can be restricted to (Lemma 2.1). Then we recall the linear-isometry theorem of Gluesing-Luerssen and Lehmann (Theorem 2.2), which we apply in .
For an -subspace containing , let
be the smallest subfield of containing . The degree of this field is invariant under linear equivalence; see [6 Corollary 2.6]. The following argument also gives the restriction of an equivalence that we need.
Lemma 2.1. Let and . Form a graph whose vertices are the codewords of , joining two distinct vertices when their intersection is nonzero. The set of distinct -linear spans of the connected components is
Consequently, if and is linearly equivalent to , then . After multiplication by a scalar, the equivalence restricts to an -linear equivalence between and .
Proof. Put , write , and let
be the multiplicative subgroup of generated by these quotients. For ,
It follows that the component containing consists of the subspaces with . Since , we have , and hence the span of this component is
The space on the right contains and is closed under multiplication. It is a finite subring of a field, so it is a field. It contains and is contained in , and therefore it equals . Multiplication by any gives the assertion for the component containing . Different components may have the same span, which is why we take the set of distinct spans.
An invertible -linear map preserves nonzero intersections, connected components and their spans. An equivalence therefore maps the set of scalar multiples of onto the corresponding set for . These subspaces have the same dimension over . Since has a unique subfield of each possible order, .
If the equivalence maps onto , multiply it by . Its restriction to is then an invertible -linear map of . Finally, the codewords of contained in are exactly the codewords of : if , then because . The same holds for , proving the last assertion. □
We use the following form of the linear-isometry theorem [11 Theorem 6.2(a)]; see also [6 Theorem 2.3].
Theorem 2.2 (Gluesing-Luerssen–Lehmann). Let and let be an integer with . Let be -dimensional -subspaces of , with and . Then and are linearly equivalent if and only if
where .
The bound is needed here. In our applications, Lemma 2.1 first replaces by the field generated by the subspace. We then check this dimension bound in that field.
Polynomial spaces and the first family
In this section we determine when two polynomial spaces are scalar multiples of each other (Lemma 3.2), and we prove part (i) of Theorem 1.1. For the case we also use the trace dual of a polynomial space given in Lemma 3.3.
Let be a finite field and let be a finite extension of . For , put . For an integer , write
Evaluation at is injective on polynomials over of degree less than . The next lemma is the polynomial-intersection calculation used in [6 Lemma 4.3]. We give the proof in the range , which will also cover the boundary case below.
Lemma 3.1. Let have degree over , and let with . Let be nonzero coprime polynomials of degrees at most . Put . Then
Proof. An element of the intersection has the form , where have degrees at most $r-1. Thus
Since , this gives the polynomial identity . As and are coprime, and for some . Conversely, every such pair gives an element of the intersection. The permitted polynomials have degree less than . Evaluation and multiplication by are injective on this space, giving the stated dimension.
Lemma 3.2. Let and let have degrees at least over . Then for some if and only if
for some with .
Proof. Suppose . Since , we may write with nonzero and coprime, both of degree at most are linearly independent over , so
Multiplication by and Lemma 3.1 now give
Thus . The quotient is nonconstant because . Its coefficient matrix is therefore invertible, and inversion gives the required expression for .
Conversely, suppose with . The denominator is nonzero since . For ,
Both spaces have dimension , and hence
This proves the converse. □
For the case , we shall also need the following trace-dual identity; see [6 Proposition 3.3].
Lemma 3.3. Let satisfy , and let be its monic minimal polynomial. For , put . With respect to the trace pairing
we have
Here is the formal derivative of , and .
Proof. The polynomial divides , whose derivative is . Thus is separable and .
For , Lagrange interpolation at the roots of gives
Comparing coefficients of yields
Products of a basis element of and a basis element of have the form with . Therefore . The trace pairing is nondegenerate, and both sides have dimension . This proves (6). □
Proof of Theorem 1.1(i). Suppose the two codes are linearly equivalent. Their representatives contain and generate and , respectively. By Lemma 2.1, these fields are equal, say , and the equivalence restricts to the orbit codes in .
First suppose . Theorem 2.2 gives
for some and . Lemma 3.2, with , now gives (3).
It remains to consider . Suppose first that . Let be an -linear equivalence between and . Define its adjoint by
For every subspace ,
Thus maps the dual codes onto one another. Since , Lemma 3.3 identifies these dual orbit codes with
Both representatives still contain and the corresponding parameter. Moreover, . Applying Theorem 2.2 and Lemma 3.2 to these spaces again gives (3).
If and , the group acts freely on the degree-three elements of . Indeed, a nonidentity fractional linear transformation fixing such an element would give a nonzero polynomial of degree at most two having it as a root. There are degree-three elements, and . The action is therefore transitive, so any two such parameters satisfy (3) with .
For the converse, is an invertible -linear map on and sends onto . (5) shows that the latter orbit code equals . This proves the assertion. □
The second family
In this section we prove part (ii) of Theorem 1.1. We show that determines the space (Lemma 4.1), and using this we determine when is a scalar multiple of (Lemma 4.2).
Throughout this section, is even, , and . Let with . To simplify the notation, put
The next lemma shows that is the largest -linear subspace contained in , and that is the -linear span of , that is, the space of all finite sums of elements with and .
Lemma 4.1. For any ,
Every -linear subspace of is contained in . Furthermore,
Proof. The elements are linearly independent over , and multiplication by preserves . Consequently,
If is -linear, then , and therefore . Taking the -span of gives .
For (7), suppose first that . Then and , so is equivalent to .
Now let and suppose . Since , we have , so for a polynomial of degree at most . If , the assertion is immediate. Otherwise, implies
The polynomial has degree at most . Its value at belongs to only if this polynomial has degree at most , by injectivity of evaluation below degree . Hence , giving . Conversely, each element of maps into by multiplication.
For any we have
since can be cancelled. This gives the following scalar-equivalence criterion.
Lemma 4.2. Let satisfy and . Then for some if and only if
Proof. Suppose . Multiplication by is -linear. It therefore carries the largest -subspace of onto that of , and carries their -spans onto one another. By Lemma 4.1,
Equations (7) and (8) imply
Thus for , with since .
Conversely, let with and . Expanding powers gives
Indeed, the change between the two polynomial bases is triangular with nonzero diagonal entries . Therefore
as required.
Proof of Theorem 1.1(ii). The smallest field containing is . Indeed, and , also when . An ambient linear equivalence therefore restricts, by Lemma 2.1, to an equivalence of the orbit codes in
Since , the codeword dimension satisfies . Thus Theorem 2.2 applies with and , and gives
for some and . The last equality holds because -Frobenius preserves and fixes . Lemma 4.2 now gives (4).
Conversely, if (4) holds, then
The map on sends the first orbit code onto the second. This proves the theorem.
Conclusion
In this paper we determined the linear-equivalence classes of all FWS one-orbit cyclic subspace codes, and hence solved the second open problem posed by Castello, Polverino and Zullo in [6]. In Family I, two codes are linearly equivalent if and only if their parameters and are related by a fractional linear transformation over and a power of -Frobenius. In Family II, the corresponding condition is an affine transformation over and a power of -Frobenius.
Acknowledgements
The research of M. Shi was supported by the National Natural Science Foundation of China under Grants W2611002 and 12471490.
School of Mathematical Sciences, Anhui University, Hefei 230601, China
Email address: [email protected]
Faculty of Engineering and Natural Sciences, Sabancı University, Istanbul, Türkiye
Email address: [email protected]
References
- [1]T. L. Alderson, A note on full weight spectrum codes, Trans. Comb. 8 (2019), no. 3, 15–22.DOI
- [2]T. L. Alderson and A. Neri, Maximum weight spectrum codes, Adv. Math. Commun. 13 (2019), no. 1, 101–119.
- [3]E. Ben-Sasson, T. Etzion, A. Gabizon and N. Raviv, Subspace polynomials and cyclic subspace codes, IEEE Trans. Inform. Theory 62 (2016), no. 3, 1157–1165.
- [4]C. Castello, O. Polverino, P. Santonastaso and F. Zullo, Constructions and equivalence of Sidon spaces, J. Algebraic Combin. 58 (2023), no. 4, 1299–1329.arxiv.org/abs/2303.17306
- [5]C. Castello, O. Polverino and F. Zullo, On one-orbit cyclic subspace codes of G_q(n, 3), in: Proc. 2024 IEEE Int. Symp. Inf. Theory (ISIT), Athens, 2024, pp. 2383–2388.
- [6]C. Castello, O. Polverino and F. Zullo, Full weight spectrum one-orbit cyclic subspace codes, J. Combin. Theory Ser. A 212 (2025), 106005.arxiv.org/abs/2405.19911
- [7]Ph. Delsarte, Four fundamental parameters of a code and their combinatorial significance, Information and Control 23 (1973), no. 5, 407–438.DOI
- [8]T. Etzion and A. Vardy, Error-correcting codes in projective space, IEEE Trans. Inform. Theory 57 (2011), no. 2, 1165–1173.
- [9]T. Garefalakis, On the action of GL_2(F_q) on irreducible polynomials over F_q, J. Pure Appl. Algebra 215 (2011), no. 8, 1835–1843.
- [10]H. Gluesing-Luerssen and H. Lehmann, Distance distributions of cyclic orbit codes, Des. Codes Cryptogr. 89 (2021), no. 3, 447–470.
- [11]H. Gluesing-Luerssen and H. Lehmann, Automorphism groups and isometries for cyclic orbit codes, Adv. Math. Commun. 17 (2023), no. 1, 119–138.
- [12]D. Heinlein, T. Honold, M. Kiermaier, S. Kurz and A. Wassermann, Classifying optimal binary subspace codes of length 8, constant dimension 4 and minimum distance 6, Des. Codes Cryptogr. 87 (2019), no. 2–3, 375–391.
- [13]T. Honold, M. Kiermaier and S. Kurz, Constructions and bounds for mixed-dimension subspace codes, Adv. Math. Commun. 10 (2016), no. 3, 649–682.arxiv.org/abs/1512.06660
- [14]R. Koetter and F. R. Kschischang, Coding for errors and erasures in random network coding, IEEE Trans. Inform. Theory 54 (2008), no. 8, 3579–3591.
- [15]K. Otal and F. Özbudak, Cyclic subspace codes via subspace polynomials, Des. Codes Cryptogr. 85 (2017), no. 2, 191–204.DOI
- [16]K. Otal and F. Özbudak, Constructions of cyclic subspace codes and maximum rank distance codes, in: Network Coding and Subspace Designs, Signals Commun. Technol., Springer, Cham, 2018, pp. 43–66.DOI
- [17]F. Özbudak, P. Santonastaso and F. Zullo, Using multi-orbit cyclic subspace codes for constructing optical orthogonal codes, Cryptogr. Commun. 17 (2025), no. 4, 695–708.arxiv.org/abs/2405.18996
- [18]R. M. Roth, N. Raviv and I. Tamo, Construction of Sidon spaces with applications to coding, IEEE Trans. Inform. Theory 64 (2018), no. 6, 4412–4422.arxiv.org/abs/1705.04560
- [19]M. Shi, X. Li, A. Neri and P. Solé, How many weights can a cyclic code have?, IEEE Trans. Inform. Theory 66 (2020), no. 3, 1449–1459.arxiv.org/abs/1807.08418
- [20]M. Shi, H. Zhu, P. Solé and G. D. Cohen, How many weights can a linear code have?, Des. Codes Cryptogr. 87 (2019), no. 1, 87–95.DOI
- [21]H. Stichtenoth and A. Topuzoglu, Factorization of a class of polynomials over finite fields, Finite Fields Appl. 18 (2012), no. 1, 108–122.DOI
- [22]A.-L. Trautmann, Isometry and automorphisms of constant dimension codes, Adv. Math. Commun. 7 (2013), no. 2, 147–160.arxiv.org/abs/1205.5465
- [23]A.-L. Trautmann, F. Manganiello, M. Braun and J. Rosenthal, Cyclic orbit codes, IEEE Trans. Inform. Theory 59 (2013), no. 11, 7386–7404.DOI
- [24]F. Zullo, Multi-orbit cyclic subspace codes and linear sets, Finite Fields Appl. 87 (2023), 102153.arxiv.org/abs/2112.08781