Return to Answer

This answer builds upon Sam Hopkins' suggestion of an oriented toroidal grid, but it's more than a comment. Bottom line: need the grid to be $2^s$ by $2^s$ where $s\ge2$ to get the requested involution property.

So here's a sketch of a grid:

WLOG we can label some vertex as $(0,0)$, and then its two out-neighbours as $(1,0)$ & $(0,1)$. But how do we know that the visual layout corresponds to the only actual two-dimensional grid? $(1,0)$ has two out-neighbours $(2,0)$ & $(1,1)$. Critically, we can distinguish these because there is only a single path of length $2$ from $(0,0)$ to $(2,0)$, while there are two paths of length $2$ from $(0,0)$ to $(1,1)$. So we can extend the edge $((0,0),(1,0))$ to $((1,0),(2,0))$ to $((2,0),(3,0))$ to ... etc, getting a "unique straight cycle" (USC) that wraps all the way around the grid horizontally, eventually arriving in $(0,0)$ again. Similarly $((0,0),(0,1))$ extends to a vertical USC, wrapping all the way to $(0,0)$.

By edge-transitivity, the horizontal USCs must have the same length as the vertical ones, so the grid is an $n$ by $n$ square. Need $n\ge3$ since otherwise there are multiple edges between pairs of vertices.

Using the two USCs as axes, we can label all the nodes as $(x,y)$ for $x,y\in\{0,\dotsc,n-1\}$, and all the edges similarly as $((x,y),(w,z))$.

It's easy to see that the action of an AM on one edge defines its action on the whole graph, so the number of AMs is equal to the number of edges $= 2n^2$. Half the AMs are just translations, where the USCs of an edge and of its image are parallel. The others are flips, where the two USCs do meet at one vertex.

Define three AMs $a$, $b$, $c$ by their action on the edge $((0,0),(1,0))$ as $((1,0),(2,0))$, $((0,1),(1,1))$, $((0,0),(0,1))$ respectively. So $a$ is "right", $b$ is "up" and $c$ is "$x$-$y$ flip".

$a^n = b^n = c^2 = 1$, $ab = ba$, $cac = b$, $cbc = a$.

Let $d = ab = ba$ (called "diagonal"). Then $cd = dc$.

A typical flip can be written as $c{a^p}{b^q}$.

$(c{a^p}{b^q})^2 = d^{(p+q)}$.

So flips have even order dividing $2n$. There are hence exactly $n$ flip involutions: $c{a^p}{b^{(n-p)}}$. Write them as $cg^p$, where $g=ab^{-1}$.

Suppose $n$ has an odd factor $k$, so $n = km$. Then any AM of the form $c{g^p}{d^m}$ taken to the $k$th power gives ${(cg^p)^k}*{d^{mk}} = cg^p$. So these involutions are powers of other AMs, contrary to the request.

On the other hand, suppose $n$ is a power of $2$, and that a flip involution $f = h^{2^j}$ for some AM $h$. Then $f = (h^2)^{2^{j-1}}$. But, as shown above, $h^2$ must be a translation, not a flip, so $f$ cannot be a flip either. So, contrary to hypothesis, $f$ is not a power of another symmetry.

So to get the requested property it's necessary and sufficient that $n=2^s$, where $s\ge2$.

This answer builds upon Sam Hopkins' suggestion of an oriented toroidal grid, but it's more than a comment. Bottom line: need the grid to be $2^s$ by $2^s$ where $s\ge2$ to get the requested involution property.

So here's a sketch of a grid:

WLOG we can label some vertex as $(0,0)$, and then its two out-neighbours as $(1,0)$ & $(0,1)$. But how do we know that the visual layout corresponds to the only actual two-dimensional grid? $(1,0)$ has two out-neighbours we label $(2,0)$ & $(1,1)$. Critically, we can distinguish these because there is only a single path of length $2$ from $(0,0)$ to $(2,0)$, while there are two paths of length $2$ from $(0,0)$ to $(1,1)$. So we can extend the edge $((0,0),(1,0))$ to $((1,0),(2,0))$ to $((2,0),(3,0))$ to ... etc, getting a "unique straight cycle" (USC) that wraps all the way around the grid horizontally, eventually arriving in $(0,0)$ again. Similarly $((0,0),(0,1))$ extends to a vertical USC, wrapping all the way to $(0,0)$.

By edge-transitivity, the horizontal USCs must have the same length as the vertical ones, so the grid is an $n$ by $n$ square. Need $n\ge3$ since otherwise there are multiple edges between pairs of vertices.

Now we are safe to label all the vertices in the obvious way, as $(x,y)$ for $x,y\in\{0,\dotsc,n-1\}$, and all the edges similarly as $((x,y),(w,z))$.

It's easy to see that the action of an AM on one edge defines its action on the whole graph, so the number of AMs is equal to the number of edges $= 2n^2$. Half the AMs are just translations, where the USCs of an edge and of its image are parallel. The others are flips, where the two USCs do meet at one vertex.

Define three AMs $a$, $b$, $c$ by their action on the edge $((0,0),(1,0))$ as $((1,0),(2,0))$, $((0,1),(1,1))$, $((0,0),(0,1))$ respectively. So $a$ is "right", $b$ is "up" and $c$ is "$x$-$y$ flip".

$a^n = b^n = c^2 = 1$, $ab = ba$, $cac = b$, $cbc = a$.

Let $d = ab = ba$ (called "diagonal"). Then $cd = dc$.

A typical flip can be written as $c{a^p}{b^q}$.

$(c{a^p}{b^q})^2 = d^{(p+q)}$.

So flips have even order dividing $2n$. There are hence exactly $n$ flip involutions: $c{a^p}{b^{(n-p)}}$. Write them as $cg^p$, where $g=ab^{-1}$.

Suppose $n$ has an odd factor $k$, so $n = km$. Then any AM of the form $c{g^p}{d^m}$ taken to the $k$th power gives ${(cg^p)^k}*{d^{mk}} = cg^p$. So these involutions are powers of other AMs, contrary to the request.

On the other hand, suppose $n$ is a power of $2$, and that a flip involution $f = h^{2^j}$ for some AM $h$. Then $f = (h^2)^{2^{j-1}}$. But, as shown above, $h^2$ must be a translation, not a flip, so $f$ cannot be a flip either. So, contrary to hypothesis, $f$ is not a power of another symmetry.

So to get the requested property it's necessary and sufficient that $n=2^s$, where $s\ge2$.

This answer builds upon Sam Hopkins' suggestion of an oriented toroidal grid, but it's more than a comment. Bottom line: need the grid to be $2^s$ by $2^s$ where $s\ge2$ to get the requested involution property.

Each edge belongs to a unique "straight cycle" (USC) that wraps around the grid horizontally or vertically. By edge-transitivity, the horizontal USCs must have the same length as the vertical ones, so the grid is an $n$ by $n$ square. Need $n\ge3$ since otherwise multiple edges between pairs of vertices.

WLOG, using two USCs as axes, label the nodes as $(x,y)$ for $x,y\in\{0,\dotsc,n-1\}$, and the edges similarly as $((w,x),(y,z))$.

It's easy to see that the action of an AM on one edge defines its action on the whole graph, so the number of AMs is equal to the number of edges $= 2n^2$. Half the AMs are just translations, where the USCs of an edge and of its image are parallel. The others are flips, where the two USCs do meet at one vertex.

Define three AMs $a$, $b$, $c$ by their action on the edge $((0,0),(1,0))$ as $((1,0),(2,0))$, $((0,1),(1,1))$, $((0,0),(0,1))$ respectively. So $a$ is "right", $b$ is "up" and $c$ is "$x$-$y$ flip".

$a^n = b^n = c^2 = 1$, $ab = ba$, $cac = b$, $cbc = a$.

Let $d = ab = ba$ (called "diagonal"). Then $cd = dc$.

A typical flip can be written as $c{a^p}{b^q}$.

$(c{a^p}{b^q})^2 = d^{(p+q)}$.

So flips have even order dividing $2n$. There are hence exactly $n$ flip involutions: $c{a^p}{b^{(n-p)}}$. Write them as $cg^p$, where $g=ab^{-1}$.

Suppose $n$ has an odd factor $k$, so $n = km$. Then any AM of the form $c{g^p}{d^m}$ taken to the $k$th power gives ${(cg^p)^k}*{d^{mk}} = cg^p$. So these involutions are powers of other AMs, contrary to the request.

On the other hand, suppose $n$ is a power of $2$, and that a flip involution $f = h^{2^j}$ for some AM $h$. Then $f = (h^2)^{2^{j-1}}$. But, as shown above, $h^2$ must be a translation, not a flip, so $f$ cannot be a flip either. So, contrary to hypothesis, $f$ is not a power of another symmetry.

So to get the requested property it's necessary and sufficient that $n=2^s$, where $s\ge2$.

This answer builds upon Sam Hopkins' suggestion of an oriented toroidal grid, but it's more than a comment. Bottom line: need the grid to be $2^s$ by $2^s$ where $s\ge2$ to get the requested involution property.

So here's a sketch of a grid:

WLOG we can label some vertex as $(0,0)$, and then its two out-neighbours as $(1,0)$ & $(0,1)$. But how do we know that the visual layout corresponds to the only actual two-dimensional grid? $(1,0)$ has two out-neighbours $(2,0)$ & $(1,1)$. Critically, we can distinguish these because there is only a single path of length $2$ from $(0,0)$ to $(2,0)$, while there are two paths of length $2$ from $(0,0)$ to $(1,1)$. So we can extend the edge $((0,0),(1,0))$ to $((1,0),(2,0))$ to $((2,0),(3,0))$ to ... etc, getting a "unique straight cycle" (USC) that wraps all the way around the grid horizontally, eventually arriving in $(0,0)$ again. Similarly $((0,0),(0,1))$ extends to a vertical USC, wrapping all the way to $(0,0)$. 

By edge-transitivity, the horizontal USCs must have the same length as the vertical ones, so the grid is an $n$ by $n$ square. Need $n\ge3$ since otherwise there are multiple edges between pairs of vertices.

Using the two USCs as axes, we can label all the nodes as $(x,y)$ for $x,y\in\{0,\dotsc,n-1\}$, and all the edges similarly as $((x,y),(w,z))$.

It's easy to see that the action of an AM on one edge defines its action on the whole graph, so the number of AMs is equal to the number of edges $= 2n^2$. Half the AMs are just translations, where the USCs of an edge and of its image are parallel. The others are flips, where the two USCs do meet at one vertex.

Define three AMs $a$, $b$, $c$ by their action on the edge $((0,0),(1,0))$ as $((1,0),(2,0))$, $((0,1),(1,1))$, $((0,0),(0,1))$ respectively. So $a$ is "right", $b$ is "up" and $c$ is "$x$-$y$ flip".

$a^n = b^n = c^2 = 1$, $ab = ba$, $cac = b$, $cbc = a$.

Let $d = ab = ba$ (called "diagonal"). Then $cd = dc$.

A typical flip can be written as $c{a^p}{b^q}$.

$(c{a^p}{b^q})^2 = d^{(p+q)}$.

So flips have even order dividing $2n$. There are hence exactly $n$ flip involutions: $c{a^p}{b^{(n-p)}}$. Write them as $cg^p$, where $g=ab^{-1}$.

Suppose $n$ has an odd factor $k$, so $n = km$. Then any AM of the form $c{g^p}{d^m}$ taken to the $k$th power gives ${(cg^p)^k}*{d^{mk}} = cg^p$. So these involutions are powers of other AMs, contrary to the request.

On the other hand, suppose $n$ is a power of $2$, and that a flip involution $f = h^{2^j}$ for some AM $h$. Then $f = (h^2)^{2^{j-1}}$. But, as shown above, $h^2$ must be a translation, not a flip, so $f$ cannot be a flip either. So, contrary to hypothesis, $f$ is not a power of another symmetry.

So to get the requested property it's necessary and sufficient that $n=2^s$, where $s\ge2$.

This answer builds upon Sam Hopkins' suggestion of an oriented toroidal grid, but it's more than a comment. Bottom line: need the grid to be $2^s$ by $2^s$ where $s\ge2$ to get the requested involution property.

Each edge belongs to a unique "straight cycle" (USC) that wraps around the grid horizontally or vertically. By edge-transitivity, the horizontal USCs must have the same length as the vertical ones, so the grid is an $n$ by $n$ square. Need $n\ge3$ since otherwise multiple edges between pairs of vertices.

WLOG, using two USCs as axes, label the nodes as $(x,y)$ for $x,y\in\{0,\dotsc,n-1\}$, and the edges similarly as $((w,x),(y,z))$.

It's easy to see that the action of an AM on one edge defines its action on the whole graph, so the number of AMs is equal to the number of edges $= 2n^2$. Half the AMs are just translations, where the USCs of an edge and of its image are parallel. The others are flips, where the two USCs do meet at one vertex.

Define three AMs $a$, $b$, $c$ by their action on the edge $((0,0),(1,0))$ as $((1,0),(2,0))$, $((0,1),(1,1))$, $((0,0),(0,1))$ respectively. So $a$ is "right", $b$ is "up" and $c$ is "$x$-$y$ flip".

$a^n = b^n = c^2 = 1$, $ab = ba$, $cac = b$, $cbc = a$.

Let $d = ab = ba$ (called "diagonal"). Then $cd = dc$.

A typical flip can be written as $c{a^p}{b^q}$.

$(c{a^p}{b^q})^2 = d^{(p+q)}$.

So flips have even order dividing $2n$. There are hence exactly $n$ flip involutions: $c{a^p}{b^{(n-p)}}$. Write them as $cg^p$, where $g=ab^{-1}$.

Suppose $n$ has an odd factor $k$, so $n = km$. Then any AM of the form $c{g^p}{d^m}$ taken to the $k$th power gives ${(cg^p)^k}*{d^{mk}} = cg^p$. So these involutions are powers of other AMs, contrary to the request.

On the other hand, suppose $n$ is a power of $2$, and that a flip involution $f = h^{2^j}$ for some AM $h$. Then $f = (h^2)^{2(j-1)}$. But $h^2$ is a translation, not a flip, so $f$ cannot be a flip either. So, contrary to hypothesis, $f$ is not a power of another symmetry.

So to get the requested property it's necessary and sufficient that $n=2^s$, where $s\ge2$.

This answer builds upon Sam Hopkins' suggestion of an oriented toroidal grid, but it's more than a comment. Bottom line: need the grid to be $2^s$ by $2^s$ where $s\ge2$ to get the requested involution property.

Each edge belongs to a unique "straight cycle" (USC) that wraps around the grid horizontally or vertically. By edge-transitivity, the horizontal USCs must have the same length as the vertical ones, so the grid is an $n$ by $n$ square. Need $n\ge3$ since otherwise multiple edges between pairs of vertices.

WLOG, using two USCs as axes, label the nodes as $(x,y)$ for $x,y\in\{0,\dotsc,n-1\}$, and the edges similarly as $((w,x),(y,z))$.

It's easy to see that the action of an AM on one edge defines its action on the whole graph, so the number of AMs is equal to the number of edges $= 2n^2$. Half the AMs are just translations, where the USCs of an edge and of its image are parallel. The others are flips, where the two USCs do meet at one vertex.

Define three AMs $a$, $b$, $c$ by their action on the edge $((0,0),(1,0))$ as $((1,0),(2,0))$, $((0,1),(1,1))$, $((0,0),(0,1))$ respectively. So $a$ is "right", $b$ is "up" and $c$ is "$x$-$y$ flip".

$a^n = b^n = c^2 = 1$, $ab = ba$, $cac = b$, $cbc = a$.

Let $d = ab = ba$ (called "diagonal"). Then $cd = dc$.

A typical flip can be written as $c{a^p}{b^q}$.

$(c{a^p}{b^q})^2 = d^{(p+q)}$.

So flips have even order dividing $2n$. There are hence exactly $n$ flip involutions: $c{a^p}{b^{(n-p)}}$. Write them as $cg^p$, where $g=ab^{-1}$.

Suppose $n$ has an odd factor $k$, so $n = km$. Then any AM of the form $c{g^p}{d^m}$ taken to the $k$th power gives ${(cg^p)^k}*{d^{mk}} = cg^p$. So these involutions are powers of other AMs, contrary to the request.

On the other hand, suppose $n$ is a power of $2$, and that a flip involution $f = h^{2^j}$ for some AM $h$. Then $f = (h^2)^{2^{j-1}}$. But, as shown above, $h^2$ must be a translation, not a flip, so $f$ cannot be a flip either. So, contrary to hypothesis, $f$ is not a power of another symmetry.

So to get the requested property it's necessary and sufficient that $n=2^s$, where $s\ge2$.