Enumeration of block companion Singer cycles

Samrith Ram

Date(s) : 12/12/2013   iCal
11 h 00 min - 12 h 00 min

We discuss 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. The problem is essentially equivalent to counting the number of so-called primitive ‘word-oriented’ linear feedback shift registers($\sigma$-LFSR). A connection with an older problem of Niederreiter about the number of splitting subspaces of a given dimension is outlined. A special case of the problem is equivalent to finding the probability that a pair of polynomials of given degree with coefficients in a finite field is coprime. We also discuss the enumeration of a subclass of $\sigma$-LFSRs called Transformation Shift Registers (TSR).

Samrith Ram, IIT Bombay

Catégories