text:
## How Many Of This Weird Prime Are There?

A friend made me aware of a neat little unsolved problem in number theory. I know it seems like number theory is nothing but unsolved problems, but this is an unfair reputation. There are as many as four solved problems in number theory. It’s a tough field.

The question started with the observation that 11 is a prime number. And so is 101. But 1,001 is not; nor is 10,001. How many prime numbers are there that have the form $10^n + 1$, for whole-number values of n? Are there infinitely many? Finitely many? If there’s finitely many, how many are there?

It turns out this is an open question. We know of three prime numbers that you can write as $10^n + 1$. I’ll leave the third for you to find.

One neat bit is that if there are more $10^n + 1$ prime numbers, they have to be ones where n is itself a whole power of 2. That is, where the number is $10^{2^k} + 1$ for some whole number k. They’ve been tested up to $10^{16,777,216} + 1$ at least, so this subset of the Generalized Fermat Numbers seems to be rare. But wouldn’t it be just our luck if from $10^{16,777,217} + 1$ onward they were nothing but primes?

## My 2019 Mathematics A To Z: Relatively Prime

I have another subject nominated by goldenoj today. And it even lets me get into number theory, the field of mathematics questions that everybody understands and nobody can prove.

# Relatively Prime.

I was once a young grad student working as a teaching assistant and unaware of the principles of student privacy. Near the end of semesters I would e-mail students their grades. This so they could correct any mistakes and know what they’d have to get on the finals. I was learning Perl, which was an acceptable pastime in the 1990s. So I wrote scripts that would take my spreadsheet of grades and turn it into e-mails that were automatically sent. And then I got all fancy.

It seemed boring to send out completely identical form letters, even if any individual would see it once. Maybe twice if they got me for another class. So I started writing variants of the boilerplate sentences. My goal was that every student would get a mass-produced yet unique e-mail. To best the chances of this I had to make sure of something about all these variant sentences and paragraphs.

So you see the trick. I needed a set of relatively prime numbers. That way, it would be the greatest possible number of students before I had a completely repeated text. We know what prime numbers are. They’re the numbers that, in your field, have exactly two factors. In the counting numbers the primes are numbers like 2, 3, 5, 7 and so on. In the Gaussian integers, these are numbers like 3 and 7 and $3 - 2\imath$. But not 2 or 5. We can look to primes among the polynomials. Among polynomials with rational coefficients, $x^2 + x + 1$ is prime. So is $2x^2 + 14x + 1$. $x^2 - 4$ is not.

The idea of relative primes appears wherever primes appears. We can say without contradiction that 4 and 9 are relative primes, among the whole numbers. Though neither’s prime, in the whole numbers, neither has a prime factor in common. This is an obvious way to look at it. We can use that definition for any field that has a concept of primes. There are others, though. We can say two things are relatively prime if there’s a linear combination of them that adds to the identity element. You get a linear combination by multiplying each of the things by a scalar and adding these together. Multiply 4 by -2 and 9 by 1 and add them and look what you get. Or, if the least common multiple of a set of elements is equal to their product, then the elements are relatively prime. Some make sense only for the whole numbers. Imagine the first quadrant of a plane, marked in Cartesian coordinates. Draw the line segment connecting the point at (0, 0) and the point with coordinates (m, n). If that line segment touches no dots between (0, 0) and (m, n), then the whole numbers m and n are relatively prime.

We start looking at relative primes as pairs of things. We can be interested in larger sets of relative primes, though. My little e-mail generator, for example, wouldn’t work so well if any pair of sentence replacements were not relatively prime. So, like, the set of numbers 2, 6, 9 is relatively prime; all three numbers share no prime factors. But neither the pair 2, 6 and the pair 6, 9 are not relatively prime. 2, 9 is, at least there’s that. I forget how many replaceable sentences were in my form e-mails. I’m sure I did the cowardly thing, coming up with a prime number of alternate ways to phrase as many sentences as possible. As an undergraduate I covered the student government for four years’ worth of meetings. I learned a lot of ways to say the same thing.

Which is all right, but are relative primes important? Relative primes turn up all over the place in number theory, and in corners of group theory. There are some thing that are easier to calculate in modulo arithmetic if we have relatively prime numbers to work with. I know when I see modulo arithmetic I expect encryption schemes to follow close behind. Here I admit I’m ignorant whether these imply things which make encryption schemes easier or harder.

Some of the results are neat, certainly. Suppose that the function f is a polynomial. Then, if its first derivative f’ is relatively prime to f, it turns out f has no repeated roots. And vice-versa: if f has no repeated roots, then it and its first derivative are relatively prime. You remember repeated roots. They’re factors like $(x - 2)^2$, that foiled your attempt to test a couple points and figure roughly where a polynomial crossed the x-axis.

I mentioned that primeness depends on the field. This is true of relative primeness. Polynomials really show this off. (Here I’m using an example explained in a 2007 Ask Dr Math essay.) Is the polynomial $3x + 6$ relatively prime to $3x^2 + 12$?

It is, if we are interested in polynomials with integer coefficients. There’s no linear combination of $3x + 6$ and $3x^2 + 12$ which gets us to 1. Go ahead and try.

It is not, if we are interested in polynomials with rational coefficients. Multiply $3x + 6$ by $\frac{1}{12}\left(1 - \frac{1}{2}x\right)$ and multiply $3x^2 + 12$ by $\frac{1}{24}$. Then add those up.

Tell me what polynomials you want to deal with today and I will tell you which answer is right.

This may all seem cute if, perhaps, petty. A bunch of anonymous theorems dotting the center third of an abstract algebra text will inspire that. The most important relative-primes thing I know of is the abc conjecture, posed in the mid-80s by Joseph Oesterlé and David Masser. Start with three counting numbers, a, b, and c. Require that a + b = c.

There is a product of the unique prime factors of a, b, and c. That is, let’s say a is 36. This is 2 times 2 times 3 times 3. Let’s say b is 5. This is prime. c is 41; it’s prime. Their unique prime factors are 2, 3, 5, and 41; the product of all these is 1,230.

The conjecture deals with this product of unique prime factors for this relatively prime triplet. Almost always, c is going to be smaller than this unique prime factors product. The conjecture says that there will be, for every positive real number $\epsilon$, at most finitely many cases where c is larger than this product raised to the power $1 + \epsilon$. I do not know why raising this product to this power is so important. I assume it rules out some case where this product raised to the first power would be too easy a condition.

Apart from that $1 + \epsilon$ bit, though, this is a classic sort of number theory conjecture. Like, it involves some technical terms, but nothing too involved. You could almost explain it at a party and expect to be understood, and to get some people writing down numbers, testing out specific cases. Nobody will go away solving the problem, but they’ll have some good exercise and that’s worthwhile.

And it has consequences. We do not know whether the abc conjecture is true. We do know that if it is true, then a bunch of other things follow. The one that a non-mathematician would appreciate is that Fermat’s Last Theorem would be provable by an alterante route. The abc conjecture would only prove the cases for Fermat’s Last Theorem for powers greater than 5. But that’s all right. We can separately work out the cases for the third, fourth, and fifth powers, and then cover everything else at once. (That we know Fermat’s Last Theorem is true doesn’t let us conclude the abc conjecture is true, unfortunately.)

There are other implications. Some are about problems that seem like fun to play with. If the abc conjecture is true, then for every integer A, there are finitely many values of n for which $n! + A$ is a perfect square. Some are of specialist interest: Lang’s conjecture, about elliptic curves, would be true. This is a lower bound for the height of non-torsion rational points. I’d stick to the $n! + A$ stuff at a party. A host of conjectures about Diophantine equations — (high school) algebra problems where only integers may be solutions — become theorems. Also coming true: the Fermat-Catalan conjecture. This is a neat problem; it claims that the equation

$a^m + b^n = c^k$

where a, b, and c are relatively prime, and m, n, and k are positive integers satisfying the constraint

$\frac{1}{m} + \frac{1}{n} + \frac{1}{k} < 1$

has only finitely many solutions with distinct triplets $\left(a^m, b^n, c^k\right)$. The inequality about reciprocals of m, n, and k is needed so we don’t have boring solutions like $2^2 + 3^3 = 31^1$ clogging us up. The bit about distinct triplets is so we don’t clog things up with a or b being 1 and then technically every possible m or n giving us a “different” set. To date we know something like ten solutions, one of them having a equal to 1.

Another implication is Pillai’s Conjecture. This one asks whether every positive integer occurs only finitely many times as the difference between perfect powers. Perfect powers are, like 32 (two to the fifth power) or 81 (three to the fourth power) or such.

So as often happens when we stumble into a number theory thing, the idea of relative primes is easy. And there are deep implications to them. But those in turn give us things that seem like fun arithmetic puzzles.

This closes out the A to Z essays for this week. Tomorrow and Saturday I hope to bring some attention to essays from past years. And next week I figure to open for topics for the end of the alphabet, the promising letters U through Z. This and the rest of the 2019 essays should appear at this link, as should the letter S next Tuesday. And all of the A to Z essays ought to be at this link. Thank you for reading.

## Reading the Comics, September 21, 2019: Prime Numbers and the Rest

This is almost all a post about some comics that don’t need more than a mention. You know, strips that just have someone in class not buying the word problem. These are the rest of last week’s.

Before I get there, though, I want to share something. I ran across an essay by Chris K Caldwell and Yeng Xiong: What Is The Smallest Prime? The topic is about 1, and whether that should be a prime number. Everyone who knows a little about mathematics knows that 1 is generally not considered a prime number. But we’re also a bit stumped to figure out why, since the idea of “a prime number is divisible by 1 and itself” seems to fit this, even if the fit is weird. And we have an explanation for this: 1 used to be thought of as prime, but it made various theorems more clumsy to present. So it was either cut 1 out of the definition or add the equivalent work to everything, and mathematicians went for the solution that was less work. I know that I’ve shared this story around here. (I’m surprised to find I didn’t share it in my Summer 2017 A-to-Z essay about prime numbers.)

The truth is more complicated than that. The truth of anything is always more complicated than its history. Even an excellent history’s. It’s not that the short story has things wrong, precisely. But that that matters are more complicated than that. The history includes things we forget were ever problems, like, the question of whether 1 should be a number. And that the question of whether mathematicians “used to” consider 1 a number is built on the supposition that mathematicians were a lot more uniform in their thinking than they were. Even to the individual: people were inconsistent in what they themselves wrote, because most mathematicians turn out to be people.

It’s an eight-page paper, and not at all technical, so if you’re just interested in the history of whether 1 is a prime number, this is quite readable. It also points out a word ready for resurrection that we could use to mean “1 and the prime numbers”: the incomposites.

So that’s some good reading. Now to the comic strips that you can glance at and agree are comic strips which say “math” somewhere in there. (They’d say “maths” if I read more British comic strips.)

Bob Scott’s Bear With Me for the 16th has Bear trying to help Molly get out of algebra.

Tim Rickard’s Brewster Rockit for the 17th mentions entropy, which is so central to understanding statistical mechanics and information theory. It’s in the popular understanding of entropy, that of it being a thing which makes stuff get worse. But that’s of mathematical importance too.

John Zakour and Scott Roberts’s Maria’s Day for the 18th is about Maria having trouble with a mathematics exam. By the 20th, though, she’s doing better, and she has reasons.

Jef Mallett’s Frazz for the 20th is set during mathematics class.

This wraps up last week’s comic strips. I hope to have my next Reading the Comics post on Sunday. And then tomorrow I get to ‘H’ in the Fall 2019 A to Z essays. Thank you for reading.

## Yes, I Am Late With The Comics Posts Today

I apologize that, even though the past week was light on mathematically-themed comic strips, I didn’t have them written up by my usual Sunday posting time. It was just too busy a week, and I am still decompressing from the A to Z sequence. I’ll have them as soon as I’m able.

In the meanwhile may I share a couple of things I thought worth reading, and that have been waiting in my notes folder for the chance to highlight?

This Fermat’s Library tweet is one of those entertaining consequences of probability, multiplied by the large number of people in the world. If you flip twenty coins in a row there’s a one in 1,048,576 chance that all twenty will come up heads, or all twenty will come up tails. So about one in every million times you flip twenty coins, they all come up the same way. If the seven billion people in the world have flipped at least twenty coins in their lives, then something like seven thousand of them had the coins turn up heads every single one of those twenty times. That all seven billion people have tossed a coin seems like the biggest point to attack this trivia on. A lot of people are too young, or don’t have access to, coins. But there’s still going to be thousands who did start their coin-flipping lives with a remarkable streak.

Also back in October, so you see how long things have been circulating around here, John D Cook published an article about the World Series. Or any series contest. At least ones where the chance of each side winning don’t depend on the previous games in the series. If one side has a probability ‘p’ of winning any particular game, what’s the chance they’ll win a best-four-of-seven? What makes this a more challenging mathematics problem is that a best-of-seven series stops after one side’s won four games. So you can’t simply say it’s the chance of four wins. You need to account for four wins out of five games, out of six games, and out of seven games. Fortunately there’s a lot of old mathematics that explores just this.

The economist Brandford DeLong noticed the first write-up of the Prisoners Dilemma. This is one of the first bits of game theory that anyone learns, and it’s an important bit. It establishes that the logic of cooperatives games — any project where people have to work together — can have a terrible outcome. What makes the most sense for the individuals makes the least sense for the group. That a good outcome for everyone depends on trust, whether established through history or through constraints everyone’s agreed to respect.

And finally here’s part of a series about quick little divisibility tests. This is that trick where you tell what a number’s divisible by through adding or subtracting its (base ten) digits. Everyone who’d be reading this post knows about testing for divisibility by three or nine. Here’s some rules for also testing divisibility by eleven (which you might know), by seven (less likely), and thirteen. With a bit of practice, and awareness of some exceptional numbers, you can tell by sight whether a number smaller than a thousand is prime. Add a bit of flourish to your doing this and you can establish a reputation as a magical mathematician.

## What I’ve Been Reading, Mid-March 2018

So here’s some of the stuff I’ve noticed while being on the Internet and sometimes noticing interesting mathematical stuff.

Here from the end of January is a bit of oddball news. A story problem for 11-year-olds in one district of China set up a problem that couldn’t be solved. Not exactly, anyway. The question — “if a ship had 26 sheep and 10 goats onboard, how old is the ship’s captain?” — squares nicely with that Gil comic strip I discussed the other day. After seeing 26 (something) and 10 (something else) it’s easy to think of what answers might be wanted: 36 (total animals) or 16 (how many more sheep there are than goats) or maybe 104 (how many hooves there are, if they all have the standard four hooves). That the question doesn’t ask anything that the given numbers matter for barely registers unless you read the question again. I like the principle of reminding people not to calculate until you know what you want to do and why that. And it’s possible to give partial answers: the BBC News report linked above includes a mention from one commenter that allowed a reasonable lower bound to be set on the ship’s captain’s age.

In something for my mathematics majors, here’s A Regiment of Monstrous Functions as assembled by Rob J Low. This is about functions with a domain and a range that are both real numbers. There’s many kinds of these functions. They match nicely to the kinds of curves you can draw on a sheet of paper. So take a sheet of paper and draw a curve. You’ve probably drawn a continuous curve, one that can be drawn without lifting your pencil off the paper. Good chance you drew a differentiable one, one without corners. But most functions aren’t continuous. And aren’t differentiable. Of those few exceptions that are, many of them are continuous or differentiable only in weird cases. Low reviews some of the many kinds of functions out there. Functions discontinuous at a point. Functions continuous only on one point, and why that’s not a crazy thing to say. Functions continuous on irrational numbers but discontinuous on rational numbers. This is where mathematics majors taking real analysis feel overwhelmed. And then there’s stranger stuff out there.

Here’s a neat one. It’s about finding recognizable, particular, interesting pictures in long enough prime numbers. The secret to it is described in the linked paper. The key is that the eye is very forgiving of slightly imperfect images. This fact should reassure people learning to draw, but will not. And there’s a lot of prime numbers out there. If an exactly-correct image doesn’t happen to be a prime number that’s all right. There’s a number close enough to it that will be. That latter point is something that anyone interested in number theory “knows”, in that we know some stuff about the biggest possible gaps between prime numbers. But that fact isn’t the same as seeing it.

And finally there’s something for mathematics majors. Differential equations are big and important. They appear whenever you want to describe something that changes based on its current state. And this is so much stuff. Finding solutions to differential equations is a whole major field of mathematics. The linked PDF is a slideshow of notes about one way to crack these problems: find symmetries. The only trouble is it’s a PDF of a Powerpoint presentation, one of those where each of the items gets added on in sequence. So each slide appears like eight times, each time with one extra line on it. It’s still good, interesting stuff.

## A Summer 2017 Mathematics A To Z Appendix: Are Colbert Numbers A Thing?

This is something I didn’t have space for in the proper A To Z sequence. And it’s more a question than exposition anyway. But what the heck: I like excuses to use my nice shiny art package.

I was looking for mathematics topics I might write about if I didn’t get requests for particular letters. ‘C’ came up ‘cohomology’, but what if it hadn’t? I found an interesting-looking listing at MathWorld’s dictionary. The Colbert Numbers sounded interesting. this is a collection of very long prime numbers. Each of them has at least a million decimal digits. They relate to a conjecture by Wacław Sierpiński, who’s gone months without a mention around here.

The conjecture is about whole numbers that are equal to $k \cdot 2^n + 1$ for some whole numbers ‘k’ and ‘n’. Are there choices of ‘k’ for which, no matter what positive whole number ‘n’ you pick, $k \cdot 2^n + 1$ is never a prime number? (‘k’ has to meet some extra conditions.) I’m not going to explain why this is interesting because I don’t know. It’s a number theory question. They’re all strange and interesting questions in their ways. If I were writing an essay about Colbert Numbers I’d have figured that out.

Thing is we believe we know what the smallest possible ‘k’ is. We think that the smallest possible Sierpiński number is 78,557. We don’t have this quite proved, though. There are some numbers that might be prime numbers of the form $k \cdot 2^n + 1$ for some ‘k’ and some ‘n’. There was a set of seventeen possible candidates of numbers smaller than 78,557 that might be Sierpiński numbers. If those candidates could be ruled out then we’d have proved 78,557 was it. That’s easy to imagine. Find for each of them a number ‘n’ so that the candidate times 2n plus one was a prime number. But finding big prime numbers is hard. This turned into a distributed-computing search. This would evaluate these huge numbers and find whether they were prime numbers. (The project, “Seventeen Or Bust”, was destroyed by computer failure in 2016. Attempts to verify the work done, and continue it, are underway.) There are six possible candidates left.

MathWorld says that the seventeen cases that had to be checked were named Colbert Numbers. This was in honor of Stephen T Colbert, the screamingly brilliant character host of The Colbert Report. (Ask me sometime about the Watership Down anecdote.) It’s a plausible enough claim. Part of Stephen T Colbert’s persona was demanding things be named for him. And he’d take appropriate delight in having minor but interesting things named for him. Treadmills on the space station. Minor-league hockey team mascots. A class of numbers for proving a 60-year-old mathematical conjecture is exactly the sort of thing that would get his name and attention.

But here’s my problem. Who named them Colbert Numbers? MathWorld doesn’t say. Wikipedia doesn’t say. The best I can find with search engines doesn’t say. When were they named Colbert Numbers? Again, no answers. Poking around fan sites for The Colbert Report — where you’d expect the naming of stuff in his honor to be mentioned — doesn’t turn up anything. Does anyone call them Colbert Numbers? I mean outside people who’ve skimmed MathWorld’s glossary for topics with intersting names?

I don’t mean to sound overly skeptical here. But, like, I know there’s a class of science fiction fans who like to explain how telerobotics engineers name their hardware “waldoes”. This is in honor of a character in a Robert Heinlein story I never read either. I’d accepted that without much interest until Google’s US Patent search became a thing. One afternoon I noticed that if telerobotics engineers do call their hardware “waldoes” they never use the term in patent applications. Is it possible that someone might have slipped a joke in to Wikipedia or something and had it taken seriously? Certainly. What amounts to a Wikipedia prank briefly gave the coati — an obscure-to-the-United-States animal that I like — the nickname of “Brazilian aardvark”. There are surely other instances of Wikipedia-generated pranks becoming “real” things.

So I would like to know. Who named Colbert Numbers that, and when, and were they — as seems obvious, but you never know — named for Stephen T Colbert? Or is this an example of Wikiality, the sense that reality can be whatever enough people decide to believe is true, as described by … well, Stephen T Colbert?

## The Summer 2017 Mathematics A To Z: Well-Ordering Principle

It’s the last full week of the Summer 2017 A To Z! Four more essays and I’ll have completed this project and curl up into a word coma. But I’m not there yet. Today’s request is another from Gaurish, who’s given me another delightful topic to write about. Gaurish hosts a fine blog, For the love of Mathematics, which I hope you’ve given a try.

# Well-Ordering Principle.

An old mathematics joke. Or paradox, if you prefer. What is the smallest whole number with no interesting properties?

Not one. That’s for sure. We could talk about one forever. It’s the first number we ever know. It’s the multiplicative identity. It divides into everything. It exists outside the realm of prime or composite numbers. It’s — all right, we don’t need to talk about one forever. Two? The smallest prime number. The smallest even number. The only even prime. The only — yeah, let’s move on. Three; the smallest odd prime number. Triangular number. One of only two prime numbers that isn’t one more or one less than a multiple of six. Let’s move on. Four. A square number. The smallest whole number that isn’t 1 or a prime. Five. Prime number. First sum of two different prime numbers. Part of the first prime pair. Six. Smallest perfect number. Smallest product of two different prime numbers. Let’s move on.

And so on. Somewhere around 22 or so, the imagination fails and we can’t think of anything not-boring about this number. So we’ve found the first number that hasn’t got any interesting properties! … Except that being the smallest boring number must be interesting. So we have to note that this is otherwise the smallest boring number except for that bit where it’s interesting. On to 23, which used to be the default funny number. 24. … Oh, carry on. Maybe around 31 things settle down again. Our first boring number! Except that, again, being the smallest boring number is interesting. We move on to 32, 33, 34. When we find one that couldn’t be interesting, we find that’s interesting. We’re left to conclude there is no such thing as a boring number.

This would be a nice thing to say for numbers that otherwise get no attention, if we pretend they can have hurt feelings. But we do have to admit, 1729 is actually only interesting because it’s a part of the legend of Srinivasa Ramanujan. Enjoy the silliness for a few paragraphs more.

(This is, if I’m not mistaken, a form of the heap paradox. Don’t remember that? Start with a heap of sand. Remove one grain; you’ve still got a heap of sand. Remove one grain again. Still a heap of sand. Remove another grain. Still a heap of sand. And yet if you did this enough you’d leave one or two grains, not a heap of sand. Where does that change?)

Another problem, something you might consider right after learning about fractions. What’s the smallest positive number? Not one-half, since one-third is smaller and still positive. Not one-third, since one-fourth is smaller and still positive. Not one-fourth, since one-fifth is smaller and still positive. Pick any number you like and there’s something smaller and still positive. This is a difference between the positive integers and the positive real numbers. (Or the positive rational numbers, if you prefer.) The thing positive integers have is obvious, but it is not a given.

The difference is that the positive integers are well-ordered, while the positive real numbers aren’t. Well-ordering we build on ordering. Ordering is exactly what you imagine it to be. Suppose you can say, for any two things in a set, which one is less than another. A set is well-ordered if whenever you have a non-empty subset you can pick out the smallest element. Smallest means exactly what you think, too.

The positive integers are well-ordered. And more. The way they’re set up, they have a property called the “well-ordering principle”. This means any non-empty set of positive integers has a smallest number in it.

This is one of those principles that seems so obvious and so basic that it can’t teach anything interesting. That it serves a role in some proofs, sure, that’s easy to imagine. But something important?

Look back to the joke/paradox I started with. It proves that every positive integer has to be interesting. Every number, including the ones we use every day. Including the ones that no one has ever used in any mathematics or physics or economics paper, and never will. We can avoid that paradox by attacking the vagueness of “interesting” as a word. Are you interested to know the 137th number you can write as the sum of cubes in two different ways? Before you say ‘yes’, consider whether you could name it ten days after you’ve heard the number.

(Granted, yes, it would be nice to know the 137th such number. But would you ever remember it? Would you trust that it’ll be on some Wikipedia page that somehow is never threatened with deletion for not being noteworthy? Be honest.)

But suppose we have some property that isn’t so mushy. Suppose that we can describe it in some way that’s indexed by the positive integers. Furthermore, suppose that we show that in any set of the positive integers it must be true for the smallest number in that set. What do we know?

— We know that it must be true for all the positive integers. There’s a smallest positive integer. The positive integers have this well-ordered principle. So any subset of the positive integers has some smallest member. And if we can show that something or other is always true for the smallest number in a subset of the positive integers, there you go.

This technique we call, when it’s introduced, induction. It’s usually a baffling subject because it’s usually taught like this: suppose the thing you want to show is indexed to the positive integers. Show that it’s true when the index is ‘1’. Show that if the thing is true for an arbitrary index ‘n’, then you know it’s true for ‘n + 1’. It’s baffling because that second part is hard to visualize. The student makes a lot of mistakes in learning, on examples of what the sum of the first ‘N’ whole numbers or their squares or cubes are. I don’t think induction is ever taught in this well-ordering principle method. But it does get used in proofs, once you get to the part of analysis where you don’t have to interact with actual specific numbers much anymore.

The well-ordering principle also gives us the method of infinite descent. You encountered this in learning proofs about, like, how the square root of two must be an irrational number. In this, you show that if something is true for some positive integer, then it must also be true for some other, smaller positive integer. And therefore some other, smaller positive integer again. And again, until you get into numbers small enough you can check by hand.

It keeps creeping in. The Fundamental Theorem of Arithmetic says that every positive whole number larger than one is a product of a unique string of prime numbers. (Well, the order of the primes doesn’t matter. 2 times 3 times 5 is the same number as 3 times 2 times 5, and so on.) The well-ordering principle guarantees you can factor numbers into a product of primes. Watch this slick argument.

Suppose you have a set of whole numbers that isn’t the product of prime numbers. There must, by the well-ordering principle, be some smallest number in that set. Call that number ‘n’. We know that ‘n’ can’t be prime, because if it were, then that would be its prime factorization. So it must be the product of at least two other numbers. Let’s suppose it’s two numbers. Call them ‘a’ and ‘b’. So, ‘n’ is equal to ‘a’ times ‘b’.

Well, ‘a’ and ‘b’ have to be less than ‘n’. So they’re smaller than the smallest number that isn’t a product of primes. So, ‘a’ is the product of some set of primes. And ‘b’ is the product of some set of primes. And so, ‘n’ has to equal the primes that factor ‘a’ times the primes that factor ‘b’. … Which is the prime factorization of ‘n’. So, ‘n’ can’t be in the set of numbers that don’t have prime factorizations. And so there can’t be any numbers that don’t have prime factorizations. It’s for the same reason we worked out there aren’t any numbers with nothing interesting to say about them.

And isn’t it delightful to find so simple a principle can prove such specific things?

## The Summer 2017 Mathematics A To Z: Ulam’s Spiral

Gaurish, of For the love of Mathematics, asked me about one of those modestly famous (among mathematicians) mathematical figures. Yeah, I don’t have a picture of it. Too much effort. It’s easier to write instead.

# Ulam’s Spiral.

Boredom is unfairly maligned in our society. I’ve said this before, but that was years ago, and I have some different readers today. We treat boredom as a terrible thing, something to eliminate. We treat it as a state in which nothing seems interesting. It’s not. Boredom is a state in which anything, however trivial, engages the mind. We would not count the tiles on the floor, or time the rocking of a chandelier, or wonder what fraction of solitaire games can be won if we were never bored. A bored mind is a mind ready to discover things. We should welcome the state.

Several times in the 20th century Stanislaw Ulam was bored. I mention solitaire games because, according to Ulam, he spent some time in 1946 bored, convalescent and playing a lot of solitaire. He got to wondering what’s the probability a particular solitaire game is winnable? (He was specifically playing Canfield solitaire. The game’s also called Demon, Chameleon, or Storehouse, if Wikipedia is right.) What’s the chance the cards can’t be played right, no matter how skilled the player is? It’s a problem impossible to do exactly. Ulam was one of the mathematicians designing and programming the computers of the day.

He, with John von Neumann, worked out how to get a computer to simulate many, many rounds of cards. They would get an answer that I have never seen given in any history of the field. The field is Monte Carlo simulations. It’s built on using random numbers to conduct experiments that approximate an answer. (They’re also what my specialty is in. I mention this for those who’ve wondered what, if any, mathematics field I do consider myself competent in. This is not it.) The chance of a winnable deal is about 71 to 72 percent, although actual humans can’t hope to do more than about 35 percent. My evening’s experience with this Canfield Solitaire game suggests the chance of winning is about zero.

In 1963, Ulam told Martin Gardner, he was bored again during a paper’s presentation. Ulam doodled, and doodled something interesting enough to have a computer doodle more than mere pen and paper could. It was interesting enough to feature in Gardner’s Mathematical Games column for March 1964. It started with what the name suggested, a spiral.

Write down ‘1’ in the center. Write a ‘2’ next to it. This is usually done to the right of the ‘1’. If you want the ‘2’ to be on the left, or above, or below, fine, it’s your spiral. Write a ‘3’ above the ‘2’. (Or below if you want, or left or right if you’re doing your spiral that way. You’re tracing out a right angle from the “path” of numbers before that.) A ‘4’ to the left of that, a ‘5’ under that, a ‘6’ under that, a ‘7’ to the right of that, and so on. A spiral, for as long as your paper or your patience lasts. Now draw a circle around the ‘2’. Or a box. Whatever. Highlight it. Also do this for the ‘3’, and the ‘5’, and the ‘7’ and all the other prime numbers. Do this for all the numbers on your spiral. And look at what’s highlighted.

It looks like …

It’s …

Well, it’s something.

It’s hard to say what exactly. There’s a lot of diagonal lines to it. Not uninterrupted lines. Every diagonal line has some spottiness to it. There are blank regions too. There are some long stretches of numbers not highlighted, many of them horizontal or vertical lines with no prime numbers in them. Those stop too. The eye can’t help seeing clumps, especially. Imperfect diagonal stitching across the fabric of the counting numbers.

Maybe seeing this is some fluke. Start with another number in the center. 2, if you like. 41, if you feel ambitious. Repeat the process. The details vary. But the pattern looks much the same. Regions of dense-packed broken diagonals, all over the plane.

It begs us to believe there’s some knowable pattern here. That we could get an artist to draw a figure, with each spot in the figure corresponding to a prime number. This would be great. We know many things about prime numbers, but we don’t really have any system to generate a lot of prime numbers. Not much better than “here’s a thing, try dividing it”. Back in the 80s and 90s we had the big Fractal Boom. Everybody got computers that could draw what passed for pictures. And we could write programs that drew them. The Ulam Spiral was a minor but exciting prospect there. Was it a fractal? I don’t know. I’m not sure if anyone knows. (The spiral like you’d draw on paper wouldn’t be. The spiral that went out to infinitely large numbers might conceivably be.) It seemed plausible enough for computing magazines to be interested in. Maybe we could describe the pattern by something as simple as the Koch curve (that wriggly triangular snowflake shape). Or as easy to program as the Mandelbrot Curve.

We haven’t found one. As keeps happening with prime numbers, the answers evade us. We can understand why diagonals should appear. Write a polynomial of the form $4n^2 + b n + c$. Evaluate it for n of 1, 2, 3, 4, and so on. Highlight those numbers. This will tend to highlight numbers that, in this spiral, are diagonal or horizontal or vertical lines. A lot of polynomials like this give a string of some prime numbers. But the polynomials all peter out. The lines all have interruptions.

There are other patterns. One, predating Ulam’s boring paper by thirty years, was made by Laurence Klauber. Klauber was a herpetologist of some renown, if Wikipedia isn’t misleading me. It claims his Rattlesnakes: Their Habits, Life Histories, and Influence on Mankind is still an authoritative text. I don’t know and will defer to people versed in the field. It also credits him with several patents in electrical power transmission.

Anyway, Klauber’s Triangle sets a ‘1’ at the top of the triangle. The numbers ‘2 3 4’ under that, with the ‘3’ directly beneath the ‘1’. The numbers ‘5 6 7 8 9’ beneath that, the ‘7’ directly beneath the ‘3’. ’10 11 12 13 14 15 16′ beneath that, the ’13’ underneath the ‘7’. And so on. Again highlight the prime numbers. You get again these patterns of dots and lines. Many vertical lines. Some lines in isometric view. It looks like strands of Morse Code.

In 1994 Robert Sacks created another variant. This one places the counting numbers on an Archimedian spiral. Space the numbers correctly and highlight the primes. The primes will trace out broken curves. Some are radial. Some spiral in (or out, if you rather). Some open up islands. The pattern looks like a Saul Bass logo for a “Nifty Fifty”-era telecommunications firm or maybe an airline.

You can do more. Draw a hexagonal spiral. Triangular ones. Other patterns of laying down numbers. You get patterns. The eye can’t help seeing order there. We can’t quite pin down what it is. Prime numbers keep evading our full understanding. Perhaps it would help to doodle a little during a tiresome conference call.

Stanislaw Ulam did enough fascinating numerical mathematics that I could probably do a sequence just on his work. I do want to mention one thing. It’s part of information theory. You know the game Twenty Questions. Play that, but allow for some lying. The game is still playable. Ulam did not invent this game; Alfréd Rényi did. (I do not know anything else about Rényi.) But Ulam ran across Rényi’s game, and pointed out how interesting it was, and mathematicians paid attention to him.

## The Summer 2017 Mathematics A To Z: Prime Number

Gaurish, host of, For the love of Mathematics, gives me another topic for today’s A To Z entry. I think the subject got away from me. But I also like where it got.

# Prime Number.

Something about ‘5’ that you only notice when you’re a kid first learning about numbers. You know that it’s a prime number because it’s equal to 1 times 5 and nothing else. You also know that once you introduce fractions, it’s equal to all kinds of things. It’s 10 times one-half and it’s 15 times one-third and it’s 2.5 times 2 and many other things. Why, you might ask the teacher, is it a prime number if it’s got a million billion trillion different factors? And when every other whole number has as many factors? If you get to the real numbers it’s even worse yet, although when you’re a kid you probably don’t realize that. If you ask, the teacher probably answers that it’s only the whole numbers that count for saying whether something is prime or not. And, like, 2.5 can’t be considered anything, prime or composite. This satisfies the immediate question. It doesn’t quite get at the underlying one, though. Why do integers have prime numbers while real numbers don’t?

To maybe have a prime number we need a ring. This is a creature of group theory, or what we call “algebra” once we get to college. A ring consists of a set of elements, and a rule for adding them together, and a rule for multiplying them together. And I want this ring to have a multiplicative identity. That’s some number which works like ‘1’: take something, multiply it by that, and you get that something back again. Also, I want this multiplication rule to commute. That is, the order of multiplication doesn’t affect what the result is. (If the order matters then everything gets too complicated to deal with.) Let me say the things in the set are numbers. It turns out (spoiler!) they don’t have to be. But that’s how we start out.

Whether the numbers in a ring are prime or not depends on the multiplication rule. Let’s take a candidate number that I’ll call ‘a’ to make my writing easier. If the only numbers whose product is ‘a’ are the pair of ‘a’ and the multiplicative identity, then ‘a’ is prime. If there’s some other pair of numbers that give you ‘a’, then ‘a’ is not prime.

The integers — the positive and negative whole numbers, including zero — are a ring. And they have prime numbers just like you’d expect, if we figure out some rule about how to deal with the number ‘-1’. There are many other rings. There’s a whole family of rings, in fact, so commonly used that they have shorthand. Mathematicians write them as “Zn”, where ‘n’ is some whole number. They’re the integers, modulo ‘n’. That is, they’re the whole numbers from ‘0’ up to the number ‘n-1’, whatever that is. Addition and multiplication work as they do with normal arithmetic, except that if the result is less than ‘0’ we add ‘n’ to it. If the result is more than ‘n-1’ we subtract ‘n’ from it. We repeat that until the result is something from ‘0’ to ‘n-1’, inclusive.

(We use the letter ‘Z’ because it’s from the German word for numbers, and a lot of foundational work was done by German-speaking mathematicians. Alternatively, we might write this set as “In”, where “I” stands for integers. If that doesn’t satisfy, we might write this set as “Jn”, where “J” stands for integers. This is because it’s only very recently that we’ve come to see “I” and “J” as different letters rather than different ways to write the same letter.)

These modulo arithmetics are legitimate ones, good reliable rings. They make us realize how strange prime numbers are, though. Consider the set Z4, where the only numbers are 0, 1, 2, and 3. 0 times anything is 0. 1 times anything is whatever you started with. 2 times 1 is 2. Obvious. 2 times 2 is … 0. All right. 2 times 3 is 2 again. 3 times 1 is 3. 3 times 2 is 2. 3 times 3 is 1. … So that’s a little weird. The only product that gives us 3 is 3 times 1. So 3’s a prime number here. 2 isn’t a prime number: 2 times 3 is 2. For that matter even 1 is a composite number, an unsettling consequence.

Or then Z5, where the only numbers are 0, 1, 2, 3, and 4. Here, there are no prime numbers. Each number is the product of at least one pair of other numbers. In Z6 we start to have prime numbers again. But Z7? Z8? I recommend these questions to a night when your mind is too busy to let you fall asleep.

Prime numbers depend on context. In the crowded universe of all the rational numbers, or all the real numbers, nothing is prime. In the more austere world of the Gaussian Integers, familiar friends like ‘3’ are prime again, although ‘5’ no longer is. We recognize that as the product of $2 + \imath$ and $2 - \imath$, themselves now prime numbers.

So given that these things do depend on context. Should we care? Or let me put it another way. Suppose we contact a wholly separate culture, one that we can’t have influenced and one not influenced by us. It’s plausible that they should have a mathematics. Would they notice prime numbers as something worth study? Or would they notice them the way we notice, say, pentagonal numbers, a thing that allows for some pretty patterns and that’s about it?

Well, anything could happen, of course. I’m inclined to think that prime numbers would be noticed, though. They seem to follow naturally from pondering arithmetic. And if one has thought of rings, then prime numbers seem to stand out. The way that Zn behaves changes in important ways if ‘n’ is a prime number. Most notably, if ‘n’ is prime (among the whole numbers), then we can define something that works like division on Zn. If ‘n’ isn’t prime (again), we can’t. This stands out. There are a host of other intriguing results that all seem to depend on whether ‘n’ is a prime number among the whole numbers. It seems hard to believe someone could think of the whole numbers and not notice the prime numbers among them.

And they do stand out, as these reliably peculiar things. Many things about them (in the whole numbers) are easy to prove. That there are infinitely many, for example, you can prove to a child. And there are many things we have no idea how to prove. That there are infinitely many primes which are exactly two more than another prime, for example. Any child can understand the question. The one who can prove it will win what fame mathematicians enjoy. If it can be proved.

They turn up in strange, surprising places. Just in the whole numbers we find some patches where there are many prime numbers in a row (Forty percent of the numbers 1 through 10!). We can find deserts; we know of a stretch of 1,113,106 numbers in a row without a single prime among them. We know it’s possible to find prime deserts as vast as we want. Say you want a gap between primes of at least size N. Then look at the numbers (N+1)! + 2, (N+1)! + 3, (N+1)! + 4, and so on, up to (N+1)! + N+1. None of those can be prime numbers. You must have a gap at least the size N. It may be larger; how we know that (N+1)! + 1 is a prime number?

No telling. Well, we can check. See if any prime number divides into (N+1)! + 1. This takes a long time to do if N is all that big. There’s no formulas we know that will make this easy or quick.

We don’t call it a “prime number” if it’s in a ring that isn’t enough like the numbers. Fair enough. We shift the name to “prime element”. “Element” is a good generic name for a thing whose identity we don’t mean to pin down too closely. I’ve talked about the Gaussian Primes already, in an earlier essay and earlier in this essay. We can make a ring out of the polynomials whose coefficients are all integers. In that, $x^2 + 1$ is a prime. So is $x^2 - 2$. If this hasn’t given you some ideas what other polynomials might be primes, then you have something else to ponder while trying to sleep. Thinking of all the prime polynomials is likely harder than you can do, though.

Prime numbers seem to stand out, obvious and important. Humans have known about prime numbers for as long as we’ve known about multiplication. And yet there is something obscure about them. If there are cultures completely independent of our own, do they have insights which make prime numbers not such occult figures? How different would the world be if we knew all the things we now wonder about primes?

## Reading the Comics, November 19, 2016: Thought I Featured This Already Edition

For the second half of last week Comic Strip Master Command sent me a couple comics I would have sworn I showed off here before.

Jason Poland’s Robbie and Bobby for the 16th I would have sworn I’d featured around here before. I still think it’s a rerun but apparently I haven’t written it up. It’s a pun, I suppose, playing on the use of “power” to mean both exponentials and the thing knowledge is. I’m curious why Polard used 10 for the new exponent. Normally if there isn’t an exponent explicitly written we take that to be “1”, and incrementing 1 would give 2. Possibly that would have made a less-clear illustration. Or possibly the idea of sleeping squared lacked the Brobdingnagian excess of sleeping to the tenth power.

Exponentials have been written as a small number elevated from the baseline since 1636. James Hume then published an edition of François Viète’s text on algebra. Hume used a Roman numeral in the superscript — xii instead of x2 — but apart from that it’s the scheme we use today. The scheme was in the air, though. Renée Descartes also used the notation, but with Arabic numerals throughout, from 1637. (With quirks; he would write “xx” instead of “x2”, possibly because it’s the same number of characters to write.) And Pierre Hérigone just wrote the exponent after the variable: x2, like you see in bad character-recognition texts. That isn’t a bad scheme, particularly since it’s so easy to type, although we would add a caret: x^2. (I draw all this history, as ever, from Florian Cajori’s A History of Mathematical Notations, particularly sections 297 through 299).

Zach Weinersmith’s Saturday Morning Breakfast Cereal for the 16th has a fun concept about statisticians running wild and causing chaos. I appreciate a good healthy prank myself. It does point out something valuable, though. People in general have gotten to understand the idea that there are correlations between things. An event happening and some effect happening seem to go together. This is sometimes because the event causes the effect. Sometimes they’re both caused by some other factor; the event and effect are spuriously linked. Sometimes there’s just no meaningful connection. Coincidences do happen. But there’s really no good linking of how strong effects can be. And that’s not just a pop culture thing. For example, doing anything other than driving while driving increases the risk of crashing. But by how much? It’s easy to take something with the shape of a fact. Suppose it’s “looking at a text quadruples your risk of crashing”. (I don’t know what the risk increase is. Pretend it’s quadruple for the sake of this.) That’s easy to remember. But what’s my risk of crashing? Suppose it’s a clear, dry day, no winds, and I’m on a limited-access highway with light traffic. What’s the risk of crashing? Can’t be very high, considering how long I’ve done that without a crash. Quadruple that risk? That doesn’t seem terrifying. But I don’t know what that is, or how to express it in a way that helps make decisions. It’s not just newscasters who have this weakness.

Mark Anderson’s Andertoons for the 18th is the soothing appearance of Andertoons for this essay. And while it’s the familiar form of the student protesting the assignment the kid does have a point. There are times an estimate is all we need, and there’s times an exact answer is necessary. When are those times? That’s another skill that people have to develop.

Arthur C Clarke, in his semi-memoir Astounding Days, wrote of how his early-40s civil service job had him auditing schoolteacher pension contributions. He worked out that he really didn’t need to get the answers exactly. If the contribution was within about one percent of right it wasn’t worth his time to track it down more precisely. I’m not sure that his supervisors would take the same attitude. But the war soon took everyone to other matters without clarifying just how exactly he was supposed to audit.

Mark Anderson’s Mr Lowe rerun for the 18th is another I would have sworn I’ve brought up before. The strip was short-lived and this is at least its second time through. But then mathematics is only mentioned here as a dull things students must suffer through. It might not have seemed interesting enough for me to mention before.

Rick Detorie’s One Big Happy rerun for the 19th is another sort of pun. At least it plays on the multiple meanings of “negative”. And I suspect that negative numbers acquired a name with, er, negative connotations because the numbers were suspicious. It took centuries for mathematicians to move them from “obvious nonsense” to “convenient but meaningless tools for useful calculations” to “acceptable things” to “essential stuff”. Non-mathematicians can be forgiven for needing time to work through that progression. Also I’m not sure I didn’t show this one off here when it was first-run. Might be wrong.

Saturday Morning Breakfast Cereal pops back into my attention for the 19th. That’s with a bit about Dad messing with his kid’s head. Not much to say about that so let me bury the whimsy with my earnestness. The strip does point out that what we name stuff is arbitrary. We would say that 4 and 12 and 6 are “composite numbers”, while 2 and 3 are “prime numbers”. But if we all decided one day to swap the meanings of the terms around we wouldn’t be making any mathematics wrong. Or linguistics either. We would probably want to clarify what “a really good factor” is, but all the comic really does is mess with the labels of groups of numbers we’re already interested in.

## Reading the Comics, April 10, 2016: Four-Digit Prime Number Edition

In today’s installment of Reading The Comics, mathematics gets name-dropped a bunch in strips that aren’t really about my favorite subject other than my love. Also, I reveal the big lie we’ve been fed about who drew the Henry comic strip attributed to Carl Anderson. Finally, I get a question from Queen Victoria. I feel like this should be the start of a podcast.

Patrick Roberts’ Todd the Dinosaur for the 6th of April just name-drops mathematics. The flash cards suggest it. They’re almost iconic for learning arithmetic. I’ve seen flash cards for other subjects. But apart from learning the words of other languages I’ve never been able to make myself believe they’d work. On the other hand, I haven’t used flash cards to learn (or teach) things myself.

Joe Martin’s Boffo for the 7th of April is a solid giggle. (I have a pretty watery giggle myself.) There are unknowable, or at least unprovable, things in mathematics. Any logic system with enough rules to be interesting has ideas which would make sense, and which might be true, but which can’t be proven. Arithmetic is such a system. But just fractions and long division by itself? No, I think we need something more abstract for that.

Carl Anderson’s Henry for the 7th of April is, of course, a rerun. It’s also a rerun that gives away that the “Carl Anderson” credit is a lie. Anderson turned over drawing the comic strip in 1942 to John Liney, for weekday strips, and Don Trachte for Sundays. There is no possible way the phrase “New Math” appeared on the cover of a textbook Carl Anderson drew. Liney retired in 1979, and Jack Tippit took over until 1983. Then Dick Hodgins, Jr, drew the strip until 1990. So depending on how quickly word of the New Math penetrated Comic Strip Master Command, this was drawn by either Liney, Tippit, or possibly Hodgins. (Peanuts made New Math jokes in the 60s, but it does seem the older the comic strip the longer it takes to mention new stuff.) I don’t know when these reruns date from. I also don’t know why Comics Kingdom is fibbing about the artist. But then they went and cancelled The Katzenjammer Kids without telling anyone either.

Eric the Circle for the 8th, this one by “lolz”, declares that Eric doesn’t like being graphed. This is your traditional sort of graph, one in which points with coordinates x and y are on the plot if their values make some equation true. For a circle, that equation’s something like (x – a)2 + (y – b)2 = r2. Here (a, b) are the coordinates for the point that’s the center of the circle, and r is the radius of the circle. This looks a lot like Eric is centered on the origin, the point with coordinates (0, 0). It’s a popular choice. Any center is as good. Another would just have equations that take longer to work with.

Richard Thompson’s Cul de Sac rerun for the 10th is so much fun to look at that I’m including it even though it just name-drops mathematics. The joke would be the same if it were something besides fractions. Although see Boffo.

Norm Feuti’s Gil rerun for the 10th takes on mathematics’ favorite group theory application, the Rubik’s Cube. It’s the way I solved them best. This approach falls outside the bounds of normal group theory, though.

Mac King and Bill King’s Magic in a Minute for the 10th shows off a magic trick. It’s also a non-Rubik’s-cube problem in group theory. One of the groups that a mathematics major learns, after integers-mod-four and the like, is the permutation group. In this, the act of swapping two (or more) things is a thing. This puzzle restricts the allowed permutations down to swapping one item with the thing next to it. And thanks to that, an astounding result emerges. It’s worth figuring out why the trick would work. If you can figure out the reason the first set of switches have to leave a penny on the far right then you’ve got the gimmick solved.

Pab Sungenis’s New Adventures of Queen Victoria for the 10th made me wonder just how many four-digit prime numbers there are. If I haven’t worked this out wrong, there’s 1,061 of them.

## Another Reasoning Puzzle From ChefMongoose

My friend ChefMongoose had another reasoning problem come to him, and I’m happy to share it further. It’s rather like that famous Singapore Birthday Problem that drove people crazy a couple of months ago. Here’s the problem:

I have a combination lock at work. There are three digits, all in the range 1 – 40; they’re all prime numbers. They’re X+Y, X+2Y, X+3Y — where X and Y are positive integers.

If I told you what X was but not Y, you wouldn’t be able to tell me the combination. If I told you what Y was but not X, you wouldn’t be able to tell me the combination. Now, what’s the combination?

I did work out the puzzle. It did make me notice a couple of strings of uniformly-spaced prime numbers I hadn’t done before, too, such as 3-13-23. (However, 3-13-23 isn’t one of the possible answers, because of the constraints of the problem. There aren’t positive X and Y for which X + Y = 3, X + 2Y = 13, and X + 3Y = 23.)

As with the Singapore Birthday Problem, this is a puzzle based on reasoning about the information we have. Mercifully there aren’t actually many prime numbers below 40, so if you want you can take the brute force approach and find all the strings of uniformly-spaced prime numbers. Then you can find what one matches the rules in ChefMongoose’s second paragraph.

I confess I wasn’t that systematic. I had a strong suspicion what the starting number of the sequence had to be, and then did some tests to be sure. I credit that to just having stared at lot at the smaller prime numbers in my life, so I’d had some intuitive feel for it. That’s a dangerous way to work. My intuitive feel, for example, hadn’t warned me about 3-13-23. But then there aren’t other trios of prime numbers spaced by ten, so that set would be ruled out by the “If I told you what Y was but not X” constraint. But now I know how to get stuff out of ChefMongoose’s work locker, you know, just in case.

## Reading the Comics, November 10, 2015: Symbols And Meanings Edition

Eric the Circle for the 5th of November, by “andei”, is a mathematics-vocabulary pun. Ellipses are measured with a property called eccentricity. It measures, in a sense, how far any conic section is from being a circle. A circle has an eccentricity of zero. An ellipse, other than a circle, has an eccentricity between 0 and 1. The smaller the eccentricity the harder it is to tell the ellipse from a circle. The larger the eccentricity the longer one direction of the ellipse is compared to the other. For example, the Earth’s orbit around the sun, a very circular thing, has an eccentricity of about 0.0167 these days. Halley’s Comet, which gets closer to the Sun than Venus does, and farther from the sun than Neptune does, has an eccentricity of about 0.967. An eccentricity of exactly 1 means the shape is a parabola. An eccentricity of greater than 1 means the shape is a hyperbola.

Mark Pett’s Mr Lowe for the 5th of November (originally the 2nd of November, 2000) gives a lousy reason to learn long division. I admit I’m not sure I can give a good reason anyone needs to know long division now that calculators are a well-proven technology. Perhaps the best reason is that long division works like much of computational mathematics does. You make a best guess for an answer, and test it, and improve it as necessary. Needing to improve an answer does not mean one started out wrong. It just means that we can approximate and modify solutions.

Russell Myers’s Broom Hilda for the 6th of November is almost this entry’s anthropomorphic numerals joke. I’m not sure just how to categorize it. Perhaps “literal” is the best to be done.

Mark Anderson’s Andertoons for the 8th of November is a joke about turning a wrong answer into a “teach the controversy!” special plea. There are mathematical controversies. But I think the only ones thriving are in fields too abstract for the average person to know or care about. But we can look to controversies of the past. An example an elementary school kid might understand is “should 1 be considered a prime number?” It’s generally not regarded as a prime number. If it were, it would add special cases or extra words to many theorems about prime numbers. That would add boring parts to a lot of work. If we move the number 1 off to its own category (a “unit”), then we can talk about prime numbers and composite numbers more easily. Is that good enough reason? If it isn’t, then what would be a good enough reason?

Bill Amend’s FoxTrot for the 8th of November (a new strip, not a rerun) is a subverted word problem joke. It does contain a mention of curves (of happiness) going to infinity, and how they might do that. There’s some interesting linguistics at work here. A plot of a function — call it f(x), for convenience — is a graph that shows sets of values where the equation y = f(x) is true. We talk about functions “going to infinity”, although properly speaking they don’t “go” anywhere at all, any more than a photograph in a paper book moves.

But it’s hard to resist the image we get from imagining drawing the curve. The eye follows the pen that sweeps, usually left to right, fluttering up and down. And near some points the pen goes soaring off the top (or bottom) of the page. If we imagine zooming out, again and again, the pen still soars off the edge of the page. So we call that “going to infinity”. What we mean is there are some values in the domain which the function matches to numbers in the range that are greater than any finite number. (Or less than any finite but negative number, if we’re going off to negative infinity.)

We can even talk about how cuves “go to” infinity. If the function y = f(x) becomes infinitely large at some point, what does the function f(x)/x do? If that function stays finite we can say f(x) grows to infinity in the same way than x does. If f(x)/x grows infinitely large we can say that f(x) grows to infinity faster than x does. If f(x)/ex stays finite, we can say that f(x) grows to infinity in the same way that the exponential function ex does.

Rates of growth may seem like a dull thing to worry about. They become more obviously relevant if we’re interested in functions that measure, for example, how much of a resource is required to do something. Suppose we have different ways to find the best choice out of a set of things. How long finding that takes depends on how many things there are to look through. If we are looking at scalability — how well we’ll be able to find the best choice out of a much larger set of things — then the rate of growth of these functions can be quite important. If doubling the set of things to look through means searching takes ten thousand times longer, we know we’re probably searching wrong, and should find a better way to do it. If doubling the set of things to look through means we have to take one-and-a-half times as long to find what we want, we’re probably using a good approach.

Greg Evans and Karen Evans’s Luann for the 8th of November builds its joke on the idea that mathematical symbols are funny-looking things you have to interpret, just the same way emojis are. Gunther gives his best shot at explaining the various symbols. The grouping of them makes me wonder exactly what mathematics class he’s taking, though. I can’t think offhand of one that would have all of these in the same textbook.

There’s also an actual mistake right up front. He identifies “(f, g)” as the inner product. The “inner product” is a name we give to a collection of functions, all with different domains but all with the range of real numbers. It allows us to describe a “norm”, or size, of whatever kind of thing we have. It also allows us to describe something that works like an angle between two things, and from it, orthogonality. If we’re looking at vectors, then this inner product is also known as the dot product. The mistake, though, is that the inner product is normally written with angled braces, as <f, g> instead. Normal parentheses usually mean we are giving a set of coordinates or an n-tuple. They can also mean that we are taking a Cartesian product, which looks a lot like giving a set of coordinates or an n-tuple. Probably the writer or artist made an understandable mistake while transcribing notes.

The talk of an inner product suggests more than anything else that the subject is linear algebra. The reference to “Dim(U)” is consistent with this. If U is a matrix, we can talk about its dimension. This is a measure of how many of the rows of the matrix U cannot be made as the sum of scalar products of other rows. That’s useful because it tells us how many of the rows are “linearly independent”, or in a way, tell us something that we can’t get from other rows. So this is linear algebra work.

φ is indeed the Golden Ratio, the number approximately 1.618. It’s a famous number but it’s really got no mathematical significance. Its reciprocal, 1/φ, is about 0.618, and that’s pretty, but that’s all. Many have tried to imbue the Golden Ratio with biological or aesthetic significance, and have failed, because it has none. In mathematics, the Golden Ratio is one of those celebrities who’s famous for no discernable reason or accomplishment.

Δ is the Delta symbol, yes. It’s often used as a shorthand for “change in”. So “Δ x” means “the change in x”. We usually take this to mean a small but noticeable change. If we mean a much smaller change, or a perturbation from what we originally wanted, we might switch to a lowercase “δ x”. If we mean an incredibly tiny change we go to “dx”. This is important in calculus and analysis, as well as in many numerical methods classes.

∝ does mean proportional to. We use it to say one quantity varies as the other one does. For example, that the distance you go in an hour is proportional to how fast you go. Go twice as fast, you go twice as far. This turns up in analysis some, and in applied mathematics that tries to model real-world phenomena. We may be unsure of the precise relationship between two things, but we can say how we expect one thing to affect the other. ∝ is a symbol that lets us talk about qualitative relationships among things.

The equals sign with a triangle above it baffled me, and I had to search about for it. It seems to baffle a modest number of people. Apparently it’s used as a way of saying “is defined as”. That is, the term on the left side of this symbol is by definition equal to whatever appears on the right side. I don’t remember seeing it before, and I don’t get what role it serves that the three-line equals sign ≡ doesn’t already do. I’m not saying the Evanses are wrong to use it, just that it’s not one I’m familiar with.

But you see why I can’t figure what course Gunther is taking. Two of the symbols make sense for linear algebra. One fits in almost anywhere in calculus or applied mathematics. One is mostly an applied mathematics term. One is useless. The last is obscure, anyway. What do they have in common? And what could Tiffany’s message showing a heart-eyed smiley face, pizza, and two check marks mean? “I love to watch pizza voting”?

Dave Kellett’s science fiction/humor comic Drive for the 9th of November reveals the probability of a catastrophe has been mis-reported. The choice of numbers is amusing. It’s hard to have an instinctive feel for the difference between a chance of 1-in-600 and a chance of 1-in-400. The difference makes itself known after a few hundred attempts, at least.

Chris Giarrusso’s absurdist G-Man Webcomics for the 9th of November takes literally the problem of haunting, mysterious shapes.

Gary Wise and Lance Aldrich’s Real Life Adventures asks how to find the area of a trapezoid. I couldn’t dare say.

## Fallacy.

Mathematics is built out of arguments. These are normally logical arguments, sequences of things which we say are true. We know they’re true because either they start from something we assume to be true or because they follow from logical deduction from things we assumed were true. Even calculations are a string of arguments. We start out with an expression we’re interested in, and do things which change the way it looks but which we can prove don’t change whether it’s true.

A fallacy is an argument that isn’t deductively sound. By deductively sound we mean that the premises we start with are true, and the reasoning we follow obeys the rules of deductive logic (omitted for clarity). if we’ve done that, then the conclusion at the end of the reasoning is — and must be — true.

## Reading The Comics, October 20, 2014: No Images This Edition

Since I started including Comics Kingdom strips in my roundups of mathematically-themed strips I’ve been including images of those, because I’m none too confident that Comics Kingdom’s pages are accessible to normal readers after some time has passed. Gocomics.com has — as far as I’m aware, and as far as anyone has told me — no such problems, so I haven’t bothered doing more than linking to them. So this is the first roundup in a long while I remember that has only Gocomics strips, with nothing from Comics Kingdom. It’s also the first roundup for which I’m fairly sure I’ve done one of these strips before.

Guy Endore-Kaiser and Rodd Perry and Dan Thompson’s Brevity (October 15, but a rerun) is an entry in the anthropomorphic-numbers line of mathematics comics, and I believe it’s one that I’ve already mentioned in the past. This particular strip is a rerun; in modern times the apparently indefatigable Dan Thompson has added this strip to the estimated fourteen he does by himself. In any event it stands out in the anthropomorphic-numbers subgenre for featuring non-integers that aren’t pi.

Ralph Hagen’s The Barn (October 16) ponders how aliens might communicate with Earthlings, and like pretty much everyone who’s considered the question mathematics is supposed to be the way they’d do it. It’s easy to see why mathematics is plausible as a universal language: a mathematical truth should be true anywhere that deductive logic holds, and it’s difficult to conceive of a universe existing in which it could not hold true. I have somewhere around here a mention of a late-19th-century proposal to try contacting Martians by planting trees in Siberia which, in bloom, would show a proof of the Pythagorean theorem.

In modern times we tend to think of contact with aliens being done by radio more likely (or at least some modulated-light signal), which makes a signal like a series of pulses counting out prime numbers sound likely. It’s easy to see why prime numbers should be interesting too: any species that has understood multiplication has almost certainly noticed them, and you can send enough prime numbers in a short time to make clear that there is a deliberate signal being sent. For comparison, perfect numbers — whose factors add up to the original number — are also almost surely noticed by any species that understands multiplication, but the first several of those are 6, 28, 496, and 8,128; by the time 8,128 pulses of anything have been sent the whole point of the message has been lost.

And yet finding prime numbers is still not really quite universal. You or I might see prime numbers as key, but why not triangular numbers, like the sequence 1, 3, 6, 10, 15? Why not square or cube numbers? The only good answer is, well, we have to pick something, so to start communicating let’s hope we find something that everyone will be able to recognize. But there’s an arbitrariness that can’t be fully shed from the process.

John Zakour and Scott Roberts’s Maria’s Day (October 17) reminds us of the value of having a tutor for mathematics problems — if you’re having trouble in class, go to one — and of paying them appropriately.

Steve Melcher’s That Is Priceless (October 17) puts comic captions to classic paintings and so presented Jusepe de Ribera’s 1630 Euclid, Letting Me Copy His Math Homework. I confess I have a broad-based ignorance of art history, but if I’m using search engines correctly the correct title was actually … Euclid. Hm. It seems like Melcher usually has to work harder at these things. Well, I admit it doesn’t quite match my mental picture of Euclid, but that would have mostly involved some guy in a toga wielding a compass. Ribera seems to have had a series of Greek Mathematician pictures from about 1630, including Pythagoras and Archimedes, with similar poses that I’ll take as stylized representations of the great thinkers.

Mark Anderson’s Andertoons (October 18) plays around statistical ideas that include expectation values and the gambler’s fallacy, but it’s a good puzzle: has the doctor done the procedure hundreds of times without a problem because he’s better than average at it, or because he’s been lucky? For an alternate formation, baseball offers a fine question: Ted Williams is the most recent Major League Baseball player to have a season batting average over .400, getting a hit in at least two-fifths of his at-bats over the course of the season. Was he actually good enough to get a hit that often, though, or did he just get lucky? Consider that a .250 hitter — with a 25 percent chance of a hit at any at-bat — could quite plausibly get hits in three out of his four chances in one game, or for that matter even two or three games. Why not a whole season?

Well, because at some point it becomes ridiculous, rather the way we would suspect something was up if a tossed coin came up tails thirty times in a row. Yes, possibly it’s just luck, but there’s good reason to suspect this coin doesn’t have a fifty percent chance of coming up heads, or that the hitter is likely to do better than one hit for every four at-bats, or, to the original comic, that the doctor is just better at getting through the procedure without complications.

Ryan North’s quasi-clip-art Dinosaur Comics (October 20) thrilled the part of me that secretly wanted to study language instead by discussing “light verb constructions”, a grammatical touch I hadn’t paid attention to before. The strip is dubbed “Compressed Thesis Comics”, though, from the notion that the Tyrannosaurus Rex is inspired to study “computationally” what forms of light verb construction are more and what are less acceptable. The impulse is almost perfect thesis project, really: notice a thing and wonder how to quantify it. A good piece of this thesis would probably be just working out how to measure acceptability of a particular verb construction. I imagine the linguistics community has a rough idea how to measure these or else T Rex is taking on way too big a project for a thesis, since that’d be an obvious point for the thesis to crash against.

Well, I still like the punch line.

## Odd Proofs

May 2013 turned out to be an interesting month for number theory, in that there’ve been big breakthroughs on two long-standing conjectures. Number theory is great fun in part because it’s got many conjectures that anybody can understand but which are really hard to prove. The one that’s gotten the most attention, at least from the web sites that I read which dip into popular mathematics, has been the one about twin primes.

It’s long been suspected that there are infinitely many pairs of “twin primes”, such as 5 and 7, or 11 and 13, or 29 and 31, separated by only two. It’s not proven that there are such, not yet. Yitang Zhang of Harvard has announced proof that there are infinitely many pairings of primes that are no more than 70,000,000 apart. This is admittedly not the tightest bound out there, but it’s better than what there was before. But while there are infinitely many primes — anyone can prove that — how many there are in any fixed-width range tends to decrease, and it would be imaginable to think that the distance between primes just keeps increasing, without bounds, the way that (say) each pair of successive powers of two is farther apart than the previous pair were. But it’s not so, and that’s neat to see.

Less publicized is a proof of Goldbach’s Odd Conjecture. Goldbach’s Conjecture is the famous one that every even number bigger than two can be written as the sum of two primes. An equivalent form would be to say that every whole number — even or odd — larger than five can be written as the sum of three primes. Goldbach’s Odd Conjecture cuts the problem by just saying that every odd whole number greater than five can be written as the sum of three primes. And it’s this which Harald Andres Helfgott claims to have a proof for. (He also claims to have a proof that every odd number greater than seven can be written as the sum of three odd primes, that is, that two isn’t needed for more than single-digit odd numbers.)

## Reblog: Animated Sieve of Eratosthenes

The Math Less Traveled has a lovely video here, animating the Sieve of Eratosthenes, one of the classic methods of finding all of the prime numbers one wants. I suppose it won’t eliminate writing out and crossing off numbers for extra credit on a math test. I actually remember that being one test I had in, I believe, seventh grade, for reasons that I don’t think I ever got. Possibly the teacher wanted to have an easy time grading, or was giving everyone a break from too much computation by shifting to evaluation of our crossing-out abilities.

Here’s something I made yesterday! (Note, I strongly suggest watching it fullscreen, in HD if you have the bandwidth for it.)

Can you figure out what’s going on? The source code for the animation is here; I was inspired by Jason Davies’ visualization which was in turn inspired by this.

View original post

## Reblog: Factorization diagrams

The Math Less Traveled over here shows off a lovely way of visualizing the factoring of integers by putting them into patterns inspired by the regular polygons. Some numbers factor into wonderfully obvious patterns; some turn into muddles of dots because integers just work that way. They’re all attractive ways to look at numbers, though.

In an idle moment a while ago I wrote a program to generate "factorization diagrams". Here’s 700:

It’s easy to see (I hope), just by looking at the arrangement of dots, that there are $latex 7 \times 5 \times 5 \times 2 \times 2$ in total.

Here’s how I did it. First, a few imports: a function to do factorization of integers, and a library to draw pictures (yes, this is the library I wrote myself; I promise to write more about it soon!).

>moduleFactorizationwhere>>importMath.NumberTheory.Primes.Factorisation(factorise)>>importDiagrams.Prelude>importDiagrams.Backend.Cairo.CmdLine>>typePicture=DiagramCairoR2

The primeLayout function takes an integer n (assumed to be a prime number) and some sort of picture, and symmetrically arranges n copies of the picture.

View original post 583 more words


text:
# Generalized likelihood ratio to Probability estimate

I implemented a generalized likelihood ratio test (GLRT) detector/identifier. The result of the identification step results in a score for each of the objects to be identified in an ordered list. The ratio values are log of a ratio number.

Is there a way to compute an estimate of the probability/confidence of similarity in that estimate ?

• well, the values should be monotonous with confidence. The conversion from log-likelihoods (or ratios thereof) to likelihoods depends on the distribition of error. Jul 28 at 19:42
• Can you write down the closed-form expression of the GLRT? Jul 30 at 4:25

format: plain


text:
# Where are the multi-qubit openpulse computers?

As the question says, I'm looking to run some pulse schedules on quantum computers. Right now, I'm really only able to find ibmq_armonk (from IBM) to be an openpulse computer that I am able to use. I've found some papers that mentioned running pulse schedules on ibmq_toronto and ibmq_montreal, but IBMQ doesn't seem to identify them to support OpenPulse when applying the filters (though, this may just be because I'm on an unpaid account). Does anyone have any recommendations? I'm looking for both paid and unpaid services.

You can check out the backends with pulse support in the table view of IBM service list, after signing in:

Programmatically, you can list the backends with pulse support you have access to with Qiskit in the following way:

from qiskit import IBMQ

You can add the n_qubits >= 2 condition in the filter to add the multi-qubit part, like this:
provider.backends(filters=lambda b:


text:
# proving a natural projection is linear and finding its kernel

Let $V_i = 1,...,N$ be a collection of vector spaces over a field $F$. Consider the Cartesian product $V=V_1 \times V_2 \times ... \times V_N$ with the natural projections $\pi=V \rightarrow V_i$. Prove that $\pi$ is linear and compute its kernel.

I am pretty confused as to what I need to do for this question. So far I've chosen an arbitrary basis for $V$ but I don't know what to do after that.

Elements of $V$ can be written as $(v_1,\dots,v_n)$ for $v_i\in V_i$. If you want to show that $\pi$ is linear, you need to show that for any $v=(v_1,\dots,v_n),w=(w_1,\dots,w_n)\in V$ and any scalar $\alpha\in F$, $$\pi(\alpha v+w)=\alpha \pi(v)+\pi(w).$$ This should follow from a quick computation, using the fact that $$\alpha(v_1,\dots,v_n)+(w_1,\dots,w_n)=(\alpha v_1+w_1,\dots,\alpha v_n+w_n).$$ As for finding the kernel, by definition $$\ker{\pi}=\{(v_1,\dots,v_n)\in V\mid \pi(v_1,\dots,v_n)=0\}.$$ But this is just any vector with $v_i=0$.
So the question wants you to show that the map $\phi_i : (v_1, v_2, ..., v_n) \rightarrow v_i$ is linear and to find the kernel of each one. Now, we can certainly take a basis for the product by taking, in each coordinate, a basis for the factor spaces. Then, just show that $a\phi_i(v) = \phi_i(av)$. This amounts to checking that scaling commutes into the coordinates i.e. $a(v_1, v_2, \ldots, vn) = (av_1, av_2, \ldots, av_n)$. Similarly, just check that adding two vectors will commute with your projection maps. Then, as for the kernel, when is $(v_1, v_2, \ldots, v_n) \rightarrow v_i = 0$? That shouldn't be too difficult to see.


text:
# Fundamental group of Klein Bottle generated by two elements

The problem asks me to show that the fundamental group of the Klein bottle is generated by "latitudinal" loops $a$ and "longitudinal" loops $b$ where $a$ and $b$ obey the relation $aba^{-1} = b^{-1}$.

The problem is that I don't understand what I'm supposed to do, since the problem is stated a bit imprecisely. I haven't covered the Seifert-Van Kampen theorem either.

-

Draw a short cartoon that shows the loop $aba^{-1}$ homotoping into $b^{-1}$, in the squares-with-edges-identified model.

For clarity, let the loop cross the corners one at a time, and be sure to indicate the direction of every visible segment of the loop in each frame.

(Writing down the homotopy symbolically, with coordinates, would probably be overkill).

-

Hint: you can obtain the Klein bottle from the unit square identifying its edges accordingly.

The blue one is $a$ and the red one is $b$.

-
Yes, I know that the Klein bottle is the unit square with opposite vertical edges identified in the same direction, and opposite horizontal edges identified in the opposite direction. –  user61642 Feb 10 '13 at 0:05


text:
Euler-Maclaurin formula and Riemann-Roch - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-25T05:53:33Z http://mathoverflow.net/feeds/question/10667 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/10667/euler-maclaurin-formula-and-riemann-roch Euler-Maclaurin formula and Riemann-Roch VA 2010-01-04T05:10:05Z 2012-12-14T02:25:23Z
Let $Df$ denote the derivative of a function $f(x)$ and $\bigtriangledown f=f(x)-f(x-1)$ be the discrete derivative. Using the Taylor series expansion for $f(x-1)$, we easily get $\bigtriangledown = 1- e^{-D}$ or, by taking the inverses, $$\frac{1}{\bigtriangledown} = \frac{1}{1-e^{-D}} = \frac{1}{D}\cdot \frac{D}{1-e^{-D}}= \frac{1}{D} + \frac12+ \sum_{k=1}^{\infty} B_{2k}\frac{D^{2k-1}}{(2k)!} ,$$ where $B_{2k}$ are Bernoulli numbers.

(Edit: I corrected the signs to adhere to the most common conventions.)

Here, $(1/D)g$ is the opposite to the derivative, i.e. the integral; adding the limits this becomes a definite integral $\int_0^n g(x)dx$. And $(1/\bigtriangledown)g$ is the opposite to the discrete derivative, i.e. the sum $\sum_{x=1}^n g(x)$. So the above formula, known as Euler-Maclaurin formula, allows one, sometimes, to compute the discrete sum by using the definite integral and some error terms.

Usually, there is a nontrivial remainder in this formula. For example, for $g(x)=1/x$, the remainder is Euler's constant $\gamma\simeq 0.57$. Estimating the remainder and analyzing the convergence of the power series is a long story, which is explained for example in the nice book "Concrete Mathematics" by Graham-Knuth-Patashnik. But the power series becomes finite with zero remainder if $g(x)$ is a polynomial. OK, so far I am just reminding elementary combinatorics.

Now, for my question. In the (Hirzebruch/Grothendieck)-Riemann-Roch formula one of the main ingredients is the Todd class which is defined as the product, going over Chern roots $\alpha$, of the expression $\frac{\alpha}{1-e^{-\alpha}}$. This looks so similar to the above, and so suggestive (especially because in the Hirzebruch's version $$\chi(X,F) = h^0(F)-h^1(F)+\dots = \int_X ch(F) Td(T_X)$$ there is also an "integral", at least in the notation) that it makes me wonder: is there a connection?

The obvious case to try (which I did) is the case when $X=\mathbb P^n$ and $F=\mathcal O(d)$. But the usual proof in that case is a residue computation which, to my eye, does not look anything like Euler-Maclaurin formula.

But is there really a connection?

An edit after many answers: Although the connection with Khovanskii-Pukhlikov's paper and the consequent work, pointed out by Dmitri and others, is undeniable, it is still not obvious to me how the usual Riemann-Roch for $X=\mathbb P^n$ and $F=\mathcal O(d)$ follows from them. It appears that one has to prove the following nontrivial

Identity: The coefficient of $x^n$ in $Td(x)^{n+1}e^{dx}$ equals $$\frac{1}{n!} Td(\partial /\partial h_0) \dots Td(\partial /\partial h_n) (d+h_0+\dots + h_n)^n |_{h_0=\dots h_n=0}$$

A complete answer to my question would include a proof of this identity or a reference to where this is shown. (I did not find it in the cited papers.) I removed the acceptance to encourage a more complete explanation.
 http://mathoverflow.net/questions/10667/euler-maclaurin-formula-and-riemann-roch/10691#10691 Answer by Dmitri for Euler-Maclaurin formula and Riemann-Roch Dmitri 2010-01-04T10:42:25Z 2010-01-04T12:04:52Z
As far as I understand this connection was observed (and generalised) by Khovanskii and Puhlikov in the article

A. G. Khovanskii and A. V. Pukhlikov, A Riemann-Roch theorem for integrals and sums of quasipolynomials over virtual polytopes, Algebra and Analysis 4 (1992), 188–216, translation in St. Petersburg Math. J. (1993), no. 4, 789–812.

This is related to toric geometry, for which some really well written introduction articles are contained on the page of David Cox http://www3.amherst.edu/~dacox/

Since 1992 many people wrote on this subject, for example

EXACT EULER MACLAURIN FORMULAS FOR SIMPLE LATTICE POLYTOPES

http://arxiv.org/PS_cache/math/pdf/0507/0507572v2.pdf

Or Riemann sums over polytopes http://arxiv.org/PS_cache/math/pdf/0608/0608171v1.pdf
 http://mathoverflow.net/questions/10667/euler-maclaurin-formula-and-riemann-roch/10696#10696 Answer by Ilya Nikokoshev for Euler-Maclaurin formula and Riemann-Roch Ilya Nikokoshev 2010-01-04T11:42:20Z 2010-01-04T15:11:02Z
Yes, this is a big area of research. I'll add some references to the ones Dmitri provides.

Here are references from a question about Moment map for toric actions:

Riemann-Roch for toric orbifolds by Victor Guillemin

to learn about toric geometry, draft of a book Toric Varieties by Cox et al

More on the topic itself:

Riemann sums over polytopes by Victor Guillemin and Shlomo Sternberg

Exact Euler Maclaurin formulas for simple lattice polytopes by Shlomo Sternberg et al.

the original paper by Pukhlikov and Khovanskii (page in English, full text in Russian)

A series of papers on arXiv by Michèle Vergne, especially:

Residues formulae for volumes and Ehrhart polynomials of convex polytopes, arXiv:math/0103097

Local Euler-Maclaurin formula for polytopes, arXiv:math/0507256

Paradan's wall crossing formula for partition functions and Khovanski-Pukhlikov differential operator

Also papers by Brion and Vergne, which seem to be missing from arXiv (Google Scholar, thanks to Steve).
 http://mathoverflow.net/questions/10667/euler-maclaurin-formula-and-riemann-roch/10699#10699 Answer by John Mangual for Euler-Maclaurin formula and Riemann-Roch John Mangual 2010-01-04T12:10:46Z 2010-01-04T12:10:46Z
Last year, Leonhard Euler posted a note, Finding the sum of any series from a given general term on the arXiv. In recent years, this idea has been extended to sums over lattice approximations of convex polytopes $\Delta \cap \mathbb{Z}^n$ as shown in the other responses.
 http://mathoverflow.net/questions/10667/euler-maclaurin-formula-and-riemann-roch/10703#10703 Answer by Steve Huntsman for Euler-Maclaurin formula and Riemann-Roch Steve Huntsman 2010-01-04T14:25:58Z 2010-01-12T02:20:57Z
I thought I'd give a more explicit answer showing how the Todd class appears. Let $Td(x) := \frac{x}{1-e^{-x}} = -\sum_{j=0}^\infty B_j \frac{x^j}{j!}$. Now for $a,b \in \mathbb{Z}$, $z \in \mathbb{R}$, $|z| << 1$, we have that $Td(\partial_h)e^{hz} = -\sum_{j=0}^\infty B_j \frac{\partial_h^{(j)}}{j!}e^{hz} = -\sum_{j=0}^\infty B_j \frac{z^j}{j!}e^{hz} = Td(z)e^{hz}$. So

$Td(\partial_g)|_{g=0} Td(\partial_h)|_{h=0} \int_{a-g}^{b+h} e^{xz} dx$

$= Td(\partial_g)|_{g=0} Td(\partial_h)|_{h=0} \frac{e^{(b+h)z} - e^{(a-g)z}}{z}$

$= \frac{Td(z)e^{bz} - Td(-z)e^{az}}{z} = \frac{e^{bz}}{1-e^{-z}} + \frac{e^{az}}{1-e^z}$

$= \sum_{k=a}^b e^{kz}$.

It follows for suitable functions $f$ (as VA pointed out below) that $\sum_{k=a}^b f(k) = Td(\partial_g)|_{g=0} Td(\partial_h)|_{h=0} \int_{a-g}^{b+h} f(x) dx$.

As far as references:

Brion and Vergne give a good treatment of the problem. Their key paper is available at http://www.jstor.org/pss/2152855

Ewald's introduction to toric varieties takes place in the context of convex polytopes and is more concrete than others (e.g., Fulton): see http://books.google.com/books?id=bz8SfJId3BgC

[PPS--I used this work to complete a structure theory for the equilibrium hybridization thermodynamics of DNA about 7 or 8 years ago: see http://mathoverflow.net/questions/10493/the-matrix-tree-theorem-for-weighted-graphs/10500#10500]
 http://mathoverflow.net/questions/10667/euler-maclaurin-formula-and-riemann-roch/12138#12138 Answer by VA for Euler-Maclaurin formula and Riemann-Roch VA 2010-01-17T20:30:24Z 2010-01-17T23:06:13Z
Euler-Maclaurin's formula transforms the integral $I=\int_a^b f(x)dx$ into the finite sum $S=\sum_a^b f(x)$, for two integers $a,b$. As Dmitri pointed out, in 1993 Khovanskii and Pukhlikov gave a multi-dimensional generalization of Euler-Maclaurin which, in particular says the following:

Let $P$ be an $n$-dimensional polytope in $\mathbb R^n\supset\mathbb Z^n$ with integral vertices, and further assume that $P$ defines a nonsingular toric variety (i.e. $P$ is simplicial and at every vertex the integral generators of the edges give a basis in $\mathbb Z^n$). Let us say the facets of $P$ are defined by the inequalities $l_j(x)\le a_j$ for some primitive integral linear functions $l_j(x_1,\dots,x_n)$. Denote by $P(h)$ the polytope defined by the inequalities $l_j(x)\le a_j+h_j$. Finally, let $$I(f,h)= \int_{P(h)} f(x)dx, \quad S(f)= \int_{P\cap \mathbb Z^n} f(x).$$ Then for any quasipolynomial $f(x)$ (a sum of products of polynomial and exponential functions) one has $$S(f) = \prod_j Td(\partial / \partial h_j)\ I(f,h)\ |_{h_j=0}.$$

Here is how the Hirzebruch-Riemann-Roch for the sheaf $\mathcal F=\mathcal O(d)$ on $X=\mathbb P^n$ follows from the Khovanskii-Pukhlikov's version of Euler-Maclaurin's formula:

Taking $P$ to be a simplex of side $d$ and $f(x)=1$, the Khovanskii-Pukhlikov's formula gives $$h^0(\mathbb P^n, \mathcal O(d)) = \prod_{j=0}^n Td(\partial/\partial h_j) \frac{(d+h_0+\dots+h_n)^n}{n!} \ |_{h_j=0}$$ which by making a substitution $y=d+h_0+\dots+h_n$ transforms into $Td(\partial/\partial y)^{n+1} (y^n/n!)\ |_{y=d}.$

The usual Hirzebruch-Riemann-Roch, on the other hand, says that $h^0(\mathbb P^n,\mathcal O(d))$ is the coefficient of $x^n$ in the expression $Td(x)^{n+1} e^{dx}$. So why is this the same? Because $$Td(x)^{n+1} e^{dx} = Td(\partial/ \partial y)^{n+1} e^{yx}\ |_{y=d}$$ (here we used the fact that $(\partial/ \partial y)^k e^{yx} = x^k e^{yx}$) and the coefficient of $x^n$ in $e^{yx}$, expanded as a power series in $x$, is $(y^n/n!)$. QED

Now that wasn't so hard, but why isn't this written somewhere? Or am I missing a reference?
 So what does this suggest conceptually about the meaning of Hirzebruch-Riemann-Roch? I think, clearly, it suggests that

The pushforward $$f_!:K(X)\to K(pt)=\mathbb Z, \qquad \mathcal F\mapsto \chi(\mathcal F) = h^0(F)-h^1(F)+\dots$$ between the K-groups should be considered to be the "discrete summation" of a "function" $f=f(\mathcal F)$. Indeed, for say a toric variety $X$ and an ample line bundle $\mathcal F$ we are just counting integral points in a polytope $P$. So that fits.

The pushforward $$f_*: A(X)_Q\to A(pt)_Q=\mathbb Q$$ between the Chow groups should be considered to be a "continuous" version, an integral. Indeed, for a cycle on $X$ its pushforward can be interpreted as, and computed by, an integral of a corresponding differential form. So this makes perfect sense as well.

So now the Riemann-Roch, = the Euler-Maclaurin for this situation, transforms the integral into the sum, by multiplying it by the differential operator given by the Todd class. This also explains why in HRR the Todd class of $T_X$ appears and not, say, of $\Omega^1_X$. The tangent bundle is the place where the derivations $\partial/\partial z$ live.
 http://mathoverflow.net/questions/10667/euler-maclaurin-formula-and-riemann-roch/116339#116339 Answer by Roman for Euler-Maclaurin formula and Riemann-Roch Roman 2012-12-14T02:25:23Z 2012-12-14T02:25:23Z
I was about to post the same question and came across yours. I wasn't aware of the "toric" direction here that other people have referred to, but I know a pretty answer in the particular case when $X$ is the flag variety of a semi-simple algebraic group. In this case RR reduces to saying that $\chi(F)={\mathrm{const}} \int ch(F\otimes L^{-1})$ where $L$ is the square root of the canonical class and the constant is explicit. So in this case at least multiplication by Todd does amount to shift (by half-forms) as in Euler-Maclaurin formula. Furthermore, in this form the formula has a very short proof via characteristic $p$, deducing it from the fact that $Fr_*(L)=L^{p^d}$, $d=\dim(X)$.

[Well, in fact it also follows from Weyl dimension formula which of course has many other proofs, I just happen to like this char p proof.] It would be cool to have a proof of the general case along these lines. Something related has been done by Pink and Rossler, arXiv:0812.0254.


text:
### The Complexity of Approximating Bounded-Degree Boolean #CSP

Martin Dyer, Leslie Ann Goldberg, Markus Jalsenius & David Richerby
The degree of a CSP instance is the maximum number of times that a variable may appear in the scope of constraints. We consider the approximate counting problem for Boolean CSPs with bounded-degree instances, for constraint languages containing the two unary constant relations $\{0\}$ and $\{1\}$. When the maximum degree is at least $25$ we obtain a complete classification of the complexity of this problem. It is exactly solvable in polynomial-time if every relation in...
This data center is not currently reporting usage information. For information on how your repository can submit usage information, please see our Documentation.