3
$\begingroup$

I am working on computing the Davenport constant $D(G)$ of symmetric groups, which is the minimal number $d$ such that every sequence of $d$ elements, possibly with repetitions, is one-product, i.e. there is always some subsequence with product (in some order) the identity element. For example for $S_3$, the Davenport constant is 4 since every sequence of four elements we can always get identity element, however there are some maximal one product-free sequences of length 3, e.g. $(1,2),(1,3),(2,3)$ or $(1,2,3),(1,2,3),(1,2)$.

There is nothing done for symmetric groups and I am using combinatorial proofs, since computations (even with computer) are extremely huge. We know the constant for all non-abelian groups of order at most 42 and $A_5$, for which $D(A_5)=9$.

In particular, now I am focusing on $S_5$ and $S_3^n$. Could someone give me a hint about which strategy to follow, in case you come up with a nice strategy? For $S_5$ I know that $D(A_5)=9$, i.e., every 9 elements in $A_5$ we get identity and I want to prove the same for any 9 odd elements in $S_5$. Moreover, maximal one-product free sequences of length 8 in $A_5$ consist of eight 5-cycles, hence using this information I know that $D(S_5)\le12$ and also $D(S_5)\ge10$, since we get a one-product free sequence of length 9 by taking maximal one-product free sequence of length 8 in $A_5$ and any odd permutation.

I strongly believe it is either 10 or 11 but I do not know how to prove it. I am stuck here, any ideas?

Improve this question
$\endgroup$
12
  • $\begingroup$ I think that by "subsequence" you allow non-contiguous subsequences, right? $\endgroup$
    – Brendan McKay
    Commented Jun 30 at 5:45
  • 1
    $\begingroup$ Can you find a sequence of length 5 which is both one-free and inverse-free (i.e. $g$ and $g^{-1}$ don't both appear as subsequence products)? Then you can join two copies together to make a sequence of length 10. $\endgroup$
    – Brendan McKay
    Commented Jun 30 at 6:09
  • $\begingroup$ Also posted to math.stack, math.stackexchange.com/questions/4937972/… without notification to either site, a violation. $\endgroup$
    – Gerry Myerson
    Commented Jun 30 at 7:32
  • $\begingroup$ And another unlinked question by this same user, mathoverflow.net/questions/474161/… $\endgroup$
    – Gerry Myerson
    Commented Jun 30 at 8:21
  • $\begingroup$ @BrendanMcKay Thanks for the rwsponse! Yes exactly, I allow non-contiguous subsequences. In particular, we allow any subsequence $g_{i1}, ..., g_{ir}$ so that the product of elements in some order gives identity. I see what you idea is, however I believe is not enough. Imagine that we find sich a sequence with some transposition, wlog $(12)$. Then, when we take the copy we have two times $(12)$ hence we get identity. $\endgroup$
    – Mikel Martinez Puente
    Commented Jun 30 at 10:38

1 Answer 1

Reset to default
3
$\begingroup$

In a comment, Brendan McKay suggested searching for quintuples which are one-free and inverse-free. There are no such quintuples, but there are quadruples, and by repeating elements from one such I present a 10-tuple which is one-free.

Let $\pi_3 = (3, 4, 5)$, $\pi_{32} = (1, 2, 3, 4)$, $\pi_{61} = (1,3)(2,4,5)$. The sequence is $\pi_3^2 \cdot \pi_{32}^3 \cdot \pi_{61}^5$. The following Sage code checks the claim that this is one-free:

S5 = list(Permutations(5))

identity = S5[0]
multiset = (S5[3],) * 2 + (S5[32],) * 3 + (S5[61],) * 5
print(S5[3].cycle_string())
print(S5[32].cycle_string())
print(S5[61].cycle_string())

for order in Permutations(multiset):
    partial = identity
    for elt in order:
        partial *= elt
        if partial == identity:
            print("Failed for", order)

print("Success")

Run it online

Therefore $D(S_5) \ge 11$.

Improve this answer
$\endgroup$
7
  • $\begingroup$ It appears that the typical maximum one-free multisets contain few distinct elements each with multiplicity one less than its order, and that makes some intuitive sense because repeating an element as much as possible reduces the number of distinct products. Thus one strategic idea we can take is to test multisets of this form first in order to get lower bounds. $\endgroup$
    – Peter Taylor
    Commented Jul 3 at 8:28
  • $\begingroup$ By exhaustive search, any one-free multiset of 11 elements contains at least 5 distinct elements. $\endgroup$
    – Peter Taylor
    Commented Jul 3 at 18:47
  • $\begingroup$ Yes, it makes sense! Thank you so much for your suggestions and help!! I will try to work on that for further cases of $S_n$. By the way, I am not an expert in Gap but I am trying to prove that $D(S_5)=11$ by brute force (almost done), in the last comment you say that any one-free multiset of 11 elements contain at least 5 distinct elements, I guess you have checked all possibilities with only 4 distinct elements and all are one-product sequences, right? Or have you found some one-free multiset of 11 elements? $\endgroup$
    – Mikel Martinez Puente
    Commented Jul 4 at 11:32
  • 1
    $\begingroup$ @MikelMartinezPuente, yes, I checked all possibilities with 4 distinct elements. I found the inverse-free multiset of 4 elements by iterative deepening: extend inverse- and one-free multisets of $k$ elements to $k+1$ elements by trying all possibilities. I actually wrote that in Python and just converted to Sage for the answer because it shifts the burden of trusting correctness to Sage's implementation rather than mine. I could rewrite it in Sage, but it's quite naïve (and in particular doesn't exploit the automorphism group to gain efficiency by using representatives of cosets). $\endgroup$
    – Peter Taylor
    Commented Jul 4 at 13:36
  • 1
    $\begingroup$ @MikelMartinezPuente, Sage code. $\endgroup$
    – Peter Taylor
    Commented Jul 4 at 15:51

You must log in to answer this question.

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