Research output: Contribution to journal › Article › peer-review

- https://arxiv.org/abs/1803.01377
Accepted author manuscript

James Hyde, Julius Jonušas, James D. Mitchell, Yann H. Péresse

A universal sequence for a group or semigroup S is a sequence of words w_{1}, w_{2},... such that for any sequence s1, s2,... ε S, the equations w_{n} = s_{n}, n ε ℕ, can be solved simultaneously in S. For example, Galvin showed that the sequence {a^{-1}(a^{n}ba^{-n})b^{-1}(a^{n}b^{-1}a^{-n})ba: n ε ℕ is universal for the symmetric group Sym(X) when X is infinite, and Sierpiński showed that (a^{2}b^{3} (abab^{3})^{n+1} ab^{2} ab^{3})_{nεℕ} is universal for the monoid X^{X} of functions from the infinite set X to itself.

In this paper, we show that under some conditions, the set of universal sequences for the symmetric group on an infinite set X is independent of the cardinality of X. More precisely, we show that if Y is any set such that |Y| ≥ |X|, then every universal sequence for Sym(X) is also universal for Sym(Y). If |X| > 2^{ℵ0}, then the converse also holds. It is shown that an analogue of this theorem holds in the context of inverse semigroups, where the role of the symmetric group is played by the symmetric inverse monoid. In the general context of semigroups, the full transformation monoid X^{X} is the natural analogue of the symmetric group and the symmetric inverse monoid. If X and Y are arbitrary infinite sets, then it is an open question as to whether or not every sequence that is universal for X^{X} is also universal for Y^{Y}. However, we obtain a sufficient condition for a sequence to be universal for X^{X} which does not depend on the cardinality of X. A large class of sequences satisfy this condition, and hence are universal for X^{X} for every infinite set X.

In this paper, we show that under some conditions, the set of universal sequences for the symmetric group on an infinite set X is independent of the cardinality of X. More precisely, we show that if Y is any set such that |Y| ≥ |X|, then every universal sequence for Sym(X) is also universal for Sym(Y). If |X| > 2

Original language | English |
---|---|

Pages (from-to) | 1917-1931 |

Journal | Proceedings of the American Mathematical Society |

Volume | 148 |

Issue number | 5 |

Early online date | 28 Jan 2020 |

DOIs | |

Publication status | Published - May 2020 |

**Discover related content**

Find related publications, people, projects and more using interactive charts.

## GAP – Groups, Algorithms, and Programming, Version 4.11.1

The GAP Group, Behrends, R., Breuer, T., Horn, M., Hulpke, A., Jefferson, C. A., Konovalov, A., Linton, S. A., Lübeck, F., Mitchell, J. D., Pfeiffer, M. J., Siccha, S. & Torpey, M. C., 2 Mar 2021Research output: Non-textual form › Software

## GAP – Groups, Algorithms, and Programming, Version 4.11.0

The GAP Group, Behrends, R., Breuer, T., Horn, M., Hulpke, A., Jefferson, C. A., Konovalov, A., Linton, S. A., Lübeck, F., Mitchell, J. D., Pfeiffer, M. J., Siccha, S. & Torpey, M. C., 29 Feb 2020Research output: Non-textual form › Software

## GAP – Groups, Algorithms, and Programming, Version 4.10.2

The GAP Group, Behrends, R., Breuer, T., Horn, M., Hulpke, A., Jefferson, C. A., Konovalov, A., Linton, S. A., Lübeck, F., Mitchell, J. D., Pfeiffer, M. J., Siccha, S. & Torpey, M. C., 19 Jun 2019Research output: Non-textual form › Software

## Computing finite semigroups

East, J., Egri-Nagy, A., Mitchell, J. D. & Péresse, Y., May 2019, In: Journal of Symbolic Computation. 92, p. 110-155 46 p.Research output: Contribution to journal › Article › peer-review

## On the Hausdorff dimension of microsets

Fraser, J. M., Howroyd, D. C., Käenmäki, A. & Yu, H., Nov 2019, In: Proceedings of the American Mathematical Society. 147, 11, p. 4921-4936 16 p.Research output: Contribution to journal › Article › peer-review

## On The

Fraser, J. M. & Kempton, T., Jan 2018, In: Proceedings of the American Mathematical Society. 146, 1, p. 161-173*L*dimensions of measures on Heuter-Lalley type self-affine sets^{q}Research output: Contribution to journal › Article › peer-review

## Finite presentability and isomorphism of Cayley graphs of monoids

Awang, J. S., Pfeiffer, M. J. & Ruskuc, N., Nov 2017, In: Proceedings of the American Mathematical Society. 145, 11, p. 4585-4593Research output: Contribution to journal › Article › peer-review

## The Assouad dimension of self-affine carpets with no grid structure

Fraser, J. M. & Jordan, T., 16 Jun 2017, In: Proceedings of the American Mathematical Society. 145, p. 4905-4918Research output: Contribution to journal › Article › peer-review

ID: 255237369