SMS scnews item created by Andrew Mathas at Thu 19 Jun 2014 1621
Type: Seminar
Distribution: World
Expiry: 24 Jun 2014
Calendar1: 24 Jun 2014 1500-1600
CalLoc1: AGR Seminar
CalTitle1: AGR Seminar: Algorithms and statistics for additive polynomials
Auth: in SMS-auth

AGR Seminar

Algorithms and statistics for additive polynomials

Professor Mark Giesbrecht (University of Waterloo)

Host venue
University of Newcastle (CARMA)


The additive or linearized polynomials were introduced by Ore in 1933 as an analogy over finite fields to his theory of difference and difference equations over function fields. The additive polynomials over a finite field F=3DGF(q), where q=3Dp^e for some p, are those of the form f =3D f_0x+f_1x^p + f_2x^{p^2} + ... + f_mx^{p^m} in F[x]. They form a non-commutative left-euclidean principal ideal domain under the usual addition and functional composition, and possess a rich structure in both their decomposition structures and root geometries. Additive polynomials have been employed in number theory and algebraic geometry, and applied to constructing error-correcting codes and cryptographic protocols. In this talk we will present fast algorithms for decomposing and factoring additive polynomials, and also for counting the number of decompositions with particular degree sequences. Algebraically, we show how to reduce the problem of decomposing additive polynomials to decomposing a related associative algebra, the eigenring. We give computationally efficient versions of the Jordan-Holder and Krull-Schmidt theorems in this context to describe all possible factorization. Geometrically, we show how to compute a representation of the Frobenius operator on the space of roots, and show how its Jordan form can be used to count the number of decompositions. We also describe an inverse theory, from which we can construct and count the number of additive polynomials with specified factorization patterns. Some of this is joint work with Joachim von zur Gathen (Bonn) and Konstantin-Ziegler (Bonn).

Seminar convenor
Matthew Tam

AGR technical support
David Allingham


If you would like to attend this seminar in our access grid room then please book the access grid room referring to this scnews item. Please liaise with the host institution to make any necessary arrangements and then send an email to to let the CSOs know of any special requirements for the seminar.

If you are registered you may mark the scnews item as read.
School members may try to .