Thursday, 10 October, 2013
SPEAKER: Prof. Murad Ozaydin, University of Oklahoma
ABSTRACT: Chicken McNuggets are sold in boxes of 6, 9 and 20. How many ways are there of buying n pieces? This is in fact a special case of a geometric question: In a given planar triangle whose vertices have rational coordinates, how many points are there with integer coordinates? What constitutes a good answer to this question?
An excellent answer one dimension lower is provided by a theorem of Popoviciu giving a short, computable formula for f(n):= the number of ways of getting n blah, if blah is sold only in boxes of sizes a and b, with the gcd(a,b)=1. No similar formula is known even for three (coprime) sizes a, b and c. 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.
Pizza will be available at 3:10 p.m.