On the solvability of a class of diophantine equations and applications

Abstract

For $1⩽i⩽k$, let $R_i$ denote $p_i(y)F_i+G_i$, where $p_i(y)$ is a polynomial in y with integer coefficients, and $F_i,G_i$ are linear polynomials in $x_1,\dots ,x_n$ with integer coefficients. Let $P(z_1,\dots ,z_k)$ be a Presburger relation over the nonnegative integers. We show that the following problem is decidable:

• Given: $R_1,\dots ,R_k$ and a Presburger relation P.

• Question: Are there nonnegative integer values for $y,x_1,\dots ,x_n$ such that for these values, $(R_1,\dots ,R_k)$ satisfies P?

We also give some applications to decision problems concerning counter machines.