# Product-one sets in non-commutative groups

A nonempty subset $$D$$ of a group $$G$$ is called

$$\bullet$$ decomposable if $$D\subseteq DD$$, that is every element $$x\in D$$ is can be written as the product $$x=yz$$ of some elements $$y,z\in D$$;

$$\bullet$$ product-one if there exists $$n\in\mathbb N$$ and pairwise distinct elements $$x_1,\dots,x_n\in D$$ such that $$x_1\cdots x_n=1$$.

Problem 1. Let $$D$$ be a finite decomposable subset of a group. Is $$D$$ product-one?

Remark 1. For commutative groups this problem was posed by Gjergji Zaimi and solved affirmatively by Lev, Nagy, and Pach.

Remarks 2. For some non-commutative groups like generalized dihedral groups the answer to Problem is also affirmative, see my partial answer below. This partial answer suggests the following

Problem 2. Let $$G$$ be a group containing an Abelian subgroup of index 2. Is every finite decomposable set in $$G$$ product-one?

• Suppose $G=\text{Sym}(X)$ for some finite $X$ and $d$ is the metric on $G$ defined by $d(f,g)=|\{x\in X\mid f(x)\neq g(x)\}|$, and $L$ is the loss function where $L(D)=\sum_{g\in D}d(g,DD)$. Then $L$ measures how close $D$ is to being decomposable and $L(D)=0$ iff $D$ is decomposable. I have therefore tried to find decomposable subsets of $\text{Sym}(X)$ simply by minimizing $L(D)$ using evolutionary algorithms and artificial intelligence, but all my examples were trivial in the sense that they always had subsets of the form $\{x,x^{-1}\}$ where $x^{2}\neq e$ or $x=e$. Jun 26, 2021 at 21:11
• Few obvious comments, for finite $G$. For a minimal counterexample (or an inductive proof), we can assume that $1 \not\in D$ and that $D$ is not contained in any maximal subgroup of $G$. With minimality we can also assume that no nonempty proper subset of $D$ is decomposable, so for all $x \in D$, the set $D \setminus \{x\}$ is not decomposable. Then for all $x \in D$, we must have $D \subseteq Dx \cup xD \cup \{x\}$.
– spin
Jun 27, 2021 at 9:23
• @spin We can also assume that $D$ contains no elements of order 2. Jun 27, 2021 at 15:24
• @TarasBanakh Can you expand on that last comment? Jun 27, 2021 at 22:43
• Possibly you view it as trivial, but anyway a simple remark is that there exist $0<m\le |D|$ and $x_1,\dots,x_m\in S$ (possibly not distinct) such that $\prod x_i=1$. Indeed, make $D$ an oriented graph with $x\to y$ if $x\in yD$. By assumption for every $x$ there exists $y$ with $x\to y$. So there is an oriented simple loop of size $0<m\le |S|$: $y_0,\dots,y_{m-1}$, with $y_i=y_{i+1}x_i$ for some $x_i\in D$, $i$ modulo $m$. Hence $y_0=y_1x_0=y_2x_1x_0=\dots=y_{m-1}x_{m-2}\dots x_0=y_0x_{m-1}\dots x_0$, so $x_{m-1}\dots x_0=e$.
– YCor
Jul 3, 2021 at 7:27

Also an extended comment.

We can consider a (finite) set $$D$$ with two self-maps $$u,v:D\to D$$, and consider the group $$G_{u,v}$$ of presentation $$G_{u,v}=\langle x:x\in D\mid x=u(x)v(x),\forall x\in D\rangle.$$ The question is equivalent to whether there for every nonempty finite set $$D$$ and $$u,v$$ there exists an injective nonempty product of elements of $$D$$ representing $$e$$ in $$G_{u,v}$$.

From previous comments by OP, this holds if $$G_{u,v}$$ is commutative, or if the image of $$D$$ in $$G_{u,v}$$ has an element of order $$\le 2$$.

An observation:

Proposition 1: if $$(D,u,v)$$ is a counterexample, then $$u$$ is non-injective on every $$v$$-cycle, and vice versa (in particular, $$u,v$$ are non-injective). Also, every cycle of $$u$$ or $$v$$ has length $$\ge 3$$.

Indeed, if $$x=u^nx,ux,\dots,u^{n-1}x$$ is a $$n$$-cycle of $$u$$, then in $$G_{u,v}$$, $$x=u(x)v(x)=u^2x.vux.vx=\dots u^nx.vu^{n-1}x\dots vux.vx$$, so $$vu^{n-1}x\dots vux.vx$$. Since $$(D,u,v)$$ is a counterexample, it follows that the elements $$vu^{n-1}x,\dots ,vux,vx$$ are not pairwise distinct.

If there is a $$1$$-cycle of $$u$$, say $$ux=x$$, then $$x=ux.vx=x.vx$$, so $$vx=1$$. If there is a $$2$$-cycle of $$u$$, say $$u^2x=x$$, the $$x=ux.vx=u^2x.vux.vx$$, so $$vux=vx$$, and in turn $$(vx)^2=e$$. But the case when $$D$$ has an element of order $$\le 2$$ was already excluded.

The other statements hold by symmetry.$$\Box$$

This reproves that $$|D|\le 3$$ is excluded, since there should be a cycle, say of length $$n$$; by non-injectivity $$n<|D|$$, and by the above, $$n\ge 3$$, so $$|D|\ge 4$$. Let's now exclude $$D=4$$.

Proposition 2 If $$(D,u,v)$$ is a counterexample then $$|D|\ge 5$$.

Let me write $$i$$ instead of $$x_i$$. So, there is a 3-cycle of $$u$$, and $$v$$ is non-injective on it. Up to reindex, $$D=\{1,2,3,4\}$$ $$u:1\mapsto 2\mapsto 3\mapsto 1$$ and $$v(1)=v(2)$$.

1. suppose $$v(1)\neq 4$$. Since $$v$$ has no fixed point, we deduce $$v(1)=v(2)=3$$: $$1=23,2=33,3=1*$$. Since $$\{1,2,3\}$$ is not a counterexample, we get $$3=14$$. Hence $$1,2\in\langle 3\rangle$$, and in turn $$4\in \langle 1,2,3\rangle=\langle 3\rangle$$. So $$G_{u,v}$$ is cyclic and this case (commutative) is already discarded.
2. so $$v(1)=4$$: $$1=24,2=34,3=1i$$. Then $$1=24=344=1i44$$, hence $$i44=e$$. If $$i=2$$ or $$i=3$$ this yields $$14=e$$ or $$24=e$$; also $$i=4$$ is impossible since $$v$$ has a 3-cycle. So $$v(3)=1$$: $$1=24$$, $$2=34$$, $$3=11$$. Then $$1=24=344=1144$$, so $$144=e$$, thus $$1\in\langle 4\rangle$$, so $$3=11\in\langle 4\rangle$$, and $$2=34\in\langle 4\rangle$$. Thus $$\langle 1,2,3,4\rangle$$ is cyclic, contradiction.
• @TarasBanakh ($e$ neutral element) If there is a 2-cycle, say $a\mapsto b\mapsto a$, so $a=bc$, $b=ad$, for some $c,d\in D$. Hence $a=bc=adc$, so $dc=1$. If $d\neq c$, $dc=e$ contradicts $D$ being non-product-one. So $d=c$, and hence $c^2=e$, and this is excluded since you checked $D$ has no element of order $2$.
– YCor
Jul 15, 2021 at 15:48

GAP shows that the groups SmallGroup(27,3), SmallGroup(27,4), SmallGroup(36,11), SmallGroup(39,1) SmallGroup(48,3) do contain many 5-element decomposable sets, which are not product-one. So, the lower bound 5 for the smallest cardinality of a counterexample, obtained by @YCor in his answer, is the best possible.

Below I write down 5-element decomposable non-product-one sets found by GAP in the groups

SmallGroup(27,3): [ f1, f2, f1 * f2, f1^2 * f2, f1 * f2^2 ]

SmallGroup(27,4): [ f1, f2, f1 * f2 * f3, f1^2 * f2 * f3, f2^2 * f3^2 ]

SmallGroup(36,11): [ f1, f2 * f3, f1^2 * f3, f1 * f2^2 * f3, f1^2 * f2^2 * f4 ]

SmallGroup(39,1): [ f1, f2, f1 * f2, f1^2 * f2, f2^4 ]

SmallGroup(48,3): [ f1, f2, f1 * f2, f2 * f3, f1^2 * f2 ]

These 5 groups are the only groups of order $$\le 50$$ that contain decomposable non-product-one sets.

• I'd be curious of explicit values of such 5-element subsets in groups of order 27 or 39.
– YCor
Jul 5, 2021 at 7:00
• Thanks! Indeed I got the (27,3) example. Namely, if in an arbitrary group $x,y$ are non-commuting elements of order 3 such that the abelianization of $\langle x,y\rangle$ has order $9$, then $\{x,y,xy,x^2y,xy^2\}$ works. This applies in the non-abelian group of order 27 and exponent 3.
– YCor
Jul 5, 2021 at 7:41

This is not an answer, but too long for a comment. Below I write down some conditions (on a group or a decomposable set) guaranteeing that a decomposable set in a group is product-one.

Proposition 1. Let $$G$$ be a group containing an abelian subgroup $$A$$ of index 2 such that for every $$x\in A$$ and $$y\in G\setminus A$$ we have $$yx=x^{-1}y$$. Every finite decomposable set $$D$$ in $$G$$ is product-one.

Proof. First observe that the intersection $$D\cap A$$ is not empty. Otherwise, $$D\subseteq DD=(D\setminus A)\cdot(D\setminus A)\subseteq (G\setminus A)(G\setminus A)=A$$ would be empty. If $$D\cap A$$ contains a decomposable subset of the abelian group $$A$$, then it is product-one by the result of Lev, Nagy, and Pach. So, we assume that $$D\cap A$$ contains no decomposable subset. In particular, $$D$$ does not contain the identity 1 of the group $$G$$. Since $$D\cap A$$ is not decomposable, there exists an element $$x\in D\cap A$$ such that $$x=yz$$ for some elements $$y,z\in D\setminus A$$. It follows from $$1\notin D$$ that $$y,z$$ differ from $$x$$.

First we assume that $$y\ne z$$. Then $$yxz=x^{-1}yz=x^{-1}x=1$$, witnessing that $$D$$ is product-one.

Now assume that $$y=z$$. In this case $$x=yz=y^2$$. Since $$D$$ is decomposable, $$y=uv$$ for some elements $$u,v\in D$$. Since $$1\notin D$$, the elements $$u,v$$ differ from $$y$$. Assuming that $$u=v$$, we conclude that $$y=uv=u^2\in A$$ as the group $$A$$ has index 2 in $$G$$. But this contradicts the choice of the points $$y=z\notin A$$. So, $$u\ne v$$. If $$x\notin\{u,v\}$$, then $$yxuv=x^{-1}yuv=x^{-1}y^2=x^{-1}x=1$$ and we are done. So, we assume that $$x\in\{u,v\}$$. If $$x=u$$, then $$x=y^2=uvy=xvy$$ implies $$vy=1$$. If $$x=v$$, then $$x=y^2=yuv=yux$$ implies $$yu=1$$. In both cases we have found two elements in $$D$$ whose product is equal 1, witnessing that $$D$$ is product-one.

Corollary. Decomposable sets in the dihedral groups $$D_{2n}$$ and dicyclic groups $$Q_{4n}$$ are product-one.

Proposition 2. If a finite decomposable subset $$D$$ of a group contains an element of order 2, then $$D$$ is product-one.

Proof. If $$D$$ contains the identity of the group, then $$D$$ is product-one. So, we assume that $$1\notin D$$. If $$D$$ contains a sequence of pairwise distinct points $$x_0,\dots,x_n$$ such that $$x_{k-1}=x_k^2$$ for any positive $$k and $$x_n=x_0^2$$, then $$x_0=x_1^2=x_1x_2^2=\dots =x_1x_2\cdots x_{n-1}x_n^2=x_1x_2\cdots x_nx_0^2$$which implies that $$x_1x_2\cdots x_nx_0=1$$ and hence $$D$$ is product-one. So, we assume that $$D$$ does not contain such a sequence. Fix any element $$x\in D$$ of order 2 and let $$n\in\mathbb N$$ be the largest number for which there exists a sequence $$x_0,\dots,x_n$$ in $$D$$ such that $$x_0=x$$ and $$x_{k-1}=x_k^2$$ for all positive $$k\le n$$. Our assumption guarantees that $$n$$ is well-defined and the points $$x_0,\dots,x_n$$ are pairwise distinct. By the decomposability of $$D$$, there exist two element $$y,z\in D$$ such that $$x_n=yz$$. The maximality of $$n$$ guarantees that $$y\ne z$$. If the doubleton $$\{y,z\}$$ is disjoint with the set $$\{x_0,\dots,x_n\}$$, then $$1=x^2=x_0x_1\cdots x_nyz$$and hence $$D$$ is product-one. So we assume that $$\{y,z\}\cap\{x_0,\dots,x_n\}\ne\emptyset$$ and find the largest number $$i$$ such that $$x_i\in\{y,z\}$$. It follows from $$x_n=yz$$ and $$1\notin D$$ that $$i. If $$x_i=z$$, then $$x_i=x_{i+1}^2=x_{i+1}\cdots x_nyz=x_{i+1}\cdots x_nyx_i$$implies that $$x_{i+1}\cdots x_ny=1$$, witnessing that $$D$$ is product-one. If $$x_i=y$$, then $$x_i=x_{i+1}^2=yzx_n\cdots x_{i+1}=x_izx_n\cdots x_{i+1}$$ implies that $$zx_n\cdots x_{i+1}=1$$, which means that $$D$$ is product-one.

Proposition 3. Every decomposable set $$D$$ of cardinality $$|D|\le 3$$ is product-one.

Proof. If $$D=\{a\}$$ is a singleton, then $$a=a^2$$ and $$a=1$$, which means that $$D$$ is product-one. Now assume that $$D=\{a,b\}$$ is a doubleton and $$1\notin D$$. Then $$a=b^2$$ and $$b=a^2=b^4$$, which implies that $$ab=b^3=1$$ and hence $$D$$ is product-one. Finally, assume that $$D=\{a,b,c\}$$ and $$D$$ contains no decomposable subsets of cardinality $$<3$$.

First we assume that some element of $$D$$ is the square of some other element of $$D$$. We lose no generality assuming that $$b=a^2$$. By the decomposability of $$D$$, $$c\in\{a^2,b^2,ab,ba\}=\{a^2,a^4,a^3\}$$ and hence $$\{a,b,c\}$$ is a decomposable subset of the abelian group $$\{a^n:n\in\mathbb Z\}$$. By the result of Lev, Nagy and Pach, the decomposable set $$D$$ is product-one.

If $$D$$ contains an element of order 2, then $$D$$ is product-open by Proposition 2.

It remains to consider the case when no element of $$D$$ is the square of another element of $$D$$ and no element of $$D$$ has order 2. By the decomposability of $$D$$, $$a=bc$$ or $$a=cb$$. We lose no generality assuming that $$a=bc$$ and hence $$c=b^{-1}a$$. By the decomposability of $$D$$, $$b=ac$$ or $$b=ca$$. If $$b=ac$$, then $$b=ac=ab^{-1}a$$ and hence $$c^2=(b^{-1}a)^2=1$$, which is forbidden by our assumption. So, $$b=ca=b^{-1}a^2$$ and hence $$b^2=a^2$$.

By the decomposability of $$D$$, $$c=ab$$ or $$c=ba$$. If $$c=ba$$, then $$ba=c=b^{-1}a$$ and hence $$b^2=1$$, which is forbidden by our assumption. So, $$ab=c=b^{-1}a$$ and hence $$aba^{-1}=b^{-1}$$. Now consider the group $$H$$ generated by the elements $$a,b$$ and the cyclic subgroup $$B$$ generated by the element $$b$$. It follows from $$a^2=b^2\in B$$ and $$aba^{-1}=b^{-1}\ne b$$ that the group $$B$$ has index 2 in $$H$$ and for every elements $$x=b^n\in B$$ and $$y=ab^m\in H\setminus B$$ we have $$yx=ab^mb^n=ab^nb^m=b^{-n}ab^m=x^{-1}y$$. Since $$D=\{a,b,c\}=\{a,b,b^{-1}a\}\subseteq H$$, we can apply Proposition 1 and conclude that the decomposable set $$D$$ is product-one.