Muchnik's Theorem

Statement

$R\subseteq\mathbb{N}^d$ is Presburger-definable if and only if:

if $d > 1$ then all sections of $R$ are Presburger-definable and

there exists $s\in\mathbb{N}$ such that, for every $k\in\mathbb{N}$, there exists $t\in\mathbb{N}$ such that for all $(x_0,\dots,x_{d-1})\in\mathbb{N}^d$ with

$$\sum_{i=0}^{d-1}x_i>t,$$

$R$ is $s$-periodic in $C(k,(x_0,\dots,x_{d-1}))$.