Finding maximal orders in semisimple algebras over \(\mathbb{Q}\) (Q1312180)

The paper concerns the algorithmic problem of constructing a maximal order in a semisimple algebra over an algebraic number field. A polynomial time ff-algorithm is presented to solve the problem. (An ff- algorithm is a deterministic method which is allowed to call oracles for factoring integers and for factoring polynomials over finite fields. The cost of a call is the size of the input given to the oracle.) The method is based on the following iterative step: If an order is not locally maximal at some prime, a larger order can be constructed in polynomial time using calls to an oracle for factoring polynomials over finite fields. The implementation of this step is based on the theory of hereditary orders. There is a straightforward iterative method using purely linear algebra in lattices for embedding an order over a discrete valuation ring into a hereditary one. To embed a hereditary order into a maximal one, Jacobinski's theory on the structure of hereditary orders can be applied. The oracle for factoring integers is only used to factor the discriminant of a starting order. In case of group rings, this discriminant has prime factors all dividing the order of the group. As an application, a method is given to compute the degrees of the irreducible representations over an algebraic number field \(K\) of a finite group \(G\), in time polynomial in the discriminant of the defining polynomial of \(K\) and the size of a multiplication table of \(G\).