I need to solve the problem: is it possible to use quantifier elimination theorem in the structure $\langle\mathbb{Z}, <, = \rangle$.
I have a proof that it is possible for $\langle\mathbb{R}, <, = \rangle$, but it uses the density of these orders (i.e. if $x<y$ then there exists $z$ such that $x<z<y$). So, this is a real difference between my problem and this one.
I probably think that there exists an example of the formula which disproves quantifier elimination for $\langle\mathbb{Z}, <, = \rangle$.
From the comments, we suspect that "there is an element between $x$ and $y$" cannot be expressed without quantifiers. One way to show this is to show that $x=1$ and $y=3$ satisfy all the same quantifier-free $\varphi(x,y)$ as $x=1$ and $y=2.$ You can do this by showing it for atomic formulas and then an induction on formula structure.