Large product-1-free sets in finite groups

Question

$\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). In particular, the number $O(G)=f_1(G)+1$ is known as Olson's 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 (1975), $f_1(G)<3\sqrt{|G|}$ for any finite group $G$.

2. By a result of Hamindoune and Zemor (1996), $f_1(C_p)<\sqrt{2p}+5\ln(p)$ for any prime number $p$.

3. By a result of Hamindoune and Zemor (1996), $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 (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 (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, 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 (2010) who improved an earlier result of Gao, Ruzsa and Thangadurai (2004).

Answer 1

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.

Answer 2

Realizing the idea of @NickGill we shall confirm the lower bound for solvable groups with five exceptions of the groups $G$ isomorphic to the groups $C_3,C_5,C_3\times C_3, D_{10}$ and $(C_3\times C_3):C_2={\tt SmallGroup}(18,4)$, which have $f_1(G)$ equal to 1, 2, 3, 3, and 4, respectively.

Theorem 1. If a finite solvable group $G$ is not isomorphic to $C_3,C_5,C_3\times C_3,D_{10}$, or $(C_3\times C_3):C_2$, then $f_1(G)\ge\log_2(|G|)$.

The proof is divided into a series of lemmas and claims.

Lemma 1. Let $H$ be a normal subgroup of a finite group $G$ such that the quotient group is cyclic. Then $f_1(G)\ge f_1(H)+a\cdot |H|+ b$ where $a$ is the largest number such that $\frac12a(a+1)|H|<|G/H|$ and $b$ is the largest number such that $\frac12a(a+1)|H|+(a+1)b<|G/H|$.

Proof. Let $g\in G$ be such that $gH$ is a generator of the cyclic group $G/H$. Let $F\subseteq H$ be a product-1-free set of cardinality $|F|=f_1(H)$. Choose any subset $B\subseteq g^{a+1}H$ of cardinality $|B|=b$ and observe that the set $$E=F\cup B\cup\bigcup_{k=1}^a g^kH$$is product-1-free in $G$ and hence $$f_1(G)\ge |E|=f_1(H)+b+a\cdot|H|.$$

The following inequality was proved by @NickGill in his answer.

Lemma 2. For any normal subgroup $H$ of a finite group $G$ we have $$f_1(G)\ge f_1(H)+f_1(G/H).$$

Lemma 3. For any cyclic group $C_n$ of order $n>10$ we have $f_1(C_n)>\log_2(n)$.

Proof. Let $k=f_1(C_n)$. As we already know, $n\le \frac12(k+1)(k+2)$. Assuming that $k=f_1(C_n)\le \log_2(n)$, we conclude that $2^k\le n\le \frac12(k+1)(k+2)$, which implies $k\le 3$ and $n\le \frac12(3+1)(3+2)=10$.

Lemma 4. For any cyclic group $C_n$ of order $n\notin\{3,5\}$ we have $f_1(C_n)\ge\log_2(n)$.

Proof. Lemma 4 follows from Lemma 3 and known values of $f_1(C_n)$ for $n\le 10$.

Lemma 5. Let $H$ be a non-trivial normal subgroup of a finite group $G$ such that $G/H$ is cyclic. If $f_1(H)\ge \log_2(|H|)$, then $f_1(G)\ge\log_2(|G|)$.

Proof. If $|G/H|\notin\{3,4\}$, then by Lemmas 2 and 4, $$f_1(G)\ge f_1(H)+f_1(G/H)\ge \log_2(|H|)+\log_2(|G/H|)=\log_2(|G|).$$

Now assume that $|G/H|=3$. Choose the largest number $a$ such that $\frac12a(a+1)|H|<|G/H|=3$ and the largest number $b$ such that $\frac12a(a+1)|H|+(a+1)b<|G/H|=3$. If $a\ge 1$, then $a\cdot|H|+b\ge |H|\ge 2$. If $a=0$, then $b=2$ and $a\cdot |H|+b=2$. In both cases we obtain $a\cdot |H|+b\ge 2$. By Lemma 1, $$f_1(G)\ge f_1(H)+a|H|+b\ge f_1(H)+2\ge \log_2(|H|)+\log_2(3)=\log_2(|G|).$$

Finally, assume that $|G/H|=5$. Choose the largest number $a$ such that $\frac12a(a+1)|H|<|G/H|=5$ and the largest number $b$ such that $\frac12a(a+1)|H|+(a+1)b<|G/H|=5$. If $|H|\ge 5$, then $a=0$, $b=4$, and $a\cdot|H|+b=4$. If $|H|=4$, then $a=1$, $b=0$ and $a\cdot|H|+b=4$. If $|H|=3$, then $a=1$, $b=0$ and $a\cdot|H|+b=3$. If $|H|=2$, then $a=1$, $b=1$ and $a\cdot|H|+b=3$. In all cases we have the inequality $a\cdot|H|+b\ge 3$. By Lemma 1, $$f_1(G)\ge f_1(H)+a\cdot|H|+b\ge f_1(H)+3\ge \log_2(|H|)+\log_2(5)=\log_2(|G|).$$

Now we can present

Proof of Theorem 1. Assume that $G$ is a finite solvable group, not isomorphic to $C_3,C_5,C_3\times C_3,D_{10}$ or $(C_3\times C_3):C_2$. If $G$ is trivial, then $f_1(G)=0=\log_2(|G|)$ and we are done. So, we assume that $G$ is not trivial. Being finite and solvable, the group $G$ admits a series of normal subgroups $G_0\subset G_1\subset \dots \subset G_n=G$ such that the group $G_0$ is trivial and for every $k\in\{1,\dots,n\}$ the quotient group $G_k/G_{k-1}$ is cyclic of prime cardinality. If $|G_1|\notin\{3,5\}$, then $f_1(G_1)\ge\log_2(|G_1|)$ by Lemma 4. Applying Lemma 5, we can inductively prove that $f_1(G_k)\ge\log_2(|G_k|)$ for every $k\in\{1,\dots,n\}$.

It remains to consider the case $|G_1|\in\{3,5\}$. Taking into account that $G=G_n$ is not isomorphic to $C_3$ or $C_5$, we conclude that $n>1$. Choose the largest number $a$ such that $\frac12a(a+1)|G_1|<|G_2/G_1|$ and the largest number $b$ such that $\frac12a(a+1)|G_1|+(a+1)b<|G_2/G_1|$. Lemma 1 implies that $f_1(G_2)\ge f_1(G_1)+a|G_1|+b$.

Claim 1. If $G_2$ is not isomorphic to $C_3\times C_3$ or $D_{10}$, then $f_1(G_2)\ge\log_2(|G_2|)$ and $f_1(G)\ge\log_2(|G|)$.

Proof. Assume that the group $G_2$ is not isomorphic to $C_3\times C_3$ or $D_{10}$ but $f_1(G_2)<\log_2(|G_2|)$. Then $f_1(G_1)+a|G_1|+b\le f_1(G_2)<\log_2(|G_2|)$.

The maximality of $a$ implies that $\frac12(a+1)(a+2)|G_1|\ge |G_2/G_1|$ and hence $\frac12(a+1)(a+2)|G_1|^2\ge |G_2|$.

If $|G_1|=3$, then the latter inequality implies $\frac92(a+1)(a+2)\ge |G_2|$. On the other hand, we have the inequality $1+3a\le f_1(G_1)+a|G_1|+b<\log_2(|G_2|)$ which implies $2^{1+3a}<|G_2|\le \frac92(a+1)(a+2)$ and $a\le 1$. Then $|G_2/G_1|\le \frac32(a+1)(a+2)\le 9$. Taking into account that $|G_2/G_1|$ is prime, we conclude that $|G_2/G_1|\in\{2,3,5,7\}$.

If $|G_2/G_1|=7$, then $a=1$, $b=1$ and $$f_1(G_2)\ge f_1(G_1)+a|G_1|+b=1+3+1=5>\log_2(21)=\log_2(|G_2|),$$ which contradicts our assumption.

If $|G_2/G_1|=5$, then $a=1$, $b=0$ and $$f_1(G_2)\ge f_1(G_1)+a|G_1|+b=1+3+0=4>\log_2(15)=\log_2(|G_2|),$$ which contradicts our assumption.

If $|G_2/G_1|=3$, then the group $G_2$ is has cardinality 9. Since $G_2$ is not isomorphic to $C_3\times C_3$, it is cyclic of order 9. Lemma 4, $f_1(G_2)>\log_2(|G_2|)$, which contradicts our assumption.

If $|G_2/G_1|=2$, then the group $G_2$ is isomorphic to $C_6$ or $S_3$ and hence has $f_1(G_2)=3>\log_2(|G|)$ by the GAP-calculations. But the equality $f_1(G_2)>\log_2(|G|)$ contradicts our assumption.

In all cases we obtain contradictions, showing that $|G_1|\ne 3$.

Then $|G_1|=5$. In this case the inequality $\frac12(a+1)(a+2)|G_1|^2\ge |G_2|$ implies $\frac{25}2(a+1)(a+2)\ge |G_2|$. On the other hand, we have the inequality $2+5a\le f_1(G_1)+a|G_1|+b<\log_2(|G_2|)$ which implies $2^{2+5a}<|G_2|\le \frac{25}2(a+1)(a+2)$ and $a\le 1$. Then $|G_2/G_1|\le \frac52(a+1)(a+2)\le 15$. Taking into account that $|G_2/G_1|$ is prime, we conclude that $|G_2/G_1|\in\{2,3,5,7,11,13\}$.

If $|G_2/G_1|=13$, then $a=1$, $b=3$ and $$f_1(G_2)\ge f_1(G_1)+a|G_1|+b=2+5+3=10>\log_2(65)=\log_2(|G_2|),$$ which contradicts our assumption.

If $|G_2/G_1|=11$, then $a=1$, $b=2$ and $$f_1(G_2)\ge f_1(G_1)+a|G_1|+b=2+5+2=9>\log_2(55)=\log_2(|G_2|),$$ which contradicts our assumption.

If $|G_2/G_1|=7$, then $a=1$, $b=0$ and $$f_1(G_2)\ge f_1(G_1)+a|G_1|+b=2+5+0=7>\log_2(35)=\log_2(|G_2|),$$ which contradicts our assumption.

If $|G_2/G_1|=5$, then $a=0$, $b=4$ and $$f_1(G_2)\ge f_1(G_1)+a|G_1|+b=2+0+4=6>\log_2(25)=\log_2(|G_2|),$$ which contradicts our assumption.

If $|G_2/G_1|=3$, then $a=0$, $b=2$ and $$f_1(G_2)\ge f_1(G_1)+a|G_1|+b=2+0+2=4>\log_2(15)=\log_2(|G_2|),$$ which contradicts our assumption.

So, $|G_2/G_1|=2$. Since the group $G_2$ is not isomorphic to the dihedral group $D_{10}$, $G_2$ is cyclic of order 10 and hence $f_1(G_2)>\log_2(|G_2|)$ by Lemma 4.

In all cases we obtained contradictions, showing that the assumption $f_1(G_2)<\log_2(|G_2|)$ was false. Therefore, $f_1(G_2)\ge\log_2(|G_2|)$. Now applying Corollary 2, we can inductively prove that $f_1(G_k)\ge\log_2(|G_k|)$ for all $k\in\{2,\dots,n\}$. This completes the proof of Claim 1.

It remains to consider the cases when the group $G_2$ is isomorphic to $C_3\times C_3$ or $D_{10}$. Since the group $G=G_n$ is not isomorphic to these two groups, we conclude that $n>2$. GAP-calculations show that $f_1(C_3\times C_3)=3=f_1(D_{10})$.

Let $a$ be the largest number such that $\frac12a(a+1)|G_2|<|G_3/G_2|$ and $b$ be the largest number such that $\frac12a(a+1)|G_2|+(a+1)b<|G_3/G_2|$. Then $$\tfrac12a(a+1)|G_2|^2<|G_3|\le \tfrac12(a+1)(a+2)|G_2|^2.$$

Claim 2. If $G_2$ is isomorphic to $D_{10}$, then $f_1(G_3)>\log_2(|G_3|)$ and $f_1(G)>\log_2(G)$.

Proof. To derive a contradiction, assume that $f_1(G_3)\le \log_2(|G_3|)$. By Theorem 1, $$3+10a\le f_1(G_2)+a|G_2|+b\le f_1(G_3)\le \log_2(|G_3|)$$ and hence $2^{3+10a}\le |G_3|$. The maximality of $a$ guarantees that $\frac{100}2(a+1)(a+2)=\frac12(a+1)(a+2)|G_2|^2\ge|G_3|$. Then $2^{3+10a}\le \frac{100}2(a+1)(a+2)$ and hence $a=0$ and $b=|G_3/G_2|-1$. Then $|G_3/G_2|\le \frac12(a+1)(a+2)|G_2|=|G_2|=10$. Taking into account that $|G_3/G_2|$ is prime, we conclude that $|G_2/G_2|\in\{2,3,5,7\}$.

If $|G_3/G_2|\in\{3,5,7\}$, then $$f_1(G_3)\ge f_1(G_2)+a|G_2|+b=3+0+|G_3/G_2|-1>\log_2(|G_3/G_2|\cdot 9)=\log_2(|G_3|),$$which contradicts our assumption. So, $|G_3/G_2|=2$. In this case $|G_3|=20$ and $f_1(G_3)\ge 5>\log_2(|G_3|)$ by the GAP-calculations. Applying Lemma 5, we can inductively prove that $f_1(G_k)>\log_2(G_k)$ for all $k\in\{3,\dots,n\}$.

Claim 3. If $G_2$ is isomorphic to $C_3\times C_3$ but $G_3$ is not isomorphic to $(C_3\times C_3):C_2$, then $f_1(G_3)>\log_2(|G_3|)$ and $f_1(G)>\log_2(G)$.

Proof. To derive a contradiction, assume that $f_1(G_3)\le \log_2(|G_3|)$. By Theorem 1, $$3+9a\le f_1(G_2)+a|G_2|+b\le f_1(G_3)\le \log_2(|G_3|)$$ and hence $2^{3+9a}\le |G_3|$. The maximality of $a$ guarantees that $\frac{81}2(a+1)(a+2)=\frac12(a+1)(a+2)|G_2|^2\ge|G_3|$. Then $2^{3+9a}\le \frac{81}2(a+1)(a+2)$ and hence $a=0$ and $b=|G_3/G_2|-1$. Then $|G_3/G_2|\le \frac12(a+1)(a+2)|G_2|=|G_2|=9$. Taking into account that $|G_3/G_2|$ is prime, we conclude that $|G_2/G_2|\in\{2,3,5,7\}$.

If $|G_3/G_2|\in\{3,5,7\}$, then $$f_1(G_3)\ge f_1(G_2)+a|G_2|+b=3+0+|G_3/G_2|-1>\log_2(|G_3/G_2|\cdot 9)=\log_2(|G_3|),$$which contradicts our assumption. So, $|G_3/G_2|=2$. In this case $|G_3|=18$ and GAP-calclulations show that $f_1(G_3)\ge 5>\log_2(18)=\log_2(|G_3)|$ (as $G_3$ is not isomorphic to $(C_3\times C_3):C_2$. This contradiction shows that $f_1(G_3)>\log_2(|G_3|)$. Applying Lemma 5, we can inductively prove that $f_1(G_k)>\log_2(|G_k|)$ for all $k\in\{3,\dots,n\}$.

Claim 4. If $G_3$ is isomorphic to $(C_3\times C_3):C_2$, then $f_1(G_4)>\log_2(|G_4|)$ and $f_1(G)>\log_2(|G|)$.

Proof. Since $G_3$ is isomorphic to $(C_3\times C_3):C_2$ and $G$ is not isomorphic to this group, $n>3$. To derive a contradiction, assume that $f_1(G_4)\le \log_2(|G_4|)$. GAP-calculations show that $f_1(G_3)=f_1(C_3\times C_3):C_2)=4$. Let $a$ be the largest number such that $\frac12a(a+1)|G_3|<|G_4/G_3|$ and $b$ be the largest number such that $\frac12a(a+1)|G_3|+(a+1)b<|G_4/G_3|$.

By Lemma 1, $$f_1(G_4)\ge f_1(G_3)+a|G_3|+b=4+18a+b$$and hence $$2^{4+18a+b}\le 2^{f_1(G_4)}\le |G_4|.$$ The maximality of $a$ guarantees that $$\frac12(a+1)(a+2)|G_3|^2\ge |G_4|\ge 2^{4+18a}$$and hence $a=0$ and $b=|G_4/G_3|-1$. Then $$2^{4+b}=2^{4+18a+b}\le |G_4|=|G_3|\cdot (|G_4/G_3|)=18(b+1)$$ and hence $b=1$. Then $|G_4/G_3|=b+1=2$ and $|G_4|=36$. GAP-calculations show that $f_1(G_4)\ge 6>\log_2(36)=\log_2(|G_4|)$. But this contradicts our assumption.

Therefore, $f_1(G_4)>\log_2(|G_4|)$. Applying Lemma 5, we can inductively prove that $f_1(G_k)>\log_2(|G_k|)$ for all $k\in\{4,\dots,n\}$.

Answer 3

For finite solvable groups $G$ we have the following lower bound for the number $f_1(G)$.

Theorem. Let $G$ be a finite solvable group of cardinality $|G|=\prod_{k=1}p_k$ for some prime numbers $p_1,\dots,p_n$. Then $$f_1(G)\ge \min_k\big(f_1(C_{p_k})-p_k+1\big)+\sum_{k=1}^n(p_k-1).$$

The proof of this theorem relies on two lemmas.

Lemma 1. Let $H$ be a normal subgroup of a finite group $G$ such that the quotient group $G/H$ is cyclic. If $|G/H|\le |H|+1$, then $$f_1(G)\ge f_1(H)+|G/H|-1.$$

Proof. Let $A\subseteq H$ be a product-1-free of cardinality $|A|=f_1(H)$. Let $gH$ be a generator of the cyclic group $G/H$. Since $|H|\ge |G/H|-1$, there exists a subset $B\subseteq gH$ of cardinality $|B|=|G/H|-1$. It is easy to see that $A\cup B$ is product-1-free in $G$ and hence $$f_1(G)\ge |A\cup B|=f_1(H)+|G/H|-1.$$

The following lemma can be proved by induction on the length of subnormal series (with application of the third Sylow Theorem).

Lemma 2. Every finite solvable group $G$ contains a subnormal series $G_0\subset G_1\subset\cdots \subset G_n$ such that

$\bullet$ $|G_0|=1$, $|G_n|=G$;

$\bullet$ for every $k\le n$ the quotient group $G_k/G_{k-1}$ is cyclic of prime order;

$\bullet$ for every $k\le n$ we have $|G_k|\le |G_{k-1}|^2$.

Theorem implies the following lower bound for $p$-groups.

Corollary. For any prime number $p$, any $p$-group $G$ of cardinality $|G|=p^n$ has $$f_1(G)\ge f_1(C_p)+(n-1)(p-1)=f_1(C_p)+(p-1)(\log_p(|G|)-1).$$

---

Below I attach a table with GAP-calculations of the function $f_1(G)$. This table shows that no counterexample to the Problem can be found among groups of order $\le 50$.

This table also shows a bit unexpected fact: the sequence $(f_1(C_n))_{n=2}^\infty$ is not monotone because $f_1(C_{42})=9>8=f_1(C_{43})$.

$$\begin{array}{c|c|c} G={\tt SmallGroup}(n,k)&\text{Structure of $G$} &f_1(G)\\ \hline (2,1)&C2&1\\ \hline (3,1)&C3& 1\\ \hline (4,1)&C4&2\\ (4,2)&C2\times C2&2\\ \hline (5,1)&C5&2\\ \hline (6,1)&S3&3\\ (6,2)&C6&3\\ \hline (7,1)&C7&3\\ \hline (8,1)&C8&3\\ (8,2)&C4\times C2&3\\ (8,3)&D8&3\\ (8,4)&Q8&3\\ (8,5)&C2 \times C2 \times C2& 3\\ \hline (9,1)&C9&4\\ (9,2)&C3\times C3&3\\ \hline (10,1)&D10&3\\ (10,2)&C10&4\\ \hline (11,1)&C11&4\\ \hline (12,1)&C3 : C4&4\\ (12,2)&C12&4\\ (12,3)&A4&4\\ (12,4)&D12&4\\ (12,5)&C6\times C2& 4\\ \hline (13,1)&C13&4\\ \hline (14,1)&D14&4\\ (14,2)&C14&5\\ \hline (15,1)&C15&5\\ \hline (16,1)&C16&5\\ (16,2)&C4\times C4& 5\\ (16,3)&(C4 \times C2) : C2& 5\\ (16,4)&C4 : C4& 5\\ (16,5)&C8\times C2& 5\\ (16,6)&C8 : C2& 5\\ (16,7)&D16& 4\\ (16,8)&QD16& 4\\ (16,9)&Q16&4\\ (16,10)& C4\times C2 \times C2& 5\\ (16,11)& C2 \times D8 & 4\\ (16,12)& C2 \times Q8 & 4\\ (16,13)&(C4 \times C2) : C2& 4\\ (16,14)& C2{\times}C2{\times}C2{\times}C2& 4\\ \hline (17,1)& C17& 5\\ \hline (18,1)& D18& 5\\ (18,2)& C18& 5\\ (18,3)& C3 \times S3& 5\\ (18,4)& (C3 \times C3) : C2& 4\\ (18,5)& C6 \times C3 & 5\\ \hline (19,1)& C19 & 5\\ \hline (20,1)& C5 : C4& 5\\ (20,2)& C20 & 6\\ (20,3)& C5 : C4 &5\\ (20,4)& D20& 5\\ (20,5)& C10 \times C2& 6\\ \hline (21,1)& C7 : C3& 5\\ (21,2)& C21& 6\\ \hline (22,1)& D22& 5\\ (22,2)& C22& 6\\ \hline (23,1)& C23& 6\\ \hline (24,1)& C3 : C8& 6\\ (24,2)& C24& 6\\ (24,3)& SL(2,3)& 5\\ (24,4)& C3 : Q8& 5\\ (24,5)& C4 \times S3 &6\\ (24,6)& D24& 5\\ (24,7) &C2 \times (C3 : C4)& 6\\ (24,8)& (C6 \times C2) : C2 & 5\\ (24,9) & C12 \times C2 & 6\\ (24,10) & C3 \times D8 & 6\\ (24,11) & C3 \times Q8 & 6\\ (24,12) & S4 & 5\\ (24,13) & C2 \times A4 & 6\\ (24,14) & C2 \times C2 \times S3 & 5\\ (24,15) & C6 \times C2 \times C2 & 6\\ \hline \end{array} $$

$$\begin{array}{c|c|c} \hline (25,1) & C25 & 7\\ (25,2) & C5 \times C5 & 6\\ \hline (26,1) & D26 & 5\\ (26,2) & C26 & 7\\ \hline (27,1) & C27 & 7\\ (27,2) & C9 \times C3 & 6\\ (27,3) & (C3 \times C3) : C3 & 5\\ (27,4) & C9 : C3 & 6\\ (27,5) & C3 \times C3 \times C3 & 6\\ \hline (28,1) & C7 : C4 & 6\\ (28,2) & C28 & 7\\ (28,3) & D28 & 6\\ (28,4) & C14 \times C2 & 7\\ \hline (29,1) & C29 & 7\\ \hline (30,1) & C5 \times S3 & 7\\ (30,2) & C3 \times D10 & 7\\ (30,3) & D30 & 6 \\ (30,4) & C30 & 7 \\ \hline (31,1) & C31 & 7\\ \hline (32,1) & C32 & 7\\ (32,2) & (C4 \times C2) : C4 & 7\\ (32,3) & C8 \times C4 & 7\\ (32,4) & C8 : C4 & 7\\ (32,5) & (C8 \times C2) : C2 & 7\\ (32,6) & (C2 \times C2 \times C2) : C4 & 6\\ (32,7) & (C8 : C2) : C2 & 6\\ (32,8) & (C2{\times}C2) . (C4{\times}C2) & 6\\ (32,9) & (C8 \times C2) : C2 & 6\\ (32,10) & Q8 : C4 & 6\\ (32,11) & (C4 \times C4) : C2 & 6\\ (32,12) & C4 : C8 & 7\\ (32,13) & C8 : C4 & 6\\ (32,14) & C8 : C4 & 6\\ (32,15) & C4 . D8 & 6\\ (32,16) & C16 \times C2 & 7\\ (32,17) & C16 : C2 & 7\\ (32,18) & D32 & 6\\ (32,19) & QD32 & 6\\ (32,20) & Q32 & 6\\ (32,21) & C4 \times C4 \times C2 & 7\\ (32,22) & C2{\times}((C4 {\times}C2) : C2) & 6\\ (32,23) & C2 \times (C4 : C4) & 6 \\ (32,24) & (C4 \times C4) : C2 & 6 \\ (32,25) & C4 \times D8 & 6\\ (32,26) & C4 \times Q8 & 6\\ (32,27) & (C2{\times}C2{\times}C2{\times}C2) : C2 & 6 \\ (32,28) & (C4{\times}C2{\times}C2) : C2 & 6 \\ (32,29) & (C2 \times Q8) : C2 & 6 \\ (32,30) & (C4 \times C2 \times C2) : C2 & 6 \\ (32,31) & (C4 \times C4) : C2 & 6 \\ (32,32) & (C2 {\times} C2) . (C2 {\times} C2 {\times} C2) & 6 \\ (32,33) & (C4 \times C4) : C2 & 6 \\ (32,34) & (C4 \times C4) : C2 & 6 \\ (32,35) & C4 : Q8 & 6 \\ (32,36) & C8 \times C2 \times C2 & 7 \\ (32,37) & C2 \times (C8 : C2) & 6 \\ (32,38) & (C8 \times C2) : C2 & 6 \\ (32,39) & C2 \times D16 & 6 \\ (32,40) & C2 \times QD16 & 6 \\ (32,41) & C2 \times Q16 & 6 \\ (32,42) & (C8 \times C2) : C2 & 6 \\ (32,43) & C8 : (C2 \times C2) & 6 \\ (32,44) & (C2 \times Q8) : C2 & 6 \\ (32,45) & C4 {\times} C2 {\times} C2 {\times} C2 & 6\\ (32,46) & C2 \times C2 \times D8 & 6 \\ (32,47) & C2 \times C2 \times Q8 & 6 \\ (32,48) & C2 {\times} ((C4 {\times} C2) : C2) & 6\\ (32,49) & (C2 {\times} C2 {\times} C2) : (C2 {\times} C2) & 5 \\ (32,50) & (C2 \times Q8) : C2 & 5\\ (32,51) & C2{\times}C2{\times}C2{\times}C2{\times}C2 & 5\\ \hline \end{array} $$

$$ \begin{array}{c|c|c} \hline (33,1) & C33 & 7\\ \hline (34,1) & D34 & 6\\ (34,2) & C34 & 8\\ \hline (35,1) & C35 & 8\\ \hline (36,1) & C9 : C4 & 7\\ (36,2) & C36 & 8 \\ (36,3) & (C2 \times C2) : C9 & 8 \\ (36,4) & D36 & 6 \\ (36,5) & C18 \times C2 & 8 \\ (36,6) & C3 \times (C3 : C4) & 8 \\ (36,7) & (C3 \times C3) : C4 & 6 \\ (36,8) & C12 \times C3 & 8\\ (36,9) & (C3 \times C3) : C4 & 6 \\ (36,10) & S3 \times S3 & 6 \\ (36,11) & C3 \times A4 & 6 \\ (36,12) & C6 \times S3 & 8 \\ (36,13) & C2 \times ((C3 \times C3) : C2) & 6 \\ (36,14) & C6 \times C6 & 8 \\ \hline (37,1) & C37 & 8 \\ \hline (38,1) & D38 & 6 \\ (38,2) & C38 & 8 \\ \hline (39,1) & C39 & 8 \\ \hline (40,1) & C5 : C8 & 8 \\ (40,2) & C40 & 8 \\ (40,3) & C5 : C8 & 8 \\ (40,4) & C5 : Q8 &7 \\ (40,5) & C4 \times D10 & 7 \\ (40,6) & D40 & 7 \\ (40,7) & C2 \times (C5 : C4) & 7 \\ (40,8) & (C10 \times C2) : C2 & 7 \\ (40,9) & C20 \times C2 & 8 \\ (40,10) & C5 \times D8 & 8 \\ (40,11) & C5 \times Q8 & 8 \\ (40,12) & C2 \times (C5 : C4) & 7 \\ (40,13) & C2 \times C2 \times D10 &7 \\ (40,14) & C10 \times C2 \times C2 & 8 \\ \hline (41,1) & C41 & 8 \\ \hline (42,1) & C7 : C6 & 8 \\ (42,2) & C2 \times (C7 : C3) & 8 \\ (42,3) & C7 \times S3 & 9 \\ (42,4) & C3 \times D14 & 8 \\ (42,5) & D42 & 7 \\ (42,6) & C42 & 9 \\ \hline (43,1) & C43 & 8 \\ \hline (44,1) & C11 : C4 & 7\\ (44,2) & C44 & 9 \\ (44,3) & D44 & 7 \\ (44,4) & C22 \times C2 & 9 \\ \hline (45,1) & C45 & 9 \\ (45,2) & C15 \times C3 & 9 \\ \hline (46,1) & D46 & 7 \\ (46,2) & C46 & 9 \\ \hline (47,1) & C47 & 9 \\ \hline \end{array} $$

$$ \begin{array}{c|c|c} \hline (48,1) & C3 : C16 & 9 \\ (48,2) & C48 & 9 \\ (48,3) & (C4 \times C4) : C3 & 7 \\ (48,4) & C8 \times S3 & 9 \\ (48,5) & C24 : C2 & 7 \\ (48,6) & C24 : C2 & 7 \\ (48,7) & D48 & 7 \\ (48,8) & C3 : Q16 & 7 \\ (48,9) & C2 \times (C3 : C8) & 9 \\ (48,10) & (C3 : C8) : C2 & 7 \\ (48,11) & C4 \times (C3 : C4) & 8 \\ (48,12) & (C3 : C4) : C4 & 7 \\ (48,13) & C12 : C4 & 7 \\ (48,14) & (C12 \times C2) : C2 & 7 \\ (48,15) & (C3 \times D8) : C2 & 7 \\ (48,16) & (C3 : Q8) : C2 & 7 \\ (48,17) & (C3 \times Q8) : C2 & 7 \\ (48,18) & C3 : Q16 & 7 \\ (48,19) & (C6 \times C2) : C4 & 7 \\ (48,20) & C12 \times C4 & 9 \\ (48,21) & C3 \times ((C4 \times C2) : C2) & 9 \\ (48,22) & C3 \times (C4 : C4) & 9 \\ (48,23) & C24 \times C2 & 9\\ (48,24) & C3 \times (C8 : C2) & 9 \\ (48,25) & C3 \times D16 & 8 \\ (48,26) & C3 \times QD16 & 8 \\ (48,27) & C3 \times Q16 & 8 \\ (48,28) & C2 . S4 = SL(2,3) . C2 & 6 \\ (48,29) & GL(2,3) & 6 \\ (48,30) & A4 : C4 & 7 \\ (48,31) & C4 \times A4 & 9 \\ (48,32) & C2 \times SL(2,3) & 8 \\ (48,33) & ((C4 \times C2) : C2) : C3 & 8 \\ (48,34) & C2 \times (C3 : Q8) & 7 \\ (48,35) & C2 \times C4 \times S3 & 7 \\ (48,36) & C2 \times D24 & 7 \\ (48,37) & (C12 \times C2) : C2 & 7 \\ (48,38) & D8 \times S3 & 7 \\ (48,39) & (C4 \times S3) : C2 & 7 \\ (48,40) & Q8 \times S3 & 7 \\ (48,41) & (C4 \times S3) : C2 & 7 \\ (48,42) & C2 \times C2 \times (C3 : C4) & 7 \\ (48,43) & C2 \times ((C6 \times C2) : C2) & 7 \\ (48,44) & C12 \times C2 \times C2 & 9 \\ (48,45) & C6 \times D8 & 8 \\ (48,46) & C6 \times Q8 & 8 \\ (48,47) & C3 \times ((C4 \times C2) : C2) & 8 \\ (48,48) & C2 \times S4 & 7 \\ (48,49) & C2 \times C2 \times A4 & 8 \\ (48,50) & (C2 \times C2 \times C2 \times C2) : C3 & 6 \\ (48,51) & C2 \times C2 \times C2 \times S3 & 7 \\ (48,52) & C6 \times C2 \times C2 \times C2 & 8 \\ \hline (49,1) & C49 & 9 \\ (49,2) & C7 \times C7 & 9 \\ \hline (50,1) & D50 & 8 \\ (50,2) & C50 & 9 \\ (50,3) & C5 \times D10 & 9 \\ (50,4) & (C5 \times C5) : C2 & 7 \\ (50,5) & C10 \times C5 & 9\\ \hline \cdots&\cdots&\cdots\\ (54,8) & ((C3{\times} C3) : C3) : C2 & 6\\ \cdots&\cdots&\cdots\\ (60,5) & A5 & 6\\ \cdots&\cdots&\cdots\\ (81,10) & (C3{\times}C3) . (C3{\times}C3) & 8\\ \cdots&\cdots&\cdots\\ \hline \end{array} $$

Remark. For abelian groups of order $\le 55$ the values of the Olson's constant $O(G)=f_1(G)+1$ have been calculated by Subocz in 2000.