# Is the small Davenport constant for $S_n$, $d(S_n)=n(n-1)/2$?

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 ;)

• 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? Commented Jul 9 at 17:23
• The sequence of all $n\choose 2$ transpositions (in the lexicographic order) is 1-product free, right? Commented Jul 9 at 17:58
• @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. Commented Jul 10 at 1:39
• @MikelMartinezPuente ah, ok. I would call it a "multiset", not a "sequence". Commented Jul 10 at 8:10
• @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.) Commented Jul 12 at 23:59

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$$.
• 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 :) Commented Jul 10 at 18:58
• 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$. Commented Jul 10 at 19:11
• 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... Commented Jul 11 at 10:53