2
$\begingroup$

The Davenport constant $D(G)$ of a finite group $G$ is the minimal $d$ such that any sequence/multiset of length $d$ is one-product, i.e., identity can be obtained as a product (in some order) of some non-empty subsequence. The small davenport constant $d(G)$ is the maximal length of one-product free sequences, i.e., $d(G)+1=D(G)$. I am focusing on $S_n$ and $A_n$.

In another post Davenport constant $D(S_5)=10$ or $11$? for computing $D(S_5)$, it ended up showing that $d(S_5)=10$, and it is also known that $d(S_3)=3$ and $d(S_4)=6$. For these three cases $d(S_n)= {n \choose 2}=n(n-1)/2$ holds, i.e., maximal one-product free sequences have this length.

I think it might be just coincidence, however this combinatorial expression appears a lot in $S_n$. For example, it is the total number of transpositions, or the largest number of inversions an element can have. If we consider adjacent transpositions $(i, i+1)$ as generators of $S_n$, this could mean that the largest length that a permutation could have is exactly ${ n \choose 2}$. Maybe it has nothing to do but...is there any relation between ${n \choose 2}$ and $d(S_n)$??

Maybe is not equality but some lower or upper bound, which would also be very interesting. This means that either we could construct a family of maximal one-product free sequences of length ${n \choose 2}$ in $S_n$ (taking the idea of distinct tranpositions or inversions into account) or prove that any sequence with more than ${n \choose 2}$ elements must be one-product. Any other strategies to get upper and lower bounds for $S_n$ or $A_n$ are also very welcome! Thanks a lot for your help ;)

$\endgroup$
7
  • 1
    $\begingroup$ Your link to "another post" is to a comment by @PeterTaylor, itself linking to Sage code. Was that what you intended? Might you have meant to link to the answer on which it is a comment? $\endgroup$
    – LSpice
    Commented Jul 9 at 17:23
  • 1
    $\begingroup$ The sequence of all $n\choose 2$ transpositions (in the lexicographic order) is 1-product free, right? $\endgroup$ Commented Jul 9 at 17:58
  • $\begingroup$ @FedorPetrov We are using that a sequence is one-product free if there is no subsequence with product one in ANY order. Thus, for n=4 for example we have (12)(34)(13)(24)(14)(23)=1. $\endgroup$ Commented Jul 10 at 1:39
  • 1
    $\begingroup$ @MikelMartinezPuente ah, ok. I would call it a "multiset", not a "sequence". $\endgroup$ Commented Jul 10 at 8:10
  • $\begingroup$ @DavidRoberts, about the edit, I took the "davenport" in the title to be intentional, per the usage in the post: there is the large-D Davenport constant $D$, and the small-d davenport constant $d$. (I am not sure how I would feel about this were it my name in play, but it seemed to be intentional.) $\endgroup$
    – LSpice
    Commented Jul 12 at 23:59

1 Answer 1

9
$\begingroup$

This guess must fail for large $n$ because $d(S_n)$ grows much faster than $n(n-1)/2$. Indeed $d(S_n) > n(n-1)/2$ for all $n \geq 16$ (and possibly also a few smaller $n$).

For any group $G$, a lower bound on $D(G)$ is the maximal order $|a|$ of any element $a \in G,$ because the sequence $a, a, a, \ldots$ of length $|a|-1$ is one-free. For $G = S_n$, this lower bound (Landau's function $g(n),$ OEIS sequence A000793) grows faster than $n(n-1)/2$ and indeed faster than any polynomial in $n$. Already for $n=16$ the product of disjoint cycles of lengths $4,5,7$ has order $140$ while $16(16-1)/2 = 120$. The OEIS goes just far enough to see that $D(S_{47}) \geq 120120 > 47^3$.

$\endgroup$
4
  • $\begingroup$ Thank you so much for the contribution! It is weird I dind't realise to check first such a natural lower bound of $D(S_n)$. By the way, do you know if there is an equivalent function as the Landau function for alternating groups? Thanks :) $\endgroup$ Commented Jul 10 at 18:58
  • $\begingroup$ You're welcome. For $A_n$, I don't know whether the maximal order has another name; I suppose you can call it $g_+(n)$. It must be at least as large as $g(n)/2$ (if the maximal order in $S_n$ is attained by an odd permutation then consider its square), and thus also increases faster than any polynomial in $n$. $\endgroup$ Commented Jul 10 at 19:11
  • $\begingroup$ Thanks a lot! That makes sense. Do you think there is also such an easy upper bound for $A_n$ or $S_n$? The unique idea I come up with is that $D(S_n) \leq n*D(S_{n-1})$ and of course $D(S_n) \leq 2*D(A_n)$, but still is need to know previous values... $\endgroup$ Commented Jul 11 at 10:53
  • $\begingroup$ @MikelMartinezPuente I don't know, sorry. The lower bound required only coming up with one example; upper bounds require actually proving something in all cases . . . $\endgroup$ Commented Jul 11 at 13:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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