16
$\begingroup$

In the literature, one sometimes sees the claim that finitely presented quandles (in particular, knot quandles) are "hard to deal with". Hence, a great deal of effort has gone into studying finite quandles and counting homomorphisms onto them, and so on. However, I have not yet come across any theorems that state formal undecidability results for finitely presented quandles similar to those for finitely presented groups. In fact, I have yet to see any formulation of such problems. (For instance, a theorem stating that the isomorphism problem is undecidable for finitely presented quandles.)

Do such results exist in the literature and, if so, could someone please provide references?

(Asked previously here on math.stackexchange, without response.)

$\endgroup$
0

2 Answers 2

8
$\begingroup$

The word problem for quandles was formulated by Rena Levitt and Sam Nelson. In Levitt's research statement the problem was formulated as follows:

Word Problem for Quandles. Given a finitely generated quandle $Q$, is there an algorithm to determine if two words in the generators represent the same element of $Q$?

Levitt and Nelson solved the word problem for some families of quandles. In particular, they proved:

Theorem. Finitely generated free quandles and knot quandles have a solvable word problem.

You can see more information in these slides of a talk given by Levitt in 2012. As far as I know, the paper is not yet published.

$\endgroup$
1
  • 2
    $\begingroup$ Solvability of the word problem is trivial for conjugation quandles of groups with solvable word problem (hence for their finitely generated subquandles as well). Hence solvability of the word problem for f.g. free quandles follows from Joyce 1982 (embedding free quandles in free groups). $\endgroup$
    – YCor
    Mar 2, 2020 at 6:48
10
$\begingroup$

I do not believe that the word problem for quandles was first formulated by the team of Rena Levitt and Sam Nelson, if this formulation was made while Levitt was at Pomona. I had been working on this question well before 2011, which is when I assume Levitt arrived in Pomona and I am certain that it had been asked before. This is a standard question that people working in universal algebra or computation would ask of such a domain. I would not be surprised at all if Sam Nelson had encountered the question well before then, given the impressive array of work he has done on quandles.

If my chronology of this problem is missing some important historical details, I welcome any and all information.

A proof for the undecidability of the word problem for finitely presented quandles was discovered by James Belk and me at Bard College in June of 2009. This result was presented to the Bard College Mathematics Seminar in September of 2009, the SUNY New Paltz Mathematics Seminar in November of 2010, and the Algebra without Borders workshop at Yeshiva University in August of 2011. There might be some earlier proof, but it was and remains unknown to us.

Moreover, I shared a manuscript of the proof in the summer of 2012 with Benjamin Fish, then a Bard MATH REU student of mine and a Pomona undergraduate and now a graduate student in the mathematics department at the University of Illinois at Chicago. Fish then completed his senior research project in 2012-2013 on a related topic under Levitt at Pomona. I assume that this manuscript, or at least its contents were shared with Levitt.

Apropos the theorem at the end of the answer above… Joyce showed in his original paper that the free quandle FQ(A) over a generating set A can be embedded in the group quandle FG(A) over the free group on A. Hence the decidability of the word problem for FQ(A) reduces to the decidability of the word problem for FG(A), and the word problem for FG(A) is certainly decidable if A is finite. Hence the first part of the theorem is a straightforward consequence of Joyce's paper in 1982.

However, one can ask whether there is a more direct proof of the decidability of the word problem for free quandles over a finite generating set that does not appeal to group theory. There is such. Fix the following theory for the theory of quandles.

x*x = x

(x*y)/y = x

(x/y)*y = x

(x*y)z = (xz)(yz)

I discovered the following term rewriting system also in 2009:

x*x -> x

x/x -> x

(x*y)/y -> x

(x/y)*y -> x

x*(y*z) -> ((x/z)*y)*z

x/(y*z) -> ((x/z)/y)*z

x*(y/z) -> ((x*z)*y)/z

x/(y/z) -> ((x*z)/y)/z

This system is both terminating and confluent and hence has unique normal forms. In particular, you can use it to decide whether two words over FQ(A) are provably the same. Extensions of this result were the subject of a Bard senior research project with Hannah Quay-de la Vallee in 2009-2010 and my summer 2011 REU at Bard with then Drew University undergraduate Gregory Hunt, who is now in the Ph.D. program in Statistics at Michigan. The term rewriting system along with a proof of confluence and termination was also shared with Ben Fish and his REU colleagues in 2012.

That is not to say that the latter half of the Theorem stated above is not original. That appears to be new work. In fact, I had thought about this problem myself to no avail. However, the manner in which the answer above is presented might mislead the reader about the origin of some of the claims. I assume that this was an oversight and not intentional.

$\endgroup$
3
  • $\begingroup$ Thanks for the clarifications! Of course I did not know about all of this. $\endgroup$ Feb 2, 2015 at 8:07
  • $\begingroup$ The word problem is by the way defined in general for f.g. structures in the context of universal algebra; I guess this was certainly done around the middle of the XXth century. $\endgroup$
    – YCor
    Mar 2, 2020 at 6:50
  • 2
    $\begingroup$ The proof that @RobertMcGrail refers to that there exist finitely presented quandles with undecidable word problem has since been published here. $\endgroup$
    – Jim Belk
    Mar 2, 2020 at 12:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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