Abstract

We discuss a number of open problems and conjectures in the theory and application of finite fields. We also provide a brief discussion of the status as well as references related to each problem.

Introduction

In this paper we try to summarise some interesting and/or important questions in the theory and application of finite fields. These questions obviously reflect our personal tastes but we have indeed tried to consider questions of general interest. We hope that these questions and even more, the methods developed for their solutions, will be of interest to other researchers. The reader may wonder why some questions we call ‘Problems’ and some we call ‘Conjectures’. Roughly speaking, we use the term Conjecture if we (and very often others) believe the statement to be true while the term Problem is used to indicate all other statements. In general we feel that our conjectures may be more difficult to resolve than our problems.

The standard notions of the theory of finite fields which we use can be found in the finite field bible by Lidl and Niederreiter.

Combinatorics

There are numerous open problems in combinatorics which are related to finite fields. In this section we briefly describe several of these. We begin with several questions related to latin squares. A latin square of order n is an n × n array based upon n distinct symbols with the property that each row and each column contains each of the n symbols exactly once.

This volume represents the refereed proceedings of the Third International Conference on Finite Fields and Applications held at the University of Glasgow, Scotland, 11–14 July, 1995, where it was hosted by the Department of Mathematics. The conference, often referred to as Fq3, was the successor of two other international conferences concerning finite fields held at the University of Nevada, Las Vegas, USA, in August 1991 and in August 1993. The Organising Committee comprised Steve Cohen, Stuart Hoggar, Bob Odoni (all of the University of Glasgow), James Hirschfeld (University of Sussex), Gary Mullen (Pennsylvania State University), Harald Niederreiter (Austrian Academy of Sciences) and Peter Shiue (University of Nevada, Las Vegas).

Finite fields with their tight structure are intrinsically fascinating; further, their study is now recognised to be extremely useful in diverse areas of pure and applicable mathematics, including aspects of number theory, algebra, analysis and algebraic geometry and, at the same time, manifold aspects of information theory, computer science and engineering. For example, coding theory is enriched by deep ideas, crucially involving finite fields, on exponential sums, function fields and linear algebra, and in turn, has stimulated further questions for finite field research. Indeed, what is particularly exciting in current activity is the interplay between various areas, within pure mathematics itself and within those having definite applications. A further sign of this vitality is the emergence in 1995 of the journal Finite Fields and Their Applications published by Academic Press.

Abstract. We give a survey on a topic in Finite Geometry which has generated considerable interest in the literature: the construction of maximal sets of mutually orthogonal Latin squares (MOLS) or, equivalently, of maximal nets. Most known constructions depend on finite fields either directly or via Galois geometry. Our subject splits naturally in two parts, namely the existence problem for small and large maximal sets of MOLS, respectively; in the first case, difference matrix methods have proved to be particularly useful, whereas the second case rests almost completely on the study of maximal partial t-spreads in finite protective spaces. For this reason, we also give a short review of what is known on the existence of maximal partial t-spreads.

INTRODUCTION

In what follows, we shall give a survey on a topic in Finite Geometry which has generated considerable interest in the literature: the construction of maximal sets of mutually orthogonal Latin squares (MOLS) or, equivalently, of maximal nets. As is well-known, the existence of a (Bruck) net of order s and degree r (for short, an (s, r)-net)) is equivalent to that of a set of r–2 mutually orthogonal Latin squares of order s; it is also well-known that this correspondence respects maximality as well as the stronger property of being transversal-free.

Abstract

New C++-implementations of the classical factorization algorithms for polynomials over finite fields of Berlekamp and the new ones of Niederreiter are presented. Their performances on various types of inputs are compared.

Introduction

The basic problem of factorizing univariate polynomials over the finite field Fq has got new impulses in the past few years with a new linearization technique developed by Niederreiter in [8], [9], [10]. Unlike Berlekamp's classical approach, which uses the Frobenius fixed point algebra in A := Fq[X]/(f) (where f is the polynomial to be factored), Niederreiter's method is based on the analysis of the solution space of certain differential equations in the field of rational functions Fq(X).

From the very beginning there have been several striking similarities between Niederreiter's and Berlekamp's algorithms in each step. Suppose for simplicity that the polynomial is monic and squarefree. Then in both algorithms a certain system of linear equations has to be set up and solved, leading to an Fq - subspace S of A, whose dimension coincides with the number of irreducible factors of f. Now the elements of S can be used to extract the irreducible factors of f by suitable gcd operations.

Niederreiter's algorithm has the following practical advantages: In the case of small fields the linear equations to be solved can be set up very efficiently. In particular in F2 they can be read off directly from the coefficients of f.

Abstract. This paper is a working out of the same-titled talk given by the author at the Third International Conference on Finite Fields and Their Applications in Glasgow, 1995. We give a survey on recent results on the characterization, the structure, the enumeration, and the construction of completely free elements and normal bases in finite dimensional extensions over finite fields.

A Strengthening of the Normal Basis Theorem. If E is a finite dimensional Galois extension over a field F with Galois group G, then the Normal Basis Theorem states that the additive group (E, +) of E is a cyclic module over the group algebra FG, i.e., there exists an element w in E such that the set {g(w) | g ∈ G} of G-conjugates of w is an F-basis of E. Such a basis is called a normal basis in E over F. Every generator w of E as FG-module is called a normal basis generator in E over F. For the sake of simplicity such an element is also called free in E over F.

If H is a subgroup of G, and Fix(H) is the intermediate field of E over F belonging to H via the Galois correspondence, i.e., the subfield of E which is fixed elementwise by H, then (E, +) likewise carries the structure of a Fix(H) H-module.