Skip to content

Junior Colloquium: Counting Integer Points in Rational Polyhedra: Popoviciu's Theorem and Beyond

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.


Ayres Hall
Room 405
1403 Circle Drive
Knoxville, TN 37996

Event Contact

Phone: 974-2463

The flagship campus of the University of Tennessee System and partner in the Tennessee Transfer Pathway.