Suppose G is a finite group. Define $\tau(G)$ as the minimal number, such that $\forall X \subset G$ if $|X| > \tau(G)$, then $XXX = \langle X \rangle$. What is $\tau(A_n)$?

Similar problems for some different classes of groups are already answered:

1) $\tau(\mathbb{Z}_n) = \lceil \frac{n}{3} \rceil + 1$ (this is a number-theoretic fact proved via arithmetic progressions)

2) Gowers, Nikolov and Pyber proved the fact that $\tau(SL_n(\mathbb{Z}_p)) = 2|SL_n(\mathbb{Z}_p)|^{1-\frac{1}{3(n+1)}}$ (this fact is proved with linear algebra)

However, I have never seen anything like that for $A_n$. It will be interesting to know if there is something...

  • 1
    $\begingroup$ I don't even understand the question. What do you mean when you say $XXX=\langle{X\rangle}$? $\endgroup$
    – C.S.
    Aug 6 '18 at 13:44
  • 1
    $\begingroup$ @crskhr, $XXX$ stands for the group subset product: $XXX = \{abc| a, b, c \in X\}$; $\langle X \rangle$ stands for group subset closure: $\langle X \rangle$ is the minimal subgroup that contains $X$. $\endgroup$ Aug 6 '18 at 13:52
  • $\begingroup$ Does anyone have the results for small values of $n$? $\endgroup$ Aug 21 '18 at 8:57
  • $\begingroup$ I expect that its pretty doable for 1 through 4. But then, for 5 it seems quite hard. $\endgroup$
    – user24142
    Aug 23 '18 at 1:27

I would guess that the answer is $O(n!/n)$. You can get an example of this size as follows. Partition $\Omega = \{1, \dots, n\}$ as $\{1\} \cup T \cup S$ where $|T| = t$, and let $X$ be the set of all $\pi$ such that $\pi(1), \pi^{-1}(1) \in T$ and $\pi(T) \subset S$. The density of $X$ is then comparable to $(t/n)^2 (1 - t/n)^t \approx (t/n)^2 \exp(-t^2/n)$. The best choice for $t$ is $cn^{1/2}$ for some constant $c$. Meanwhile, by design, $X^{-1} \cap XX = \emptyset$, so $XXX$ does not contain $1$.

Can anybody spot a better construction?

More is known about a slight variant of your question. Suppose you want to know the minimal density $\alpha$ such that if $X, Y, Z$ each have density at least $\alpha$ then $XYZ = G$. Let $G = A_n$. Gowers's method gives the upper bound $n^{-1/3}$. An example like the one above gives a lower bound $n^{-1/2}$. The truth is $n^{-1/2+o(1)}$. I wrote a paper about this a few years ago, which you can find here: https://arxiv.org/abs/1512.03517.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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