Elements that are automorphic images

Question

Consider an finite abelian group $G$ and two elements $x,y \in G$. Is there a way to check whether there exists a $\phi \in \mathrm{Aut}(G)$ such that $\phi(x) = y$?

Here are some necessary conditions for the property to hold that I was able to prove

• $G/\langle x\rangle \cong G/\langle y \rangle$
• Consider a positive integer $k$. If there exists in an $a\in G$ such that $a^k = x$, then there exists a $b\in G$ such that $b^k =y$. Furthermore, if there exists a $b\in G$ such that $b^k = y$, then there exists an $a\in G$ such that $a^k=x$.

I feel like the problem is either well known & solved or well know & computationally difficult. Any thoughts/results about this?

Answer 1

(I will use additive notation. In particular, $n\mid x$ for $n\in\mathbb N$ and $x\in G$ means there exists $y$ such that $ny=x$.)

It follows from Szmielew’s quantifier elimination that two elements $x,y$ of an abelian group $G$ satisfy the same first-order formulas if and only if $$m\mid nx\iff m\mid ny$$ for all integers $n,m\ge0$; in other words, $x$ and $y$ have the same order in $G/mG$. This reduces to the following two special cases:

1. $x$ and $y$ have the same order (i.e., $nx=0\iff ny=0$ for all $n$).
2. $p^l\mid p^kx\iff p^l\mid p^ky$ for all primes $p$ and $l>k\ge0$ (where we may assume that $p^k$ divides the order of $x$ and/or $y$).

Now, if $G$ is finite, this is equivalent to the existence of an automorphism $\phi$ such that $\phi(x)=y$, because elementary equivalent finite structures are isomorphic. Moreover, in a finite (or: bounded exponent) abelian group, condition 2 implies condition 1. Thus, as a summary: for finite $G$, $x$ is automorphic to $y$ iff

$$\text{$x$ and $y$ have the same order in $G/p^lG$ for each prime power $p^l\mid\lvert G\rvert$.}$$

In fact, this criterion shows that your condition $$\def\p#1{\langle#1\rangle}G/\p x\simeq G/\p y$$ is already necessary and sufficient: if it holds, then for any $m\ge0$, $$G/(\p x+mG)\simeq(G/\p x)/m(G/\p x)\simeq(G/\p y)/m(G/\p y)\simeq G/(\p y+mG),$$ thus $|\p x+mG|=|\p y+mG|$, i.e., $x$ and $y$ have the same order in $G/mG$.

(I’m sure there is a direct algebraic proof of this using the classification of finite abelian groups and the like, but well, I’m a logician, not an algebraist.)

Answer 2

Indeed automorphisms of finite abelian groups and their orbits are well-known. Here's an algebraic point of view on describing what they are.

By the classification theorem, every finite abelian group is of the form $G = \prod_{p~\text{prime}} G_p$, with $G_p = \prod_{m \in n_{p}} (\mathbb{Z}/p^{m}\mathbb{Z})$, where for each prime $p$, $n_p$ is a finite non-increasing sequence of integers $n_{p,1} \ge n_{p,2} \ge \cdots \ge 1$. Of course, $G_p$ can be non-trivial only for finitely many $p$. The first observation is that $\operatorname{Aut}(G) = \prod_{p} \operatorname{Aut}(G_p)$ and that $g,h \in G$ are in the same automorphism orbit iff the projections $g_p, h_p$ under $G\to G_p$ are in the same $\operatorname{Aut}(G_p)$ orbit for each $p$.

So the question is reduced to $G_p$ for each prime $p$. As for any sequence $n_p$ of non-decreasing integers, it is tempting to write it as a box diagram (the term Young diagram may be overkill here), e.g., $n_p = (7,5,5,2)$:

*******        (a)
*****
*****
**

You can think of the $i$th line representing the base-$p$ digit expansion an element of $\mathbb{Z}/p^{n_{p,i}} \mathbb{Z}$. I have aligned them by the most significant digit, because any homomorphism $\mathbb{Z}/p^{m} \mathbb{Z} \to \mathbb{Z}/p^{n} \mathbb{Z}$ with $n\ge m$ must factor through the embedding $g \mapsto p^{n-m} g$, which sends the most significant digit to the most significant digit. Using this embedding on each line, we can actually identify $G_p$ with its image in $(\mathbb{Z}/p^{n_{p,1}} \mathbb{Z})^{|n_p|}$. From this point of view, the digit expansions of each row are padded with trailing zeros until all the rows are the same length.

The main observation from this arrangement is that $\operatorname{Aut}(G_p)$ can be identified with those invertible endomorphisms of $(\mathbb{Z}/p^{n_{p,1}} \mathbb{Z})^{|n_p|}$ that preserve the above embedding.

For the following explanation it will actually be more convenient to write it in a different way:

7: *******  x 1   (b)
6: 
5: *****  x 2
4: 
3: 
2: **  x 1
1: 

Now, endomorphisms of $(\mathbb{Z}/p^{n_{p,1}} \mathbb{Z})^{|n_p|}$ are just $|n_p| \times |n_p|$ matrices with entries from $\mathbb{Z}/p^{n_{p,1}}\mathbb{Z}$. The condition of preserving the image of $G_p$ amounts to a special block structure: Each non-empty line in the last diagram corresponds to a square diagonal block of indicated size, while the blocks below the diagonal must be proportional to an appropriate power of $p$ to account for the difference between the number of trailing zeros. In the running example, this is $$\begin{bmatrix} * & * & * \\ O(p^2) & * & * \\ O(p^5) & O(p^3) & * \end{bmatrix}.$$ Invertibility comes down to reducing all the elements mod-$p$ and checking that the diagonal blocks are invertible as matrices over the prime field $\mathbb{Z}/p\mathbb{Z}$.

On to the automorphism orbits. Given the diagrammatic presentation of $G_p$ in (b), there is an interesting partial order on the base-$p$ digits of its elements. Take for instance $1\cdot p^1$ as an element of one of the copies of $\mathbb{Z}/5\mathbb{Z}$ in the running example. From the structure of the endomorphisms of the group, it is clear that it can only be mapped to elements that have non-zero base-$p$ digits in the following pattern, where I've added extra dots to guide the eye:

7: ****000        (c)
6: ····
5: ****0
4: ···
3: ··
2: *0
1: 

Namely, the significance of the digit cannot decrease between the rows and the number of trailing zeros also cannot decrease between rows (which is another way of saying that homomorphisms $\mathbb{Z}/p^m\mathbb{Z} \to \mathbb{Z}/p^n\mathbb{Z}$ must preserve the order or an element, $p^k g \mapsto p^k h$). And in fact these are the only restrictions.

So if we label a digit in the base-$p$ expansion of an element of $G_p$ as $(r,c)$ according to its row (numbered as indicated, say) and column (numbered from left to right, say) position in diagram (b), then we can say that a digit dominates another one $(r,c) \ge (r',c')$ when $c\ge c'$ and $c - (r-r') \ge c'$. To $g \in G_p$ we can associate a domaination pattern by marking in the diagram (b) all the digits dominated by a non-zero digit in the base-p expansion of $g$.

The conclusion is that $g,h \in G_p$ belong to the same automorphism orbit iff they have the same domination pattern.

As a lower set in the domination partial order, a domination pattern can be characterized for instance by its maximal elements.

Here's some literature where all the details are discussed (N.B.: some of my terminology may not be completely standard).

• Hillar, Christopher J.; Rhea, Darren L., Automorphisms of finite Abelian groups., Am. Math. Mon. 114, No. 10, 917-923 (2007). ZBL1156.20046. arXiv:math/0605185
• Dutta, Kunal; Prasad, Amritanshu, Degenerations and orbits in finite Abelian groups., J. Comb. Theory, Ser. A 118, No. 6, 1685-1694 (2011). ZBL1229.20053. arXiv:1005.5222
• Schwachhöfer, Martin; Stroppel, Markus, Finding representatives for the orbits under the automorphism group of a bounded Abelian group, J. Algebra 211, No. 1, 225-239 (1999). ZBL0916.20040.