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

Improve this question
$\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$
    – Fedor Petrov
    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$
    – Mikel Martinez Puente
    Commented Jul 10 at 1:39
  • 1
    $\begingroup$ @MikelMartinezPuente ah, ok. I would call it a "multiset", not a "sequence". $\endgroup$
    – Fedor Petrov
    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

Reset to default
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$.

Improve this answer
$\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$
    – Mikel Martinez Puente
    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$
    – Noam D. Elkies
    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$
    – Mikel Martinez Puente
    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$
    – Noam D. Elkies
    Commented Jul 11 at 13:07

You must log in to answer this question.

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