Subsemigroup, ideal and congruence growth of free semigroups
| Autor: | Robert Snocken, Alex Bailey, Martin Finn-Sell |
|---|---|
| Rok vydání: | 2014 |
| Předmět: |
Polynomial
Pure mathematics Sequence Rank (linear algebra) General Mathematics 010102 general mathematics 0102 computer and information sciences Group Theory (math.GR) Type (model theory) Congruence relation 01 natural sciences Exponential function 010201 computation theory & mathematics FOS: Mathematics Mathematics - Combinatorics Congruence (manifolds) Ideal (ring theory) Combinatorics (math.CO) 20M05 20E07 0101 mathematics Mathematics - Group Theory Mathematics |
| DOI: | 10.48550/arxiv.1409.2444 |
| Popis: | Using Rees index, the subsemigroup growth of free semigroups is investigated. Lower and upper bounds for the sequence are given and it is shown to have superexponential growth of strict type $n^n$ for finite free rank greater than 1. It is also shown that free semigroups have the fastest subsemigroup growth of all finitely generated semigroups. Ideal growth is shown to be exponential with strict type $2^n$ and congruence growth is shown to be at least exponential. In addition we consider the case when the index is fixed and rank increasing, proving that for subsemigroups and ideals this sequence fits a polynomial of degree the index, whereas for congruences this fits an exponential equation of base the index. We use these results to describe an algorithm for computing values of these sequences and give a table of results for low rank and index. Comment: 29 pages including 4 appendices |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|