Parametric Presburger arithmetic: complexity of counting and quantifier elimination

We consider an expansion of Presburger arithmetic which allows multiplication by k parameters $t_1,\dots ,t_k$. A formula in this language defines a parametric set $S_{\mathbf{t}}?{\mathbb{Z}}^d$ as $\mathbf{t}$ varies in ${\mathbb{Z}}^k$, and we examine the counting function $|S_{\mathbf{t}}|$ as a function of t . For a single parameter, it is known that $|S_t|$ can be expressed as an eventual quasi‐polynomial (there is a period m such that, for sufficiently large t, the function is polynomial on each of the residue classes mod m). We show that such a nice expression is impossible with 2 or more parameters. Indeed (assuming $\mathbf{P}\ne \mathbf{NP}$) we construct a parametric set $S_{t_1,t_2}$ such that $|S_{t_1,t_2}|$ is not even polynomial‐time computable on input $(t_1,t_2)$. In contrast, for parametric sets $S_{\mathbf{t}}?{\mathbb{Z}}^d$ with arbitrarily many parameters, defined in a similar language without the ordering relation, we show that $|S_{\mathbf{t}}|$ is always polynomial‐time computable in the size of t , and in fact can be represented using the gcd and similar functions.