# Must the poset of "automorphism group variants" be upwards-directed?

Say that two structures $$\mathfrak{A},\mathfrak{B}$$ are parametrically equivalent ("$$\approx$$") iff they have the same underlying set and each primitive relation/function of one is definable (by a single first-order formula, with parameters) in the other. The automorphism group spectrum of a structure $$\mathfrak{A}$$ is the set of automorphism groups of its parametric equivalents: $$\mathsf{AGS}(\mathfrak{A})=\{Aut(\mathfrak{B}): \mathfrak{B}\approx\mathfrak{A}\}.$$

In general this may be quite large. For example, the following three structures are parametrically equivalent but have quite different automorphism groups:

• $$\mathfrak{A}=(\mathbb{Q};+,<,1)$$ has no nontrivial automorphisms. (Indeed every structure is parametrically equivalent to a rigid one - just add constants naming every element.)

• $$\mathfrak{B}=(\mathbb{Q};+,<)$$ has some automorphisms: they're exactly the maps $$x\mapsto ax$$ for $$a$$ a positive rational.

• The "torsor-and-betweenness version" of $$\mathfrak{B}$$, namely $$\mathfrak{C}=(\mathbb{Q}; (x,y,z)\mapsto x-y+z, \{(x,y,z): \vert y-x\vert+\vert z-y\vert=\vert z-x\vert\}),$$ has even more automorphisms: its automorphism group is generated by $$Aut(\mathfrak{B})$$, multiplication by $$-1$$, and addition by any fixed rational number.

There's quite a lot (to put it mildly!) known about the relationship between a structure and its automorphism group. I'm curious about the relationship between a structure and its automorphism group spectrum, which is obviously a vastly looser construction. However, at present I know very little about this even in relatively tame situations. I think the following seemingly-trivial question is a good starting point:

Is $$\mathsf{AGS}(\mathfrak{A})$$ always upwards-directed? That is, if $$\mathfrak{A}\approx\mathfrak{B}$$, must there be a $$\mathfrak{C}$$ with $$\mathfrak{C}\approx\mathfrak{A}$$ and $$Aut(\mathfrak{A})\cup Aut(\mathfrak{B})\subseteq Aut(\mathfrak{C})$$?

(Of course downwards-directedness is trivial, since we can just combine the structures involved in the obvious way. In fact $$\mathsf{AGS}(\mathfrak{A})$$ is always a lower semilattice.)

Note that the structures involved do not have to have finite languages, so we have a fair amount of control here.

EDIT: I think it may be helpful to include a bit more "flavor:" namely, $$\mathsf{AGS}(\mathfrak{A})$$ never (except in trivial situations) has a greatest element.

Suppose we have a relational structure $$\mathfrak{A}$$ with domain $$A$$ and primitive relations $$R_i$$ of arity $$n_i$$ ($$i\in I$$) and elements $$a,b\in\mathfrak{A}$$. Consider the new structure $$\hat{\mathfrak{A}}$$ defined as follows. The domain of $$\hat{\mathfrak{A}}$$ is $$A$$, and the language of $$\hat{\mathfrak{A}}$$ has a $$2n_i$$-ary relation $$S_i$$ for each $$n_i$$-ary relation $$R_i$$. We set $$S_i^\hat{\mathfrak{A}}$$ to be the set of tuples $$(x_1,...,x_{2n_i})\in A^{2n_i}$$ such that

• for each $$1\le k\le n_i$$, either $$x_{2k-1}=x_{2k}$$ or $$\{x_{2k-1},x_{2k}\}\subseteq\{a,b\}$$, and

• in $$\mathfrak{A}$$ we have $$R_i([x_1,x_2],[x_3,x_4],...,[x_{2n_i-1}, x_{2n_i}])$$,

where the bracket operation is defined as follows: $$[u_1,u_2]=\begin{cases} u_1 & \mbox{ if }u_1=u_2\not\in\{a,b\},\\ a & \mbox{ if }\{u_1,u_2\}\in\{\{a\},\{b\}\},\\ b & \mbox{ if }\{u_1,u_2\}=\{a,b\},\\ \mbox{[doesn'tmatter]} & \mbox{otherwise}.\\ \end{cases}$$

We have $$\mathfrak{A}\approx\hat{\mathfrak{A}}$$ (just name one of $$a$$ or $$b$$), but now the permutation swapping $$a$$ and $$b$$ and leaving everything else fixed is in $$Aut(\hat{\mathfrak{A}})$$. Teasing this out, the only way $$\mathsf{AGS}(\mathfrak{A})$$ can have a top element is if $$\mathfrak{A}$$ is parametrically equivalent to a structure where every permutation is an automorphism.

Admittedly things might get more interesting if we weaken the notion of maximality (e.g. ask whether there is $$H\in\mathsf{AGS}(\mathfrak{A})$$ such that for all $$\mathfrak{B}\approx\mathfrak{A}$$ there are $$\pi_1,...,\pi_j$$ such that the group generated by $$H\cup\{\pi_1,...,\pi_j\}$$ contains $$Aut(\mathfrak{B})$$) or constrain the language (e.g. forbid relations of arity $$>n$$ for some "small" $$n$$) but at least for literal maximality there is no interesting behavior possible.

No, it’s not always upwards-directed.

The underlying set will be $$\mathbb Q.$$ Define relations $$<_n$$ by $$a<_n b \iff n

Take $$\mathfrak A$$ to have relations $$<_n$$ for $$n$$ even, and take $$\mathfrak B$$ to have relations $$<_n$$ for $$n$$ odd. These models have the same definable sets. $$\operatorname{Aut}(\mathfrak A)$$ is the group of order-preserving bijections fixing the even integers. $$\operatorname{Aut}(\mathfrak B)$$ is the group of order-preserving bijections fixing the odd integers.

By a shuffle that does not translate well to text (though I can try if you like!), the map $$\tau:x\mapsto x+1$$ is a composition of bijections in $$\operatorname{Aut}(\mathfrak A)\cup \operatorname{Aut}(\mathfrak B).$$ Consider a unary relation $$U(x)$$ that is definable by a formula $$\phi(x,y)$$ in $$\mathfrak A$$ with a tuple $$y$$ as a parameter. For sufficiently large integers $$N,$$ the parameter $$y$$ and all operations and relations used by $$\phi$$ are invariant under bijections that fix $$[-N,N].$$ If $$U$$ is invariant under $$\tau^{4N},$$ then it must also be invariant under bijections that fix $$[3N,5N].$$ This can’t happen unless $$U$$ is either $$\emptyset$$ or $$\mathbb Q.$$

In particular $$U$$ cannot be the interval $$(0,2)=\{x:x<_0 2\}.$$ So no $$\mathfrak C\approx \mathfrak A$$ can be $$\tau$$-invariant.

• Nice! Do you see a way to get a finite-language example? Unless I'm missing something that's not a trivial modification. Commented Aug 2, 2021 at 5:13
• @NoahSchweber: No, I don’t see a way to get a finite language example unfortunately Commented Aug 2, 2021 at 10:19
• I've asked the finite language version here. Commented Aug 9, 2021 at 4:10