I need to get back to just talking about mathematics problems some. Happily there was some news come across my desk. It’s about the Travelling Salesman Problem. This is one of those classic problems, simple to state and obviously interesting, and that are terribly hard to solve. How do you draw a path connecting a large number of points with the shortest total path? You can recast what you’re doing: make the path that takes the shortest time, or that has the lowest cost, the least energy, the greatest profit, whatever. Optimization problems are very alike, and useful.
There’s not many good answers to the problem, though. Basically, test out every possible combination and pick the best one from all that. For large enough problems this is hopeless. For small enough problems, though? You can work something out. So there’s this report of researchers, lead by Professor Takayuki Kawahara at the Tokyo University of Science. They’ve developed an integrated circuit with really good performance for, they believe, up to 22 ‘cities’. That 22 is a breakthrough tells you something of how hard the problems are.
I’m unclear, from the press release, just how the system works. (I’m also unsure, from reading the press releases, that they have actually used this for 22 cities or whether they have good reason to think it will work as hoped for. I may be over-parsing.) There’s a description of using “spin cells” and it happens I know about something named spin cells. And that they are used in optimization problems. What I do not know is that my spin cells are the spin cells being used here. If I find out, I’ll share.
I never heard of today’s entry topic three months ago. Indeed, three weeks ago I was still making guesses about just what Gaurish, author of For the love of Mathematics,, was asking about. It turns out to be maybe the grand union of everything that’s ever been in one of my A To Z sequences. I overstate, but barely.
The specific thing that a Young Tableau is is beautiful in its simplicity. It could almost be a recreational mathematics puzzle, except that it isn’t challenging enough.
Start with a couple of boxes laid in a row. As many or as few as you like.
Now set another row of boxes. You can have as many as the first row did, or fewer. You just can’t have more. Set the second row of boxes — well, your choice. Either below the first row, or else above. I’m going to assume you’re going below the first row, and will write my directions accordingly. If you do things the other way you’re following a common enough convention. I’m leaving it on you to figure out what the directions should be, though.
Now add in a third row of boxes, if you like. Again, as many or as few boxes as you like. There can’t be more than there are in the second row. Set it below the second row.
And a fourth row, if you want four rows. Again, no more boxes in it than the third row had. Keep this up until you’ve got tired of adding rows of boxes.
How many boxes do you have? I don’t know. But take the numbers 1, 2, 3, 4, 5, and so on, up to whatever the count of your boxes is. Can you fill in one number for each box? So that the numbers are always increasing as you go left to right in a single row? And as you go top to bottom in a single column? Yes, of course. Go in order: ‘1’ for the first box you laid down, then ‘2’, then ‘3’, and so on, increasing up to the last box in the last row.
Can you do it in another way? Any other order?
Except for the simplest of arrangements, like a single row of four boxes or three rows of one box atop another, the answer is yes. There can be many of them, turns out. Seven boxes, arranged three in the first row, two in the second, one in the third, and one in the fourth, have 35 possible arrangements. It doesn’t take a very big diagram to get an enormous number of possibilities. Could be fun drawing an arbitrary stack of boxes and working out how many arrangements there are, if you have some time in a dull meeting to pass.
Let me step away from filling boxes. In one of its later, disappointing, seasons Futurama finally did a body-swap episode. The gimmick: two bodies could only swap the brains within them one time. So would it be possible to put Bender’s brain back in his original body, if he and Amy (or whoever) had already swapped once? The episode drew minor amusement in mathematics circles, and a lot of amazement in pop-culture circles. The writer, a mathematics major, found a proof that showed it was indeed always possible, even after many pairs of people had swapped bodies. The idea that a theorem was created for a TV show impressed many people who think theorems are rarer and harder to create than they necessarily are.
It was a legitimate theorem, and in a well-developed field of mathematics. It’s about permutation groups. These are the study of the ways you can swap pairs of things. I grant this doesn’t sound like much of a field. There is a surprising lot of interesting things to learn just from studying how stuff can be swapped, though. It’s even of real-world relevance. Most subatomic particles of a kind — electrons, top quarks, gluons, whatever — are identical to every other particle of the same kind. Physics wouldn’t work if they weren’t. What would happen if we swap the electron on the left for the electron on the right, and vice-versa? How would that change our physics?
A chunk of quantum mechanics studies what kinds of swaps of particles would produce an observable change, and what kind of swaps wouldn’t. When the swap doesn’t make a change we can describe this as a symmetric operation. When the swap does make a change, that’s an antisymmetric operation. And — the Young Tableau that’s a single row of two boxes? That matches up well with this symmetric operation. The Young Tableau that’s two rows of a single box each? That matches up with the antisymmetric operation.
How many ways could you set up three boxes, according to the rules of the game? A single row of three boxes, sure. One row of two boxes and a row of one box. Three rows of one box each. How many ways are there to assign the numbers 1, 2, and 3 to those boxes, and satisfy the rules? One way to do the single row of three boxes. Also one way to do the three rows of a single box. There’s two ways to do the one-row-of-two-boxes, one-row-of-one-box case.
What if we have three particles? How could they interact? Well, all three could be symmetric with each other. This matches the first case, the single row of three boxes. All three could be antisymmetric with each other. This matches the three rows of one box. Or you could have two particles that are symmetric with each other and antisymmetric with the third particle. Or two particles that are antisymmetric with each other but symmetric with the third particle. Two ways to do that. Two ways to fill in the one-row-of-two-boxes, one-row-of-one-box case.
This isn’t merely a neat, aesthetically interesting coincidence. I wouldn’t spend so much time on it if it were. There’s a matching here that’s built on something meaningful. The different ways to arrange numbers in a set of boxes like this pair up with a select, interesting set of matrices whose elements are complex-valued numbers. You might wonder who introduced complex-valued numbers, let alone matrices of them, into evidence. Well, who cares? We’ve got them. They do a lot of work for us. So much work they have a common name, the “symmetric group over the complex numbers”. As my leading example suggests, they’re all over the place in quantum mechanics. They’re good to have around in regular physics too, at least in the right neighborhoods.
These Young Tableaus turn up over and over in group theory. They match up with polynomials, because yeah, everything is polynomials. But they turn out to describe polynomial representations of some of the superstar groups out there. Groups with names like the General Linear Group (square matrices), or the Special Linear Group (square matrices with determinant equal to 1), or the Special Unitary Group (that thing where quantum mechanics says there have to be particles whose names are obscure Greek letters with superscripts of up to five + marks). If you’d care for more, here’s a chapter by Dr Frank Porter describing, in part, how you get from Young Tableaus to the obscure baryons.
Porter’s chapter also lets me tie this back to tensors. Tensors have varied ranks, the number of different indicies you can have on the things. What happens when you swap pairs of indices in a tensor? How many ways can you swap them, and what does that do to what the tensor describes? Please tell me you already suspect this is going to match something in Young Tableaus. They do this by way of the symmetries and permutations mentioned above. But they are there.
As I say, three months ago I had no idea these things existed. If I ever ran across them it was from seeing the name at MathWorld’s list of terms that start with ‘Y’. The article shows some nice examples (with each rows a atop the previous one) but doesn’t make clear how much stuff this subject runs through. I can’t fit everything in to a reasonable essay. (For example: the number of ways to arrange, say, 20 boxes into rows meeting these rules is itself a partition problem. Partition problems are probability and statistical mechanics. Statistical mechanics is the flow of heat, and the movement of the stars in a galaxy, and the chemistry of life.) I am delighted by what does fit.
I have two pieces to assemble for this. One is in factors. We can take any counting number, a positive whole number, and write it as the product of prime numbers. 2038 is equal to the prime 2 times the prime 1019. 4312 is equal to 2 raised to the third power times 7 raised to the second times 11. 1040 is 2 to the fourth power times 5 times 13. 455 is 5 times 7 times 13.
There are many ways to divide up numbers like this. Here’s one. Is there a square number among its factors? 2038 and 455 don’t have any. They’re each a product of prime numbers that are never repeated. 1040 has a square among its factors. 2 times 2 divides into 1040. 4312, similarly, has a square: we can write it as 2 squared times 2 times 7 squared times 11. So that is my first piece. We can divide counting numbers into squarefree and not-squarefree.
The other piece is in binomial coefficients. These are numbers, often quite big numbers, that get dumped on the high school algebra student as she tries to work with some expression like . They’re also dumped on the poor student in calculus, as something about Newton’s binomial coefficient theorem. Which we hear is something really important. In my experience it wasn’t explained why this should rank up there with, like, the differential calculus. (Spoiler: it’s because of polynomials.) But it’s got some great stuff to it.
Binomial coefficients are among those utility players in mathematics. They turn up in weird places. In dealing with polynomials, of course. They also turn up in combinatorics, and through that, probability. If you run, for example, 10 experiments each of which could succeed or fail, the chance you’ll get exactly five successes is going to be proportional to one of these binomial coefficients. That they touch on polynomials and probability is a sign we’re looking at a thing woven into the whole universe of mathematics. We saw them some in talking, last A-To-Z around, about Yang Hui’s Triangle. That’s also known as Pascal’s Triangle. It has more names too, since it’s been found many times over.
The theorem under discussion is about central binomial coefficients. These are one specific coefficient in a row. The ones that appear, in the triangle, along the line of symmetry. They’re easy to describe in formulas. for a whole number ‘n’ that’s greater than or equal to zero, evaluate what we call 2n choose n:
If ‘n’ is zero, this number is or 1. If ‘n’ is 1, this number is or 2. If ‘n’ is 2, this number is 6. If ‘n’ is 3, this number is (sparing the formula) 20. The numbers keep growing. 70, 252, 924, 3432, 12870, and so on.
So. 1 and 2 and 6 are squarefree numbers. Not much arguing that. But 20? That’s 2 squared times 5. 70? 2 times 5 times 7. 252? 2 squared times 3 squared times 7. 924? That’s 2 squared times 3 times 7 times 11. 3432? 2 cubed times 3 times 11 times 13; there’s a 2 squared in there. 12870? 2 times 3 squared times it doesn’t matter anymore. It’s not a squarefree number.
There’s a bunch of not-squarefree numbers in there. The question: do we ever stop seeing squarefree numbers here?
So here’s Sárközy’s Theorem. It says that this central binomial coefficient is never squarefree as long as ‘n’ is big enough. András Sárközy showed in 1985 that this was true. How big is big enough? … We have a bound, at least, for this theorem. If ‘n’ is larger than the number then the corresponding coefficient can’t be squarefree. It might not surprise you that the formulas involved here feature the Riemann Zeta function. That always seems to turn up for questions about large prime numbers.
That’s a common state of affairs for number theory problems. Very often we can show that something is true for big enough numbers. I’m not sure there’s a clear reason why. When numbers get large enough it can be more convenient to deal with their logarithms, I suppose. And those look more like the real numbers than the integers. And real numbers are typically easier to prove stuff about. Maybe that’s it. This is vague, yes. But to ask ‘why’ some things are easy and some are hard to prove is a hard question. What is a satisfying ’cause’ here?
It’s tempting to say that since we know this is true for all ‘n’ above a bound, we’re done. We can just test all the numbers below that bound, and the rest is done. You can do a satisfying proof this way: show that eventually the statement is true, and show all the special little cases before it is. This particular result is kind of useless, though. is a number that’s something like 241 digits long. For comparison, the total number of things in the universe is something like a number about 80 digits long. Certainly not more than 90. It’d take too long to test all those cases.
That’s all right. Since Sárközy’s proof in 1985 there’ve been other breakthroughs. In 1988 P Goetgheluck proved it was true for a big range of numbers: every ‘n’ that’s larger than 4 and less than . That’s a number something more than 12 million digits long. In 1991 I Vardi proved we had no squarefree central binomial coefficients for ‘n’ greater than 4 and less than , which is a number about 233 million digits long. And then in 1996 Andrew Granville and Olivier Ramare showed directly that this was so for all ‘n’ larger than 4.
So that 70 that turned up just a few lines in is the last squarefree one of these coefficients.
Is this surprising? Maybe, maybe not. I’ll bet most of you didn’t have an opinion on this topic twenty minutes ago. Let me share something that did surprise me, and continues to surprise me. In 1974 David Singmaster proved that any integer divides almost all the binomial coefficients out there. “Almost all” is here a term of art, but it means just about what you’d expect. Imagine the giant list of all the numbers that can be binomial coefficients. Then pick any positive integer you like. The number you picked will divide into so many of the giant list that the exceptions won’t be noticeable. So that square numbers like 4 and 9 and 16 and 25 should divide into most binomial coefficients? … That’s to be expected, suddenly. Into the central binomial coefficients? That’s not so obvious to me. But then so much of number theory is strange and surprising and not so obvious.
So for all I worried about the Gocomics.com redesign it’s not bad. The biggest change is it’s removed a side panel and given the space over to the comics. And while it does show comics you haven’t been reading, it only shows one per day. One week in it apparently sticks with the same comic unless you choose to dismiss that. So I’ve had it showing me The Comic Strip That Has A Finale Every Day as a strip I’m not “reading”. I’m delighted how thisbreaks the logic about what it means to “not read” an “ongoing comic strip”. (That strip was a Super-Fun-Pak Comix offering, as part of Ruben Bolling’s Tom the Dancing Bug. It was turned into a regular Gocomics.com feature by someone who got the joke.)
Comic Strip Master Command responded to the change by sending out a lot of comic strips. I’m going to have to divide this week’s entry into two pieces. There’s not deep things to say about most of these comics, but I’ll make do, surely.
Julie Larson’s Dinette Set rerun for the 8th is about one of the great uses of combinatorics. That use is working out how the number of possible things compares to the number of things there are. What’s always staggering is that the number of possible things grows so very very fast. Here one of Larson’s characters claims a science-type show made an assertion about the number of possible ideas a brain could hold. I don’t know if that’s inspired by some actual bit of pop science. I can imagine someone trying to estimate the number of possible states a brain might have.
And that has to be larger than the number of atoms in the universe. Consider: there’s something less than a googol of atoms in the universe. But a person can certainly have the idea of the number 1, or the idea of the number 2, or the idea of the number 3, or so on. I admit a certain sameness seems to exist between the ideas of the numbers 2,038,412,562,593,604 and 2,038,412,582,593,604. But there is a difference. We can out-number the atoms in the universe even before we consider ideas like rabbits or liberal democracy or jellybeans or board games. The universe never had a chance.
Or did it? Is it possible for a number to be too big for the human brain to ponder? If there are more digits in the number than there are atoms in the universe we can’t form any discrete representation of it, after all. … Except that we kind of can. For example, “the largest prime number less than one googolplex” is perfectly understandable. We can’t write it out in digits, I think. But you now have thought of that number, and while you may not know what its millionth decimal digit is, you also have no reason to care what that digit is. This is stepping into the troubled waters of algorithmic complexity.
Bob Weber Jr’s Slylock Fox and Comics for Kids for the 9th of January, 2017. Not sure why Shady Shrew is selling the circular wands at 50 cents. Sure, I understand wanting a triangle or star or other wand selling at a premium. But then why have the circular wands at such a cheap price? Wouldn’t it be better to put them at like six dollars, so that eight dollars for a fancy wand doesn’t seem that great an extravagance? You have to consider setting an appropriate anchor point for your customer base. But, then, Shady Shrew isn’t supposed to be that smart.
Bob Weber Jr’s Slylock Fox and Comics for Kids for the 9th is built on soap bubbles. The link between the wand and the soap bubble vanishes quickly once the bubble breaks loose of the wand. But soap films that keep adhered to the wand or mesh can be quite strangely shaped. Soap films are a practical example of a kind of partial differential equations problem. Partial differential equations often appear when we want to talk about shapes and surfaces and materials that tug or deform the material near them. The shape of a soap bubble will be the one that minimizes the torsion stresses of the bubble’s surface. It’s a challenge to solve analytically. It’s still a good challenge to solve numerically. But you can do that most wonderful of things and solve a differential equation experimentally, if you must. It’s old-fashioned. The computer tools to do this have gotten so common it’s hard to justify going to the engineering lab and getting soapy water all over a mathematician’s fingers. But the option is there.
Gordon Bess’s Redeye rerun from the 28th of August, 1970, is one of a string of confused-student jokes. (The strip had a Generic Comedic Western Indian setting, putting it in the vein of Hagar the Horrible and other comic-anachronism comics.) But I wonder if there are kids baffled by numbers getting made several different ways. Experience with recipes and assembly instructions and the like might train someone to thinking there’s one correct way to make something. That could build a bad intuition about what additions can work.
Gordon Bess’s Redeye rerun from the 28th of August, 1970. Reprinted the 9th of January, 2017. What makes the strip work is how it’s tied to the personalities of these kids and couldn’t be transplanted into every other comic strip with two kids in it.
Corey Pandolph’s Barkeater Lake rerun for the 9th just name-drops algebra. And that as a word that starts with the “alj” sound. So far as I’m aware there’s not a clear etymological link between Algeria and algebra, despite both being modified Arabic words. Algebra comes from “al-jabr”, about reuniting broken things. Algeria comes from Algiers, which Wikipedia says derives from `al-jaza’ir”, “the Islands [of the Mazghanna tribe]”.
Guy Gilchrist’s Nancy for the 9th is another mathematics-cameo strip. But it was also the first strip I ran across this week that mentioned mathematics and wasn’t a rerun. I’ll take it.
Donna A Lewis’s Reply All for the 9th has Lizzie accuse her boyfriend of cheating by using mathematics in Scrabble. He seems to just be counting tiles, though. I think Lizzie suspects something like Blackjack card-counting is going on. Since there are only so many of each letter available knowing just how many tiles remain could maybe offer some guidance how to play? But I don’t see how. In Blackjack a player gets to decide whether to take more cards or not. Counting cards can suggest whether it’s more likely or less likely that another card will make the player or dealer bust. Scrabble doesn’t offer that choice. One has to refill up to seven tiles until the tile bag hasn’t got enough left. Perhaps I’m overlooking something; I haven’t played much Scrabble since I was a kid.
Perhaps we can take the strip as portraying the folk belief that mathematicians get to know secret, barely-explainable advantages on ordinary folks. That itself reflects a folk belief that experts of any kind are endowed with vaguely cheating knowledge. I’ll admit being able to go up to a blackboard and write with confidence a bunch of integrals feels a bit like magic. This doesn’t help with Scrabble.
Gordon Bess’s Redeye rerun from the 29th of August, 1970. Reprinted the 10th of January, 2017. To be less snarky, I do like the simply-expressed weariness on the girl’s face. It’s hard to communicate feelings with few pen strokes.
Gordon Bess’s Redeye continued the confused-student thread on the 29th of August, 1970. This one’s a much older joke about resisting word problems.
Ryan North’s Dinosaur Comics rerun for the 10th talks about multiverses. If we allow there to be infinitely many possible universes that would suggest infinitely many different Shakespeares writing enormously many variations of everything. It’s an interesting variant on the monkeys-at-typewriters problem. I noticed how T-Rex put Shakespeare at typewriters too. That’ll have many of the same practical problems as monkeys-at-typewriters do, though. There’ll be a lot of variations that are just a few words or a trivial scene different from what we have, for example. Or there’ll be variants that are completely uninteresting, or so different we can barely recognize them as relevant. And that’s if it’s actually possible for there to be an alternate universe with Shakespeare writing his plays differently. That seems like it should be possible, but we lack evidence that it is.
. They’re also dumped on the poor student in calculus, as something about Newton’s binomial coefficient theorem. Which we hear is something really important. In my experience it wasn’t explained why this should rank up there with, like, the differential calculus. (Spoiler: it’s because of polynomials.) But it’s got some great stuff to it. 
or 1. If ‘n’ is 1, this number is 
or 2. If ‘n’ is 2, this number is 
6. If ‘n’ is 3, this number is (sparing the formula) 20. The numbers keep growing. 70, 252, 924, 3432, 12870, and so on. 
is never squarefree as long as ‘n’ is big enough. András Sárközy showed in 1985 that this was true. How big is big enough? … We have a bound, at least, for this theorem. If ‘n’ is larger than the number 
then the corresponding coefficient can’t be squarefree. It might not surprise you that the formulas involved here feature the Riemann Zeta function. That always seems to turn up for questions about large prime numbers. 
. That’s a number something more than 12 million digits long. In 1991 I Vardi proved we had no squarefree central binomial coefficients for ‘n’ greater than 4 and less than 
, which is a number about 233 million digits long. And then in 1996 Andrew Granville and Olivier Ramare showed directly that this was so for all ‘n’ larger than 4. 
nebusresearch 
