43
$\begingroup$

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...

$\endgroup$
4
  • 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, 2018 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$
    – Chain Markov
    Aug 6, 2018 at 13:52
  • $\begingroup$ Does anyone have the results for small values of $n$? $\endgroup$
    – mathworker21
    Aug 21, 2018 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, 2018 at 1:27

1 Answer 1

Reset to default
2
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

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