Permutation modules and the simple group of order 168

In an earlier post I decomposed the permutation module for acting on the non-zero lines in , with coefficients in a field of characteristic . Some related ideas give the shortest proof I know of the exceptional isomorphism between and . The motivation section below explains why what we do ‘must work’, but is not logically necessary.

Motivation

Let have order and let

The simple modules for in characteristic are the trivial module, the natural module , its dual , and the reduction modulo of a module affording the -dimensional character induced from either of the two non-trivial linear characters of . (A short calculation with Mackey’s Formula and Frobenius Reciprocity shows the module is irreducible in characteristic zero; then since is odd, it reduces modulo to a simple projective. Alternatively one can work over and perform the analogue of the characteristic zero construction directly.) The permutation module for acting on the cosets of , defined over , is projective. Since it has the trivial module in its socle and top, the only possible Loewy structure is

In particular, it contains a -dimensional -submodule having as a top composition factor. Below we construct as a module for and hence obtain the exceptional isomorphism in the form .

Construction

Let regarded as a permutation group acting on the non-zero lines in . For , let denote the line through , and let denote the line through . Let be the corresponding -permutation module.

Let , corresponding to the Möbius map and to the matrix in . The simple modules for correspond to the factors of

Since is permuted by squaring, an idempotent killing the simple modules with minimal polynomial is . Therefore the module we require has codimension in the -dimensional module

(For example, applying to the final basis vector gives which is the sum of the first three basis vectors.) Since must appear, it can only be that is generated by where

and so has basis where for each .

Let and let

chosen so that and . The corresponding Möbius maps are and and one choice of corresponding matrices in is and . Computation shows that in their (right) action on ,

The unique trivial submodule of is spanned by

Quotienting out, we obtain the -dimensional representation of where

Since has cyclic Sylow -subgroups and cyclic Sylow -subgroups, and a unique conjugacy class of elements of order (which contains ), one can see just from the matrices above that the representation is faithful. Comparing orders, we get .

Advertisements

A weighted Chebyshev’s order inequality

Let be non-negative weights and let , be non-negative numbers such that

Then

where the middle step follows from the inequality . In particular, if then we obtain

This is a weighted version of Chebyshev’s order inequality. The weighted Chebychev’s order inequality appears (with a different proof) in an interesting article in MAA Mathematics Magazine, where it is used to deduce Jensen’s inequality.

Permutation bases and an unexpected duality

Let be a finite group acting transitively on a set . An important object in representation theory, much used by Burnside and his successors to study the action of , is the permutation module , defined to be the vector space of all formal linear combinations of the elements of , over a chosen field . Thus has as a canonical basis.

It’s easy to fall into the trap of thinking that the canonical basis of a permutation module is in some sense special, or even unique. The latter is certainly wrong in all but the smallest cases. For example, whenever has characteristic zero, or the characteristic of does not divide , the linear map defined on the canonical basis by

is an isomorphism of -modules. Generally, if has rank in its action on then , and a generic linear combination of these -linearly independent homomorphisms is an automorphism of sending the canonical basis to a basis of permuted by .

The motivation for this post is an example where has a permutation basis not obtained in this way. Take acting on . Let be the set of lines in . (Each line has a unique non-zero point; but we use the line notation to makes clear the distinction between and .) The canonical basis for is therefore

For each plane contained in , let . Clearly , for , so the are permuted by . The duality gives a bijection between the lines and planes. Ordering basis vectors as above, the for non-zero have the coefficients shown in the matrix below.

The determinant of is , so whenever has characteristic or has prime characteristic , the form a permutation basis for . Since acts -transitively on , the endomorphism algebra of is -dimensional, spanned by the identity and the ‘complementing’ map defined above. Therefore this alternative basis is not obtained by an endomorphism of .

Now for the surprising duality. When has characteristic , the three linear relations whose first is

show that . It is clear from the final four rows of that , , , are linearly independent and span a -dimensional submodule of . The sum of these vectors, namely , spans the unique trivial submodule of . Since is odd, it splits off as a direct summand. Observe from rows and of the matrix that

A convenient basis for a complement to the trivial submodule is therefore

We have shown that is a -dimensional -submodule of . In the special case , the representation homomorphism is even an isomorphism. Looking at the definitions of , it might seem almost obvious that is isomorphic to the natural representation of .

This is not the case. There are two -dimensional irreducible -modules, namely the natural module and its dual . These are distinguished by the action of the matrices in of order . Let

be the companion matrix for the irreducible cubic . Computing the action of on we find that

Similar calculations show that and . Reordering basis vectors as , we see that in its action on , is represented by the matrix

This is the companion matrix of the irreducible cubic , which lies in the other conjugacy class of matrices of order to . Therefore .

Since , it follows that where is an indecomposable -dimensional -module with and . As expected, the summand is self-dual, but I think it is a mild surprise that it has and not in its socle.

Hill climbing on substitution ciphers

On Saturday the BSHM held a fascinating meeting The history of cryptography and codes. In the second talk, Solving Historical Ciphers with Modern Means, Klaus Schmeh mentioned an attack on the old-school Turning Grille cipher by the thoroughly new-school method of hill climbing. This got me thinking about whether hill climbing could be an effective attack on the monoalphabetic substitution cipher.

As a running example, we use the ciphertext below; it is the encryption, by a randomly chosen substitution cipher, of the first two sentences in Section 1.1 of Stinson’s highly recommended book Crpytography: Theory and Practice, punctuation and spaces deleted.

kqxwjzruhxzkuygtoxskpixgwsmbfkgvmufqbplkgxzutyxkdgfxgfyxjljuyybmxwxmmxr
kguluypsxuzrtgtkgsghhjzpsukxgixmuzpzlxsjmxsquzzxypzljsqudubkqukuzgffgzx
zkglsumsuzzgkjzrxmlkuzrdqukpltxpzvluprkqplsquzzxysgjyrtxukxyxfqgzxypzxg
msghfjkxmzxkdgmewgmxcuhfy

Frequency analysis shows that the most common letters are xzugk with 30, 23, 23, 21 and 19 occurrences, respectively. We therefore guess that x is the encryption of e, that z and u are the encryptions of t and a (in some order), and so on. Decrypting by the key zpxyjcofvuidsqkrlmnwabgeht implied by the frequency counts gives

ilegutmafetiahowkenirveognspciobsaclprdioetawheiyoceocheuduahhpsegessem
ioadahrneatmwowionoffutrnaieovesatrtdenusenlattehrtdunlayapilaiatoccote
tiodnasnattoiutmesdiatmylairdwertbdarmilrdnlattehnouhmweaieheclotehrteo
snofcuiesteiyosjgosexafche

From here I think it is feasible—but certainly non-trivial—to complete the decryption by hand. A good place to start is the final seven letters exafche, on the assumption that the (common) e and a are correct, and the (rare) x is also correct.

For a hill climb, we need

• a place to start;
• a way to step;
• a scoring function.

The obvious starting point is the key guessed by frequency analysis.
Repeated steps must allow the climb to reach all permutations of the Roman alphabet. A natural generating set for the symmetric group on the alphabet is the transpositions. Thus in each step we interchange two letters of the decryption key. For instance, in the first step in the example below, zpxyj … becomes zyxpk… swapping the decrypts of b and d.

A good scoring function is far less obvious. In my first try, I scored a putative plaintext of length by , where is the length of the longest English word starting in position . For example, exampletext gives scores (7,0,1,0,0,3,0,4,0,0,0), taking words from a small dictionary containing let but not ample. After 25 steps, the score increases from 115 to 187, and the hill climb then aborts, since no step improves the score. Unfortunately the putative plaintext is by this point

dmeyitcanetdaboxkesduweoysfprdojfarmpuhdoetaxbedgoreorbeihiabbpfeyeffec
doahabuseatcxoxdosonnitusadeowefatuthesifesmattebuthismagapdmadatorrote
tdohsafsattoditcefhdatcgmaduhxeutjhaucdmuhsmattebsoibcxeadebermotebuteo
fsonrideftedgoflyofevanrbe

which, while a local maximum of the hill climb, seems barely more ‘Englishy’ than the first guess. Permitting two transpositions to be applied in each single step, the hill climb continued for 40 steps (the final 15 steps each taking a minute or so), and aborted with

thefilkaneltabomcestupeofsrywtojrawhyudtoelambetgoweowbeidiabbyreferrek
toadabusealkmomtosonnilusateoperaluldesireshallebuldishagaythatalowwole
ltodsarsallotilkerdtalkghatudmeuljdaukthudshallebsoibkmeatebewholebuleo
rsonwiterletgorxforevanwbe

of score 219. While closer to the truth, this seems a poor return on so much computational time. Increasing the dictionary size, and trying variant statistics, for example, the sum squared of the subword lengths, gave equally discouraging results.

At this point I searched for prior art, and found Cryptanalysis of the Simple Substitution Cipher, which recommends a score based on quadgram frequencies. For instance the most common quadgram is tion, with probability , followed by nthe and ther. The suggested score is where the sum is over all quadgrams in the putative plaintext. Using transpositions as steps, the hill climb took 31 steps (and about 10 seconds, most of which is spent building a look-up table of quadgram frequencies) to improve the score from to . Half-way through the putative plaintext is

rlegutfametrahowvecrikeogcsyprobsaplyidroetawhernopeopheuduahhysegessef
roadahiceatfwowrocommuticareokesatitdecuseclattehitduclanayrlaratoppote
trodcascattorutfesdratfnlaridweitbdaifrlidclattehcouhfweareheplotehiteo
scompuresternoszgosexamphe

and the final putative plaintext is correct in every character:

thefundamentalobjectiveofcryptographyistoenabletwopeopleusuallyreferred
toasaliceandbobtocommunicateoveraninsecurechannelinsuchawaythatanoppone
ntoscarcannotunderstandwhatisbeingsaidthischannelcouldbeatelephonelineo
rcomputernetworkforexample

For the record, the decryption key is zyxwkpomvutsrqjihdcbagfeln. Similarly impressive results were obtained using trigrams or quintgrams. (Some online code I wrote for the trigram attack is linked below.) Bigrams with transposition steps aborted after 23 steps at the local maximum

rmebuthapetradofjesriveobsnglrownalmgicroetafderyoleoldeucuaddgnebenneh
roacadiseathfofrosopputisareovenatitcesunesmatteditcusmayagrmaratollote
trocsansattoruthencrathymaricfeitwcaihrmicsmattedsoudhfearedelmotediteo
nsoplurenteryonkbonexaplde

but allowing double transpositions the hill climb reaches (after 37 steps and a few minutes)

thebundamentalofjectiveobcryptographyistoenafletwopeopleusuallyreberred
toasaliceandfoftocommunicateoveraninsecurechannelinsuchawaythatanoppone
ntoscarcannotunderstandwhatisfeingsaidthischannelcouldfeatelephonelineo
rcomputernetworkborexample

which is correct up to a single transposition. This transposition is a possible step, but it is rejected by the algorithm since making it worsens the bigram score, from to . Thus for bigrams with double transposition steps, this plaintext is not even a local maximum of the hill climb. (Despite this theoretical obstruction, there is obviously no problem completing the decryption.)

Some final thoughts.

• My first choice of scoring function suffers on the example text by getting stuck at local maxima that have some plausible chunks (for example, consider the extract … operaluldesireshallebuldish, while other parts look completely wrong. The less ‘brittle’ quadgram statistic appears to lead to a smoother, steady improvement.
• The score by summing the logs of the probabilities of digrams is suggested by maximum likelihood estimates. Thus the more successful score has the more solid theoretical basis.
• These experiments suggest that, at least for the substitution cipher, the choice of scoring function is far more important than the choice of steps. My attempt to salvage a poor scoring function by increasing the number of possible steps was somewhat successful, at the cost of vastly increased running time. Given the exponential growth in the search space, it seems clear that a small menu of steps, directed by a good scoring function, and possibly iterated many times, is the ideal to aim for.
• A simplified version of the Haskell code I wrote is online here. Because of limitations of the online environment, it only works with bigrams and a reduced list of 2500 trigrams. Some trials suggest that the reduced trigrams suffice on most ciphertexts longer than a few sentences.

In my Cipher Systems course I had a computer demonstration in most lectures. I used Mathematica at first, in the hope (partially realised), that students would be able to re-use the notebooks for problem sheets, but switched to Haskell for the more computationally expensive attacks later in the course. My worry was that, since I never had time to explained the code beyond the bare mathematical details of the underlying algorithm, this would just deepen the students’ mystification. Feedback suggests, however, that these demonstrations were found surprisingly helpful.

The Gini coefficient

We define the Gini coefficient of a probability measure on with mean by

where and are independently distributed according to . Thus . Dividing by makes a dimensionless quantity. The reason for normalizing by will be seen shortly.

The Gini coefficient is a measure of inequality. For instance, if is the probability that a citizen’s wealth is , then we can sample by picking two random citizens, and taking the (absolute value of) the difference of their wealths. In

• Utopia, where everyone happily owns the same ample amount (right up to the point when they are beheaded for treason), the Gini coefficient is ;
• Dystopia, where the ruler has a modest fortune of units, and the other `citizens’ have nothing at all, and the Gini coefficient is ;
• Subtopia, where each serf has unit, and each land-owner has units (plus two serfs to boss around), . Picking two people at random, the probability that come from different classes is , hence the Gini coefficient is .

A striking interpretation of uses the Lorenz curve. Staying with the wealth interpretation, define to be the proportion of all wealth owned by the poorest of the population. Thus , and, since the poorest third (for example) cannot have more than a third of the wealth, for all . When is large we can approximate by the following functions : in

• Utopia for all ;

• Dystopia if and ;
• Subtopia if and if .

Since the area below the Subtopian Lorenz curve is , the orange area is . This is half the Gini coefficient. Clearly the same result holds in Utopia and Dystopia.

Theorem. is twice the area between the Lorenz curve for and the diagonal.

Proof. Let be the cumulative density function for , so . If you are person , and your wealth is then . Thus if and only if person is in the poorest of the population. Therefore the poorest of the population form the event . Their proportion of the wealth is the expectation of , taken over this event, scaled by . That is

The area, say, under the Lorenz curve is therefore

where we made the substitution to go from line 2 to line 3. Now since , where the event is assumed to be negligible, it follows from linearity of expectation that . (Here denotes the expectation taken over both random variables.) Substituting we obtain

From the identity then another application of linearity of expectation, and finally the definition of we get

Therefore , as claimed.

Some related integrals. My interest in this mainly comes from a way to compute from the formula

where we introduced independent random variables and distributed according to , and then used the standard result which holds for any random variable . Very similarly, since we have and

Both these formula generalize to give formulae for the minimum and maximum of independent identically distributed random variables. For instance, a corollary of these formulae for is that

and for , since ,

.

It’s perhaps surprising that sampling three people rather than two (and then taking max minus min) does not give an essentially different inequality statistic. But simply taking the middle does give something new:

A similar argument shows that

(Alternatively this can be proved from the previous remark.) Since the mean and median are not, in general, the same, it should not be a surprise that in a sample of three people, the middle wealth is not an unbiased estimator of the mean wealth. But still I find it slightly striking that it therefore serves as a measure of inequality.

Another interesting fact is that, generalizing the formulae for the cumulative density functions of the maximum and minimum above, the rank statistics for any number of independent samples have nice c.d.f.s. For example, since if and only if either all three random variables are or exactly two random variables are , we have

and in general, the -th largest of -independent random variables has c.d.f.

A motivated proof of the MacWilliams Identity

Fix and let . Let denote the weight of , defined by . Given a subset of , we define its weight enumerator by

The MacWilliams Identity states that if is a linear subspace of , and is its orthogonal complement with respect to the dot product then

The MacWilliams Identity is important in coding theory. It was first proved by the coding theorist Jessie MacWilliams, yet another alumnus of Bell Labs. To my mind, the best motivation for its proof comes from certain related identities in binomial coefficients and the generating function techniques used to prove them, which, in turn, are best understood in terms of the characters of cyclic groups.

Binomial coefficients

The Binomial Theorem states that . It has a one-line combinatorial proof: expand , by choosing from of the brackets and from the other brackets; there are ways to do this, so is the coefficient of .

Now consider the sum of binomial coefficients with even `denominator’. This can be evaluated using the binomial theorem, using the two sums below to cancel out the unwanted binomial coefficients with odd denominator:

For the sums are and , respectively. Therefore . More generally, this trick shows that

which already has some of the appearance of the MacWilliams Identity.
How about ? Since powers of worked for the two-step identity, it is reasonable to try powers of . This gives

By the Binomial Theorem, the sums are , , and . For example, if where then , so we have . Similar formulae can be obtained for the other cases for modulo .

Character theory

Consider the cyclic group . It has four irreducible complex characters, taking values , , and . The previous displayed equation comes from expressing the indicator function as a linear combination of irreducible characters

As an exercise, the reader might use the characters of to decompose the indicator function of and so prove the related identity for .

MacWilliams’ Identity for the repetition code

Let . In this case the left-hand side of the MacWilliams’ Identity is sum of all over of even weight. By analogy with the binomial sum, we write

The first summand is the generating function enumerating all by their weight. Since there are elements of of weight , it is , which is by the Binomial Theorem. Replacing with we see that the second summand is . Therefore

Since , this agrees with the MacWilliams’ Identity. Note that the second sum could be written as

.

MacWilliams Identity for a larger code

Take and . Then

We can describe as the intersection of the two codimension hyperplanes , with ‘normals’ and . Thus

For each , we define ; these are the irreducible complex characters of . Using them to decompose the indicator function we get

.

It now suffices to find . If then, by symmetry, we may assume that , where there are exactly ones. Now records the parity of the number of ones in the first positions of , so writing as the concatenated vector where and , we have

Therefore

as required. (In this case, since is self-dual, we even have .)

MacWilliams Identity in general

The general proof needs no more ideas than those seen in the previous example. The indicator function decomposition is

and so

as required.

Runups and cycles

Let xs be a stream of values that can be compared for equality. Let ++ denote concatenation of lists. Assuming that xs is of the form runUp ++ cyc ++ cyc ++ ..., what is a good way to find the decomposition (runUp, cyc)?

The problem is more subtle than it might seem. If xs is produced by iterating a function, so the entries are [x, f x, f f x, ...] then there are several cycle finding algorithms that can be used. In general, an algorithmic solution is impossible, because the stream may be of the form cyc ++ rest, where cyc has arbitrary length and agrees with rest for positions. In practice, we might know that any cycle has some bounded length, or be prepared to accept a small chance of misidentification.

In this case, the following Haskell code finds the first decomposition (runUp, guessedCycle) such that the stream is runUp ++ rest and rest, which has length at least t, is of the form guessedCycle ++ guessedCycle ++ rest'.

runupAndCycle t xs = 
         runupAndCycleAux t bs (zip [1..] (tail xs))

runupAndCycleAux t xs [] = error $ show (t, xs)
runupAndCycleAux t xs qxs@((q, x) : _)
    = case lookup (map snd $ take t qxs) (take q tailsPositions) of
        Nothing -> runupAndCycleAux t xs (tail qxs)
        Just p  -> -- the t entries starting in positions q and p agree;
                   -- test if taking guessedCycle to be all entries
                   -- between positions q and p-1 gives a decomposition 
                   -- of the required form
                   let xsFirst  = take (q-p) $ drop p xs
                       xsSecond = take (q-p) $ map snd qxs
                   in  if and (zipWith (==) xsFirst xsSecond) 
                          then (take p xs, xsSecond) 
                          else runupAndCycleAux t xs (tail qxs)
    where tailsPositions 
              = [(take t ys, p) | (ys, p) <- zip (tails xs) [0..]]

For example

• runupAndCycle 4 [1,2,3,1,2,3,4,5,1,2,3,4,5] evaluates to ([1,2,3],[1,2,3,4,5]);
• runupAndCycle 4 [1,2,3,1,2,3,4,6,1,2,3,4,5] raises an exception, because while there is agreement for four positions, this is shown by the if ... then ... else ... test not to correspond to a cycle (and the bistream is then exhausted without finding anything better);
• runUpAndCycle 4 [1,2,3,1,2,3,4,5,1,2,3,4,6] raises an exception for the same reason;
• runUpAndCycle 4 [1,2,3,1,2,3,4,5,1,2,3,4,5,6] evaluates to ([1,2,3],[1,2,3,4,5]), as the first example, wrongly suggesting a 5-cycle. Replacing the first argument 4 with 6 we get an exception instead.

The algorithm may use work to exhaust bits without finding a suitable decomposition. For example with , the stream [0,0,0,1,0,0,0,2,0,0,0,3,0,0,0,4, ...] finds possible cycle starts in every fourth position; by position , these require work to investigate.

I’d like to know if there is a faster or more elegant algorithm—ideally both of course—but some searching only found hits for the deterministic version of the problem.