Deciding Identities in Nonassociative Algebras with Dynamic Programming

点击翻译按钮获取中文摘要

This investigation is concerned with algorithms and computational techniques to decide if a given nonassociative polynomial is an identity for a variety of nonassociative algebras. In general, this problem is computationally very difficult, and existing methods suffer from prohibitive time and memory requirements. The approach used in this investigation is to use a dynamic programming algorithm. The algorithm solves the problem by constructing a certain homomorphic image of the free algebra. The number of arithmetic operations required to construct the algebra is bound by a polynomial in the dimension of the resulting algebra (but for many varieties the algorithm might not be polynomial-time in the input size). Using this method, it appears that many questions, which previously appeared to be computationally impractical, may now be solved with existing computers. Preliminary tests show that this method can be used to decide in minutes if certain polynomials, up to degree 10, were identities in the variety of commutative, fourth-power-associative algebras. While the method looks promising, several theoretic issues need to be examined in order to make the method more practical. A goal is to implement the full version of the algorithm on several specific problems. One such problem is the search for Jordan s-identities. Another is determining whether there exist nonspecial Malcev algebras.