Exceptional scattered sequences

Bartoli, Daniele; Marino, Giuseppe; Neri, Alessandro; Vicino, Lara

doi:10.5802/alco.377

Bartoli, Daniele ¹; Marino, Giuseppe ²; Neri, Alessandro ³; Vicino, Lara ⁴

¹ University of Perugia Department of Mathematics and Informatics Perugia ITALY
² University of Naples Federico II Department of Mathematics and Applications “R. Caccioppoli” Naples ITALY
³ Ghent University Department of Mathematics: Analysis, Logic and Discrete Mathematics Ghent BELGIUM
⁴ University of Groningen Faculty of Science and Engineering - Bernoulli Institute Groningen THE NETHERLANDS

Algebraic Combinatorics, Volume 7 (2024) no. 5, pp. 1405-1431.

Abstract

The concept of scattered polynomials is generalized to those of exceptional scattered sequences which are shown to be the natural algebraic counterpart of $𝔽_{q^{n}}$ -linear MRD codes. The first infinite family in the first nontrivial case is also provided and equivalence issues are considered. As a byproduct, a new infinite family of MRD codes is obtained.

Received: 2023-08-30
Revised: 2024-05-08
Accepted: 2024-05-21
Published online: 2024-10-31

DOI: 10.5802/alco.377

Classification: 94B05, 51E20, 94B27, 11T06
Keywords: Scattered polynomials, linearized polynomials, MRD codes, finite fields

Author's affiliations:

Bartoli, Daniele ¹; Marino, Giuseppe ²; Neri, Alessandro ³; Vicino, Lara ⁴

¹ University of Perugia Department of Mathematics and Informatics Perugia ITALY
² University of Naples Federico II Department of Mathematics and Applications “R. Caccioppoli” Naples ITALY
³ Ghent University Department of Mathematics: Analysis, Logic and Discrete Mathematics Ghent BELGIUM
⁴ University of Groningen Faculty of Science and Engineering - Bernoulli Institute Groningen THE NETHERLANDS

License:

CC-BY 4.0

Copyrights: The authors retain unrestricted copyrights and publishing rights

@article{ALCO_2024__7_5_1405_0,
     author = {Bartoli, Daniele and Marino, Giuseppe and Neri, Alessandro and Vicino, Lara},
     title = {Exceptional scattered sequences},
     journal = {Algebraic Combinatorics},
     pages = {1405--1431},
     publisher = {The Combinatorics Consortium},
     volume = {7},
     number = {5},
     year = {2024},
     doi = {10.5802/alco.377},
     language = {en},
     url = {https://alco.centre-mersenne.org/articles/10.5802/alco.377/}
}

TY  - JOUR
AU  - Bartoli, Daniele
AU  - Marino, Giuseppe
AU  - Neri, Alessandro
AU  - Vicino, Lara
TI  - Exceptional scattered sequences
JO  - Algebraic Combinatorics
PY  - 2024
SP  - 1405
EP  - 1431
VL  - 7
IS  - 5
PB  - The Combinatorics Consortium
UR  - https://alco.centre-mersenne.org/articles/10.5802/alco.377/
DO  - 10.5802/alco.377
LA  - en
ID  - ALCO_2024__7_5_1405_0
ER  -

%0 Journal Article
%A Bartoli, Daniele
%A Marino, Giuseppe
%A Neri, Alessandro
%A Vicino, Lara
%T Exceptional scattered sequences
%J Algebraic Combinatorics
%D 2024
%P 1405-1431
%V 7
%N 5
%I The Combinatorics Consortium
%U https://alco.centre-mersenne.org/articles/10.5802/alco.377/
%R 10.5802/alco.377
%G en
%F ALCO_2024__7_5_1405_0

Bartoli, Daniele; Marino, Giuseppe; Neri, Alessandro; Vicino, Lara. Exceptional scattered sequences. Algebraic Combinatorics, Volume 7 (2024) no. 5, pp. 1405-1431. doi : 10.5802/alco.377. https://alco.centre-mersenne.org/articles/10.5802/alco.377/

References
Cited by

[1] Alfarano, Gianira N.; Borello, Martino; Neri, Alessandro; Ravagnani, Alberto Linear cutting blocking sets and minimal codes in the rank metric, J. Combin. Theory Ser. A, Volume 192 (2022), Paper no. 105658, 44 pages | DOI | MR | Zbl

[2] Alfarano, Gianira N.; Byrne, Eimear The Critical Theorem for $q$ -Polymatroids, 2023 | arXiv

[3] Bartoli, Daniele Hasse-Weil type theorems and relevant classes of polynomial functions, Surveys in combinatorics 2021 (London Math. Soc. Lecture Note Ser.), Volume 470, Cambridge Univ. Press, Cambridge, 2021, pp. 43-101 | DOI | MR | Zbl

[4] Bartoli, Daniele; Csajbók, Bence; Marino, Giuseppe; Trombetti, Rocco Evasive subspaces, J. Combin. Des., Volume 29 (2021) no. 8, pp. 533-551 | DOI | MR | Zbl

[5] Bartoli, Daniele; Giulietti, Massimo; Marino, Giuseppe; Polverino, Olga Maximum scattered linear sets and complete caps in Galois spaces, Combinatorica, Volume 38 (2018) no. 2, pp. 255-278 | DOI | MR | Zbl

[6] Bartoli, Daniele; Giulietti, Massimo; Zini, Giovanni Towards the classification of exceptional scattered polynomials, 2022 | arXiv

[7] Bartoli, Daniele; Marino, Giuseppe; Neri, Alessandro New MRD codes from linear cutting blocking sets, Ann. Mat. Pura Appl. (4), Volume 202 (2023) no. 1, pp. 115-142 | DOI | MR | Zbl

[8] Bartoli, Daniele; Montanucci, Maria On the classification of exceptional scattered polynomials, J. Combin. Theory Ser. A, Volume 179 (2021), Paper no. 105386, 28 pages | DOI | MR | Zbl

[9] Bartoli, Daniele; Zanella, Corrado; Zullo, Ferdinando A new family of maximum scattered linear sets in $PG (1, q^{6})$ , Ars Math. Contemp., Volume 19 (2020) no. 1, pp. 125-145 | DOI | MR | Zbl

[10] Bartoli, Daniele; Zhou, Yue Exceptional scattered polynomials, J. Algebra, Volume 509 (2018), pp. 507-534 | DOI | MR | Zbl

[11] Bartoli, Daniele; Zhou, Yue Asymptotics of Moore exponent sets, J. Combin. Theory Ser. A, Volume 175 (2020), Paper no. 105281, 18 pages | DOI | MR | Zbl

[12] Bartoli, Daniele; Zini, Giovanni; Zullo, Ferdinando Linear maximum rank distance codes of exceptional type, IEEE Trans. Inform. Theory, Volume 69 (2023) no. 6, pp. 3627-3636 | DOI | MR | Zbl

[13] Blokhuis, Aart; Lavrauw, Michel Scattered spaces with respect to a spread in $PG (n, q)$ , Geom. Dedicata, Volume 81 (2000) no. 1-3, pp. 231-243 | DOI | MR | Zbl

[14] Csajbók, Bence; Marino, Giuseppe; Polverino, Olga; Zanella, Corrado A new family of MRD-codes, Linear Algebra Appl., Volume 548 (2018), pp. 203-220 | DOI | MR | Zbl

[15] Csajbók, Bence; Marino, Giuseppe; Polverino, Olga; Zullo, Ferdinando Maximum scattered linear sets and MRD-codes, J. Algebraic Combin., Volume 46 (2017) no. 3-4, pp. 517-531 | DOI | MR | Zbl

[16] Csajbók, Bence; Marino, Giuseppe; Polverino, Olga; Zullo, Ferdinando Generalising the scattered property of subspaces, Combinatorica, Volume 41 (2021) no. 2, pp. 237-262 | DOI | MR | Zbl

[17] Csajbók, Bence; Marino, Giuseppe; Zullo, Ferdinando New maximum scattered linear sets of the projective line, Finite Fields Appl., Volume 54 (2018), pp. 133-150 | DOI | MR | Zbl

[18] Delsarte, Ph. Bilinear forms over a finite field, with applications to coding theory, J. Combin. Theory Ser. A, Volume 25 (1978) no. 3, pp. 226-241 | DOI | MR | Zbl

[19] Dvir, Zeev; Lovett, Shachar Subspace evasive sets, STOC’12—Proceedings of the 2012 ACM Symposium on Theory of Computing, ACM, New York (2012), pp. 351-358 | DOI | MR | Zbl

[20] Ferraguti, Andrea; Micheli, Giacomo Exceptional scatteredness in prime degree, J. Algebra, Volume 565 (2021), pp. 691-701 | DOI | MR | Zbl

[21] Gabidulin, È. M. Theory of codes with maximum rank distance, Problemy Peredachi Informatsii, Volume 21 (1985) no. 1, pp. 3-16 | MR | Zbl

[22] Gabidulin, È. M.; Paramonov, A. V.; Tretjakov, O. V. Ideals over a noncommutative ring and their application in cryptology, Advances in cryptology—EUROCRYPT ’91 (Brighton, 1991) (Lecture Notes in Comput. Sci.), Volume 547, Springer, Berlin, 1991, pp. 482-489 | DOI | MR | Zbl

[23] Gruica, Anina; Horlemann, Anna-Lena; Ravagnani, Alberto; Willenborg, Nadja Densities of codes of various linearity degrees in translation-invariant metric spaces, Des. Codes Cryptogr., Volume 92 (2024) no. 3, pp. 609-637 | DOI | MR | Zbl

[24] Guruswami, Venkatesan Linear-algebraic list decoding of folded Reed-Solomon codes, 26th Annual IEEE Conference on Computational Complexity, IEEE Computer Soc., Los Alamitos, CA, 2011, pp. 77-85 | MR

[25] Guruswami, Venkatesan; Wang, Carol; Xing, Chaoping Explicit list-decodable rank-metric and subspace codes via subspace designs, IEEE Trans. Inform. Theory, Volume 62 (2016) no. 5, pp. 2707-2718 | DOI | MR | Zbl

[26] Hartshorne, Robin Algebraic geometry, Graduate Texts in Mathematics, No. 52, Springer-Verlag, New York-Heidelberg, 1977, xvi+496 pages | DOI | MR

[27] Hirschfeld, J. W. P.; Korchmáros, G.; Torres, F. Algebraic curves over a finite field, Princeton Series in Applied Mathematics, Princeton University Press, Princeton, NJ, 2008, xx+696 pages | DOI | MR

[28] Kim, Kwang Ho; Choe, Junyop; Mesnager, Sihem Solving $X^{q + 1} + X + a = 0$ over finite fields, Finite Fields Appl., Volume 70 (2021), Paper no. 101797, 16 pages | DOI | MR | Zbl

[29] Kshevetskiy, A.; Gabidulin, E. The new construction of rank codes, Proceedings. International Symposium on Information Theory, 2005. ISIT 2005., IEEE, 2005, pp. 2105-2108 | DOI

[30] Loidreau, Pierre A new rank metric codes based encryption scheme, Post-quantum cryptography (Lecture Notes in Comput. Sci.), Volume 10346, Springer, Cham, 2017, pp. 3-17 | DOI | MR | Zbl

[31] Longobardi, G.; Marino, Giuseppe; Trombetti, Rocco; Zhou, Yue A large family of maximum scattered linear sets of $PG (1, q^{n})$ and their associated MRD codes, Combinatorica, Volume 43 (2023) no. 4, pp. 681-716 | DOI | MR | Zbl

[32] Longobardi, Giovanni; Zanella, Corrado Linear sets and MRD-codes arising from a class of scattered linearized polynomials, J. Algebraic Combin., Volume 53 (2021) no. 3, pp. 639-661 | DOI | MR | Zbl

[33] Lunardon, G.; Polito, P.; Polverino, O. A geometric characterisation of linear $k$ -blocking sets, J. Geom., Volume 74 (2002) no. 1-2, pp. 120-122 | DOI | MR | Zbl

[34] Lunardon, G.; Polverino, O. Blocking sets of size $q^{t} + q^{t - 1} + 1$ , J. Combin. Theory Ser. A, Volume 90 (2000) no. 1, pp. 148-158 | DOI | MR | Zbl

[35] Lunardon, Guglielmo; Polverino, Olga Translation ovoids of orthogonal polar spaces, Forum Math., Volume 16 (2004) no. 5, pp. 663-669 | DOI | MR | Zbl

[36] Lunardon, Guglielmo; Trombetti, Rocco; Zhou, Yue Generalized twisted Gabidulin codes, J. Combin. Theory Ser. A, Volume 159 (2018), pp. 79-106 | DOI | MR | Zbl

[37] Marino, Giuseppe; Montanucci, Maria; Zullo, Ferdinando MRD-codes arising from the trinomial $x^{q} + x^{q^{3}} + c x^{q^{5}} \in 𝔽_{q^{6}} [x]$ , Linear Algebra Appl., Volume 591 (2020), pp. 99-114 | DOI | MR | Zbl

[38] Marino, Giuseppe; Neri, Alessandro; Trombetti, Rocco Evasive subspaces, generalized rank weights and near MRD codes, Discrete Math., Volume 346 (2023) no. 12, Paper no. 113605, 18 pages | DOI | MR | Zbl

[39] McGuire, Gary; Sheekey, John A characterization of the number of roots of linearized and projective polynomials in the field of coefficients, Finite Fields Appl., Volume 57 (2019), pp. 68-91 | DOI | MR

[40] Neri, Alessandro; Horlemann-Trautmann, Anna-Lena; Randrianarisoa, Tovohery; Rosenthal, Joachim On the genericity of maximum rank distance and Gabidulin codes, Des. Codes Cryptogr., Volume 86 (2018) no. 2, pp. 341-363 | DOI | MR | Zbl

[41] Neri, Alessandro; Santonastaso, Paolo; Zullo, Ferdinando Extending two families of maximum rank distance codes, Finite Fields Appl., Volume 81 (2022), Paper no. 102045, 31 pages | DOI | MR | Zbl

[42] Polverino, Olga Linear sets in finite projective spaces, Discrete Math., Volume 310 (2010) no. 22, pp. 3096-3107 | DOI | MR | Zbl

[43] Polverino, Olga; Santonastaso, Paolo; Sheekey, John; Zullo, Ferdinando Divisible linear rank metric codes, IEEE Trans. Inform. Theory, Volume 69 (2023) no. 7, pp. 4528-4536 | DOI | MR | Zbl

[44] Pudlák, Pavel; Rödl, Vojtěch Pseudorandom sets and explicit constructions of Ramsey graphs, Complexity of computations and proofs (Quad. Mat.), Volume 13, Dept. Math., Seconda Univ. Napoli, Caserta, 2004, pp. 327-346 | MR | Zbl

[45] Randrianarisoa, Tovohery Hajatiana A geometric approach to rank metric codes and a classification of constant weight codes, Des. Codes Cryptogr., Volume 88 (2020) no. 7, pp. 1331-1348 | DOI | MR | Zbl

[46] Sheekey, John A new family of linear maximum rank distance codes, Adv. Math. Commun., Volume 10 (2016) no. 3, pp. 475-488 | DOI | MR | Zbl

[47] Silva, Danilo; Kschischang, Frank R.; Kötter, Ralf A rank-metric approach to error control in random network coding, IEEE Trans. Inform. Theory, Volume 54 (2008) no. 9, pp. 3951-3967 | DOI | MR | Zbl

[48] Stichtenoth, Henning Algebraic function fields and codes, Graduate Texts in Mathematics, 254, Springer-Verlag, Berlin, 2009, xiv+355 pages | DOI | MR

[49] Taylor, Donald E. The geometry of the classical groups, Sigma Series in Pure Mathematics, 9, Heldermann Verlag, Berlin, 1992, xii+229 pages | MR

[50] Zanella, Corrado A condition for scattered linearized polynomials involving Dickson matrices, J. Geom., Volume 110 (2019) no. 3, Paper no. 50, 9 pages | DOI | MR | Zbl

[51] Zanella, Corrado; Zullo, Ferdinando Vertex properties of maximum scattered linear sets of $PG (1, q^{n})$ , Discrete Math., Volume 343 (2020) no. 5, Paper no. 111800, 14 pages | DOI | MR | Zbl

[52] Zini, Giovanni; Zullo, Ferdinando Scattered subspaces and related codes, Des. Codes Cryptogr., Volume 89 (2021) no. 8, pp. 1853-1873 | DOI | MR | Zbl

Cited by Sources: