Tag Archives: math

amusing footnote in Symmetric Functions and Hall Polynomials

Posted on by

In I.G. Macdonald’s Symmetric Functions and Hall Polynomials, on page 2 there is the following comment on the standard way to write down diagrams of partitions and tableaux:

Some authors (especially Francophones) prefer the convention of coordinate geometry (in which the first coordinate increases from left to right and the second coordinate from bottom to top) and define the diagram of \lambda to be the set of (i,j) \in \mathbf{Z}^2 such that 1 \le i \le \lambda_j. Readers who prefer this convention should read this book upside down in a mirror.

Oh, snap!

delays delays

Posted on by

The defense/talk went pretty well, I thought. And there was champagne afterwards! However, filing the thesis has been pushed off until early in the summer. Although this has the benefit of making the finished document much better, the downside is that such a large object sitting in my brain tends to crowd out other more exciting projects that I would like to work on or think about. In the meantime, I will try to blog a bit more frequently so that I don’t end up with tunnel vision.

Robin sent along a link to some mathematical models in metal. They look like more hard-core versions of the sculpted surfaces seen in display cases in math department hallways. I took a few math classes at UIUC during high school and I remember walking past these dusty shelves filled with plaster (?) shapes with intriguing names like “the ring of the nodoid.”

Hubert Newton, pioneer

Posted on by

I read a fascinating article [pdf] by Steve Batterson about Hubert Newton, the advisor of E. H. Moore, the so-called “father of American mathematics” who has a stunning 11938 academic descendants.

As is made clear in the article, the idea that Chasles was his academic advisor is questionable by the standards of today. Indeed, it was not until Newton started teaching at Yale that they even offered a PhD.

Interestingly, Google turned up Newton’s obituary from the NY Times.

EE Toolkit Topics

Posted on by

Alex and I were talking this week about what the syllabus for a course along the lines of Arora’s Theorist’s Toolkit or Kelner’s An Algorithmist’s Toolkit (HT to Lav for the link on my last post on this topic). I think developing a course along these lines with interchangeable 2-4 lecture “modules” would be a great thing in general. Modular design is appealing from an engineering perspective (although, as my advisor might say, separation of design is in general suboptimal). The question is, what would a good set of topics be? Here’s a partial set:

  • Advanced matrix tricks: matrix derivatives and other tools
  • Majorization and applications
  • Random graphs and random geometric graphs
  • Mixing times for Markov chains
  • Auctions and related allocation mechanisms
  • Random matrix theory : the basic results
  • Message passing algorithms
  • High-dimensional convex geometry
  • Concentration of measure phenomena
  • Alternating projection techniques

If any readers have ideas for additional topics, please leave a comment.

The point of such a course would be to give students some exposure to analysis and modeling techniques and more importantly a set of references so they could learn more if they need to. It’s like having a kind of cultural literacy to read systems EE papers. Of course, if you’re going to go and study LDPC codes, the brief introduction to message passing wouldn’t be enough, but if you want to understand the issues around BP decoding, the 3 lectures may be sufficient for you to follow what is going on. The list above has some items that are too narrow and some that are too broad. There are a lot of different tools out there, and some exposure to what they are used for would be useful, especially for graduate students at schools which don’t have an extremely diverse seminar series.

how JPEG works?

Posted on by

In this month’s Notices of the AMS, there was an article on how JPEG works [pdf]. These little articles are supposed to be about neat topics in mathematics or applications, and they are often uneven and sometimes contentious, as the Koblitz article [pdf] has recently demonstrated.

Even though I do signal processing research, I hadn’t looked under the hood of JPEG too carefully in any of my classes, so it was interesting to me to read about process of translating RGB to luminance and two chrominances, the DCT coefficient quantization scheme, and so on. The bit at the end on wavelets in JPEG-2000 I already knew about. But I think that for a mathematician the “why” was lost in all of the details of Huffman coding, Cohen-Daubechies wavelets, and so on. All of the engineering choices were made (in terribly contentious standards meetings, I’m sure) for a reason, and the choice of the mathematics is really a choice of model of “natural” images. He does a good explanation of luminance-chrominance vs. RGB in terms of the visual system, but what about the Fourier transform in terms of capturing edge detail in high frequency coefficients?

Unfortunately for me, the article ended up confirming my pessimistic view that standards look like a sequence of ad-hoc decisions. There’s lots of theory behind those implementations, and I think that might appeal to more mathematicians.

sequences and series

Posted on by

I think that learning math has colored my ideas about the connotations of words. In particular, the words “sequence” and “series” have the meanings “a set of related things that follow each other in a particular order” and “a number of things of a similar nature coming one after the other.” They appear to be mostly interchangeable. But consider the phrase “in a sequence/series of of papers, Csiszár and Narayan proved…” Is there a difference in meaning?

To me, “series” connotes a cumulative effect — the set of papers build upon each other, as in the summation of a series encountered in calculus. The word “sequence” is milder — these are set of related papers that follow chronologically, but may look at different angles of the same problem rather than building on each other. Clearly this difference is leaking in from the technical definitions into my writing. Does this happen to anyone else?

those crazy Brits

Posted on by

So I was reading the science news over at the BBC when I came across this article:

Although there are still those who argue over the US and “former UK” definitions of figures such as a billion and trillion, according to Michael there is now basic agreement that a trillion is a thousand billion and a billion is a thousand million.

Maybe it’s my American-centric upbringing, but was there really a debate about this? I went and consulted a few dictionaries. Merriam-Webster says:

1 — see NUMBER table
2 : an indeterminately large number

The “number table” gives the following (American, British, integer) triples: (billion, milliard, 109), (trillion, billion, 1012), and (quintillion, trillion, 1018). Apparently 10n where n = 3 (mod 6) and n > 14 don’t warrant their own name — they can be a “thousand 10n – 3.”

The regional bias is clearer in the American Heritage versus OED. The American Heritage Dictionary puts 1012 first:

1. The cardinal number equal to 1012.
2. Chiefly British The cardinal number equal to 1018.

The OED has its own bias:

The third power of a million; a million billions, i.e. millions of millions. Also, orig. in France and local U.S., a thousand ‘billions’, or 1012 (i.e. the traditional English billion: see BILLION): this sense is now standard in the U.S. and is increasingly common in British usage.

paper a day : auctions where the seller can restrict the supply

Posted on by

Auctions of divisible goods with endogenous supply
K. Back and J.F. Zender
Economics Letters 73 (2001) 29–34

I’m working on a research problem that has some relationship to auction theory, so I’m trying to read up on some of the literature. I finally found this paper, which is more related to what I’m doing — an auction in which the amount of the divisible good is determined after the bidding. This is used in Treasury auctions in some countries, but is also a reasonable model for a kind of “middleman scenario” I think, where the seller is a middleman and uses the bids to purchase the good to be sold from a supplier.

In a uniform-price auction (where the bidders bid demand curves and the seller sets a price), equilibria exists where the bidders bid really low and then get the good for free. This can be arbitrarily bad for the seller. In a discriminatory-price auction (where the price bidders pay is kind of like an integral of their demand curve), this problem doesn’t happen, since bidders are interested in their entire demand curve. This is good for the seller.

But you can fix up a uniform price auction by letting the seller restrict the supply after the bids come in, This paper shows that in that case, the equilibria are better for the seller, and in fact the seller will not have to restrict the supply. So by retaining the right to restrict the supply, the situation is improved, but that right need not be exercised.

Good survey articles for communications theorists

Posted on by

One thing that I could have used when I started graduate school was a good list of survey articles and introductions to different modeling paradigms and mathematical ideas used in communications and signal processing. It would have done wonders to help me get up to speed on these widely-used ideas. As a grad student, you can’t take classes in everything, and a lot of these ideas are important in research but haven’t really made it into course curricula either. Hopefully people reading this will comment and suggest more titles — I’ll expand the list as more material is suggested.

Topics that it would nice to have (preferably at a level for early graduate school) : convex analysis, Fourier analysis, percolation (there’s a book but it’s a bit advanced for many I think), generating functions… anything else, really.

High dimensional convex geometry

Keith M. Ball, An Elementary Introduction to Convex Geometry, Mathematical Sciences Research Institute Publications Vol. 31 : Flavors of Geometry, 1998.
This is a survey article that requires a bit of mathematical maturity, but covers a lot interesting material on high dimensional balls, convex polytopes, volume ratios, and ends up in Dvoretsky’s Theorem. This is less of a “techniques” paper but is good for getting some intuition and facts straight about high dimensional convex things.

Isoperimetric inequalities

A. Dembo, T. Cover, and J.A. Thomas, Information theoretic inequalities, IEEE Transactions on Information Theory, 37(6), 1991.
This is the information-theoretic take on some isoperimetric inequalities.

Markov Chains and Mixing

V. Guruswami. Rapidly Mixing Markov Chains: A Comparison of Techniques, May 2000.
A nice readable survey that gets the main results across.

Game Theory

Robert Gibbons, Game Theory for Applied Economists, Princeton University Press, 1992.
This is a quick read that will get the basic terminology and ideas of game theory. It’s not as useful for learning the deeper stuff, but it’s definitely accessible and well-written.

Auctions and auction theory — used for network congestion and resource allocation

Paul Klemperer, A Survey of Auction Theory, in Auctions: Theory and Practice, Princeton University Press, 2004.
A non-technical introduction to the study of auctions and how they are modeled. Good for getting an idea of what all the fuss is about.
Vijay Krishna, Auction Theory, Academic Press, 2002.
This book covers the basics and reading the first few chapters should let you get a handle on the terminology so that you can read some of the network congestion and pricing papers.