Can one always find independent witnesses of the order property in a simple theory? A friend of mine has raised the following interesting question. Let $\phi(x;y)$ be an unstable formula in a complete theory $T$, and let $M\models T$ be a model. Then by Ramsey+compactness we may find an $M$-indiscernible sequence $(a_ib_i)_{i\in\omega}$ witnessing the order property for $\phi$, so that $\models\phi(a_i;b_j)$ iff $i\leqslant j$ for all $i,j\in\omega$.

Question: if $T$ is simple, may we also find an $M$-indiscernible witness $(a_ib_i)_{i\in\omega}$ such that $a_i\perp_M b_j$ for all $i,j\in\omega$?


I think I have a slightly convoluted example showing that we cannot do this in general if $T$ is not simple.
Let $M=(\mathbb{N},<)$ and let $T=\operatorname{Th}(M)$, and consider the formula $$\phi(x_1x_2;y_1y_2)\equiv (x_1<y_1)\wedge (x_2=y_2)\wedge (y_1\leqslant y_2).$$ Then $\phi$ is certainly unstable; pick any sequence $c_0<d_0<c_1<d_1<\dots<c_\star$, define $a^i=c_ic_\star$ and $b^i=d_ic_\star$ for each $i\in\omega$, and then we have $\models\phi(a^i;b^j)$ iff $i\leqslant j$.
However, it is not possible to find $(a^ib^i)_{i\in\omega}$ witnessing the order property, indiscernible over $M$, and with $a^i\perp_M b^j$ for $i,j\in\omega$. To see this, suppose $(a^ib^i)_{i\in\omega}$ is any $M$-indiscernible sequence witnessing the order property for $\phi$, say with $a^i=a^i_1a^i_2$ and $b^i=b^i_1b^i_2$. Then $(a^i_1b^i_1)_{i\in\omega}$ witnesses the order property for the formula $x<y$, and so is non-constant; since it is also $M$-indiscernible, it must be disjoint from $M$, and so since $M$ is an initial segment of every model of $T$ we have $M<b^0_1$. Since $\phi(x_1x_2;y_1y_2)\to y_1\leqslant y_2$, and $\phi(x_1x_2;b^0)$ is satisfiable, $b^0_1\leqslant b^0_2$, so also $M<b^0_2$. In particular, the formula $x_2=b^0_2$ divides over $M$. But the formula $\phi(x_1x_2;b^0)$ implies $x_2=b^0_2$, and hence divides over $M$ as well. Since $\models\phi(a^0;b^0)$, thus $a^0\not\perp_M b^0$, so we are done.

Does this counterexample look right? If so, then, if I'm not mistaken, a very similar counterexample exists in any theory with the strict order property. The main trick behind this example is to find a formula $\phi(x;y)$ such that (i) for any $y$-tuple $b$ none of whose components lies in $M$, the formula $\phi(x;b)$ divides over $M$, and (ii) being an $M$-indiscernible witness of the order property for $\phi$ will force the components of the relevant tuples to lie outside $M$. Point ii is the part that seems to rely on the theory having SOP, and I don't see any way of replicating it eg in the theory of the random graph.
(Note that, if we replaced $M$ in the above question with $\varnothing$, then point ii is moot and I do think a similar example should work when $T$ is the theory of the random graph; just take $\phi(x_1x_2;y_1y_2)\equiv x_1Ry_1\wedge x_2=y_2$ and proceed as above. The formula $\phi(x;b)$ then divides over $\varnothing$ for any $b$, as needed.)
In light of all of this, if the answer to the first question above is affirmative, then there is a natural follow-up question:

Question: How about if $T$ is not necessarily simple, but at least $\text{NSOP}$?


It seems plausible to us that this should be possible in the case that $T$ is simple; however, we did not get anywhere trying to prove this. The case my friend is interested in is when $T=\text{ACFA}$, so that case is also of particular interest even if nothing can be said for general $T$. Any insight would be appreciated!
 A: I can give a negative answer to your question and a positive answer to a closely related question (which might satisfy you).
First the counterexample. Let $(G_n)_{n\in \omega}$ be a sequence of finite graphs with $|G_n|<|G_{n+1}|$ for all $n$, whose theories converge to the theory of the random graph. That is, for every sentence $\varphi$ in the theory of the random graph, there is some $N\in \omega$ such that $G_n\models \varphi$ for all $n>N$. For example, we can take the Paley graphs. Let $M$ be a structure in the language $\{E,R\}$, where $E$ is an equivalence relation with $\omega$-many classes, such that class $n$ is a copy of $G_n$ with edge relation $R$ (and there are no instances of $R$ between distinct classes). In particular, every $E$-class in $M$ is finite, $M$ contains at most one class of each finite size, and $M$ contains arbitrarily large classes.
Now an arbitrary model of $T = \mathrm{Th}(M)$ looks like $M$ together with some other $E$-classes, each of which is infinite and contains a model of the theory of the random graph. This is a simple theory (of $U$-rank $2$). The formula $xRy$ is unstable, but in any witness to the order property $(a_ib_i)_{i\in \omega}$, all the $a_i$ and $b_i$ have to be in the same (infinite) $E$-class, which does not intersect $M$. Thus $a_i$ and $b_j$ are not independent over $M$,  witnessed by the formula $xEy$.

Ok, but what if instead of fixing the model $M$ in advance, we ask: Given an unstable formula $\varphi(x;y)$ in a simple theory $T$, can we find a model $M$ and an $M$-indiscernible witness $(a_ib_i)_{i\in  \omega}$ to the order property, such that $a_i\perp_M b_j$ for all $i,j\in \omega$?
Now the answer is yes. All we need is that $M$ itself contains a witness to the order property (so taking $M$ to be $\aleph_0$-saturated will do).
Recall that for a sequence $I = (c_i)_{i\in \omega}$ and an ultrafilter $U$ on $\omega$, we define: $$\mathrm{Av}(I,U) = \{\varphi(z,b)\mid \{i\in \omega\mid \models \varphi(c_i,b)\}\in U\}.$$ This is called the average type of $I$ (by $U$). It is a global type finitely satisfiable in $I$.
Now suppose $\varphi(x;y)$ is an unstable formula. Let $(a_ib_i)_{i\in \omega}$ be a witness to the order property for $\varphi$ inside a model $M$. Let $I = (a_i)_{i\in \omega}$, and let $J = (b_i)_{i\in \omega}$. Let $U$ be a non-principal ultrafilter on $\omega$, and define $p = \mathrm{Av}(I,U)$ and $q = \mathrm{Av}(J,U)$.
Let $(a_i'b_i')_{i\in\omega}\models (p\otimes q)^{\otimes \omega}|_M$. That is, for all $n$, $b_n'$ realizes $q|_{Ma_0'b_0'\dots a_{n-1}'b_{n-1}'}$ and $a_n'$ realizes $p|_{Ma_0'b_0'\dots a_{n-1}'b_{n-1}'b_n'}$. Since $p$ and $q$ are both $M$-invariant types, $(p\otimes q)$ is $M$-invariant, and  $(a_i'b_i')_{i\in\omega}$ is $M$-indiscernible. Even better, it's a Morley sequence over $M$!
I claim that $(a_i'b_i')_{i\in\omega}$ witnesses the order property, in the sense that $\models \varphi(a_i';b_j')$ if and only if $i\geq j$ (note that the order has reversed from the original witness).
Suppose $i\geq j$. For any $n\in \omega$, the set $\{m\in \omega\mid \models \varphi(a_n;b_m)\}\in U$, so $\varphi(a_n;y)\in q$. Since $b_j'$ realizes $q$ over $M$, we have $\models \varphi(a_n;b_j')$ for all $n\in \omega$. But then $\varphi(x;b_j')\in p$. Since $a_i'$ realizes $p$ over $b_j'$, we have $\models \varphi(a_i';b_j')$.
Conversely, suppose $i<j$. For any $m\in \omega$, the set $\{n\in \omega\mid \models \lnot \varphi(a_n;b_m)\}\in U$, so $\lnot\varphi(x;b_m)\in p$. Since $a_i'$ realizes $p$ over $M$, we have $\models \lnot\varphi(a_i';b_m)$ for all $m\in \omega$. But then $\lnot\varphi(a_i';y)\in q$. Since $b_j'$ realizes $q$ over $a_i'$, we have $\models \lnot\varphi(a_i';b_j')$.
Finally, note that when $i\geq j$, $a_i'$ realizes a global $M$-invariant type over $b_j'$, so $a_i'\perp_M b_j'$. Similarly, when $i < j$, $b_j'\perp_M a_i'$.
All of the above works in any (unstable) theory $T$. If $T$ is simple, we can use symmetry of forking to conclude $a_i'\perp_M b_j'$ for all $i,j\in\omega$, as desired.
