8
$\begingroup$

I am looking for a good name for the following problem:

Given elements $g_1,\dotsc,g_n$ in a (finitely generated) group $G$, determine if the product of their conjugacy classes $g_1^G\dotsb g_n^G$ contains the identity element $1$.

In some situations it might be more natural to pose this problem slightly differently:

Given elements $g_1,\dotsc,g_n$ and $g$ in $G$, determine if $g_1^G\dotsb g_n^G$ contains $g$.

This problem generalizes the conjugacy problem.

Geometrically the problem can be stated as follows: given a path-connected space $X$ (with fundamental group $G$) and a sphere with holes $S$, determine for every mapping $\partial S\to X$ (a mapping of the boundary circles of $S$ to $X$) if this mapping can be extended to a mapping $S\to X$.

It would be nice to also have consistent names for other related problems. In particular, for this one:

Given elements $g_1,\dotsc,g_n$ in $G$, determine if the product of their conjugacy classes $g_1^G\dotsb g_n^G$ contains a commutator.

Geometrically this problem can be stated as follows: given a path-connected space $X$ and a torus with holes $S$, determine for every mapping $\partial S\to X$ if this mapping can be extended to a mapping $S\to X$.

Suggestions

Would generalized conjugacy problem be an acceptable name for this problem? I've seen that this term is already used for other problems, but it does not seem to have a generally accepted meaning. For example i've seen it used for the simultaneous conjugacy problem, but we do not need two names for the same problem.

Improve this question
$\endgroup$
5
  • $\begingroup$ I thought this kind of problem was called factorization $\endgroup$
    – thedude
    Commented Mar 5, 2016 at 15:27
  • $\begingroup$ Well, but how to call this particular kind of factorization? $\endgroup$
    – Alexey Muranov
    Commented Mar 5, 2016 at 15:36
  • $\begingroup$ Do you know the paper "Enumeration of Planar Constellations" by Bousquet-Mélou and Schaeffer? You will find some references there. $\endgroup$
    – thedude
    Commented Mar 5, 2016 at 20:46
  • 1
    $\begingroup$ "product conjugacy problem"? it's not elegant, but more self-defined than the vague and commonplace "generalized". $\endgroup$
    – YCor
    Commented Mar 6, 2016 at 15:33
  • 1
    $\begingroup$ As it has been remarked in the other comments, the solvability of this problem and the solvability of the same problem with the additional requirement of outputting conjugating elements, are equivalent. But the latter step (exhaustive search) is highly ineffective, so in one has in mind implementation, or even complexity issues, these are distinct problems. $\endgroup$
    – YCor
    Commented Mar 6, 2016 at 15:35

1 Answer 1

Reset to default
3
$\begingroup$

There is a name for this problem: (the solvability of) a genus 0 quadratic equation over G. Check out Sections 2.1 and 3.3 in http://arxiv.org/abs/0802.3839.

This terminology is also consistent with your topological interpretation. Also, whether the set $$ g_1^G\cdots g_n^G $$ contains a commutator is equivalent to the solvability of the genus 1 quadratic equation $$ [x,y]\prod_{i=1}^n t_i^{-1}g_it_i=1. $$ in variables $x,y,t_1,\ldots,t_n$. This is terrible terminology.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Thanks Nick :). This might work for me. I have already thought of equations, but there can be slight variations of the problem where one would be looking not for the conjugating elements themselves but only for the conjugates of $g_1,\dotsc,g_n$. Also one may be interested in the decision problem: whether or not a solution exists. $\endgroup$
    – Alexey Muranov
    Commented Mar 6, 2016 at 15:36
  • $\begingroup$ Hi Alexey :-) If you look at the paper it's actually about a decision problem, i.e. the solvability of quadratic equations. In particular actual solutions to the quadratic equations aren't actually constructed, only certificates of the existence of a solution. Also whether a product of conjugates of $g_i$ contains a commutator is exactly whether a genus 1 quadratic equation with coefficients $g_1,\ldots,g_n$ has a solution. That being said, the solvability of genus 1 quadratic equations is terrible terminology, so I don't think my answer is that good :-) $\endgroup$
    – NWMT
    Commented Mar 7, 2016 at 15:48
  • $\begingroup$ I think after all that this terminology is quite precise and easy to generalize. One cannot expect to find a short unique descriptive name for every algorithmic problem. Besides, i was interested not only in solvability, but in solutions too. $\endgroup$
    – Alexey Muranov
    Commented Mar 8, 2016 at 13:10
  • $\begingroup$ How about calling $g_1^{t_1}\cdots g_n^{t_n}$ a spherical product since it corresponds to a spherical (a.k.a. genus 0) quadratic equation? $\endgroup$
    – NWMT
    Commented Mar 8, 2016 at 15:48

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .