Return to 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$.

$\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).

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

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

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

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