22
$\begingroup$

Let $n \in \mathbb{N}$. Is it true that for every $k \in \{1, \dots, n!\}$ there are some group $G$ and pairwise distinct elements $g_1, \dots, g_n \in G$ such that the set $\{g_{\sigma(1)} \cdot \ \dots \ \cdot g_{\sigma(n)} \ | \ \sigma \in {\rm S}_n\}$ of all products of the $g_i$ obtained by permuting the factors has cardinality $k$?

Added on Mar 21, 2013: On Mar 19, 2013, Benjamin Young gave a presentation of a group in which the above set has cardinality $\leq k$ (see below). As such this is trivial, since this is the case in particular in every abelian group. The thing that is missing to turn this into an answer to the question is to prove that the given relations do not force equality among any other products.

The assertion is true at least for $n \leq 4$. In case $n = 4$, for all $k \in \{1, \dots, 4!\}$ suitable 4-tuples of group elements can be taken from ${\rm S}_5$:

k =  1: (), (1,2), (3,4), (1,2)(3,4)              [    215]
k =  2: (), (1,2)(3,4), (1,2,3,4), (2,4)          [   1845]
k =  3: (), (2,3), (2,3,4), (3,4)                 [  10230]
k =  4: (), (1,2), (2,3), (3,4)                   [  38870]
k =  5: (), (1,2), (2,3), (2,3,4)                 [  85350]
k =  6: (), (1,2), (2,3), (2,4)                   [ 186220]
k =  7: (1,2), (1,2,3,4), (2,3,4), (2,4,3)        [   7920]
k =  8: (1,2), (2,3), (2,3,4), (2,4,3)            [  40560]
k =  9: (1,2), (2,3), (2,3,4), (3,4)              [  39535]
k = 10: (1,2), (1,2)(3,4), (2,3), (2,3,4),        [  96240]
k = 11: (1,2), (1,2)(3,4), (2,3), (2,4)           [ 116715]
k = 12: (1,2), (1,2,3), (2,4,3), (2,4)            [ 264360]
k = 13: (1,2), (1,2,3), (1,5), (2,3,4)            [ 284020]
k = 14: (1,2), (1,2,3), (1,5), (2,4)              [ 449940]
k = 15: (1,2,3), (1,2,3,4), (1,5), (2,3,4)        [ 525420]
k = 16: (1,2), (1,2,3), (1,5), (2,4,3)            [ 814070]
k = 17: (1,2,3), (1,2,3,4), (1,5), (2,3)          [1034670]
k = 18: (1,2)(3,4), (1,2,3,4), (1,2,4,3), (1,5)   [1208650]
k = 19: (1,2), (1,2,3), (1,2,3,4), (1,5)          [1199930]
k = 20: (1,2,3,4), (1,2,4,3), (1,3,2,4), (1,5)    [ 968760]
k = 21: (1,2)(3,4), (1,2,3,4), (1,5)(3,4), (2,3)  [ 527160]
k = 22: (1,2)(3,4), (1,3), (1,4), (1,5)           [ 242340]
k = 23: (1,2,3), (1,2,3,4), (1,5)(3,4), (2,4,3)   [  63240]
k = 24: (1,2), (1,3), (1,4), (1,5)                [   8310]

In brackets (added on Sep 18, 2013): the numbers of such 4-tuples of elements of ${\rm S}_5$.

Added on Sep 18, 2013: In case $n = 5$, at least for all $k \in \{1, \dots, 5!\} \setminus \{117, 119\}$, suitable 5-tuples of group elements can be taken from ${\rm S}_6$ -- see 5tuples.txt.

Update (December 2013): This question will appear as Problem 18.50 in:

Kourovka Notebook: Unsolved Problems in Group Theory. Editors V. D. Mazurov, E. I. Khukhro. 18th Edition, Novosibirsk 2014.

Improve this question
$\endgroup$
4
  • $\begingroup$ In your example you have one group working for all k up to n! Is this what you want or can the group change? $\endgroup$
    – Benjamin Steinberg
    Commented Mar 7, 2013 at 22:11
  • 3
    $\begingroup$ I think this doesn't make a difference -- if $G$ works for $k_1$ and $H$ works for $k_2$, then $G \times H$ works for both. $\endgroup$
    – Stefan Kohl ♦
    Commented Mar 7, 2013 at 23:23
  • 1
    $\begingroup$ What about generalizing the problem: given any equivalence relation on $S_n$, can one find $G$ and the $g_i$ such that the map $S_n\to G,\: \sigma \mapsto g_{\sigma(1)}\cdot\ldots\cdot g_{\sigma(n)}$ identifies two permutations if and only if they are equivalent? Or is this trivially false? $\endgroup$
    – Tobias Fritz
    Commented Apr 1, 2014 at 1:40
  • 2
    $\begingroup$ Trivially false: if $abc=acb$, then $bca=cba$ as well. $\endgroup$
    – fedja
    Commented May 31, 2014 at 11:00

1 Answer 1

Reset to default
-1
$\begingroup$

Pedantic answer: take $G$ to be a finitely presented group on $n+1$ generators $x_i$, with relations of the form $x_{n+1}^{-1}x_{\sigma(1)}...x_{\sigma(n)}$. Here, $\sigma$ ranges over your favorite set of $n!-k+1$ permutations. Take $g_i=x_i$.

If you really want a finite group $G$, then I don't know.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ You ensure that at least $n!-k+1$ of the products of the $g_i$ are equal -- but can you also prove that the remaining $k-1$ are pairwise distinct? -- Your relations might force some of them to be equal as well, or at least I don't see why they don't. $\endgroup$
    – Stefan Kohl ♦
    Commented Mar 19, 2013 at 9:41
  • 1
    $\begingroup$ Hmm, I guess I don't either, now that you mention it. $\endgroup$
    – Benjamin Young
    Commented Apr 25, 2013 at 5:14

You must log in to answer this question.

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