7
$\begingroup$

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?

$\endgroup$
8
  • 2
    $\begingroup$ 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$. $\endgroup$ Jun 26, 2021 at 21:11
  • 3
    $\begingroup$ 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\}$. $\endgroup$
    – spin
    Jun 27, 2021 at 9:23
  • $\begingroup$ @spin We can also assume that $D$ contains no elements of order 2. $\endgroup$ Jun 27, 2021 at 15:24
  • $\begingroup$ @TarasBanakh Can you expand on that last comment? $\endgroup$
    – verret
    Jun 27, 2021 at 22:43
  • 1
    $\begingroup$ 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$. $\endgroup$
    – YCor
    Jul 3, 2021 at 7:27

3 Answers 3

5
$\begingroup$

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.
$\endgroup$
1
  • $\begingroup$ @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$. $\endgroup$
    – YCor
    Jul 15, 2021 at 15:48
3
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ I'd be curious of explicit values of such 5-element subsets in groups of order 27 or 39. $\endgroup$
    – YCor
    Jul 5, 2021 at 7:00
  • 2
    $\begingroup$ 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. $\endgroup$
    – YCor
    Jul 5, 2021 at 7:41
0
$\begingroup$

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

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.