Small partial Latin squares that embed in an infinite group but not into any finite group

Research output: Contribution to journalArticleResearchpeer-review

Abstract

Suppose that Y1, Y2, Y3 are finite sets and P ⊆ Y1 × Y2 × Y3.  We say that P embeds in a group G if there exist injective maps Φi :Yi → G for i = 1, 2, 3 such that Φ1(y1)Φ2(y2) = Φ3(y3) for each (y1,y2,y3) ∈ P. Hirsch and Jackson asked for the cardinality of the smallest P that embeds in some infinite group but not into any finite group.  We prove that the answer to their question is 12. Moreover, we show that there are 50 examples of cardinality 12, up to equivalence, and each of them embeds in the (infinite) Baumslag group G =〈a,b|b=[b,ba]〉. Our proof uses computations to answer questions about finitely presented groups which are known to be algorithmically undecidable in general.

Original languageEnglish
Pages (from-to)142-152
Number of pages11
JournalJournal of Symbolic Computation
Volume86
DOIs
Publication statusPublished - 2018

Keywords

  • Baumslag group
  • Finitely presented group
  • Group embedding
  • Partial Latin square

Cite this

@article{0b14e51854e143fc9a440a3aa766dd58,
title = "Small partial Latin squares that embed in an infinite group but not into any finite group",
abstract = "Suppose that Y1, Y2, Y3 are finite sets and P ⊆ Y1 × Y2 × Y3.  We say that P embeds in a group G if there exist injective maps Φi :Yi → G for i = 1, 2, 3 such that Φ1(y1)Φ2(y2) = Φ3(y3) for each (y1,y2,y3) ∈ P. Hirsch and Jackson asked for the cardinality of the smallest P that embeds in some infinite group but not into any finite group.  We prove that the answer to their question is 12. Moreover, we show that there are 50 examples of cardinality 12, up to equivalence, and each of them embeds in the (infinite) Baumslag group G =〈a,b|b=[b,ba]〉. Our proof uses computations to answer questions about finitely presented groups which are known to be algorithmically undecidable in general.",
keywords = "Baumslag group, Finitely presented group, Group embedding, Partial Latin square",
author = "Heiko Dietrich and Wanless, {Ian M.}",
year = "2018",
doi = "10.1016/j.jsc.2017.04.002",
language = "English",
volume = "86",
pages = "142--152",
journal = "Journal of Symbolic Computation",
issn = "0747-7171",
publisher = "Elsevier",

}

Small partial Latin squares that embed in an infinite group but not into any finite group. / Dietrich, Heiko; Wanless, Ian M.

In: Journal of Symbolic Computation, Vol. 86, 2018, p. 142-152.

Research output: Contribution to journalArticleResearchpeer-review

TY - JOUR

T1 - Small partial Latin squares that embed in an infinite group but not into any finite group

AU - Dietrich, Heiko

AU - Wanless, Ian M.

PY - 2018

Y1 - 2018

N2 - Suppose that Y1, Y2, Y3 are finite sets and P ⊆ Y1 × Y2 × Y3.  We say that P embeds in a group G if there exist injective maps Φi :Yi → G for i = 1, 2, 3 such that Φ1(y1)Φ2(y2) = Φ3(y3) for each (y1,y2,y3) ∈ P. Hirsch and Jackson asked for the cardinality of the smallest P that embeds in some infinite group but not into any finite group.  We prove that the answer to their question is 12. Moreover, we show that there are 50 examples of cardinality 12, up to equivalence, and each of them embeds in the (infinite) Baumslag group G =〈a,b|b=[b,ba]〉. Our proof uses computations to answer questions about finitely presented groups which are known to be algorithmically undecidable in general.

AB - Suppose that Y1, Y2, Y3 are finite sets and P ⊆ Y1 × Y2 × Y3.  We say that P embeds in a group G if there exist injective maps Φi :Yi → G for i = 1, 2, 3 such that Φ1(y1)Φ2(y2) = Φ3(y3) for each (y1,y2,y3) ∈ P. Hirsch and Jackson asked for the cardinality of the smallest P that embeds in some infinite group but not into any finite group.  We prove that the answer to their question is 12. Moreover, we show that there are 50 examples of cardinality 12, up to equivalence, and each of them embeds in the (infinite) Baumslag group G =〈a,b|b=[b,ba]〉. Our proof uses computations to answer questions about finitely presented groups which are known to be algorithmically undecidable in general.

KW - Baumslag group

KW - Finitely presented group

KW - Group embedding

KW - Partial Latin square

UR - http://www.scopus.com/inward/record.url?scp=85020134797&partnerID=8YFLogxK

U2 - 10.1016/j.jsc.2017.04.002

DO - 10.1016/j.jsc.2017.04.002

M3 - Article

VL - 86

SP - 142

EP - 152

JO - Journal of Symbolic Computation

JF - Journal of Symbolic Computation

SN - 0747-7171

ER -