Counting magic squares

How many k × k magic squares are possible? If you start from a liberal definition of magic square, there’s an elegant result. For the purposes of this post, a magic square is a square arrangement of non-negative numbers such that the rows and columns all sum to the same non-negative number m called the magic constant. Note that this allows the possibility that numbers will be repeated, and this places no restriction on the diagonals.

With this admittedly non-standard definition, the number of k × k magic squares with magic constant m is always a polynomial in m of degree no more than (k – 1)2. For k = 3, the result is

(m + 1)(m + 2)(m2 + 3m + 4)/8

There is no general formula for all k, but there is an algorithm for finding a formula for each value of k.

Source: The Concrete Tetrahedron

Update: I had reported the polynomial degree as k + 1, but looking back at Concrete Tetrahedron, that book lists the order as (k + 1)2. However, the paper cited in the comments lists the exponent as (k – 1)2, which I believe is correct.

Related posts:

Bad science is tolerable, résumé padding is not

The Economist posted an article online this weekend about the scandal over irreproducible cancer research by Anil Potti. My colleagues Keith Baggerly and Kevin Coombes have been crying foul about this since 2007. I first blogged about it in January 2008.

The story started getting wide-spread attention last summer when the Cancer Letter reported that Dr. Potti had lied on grant applications. Since then there have been articles in the popular press, and people are staring to file lawsuits.

Apparently the tipping point in the story was finding a fib on Potti’s resume. According to The Economist

He falsely claimed to have been a Rhodes Scholar in Australia (a curious claim in any case, since Rhodes scholars only attend Oxford University).

So what finally got people to pay attention was not accusations of incompetent or fraudulent science, but résumé padding. As Keith Baggerly commented,

I find it ironic that we have been yelling for three years about the science, which has the potential to be very damaging to patients, but that was not what has started things rolling.

Related posts:

Five interesting things about Mersenne primes

A Mersenne prime is a prime number that is one less than a power of 2. These primes are indexed by the corresponding power of two, i.e. Mp = 2p – 1. It turns out p must be prime before 2p – 1 can be prime.

Here are five things I find interesting about Mersenne primes.

1. Record size primes

The largest known prime number is a Mersenne prime, M43,112,609, proved prime in 2008. And ever since M521 was proven prime in 1952, the largest known prime has always been a Mersenne prime (with one exception in 1989). See a history of prime number records.

One reason for the prevalence of Mersenne primes in the record books is that there is a special algorithm for testing whether a number of the form 2p – 1 is prime, the Lucas-Lehmer test.

Update: A new prime record was set in 2016. The largest known prime is still a Mersenne prime, now M74,207,281.

2. Finiteness

There may only be a finite number of Mersenne primes. Only 47 are known so far. There are conjectures that predict there are an infinite number of Mersenne primes, but these have not been settled.

3. Connection with perfect numbers

Euclid proved that if M is a Mersenne prime, M(M+1)/2 is a perfect number. Two millennia later, Euler proved that if N is an even perfect number, N must be of the form M(M+1)/2 where M is a Mersenne prime. (More details here.)

Since we only know of 47 Mersenne primes at the moment, and we don’t know of any odd perfect numbers, there are only 47 known perfect numbers.

4. Connection with random number generation

The Mersenne twister is a popular, high-quality random number generator. The generator is so named because its period is a Mersenne prime, M19,937.

5. History

Mersenne primes are named after the French monk Marin Mersenne (1588–1648) who compiled a list of Mersenne primes. Mersenne wasn’t the first to be aware of such primes. As mentioned above, Euclid connected these primes with perfect numbers.

Marin Mersenne is one of my academic ancestors. I studied under Ralph Showalter, who studied under Tsuan Ting, and so forth back to Frans van Shooten Jr., who studied under Marin Mersenne.

What I find fascinating about this is not my particular genealogy, but that adequate records exist to construct such genealogies. The Mathematics Genealogy Project has over 150,000 records, some reaching back to the Middle Ages.


Normal subgroups are not transitive

The property “is a normal subgroup of” is not transitive.

If A is a subgroup of B, and B is a subgroup of C, then A is a subgroup of C. But the corresponding statement about normal subgroups is false. And there’s a simple example that shows it is false.

We need to find a group C with subgroups A and B such that A is normal in B, B is normal in C, but A is not normal in C.

The subgroup A must have at least two elements, otherwise A would just be the group identity and would then be a normal subgroup of C. The order of a subgroup divides the order of the group, so B must have at least twice as many elements as A, and C must have twice as many elements as B. So the smallest possible example would be a group with 8 elements and subgroups of order 2 and 4.

We’re in luck, because there’s a group of order 8 that will work, D8. This is the group of symmetries of a square under flips and rotations. Let A be the subgroup of flips about the vertical axis of symmetry. Let B the symmetries you can find by combinations of such flips and 180 degree rotations. You can show that A is normal in B, and B is normal in C.

Now let c be a 90 degree clockwise turn and let a be a flip. You can show that cac-1 is not a flip or the identity, so A is not a normal subgroup of C.

Related post: A 3,000 page proof (classification of finite simple groups)

For daily tweets on algebra and other math, follow @AlgebraFact on Twitter.

AlgebraFact logo

Bastrop wildfire

Smoke from the wildfires in Bastrop, Texas.

Photo by Kerri West. Full-sized image here. More Bastrop photos by Kerri West here.

At least two people have died in the fires and many have lost their homes.

I’ve taken my daughters a couple times to a father-daughter retreat at Wilderness Ridge Camp near Bastrop. That camp has been completely destroyed by the fires.

Anti-calculus proposition of Erdős

The “anti-calculus proposition” is a little result by Paul Erdős that contrasts functions of a real variable and functions of a complex variable.

A standard calculus result says the derivative of a function is zero where the function takes on its maximum. The anti-calculus proposition says that for analytic functions, the derivative cannot be zero at the maximum.

To be more precise, a differentiable real-valued function on a closed interval takes on its maximum where the derivative is zero or at one of the ends. It’s possible that the maximum occurs at one of the ends of the interval and the derivative is zero there.

The anti-calculus proposition says that the analogous situation cannot occur for functions of a complex variable. Suppose a function f is analytic on a closed disk and suppose that f is not constant. Then |f| must take on its maximum somewhere on the boundary by the maximum modulus theorem. Erdős’ anti-calculus proposition adds that at the point on the boundary where |f| takes on its maximum, the derivative cannot be zero.

Related posts:

Bayes isn’t magic

If a study is completely infeasible using traditional statistical methods, Bayesian methods are probably not going to rescue it. Bayesian methods can’t squeeze blood out of a turnip.

The Bayesian approach to statistics has real advantages, but sometimes these advantages are oversold. Bayesian statistics is still statistics, not magic.

Click to learn more about Bayesian statistics consulting

Intolerant anarchists

From Jaron Lanier:

Even in the places that are called anarchistic, in fact, what happens is a new kind of order, which is often very oppressive if you don’t happen to fit in. In San Francisco you can be attacked by mobs of bicycling advocates who’ve occasionally been quite ruthless because they believe in bicycles, and they think that they’re the most enlightened, free people in the world, and yet if somebody doesn’t agree with them, then they have trouble.

Similarly, Burning Man, which people who fit in at Burning Man must perceive is the most open, accepting place in the world is, in fact, extraordinarily unaccepting of people who don’t conform.

Loving your literal neighbor

It’s one thing to love your neighbor in the abstract. It’s quite another to love your literal neighbor.

As G. K. Chesterton explains:

We make our friends; we make our enemies; but God makes our next-door neighbor. … The duty towards humanity may often take the form of some choice which is personal or even pleasurable. That duty may be a hobby … We may be made as to be particularly fond of lunatics or specially interested in leprosy … But we have to love our neighbor because he is there — a much more alarming reason for a much more serious operation. He is the sample of humanity actually given us.

Quote found in From the Library of C. S. Lewis

Willie Sutton and the multivariate normal distribution

When asked why he robbed banks, Willie Sutton famously replied “Because that’s where the money is.”

If you read about data analysis in high dimensions, you might hear someone say they’re focused on a thin shell because that’s where the probability is. For a multivariate normal distribution in high dimensions, nearly all the probability mass is concentrated in a thin shell some distance away from the origin.

What does that mean? Why is it true? How thin is the shell and what is its radius?

It seems absurd to say the probability is concentrated in a shell. The multivariate normal density has its greatest value at the origin and quickly decays as you move out in any direction. So most of the probability must be near the origin, right? No, because mass equals density times volume. The density decays quickly as you move away from the origin, but volume increases quickly. The product of the two is greatest at some radius away from the origin. That’s the shell.

The volume of a sphere in d dimensions is proportional to rd, so volume increases very quickly if d is large. For example, if d = 100, how much of the volume of a unit sphere is between a distance of 0.99 and 1 from the origin? Since 1100 – 0.99100 = 0.634, this says 63.4% of the volume is in the outer shell of thickness 0.01.

Since volume of a sphere is proportional to rd, the volume of a shell of radius r and thickness Δr is roughly proportional to d rd-1 Δr. When you multiply that volume by the probability density exp( –r2 / 2 ) you get that the probability mass in the shell is proportional to

rd-1 exp( –r2 / 2 ) Δr.

This leads to a χ distribution with d degrees of freedom. (Not the better known χ2 distribution.) This distribution has mode √(d-1) and variance 1. For large d, the distribution is approximately normal. So a multivariate normal in d dimensions with d large has roughly 95% of its probability mass in a shell of radius √d with thickness 4, two standard deviations either side of √d. (I’m approximating anyway, so I approximated √(d-1) as √d to make the conclusion a little simpler.)

The graph below gives the probability density of shells as a function of radius in dimensions 10 and 100.

Related post: Volumes of Lp unit balls