It follows easily from Matiyasevich's Theorem that the Diophantine sets are closed under concatenation. I am trying to figure out the mechanism by which they are closed under concatenation. In other words...
Given Diophantine polynomials $p(x \, | \, a_1, \dots, a_n)$ and $q(x \, | \, b_1, \dots, b_m)$, find a Diophantine polynomial $r(x \, | \, c_1, \dots, c_k)$ (described in terms of $p$ and $q$) such that if:
- There exist $a_1, \dots, a_n$ such that $p(x_1 \, | \, a_1, \dots, a_n) = 0$, and
- There exist $b_1, \dots, b_m$ such that $q(x_2 \, | \, b_1, \dots, b_m) = 0$, then
- There exist $c_1, \dots, c_k$ such that $r(2^{\lfloor\log x_2\rfloor} \cdot x_1 + x_2 \, | \, c_1, \dots, c_k) = 0$
Any advice?
Matiyasevich gives a polynomial for exponentiation, call it $$ e(x,y,z) = 0 \iff x=y^z $$ then to concatenate $x_1$ and $x_2$ we need a polynomial combining $$ e(\beta,2,\alpha) = 0 \\ x_2<\beta<2 x_2 \\ x=\beta x_1+x_2 $$ call this $S(x,x_1,x_2)=0 \iff x=2^{\lceil \log_2 x_2 \rceil}x_1+x_2$.
Identify the variables $$ (c_1,c_2,c_3,\ldots,c_k) = (x_1,x_2,a_1,a_2,\ldots,a_n,b_1,b_2,\ldots,b_m) $$ then $$ r(x|c_1,\ldots,c_k) = S(x,c_1,c_2)^2+p(c_1|c_3,\ldots,c_{n+2})^2+ q(c_2|c_{n+3},\ldots,c_k)^2 $$ satisfies your conditions.