At Uncertain Principles and Unqualified Offerings there has been talk about how students in disciplines where the numbers come with units seem to be conditioned to expect numbers of order unity. (And so are professional scientists, who deal with this by defining appropriate units.)
Mathematicians, of course, don't have this luxury. But we are conditioned to think, perhaps, that rational numbers are better than irrational ones, that algebraic numbers are better than transcendental ones (except maybe π and e), and so on. In my corner of mathematics (discrete probability/analysis of algorithms/combinatorics), often sequences of integers a(1), a(2), ... arise and you want to know approximately how large the nth term is. For example, the nth Fibonacci number is approximately φn/51/2, where φ = (1+51/2)/2 is the "golden ratio". The nth Catalan number (another sequence that arises often) is approximately 4n/(π n3)1/2. In general, "many" sequences turn out to satisfy something like
a(n) ~ p qn (log n)r ns
where p, q, r, and s are constants. There are deep reasons for this that can't fully be explained in a blog post, but have to do with the fact that a(n) often has a generating function of a certain type. What's surprising is that while p and q are often irrational, r and s are almost never irrational, at least for sequences that arise in the "real world". Furthermore, they usually tend to be "simple" rational numbers -- 3/2, not 26/17. If you told me some sequence of numbers grows like πn I'd be interested. If you told me some sequence of numbers grows like nπ. I'd assume I misheard you. Of course, there's the possibility of sampling bias -- I think that the exponents tend to be rational because if they weren't rational I wouldn't know what to do! They do occur -- for example, consider the Hardy-Ramanujan asymptotic formula for the number of partitions p(n) of an integer n:
p(n) ~ exp(π (2n/3)1/2)/(4n √3)).
I know this exists, but it still just looks weird.
(This is an extended version of a comment I left at Uncertain principles.)
Showing posts with label partitions. Show all posts
Showing posts with label partitions. Show all posts
06 March 2009
19 November 2007
Abusive dimensions and cohomology of Grassmannians
Yesterday I complained about the abuse of the word "dimension" by a lot of popular authors, namely the fact that they tried to order the dimensions.
Being a discrete mathematician, I don't think about dimensions all that often. But I'm taking a course in algebraic topology (it's required for my program); I have a habit of trying to twist the problems there into combinatorics problems whenever possible. Recently we were asked to compute the cohomology of the Grassmannian manifold GnRk. This Grassmannian is just the manifold of n-dimensional subspaces of k-dimensional space passing through the origin. It is of dimension k(n-k), as we can see by "dimension-counting". To obtain such a subspace we pick n orthogonal unit vectors in k-space. The first one is chosen from Sk-1 and thus we have k-1 "degrees of freedom", contributing k-1 to the dimension. The second one is chosen from a (k-2)-sphere in the (k-1)-dimensional orthogonal complement of this first vector; this contributes k-2 dimensions. And so on, down to k-n dimensions for the nth vector. But we've overcounted by 1 + 2 + ... + n-1, since we've actually chosen an n-dimensional flag in k dimensions; thus we need to quotient out by the orthogonal group SO(n), which has this dimension. Thus the dimension of the Grassmanian is
[(k-1) + (k-2) + ... + (k-n)] - [0 + 1 + ... + (n-1)] = n(k-n).
As you may have noticed, I used "dimension" in two senses there; the rigorous sense of the topological invariant which is always an integer, and the non-rigorous sense of "degree of freedom". At this point my complaint from yesterday is still valid, because I never ordered the dimensions, and that was the cardinal sin I attributed to people who don't know what they're talking about.
But then I caught myself saying things like "the cohomology of G2R5 in the second dimension is Z2." That's no good.
As it turns out, I rediscovered the fact that the dimension of Hm(GnRk) is the number of integer partitions of m into at most k-n parts, none of which exceed n; in the case I just mentiond we have m = 2, n = 2, k = 5, so we're looking for integer partitions of 2 into 2 parts which don't exceed 3. There are two of them, namely 2 and 1 + 1. This isn't too interesting, but say we want to know, for example, the dimension of H9(G3R10)? Then we can just write down all the partitions of 9 into three parts which are at most 7;
7+2+0, 7+1+1, 6+3+0, 6+2+1, 5+4+0, 5+3+1, 5+2+2, 4+4+1, 4+3+2, 3+3+3
and there are ten of them; thus H9(G3R10) = Z10. You can write down generating functions for these sequences of integers; I suppose one could even ask about the asymptotic behavior of these dimensions, although I don't think a topologist would care. (I can't find a source for this fact, but I'm actually pretty sure I've heard it before; the two obvious sources to me were Hatcher's Algebraic Topology and Stanley's Enumerative Combinatorics, which are both books I know reasonably well, and I found the place in each where this should be mentioned. Stanley just says that there is a connection to the cohomology of the Grassmannian and leaves it at that; Hatcher talks about symmetric polynomials but never sinks to finding actual numbers.)
But as I said, I caught myself saying things like "what's the second-dimensional cohomology of G2R5"? Second-dimensional. And I've heard this usage from Real Algebraic Topologists, too. So apparently what was bothering me yesterday was something more subtle than this abuse of language.
Being a discrete mathematician, I don't think about dimensions all that often. But I'm taking a course in algebraic topology (it's required for my program); I have a habit of trying to twist the problems there into combinatorics problems whenever possible. Recently we were asked to compute the cohomology of the Grassmannian manifold GnRk. This Grassmannian is just the manifold of n-dimensional subspaces of k-dimensional space passing through the origin. It is of dimension k(n-k), as we can see by "dimension-counting". To obtain such a subspace we pick n orthogonal unit vectors in k-space. The first one is chosen from Sk-1 and thus we have k-1 "degrees of freedom", contributing k-1 to the dimension. The second one is chosen from a (k-2)-sphere in the (k-1)-dimensional orthogonal complement of this first vector; this contributes k-2 dimensions. And so on, down to k-n dimensions for the nth vector. But we've overcounted by 1 + 2 + ... + n-1, since we've actually chosen an n-dimensional flag in k dimensions; thus we need to quotient out by the orthogonal group SO(n), which has this dimension. Thus the dimension of the Grassmanian is
[(k-1) + (k-2) + ... + (k-n)] - [0 + 1 + ... + (n-1)] = n(k-n).
As you may have noticed, I used "dimension" in two senses there; the rigorous sense of the topological invariant which is always an integer, and the non-rigorous sense of "degree of freedom". At this point my complaint from yesterday is still valid, because I never ordered the dimensions, and that was the cardinal sin I attributed to people who don't know what they're talking about.
But then I caught myself saying things like "the cohomology of G2R5 in the second dimension is Z2." That's no good.
As it turns out, I rediscovered the fact that the dimension of Hm(GnRk) is the number of integer partitions of m into at most k-n parts, none of which exceed n; in the case I just mentiond we have m = 2, n = 2, k = 5, so we're looking for integer partitions of 2 into 2 parts which don't exceed 3. There are two of them, namely 2 and 1 + 1. This isn't too interesting, but say we want to know, for example, the dimension of H9(G3R10)? Then we can just write down all the partitions of 9 into three parts which are at most 7;
7+2+0, 7+1+1, 6+3+0, 6+2+1, 5+4+0, 5+3+1, 5+2+2, 4+4+1, 4+3+2, 3+3+3
and there are ten of them; thus H9(G3R10) = Z10. You can write down generating functions for these sequences of integers; I suppose one could even ask about the asymptotic behavior of these dimensions, although I don't think a topologist would care. (I can't find a source for this fact, but I'm actually pretty sure I've heard it before; the two obvious sources to me were Hatcher's Algebraic Topology and Stanley's Enumerative Combinatorics, which are both books I know reasonably well, and I found the place in each where this should be mentioned. Stanley just says that there is a connection to the cohomology of the Grassmannian and leaves it at that; Hatcher talks about symmetric polynomials but never sinks to finding actual numbers.)
But as I said, I caught myself saying things like "what's the second-dimensional cohomology of G2R5"? Second-dimensional. And I've heard this usage from Real Algebraic Topologists, too. So apparently what was bothering me yesterday was something more subtle than this abuse of language.
15 November 2007
Asymptotics of partition polynomials
I've previously mentioned Richard Stanley's page of interesting zeros of polynomials. For an example of this in action, you can see a couple papers which were justed posted to the arXiv, by Robert P. Boyer and William M. Y. Goh:
Partition Polynomials: Asymptotics and Zeros
Polynomials associated with Partitions: Their Asymptotics and Zeros
In the first paper, we take the polynomial which counts the partitions of n by number of parts; when n = 200 the zeroes of this polynomial are plotted at Richard Stanley's web site. What's surprising is that the zeroes are actually a good bit more subtle than they'd look from that picture; they come in three families, the third of which doesn't appear until n = 13,000.
The second paper makes a similar conjecture for the zeroes of the "rank polynomial" and "crank polynomial" of high degree, where partitions are counted by their rank (the difference between the largest part and the number of parts) or the crank (see p. 11 for definition). (In the rank case, at least, Boyer and Goh actually just count partitions with positive rank; by conjugation one can get those with negative rank.) The zeroes of the rank polynomial appear to lie approximately on the unit circle, and are spread out uniformly.
By the way, I've previously credited this idea of looking at the zeros of combinatorially defined polynomials to Stanley. Apparently it's actually due to Rota, who once said:
Rota was Stanley's thesis advisor.
Partition Polynomials: Asymptotics and Zeros
Polynomials associated with Partitions: Their Asymptotics and Zeros
In the first paper, we take the polynomial which counts the partitions of n by number of parts; when n = 200 the zeroes of this polynomial are plotted at Richard Stanley's web site. What's surprising is that the zeroes are actually a good bit more subtle than they'd look from that picture; they come in three families, the third of which doesn't appear until n = 13,000.
The second paper makes a similar conjecture for the zeroes of the "rank polynomial" and "crank polynomial" of high degree, where partitions are counted by their rank (the difference between the largest part and the number of parts) or the crank (see p. 11 for definition). (In the rank case, at least, Boyer and Goh actually just count partitions with positive rank; by conjugation one can get those with negative rank.) The zeroes of the rank polynomial appear to lie approximately on the unit circle, and are spread out uniformly.
By the way, I've previously credited this idea of looking at the zeros of combinatorially defined polynomials to Stanley. Apparently it's actually due to Rota, who once said:
The one contribution of mine that I hope will be remembered has consisted in just pointing out that all sorts of problems of combinatorics can be viewed as problems of location of the zeros of certain polynomials and in giving these zeros a combinatorial interpretation. This is now called the critical problem. Over the years people have added examples of critical problems, though we still haven't gotten any idea of how to solve it in general. I'd like to see someone get such an idea before I die. The four-color conjecture-that with only four colors you can color every planar map so that no two adjacent regions have the same color-is one of these critical problems.
Rota was Stanley's thesis advisor.
29 October 2007
Enumerating multiset partitions
Brent Yorgey on enumerating multiset partitions. He came to the problem the same way I did -- I was trying to count the number of factorizations of an integer. An integer of the form pn, where p is a prime, has p(n) factorizations, where p(n) is the partition function; for example
giving the p(5) = 7 factorizations of p5. An integer of the form p1p2...pn has Bn factorizations (the nth Bell number); for example, 2310 = (2)(3)(5)(7)(11) has fifty-two factorizations. But what about, say, an integer of the form p3qr? How many factorizations does it have? Naturally, this associates an integer with each partition; from the number p5 we get the partition 5 and the number of factorizations 15; from the number p1p2p3p4p5 we get the partition 1 + 1 + 1 + 1 + 1 we associate 52.
Unfortunately, I don't really follow Yorgey's work because I don't know Haskell. And I don't know a general way to compute these yet, except in the trivial cases. But, for example, p2 q has four factorizations:
(p2q) = (p2)(q) = (p)(pq) = (p)(p)(q)
and so we associate to 2 + 1 the number 4; this is intermediate between p(3) (which is 3) and B3 (which is 5). This makes sense; in general p(n) counts the number of partitions of {1, ..., n} when no elements are distinguishable, and Bn when all elements are distinguishable. Multiset partitions interpolate between integer partitions and set partitions.
(Yorgey says that the problem is also solved in Volume 4, Fascicle 3 of Knuth, which I may track down. But I want the pleasure of working this out for myself, to some extent.)
Yorgey also says that he found the problem via Project Euler, which gives a couple hundred examples of problems that can, in general, be solved by ridiculously inefficient brute force methods or by elegant methods that require not so much computation.
giving the p(5) = 7 factorizations of p5. An integer of the form p1p2...pn has Bn factorizations (the nth Bell number); for example, 2310 = (2)(3)(5)(7)(11) has fifty-two factorizations. But what about, say, an integer of the form p3qr? How many factorizations does it have? Naturally, this associates an integer with each partition; from the number p5 we get the partition 5 and the number of factorizations 15; from the number p1p2p3p4p5 we get the partition 1 + 1 + 1 + 1 + 1 we associate 52.
Unfortunately, I don't really follow Yorgey's work because I don't know Haskell. And I don't know a general way to compute these yet, except in the trivial cases. But, for example, p2 q has four factorizations:
(p2q) = (p2)(q) = (p)(pq) = (p)(p)(q)
and so we associate to 2 + 1 the number 4; this is intermediate between p(3) (which is 3) and B3 (which is 5). This makes sense; in general p(n) counts the number of partitions of {1, ..., n} when no elements are distinguishable, and Bn when all elements are distinguishable. Multiset partitions interpolate between integer partitions and set partitions.
(Yorgey says that the problem is also solved in Volume 4, Fascicle 3 of Knuth, which I may track down. But I want the pleasure of working this out for myself, to some extent.)
Yorgey also says that he found the problem via Project Euler, which gives a couple hundred examples of problems that can, in general, be solved by ridiculously inefficient brute force methods or by elegant methods that require not so much computation.
16 October 2007
Polynomials with interesting sets of zeros
Polynomials with interesting sets of zeros, from Richard Stanley.
There are certain polynomials which are naturally defined in terms of combinatorial objects, which have interesting sets of zeros. For example, consider the polynomials
F1(x) = x
F2(x) = x + x2
F3(x) = x + x2 + x3
F4(x) = x + 2x2 + x3 + x4
F5(x) = x + 2x2 + 2x3 + x4 + x5
where the xk coefficient of Fn(x) is the number of partitions of n into k parts, that is, the number of ways to write n as a sum of k integers where order doesn't matter. For example, the partitions of 5 are
5, 4+1, 3+2, 3+1+1, 2+2+1, 2+1+1+1, 1+1+1+1+1
which have 1, 2, 2, 3, 3, 4, and 5 parts respectively; that's where F5 comes from. It turns out that if you take Fn for large n and plot its zeros in the complex plane, you get a nice-looking figure; see this PDF file. This is true of other combinatorially defined families of polynomials as well. The zeroes of this particular set of polynomials are given in some recent work of Robert Boyer and William Goh. (Boyer gave a talk today at Temple which I went to, hence why this is on my mind lately; I'd actually heard about this phenomenon when I took a class from Stanley as an undergrad.)
At least in the case of the partitions, it seems noteworthy that if we sum yn Fn(x) over all n, getting the generating function of all partitions by size and number of parts, we have something nice, namely
and a lot of the other sets of polynomials described by Stanley can probably be described similarly. (Boyer and Goh allude to this at the end of their expository paper.) I don't know enough analytic number theory to say something intelligent about this, though; the proof that the pictures keep looking "like that" (in the case of partition) apparently uses some very heavy machinery.
There are certain polynomials which are naturally defined in terms of combinatorial objects, which have interesting sets of zeros. For example, consider the polynomials
F1(x) = x
F2(x) = x + x2
F3(x) = x + x2 + x3
F4(x) = x + 2x2 + x3 + x4
F5(x) = x + 2x2 + 2x3 + x4 + x5
where the xk coefficient of Fn(x) is the number of partitions of n into k parts, that is, the number of ways to write n as a sum of k integers where order doesn't matter. For example, the partitions of 5 are
5, 4+1, 3+2, 3+1+1, 2+2+1, 2+1+1+1, 1+1+1+1+1
which have 1, 2, 2, 3, 3, 4, and 5 parts respectively; that's where F5 comes from. It turns out that if you take Fn for large n and plot its zeros in the complex plane, you get a nice-looking figure; see this PDF file. This is true of other combinatorially defined families of polynomials as well. The zeroes of this particular set of polynomials are given in some recent work of Robert Boyer and William Goh. (Boyer gave a talk today at Temple which I went to, hence why this is on my mind lately; I'd actually heard about this phenomenon when I took a class from Stanley as an undergrad.)
At least in the case of the partitions, it seems noteworthy that if we sum yn Fn(x) over all n, getting the generating function of all partitions by size and number of parts, we have something nice, namely
and a lot of the other sets of polynomials described by Stanley can probably be described similarly. (Boyer and Goh allude to this at the end of their expository paper.) I don't know enough analytic number theory to say something intelligent about this, though; the proof that the pictures keep looking "like that" (in the case of partition) apparently uses some very heavy machinery.
06 October 2007
Some partition identities due to Euler
I wrote a couple weeks ago about my love of the identity
which is an analytic version of the fact that every integer is uniquely a sum of distinct powers of 2. What I didn't realize at the time, but learned from George Andrews article Euler's "De Partitio Numerorum", in the current issue (Vol. 44, No. 4) of the Bulletin of the American Mathematical Society, is that this is due to Euler. This is hardly surprising, though, as Euler was as far as I know the first person to apply generating functions to partitions. (The result was known before that; it's the generating-function statement that's due to Euler.)
But here's one I didn't know:
This is an analytic version of the fact that every integer is uniquely a sum of distinct powers of 3 and their negatives, and is Theorem 4 of the Andrews paper. For example, 1 = 1, 2 = 3-1, 3 = 3, 4 = 3+1, 5 = 9-3+1, 6 = 9-3, 7 = 9-3+1, and so on.
To see this fact combinatorially, note that we can make 3k sums out of the numbers 30, 31, ..., 3k-1; for each of these we include the number, its negative, or neither. If we can show that these are the distinct integers from -l to l, where l = (3k-1)/2, then that's enough. (For example, when k = 2, we have l = 4, and the nine possible sums of 1, 3, and their negatives are
-3-1, -3, -3+1, -1, 0, 1, 3-1, 3, 3+1
where "0" denotes the empty sum. These are just the integers from -4 to 4.)
But this can be shown by induction on k. Clearly it's true for k = 0. Then, for the induction, consider the 3k sums of the powers of three up to 3k-1 and their negatives; by the inductive hypothesis these are just the integers in the interval![$\left[ {1-3^k \over 2}, {3^k-1 \over 2} \right]$](http://snappy.at.org/~cola/tex2img/image.php?id=89ebf2a3ea9c401040c6021e45b586ad)
. Now consider the 3k+1 sums of the powers of three up to 3k and their negatives. There are 3k of these which are just the ones which don't include 3k. Those that include +3k add up to ![$\left[ {1-3^k \over 2}+3^k, {3^k-1 \over 2}+3^k \right]$](http://snappy.at.org/~cola/tex2img/image.php?id=6a41e77e512e886790f994891cc54d81)
, and those which include -3k add up to ![$\left[ {1-3^k \over 2}-3^k, {3^k-1 \over 2}-3^k \right]$](http://snappy.at.org/~cola/tex2img/image.php?id=948cc1eb5ffb231e21688155303358c6)
. These three intervals put together are ![$\left[ {1-3^{k+1} \over 2}, {3^{k+1}-1 \over 2} \right]$](http://snappy.at.org/~cola/tex2img/image.php?id=682ae589187bbd0a1c76390ac26fa9f3)
, as desired. (For example, when k=2, these three intervals are [-4, 4], [5, 13], and [-13, -5], which together make up [-13, 13].) By induction, we can make each integer in uniquely as a sum of distinct powers of 3 which are less than 3k and their negatives, which is essentially the desired result.
The last section of the article talks about partitions with some negative parts, or "signed partitions". For example, 9+8-6-5 is a signed partition of 6. These are a bit more awkward to work with in terms of generating functions -- the generating function above about the powers of 3 doesn't converge, ever! So it's basically a curiosity, but one can actually prove things about these signed partitions using generating functions; see the article for examples.
which is an analytic version of the fact that every integer is uniquely a sum of distinct powers of 2. What I didn't realize at the time, but learned from George Andrews article Euler's "De Partitio Numerorum", in the current issue (Vol. 44, No. 4) of the Bulletin of the American Mathematical Society, is that this is due to Euler. This is hardly surprising, though, as Euler was as far as I know the first person to apply generating functions to partitions. (The result was known before that; it's the generating-function statement that's due to Euler.)
But here's one I didn't know:
This is an analytic version of the fact that every integer is uniquely a sum of distinct powers of 3 and their negatives, and is Theorem 4 of the Andrews paper. For example, 1 = 1, 2 = 3-1, 3 = 3, 4 = 3+1, 5 = 9-3+1, 6 = 9-3, 7 = 9-3+1, and so on.
To see this fact combinatorially, note that we can make 3k sums out of the numbers 30, 31, ..., 3k-1; for each of these we include the number, its negative, or neither. If we can show that these are the distinct integers from -l to l, where l = (3k-1)/2, then that's enough. (For example, when k = 2, we have l = 4, and the nine possible sums of 1, 3, and their negatives are
-3-1, -3, -3+1, -1, 0, 1, 3-1, 3, 3+1
where "0" denotes the empty sum. These are just the integers from -4 to 4.)
But this can be shown by induction on k. Clearly it's true for k = 0. Then, for the induction, consider the 3k sums of the powers of three up to 3k-1 and their negatives; by the inductive hypothesis these are just the integers in the interval
The last section of the article talks about partitions with some negative parts, or "signed partitions". For example, 9+8-6-5 is a signed partition of 6. These are a bit more awkward to work with in terms of generating functions -- the generating function above about the powers of 3 doesn't converge, ever! So it's basically a curiosity, but one can actually prove things about these signed partitions using generating functions; see the article for examples.
Subscribe to:
Posts (Atom)
