Block companion singer cycles, primitive recursive vector sequences, and coprime polynomial pairs over finite fields. (English) Zbl 1263.11112
Summary: We discuss a conjecture concerning the enumeration of nonsingular matrices over a finite field that are block companion and whose order is the maximum possible in the corresponding general linear group. A special case is proved using some recent results on the probability that a pair of polynomials with coefficients in a finite field is coprime. Connection with an older problem of Niederreiter about the number of splitting subspaces of a given dimension are outlined and an asymptotic version of the conjectural formula is established. Some applications to the enumeration of nonsingular Toeplitz matrices of a given size over a finite field are also discussed.
MSC:
| 11T55 | Arithmetic theory of polynomial rings over finite fields |
| 11T06 | Polynomials over finite fields |
| 20G40 | Linear algebraic groups over finite fields |
| 15B05 | Toeplitz, Cauchy, and related matrices |
Keywords:
singer cycle; block companion matrix; multiple recursive matrix method; linear feedback shift register (LFSR); splitting subspace; Toeplitz matrixReferences:
| [1] | Benjamin, A. T.; Bennett, C. D., The probability of relatively prime polynomials, Math. Mag., 80, 196-202 (2007) · Zbl 1204.11059 |
| [2] | Corteel, S.; Savage, C.; Wilf, H.; Zeilberger, D., A pentagonal number sieve, J. Combin. Theory Ser. A, 82, 186-192 (1998) · Zbl 0910.05008 |
| [3] | Daykin, D. E., Distribution of bordered persymmetric matrices in a finite field, J. Reine Angew. Math., 203, 47-54 (1960) · Zbl 0104.01304 |
| [4] | Fine, N. J.; Herstein, I. N., The probability that a matrix be nilpotent, Illinois J. Math., 2, 499-504 (1958) · Zbl 0081.01504 |
| [5] | Gao, Z.; Panario, D., Degree distribution of the greatest common divisor of polynomials over \(F_q\), Random Structures Algorithms, 29, 26-37 (2006) · Zbl 1099.11072 |
| [6] | García-Armas, M.; Ghorpade, S. R.; Ram, S., Relatively prime polynomials and nonsingular Hankel matrices over finite fields, J. Combin. Theory Ser. A, 118, 819-828 (2011) · Zbl 1241.11134 |
| [7] | Ghorpade, S. R.; Hasan, S. U.; Kumari, M., Primitive polynomials, Singer cycles, and word-oriented linear feedback shift registers, Des. Codes Cryptogr., 58, 123-134 (2011) · Zbl 1263.11108 |
| [8] | B. Hanson, D. Panario, D. Thomson, Swan-like results for binomials and trinomials over \(\mathbb{F}_qq\) doi:10.1007/s10623-010-9476-7; B. Hanson, D. Panario, D. Thomson, Swan-like results for binomials and trinomials over \(\mathbb{F}_qq\) doi:10.1007/s10623-010-9476-7 · Zbl 1248.11097 |
| [9] | Hou, X.; Mullen, G. L., Number of irreducible polynomials and pairs of relatively prime polynomials in several variables over finite fields, Finite Fields Appl., 15, 304-331 (2009) · Zbl 1190.11063 |
| [10] | Jacobson, N., Basic Algebra I (1985), W.H. Freeman: W.H. Freeman New York · Zbl 0557.16001 |
| [11] | Kaltofen, E.; Lobo, A., On rank properties of Toeplitz matrices over finite fields, (Proc. 1996 Internat. Symp. Symbolic Algebraic Comput. (ISSAC ʼ96) (1996), ACM Press: ACM Press New York), 241-249 · Zbl 0914.65039 |
| [12] | Knuth, D. E., The Art of Computer Programming, Seminumerical Algorithms, vol. 2 (1969), Addison Wesley: Addison Wesley Reading, MA · Zbl 0191.18001 |
| [13] | Lidl, R.; Niederreiter, H., Finite Fields, Encyclopedia Math. Appl., vol. 20 (1983), Cambridge University Press: Cambridge University Press Cambridge · Zbl 0554.12010 |
| [14] | Niederreiter, H., Factorization of polynomials and some linear-algebra problems over finite fields, Linear Algebra Appl., 192, 301-328 (1993) · Zbl 0845.11042 |
| [15] | Niederreiter, H., The multiple-recursive matrix method for pseudorandom number generation, Finite Fields Appl., 1, 3-30 (1995) · Zbl 0823.11041 |
| [16] | Reifegerate, A., On an involution concerning pairs of polynomials in \(F_2\), J. Combin. Theory Ser. A, 90, 216-220 (2000) · Zbl 1010.11068 |
| [17] | Swan, R. G., Factorization of polynomials over finite fields, Pacific J. Math., 12, 1099-1106 (1962) · Zbl 0113.01701 |
| [18] | Tsaban, B.; Vishne, U., Efficient linear feedback shift registers with maximal period, Finite Fields Appl., 8, 256-267 (2002) · Zbl 1015.94005 |
| [19] | von zur Gathen, J., Irreducible trinomials over finite fields, Math. Comp., 72, 1987-2000 (2003) · Zbl 1083.11078 |
| [20] | Zeng, G.; Han, W.; He, K., Word-oriented feedback shift register: \(σ\)-LFSR, Cryptology ePrint Archive: Report 2007/114 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
