Magic Squares and Algebraic Number Theory

March 9, 2007

Foxy asks whether it’s possible to have a 3*3 magic square all of whose entries are square integers. It’s fairly elementary to show that in a 3*3 magic square, the common sum is three times the middle entry. So let’s say the entries of the magic square go [a^2, b^2, c^2; d^2, e^2; f^2; g^2, q^2, h^2]; we want to have, for example, a^2 + h^2 = 2e^2.

This alone is very restrictive, since it requires (a^2, e^2, h^2) to be an arithmetic sequence, a sufficiently special situation that unless a = e = h, the next term in the sequence will never be a square (no, I can’t prove it; I’ve tried). So to find such magic squares whose entries are not all the same, it makes sense to start bashing through the Diophantine equation a^2 + h^2 = 2e^2.

First, the easy part: we can assume a, e, and h are coprime; otherwise, divide by their greatest common divisor. If e is even, then 2e^2 is divisible by 8, in which case it’s impossible for a and h to be odd since odd squares are equivalent to 1 mod 8, so that a and h are even and the three numbers are not coprime. So e is odd, from which it’s easy to show that so are a and h.

Now, when we have sums of two squares, the most natural environment to study divisibility is Z[i], the ring of Gaussian integers. We get (a + hi)(ahi) = 2e^2. As a and h are odd, a (+/-) hi is not divisible by 2, so both a + hi and ahi must be divisible by 1 + i. That condition isn’t a problem: (a + hi)/(1 + i) = (a + hi)(1 – i)/2 = (a + h)/2 + i(ha)/2, and similarly (ahi)/(1 – i) = (a + h)/2 + i(ah)/2.

It now makes sense to write x = (a + h)/2, y = (ah)/2. Conversely, a = x + y and h = xy; as a and h are odd, this means that x and y have opposite parities. Since dividing once by 1 + i and once by 1 – i factors out 2 on the right-hand side, this turns the equation into (x + iy)(xiy) = e^2, or x^2 + y^2 = e^2.

Here is where things get nightmarishly complicated. Any common factor of x and y divides a, e, and h, so x, y, and e are coprime. Consider the primes of Z[i] that divide x + iy; none can be in Z because that would imply a common factor of x and y. But all primes in Z[i] that have no associate in Z have norm equivalent to 1 or 2 mod 4, where here 1 + i is impossible because 1 + i divides x + iy iff x and y have the same parity. So right off the bat, e is the product of primes equivalent to 1 mod 4.

Further, each distinct prime factor after the first of e gives exactly two choices of x and y. To see what I mean, first consider the case when e is prime. Then e = (r + is)(ris), so e^2 = (r + is)(ris)(r + is)(ris). There are two ways of grouping them into x and y, but the one that sends the first two to x + iy factors e^2 as e*e, i.e. x = e and y = 0. Hence there’s only one way, the one that sends (r + is)^2 to x + iy. If e is divisible by an additional prime and breaks as (r1 + is1)(r1 – is1)(r2 + is2)(r2 – is2) then once the decision to send (r1 + is1)^2 to x + iy has been made, it’s possible to send (r2 + is2)^2 or (r2 – is2)^2 to x + iy. This easily generalizes to further prime factors, but not to repeated factors.

This means that e can’t be prime because then the eight elements of the magic square around it will all be either a^2 or h^2, making it impossible for the other magic square conditions to hold. Now, using capital letters to denote squares, we get that the magic square is [A, B, 3E - A - B; 4E - 2A - B, E, 2A + B - 2E; A + B - E, 2E - B, 2E - A].

The above considerations show that E must be divisible only by primes equivalent to 1 mod 4 because it’s sandwiched between A and 2E – A. But by the same token, 2E – A is sandwiched between 4E – 2A – B and B, so it must similarly be divisible only by primes equivalent to 1 mod 4; similar considerations apply to A, which is sandwiched between 2A + B – 2E and 2E – B.


Carnival of Mathematics #3 is Up

March 9, 2007

The third Carnival is up on Michi’s Blog, complete with algebra, topology, and a lot of math teaching. There’s less computer science than before, but it simply makes me feel less stupid for not knowing Haskell. There’s even a HUHO-themed post that explains why payday loans are a bad idea.

Carnival of Mathematics #4 will be posted on EvolutionBlog on March 23rd. Send submissions to Jason Rosenhouse at rosenhjd at jmu dot edu or to me at alon_levy1@yahoo.com or use the submission form (which surprisingly few people seem to do).


Galois Theory: Infinite Galois Theory

March 7, 2007

So far I’ve only discussed finite Galois theory, that is the Galois theory of finite extensions. But there’s also an infinite theory; the extensions it studies are separable and normal, just like finite Galois extensions, but the fundamental theorem needs to be modified to apply. I could transfer it almost in its entirety by using the theory of topological groups, but I think it’s simpler to just make exceptions and note the equivalent topological terminology where necessary.

Infinite Galois theory is wedded to the theory of projective limits of groups, which is based on directed systems.

A set I is a directed system if it comes equipped with a partial order, which I’ll denote <–, such that given any two elements i and j of I, there exists a k in I such that i <– k and j <– k. For example, a total order induces a directed system. For a less trivial example, let I = N (without zero), with a <– b iff a divides b; given any i and j, a suitable k is their least common multiple. Note that if I has a maximal element, then that maximal element is unique.

Now, an inverse system of groups is a family of groups G(i) indexed by the set I, and homomorphisms from G(j) to G(i) whenever i <– j, denoted f(ij). The homomorphisms must be consistent with one another, i.e. given i <– j <– k, every g in G(k) must satisfy f_{ik}(g) = f_{ij}(f_{jk}(g)). Typically the homomorphisms are taken to be surjective, but strictly speaking this is not necessary.

For example, if I = N with the normal ordering, letting G(n) = Z/(p^n)Z and f(mn) be the obvious remainder map from Z/(p^n)Z to Z/(p^m)Z yields an inverse system. Alternatively, if I has the divisibility ordering defined above, then G(n) = Z/nZ with the remainder maps is similarly an inverse system.

An inverse system has a limit, defined to be the group that projects on all groups in the system. More precisely, let P be the product of all groups G(i). Note that this is a product rather than a direct sum, the difference being that in a direct sum all but finitely many terms must be the identity element. The inverse or projective limit \underleftarrow{\lim}G_{i} is the subgroup of P consisting of all elements g in P such that for all i <– j in I, g_{i} = f_{ij}(g_{j}).

Finally living up to my blog’s name, I’ll also prove the abstract nonsense definition of projective limits. The projective limit comes with obvious projection maps f_{i}: g \mapsto g_{i}; if each f(ij) is surjective, then so is each f(i). Furthermore, taken together with those projection maps, it’s universal with the property that f_{ij}(f_{j}(g)) = f_{i}(g). In plain mathematical English, it means that if H is another group with projection maps h(i) such that f(ij)h(j) = h(i), then there exists a unique group homomorphism p from H to the projective limit such that h(i) = f(i)p.

This is likely the first time you encounter universal properties – if it is, consider yourself lucky to have never seen these monsters until now – so I’ll prove it in full instead of appeal to other universal properties. The idea is to explicitly define p in such a way that will yield h(i) = f(i)p.

Every a in H induces an element h_{i}(a) for each i in I. Furthermore, the condition that f(ij)h(j) = h(i) implies that f_{ij}(h_{j}(a)) = h_{i}(a). Therefore, the element of P whose ith entry is h_{i}(a) is in fact in the projective limit, yielding a function p from H to \underleftarrow{\lim}G_{i}. This is a group homomorphism, roughly because the ith element of p(ab) is h_{i}(ab) = h_{i}(a)h_{i}(b). Further, that the ith element of p(a) is h_{i}(a) implies immediately that h(i) = f(i)p.

Conversely, this homomorphism is unique because the condition that h(i) = f(i)p forces the ith element of p(a) to be h_{i}(a). This is important because it shows that if H and H’ satisfy the universal property of the projective limit of the same inverse system of groups, then there exists a unique p with h(i) = h‘(i)p and a unique p‘ with h(i)p = h‘(i) so that p and p‘ are isomorphisms that are inverses of each other, and the universal property uniquely defines the projective limit.

Note that it’s possible to define similar inverse limits of every algebraic structure – rings, modules, algebras, and so on – as well as of topological spaces. Also note that if I has a maximal element then the projective limit is just that element, making the case of interest the one with no maximal element. Finally, duplicating an index – i.e. splitting i into i1 and i2, with i(j) <– k iff i <– k and k <– i(j) iff k <– i, and with i1 and i2 either comparable or incomparable – doesn’t change the projective limit.

As an example, the projective limit of G(n) = Z/(p^n)Z is \mathbb{Z}_{p}, the additive group of the p-adic integers; it’s certainly true that every sequence of residue classes modulo p^n compatible under taking remainders induces a p-adic integer and vice versa.

More interestingly, the projective limit of G(n) = Z/nZ is the product of Z(p) over all primes p. This is because by the universal property, \underleftarrow{\lim}(G_{i} \times H_{i}) = \underleftarrow{\lim}G_{i} \times \underleftarrow{\lim}H_{i}, and Z/(p1^a1)(p2^a2)…(p(k)^a(k))Z = Z/(p1^a1)Z * Z/(p2^a2)Z * … * Z/(p(k)^a(k))Z.

Back to Galois theory now. If L/K is an infinite Galois extension (i.e. separable and normal, as in the finite case), then the Galois groups of the intermediate Galois extensions form an inverse system, roughly because if F/E/K is a tower of Galois extensions, then Gal(F/K) projects onto Gal(E/K). If you deal with sequences better than with abstract inverse systems, then let L be the splitting field of {f1, f2, …} and look at the splitting field of f1, then this of f1f2, then this of f1f2f3…

A K-automorphism of L is defined by its action on each a in L. But L/K is assumed to be algebraic, so each a in L is contained in a finite extension of K, which has a Galois closure, say F. As F/K is normal, every K-automorphism of any extension of F will map F to itself; this was proved together with the part of the fundamental theorem concerning normal subgroups of the Galois group and normal extensions. Therefore, a K-automorphism of L is completely determined by the automorphisms it induces on each finite Galois extension F/K.

Finally, to see that Gal(L/K) is the inverse limit of Gal(F/K) over all intermediate F, note that given a tower of Galois extensions L/F/E/K, the map from Gal(L/K) to Gal(E/K) is fairly obviously the same as the map from Gal(L/K) to Gal(F/K) composed with the one from Gal(F/K) to Gal(E/K).

Here is where the standard Galois correspondence breaks down. To see why, let K = F(p) for any p, and L be the union of F(p^(q^n)) over all n; then Gal(L/K) is Z(q). The group Z(q) is uncountable and so has uncountably many subgroups, but L/K only has one proper intermediate extension for each integer n.

It’s necessary to view the projective limit as not just a group but also the inverse system it’s based on and the homomorphisms to each of the groups in the system. In this view, a subgroup must come from the groups in the system. More precisely, a sub-projective limit of G(i) arises as the projective limit of a collection of subgroups H(i) such that f(ij)(H(j)) = H(i). That will correspond to a field generated by the fixed fields of all H(i)’s.

Conversely, let F be an intermediate extension of L/K. Then F intersects every finite Galois extension in some finite intermediate extension, yielding a corresponding sub-projective limit. These two correspondences are inverses of each other by the fundamental theorem of (finite) Galois theory. Further, the sub-projective limit defined by H(i) is a normal subgroup iff each H(i) is normal in G(i), so the second part of the fundamental theorem holds as well.

Obviously, L/F is finite iff the sub-projective limit is a finite group, and F/K is finite iff the sub-projective limit has finite index in the projective limit. In the latter case, F is contained in some finite Galois extension, so it arises from a single H(i); then for all j with i <– j, H(j) is the preimage of H(i) in G(j), and for all k <– j, H(k) = f(kj)(H(j)). Conversely, a sub-projective limit that arises from a single H(i) this way has the property every g in the inverse limit that maps into H(i) in G(i) maps into the preimage of H(i) in each G(j) with i <– j, so that it’s in the sub-projective limit; the sub-projective limit is then the inverse image of H(i) in the projective limit, so its index in the projective limit is [G(i):H(i)], which is finite.


Galois Theory: The Primitive Element Theorem

March 5, 2007

The fundamental theorem of Galois theory immediately implies several nifty results about Galois extensions, which with a little work extend to a greater class of extensions, typically separable extensions. Here I will show that every separable extension L/K admits a primitive element, that is an element a of L such that L = K(a).

First, the normal closure of a separable extension is itself separable. To see why, recall that the normal closure of L/K is the splitting field of all the minimal polynomials of the elements of L. L/K is separable, so each a in L is separable over K; but separability is a property of the minimal polynomial of the element, so all other roots of m(a) are separable, and the normal closure is generated by separable elements.

In addition, the normal closure of a finite extension is finite, since if {a1, …, a(n)} is a basis for L over K, then it’s enough to take the splitting field of the finite set of polynomials m(a(i)).

Second, since the intermediate fields of a Galois extension correspond to subgroups of a finite group, there are only finitely many intermediate fields. This property then extends to extensions that are merely separable, since if M/L/K is a tower of extensions then every intermediate field of L/K is intermediate between M and K.

And third, an element not contained in any proper intermediate field is primitive, because K(a) is an intermediate field strictly containing K for a not in K. If K is finite and L has p^n elements, then just take one of the roots of the polynomial x^(p^(n – 1)) – 1, which will generate all the others. Otherwise, note that every proper intermediate field is a proper subspace of L, and no finite vector space over an infinite field can be covered by finitely many proper subspaces.

Proving that last assertion is an induction argument on the dimension of the vector space K^n. If n = 1, then a proper subspace is the trivial subspace consisting only of the origin, so the theorem obviously holds. If n = 2, then a non-trivial proper subspace is a line generated by scalar multiples of some point (a, b). No line can contain two points of the form (1, a) because then it will necessarily contain (0, ab), hence (0, 1), (0, a), (1, 0), and finally the entire space. But K is infinite so there are infinitely many points of that form, proving the theorem for n = 2.

More generally, suppose the theorem is true for all dimensions less than n. It’s enough to find a proper subspace of dimension n – 1 in K^n that isn’t contained in any of the proper subspaces we’re covering the space by; by a dimension argument, this is equivalent to showing the subspace of dimension n – 1 isn’t one of those proper subspaces. So it suffices to show that there are infinitely many subspaces of dimension n – 1.

But if a and b are distinct, then the subspaces spanned by {(1, 0, 0, …, 0), (0, 1, 0, …, 0), (0, 0, 1, …, 0), …, (0, …, 1, 0, 0), (0, …, 0, 1, a)} and {(1, 0, 0, …, 0), (0, 1, 0, …, 0), (0, 0, 1, …, 0), …, (0, …, 1, 0, 0), (0, …, 0, 1, b)} are distinct, by a similar argument to the one that works for K^2. That’s enough to prove the theorem.


Galois Theory: Examples of Galois Groups

March 1, 2007

Armed with the fundamental theorem of Galois theory, the aspiring mathematician can now go and compute Galois groups of some easy extensions.

Example #1: K = Q, L = Q(SQRT(n)) for any squarefree integer n. The minimal polynomial of SQRT(n) is x^2 – n; L is obviously normal over K, so it’s Galois and the fundamental theorem applies. The degree of L over K is 2, so Gal(L/K) has order 2. There is only one group of size 2, Z/2Z. That group has only two subgroups, the improper subgroup consisting of the entire group and the trivial subgroup consisting of the identity element 0. The non-identity element of the Galois group is the automorphism sending a + bSQRT(n) to abSQRT(n).

Example #2: K = R, L = C. As with example #1, this is a quadratic extension with minimal polynomial x^2 + 1, so Gal(L/K) = Z/2Z.

Example #3: K = Q, L = Q(2^(1/3), w) where w is a primitive cube root of unity. This is simply the splitting field of x^3 – 2 over Q, since the three roots are 2^(1/3), 2^(1/3)w, and 2^(1/3)w^2. The degree of the extension must divide 6 = 3! since 3 is the degree of the polynomial it’s a splitting field of; it must also be divisible by 2 since [Q(w):Q] = 2 and by 3 since [Q(2^(1/3)):Q] = 3.

There are only two groups of size 6, Z/6Z and S(3), the group of permutations of three elements. If Gal(L/K) = Z/6Z, then every subgroup of Gal(L/K) is normal since it is abelian; therefore, every intermediate field is normal, contradicting the fact that Q(2^(1/3))/Q is not normal. So Gal(L/K) = S(3). The elements of S(3) can be written in disjoint cycle notation as {(1), (1 2), (1 3), (2 3), (1 2 3), (1 3 2)}; then the proper nontrivial subgroups are generated by (1 2), (1 3), (2 3), and (1 2 3).

Assigning 1 to 2^(1/3), 2 to 2^(1/3)w, and 3 to 2^(1/3)w^2, we get that (1 2) fixes Q(2^(1/3)w^2), (1 3) fixes Q(2^(1/3)w), (2 3) fixes Q(2^(1/3)), and (1 2 3) and (1 3 2) fix Q(w). The only one of the four that is normal is Q(w), corresponding to the fact that {(1), (1 2 3), (1 3 2)} is the only proper nontrivial normal subgroup S(3).

Example #4: K = Q, L = Q(2^(1/4), i) where i is the imaginary unit. This is the splitting field of x^4 – 2, which has degree divisible by 4 and dividing 8. To see that it has degree 8, it’s enough to prove that x^4 – 2 is irreducible over Q(i). But it has no root in Q(i) by taking norms, so it has no linear factor. If it has two quadratic factors, then they can be written as x^2 + ax + b and x^2 – ax – 2/b; equating x-coefficients gives a(2/b + b) = 0, i.e. a(2 + b^2) = 0, so a = 0 since x^2 + 2 has no root in Q(i). But then equating x^2-coefficients yields b = -(2/b), i.e. 2 + b^2 = 0, a contradiction.

There are five groups of size 8: Z/8Z, Z/4Z * Z/2Z, Z/2Z * Z/2Z * Z/2Z, Q(8), and D(4). D(n) is the group of symmetries of a regular polygon with n sizes, where D(3) = S(3); note that notations vary, and some people write what I call D(n) as D(2n). Q(8) = \{\pm1, \pm i, \pm j, \pm k\} where i^{2} = j^{2} = k^{2} = ijk = -1; although it is not abelian, all of its subgroups are normal. But L/K has the non-normal intermediate field Q(2^(1/4)), so Gal(L/K) = D(4).

Example #5: L and K are finite fields (classified here), with K = F(p) and L = F(p^n). L is the splitting field for x^(p^n) – x over K, and K is a perfect field, so L/K is Galois. Hence, Gal(L/K) has size equal to [L:K] = n. In fact, it’s isomorphic to Z/nZ, generated by the Frobenius automorphism, which sends each a to a^p.

To see that the Frobenius automorphism f generates Gal(L/K), consider its fixed field. The fixed field contains K, obviously. In addition, a^p = a iff a is a root of the polynomial x^px; the p elements of K are then the roots of the polynomial, so L^{f} = K. Now, consider the subgroup of Gal(L/K) consisting of powers of f. Its fixed field is clearly K, so it must be the improper subgroup Gal(L/K); hence, f indeed generates Gal(L/K).

The group Z/nZ has one subgroup per divisor of n. The subgroup whose size is the divisor d is generated by n/d, so its fixed field is the set of all roots of x^(p^(n/d)) – x in L. But that’s just F(p^(n/d)), confirming that L/K has one intermediate field for each divisor of [L:K]. Note that this also solves the case of the extension L/K where K is any finite field; if K = F(p^m), then Gal(L/K) is generated by the largest subgroup of L/F(p) fixing K, i.e. by the automorphism that sends a to a^(p^m).


Visualizing Math

February 28, 2007

Lynet writes about how she tried explaining the PoincarĂ© Conjecture to a literary theorist and a historian. The bone of contention wasn’t really the conjecture, which the media dumbed down just enough so that non-mathematicians could understand a statement vaguely resembling what Perelman actually proved. Rather, it was how mathematicians could visualize a four-dimensional world.

“Can mathematicians actually picture four dimensional space?”

“Roger Penrose says he did it – briefly – once,” I said, grinning [1].

“No, but are there people out there who can actually…”

“Not that I know of.”

My historian friend was relieved. My literary theorist friend was confused. “If you can’t picture it,” he asked, “how could you have any intuition about it? I mean, you could just say whatever you wanted about it and no-one would be able to refute you.”

I’ll leave it up to you to make an appropriate snarky comment about literary theorists. I’d reply to Lynet’s friend by noting that at least the simpler intuitions, namely, those relating to the vector space structure, are easily generalizable.

I can view points in the plane as pairs of coordinates (x, y), and work out things like angles between lines, lengths of lines, tangent lines to curves, functions on the plane, and so on. Regarding the point (x, y) as a vector from (0, 0) to (x, y), I can add vectors pointwise by (x1, y1) + (x2, y2) = (x1 + x2, y1 + y2) and multiply them by scalars by k(x, y) = (kx, ky). I can look at linear transformations of the plane, or even affine transformations.

All of those are intuitively thought of using very concrete notions: length and angle are measurable concepts; tangent lines touch curves at only one point; vector addition consists of walking from (0, 0) to (x1, y1) and then along the same direction and for the same distance as from (0, 0) to (x2, y2); linear transformations are combinations of rotations, reflections, shears, stretches, and compressions, while affine transformations add translations.

But in higher mathematics, they’re considered abstractly, in order to generalize as much as possible. Length is defined using Pythagoras’s theorem, and angle is defined using inner products. Linear transformations are defined by the more easily generalized property that T(v1 + v2) = T(v1) + T(v2) and T(kv) = kT(v), which coincides with the more concrete definition in two dimensions.

Not coincidentally, for two or three years of university, students only ever see algebraic arguments, which don’t involve visualizing anything. Later some geometric aspects return, but even they are typically schematic; people who draw a line with a loop in it in algebraic geometry only look at very general aspects, like having a point with two tangent lines and not being decomposable into two lines.


The Carnival of Mathematics #2 is Up

February 23, 2007

Two weeks ago, I put up a carnival with posts from slightly more than 10 different people. Now Mark Chu-Carroll has posted his edition of the Carnival of Mathematics, with 27 different posters and a fitting theme.

Next edition will be posted on March 9th on Michi’s blog. Send your submissions to Michi at mikael@johanssons.org, or to me at alon_levy1@yahoo.com, or use the submission form.


Follow

Get every new post delivered to your Inbox.