Alexei Belov, Louis Rowen & Uzi Vishne

Normal basis of algebras


This talk is devoted to algorithmic and combinatorial problems related to normal forms of elements in ring theory.

Due to Shirshov's height theorem, a finitely generated PI-algebra A is spanned by the set of words of following type

u i1k1 … u isks

where {u i} is a fixed set of words in the generators, and s is bounded by the height h of the algebra.

We will touch the following problems:

  1. What sets of words can serve as {u i} in the above assertion? This is related with conjecture of S. Amitzur and I. Shestakov.
  2. What can be said about set of power vectors {k1,…,ks} corresponding to "irreducible words" (these are the words that cannot be represented as the linear combination of lexicographically smaller words).

This set of power vectors can be expressed in terms of a system of exponential polynomials in the variables k1,…,ks:

∑i Pij (k1,…,ks) λ1ij1 … λks ijs = 0 .

Due to results of J. Robinson and Yu. Matziasevich in connection to Hilbert's tenth problem, many problems related to isomorphism problem and structure of bases of representable algebras are algorithmically unsolvable. On the other hand, the speaker proved (with Chilikov) that in positive characteristic, the set of solutions of any such system can be described in terms of a regular langauge, and in particular can be handled algorithmically. This implies a positive solution of many algoritmic problems of positive characteristics which are unsolvable in zero characteristic.