# Checking if a finite subset is a subgroup

It happens that, $$G$$ being a group, we want to check if a finite subset $$\{a_{1}, \ldots , a_{n}\}$$ of $$G$$, with $$n \geq 1$$, is a subgroup of $$G$$.

It is a subgroup if and only if for every $$i, j$$ in $$\{1, \ldots , n\}$$, $$a_{i} a_{j}$$ is in $$\{a_{1}, \ldots , a_{n}\}$$. (A nonempty finite submagma of a group is a subgroup.)

If I'm not wrong, it is sufficient to verify that for every $$i, j$$ in $$\{1, \ldots , n\}$$ such that $$i \leq j$$, $$a_{i} a_{j}$$ is in $$\{a_{1}, \ldots , a_{n}\}$$, where we can clearly assume that the $$a_{i}$$'s are pairwise distinct.

(Edit : Thus (if I'm not wrong), instead of verifying that, for every $$i, j$$ such that $$i \leq j$$, the elements $$a_{i} a_{j}$$ AND $$a_{j} a_{i}$$ are in $$\{a_{1}, \ldots , a_{n}\}$$, we need only to show that $$a_{i} a_{j}$$ is in $$\{a_{1}, \ldots , a_{n}\}$$. So, we avoid almost half of the calculations.)

I have a proof (I give it below), but it is perhaps too complicated. Thus, my questions are :

1° is the statement correct ?

2° if the statement is correct, is the proof accurate ?

3° if the proof is accurate, is it the simplest possible ?

4° if the statement is correct, is it useful ?

5° do you know a reference to the literature about this question ?

Definition. Let $$G$$ be a group. We define a semistable sequence of elements of $$G$$ as a nonempty finite sequence $$(a_{1}, \ldots , a_{n})$$ of pairwise distinct elements of $$G$$ such that for every $$i, j$$ in $$\{1, \ldots , n\}$$ such that $$i \leq j$$, $$a_{i} a_{j}$$ is in $$\{a_{1}, \ldots , a_{n}\}$$.

Our problem is to prove that if $$(a_{1}, \ldots , a_{n})$$ is a semistable sequence of elements of $$G$$, then $$\{a_{1}, \ldots , a_{n}\}$$ is a subgroup of $$G$$.

Step 1. Let $$(a_{1}, \ldots , a_{n})$$ be a semistable sequence of elements of a group $$G$$, let $$i$$ be an index in $$\{1, \ldots , n\}$$. Then $$a_{i}$$ is of finite order ($$\leq n$$) and for every $$s$$ in $$\mathbb{Z}$$, $$a_{i}^{s}$$ is in $$\{a_{1}, \ldots , a_{n}\}$$. The function $$a \mapsto a^{-1}$$ is a permutation of $$\{a_{1}, \ldots , a_{n}\}$$.

Proof. Let us prove that for every natural number $$r \geq 1$$, $$a_{i}^{r}$$ is in $$\{a_{1}, \ldots , a_{n}\}$$. It is true if $$r = 1$$. Assume that it is true for a natural number $$r$$. Then $$a_{i}^{r} = a_{j}$$ for some $$j$$. It implies $$a_{i}^{r+1} = a_{i}a_{j}$$ and also $$a_{i}^{r+1} = a_{j}a_{i}$$. The first of these two results gives $$a_{i}^{r+1} \in \{a_{1}, \ldots , a_{n}\}$$ if $$i \leq j$$ and the second result also gives $$a_{i}^{r+1} \in \{a_{1}, \ldots , a_{n}\}$$ if $$j \leq i$$. By induction on $$r$$, we conclude that

(1) for every natural number $$r \geq 1$$, $$a_{i}^{r}$$ is in $$\{a_{1}, \ldots , a_{n}\}$$.

In particular, the $$n+1$$ elements $$a_{i}, a_{i}^{2}, \ldots , a_{i}^{n+1}$$ are all in $$\{a_{1}, \ldots , a_{n}\}$$. Since $$\{a_{1}, \ldots , a_{n}\}$$ has only $$n$$ elements, there are at least two exponents $$r$$ and $$t$$ in $$\{1, \ldots , n+1\}$$ such that $$a_{i}^{t} = a_{i}^{r}$$ and this implies that $$a_{i}$$ is of finite order ($$\leq n$$). Thus, for every $$s$$ in $$\mathbb{Z}$$, $$a_{i}^{s}$$ is of the form $$a_{i}^{r}$$ with some $$r \geq 1$$,thus, in view of (1), $$a_{i}^{s}$$ is in $$\{a_{1}, \ldots , a_{n}\}$$ for every $$s$$ in $$\mathbb{Z}$$. It is true in particular for $$s=-1$$, thus the inverse of each element of $$\{a_{1}, \ldots , a_{n}\}$$ is in $$\{a_{1}, \ldots , a_{n}\}$$, so the function $$a \mapsto a^{-1}$$ is a permutation of $$\{a_{1}, \ldots , a_{n}\}$$.

Step 2. Let $$(a_{1}, \ldots , a_{n})$$ be a semistable sequence of elements of a group $$G$$, let $$i$$ be an index in $$\{1, \ldots , n\}$$. The two following conditions are equivalent :

(i) for every $$j \in \{1, \ldots , n\}$$, $$a_{i} a_{j}$$ is in $$\{a_{1}, \ldots , a_{n}\}$$;

(ii) for every $$j \in \{1, \ldots , n\}$$, $$a_{j} a_{i}$$ is in $$\{a_{1}, \ldots , a_{n}\}$$.

Proof. Let's define (temporarily) a left universal of $$(a_{1}, \ldots , a_{n})$$ as an $$a_{i}$$ such that condition (i) is satisfied, i.e. such that for every $$j \in \{1, \ldots , n\}$$, $$a_{i} a_{j}$$ is in $$\{a_{1}, \ldots , a_{n}\}$$ and let's define a right universal of $$(a_{1}, \ldots , a_{n})$$ as an $$a_{i}$$ such that condition (ii) is staisfied, i.e. such that for every $$j \in \{1, \ldots , n\}$$, $$a_{j} a_{i}$$ is in $$\{a_{1}, \ldots , a_{n}\}$$. Thus, the statement amounts to say that the left universals are exactly the right universals.

Let us prove that if $$a_{i}$$ is a left universal, then $$a_{i}^{-1}$$ is a right universal. Since $$a_{i}$$ is a left universal, we have $$a_{i}a_{j} \in \{a_{1}, \ldots , a_{n}\}$$ for every $$j$$. We saw at step 1 that the function $$a \mapsto a^{-1}$$ is a permutation of $$\{a_{1}, \ldots , a_{n}\}$$, thus $$a_{j}^{-1} a_{i}^{-1} \in \{a_{1}, \ldots , a_{n}\}$$ for every $$j$$. Still because $$a \mapsto a^{-1}$$ is a permutation of $$\{a_{1}, \ldots , a_{n}\}$$, $$a_{j}^{-1}$$ runs over $$\{a_{1}, \ldots , a_{n}\}$$ as does $$a_{j}$$, thus, for every $$j \in \{1, \ldots , n\}$$, $$a_{j} a_{i}^{-1} \in \{a_{1}, \ldots , a_{n}\}$$. Since (step 1) $$a_{i}^{-1}$$ is in $$\{a_{1}, \ldots , a_{n}\}$$, this proves that

(1) if $$a_{i}$$ is a left universal, $$a_{i}^{-1}$$ is a right universal.

Similarly,

(2) if $$a_{i}$$ is a right universal, $$a_{i}^{-1}$$ is a left universal.

Now let us prove that the inverse of a left universal is also a left universal. Let $$a_{i}$$ be a left universal, let $$j$$ an index in $$\{1, \ldots , n\}$$. If $$r$$ is a natural number such that $$a_{i}^{r} a_{j}$$ is in $$\{a_{1}, \ldots , a_{n}\}$$, we have $$a_{i}^{r} a_{j} = a_{k}$$ for some $$k$$, whence $$a_{i}^{r+1} a_{j} = a_{i}a_{k}$$. Since $$a_{i}$$ is a left universal, the right member is in $$\{a_{1}, \ldots , a_{n}\}$$, thus $$a_{i}^{r+1} a_{j}$$ is in $$\{a_{1}, \ldots , a_{n}\}$$. By induction on $$r$$, we conclude that for every natural number $$r \geq 1$$, $$a_{i}^{r}$$ is a left universal. Since (step 1) $$a_{i}$$ is of finite order, $$a_{i}^{-1}$$ is of the form $$a_{i}^{r}$$ with a natural number $$r \geq 1$$, thus $$a_{i}^{-1}$$ is a left universal. We thus proved that

(3) if $$a_{i}$$ is a left universal, $$a_{i}^{-1}$$ is also a left universal.

Similarly,

(4) if $$a_{i}$$ is a right universal, $$a_{i}^{-1}$$ is also a right universal.

Let $$a_{i}$$ be a left universal. In view of (3), $$a_{i}^{-1}$$ is also a left universal. Thus, in view of (1), $$a_{i}$$ is a right universal. Thus every left universal is a right universal. Similarly, every right universal is a left universal. As noted, this proves step 2.

Definition. Let $$(a_{1}, \ldots , a_{n})$$ be a semistable sequence of elements of a group $$G$$. We define a universal of $$(a_{1}, \ldots , a_{n})$$ as an $$a_{i}$$ such that the two equivalent conditions of step 2 are satisfied.

Theorem. Let $$(a_{1}, \ldots , a_{n})$$ be a semistable sequence of elements of a group $$G$$. The set $$\{a_{1}, \ldots , a_{n}\}$$ is a subgroup of $$G$$.

Proof. Since $$(a_{1}, \ldots , a_{n})$$ is a semistable sequence of elements of a group $$G$$, we have $$a_{1} a_{j} \in \{a_{1}, \ldots , a_{n}\}$$ for every $$j$$ in $$\{1, \ldots , n\}$$, thus $$a_{1}$$ satisfies condition (i) of step 2 on $$a_{i}$$, thus

(1) $$a_{1}$$ is a universal of $$(a_{1}, \ldots , a_{n})$$.

If $$n \geq 2$$, we have $$a_{2} a_{j} \in \{a_{1}, \ldots , a_{n}\}$$ for every $$j \geq 2$$, because $$(a_{1}, \ldots , a_{n})$$ is a semistable sequence, and we have also $$a_{2} a_{1} \in \{a_{1}, \ldots , a_{n}\}$$, because of (1). Thus, if $$n \geq 2$$,

(2) $$a_{2}$$ is a universal of $$(a_{1}, \ldots , a_{n})$$.

Similarly, we deduce from (1) and (2) that (if $$n \geq 3$$) $$a_{3}$$ is a universal, and so on. Thus $$a_{1}, \ldots , a_{n}$$ are all universals, thus $$\{a_{1}, \ldots , a_{n}\}$$ is a subgroup of $$G$$.

Edit. The proof of relation (3) in step 2 (if $$a_{i}$$ is a left universal, $$a_{i}^{-1}$$ is also a left universal) can be simplified. Since $$a_{i}$$ is a left universal, we have $$a_{i} A = A$$, where $$A$$ denotes the set $$\{a_{1}, \ldots , a_{n}\}$$. Left multiplication by $$a_{i}^{-1}$$ gives $$A = a_{i}^{-1} A$$. Since, from step 1, $$a_{i}^{-1}$$ is in A, this shows that $$a_{i}^{-1}$$ is a left universal. Similarly, the inverse of a right universal is a right universal.

• I have looked through your proof and I believe it is correct. It is a little long winded, but I don't know whether there is any significantly simpler proof. – Derek Holt Nov 10 '19 at 15:34
• E.g. for (3), if $a_i$ is left universal, so are its powers, including $a_i^{o(a_i)-1}=a_i^{-1}$. – Berci Nov 10 '19 at 16:16
• Thanks to Derek Holt and Berci for the comments. – Panurge Nov 10 '19 at 16:55
• Seems to be true, and the proof seems overly long but I'm struggling to come up with an argument that doesn't involve reinventing your little chain of three lemmas. – Jack M Nov 18 '19 at 13:17