Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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
1  
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
show 1 more comment

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

share|improve this answer
    
I see an (easy) proof; problem partly solved; thanks! –  fgrieu Apr 22 '13 at 15:04
add comment

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

share|improve this answer
2  
Perhaps more interesting: Any coset of any normal subgroup of $\mathcal P$ is pure. –  Andreas Blass Apr 22 '13 at 12:26
add comment

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

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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