---
tag: 718DQ1KH8W
kind: statement
role: theorem
name: Muchnik's Theorem
sources:
  - wikipedia: en:23756@r1374594859
    locator: Presburger arithmetic, section Presburger-definable integer relation > Muchnik's characterization
    note: adopted
    mention: wikipedia://en/23756#X6QZ
    sections: [Statement]
inventory: [76AGFZ28JT]
---

## 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}))$.