Category Archives: math

Hill verses Hamming

Posted on by

It’s easy to imagine the 19th century Philadelphia wool dealer Frank J. Primrose as a happy man. I envision him shearing sheep during the day, while in the evening he brings his wife flowers and plays games with his little children until bedtime. However, in 1887 Frank J. Primrose was not a happy man. This is because in June of that year, he had telegraphed his agent in Kansas instructions to buy a certain amount of wool. However, the telegraph operator made a single mistake in transmitting his message and Primrose unintentionally bought far more wool than he could possibly sell. Ordinarily, such a small error has little consequence, because errors can often be detected from the context of the message. However, this was an unusual case and the mistake cost him about a half-million dollars in today’s money. He promptly sued and his case eventually made its way to the Supreme Court. The famous 1894 United States Supreme Court case Primrose v. Western Union Telegraph Company decided that the telegraph company was not liable for the error in transmission of a message.

Thus was born the need for error-correcting codes.


Introduction

Lester Hill is most famously known for the Hill cipher, frequently taught in linear algebra courses today. We describe this cryptosystem in more detail in one of the sections below, but here is the rough idea. In this system, developed and published in the 1920’s, we take a k\times k matrix K, composed of integers between 0 and 25, and encipher plaintext p by p\longmapsto c=Kp, where the arithmetical operations are performed mod 26. Here K is the key, which should be known only to the sender and the intended receiver, and c is the ciphertext transmitted to the receiver.

On the other hand, Richard Hamming is known for the Hamming codes, also frequently taught in a linear algebra course. This will be describes in more detail in one of the sections below, be here is the basic idea. In this scheme, developed in the 1940’s, we take a k\times k matrix G over a finite field F, constructed in a very particular way, and encode a message m by m\longmapsto c=mG, where the arithmetical operations are performed in F. The matrix G is called the generator matrix and c is the codeword transmitted to the receiver.

Here, in a nutshell, is the mystery at the heart of this post.

These schemes of Hill and Hamming, while algebraically very similar, have quite different aims. One is intended for secure communication, the other for reliable communication. However, in an unpublished paper [H5], Hill developed a hybrid encryption/error-detection scheme, what we shall call “Hill codes” (described in more detail below).

Why wasn’t Hill’s result published and therefore Hill, more than Hamming, known as a pioneer of error-correcting codes?

Perhaps Hill himself hinted at the answer. In an overly optimistic statement, Hill wrote (italics mine):

Further problems connected with checking operations in finite fields will be treated in another paper. Machines may be devised to render almost quite automatic the evaluation of checking elements c_1,\dots,c_q according to any proposed reference matrix of the general type described in Section 7, whatever the finite field in which the operations are effected. Such machines would enable us to dispense entirely with tables of any sort, and checks could be determined with great speed. But before checking machines could be seriously planned, the following problem — which is one, incidentally, of considerable interest from the standpoint of pure number theory — would require solution.

– Lester Hill, [H5]

By my interpretation, this suggests Hill wanted to answer the question below before moving on. As simple looking as it is, this problem is still, as far as I know, unsolved at the time of this writing.

Question 1 (Hill’s Problem):
Given k and q, find the largest r such that there exists a k\times r van der Monde matrix with the property that every square submatrix is non-singular.

Indeed, this is closely related to the following related question from MacWilliams-Sloane [MS77], also still unsolved at this time. (Since Cauchy matrices do give a large family of matrices with the desired property, I’m guessing Hill was not aware of them.)

Question 2: Research Problem (11.1d)
Given k and q, find the largest r such that there exists a k\times r matrix having entries in GF(q) with the property that every square submatrix is non-singular.

In this post, after brief biographies, an even more brief description of the Hill cipher and Hamming codes is given, with examples. Finally, we reference previous blog posts where the above-mentioned unpublished paper, in which Hill discovered error-correcting codes, is discussed in more detail.


Short biographies

Who is Hill? Recent short biographies have been published by C. Christensen and his co-authors. Modified slightly from [C14] and [CJT12] is the following information.

Lester Sanders Hill was born on January 19, 1890 in New York. He graduated from Columbia University in 1911 with a B. A. in Mathematics and earned his Master’s Degree in 1913. He taught mathematics for a few years at Montana University, then at Princeton University. He served in the United States Navy Reserves during World War I. After the WWI, he taught at the University of Maine and then at Yale, from which he earned his Ph.D. in mathematics in 1926. His Ph.D. advisor is not definitely known at this writing but I think a reasonable guess is Wallace Alvin Wilson.

In 1927, he accepted a position with the faculty of Hunter College in New York City, and he remained there, with one exception, until his resignation in 1960 due to illness. The one exception was for teaching at the G.I. University in Biarritz in 1946, during which time he may have been reactivated as a Naval Reserves officer. Hill died January 9, 1961.

Thanks to an interview that David Kahn had with Hill’s widow reported in [C14], we know that Hill loved to read detective stories, to tell jokes and, while not shy, enjoyed small gatherings as opposed to large parties.

Who is Hamming? His life is much better known and details can be readily found in several sources.

Richard Wesley Hamming was born on February 11, 1915, in Chicago. Hamming earned a B.S. in mathematics from the University of Chicago in 1937, a masters from the University of Nebraska in 1939, and a PhD in mathematics (with a thesis on differential equations)
from the University of Illinois at Urbana-Champaign in 1942. In April 1945 he joined the Manhattan Project at the Los Alamos Laboratory, then left to join the Bell Telephone Laboratories in 1946. In 1976, he retired from Bell Labs and moved to the Naval Postgraduate School in Monterey, California, where he worked as an Adjunct Professor
and senior lecturer in computer science until his death on January 7, 1998.

Hill’s cipher

The Hill cipher is a polygraphic cipher invented by Lester S. Hill in 1920’s. Hill and his colleague Wisner from Hunter College filed a patent for a telegraphic device encryption and error-detection device which was roughly based on ideas arising from the Hill cipher. It appears nothing concrete became of their efforts to market the device to the military, banks or the telegraph company (see Christensen, Joyner and Torres [CJT12] for more details). Incidently, Standage’s excellent book [St98] tells the amusing story of the telegraph company’s failed attempt to add a relatively simplistic error-detection to telegraph codes during that time period.

Some books state that the Hill cipher never saw any practical use in the real world. However, research by historians F. L. Bauer and David Kahn uncovered the fact that the Hill cipher saw some use during World War II encrypting three-letter groups of radio call signs [C14]. Perhaps insignificant, at least compared to the practical value of Hamming codes, none-the-less, it was a real-world use.

The following discussion assumes an elementary knowledge of matrices. First, each letter is first encoded as a number, namely

A \leftrightarrow 0, B \leftrightarrow 1, \dots, Z \leftrightarrow 25. The subset of the integers \{0, 1, \dots , 25\} will be denoted by Z/26Z. This is closed under addition and multiplication (mod 26), and sums and products (mod 26) satisfy the usual associative and distributive properties. For R = Z/26Z, let GL(k,R) denote the set of invertible matrix transformations T:R^k\to R^k (that is, one-to-one and onto linear functions).


The construction

Suppose your message m consists of n capital letters, with no spaces. This may be regarded an n-tuple M with elements in R = Z/26Z. Identify the message M as a sequence of column vectors {\bf p}\in R^k. A key in the Hill cipher is a k\times k matrix K, all of whose entries are in R, such that the matrix K is invertible. It is important to keep K and k secret.

The encryption is performed by computing {\bf c} = K{\bf p}, and rewriting the resulting vector as a string over the same alphabet. Decryption is performed similarly by computing {\bf p} = K^{-1} {\bf c}..

Example 1: Suppose m is the message “BWGN”. Transcoding into numbers, the plaintext is rewritten p_0=1, p_1=22, p_2=6, p_3=13. Suppose the key is
K=\left(\begin{array}{rr} 1 & 3 \\ 5 & 12 \end{array}\right).
Using Hill’s encryption above gives c_0=7,c_1=3,c_2=24,c_3=3. (Verification is left to the reader as an exercise.)

Security concerns: For example, this cipher is linear and can be broken by a known plaintext attack.


Hamming codes

Richard Hamming is a pioneer of coding theory, introducing the binary
Hamming codes in the late 1940’s. In the days when an computer error could crash the computer and force the programmer to retype his punch cards, Hamming, out of frustration, designed a system whereby the computer could automatically correct certain errors. The family of codes named after him can easily correct one error.


Hill’s unpublished paper

While he was a student at Yale, Hill published three papers in Telegraph and Telephone Age [H1], [H2], [H3]. In these papers Hill described a mathematical method for checking the accuracy of telegraph communications. There is some overlap with these papers and [H5], so it seems likely to me that Hill’s unpublished paper [H5] dates from this time (that is, during his later years at Yale or early years at Hunter).

In [H5], Hill describes a family of linear block codes over a finite field and an algorithm for error-detection (which can be easily extended to error-correction). In it, he states the construction of what I’ll call the “Hill codes,” (defined below), gives numerous computational examples, and concludes by recording Hill’s Problem (stated above as Question 1). It is quite possibly Hill’s best work.

Here is how Hill describes his set-up.

Our problem is to provide convenient and practical accuracy checks upon
a sequence of n elements f_1, f_2, \dots, f_r in a finite algebraic
field F. We send, in place of the simple sequence f_1, f_2, \dots, f_r, the amplified sequence f_1, f_2, \dots, f_r, c_1, c_2, \dots, c_k
consisting of the “operand” sequence and the “checking” sequence.

– Lester Hill, [H5]

Then Hill continues as follows. Let F=GF(p) denote the finite field having p elements, where p>2 is a prime number. The checking sequence contains k elements of F as follows:
c_j = \sum_{i=1}^r a_{i}^jf_i,
for j = 1, 2, \dots, k. The checks are to be determined by means of a
fixed matrix
A = \left( \begin{array}{cccc} a_{1} & a_{2} & \dots & a_{r} \\ a_{1}^2 & a_{2}^2 & \dots & a_{r}^2 \\ \vdots & & & \vdots \\ a_{1}^k & a_{2}^k & \dots & a_{r}^k \\ \end{array} \right)
of elements of F, the matrix having been constructed according to the criteria in Hill’s Problem above. In other words, if the operand sequence (i.e., the message) is the vector {\bf f} = (f_1, f_2, \dots, f_r), then the amplified sequence (or codeword in the Hill code) to be transmitted is

{\bf c} = {\bf f}G,
where G = \left( I_r, A \right) and where I_r denotes the
r\times r identity matrix. The Hill code is the row space of G.

We conclude with one more open question.

Question 3:
What is the minimum distance of a Hill code?

The minimum distance of any Hamming code is 3.

Do all sufficiently long Hill codes have minimum distance greater than 3?


Summary

Most books today (for example, the excellent MAA publication written by Thompson [T83]) date the origins of the theory of error-correcting codes to the late 1940s, due to Richard Hamming. However, this paper argues that the actual birth is in the 1920s due to Lester Hill. Topics discussed include why Hill’s discoveries weren’t publicly known until relatively recently, what Hill actually did that trumps Hamming, and some open (mathematical) questions connected with Hill’s work.

For more details, see these previous blog posts.

Acknowledgements: Many thanks to Chris Christensen and Alexander Barg for
helpful and encouraging conversations. I’d like to explicitly credit Chris Christensen, as well as historian David Kahn, for the original discoveries of the source material.


Bibliography

[C14] C. Christensen, Lester Hill revisited, Cryptologia 38(2014)293-332.

[CJT12] ——, D. Joyner and J. Torres, Lester Hill’s error-detecting codes, Cryptologia 36(2012)88-103.

[H1] L. Hill, A novel checking method for telegraphic sequences, Telegraph and
Telephone Age (October 1, 1926), 456 – 460.

[H2] ——, The role of prime numbers in the checking of telegraphic communications, I, Telegraph and Telephone Age (April 1, 1927), 151 – 154.

[H3] ——, The role of prime numbers in the checking of telegraphic
communications, II, Telegraph and Telephone Age (July, 16, 1927), 323 – 324.

[H4] ——, Lester S. Hill to Lloyd B. Wilson, November 21, 1925. Letter.

[H5] ——, Checking the accuracy of transmittal of telegraphic communications by means of operations in finite algebraic fields, undated and unpublished notes, 40 pages.
(hill-error-checking-notes-unpublished)

[MS77] F. MacWilliams and N. Sloane, The Theory of Error-Correcting Codes, North-Holland, 1977.

[Sh] A. Shokrollahi, On cyclic MDS codes, in Coding Theory and Cryptography: From Enigma and Geheimschreiber to Quantum Theory, (ed. D. Joyner), Springer-Verlag, 2000.

[St98] T. Standage, The Victorian Internet, Walker & Company, 1998.

[T83] T. Thompson, From Error-Correcting Codes Through Sphere Packings to Simple Groups, Mathematical Association of America, 1983.

Mathematics of zombies

Posted on by

What do you do if there is a Zombie attack? Can mathematics help? This page is (humorously) dedicated to collecting links to papers or blog posted related to the mathematical models of Zombies.

 

George Romero’s 1968 Night of the Living Dead, now in the public domain, introduced reanimated ghouls, otherwise known as zombies, which craved live human flesh. Romero’s script was insired on Richard Matheson’s I Am Legend. In Romero’s version, the zombies could be killed by destroying the zombie’s brain. A dead human could, in some cases be “reanimated,” turning into a zombie. These conditions are modeled mathematically in several papers, given below.

  1. When Zombies Attack! Mathematical Modelling of a Zombie Outbreak!, paper by Mathematicians at the University of Ottawa, Philip Munz, Ioan Hudea, Joe Imad and Robert J. Smith? (yes, his last name is spelled “Smith?”).
  2. youtube video 28 Minutes Later – The Maths of Zombies , made by Dr James Grime (aka, “siningbanana”), which references the above paper.
  3. Epidemics in the presence of social attraction and repulsion, Oct 2010 Zombie paper by Evelyn Sander and Chad M. Topaz.
  4. Statistical Inference in a Zombie Outbreak Model, slides for a talk given by Des Higman, May 2010.
  5. Mathematics kills zombies dead!, 08/17/2009 blog post by “Zombie Research Society Staff”.
  6. The Mathematics of Zombies, August 18, 2009 blog post by Mike Elliot.
  7. Love, War and Zombies – Systems of Differential Equations using Sage, April 2011 slides by David Joyner. Sage commands for Love, War and Zombies talk. This was given as a Project Mosaic/M-cast broadcast.
  8. Public domain 1968 film Night of the Living Dead by George Romero.

Complements in the symmetric group

Posted on by

About 20 years ago I was asked a question of Herbert Kociemba, a computer scientist who has one of the best Rubik’s cube solving programs known. Efficient methods of storing permutations in S_E and S_V (the groups of all permutations of the edges E and vertices V, respectively, of the Rubik’s cube) are needed, hence leading naturally to the concept of the complement of S_m in S_n. Specifically, he asked if S_8 has a complement in S_{12} (this terminology is defined below). The answer is,
as we shall see, ”no.” Nonetheless, it turns out to be possible to introduce a slightly more general notion of a “k-tuple of complementary subgroups” (defined below) for which the answer to the analogous question is ”yes.”

This post is a very short summary of a paper I wrote (still unpublished) which can be downloaded here.

Splitting fields of representations of generalized symmetric groups, 8

Posted on by

In this post, we give an example.

Let G=C_3^8\, >\!\!\lhd \, S_8 and let

\pi = \theta_{\mu,\rho}=Ind_{G_\mu}^G(\mu\cdot \tilde{\rho}),

where \mu is a character of C_3^8 and \rho is an irreducible representation of its stabilizer in S_8, (S_8)_\mu.

The real representations \pi of G are the ones for which

  1. \mu is represented by a character of the form

    (1,1,1,1,1,1,\omega,\omega^2) \ {\rm or}\ (1,1,...,1),

    and \rho anything, or

  2. \mu is represented by a character of the form

    (1,1,1,1,\omega,\omega,\omega^2,\omega^2), \rho_1=(\pi_1,\pi_2,\pi_2)\in (S_4)^*\times (S_2)^*\times (S_2)^*,

    or

  3. \mu is represented by a character of the form

    (\omega,\omega,\omega,\omega,\omega^2,\omega^2,\omega^2,\omega^2), \rho_1=(\pi_2,\pi_2)\in (S_4)^*\times (S_4)^*,

    or

  4. \mu is represented by a character of the form

    (1,1,\omega,\omega,\omega,\omega^2,\omega^2,\omega^2), \rho_1=(\pi_1,\pi_2,\pi_2)\in (S_2)^*\times (S_3)^*\times (S_3)^*.

The complex representations of G are: the representations
whose characters have at least one complex value. Such representations \pi = \theta_{\mu,\rho} are characterized by the fact that (\mu,\rho) is inequivalent to (\overline{\mu},\rho) under the obvious $S_8$-equivalence relation (which can be determined from the equivalence relation for representations in G^*).

The complex representations of G are the remaining representations not included in the above list.

There are no quaternionic representations of G.

The claims above follow from the fact that a representation
\theta_{\rho,\mu} is complex if and only if \mu is not self-dual.

Splitting fields of representations of generalized symmetric groups, 7

Posted on by

In this post, we discover which representations of the generalized symmetric group G = S_n\ wr\ C_\ell = C_\ell^n\, >\!\!\lhd \, S_n can be realized over a given abelian extension of {\mathbb{Q}}.

Let \theta_{\mu,\rho}\in G^* be the representation defined previously, where \rho\in ((S_n)_\mu)^*.

Let K\subset {\mathbb{Q}}(\zeta_\ell) be a subfield, where \zeta_\ell is a primitive \ell^{th} root of unity. Assume K contains the field generated by the values of the character of \theta_{\mu,\rho}. Assume K/{\mathbb{Q}} is Galois and let \Gamma_K=Gal({\mathbb{Q}}(\zeta_\ell)/K). Note if we regard C_\ell as a subset of {\mathbb{Q}}(\zeta_\ell) then there is an induced action of \Gamma_K on C_\ell,

\sigma:\mu \longmapsto \mu^\sigma, \ \ \ \ \ \ \ \ \ \mu\in (C_\ell)^*,\ \ \sigma\in \Gamma_K,

where \mu^\sigma(z)=\mu(\sigma^{-1}(z)), z\in C_\ell. This action extends to an action on (C_\ell^n)^*=(C_\ell^*)^n.

Key Lemma:
In the notation above, \theta_{\mu,\rho}\cong\theta_{\mu,\rho}^\sigma if and only if \mu is equivalent to \mu^\sigma under the action of S_n on (C_\ell^n)^*.

Let

n_\mu(\chi)=|\{i\ |\ 1\leq i\leq n,\ \mu_i=\chi\}|,

where \mu=(\mu_1,...,\mu_n)\in (C_\ell^n)^* and \chi\in C_\ell^*.

Theorem: The character of \theta_{\mu,\rho}\in G^* has values in K if and only if n_\mu(\chi)=n_\mu(\chi^\sigma),
for all \sigma\in \Gamma_K and all \chi\in C_\ell^*.

This theorem is proven in this paper.

We now determine the splitting field of any irreducible character of a generalized symmetric group.

Theorem: Let \chi=tr(\theta_{\rho,\mu}) be an irreducible character of G=S_n\ wr\ C_\ell. We have

Gal({\mathbb{Q}}(\zeta_\ell)/{\mathbb{Q}}(\chi))= Stab_\Gamma(\chi).

This theorem is also proven in this paper.

In the next post we shall give an example.

Splitting fields of representations of generalized symmetric groups, 6

Posted on by

This post shall list some properties of the Schur index m_F(G) in the case where G = S_n\ wr\ C_\ell is a generalized symmetric group and F is either the reals or rationals.

Let \eta_k(z)=z^k, for z\in C_\ell, 1\leq k\leq \ell.

Theorem: Let G = S_n\ wr\ C_\ell. Let \mu=(\eta_{e_1},...,\eta_{e_n})\in (C_\ell^n)^*, for some e_j\in \{0,...,\ell-1\}, and let \rho\in (S_n)_\mu^*. Let
\chi denotes the character of \theta_{\mu,\rho}.

  1. Suppose that one of the following conditions holds:
    1. 4|\ell and \overline{e_1+...+e_n} divides \overline{\ell/4} in {\mathbb{Z}}/\ell {\mathbb{Z}}, or
    2. (e_1+...+e_n,\ell)=1,

    Then m_{\Bbb{Q}}(\chi)=1.

  2. Suppose that one of the following conditions holds:
    1. (n,\ell)=1, 4|\ell, and (e_1+...+e_n)x\equiv \ell /4\ ({\rm mod}\ \ell) is not solvable, or
    2. (n,\ell)=1 and (e_1+...+e_n,\ell)>1.

    Then m_{\mathbb{Q}}(\chi\eta_1)=1.

This theorem is proven in this paper. Benard has shown that m_{\mathbb{Q}}(\chi)=1, for all \chi as in the above theorem.

Since the Schur index over {\mathbb{Q}} of any irreducible character \chi of a generalized symmetric group G is equal to 1, each such character is associated to a representation \pi all of whose matrix coefficients belong to the splitting field {\mathbb{Q}}(\chi).

What is the splitting field {\mathbb{Q}}(\chi), for \chi\in G^*?

This will be addressed in the next post.

Splitting fields of representations of generalized symmetric groups, 5

Posted on by

It is a result of Benard (Schur indices and splitting fields of the unitary reflection groups, J. Algebra, 1976) that the Schur index over {\mathbb{Q}} of any irreducible character of a generalized symmetric group is equal to 1. This post recalls, for the sake of comparison with the literature, other results known about the Schur index in this case.

Suppose that G is a finite group and \pi \in G^* is an irreducible representation of G, \pi :G\rightarrow Aut(V), for some complex vector space V. We say that \pi may be realized over a subfield F\subset {\mathbb{C}} if there is an F-vector space V_0 and an action of G on V_0 such that V and {\mathbb{C}}\otimes V_0 are equivalent representations of G, where G acts on {\mathbb{C}}\otimes V_0 by “extending scalars” in V_0 from F to {\mathbb{C}}. Such a representation is called an F-representation. In other words, \pi is an F-representation provided it is equivalent to a representation which can be written down explicitly using matrices with entries in F.

Suppose that the character \chi of \pi has the property that

\chi(g)\in F, \ \ \ \ \ \ \forall g\in G,

for some subfield F\subset {\mathbb{C}} independent of g. It is unfortunately true that, in general, \pi is not necessarily an F-representation. However, what is remarkable is that, for some m\geq 1, there are m representations, \pi_1,...,\pi_m, all equivalent to \pi, such that \pi_1\oplus ...\oplus \pi_m is an F-representation. The precise theorem is the following remarkable fact.

Theorem: (Schur) Let \chi be an irreducible character and let F be any field containing the values of \chi. There is an integer m \geq 1 such that m\chi is the character of an F-representation.

The smallest m\geq 1 in the above theorem is called the Schur index and denoted m_F(\chi).

Next, we introduce some notation:

  1. let {\mathbb{R}}(\pi) = {\mathbb{R}}(\chi) denote the extension field of {\mathbb{R}} obtained by adjoining all the values of \chi(g)\ ($g\in G$), where \chi is the character of \pi,
  2. let \nu(\pi) = \nu(\chi) denote the Frobenius-Schur indicator of \pi (so \nu(\pi)= {1\over |G|}\sum_{g\in G} \chi(g^2)),
  3. let m_{\mathbb{R}}(\pi) = m_{\mathbb{R}}(\chi) denote the Schur multiplier of \pi (by definition, the smallest integer m\geq 1 such that $m\chi$ can be realized over {\mathbb{R}} (this integer exists, by the above-mentioned theorem of Schur).

The following result shows how the Schur index behaves under induction (see Proposition 14.1.8 in G. Karpilovsky,
Group representations, vol. 3, 1994).

Proposition: Let \chi be an irreducible character of G and let \psi denote an irreducible character of a subgroup H of G. If = 1 then m_{\Bbb{R}}(\chi) divides m_{\Bbb{R}}(\psi).

A future post shall list some properties of the Schur index in the case where G is a generalized symmetric group and F is either the reals or rationals.

Splitting fields of representations of generalized symmetric groups, 4

Posted on by

This post if an aside on cyclotomic fields and Tchebysheff polynomials. Though it seems certain this material is known, I know of no reference.

Let n denote a positive integer divisible by 4, let r=\cos(2\pi/n), s=\sin(2\pi/n), and let d=n/4. If

T_1(x)=x,\ \ T_2(x)=2x^2-1,\ \ T_3(x)=4x^3-3x,\ \ T_4(x)=8x^4-8x^2+1,\ \ ...,

denote the Tchebysheff polynomials (of the 1st kind), defined by

\cos(n\theta)=T_n(\cos(\theta)),

then T_d(r)=0.

Let \zeta_n=exp(2\pi i/n) and let F_n={\mathbb{Q}}(\zeta_n) denote the cyclotomic field of degree \phi(n) over {\mathbb{Q}}. If \sigma_j\in Gal(F_n/{\Bbb{Q}}) is defined by \sigma_j(\zeta_n)=\zeta_n^j then

Gal(F_n/{\Bbb{Q}})\cong ({\Bbb{Z}}/n{\Bbb{Z}})^\times,

where \sigma_j\longmapsto j.

Lemma: Assume n is divisible by 4.

  1. {\mathbb{Q}}(r) is the maximal real subfield of F_n, Galois over {\mathbb{Q}} with

    Gal(F_n/{\Bbb{Q}}(r))=\{1,\tau\},

    where $\tau$ denotes complex conjugation. Under the canonical isomorphism

    Gal(F_n/{\Bbb{Q}})\cong ({\Bbb{Z}}/n{\Bbb{Z}})^\times,

    we have

    Gal({\Bbb{Q}}(r)/{\Bbb{Q}})\cong ({\Bbb{Z}}/n{\Bbb{Z}})^\times/\{\pm 1\}.

  2. If n is divisible by 8 then r and s are conjugate roots of T_d. In particular, s\in {\mathbb{Q}}(r) and T_d(s)=0.

  3. We have \sigma_j(r)=T_j(r).
  4. If n\geq 4 is a power of 2 then T_d is the minimal polynomial of {\mathbb{Q}}(r). Furthermore, in this case

    \cos(\pi/4)=\sqrt{2}/2,\ \ \cos(\pi/8)=\sqrt{2+\sqrt{2}}/2,\ \ \cos(\pi/16)=\sqrt{2+\sqrt{2+\sqrt{2}}}/2,\ \ ... .

Splitting fields of representations of generalized symmetric groups, 4

Posted on by

First a technical definition.

Let A=C_\ell^n. Let \eta_k(z)=z^k, for z\in C_\ell and 1\leq k\leq \ell-1. For \eta\in C_\ell^*, let \mu\otimes \eta =(\mu_1\eta,\mu_2\eta,...,\mu_n\eta) where \mu=(\mu_1,\mu_2,...,\mu_n). This defines an action of C_\ell^* on A^* and hence on the set of equivalence classes of G, G^*. We call two representations \theta_{\mu,\rho}, \theta_{\mu',\rho'} C_\ell^*-equivalent, and write

\theta_{\mu,\rho}\sim_\ell \theta_{\mu',\rho'},

if \rho=\rho' and \mu'=\mu\otimes \eta for some \eta\in C_\ell^*. Similarly, we call two characters \mu, \mu' of C_\ell^n C_\ell^*-equivalent, and write

\mu\sim_\ell \mu',

if \mu'=\mu\otimes \eta for some \eta\in C_\ell^*.

For example, Let \ell =9, n=3 and \mu=(\eta_2,\eta_5,\eta_8). Then \mu\sim \mu\otimes\eta_3.

Let \theta_{\mu,\rho} be as in the previous post. Note that

\theta_{\mu\otimes \eta,\rho} = \theta_{\mu,\rho}\otimes \eta ,

for \eta\in C_\ell^*. Therefore, the matrix representations of two C_\ell^*-equivalent representations differ only
by a character.

Let G=C_\ell^n\, >\!\!\lhd \, S_n.

The results in the above section tells us how to construct all the irreducible representations of G. We must

  1. write down all the characters (i.e., 1-dimensional representations) of A=C_\ell^n,
  2. describe the action of S_n on A^*,
  3. for each \mu\in [A^*], compute the stabilizer (S_n)_{\mu},
  4. describe all irreducible representations of each (S_n)_{\mu},
  5. write down the formula for the character of \theta_{\mu,\rho}.

Write \mu\in [A^*] as \mu=(\mu_1,...,\mu_n), where each component is a character of the cyclic group C_\ell, \mu_j\in C_\ell^*. Let \mu'_1,...,\mu'_r denote all the distinct characters which occur in \mu, so

\{\mu'_1,...,\mu'_r\}=\{ \mu_1,...,\mu_n\}.

Let n_1 denote the number of \mu'_1‘s in \mu, n_2 denote the number of \mu'_2‘s in \mu, …, n_r denote the number of \mu'_r‘s in \mu. Then n=n_1+...+n_r. Call this the partition associated to \mu.

If two characters \mu=(\mu_1,...,\mu_n), \mu'=(\mu'_1,...,\mu'_n) belong to the same class in [(C_\ell^n)^*], under the S_n-equivalence relation, then their associated partitions are equal.

The Frobenius formula for the character of an induced representation gives the following character formula. Let \chi denote the character of \theta_{\mu,\rho}. Then

\chi(\vec{v},p)=\sum_{g\in S_n/(S_n)_\mu} \chi^o_\rho(gpg^{-1})\mu^g(\vec{v}),

for all \vec{v}\in C_\ell^n and p\in S_n. In particular, if p=1 then

\chi(\vec{v},1)=({\rm dim}\ \rho)\sum_{g\in S_n/(S_n)_\mu} \mu^g(\vec{v}).

Splitting fields of representations of generalized symmetric groups, 3

Posted on by

The representations of a semi-direct product of a group H by an abelian group A, written G=A\, >\!\!\lhd \, H (so A is normal in G) can be described explicitly in terms of the representations of A and H. The purpose of this post is to explain how this is done.

Again, a good reference for all this is Serre’s well-known book, Linear representations of finite groups.

Let f be a class function on $H$. Extend f to G trivially as follows:

f^0(g)= \left\{ \begin{array}{cc} f(g),&g\in H,\\ 0, & g\notin H, \end{array} \right.

for all g\in G. This is not a class function on G in general. To remedy this, we “average over G” using conjugation: Define the function f^G=Ind_H^G(f) induced by f to be

Ind_H^G(f)(g)={1\over |H|}\sum_{x\in G} f^0(x^{-1}gx)=\sum_{x\in G/H}f^0(x^{-1}gx).

This is referred to as the Frobenius formula.

Since A is normal in G, G acts on the vector space of formal complex linear combinations of elements of A^* (=the characters of A),

V={\mathbb{C}}[A^*]=span\{\mu\ |\ \mu\in A^*\},

by

(g\mu)(a)=\mu(g^{-1}ag),\ \ \ \ \forall g\in G,\ a\in A,\ \mu\in A^*.

We may restrict this action to H, giving us a homomorphism \phi^*:H\rightarrow S_{A^*}, where S_{A^*} denotes the symmetric group of all permutations of the set A^*. This restricted action is an equivalence relation on A^* which we refer to below as the H-equivalence relation}. Let [A^*] denote the set of equivalence classes of this equivalence relation. If \mu,\mu' belong to the same equivalence class then we write

\mu'\sim \mu

(or \mu'\sim_H\mu if there is any possible ambiguity). When there is no harm, we identify each element of [A^*] with a character of A.

Suppose that H acts on A by means of the automorphism given by a homomorphism \phi:H\rightarrow S_{A}, where S_{A} denotes the symmetric group of all permutations of the set A. In this case, two characters \tau,\tau'\in A^* are equivalent if there is an element h\in H such that, for all a\in A, we have \tau'(a)=\tau(\phi(h)(a)).

For each \mu\in [A^*], let

H_{\mu}=\{h\in H\ |\ h\mu = \mu\}.

This group is called the stabilizer of \mu in H. Let

G_{\mu}=A\, >\!\!\lhd \, H_{\mu},

for each \mu\in [A^*]. There is a natural projection map

p_{\mu}:G_{\mu}\rightarrow H_{\mu}

given by ah\longmapsto h, i.e., by p_\mu(ah)=a.

Extend each character \mu\in [A^*] from H_{\mu} to G_{\mu} trivially by defining

\mu(ah)=\mu(a),

for all a\in A and h\in H_{\mu}. This defines a character \mu\in G^*_{\mu}. For each \rho\in H_{\mu}^*, say \rho:H_{\mu} \rightarrow Aut(V), let \tilde{\rho}\in G_{\mu}^* denote the representation of G_{\mu} obtained by pulling back \rho via the projection p_\mu:G_{\mu}\rightarrow H_{\mu}, i.e., define

\tilde{\rho}=\rho\circ p_{\mu}.

For each \mu \in [A^*] and \rho\in H_\mu^* as above, let

\theta_{\mu,\rho}=Ind_{G_\mu}^G(\mu\cdot \tilde{\rho}).

Finally, we can completely describe all the irreducible representations of G=A\, >\!\!\lhd \, H. (This is Proposition 25 in chapter 8 of Serre’s book.)

Theorem:

  1. For each \mu \in [A^*] and \rho\in H_\mu^*, as above, then \theta_{\mu,\rho} is an irreducible representation of G.
  2. Suppose \mu_1,\mu_2 \in [A^*], \rho_1\in H_{\mu_1}^*, \rho_2\in H_{\mu_2}^*. If \theta_{\mu_1,\rho_1}\cong \theta_{\mu_2,\rho_2} then \mu_1\sim \mu_2 and \rho_1\cong \rho_2.
  3. If \pi is an irreducible representation of G then \pi\cong \theta_{\mu,\rho}, for some \mu \in [A^*] and \rho\in H_{\mu}^* as above.

In the next post, we will examine the special case A=C_\ell^n and H=S_n.