# Numbers of distinct products obtained by permuting the factors

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.

-
In your example you have one group working for all k up to n! Is this what you want or can the group change? –  Benjamin Steinberg Mar 7 '13 at 22:11
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. –  Stefan Kohl Mar 7 '13 at 23:23
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? –  Tobias Fritz Apr 1 '14 at 1:40
Trivially false: if $abc=acb$, then $bca=cba$ as well. –  fedja May 31 '14 at 11:00

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.
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. –  Stefan Kohl Mar 19 '13 at 9:41