What’s New

Research visit to Perugia

From October 27 til November 1, Peter Beelen visited Prof. Massimo Giulietti and his team at the Università degli Studi di Perugia in Italy. During the visit he finished an article with Maria Montanucci, who visited DTU as a guest PhD in 2017. Directly after the visit, Maria started as a postdoctoral researcher at the University of Padua.

In the joint article certain subfields are described of the new maximal function fields found by Maria and Peter in 2017. Such subfields are of interest, since by a result of Serre, they are maximal as well. The article has been submitted to the journal Finite Fields and Their Applications. A preprint is available here.

FNU-funded PhD starts

Grigory Solomatov PhD student at Algebra Group DTU

On October 15, PhD student Grigory Solomatov joined our team! Grigory did a dual master at NTNU and DTU. In the coming three years, he will work on the decoding of AG-codes. His project is an important part of the FNU-project “Correcting on a Curve”.

Research project in the media

Our research project “Correcting on a Curve”, funded by DFF-FNU, has received attention in the media, more specifically the web-based business newspaper Finans.dk:

Danske forskere vil udvikle verdens hurtigste fejlrettende koder

(The full article is unfortunately behind a paywall)

Our project is also featured by DFF’s web page for funded projects:

https://dff.dk/cases/forskere-skal-udvikle-verdens-hurtigste-fejlrettende-koder-til-digital-kommunikation

Paper on record-breaking decoding accepted

The paper “Improved Power Decoding of Interleaved One-Point Hermitian Codes” was accepted for publication in the journal Designs, Codes and Cryptography, and should appear soon!

Visit by Prof. Mark Giesbrecht

During the first week of September 2018, Professor Mark Giesbrecht visited Johan. Mark is Director of the David R. Cheriton School of Computer Science at the University of Waterloo. His research is in symbolic mathematical computation, both developing the algorithmic and complexity theoretical tools as well as building computer algebra software. He was named ACM Distinguished Scientist in 2013 and received an NSERC Synergy Award in 2003 for work with MapleSoft on Maple.

During his visit, Mark and Johan worked together on computing reduced forms of matrices over Ore polynomial rings, with a focus on \(\mathbb Q[x][\partial; d/dx]\). Ore polynomials are a type of non-commutative polynomials which has applications in such diverse fields as partial differential equations, control theory, and coding theory. Matrices over such polynomials arise e.g. when studying systems of equations in these applications, and reducing the matrices can be used to find small representations of the systems which can reduce later, computationally hard steps. The work is together with Arne Storjohann also at University of Waterloo with whom Johan has worked on this issue earlier.

During his visit, Mark also gave a talk entitled “Algorithms and statistics for additive polynomials”

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 \(\mathbb{F}_q\), where \(q=p^e\) for some prime \(p\),
are those of the form

$$f = f_0 x + f_1 x^p + f_2 x^{p^2} + … + f_m x^{p^m} \in \mathbb{F}_q[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 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 (Landshut).

Paper on computing reduced form of polynomial matrices presented

The paper “Computing Popov and Hermite forms of rectangular polynomial matrices” was accepted at the prestigious ISSAC conference  earlier this year, and was recently presented at the conference in New York.

The paper is a collaboration between Johan Rosenkilde from the group,  former postdoc Vincent Neiger,  and former Master’s thesis student Grigory Solomatov. Parts of the results were obtained by Grigory during his Master’s thesis!

The paper concerns the computation of something similar to Gaussian elimination but for matrices with entries which are polynomials (univariate).  These kind of computations were recently improved by Vincent for square matrices, but it was still open how to generalise these results to cover rectangular matrices. There are good reasons why this generalisation is not completely straightforward, and in fact most of Grigory’s thesis work was about shooting down all the obvious ways one could think of doing this.

In the end, we found a very elegant randomized algorithm, which is fast in many cases, and a more sophisticated algorithm which works well in almost all cases. The issue is not completely settled, though, and there are still a spectrum of input for which we believe a slightly faster algorithm should exist. That’s for future work!

The full paper can be found here. 

DFF-FNU research project 1 grant received!

Danmarks Frie Forskningsfond (Independent Research Fund Denmark) each year supports many prestigious research projects. They have just announced that they will support a research project of the algebra group. This grant will enable us to hire a Ph.D. student as well as to visit and invite researchers from all over the world. We are very grateful for the support!

A brief summary of the research project is the following:

Error-correcting codes ensure reliability in e.g. satellite communication, distributed storage and cloud computing. It is vital that the error-correction can be done fast. Excellent error-correcting codes can be constructed using algebraic curves – AG codes – but no fast decoding algorithms are available for these codes. This has limited their theoretical impact and prohibited any practical impact. This project aims to change that.

Decoding of AG codes boils down to solving a Padé approximation on the algebraic curve. Current techniques throw away many levels of structure, leaving a problem on univariate polynomials. We will seek algorithms that retain these levels, and we will build on the latest developments in computer algebra. We expect improvements for both the simplest as well as more complex AG codes.

The project will be carried out by the algebra group at DTU and international collaborators from France and Canada.

Prof. Masaaki Homma visiting the algebra group

From April 15 til May 8, Prof. Masaaki Homma from Kanagawa University visits the algebra group. He will work with Peter Beelen and Mrinmoy Datta on problems related to the intersection of a Hermitian surface and a surface of degree d. The aim is to solve a conjecture posed by a Danish Ph.D. student A.B. Sørensen in 1991. For d=1 and d=2 the conjecture is known to be true, while Peter and Mrinmoy recently made significant progress for d=3, see this previous post. For d>3 nothing is known as yet, but this may change soon!

Published article in FFA.

As announced in a previous post, Peter Beelen and guest Ph.D. Maria Montanucci recently solved a conjecture on the structure of Weierstrass semigroups of points on the Giulietti-Korchmaros maximal curve. These results have now appeared in the journal Finite Fields and Their Applications. Click here to see the article.

Progress Sørensen’s conjecture

Peter Beelen and Mrinmoy Datta have just submitted an article in which a conjecture from 1991 by Sørensen is partially resolved. In this conjecture a formula for the minimum distance of q^2-ary codes constructed from Hermitian surfaces is given. Equivalently, the conjecture gives a formula for the maximal number of GF(q^2)-rational points that a Hermitian surface and a hypersurface of degree d>1 can have. For d=2, the conjecture was solved in 2007 by Edoukou, but since then no progress has been made until now. We show that the conjecture is correct for d=3 as long as q>7. A preprint can be found here.