Type: Seminar

Distribution: World

Expiry: 24 Jun 2014

CalTitle1: AGR Seminar: Algorithms and statistics for additive polynomials

Auth: mathas@118.50.broadband5.iol.cz in SMS-auth

**Host venue**

University of Newcastle (CARMA)

**Abstract**

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 accessgridroom@maths.usyd.edu.au to let the CSOs know of any special requirements for the seminar.