I wonder how hard identity testing (similar to polynomial identity testing) can be for a free algebra. I thought that in a certain sense, the problem should always be semi-decidable, because the free algebra is defined with respect to the identities which follow from the given set of equational axioms. So how do I have to interpret the following statement from Equational and universal Horn theory of modular lattices:

The free modular lattice on 4 or more generators has an unsolvabe word problem.

Are they talking about the same identity testing problem I'm interested in? Do they use "unsolvable" instead of "semi-decidable", because the semi-decidability is obviously already part of the definition? Or does unsolvable quite generally just means that one of the two directions is not decidable?

  • $\begingroup$ Unsolvable word problem means undecidable. But a free modular lattice is very far from free algebraically. $\endgroup$ – Matt Samuel Dec 15 '15 at 11:40
  • $\begingroup$ All algebras defined by a presentation are defined by the identities that follow from the relations. Decidability of the word problem has to do with being able to find certain equations algorithmically, not whether they exist. In that sense the word problem is always decidable, except that it can be independent of the axioms (which it generally is) and nobody really understands what goes on in that case. $\endgroup$ – Matt Samuel Dec 15 '15 at 11:55
  • 1
    $\begingroup$ @MattSamuel Why do you mean that a free modular lattice is very far from free algebraically? It seems to fit exactly the definition of a free algebra. No sets of relations in addition to the equational axioms seem to be allowed, so it seems significantly more restricted than an algebra presented by a set of generators and relations. (In which case the relations would be allowed to explicitly name a specific generator, while the equational axioms only contain universal quantified variables without any reference to the generators). $\endgroup$ – Thomas Klimpel Dec 15 '15 at 12:29
  • 1
    $\begingroup$ the "equational axioms" are relations. They don't disappear because every algebra of the type satisfies them. $\endgroup$ – Matt Samuel Dec 15 '15 at 12:39
  • $\begingroup$ @MattSamuel I thought about it some more, and came to the conclusion that equational axioms and relations are completely different things. If $a,b,c$ are your generators, then a relation is an equation between $a,b,c$ containing no free variable (=universally quantified variable) at all. An equational axiom on the other hand is an equation between free variables, containing no generators at all. $\endgroup$ – Thomas Klimpel Dec 15 '15 at 18:01

Yes this theorem states that, for any fixed $n$ at least 4, the equational theory of modular lattices in $n$ generators is not computable. Here a lattice is viewed as an algebra with two binary operations, not as a relational structure. Ralph Freese


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.