Is every pure set of permutations a group?

Let $\mathcal{P}$ be the set of permutations over a finite set $\mathcal{S}$, with $|\mathcal{P}|$=$|\mathcal{S}|!$

$(\mathcal{P},\circ)$ is a finite group, where $\circ$ is composition.

A subset $\mathcal{Q}$ of $\mathcal{P}$ is defined as pure when $\forall (a,b,c)\in\mathcal{Q}^3, a\circ b^{-1}\circ c\in \mathcal{Q}$ (update: and $\mathcal{Q}$ is non-empty).

Any (update: non-empty) subset $\mathcal{Q}$ of $\mathcal{P}$ that is closed under $\circ$ is a (finite, sub)group, and is thus pure.

Is every pure set of permutations a group? If not except for trivial $|\mathcal{S}|$, what's a minimal counterexample? (Solved, see update below).

Any idea to determine if the set $\mathcal{Q}$ of permutations resulting from the cryptographic function DES is pure, with application to the security of 3DES, as asked in this question?

Update: a minimal counterexample occurs when $\mathcal{P}$ is the set of the 2 permutations of 2 elements; and $\mathcal{Q}$ is the set consisting of the single non-identity permutation, which is pure, but not a group.

Marc van Leeuwen states in his answer that a pure subset $\mathcal{Q}$ of $\mathcal{P}$ (assumed finite) is a group iff it contains the identity. Proof in the not-quite-trivial direction: if $\mathcal{Q}$ is pure and contains the identity $e$, then

• by setting $a=c=e$, $\mathcal{Q}$ contains the inverse of each of its element $b$;
• by setting $b=e$, $\mathcal{Q}$ is closed under $\circ$;
• thus $\mathcal{Q}$ obeys all the properties of a group.

Even combined with the established fact that DES is not a group, and that it would be possible to test/prove that DES does not contains identity, that does not seem to prove that DES is not pure.

-
What's a "pure" set of permutations? – Marra Apr 22 '13 at 11:46
@Gustavo Marra: see third paragraph of the question. – fgrieu Apr 22 '13 at 11:50
Ok I missed it the first time! – Marra Apr 22 '13 at 11:55
+1 for a correctly written and redacted question, with links and definitions. Alas, this is becoming very rare in this site... – DonAntonio Apr 22 '13 at 12:22
The claim that any subset $\mathcal Q$ of $\mathcal P$ that is closed under $\circ$ is pure fails in two ways (that may be irrelevant to this question though): $\mathcal Q=\emptyset$ fails to contain the identity, and, in case $\mathcal P$ is infinite, for instance $\mathcal P=\Bbb Z$, certain "monotonic" subsets may just be semigroups, for instance the permutations of $\Bbb Z$ that add a constant${}\geq13$. – Marc van Leeuwen Apr 22 '13 at 12:46

3 Answers

Under the assumption that $\mathcal P$ is finite, a pure subset is a subgroup if and only if it contains the identity permutation$~e$ (and you only need instances with $c=e$ in the description of pure subsets to show this).

-
I see an (easy) proof; problem partly solved; thanks! – fgrieu Apr 22 '13 at 15:04

The empty set and all one-element subsets of $\mathcal P$ are pure.

-
Perhaps more interesting: Any coset of any normal subgroup of $\mathcal P$ is pure. – Andreas Blass Apr 22 '13 at 12:26

$$Q:=\{(12)\}\subset S_3\;:(12)(12)^{-1}(12)=(12)\in Q$$

yet $\,Q\,$ is not a subgroup...

-