- Given integers $0<a_1<\dots<a_t$ and $0<b_1<\dots<b_t$ with $a_t<b_t<M$ can we find integers $m,n,m',n'\in\mathbb Z$ such that
$$ma_i+n<m'b_i+n'<ma_{i+1}+n$$ holds at every $i\in\{1,\dots,t-1\}$?
- If so is there a fixed $c>0$ such that $\max(|m|,|n|,|m'|,|n'|)<t^{\log^c M}$ holds?
Related: https://mathoverflow.net/questions/334885/interlacing-sequences-by-polynomials.
The answer is no to your first question, i.e., is there always $m,n,m',n'\in \mathbb{Z}$ such that
$$ma_i+n<m'b_i+n'<ma_{i+1}+n \tag{1}\label{eq1}$$
is true for all $1 \le i \le t - 1$. First, note that, from \eqref{eq1}, requiring $ma_i + n \lt ma_{i+1} + n$, where $a_i \lt a_{i+1}$, means $m \gt 0$. Thus, since the values of $m'b_i + n'$ need to be increasing with increasing values of $i$, with $b_i \lt b_{i+1}$, means that $m' \gt 0$.
Consider $t = 5$, so the set of inequalities become
$$a_1 m + n \lt b_1 m' + n' \lt a_2 m + n \tag{2}\label{eq2}$$ $$a_2 m + n \lt b_2 m' + n' \lt a_3 m + n \tag{3}\label{eq3}$$ $$a_3 m + n \lt b_3 m' + n' \lt a_4 m + n \tag{4}\label{eq4}$$ $$a_4 m + n \lt b_4 m' + n' \lt a_5 m + n \tag{5}\label{eq5}$$
Combining \eqref{eq2} and \eqref{eq3} gives
$$a_1 m + n \lt b_1 m' + n' \lt b_2 m' + n' \lt a_3 m + n \tag{6}\label{eq6}$$
This means the difference between the $2$ middle parts is less than the difference of the $2$ outer parts, i.e.,
$$(b_2 m' + n') - (b_1 m' + n') \lt (a_3 m + n) - (a_1 m + n) \; \iff \; (b_2 - b_1)m' \lt (a_3 - a_1)m \tag{7}\label{eq7}$$
Next, comparing \eqref{eq2} with \eqref{eq5}, you have
$$b_1 m' + n' \lt a_2 m + n \lt a_4 m + n \lt b_4 m' + n' \tag{8}\label{eq8}$$
Once again, the difference between the $2$ middle parts is less than the difference of the $2$ outer parts, i.e.,
$$(a_4 m + n) - (a_2 m + n) \lt (b_4 m' + n') - (b_1 m' + n') \; \iff \; (a_4 - a_2)m \lt (b_4 - b_1)m' \tag{9}\label{eq9}$$
Now, if $a_1 = 1$, $a_2 = 2$, $a_3 = 3$, $a_4 = 6$, $a_5 = 7$, and $b_1 = 4$, $b_2 = 6$, $b_3 = 7$, $b_4 = 8$, $b_5 = 9$. In this case, \eqref{eq7} becomes
$$(6 - 4)m' \lt (3 - 1)m \; \iff \; m' \lt m \tag{10}\label{eq10}$$
and \eqref{eq9} becomes
$$(6 - 2)m \lt (8 - 4)m' \; \iff \; m \lt m' \tag{11}\label{eq11}$$
However, this contradicts \eqref{eq10}, so in this case there are no such $m,n,m',n'\in \mathbb{Z}$. Note, also, that not only is $a_5 \lt b_5$ as required, but also $a_i \lt b_i$ for all $1 \le i \le 5$.
Nonetheless, there are cases where it does work. As for those cases always satisfying your second question, consider $t = 3$, with $a_i = i$, $b_i = 2i$ for $1 \le i \le 3$, with $a_i \lt b_i$ once again. The equations are now
$$m + n \lt 2m' + n' \lt 2m + n \tag{12}\label{eq12}$$ $$2m + n \lt 4m' + n' \lt 3m + n \tag{13}\label{eq13}$$
In this case, have $m = 2k$ and $m' = k$ for any integer $k \gt 0$, and $n = n' - 1$ for any $n' \in \mathbb{Z}$. Then you can confirm both \eqref{eq12} and \eqref{eq13} are satisfied since they become $2k + n' - 1 \lt 2k + n' \lt 4k + n' - 1$ and $4k + n' - 1 \lt 4k + n' \lt 6k + n' - 1$. Also, although $\max(|m|,|n|,|m'|,|n'|)$ exists for any given $m'$ and $n'$, as these values are unbounded, there's no upper limit for this maximum and, thus, there's for any given $t, M \gt 0$, there's no fixed $c \gt 0$ such that $\max(|m|,|n|,|m'|,|n'|)<t^{\log^c M}$ holds.