We consider polyhedra with coordinates lying in a real algebraic number field \(F\). The structure of integer points in such algebraic polyhedra is much less well understood compared to the rational case. We formalize by extending the classical Presburger Arithmetic to a theory \(S\), which allows algebraic scalar multiplication besides additions of integers. A dichotomy is established: the theory \(S\) is decidable if and only if \(K\) is a quadratic field. Geometrically, this means the structure of integer points in algebraic polyhedra becomes intractable under coordinate projections and Boolean operations. Our method combines several ideas from computability theory and elementary number theory. Ostrowski representation of real numbers play a crucial role. Joint work with Philipp Hieronymi and Igor Pak.
Before the talk, at 3:10pm, there will be tea and cookies in Wean 6220.
The ACO Seminar (2019–2020)