Sharp bounds for the Tao-Vu Discrete John's Theorem

Abstract

Tao and Vu showed that every centrally symmetric convex progression $C\subset {\mathbb{Z}}^d$ is contained in a generalised arithmetic progression of size $d^{O(d^2)}\#C$. Berg and Henk improved the size bound to $d^{O(d\log d)}\#C$. We obtain the bound $d^{O(d)}\#C$, which is sharp up to the implied constant, and is of the same form as the bound in the continuous setting given by John's Theorem.

2 pages