Recall that a group $G$ is *pseudofinite* if every first-order sentence $\varphi$ (in the language of groups) satisfied in $G$ is also satisfied in some finite group. Also recall that an instance of the *order property* in $G$ is a pair of sequences of finite tuples of elements of $G$, $\{\bar{a}\_i\}\_{i<\omega}$ and $\{\bar{b}\_{j}\}\_{j < \omega}$ (with any two $\bar{a}\_i$'s the same length and any two $\bar{b}\_{j}$'s the same length), together with a formula $\varphi(\bar{x},\bar{y})$ such that for any $i, j < \omega$, $G$ satisfies $\varphi(\bar{a}\_i,\bar{b}\_j)$ if and only if $i<j$.


I'm curious about the existence of such a thing with $\varphi$ a quantifier free formula. Using some typical arguments, you can show that if such a thing exists, then it exists with $\varphi$ a positive atomic formula, which can further be reduced to an expression of the form $t(\bar{x},\bar{y})=e$, with $e$ the group identity. By rearranging the tuples in question and possibly adding inverses and instances of $e$ in, we can actually assuming that this expression is of the form $\prod\_{\ell<n} x\_\ell y\_\ell = e$. By a compactness argument, this finally reduces to the following question:



> 
> **Question:** Does there exist an $n< \omega$ such that for every $k< \omega$, there is a finite group $H$ together with $n$-tuples $\bar{a}^0,\dots,\bar{a}^{k-1},\bar{b}^0,\dots,\bar{b}^{k-1} \in H$ for which for any $i,j < k$, $\prod\_{\ell<n} a^i\_\ell b^j\_\ell = e$ if and only if $i < j$?
> 
> 
> 


This is pretty likely to be true and also likely to be known, but I'm having difficulty thinking of something or finding a reference. I'm also curious about quantifier-free instances of the independence property and the strong order property, but I wanted to keep this question focused.



Is there a pseudofinite group with a quantifier-free instance of the order property?
**Short answer:** Given a prime $p>2$, an infinite extra-special $p$ group is pseudofinite, and the quantifier-free formula $xy=yx$ witnesses the independence property (and so witnesses the order property too).


**Details:** I am basically just quoting from the Appendix in *[Definable envelopes in groups having a simple theory](https://hal.archives-ouvertes.fr/hal-00657716v2/document)* by Milliet. Let $p>2$ be prime. An *extra-special $p$ group* is a group $G$ such that $g^p=1$ for all $g\in G$, $Z(G)$ is cyclic of order $p$, and $Z(G)=[G,G]$.


It is well-known that there is a unique countably infinite extra-special $p$-group. In fact, Felgner showed that the theory of infinite extra-special $p$-groups is a well-defined complete $\aleph\_0$-categorical first-order theory in the language of groups. The following is a concrete construction of the countable model.


Let $V$ be a vector space over $\mathbb{F}\_p$ of dimension $\aleph\_0$, and let $\langle\cdot,\cdot\rangle$ be a non-degenerate skew-symmetric bilinear form on $V$. Let $G=V\times\mathbb{F}\_p$ and define the group operation
$$
(u,a)\ast (v,b)=(u+v,a+b+\langle u,v\rangle).
$$
Then $(G,\ast)$ is the countably infinite extra-special $p$-group.


Now, since the bilinear form is skew-symmetric, and $p>2$, it follows that $(u,a)\ast(v,b)=(v,b)\ast (u,a)$ if and only if $\langle u,v\rangle=0$. So we can witness the independence property for the formula $\varphi(x,y)$ given by $x\ast y=y\ast x$. Specifically, we fix $n$ and find $g\_1,\ldots,g\_n\in G$ such that for any $X\subseteq\{1,\ldots,n\}$ there is some $h\_X\in G$ so that $g\_i\ast h\_X=h\_X\ast g\_i$ if and only if $i\in X$. Let $u\_1,\ldots,u\_n$ be linearly independent vectors in $V$ and set $g\_i=(u\_i,0)$. Since the bi-linear form is non-degenerate, the maps $v\mapsto \langle u\_i,v\rangle$ are linearly independent. So we can find $v\_X\in V$ such that $\langle u\_i,v\_X\rangle =0$ if $i\in X$ and $\langle u\_i,v\_X\rangle =1$ if $i\not\in X$. Now let $h\_X=(v\_X,0)$ and we have the desired elements of $G$.


Note that we are really just using the fact that $G$ interprets the structure $V$ (with the bilinear form), which has the independence property witnessed by the formula $\langle x,y\rangle =0$. (Actually these theories are bi-interpretable.)


Finally, to see that this theory is pseudofinite, one only needs to know that there are arbitrarily large finite extra-special $p$-groups, which is also well-known. Then any non-principal ultraproduct is a model of the theory. Actually this is a $1$-dimensional asymptotic class in the sense of Macpherson and Steinhorn (see Proposition 3.11 of *[One-dimensional asymptotic classes of finite structures](https://www.ams.org/journals/tran/2008-360-01/S0002-9947-07-04382-6/S0002-9947-07-04382-6.pdf)*).


**Edit.** The theory of infinite extra-special $p$ groups is simple, so there is no formula with the strict order property. I don't know an example for SOP. There is no $\aleph\_0$-categorical example, since no $\aleph\_0$-categorical pseudofinite theory has the strict order property (see Proposition 1.3 [this paper](https://arxiv.org/pdf/1510.03539.pdf) by Alex Kruckman).


