Skip to main content
Code Golf

Return to Answer

Add brief definitions of free group and generated subgroup (addressing comment by @Bbrk24), and add some harmless restrictions on input
Source Link
Daniel Schepler
Daniel Schepler
  • 1.4k
  • 7
  • 3

Suppose you are given the free group \$F_n\$ on \$n\$ generators\${}^1\$, a finite subset \$S\$ of \$F_n\$, and an element \$x \in F_n\$. Then there is an algorithm to determine whether \$x\$ is in the subgroup generated\${}^2\$ by \$S\$, as follows:

If it is useful, you may assume the list of subgroup generators is nonempty, and also that \$x\$ and each element of the list is not the empty word.

[], identity (empty string) -> True
[], abc -> False
[aa, ab], a -> False
[aa, ab], ba -> False
[aa, ab], Ba -> True
[aBc, bc], identity -> True
[aBc, bc], aBBCbA -> True
[aBc, bc], abc -> False
[identity, identity], a -> False
[aaaaa, aaa], a -> True

This is : the shortest code in bytes for any given programming language wins.

\${}^1\$ The free group \$F_n\$ on \$n\$ generators can be described as the reduced words in the alphabet consisting of formal symbols \$g_1, g_1^{-1}, g_2, g_2^{-1}, \ldots, g_n, g_n^{-1}\$. Here, "reduced" means that \$g_i\$ and \$g_i^{-1}\$ never appear next to each other in the word. To multiply two words, concatenate them and then iteratively cancel out pairs \$g_i g_i^{-1}\$ or \$g_i^{-1} g_i\$ in the middle. This has the empty word as an identity element, and to find the inverse of a reduced word, reverse the order and transform each \$g_i\$ into \$g_i^{-1}\$ and vice versa.

\${}^2\$ The subgroup of \$F_n\$ generated by a subset \$S \subseteq F_n\$ is the smallest subset of \$F_n\$ which contains \$S\$, also contains the identity element, and is closed under multiplication and inverses. This can alternately be described as the set of elements of \$F_n\$ which can be formed as the product of some finite sequence of elements of \$S\$, and/or their inverses.

Suppose you are given the free group \$F_n\$ on \$n\$ generators, a finite subset \$S\$ of \$F_n\$, and an element \$x \in F_n\$. Then there is an algorithm to determine whether \$x\$ is in the subgroup generated by \$S\$, as follows:

[], identity (empty string) -> True
[], abc -> False
[aa, ab], a -> False
[aa, ab], ba -> False
[aa, ab], Ba -> True
[aBc, bc], identity -> True
[aBc, bc], aBBCbA -> True
[aBc, bc], abc -> False
[identity, identity], a -> False
[aaaaa, aaa], a -> True

This is : the shortest code in bytes for any given programming language wins.

Suppose you are given the free group \$F_n\$ on \$n\$ generators\${}^1\$, a finite subset \$S\$ of \$F_n\$, and an element \$x \in F_n\$. Then there is an algorithm to determine whether \$x\$ is in the subgroup generated\${}^2\$ by \$S\$, as follows:

If it is useful, you may assume the list of subgroup generators is nonempty, and also that \$x\$ and each element of the list is not the empty word.

[aa, ab], a -> False
[aa, ab], ba -> False
[aa, ab], Ba -> True
[aBc, bc], aBBCbA -> True
[aBc, bc], abc -> False
[aaaaa, aaa], a -> True

This is : the shortest code in bytes for any given programming language wins.

\${}^1\$ The free group \$F_n\$ on \$n\$ generators can be described as the reduced words in the alphabet consisting of formal symbols \$g_1, g_1^{-1}, g_2, g_2^{-1}, \ldots, g_n, g_n^{-1}\$. Here, "reduced" means that \$g_i\$ and \$g_i^{-1}\$ never appear next to each other in the word. To multiply two words, concatenate them and then iteratively cancel out pairs \$g_i g_i^{-1}\$ or \$g_i^{-1} g_i\$ in the middle. This has the empty word as an identity element, and to find the inverse of a reduced word, reverse the order and transform each \$g_i\$ into \$g_i^{-1}\$ and vice versa.

\${}^2\$ The subgroup of \$F_n\$ generated by a subset \$S \subseteq F_n\$ is the smallest subset of \$F_n\$ which contains \$S\$, also contains the identity element, and is closed under multiplication and inverses. This can alternately be described as the set of elements of \$F_n\$ which can be formed as the product of some finite sequence of elements of \$S\$, and/or their inverses.

Source Link
Daniel Schepler
Daniel Schepler
  • 1.4k
  • 7
  • 3

Finitely generated subgroups of free groups

Suppose you are given the free group \$F_n\$ on \$n\$ generators, a finite subset \$S\$ of \$F_n\$, and an element \$x \in F_n\$. Then there is an algorithm to determine whether \$x\$ is in the subgroup generated by \$S\$, as follows:

  • Start with a directed graph with a single "base" vertex, and no edges.
  • For each element of \$S\$, add a cycle to the graph according to the corresponding free group word. Start at the base vertex; for each generator \$g_n\$ in the word, add an arrow labelled by \$n\$; for each inverse of a generator \$g_n^{-1}\$ in the word, add an arrow in the opposite direction labelled by \$n\$; and end at the base vertex.
  • If there is a pair of edges with the same label and with either the same source or the same destination, merge those two edges and the two vertices at the other end. (Except that merging two vertices is not necessary if the two edges have the same source and the same destination.)
  • Iterate the previous step until there is no such pair of edges left.
  • Now follow the graph from the base vertex, according to the reduced free group word corresponding to \$x\$. For each generator \$g_n\$ in the word, look for an edge with source at the current vertex and label \$n\$, and move to the destination of that edge. For each generator \$g_n^{-1}\$ in the word, look for an edge with target at the current vertex and label \$n\$, and move to the source of that edge.
    • If at any point, you do not find such an edge, then \$x \notin \langle S \rangle\$.
    • If at the end, you end up back at the base vertex, then \$x \in \langle S \rangle\$; otherwise, \$x \notin \langle S \rangle\$.

(I plan to give an example of the operation of this algorithm; but I do not have time at the moment to generate the required graph diagrams.)

Task

Your task is: given a finite subset \$S\$ of a free group \$F_n\$ and an element \$x \in F_n\$, determine whether \$x\$ is in the subgroup generated by \$S\$. (Note: we are not asking to determine whether \$x\$ is in the normal subgroup generated by \$S\$; that problem is undecidable in general.)

You are not required to use the above algorithm. On the other hand, your program or function must always terminate in finite time; so for example, that rules out a naive algorithm just taking all possible products of elements of \$S\$ and their inverses and determining whether you eventually find \$x\$ in the output.

Input

You will be given a list of free group elements, and a second input giving another free group element. Possible input formats for free group elements include:

  • An element of a built-in free group type.
  • A string in the form abCbcA where the generators are a through z and for example C represents the inverse of the generator c. You may assume the string is in reduced form, so for example it will not contain either Cc or cC.

If you like, you could also take a single list of free group elements, and use the first element as \$x\$ and the rest of the list as \$S\$.

Output

A truthy/falsey value according to whether or not \$x \in \langle S \rangle\$, where \$S\$ is the set of elements of the list for the first input and \$x\$ is the second input.

Examples

[], identity (empty string) -> True
[], abc -> False
[aa, ab], a -> False
[aa, ab], ba -> False
[aa, ab], Ba -> True
[aBc, bc], identity -> True
[aBc, bc], aBBCbA -> True
[aBc, bc], abc -> False
[identity, identity], a -> False
[aaaaa, aaa], a -> True

Score

This is : the shortest code in bytes for any given programming language wins.