Complexity of linear relaxations in integer programming

For a set $X$ of integer points in a polyhedron, the smallest number of facets of any polyhedron whose set of integer points coincides with $X$ is called the relaxation complexity $\mathrm{r}\mathrm{c}(X)$. This parameter was introduced by Kaibel & Weltge (2015) and captures the complexity of linear descriptions of $X$ without using auxiliary variables. Using tools from combinatorics, geometry of numbers, and quantifier elimination, we make progress on several open questions regarding $\mathrm{r}\mathrm{c}(X)$ and its variant ${\mathrm{r}\mathrm{c}}_{\mathbb{Q}}(X)$, restricting the descriptions of $X$ to rational polyhedra. As our main results we show that $$\mathrm{r}\mathrm{c}$(X) = $\mathrm{r}\mathrm{c}$_{$\mathbb{Q}$}(X)$when:(a)$X$isatmostfour-dimensional,(b)$X$representseveryresidueclassin$($\mathbb{Z}$/2$\mathbb{Z}$)^d$, © the convex hull of $X$ contains an interior integer point, or (d) the lattice-width of $X$ is above a certain threshold. Additionally, $\mathrm{r}\mathrm{c}(X)$ can be algorithmically computed when $X$ is at most three-dimensional, or $X$ satisfies one of the conditions (b), ©, or (d) above. Moreover, we obtain an improved lower bound on $\mathrm{r}\mathrm{c}(X)$ in terms of the dimension of $X$.