$\DeclareMathOperator\SmallGroup{SmallGroup}$**Definition.** A subset $A$ of a group $G$ is called *product-1-free* if for any sequence of pairwise distinct elements $a\_1,\dots,a\_n$ of $A$ the product $a\_1\cdots a\_n$ is not equal to 1 in $G$.


For a finite group $G$, let $f\_1(G)$ be the largest cardinality of a product-1-free set in $G$.


**Example 1.** For every $n\ge 2$ the cyclic group $C\_n$ has $$f\_1(C\_n)\ge \left\lfloor\frac{\sqrt{8n-7}-1}2\right\rfloor.$$
This lower bound follows from the observation that $1+\dots+k<n$ for $k=\left\lfloor\frac{\sqrt{8n-7}-1}2\right\rfloor$.


**Example 2.** Each finite Boolean group $G$ has $f\_1(G)=\log\_2(|G|).$



> 
> **Problem.** Is $\lfloor\log\_2(|G|)\rfloor\le f\_1(|G|)<\sqrt{2|G|}$ for any finite group $G$?
> 
> 
> 


**Remark 1.** By a greedy algorithm mentioned in the comment of @Nick Gill, one can prove the following lower bounds:


$1)$ $f\_1(G)+2^{f\_1(G)}\ge |G|$ for every finite Abelian group $G$;


$2)$ $f\_1(G)+e\cdot f\_1(G)! \ge |G|$ for every finite group.


**Remark 2.** Calculations of $f\_1(G)$ in GAP show that a counterexample to the problem cannot be found among groups of cardinality $\le 50$ (see my partial answer below).


**Added in Edit.** After asking this question, I have found that it has been considered in the literature (see e.g. p.95 in [the book of Erdos and Graham](https://eu1lib.org/dl/447894/7c30e8)). In particular, the number $O(G)=f\_1(G)+1$ is known as [Olson's constant](https://en.wikipedia.org/wiki/Davenport_constant) of a group $G$. Below I write down some known non-trivial upper bounds for the number $f\_1(G)$.


1. By a result of [Olson](http://matwbn.icm.edu.pl/ksiazki/aa/aa28/aa2825.pdf) (1975), $f\_1(G)<3\sqrt{|G|}$ for any finite group $G$.
2. By a result of [Hamindoune and Zemor (1996)](http://matwbn.icm.edu.pl/ksiazki/aa/aa78/aa7823.pdf), $f\_1(C\_p)<\sqrt{2p}+5\ln(p)$ for any prime number $p$.
3. By a result of [Hamindoune and Zemor (1996)](http://matwbn.icm.edu.pl/ksiazki/aa/aa78/aa7823.pdf), $f\_1(G)\le \sqrt{2|G|}+O(|G|^{1/3}\ln(|G|))$ for any finite Abelian group $G$.
4. By a result of [Hoi Nguyen, E. Szemeredi, and Van Vu](https://people.math.osu.edu/nguyen.1261/cikk/zero.pdf) (2009), for every sufficiently large prime number $p$ we have
$f\_1(C\_p)=\big\lfloor\frac{\sqrt{8p-7}-1}2\big\rfloor$.
5. By a result of [Balandraud](https://link.springer.com/article/10.1007/s11856-011-0171-9) (2012), for every prime number $p$ we have $f\_1(C\_p)=\big\lfloor\frac{\sqrt{8p-7}-1}2\big\rfloor$.
6. By the observation of [Hoi Nguyen, E. Szemeredi, and Van Vu](https://people.math.osu.edu/nguyen.1261/cikk/zero.pdf), for every $n\ge 4$ and $m=\frac12n(n+1)-1$ the set $A=\{1,3,\dots,n,m-2\}\subset C\_m$ is product-1-free witnessing that $f\_1(C\_m)\ge n=1+\big\lfloor\frac{\sqrt{8m-7}-1}2\big\rfloor$.
7. It is easy to see that $f\_1(C\_n\oplus C\_n)\ge f\_1(C\_n)+n-1$ for every $n\in \mathbb N$. If $n>6000$ is prime, then $$f\_1(C\_n\oplus C\_n)=f\_1(C\_n)+n-1=n+\left\lfloor\tfrac{\sqrt{8n-7}-3}2\right\rfloor$$ according to the result of [Bhowmik and Schlage-Puchta](https://www.impan.pl/shop/en/publication/transaction/download/product/83035) (2010) who improved an earlier result of
[Gao, Ruzsa and Thangadurai](https://www.sciencedirect.com/science/article/pii/S009731650400038X?via%3Dihub) (2004).



Large product-1-free sets in finite groups
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). 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 $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.


