1
$\begingroup$

We could convert or encode a permutation of the 6 subsets of {1,2,3,4} that have exactly 2 elements into a permutation of {1,2,3,4,5,6}, but I would like to keep things in their original form. In other words, what gets permuted is precisely the set { {1,2}, {1,3}, {1,4}, {2,3}, {2,4}, {3,4}}.

It may be helpful to explain the motivation, before I get to the actual question. I'm interested in generalizing from an ordinary binary one-time pad for encryption of data that is not necessarily binary. Let's suppose that we have converted our plain-text into a sequence of symbols, with each symbol in the sequence chosen from an inventory or alphabet of exactly 6 values.

Now, if we write each of the six values of our inventory or alphabet as a four-digit sequence of zeroes and ones, with exactly two 0s and exactly two 1s in each such four-digit sequence, then we have a simple representation of a 2-element subset of {1,2,3,4}.

Given this context, it seems obvious that if each of the 24 permutations of {1,2,3,4} is equally likely to arise, and the sequence of permutations of {1,2,3,4} is truly random, and we apply a one-time pad sequence of permutations of {1,2,3,4} to our input sequence (each item of the input sequence being one of six possible values) ...

... then our output cipher-text should give no clues about the input sequence.

My question: what is special about the 24 permutations?

If we considered all possible permutations of 6 things, then we would be looking at not merely 24 possible permutations, but (24 * 5 * 3 * 2) = (24 * 30) permutations. So a selection has been made.

Often, when we consider permutations of 6 things, we assume for the sake of convenience and simplicity that those six things are simply the numbers from 1 to 6. However, I haven't selected one particular subset of 24 permutations from the set of all permutations of {1, ..., 6}. What I have done is identify a kind of subset of the set of permutations of {1, ..., 6}. In particular, the kind of subset that I have described always consists of exactly 24 permutations.

To get one particular set of 24 permutations, as described, from among the permutations of {1, ..., 6}, we would need to use a particular one-to-one correspondence between {1, ..., 6} and the set of subsets of {1,2,3,4} that have exactly 2 elements.

If there's a simple and clear answer, then I am hoping that it's possible to generalize. For example, maybe 4 becomes 2k and 6 gets replaced with C(2k,k), the number of subsets of a set of 2k elements, each subset having exactly k elements. However, we can initially keep things very simple and specific, with k = 2.

$\endgroup$
1
  • 3
    $\begingroup$ Do you know some basic group theory? Knowing that will help an answerer choose language. In short, an assignment of combinations of $1, 2, 3, 4$ taken $2$ at a time to $1, \ldots, 6$ defines an embedding of groups (an injective group homomorphism) $S_4 \hookrightarrow S_6$, and changing your mind about the assignments, say, by composing the assignment with $g \in S_6$ replaces the image of the homomorphism with the conjugate copy $g S_4 g^{-1}$ of $S_4$ in $S_6$. $\endgroup$ Feb 22, 2023 at 22:41

1 Answer 1

1
$\begingroup$

The $24$ permutations used have the property that if two subsets share an element, the mappings of those two subsets also share an element.

Your assignment between six letters and the six pairs does make a difference. For example, each pair has its complement pair. And if two pairs are not complements, there's a unique third pair such that the union of the three is just three of the four elements.

Imagine we build a regular tetrahedron out of $4$ identical marshmallows (vertices) and $6$ differently colored sticks (edges). If we say the tetrahedron must have one vertex on top, one in front, one in a rear-left position, and one in a rear-right position, that fixes the overall shape. The full $6!$ permutations are like taking the whole thing apart and putting it together any which way. The $4!$ permutations are the ones we can get by rotating and reflecting the whole shape. These symmetry permutations preserve connectedness properties: Two edges either share a vertex or don't, before and after the permutation. Three edges either form a triangle or don't, before and after the permutation.

If we generalize to the effects of the $n!$ permutations of a set of $n$ elements on its $n \choose k$ subsets of size $k$, we have similar facts. (It's not necessary that $n=2k$, but that does give a relatively large number of subsets.) For example, the size of intersections is preserved: given $A \subset C$ and $B \subset C$ and a permutation $\sigma$ of $C$, then

$$ |\sigma(A) \cap \sigma(B)| = |A \cap B| $$

The same can't be said of a general $\sigma$ which just permutes the subsets.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .