Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
    
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
3  
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
1  
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 at 1:40
2  
Trivially false: if $abc=acb$, then $bca=cba$ as well. –  fedja May 31 at 11:00

1 Answer 1

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.

share|improve this answer
1  
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
1  
Hmm, I guess I don't either, now that you mention it. –  Benjamin Young Apr 25 '13 at 5:14

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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