There have been a good few interesting talks at GAIA2013 dealing with computation. Peter Jipsen's talk was, as usual, both fun and stimulating; today's talk by David Clark was also well worth listening to.
Talking to Peter today in one of the coffee breaks, I asked him what computational tool is currently unimplemented for universal algebraists that he would like to see. His answer: finite presentations.
To wit: if you are a group theorist, you can use GAP to investigate the following problem: consider the group\[\langle X \| \mathcal{R} \rangle\]given by a finite presentation. Now, it is a famous theorem that there does not exist an algorithm to determine whether two words in the generators evaluate to the same element; however, GAP tries to get "close" to this, whatever that might precisely mean.
This undecidability comes from the fact that a finitely presented group can still be infinite. But what if we're universal algebraists and we want to look at presentations with respect to a background theory strong enough to guarantee that finitely generated things are finite? Wait! We are universal algebraists, and such theories (called locally finite) are a stock in trade! In particular, presentations are the right tool for theories, like the theory of groups, which are axiomatized by equations.
Problem 1: Given a locally finite variety \( \mathcal{V} \) in a finite language, to produce an algorithm which efficiently solves the word problem with respect to finite presentations.
I left something out of the description of this problem, however: how we even told the computer enough about \( \mathcal{V} \) to make sense of the problem. I'm not going to remedy that: I don't know what you'd want to give the computer, or what would be reasonable to expect for an arbitrary locally finite variety.
The situation really isn't so bad, however, because we are very seldom actually interested in a completely arbitrary locally finite variety; instead, we're usually interested in varieties of the form \[ \mathcal{V} = \mathrm{HSP}(\mathbf{A}) \]that is, algebras \( \mathbf{B} \) which can be obtained by starting from some fixed finite algebra \( \mathbf{A} \), taking some direct power, then taking a subalgebra, then taking a homomorphic image. (Such varieties are called finitely generated.)
Together, Exercise 2 and Theorem 3 give a brute-force algorithm solving Problem 1 if \( \mathcal{V} \) is finitely generated. However, it's not a good algorithm.
Talking to Peter today in one of the coffee breaks, I asked him what computational tool is currently unimplemented for universal algebraists that he would like to see. His answer: finite presentations.
To wit: if you are a group theorist, you can use GAP to investigate the following problem: consider the group\[\langle X \| \mathcal{R} \rangle\]given by a finite presentation. Now, it is a famous theorem that there does not exist an algorithm to determine whether two words in the generators evaluate to the same element; however, GAP tries to get "close" to this, whatever that might precisely mean.
This undecidability comes from the fact that a finitely presented group can still be infinite. But what if we're universal algebraists and we want to look at presentations with respect to a background theory strong enough to guarantee that finitely generated things are finite? Wait! We are universal algebraists, and such theories (called locally finite) are a stock in trade! In particular, presentations are the right tool for theories, like the theory of groups, which are axiomatized by equations.
Problem 1: Given a locally finite variety \( \mathcal{V} \) in a finite language, to produce an algorithm which efficiently solves the word problem with respect to finite presentations.
INPUT:However, as stated, I don't know of even a brute-force algorithm that solves Problem 1.
OUTPUT:
- a finite set \(X = \{x_1, \ldots, x_n \}\) of generators
- a finite set \( \mathcal{R} = \{ u_1 = v_1, \ldots, u_\ell = v_\ell \} \) of relators. (Each \(u_i\) and \(v_i\) is a term built from the variables in \(X\).)
- two more terms \(a,b\) built from \(X\).
- "True" if, whenever \( \mathbf{A} \) is an algebra in \( \mathcal{V} \) generated by elements \( x_1, \ldots, x_n \) such that the terms \( u_i = v_i \) in \( \mathbf{A} \), the elements \(a(X) \) and \(b(X) \) are equal also,
- "False" otherwise.
I left something out of the description of this problem, however: how we even told the computer enough about \( \mathcal{V} \) to make sense of the problem. I'm not going to remedy that: I don't know what you'd want to give the computer, or what would be reasonable to expect for an arbitrary locally finite variety.
Exercise for the reader 2: Give an algorithm solving problem 1 in the case where we have an algorithm which, given an input \(n\), computes the word problem for the free algebra in \( \mathcal{V} \) on \(n\) generators.
The situation really isn't so bad, however, because we are very seldom actually interested in a completely arbitrary locally finite variety; instead, we're usually interested in varieties of the form \[ \mathcal{V} = \mathrm{HSP}(\mathbf{A}) \]that is, algebras \( \mathbf{B} \) which can be obtained by starting from some fixed finite algebra \( \mathbf{A} \), taking some direct power, then taking a subalgebra, then taking a homomorphic image. (Such varieties are called finitely generated.)
Theorem 3: The free algebra on \(n\) generators in \( \mathrm{HSP}(\mathbf{A}) \) can be found as a subalgebra of \( \mathbf{A}^{(A^n)} \) in an algorithmic way.
Sketch of proof: Elements of \( \mathbf{A}^{(A^n)} \) should be thought of as functions \( f: A^n \rightarrow \mathbf{A} \). The generators we want to use are the functions \[ \pi_i: \begin{bmatrix} a_1 \\ \vdots \\ a_n \end{bmatrix} \mapsto a_i \qquad (1 \leq i \leq n)\]. Now we just have to prove that this works.
Together, Exercise 2 and Theorem 3 give a brute-force algorithm solving Problem 1 if \( \mathcal{V} \) is finitely generated. However, it's not a good algorithm.
Problem 1': Give a better algorithm.
Problem 4: Find conditions under which the word problem for \( \mathcal{V} \)-presentations is polynomial-time. Then find the actual algorithm that works.
Problem 4': Find conditions under which the word problem for \( \mathcal{V} \)-presentations is in NP.
Problem 5: Implement these algorithms in Python, in UACalc, or in other systems.
No comments:
Post a Comment