Counting Points with Dr. Ozaydin

On Monday evenings is the Graduate Student Seminar (aka the Pizza Seminar).  It is the grad student version of the Math Club.  There are talks and pizza, with the only difference being that the talks are a little more advanced.  But upper level undergrads are always welcome to attend!  It’s this

Monday, September 16th at 5:30 pm in PHSC 1105.

This week’s is a particularly good one.  Dr. Ozaydin will be talking about how to count points inside polygons and polyhedra.  It’s an elementary question with a beautiful answer.  Stop on by!

Count the points!

Count the points!

The general topic is to compute the number of points with integer coordinates in a convex rational polytope (i.e. the convex hull of finitely many points with rational coordinates in a Euclidean space). This is Ehrhart Theory, an area rich with beautiful qualitative results (of Ehrhart, MacDonald, Stanley, Brion, Lawrence, Berline-Vergne and others). However, explicit computable formulas are very rare.

A specific problem is to find a computable formula for the generating function f(n):= the no. of ways of paying n using only coins of denominations a, b and c (assuming a, b, c are relatively prime). A theorem of Popoviciu gives a good answer for two (relatively prime) denominations (a and b), but no similar formula is known even for three denominations. (There are algorithms that compute f(n) in polynomial time, due to Barvinok and others, but no explicit computable formula.)

The usual proofs of Popoviciu’s theorem uses the Discrete Fourier Transform, instead I’ll present a short elementary geometric proof. Then I hope to discuss what is known in higher dimensions and where the difficulties lie.

— Dr. Ozaydin’s abstract

Advertisements