Return to Answer

1. It seems to me that this same method should yield a similar lower bound even if you allow repeats in your product (but still bound the length of the product by the size of the set of course).

2. It also seems that one could obtain a similar lower bound for product-$g$-free sets for any $g\in G$. Defining $f_g(G)$ in the obvious way, one could use the method of proof in the lemma to prove something like this:

1. It seems to me that this same method should yield a similar lower bound even if you allow repeats in your product (but still bound the length of the product by the size of the set of course). There will be more exceptions of course, e.g. $C_2^d$.

2. It also seems that one could obtain a similar lower bound for product-$g$-free sets for any $g\in G$. Defining $f_g(G)$ in the obvious way, one could use the method of proof in the lemma to prove something like this:

Let me sketch a strategy for proving the lower bound:

Lemma: Let $S_1,\dots, S_k$ be the composition factors of $G$. Then $$ f_1(G)\geq f_1(S_1)+\cdots +f_1(S_k).$$ Sketch of proof: Take a series: $$G=G_0\rhd G_1 \rhd \cdots \rhd G_k=\{1\}$$ where $G_{i-1}/G_i\cong S_i$. For each $i$ write $\ell_i=f_1(S_i)$ and take $g_{i,1},\dots g_{i, \ell_i}$ to be a set of elements in $G_{i-1}$ such that $g_{i,1}G_i,\dots, g_{i, \ell_i}G_i$ is a product-1-free set of $G_{i-1}/G_i=S_i$. I claim that these elements will be a product-1-free set of $G$. To see this take $\Delta$ any subset of them and form a product in some order -- write this as $f_1\cdots f_r$. Let $i$ be the smallest integer such that $\Delta$ contains an element in $G_{i-1}\setminus G_i$. Now consider the product $(f_1G_i)\cdots (f_rG_i)$. A bunch of these will be equal to the identity (corresponding to elements $f_j\in G_i$). Those that aren't will be distinct and will correspond to a product-1-free set of $G_{i-1}/G_i$. Thus the product will not lie in $G_i$ and so cannot equal $1$. QED

Edit -- 8 Jul 2021 -- using comments of Sean Eberhard.

The lemma reduces the problem to a question about simple groups. The original post showed that if $G$ is cyclic, then $f_1(G)\sim \sqrt{|G|}>\log_2|G|$. Combining this with the lemma gives the result for $G$ solvable. (And the answer by Taras Banakh does this in detail.)

So we must deal with $G$ non-abelian simple. These are dealt with by applying the bound in the original post to large cyclic subgroups.

Suppose $G$ is of Lie type of rank $r$ over $\mathbb{F}_q$. Then one can check that $|G|<q^{8r^2}$. On the other hand there is typically a cyclic subgroup of order at least $q^{r-2}$ (I say "typically" because I haven't checked every case.)

Now $\sqrt{q^{r-2}}>\log_2(q^{8r^2})$ unless $r$ is small. For $r$ small we can use the fact that $G$ has a large solvable subgroup (the Borel) for which the cyclic bound in the original post combined with the lemma gives a much better bound than that which is needed. This will give the bound for the whole group.

Suppose $G=A_n$ with $n\geq 5$. In this case $G$ has an element of order $d$ where $d$ is the product of the first $k$ primes $p_1,\dots, p_k$ where $k$ is chosen to be as large as possible such that $p_1+\cdots+p_k\leq n$. Now $d\sim\exp(\sqrt{n\log n})$ and, again, we use the fact that $\sqrt{\exp(\sqrt{n\log n})}>\log(n!)$ provided $n$ is large enough.

Suppose $G$ is sporadic. This case looks more tricky -- element orders in the sporadics tend to be small compared to the size of the group. My strategy would be to choose a small index maximal subgroup for which one can prove a better lower bound (using the previous cases) and, with any luck, this will be sufficient to give the lower bound for the whole group.

Let me sketch a strategy for proving the lower bound:

Lemma: Let $S_1,\dots, S_k$ be the composition factors of $G$. Then $$ f_1(G)\geq f_1(S_1)+\cdots +f_1(S_k).$$ Sketch of proof: Take a series: $$G=G_0\rhd G_1 \rhd \cdots \rhd G_k=\{1\}$$ where $G_{i-1}/G_i\cong S_i$. For each $i$ write $\ell_i=f_1(S_i)$ and take $g_{i,1},\dots g_{i, \ell_i}$ to be a set of elements in $G_{i-1}$ such that $g_{i,1}G_i,\dots, g_{i, \ell_i}G_i$ is a product-1-free set of $G_{i-1}/G_i=S_i$. I claim that these elements will be a product-1-free set of $G$. To see this take $\Delta$ any subset of them and form a product in some order -- write this as $f_1\cdots f_r$. Let $i$ be the smallest integer such that $\Delta$ contains an element in $G_{i-1}\setminus G_i$. Now consider the product $(f_1G_i)\cdots (f_rG_i)$. A bunch of these will be equal to the identity (corresponding to elements $f_j\in G_i$). Those that aren't will be distinct and will correspond to a product-1-free set of $G_{i-1}/G_i$. Thus the product will not lie in $G_i$ and so cannot equal $1$. QED

Edit -- 8 Jul 2021 -- using comments of Sean Eberhard.

The lemma reduces the problem to a question about simple groups. The original post showed that if $G$ is cyclic, then $f_1(G)\sim \sqrt{|G|}>\log_2|G|$. Combining this with the lemma gives the result for $G$ solvable. (And the answer by Taras Banakh does this in detail.)

So we must deal with $G$ non-abelian simple. These are dealt with by applying the bound in the original post to large cyclic subgroups.

Suppose $G$ is of Lie type of rank $r$ over $\mathbb{F}_q$. Then one can check that $|G|<q^{8r^2}$. On the other hand there is typically a cyclic subgroup of order at least $q^{r-2}$ (I say "typically" because I haven't checked every case.)

Now $\sqrt{q^{r-2}}>\log_2(q^{8r^2})$ unless $r$ is small. For $r$ small we can use the fact that $G$ has a large solvable subgroup (the Borel) for which the cyclic bound in the original post combined with the lemma gives a much better bound than that which is needed. This will give the bound for the whole group.

Suppose $G=A_n$ with $n\geq 5$. In this case $G$ has an element of order $d$ where $d$ is the product of the first $k$ primes $p_1,\dots, p_k$ where $k$ is chosen to be as large as possible such that $p_1+\cdots+p_k\leq n$. Now $d\sim\exp(\sqrt{n\log n})$ and, again, we use the fact that $\sqrt{\exp(\sqrt{n\log n})}>\log(n!)$ provided $n$ is large enough.

Suppose $G$ is sporadic. This case looks more tricky -- element orders in the sporadics tend to be small compared to the size of the group. My strategy would be to choose a small index maximal subgroup for which one can prove a better lower bound (using the previous cases) and, with any luck, this will be sufficient to give the lower bound for the whole group.

Edit 2 -- 8 July 2021.

1. It seems to me that this same method should yield a similar lower bound even if you allow repeats in your product (but still bound the length of the product by the size of the set of course).

2. It also seems that one could obtain a similar lower bound for product-$g$-free sets for any $g\in G$. Defining $f_g(G)$ in the obvious way, one could use the method of proof in the lemma to prove something like this:

Let $g\in G$ and $N\lhd G$. If $g\in N$, then $$f_g(G) \geq f_{1}(G/N) + f_g(N).$$ If $g\in G\setminus N$, then $$f_g(G) \geq f_{gN}(G/N) + |N|.$$

This would again reduce the problem to a question about simple groups. If one could show something like $\sqrt{|G|}$ lower bound for cyclic groups as in the OP, then the same general bound follows.

Let me sketch a strategy for proving the lower bound:

Lemma: Let $S_1,\dots, S_k$ be the composition factors of $G$. Then $$ f_1(G)\geq f_1(S_1)+\cdots +f_1(S_k).$$ Sketch of proof: Take a series: $$G=G_0\unrhd G_1 \unrhd \cdots \unrhd G_k=\{1\}$$ where $G_{i-1}/G_i\cong S_i$. For each $i$ write $\ell_i=f_1(S_i)$ and take $g_{i,1},\dots g_{i, \ell_i}$ to be a set of elements in $G_{i-1}$ such that $g_{i,1}G_i,\dots, g_{i, \ell_i}G_i$ is a product-1-free set of $G_{i-1}/G_i=S_i$. I claim that these elements will be a product-1-free set of $G$. To see this take $\Delta$ any subset of them and form a product in some order -- write this as $f_1\cdots f_r$. Let $i$ be the smallest integer such that $\Delta$ contains an element in $G_{i-1}\setminus G_i$. Now consider the product $(f_1G_i)\cdots (f_rG_i)$. A bunch of these will be equal to the identity (corresponding to elements $f_j\in G_i$). Those that aren't will be distinct and will correspond to a product-1-free set of $G_{i-1}/G_i$. Thus the product will not lie in $G_i$ and so cannot equal $1$. QED

Now in the original post you showed that if $G$ is cyclic, then $f_1(G)\sim \sqrt{|G|}>\log_2|G|$. Combining this with the lemma gives the result for $G$ solvable. In fact you should get a stronger bound than $\log_2|G|$ for a large class of solvable groups... and this will be important for what comes next.

For $G$ non-solvable you need to have a lower bound for $f_1(G)$ for $G$ non-abelian simple. Here I can only speculate about what to do...

Let me ignore the sporadics. If $G$ is simple and of Lie type of bounded rank, then perhaps you can use the fact that $G$ has a large solvable subgroup. For example if $G={\rm PSL}_2(q)$, then $G$ has a solvable subgroup $M$ of order $\sim|G|^{2/3}$. The fact that you have a stronger lower bound for this solvable group should yield the required bound for $G$ -- you need $f_1(M)>\frac32\log_2|M|$ or thereabouts.

When the rank is unbounded one could hope to apply some sort of inductive reasoning: use the fact that there are large parabolic subgroups with composition factors that are abelian or else of Lie type of lower rank.

One might hope to work similarly with alternating groups -- using the fact that $A_n$ has large subgroups that are alternating groups of smaller degree... although here I'm less hopeful that induction will yield a bound of the sort you propose.

Let me sketch a strategy for proving the lower bound:

Lemma: Let $S_1,\dots, S_k$ be the composition factors of $G$. Then $$ f_1(G)\geq f_1(S_1)+\cdots +f_1(S_k).$$ Sketch of proof: Take a series: $$G=G_0\rhd G_1 \rhd \cdots \rhd G_k=\{1\}$$ where $G_{i-1}/G_i\cong S_i$. For each $i$ write $\ell_i=f_1(S_i)$ and take $g_{i,1},\dots g_{i, \ell_i}$ to be a set of elements in $G_{i-1}$ such that $g_{i,1}G_i,\dots, g_{i, \ell_i}G_i$ is a product-1-free set of $G_{i-1}/G_i=S_i$. I claim that these elements will be a product-1-free set of $G$. To see this take $\Delta$ any subset of them and form a product in some order -- write this as $f_1\cdots f_r$. Let $i$ be the smallest integer such that $\Delta$ contains an element in $G_{i-1}\setminus G_i$. Now consider the product $(f_1G_i)\cdots (f_rG_i)$. A bunch of these will be equal to the identity (corresponding to elements $f_j\in G_i$). Those that aren't will be distinct and will correspond to a product-1-free set of $G_{i-1}/G_i$. Thus the product will not lie in $G_i$ and so cannot equal $1$. QED

Edit -- 8 Jul 2021 -- using comments of Sean Eberhard.

The lemma reduces the problem to a question about simple groups. The original post showed that if $G$ is cyclic, then $f_1(G)\sim \sqrt{|G|}>\log_2|G|$. Combining this with the lemma gives the result for $G$ solvable. (And the answer by Taras Banakh does this in detail.)

So we must deal with $G$ non-abelian simple. These are dealt with by applying the bound in the original post to large cyclic subgroups.

Suppose $G$ is of Lie type of rank $r$ over $\mathbb{F}_q$. Then one can check that $|G|<q^{8r^2}$. On the other hand there is typically a cyclic subgroup of order at least $q^{r-2}$ (I say "typically" because I haven't checked every case.)

Now $\sqrt{q^{r-2}}>\log_2(q^{8r^2})$ unless $r$ is small. For $r$ small we can use the fact that $G$ has a large solvable subgroup (the Borel) for which the cyclic bound in the original post combined with the lemma gives a much better bound than that which is needed. This will give the bound for the whole group.

Suppose $G=A_n$ with $n\geq 5$. In this case $G$ has an element of order $d$ where $d$ is the product of the first $k$ primes $p_1,\dots, p_k$ where $k$ is chosen to be as large as possible such that $p_1+\cdots+p_k\leq n$. Now $d\sim\exp(\sqrt{n\log n})$ and, again, we use the fact that $\sqrt{\exp(\sqrt{n\log n})}>\log(n!)$ provided $n$ is large enough.

Suppose $G$ is sporadic. This case looks more tricky -- element orders in the sporadics tend to be small compared to the size of the group. My strategy would be to choose a small index maximal subgroup for which one can prove a better lower bound (using the previous cases) and, with any luck, this will be sufficient to give the lower bound for the whole group.