Block Companion Singer Cycles, Primitive Recursive Vector Sequences, and Coprime Polynomial Pairs over Finite Fields

Abstract

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.

12 pages; to appear in: Finite Fields and Their Applications

References in corpus (3)

• Efficient linear feedback shift registers with maximal period
• Primitive Polynomials, Singer Cycles, and Word-Oriented Linear Feedback Shift Registers
• Relatively Prime Polynomials and Nonsingular Hankel Matrices over Finite Fields

Cited by in corpus (8)

• The Splitting Subspace Conjecture
• Relatively Prime Polynomials and Nonsingular Hankel Matrices over Finite Fields
• A note on the multiple-recursive matrix method for generating pseudorandom vectors
• An asymptotic formula for the number of irreducible transformation shift registers
• Enumeration of Linear Transformation Shift Registers
• Splitting subspaces and a finite field interpretation of the Touchard-Riordan Formula
• Subspace Profiles over Finite Fields and $q$-Whittaker Expansions of Symmetric Functions
• Primitive transformation shift registers over finite fields