Abstract
We provide an improved lower bound for the convergence rate of the fraction of simple algebras using combinatorial arguments.
Similar content being viewed by others
Avoid common mistakes on your manuscript.
1 Introduction
In this note, we investigate the probability that a randomly chosen finite algebra of a given type is simple. For a given finite type \(\rho \) (i.e., a type \(\rho \) consisting of finitely many operation symbols) and \(n\in {\mathbb {N}}\), we let \({\text {Alg}}_{\rho ,n}\) be the set of algebras of type \(\rho \) with universe \(\{1,\dots , n\}\). For any property \(\Pi \) of such algebras, we define
as the fraction of those algebras in \({\text {Alg}}_{\rho ,n}\) that have property \(\Pi \). We will be interested in the limit of \(P(\Pi ,\text {Alg}_{\rho , n})\) as n tends to infinity. To state this precisely, we set \(\text {Alg}_{\rho }=\bigcup _{n\in {\mathbb {N}}} \text {Alg}_{\rho , n}\), and define the fraction of finite algebras of type \(\rho \) having property \(\Pi \) by
if this limit exists; \(P(\Pi ;\text {Alg}_{\rho })\) is undefined otherwise. In [2], R.O. Davies showed that the fraction of primal groupoids is 1/e. Before, V.L. Murskiĭ had proved that for a type \(\rho \) with at least one operation symbol of arity greater than 1, the fraction of finite algebras of type \(\rho \) that are idemprimal is 1. For a type \(\rho \) with at least two operation symbols, one at least unary and the other at least binary, he showed that the fraction of finite algebras of type \(\rho \) that are primal is 1 [4]. Clearly, since every idemprimal algebra is simple, the fraction of simple algebras is bounded from below by the fraction of idemprimal algebras. We will consider the convergence rate of the limit given in (1.1). Denote by S the property of being simple. If we extract a bound from Murskiĭ’s proof, we obtain f(n) with \(P(S,\text {Alg}_{\rho , n})\ge f(n)\), where \({\text {lim}}_{n\rightarrow \infty } f(n)=1\) but \(f(n)\le 1-4/n^2\) for all \(n\in {\mathbb {N}}\) [1, Theorem 6.17]. In the case where there is at least one operation symbol of arity greater or equal 3, we provide a lower bound with faster convergence to 1.
Theorem 1.1
Let \(k\ge 3\), and let \(\rho \) be a finite type that contains at least one operation symbol of arity k. Then
We note that this implies that for \(k\ge 3\), we have \(P(S,{\text {Alg}}_{\rho })=1\). By a result of R. Freese, this fraction does not change if we count algebras up to isomorphism instead [3].
2 Preliminaries
In this section we provide the inequalities that we will need in the proof of Theorem 1.1.
Lemma 2.1
Let \(n\in {\mathbb {N}}\), \(n>1\) and define
Then \((f_n)_{n\in {\mathbb {N}}}\) is an increasing sequence converging to e, \((g_n)_{n\in {\mathbb {N}}}\) is a decreasing sequence converging to e, \((h_n)_{n\in {\mathbb {N}}}\) is an increasing sequence converging to 1/e and \((i_n)_{n\in {\mathbb {N}}}\) is a decreasing sequence converging to 1/e.
Proof
It is a well known fact that \((f_n)_{n\in {\mathbb {N}}}\) and \((g_n)_{n\in {\mathbb {N}}}\) are converging to e while \((h_n)_{n\in {\mathbb {N}}}\) and \((i_n)_{n\in {\mathbb {N}}}\) are converging to 1/e. We show that \((f_n)_{n\in {\mathbb {N}}}\) is increasing using Bernoulli’s inequality:
We show that \((g_n)_{n\in {\mathbb {N}}}\) is decreasing:
The above inequality holds since, using Bernoulli’s inequality, we have
We show that \((h_n)_{n\in {\mathbb {N}}}\) is increasing:
Here we have used the inequality of arithmetic and geometric means. It remains to show that \((i_n)_{n\in {\mathbb {N}}}\) is decreasing:
Here we have again used Bernoulli’s inequality. \(\square \)
Lemma 2.2
For \(n\in {\mathbb {N}}\), let \(f_n:=(\frac{n}{e}+1)^{n/e}\cdot n^{n-n/e-1}\cdot (n-1)^{2-n}\). Then \((f_n)_{n\ge 7}\) is decreasing.
Proof
We want to show that for \(n\ge 7\), \(f_n\ge f_{n+1}\), i.e.:
or equivalently
We can find a lower bound for the first factor, since
For the second factor we have
And for the third factor we get
since \(\left( 1-\frac{1}{n}\right) ^{n-2}\) is decreasing and \(n\ge 7\). Thus for the product we have
Clearly \(\frac{n+1}{n+1+e}\) is converging to 1 increasingly as \(n\rightarrow \infty \) and so is \(\left( \frac{n+1}{n+1+e}\right) ^{1/e}\), and thus \(\left( \frac{n+1}{n+1+e}\right) ^{1/e}\ge \left( \frac{8}{8+e}\right) ^{\frac{1}{e}}\) for \(n\ge 7\). Hence
\(\square \)
Lemma 2.3
Let \(n\in {\mathbb {N}}\) with \(n\ge 3\), and for \(m\in \{2,\dots , n-1\}\), let \(a_m:= m^{m-1}n^{n-m+1}\). Then for all \(m\in \{2,\dots , n-1\}\), we have \(a_m\le a_{n-1}=n^2(n-1)^{n-2}\).
Proof
We prove the statement distinguishing between three cases.
Case\(m\le n/e\): Then \(n/m\ge e\). Since \((1+\tfrac{1}{m})^m\) is an increasing sequence converging to e, we have \(\frac{n}{m}\ge \left( \frac{m+1}{m}\right) ^m\). Thus \(nm^{m-1}\ge (m+1)^m\) and hence \(nm^{m-1}n^{n-m}\ge (m+1)^m n^{n-m}\). But then \(a_m=m^{m-1}n^{n-m+1}\ge (m+1)^{(m+1)-1}n^{n-(m+1)+1}=a_{m+1}\). Thus \((a_m)\) is decreasing for \(2\le m\le n/e\), i.e. \(a_2=2n^{n-1}\ge a_m\) in this interval. We now show that for \(n\ge 3\), \(a_2\le a_{n-1}\), i.e.: \(2n^{n-1}\le n^2(n-1)^{n-2}\) or equivalently \(2\le n(\frac{n-1}{n})^{n-2}\). For \(3\le n \le 5\) it can be seen easily that the inequality holds. Therefore, let \(n\ge 6\). Since \((\frac{n-1}{n})^{n-2}\) converges to 1/e monotonically decreasing, \(n(\frac{n-1}{n})^{n-2}\ge \frac{n}{e}\ge 6/e> 2\).
Case \(m\ge n/e+1\): Then \(n/m\le e(\frac{m-1}{m})\). Since \((\frac{m+1}{m})^{m+1}\) is a decreasing sequence converging to e, we can write
Therefore, proceeding as in the previous case, we get \(a_m=m^{m-1}n^{n-m+1}\le (m+1)^{(m+1)-1}n^{n-(m+1)+1}=a_{m+1}\). Thus \((a_m)\) is increasing in this interval and hence is bounded above by \(a_{n-1}\).
Case \(n/e< m < n/e+1\): For \(3\le n\le 11\) it can be checked easily that \(a_m\le a_n\). Therefore, let \(n\ge 12\). Since \(n/e< m < n/e+1\),
We want to show that \((\frac{n}{e}+1)^{n/e}\cdot n^{n-n/e+1}\le n^2\cdot (n-1)^{n-2}=a_{n-1}\) or equivalently \((\frac{n}{e}+1)^{n/e}\cdot n^{n-n/e-1}\cdot (n-1)^{2-n}=:f_n\le 1\). By Lemma 2.2, we know that \((f_n)_{n\ge 7}\) is decreasing. Thus, since \(f_{12}<1\), \(f_n<1\) for \(n\ge 12\). \(\square \)
For our purposes, the following rough estimation of the Bell number will be sufficient.
Lemma 2.4
There are at most n! possible partitions of an n-element set.
Proof
Consider the mapping \(\mu : S_n\rightarrow P_n\) from the symmetric group of an n-element set to the set of partitions of an n-element set, where a cycle decomposition is mapped to the corresponding set of subsets
Since \(\mu \) is obviously surjective, \(|P_n|\le |S_n|=n!\). \(\square \)
3 The fraction of simple algebras
Proof of Theorem 1.1
Obviously every one or two-element algebra is simple and thus we we can restrict ourselves to the case \(n\ge 3\). Let \(k\in {\mathbb {N}}\) and let \(\rho \) be a finite type containing at least one operation symbol of arity k. Thus for \(m\in {\mathbb {N}}\) and finitary operation symbols \(f_1,\dots , f_m\), we can write \(\rho =\{f_1,\dots ,f_m\}\) and we assume that \(\text {arity}(f_1)=k\). In order to prove the statement of the theorem, we will show that
To this end, we call an algebra \(\varvec{A}\in {\text {Alg}}_{\rho , n}\) \(\rho \)-admissible if and only if its operations preserve a nontrivial equivalence relation. We denote the number of \(\rho \)-admissible algebras by \(N(\rho )=N(f_1,\dots , f_{m})\). Clearly, if \(\varvec{A}\) is \(\rho \)-admissible, then for every \(f_i\in \rho \), \(\langle A,f_i\rangle \) is \(\{f_i\}\)-admissible. Thus
Hence for the fraction of such algebras we get
Therefore we may restrict ourselves to the case that \(\rho \) contains only one single k-ary operation symbol f. Fix a nontrivial equivalence relation \(\theta \) on A. How many algebras in \({\text {Alg}}_{\rho ,n}\) preserve \(\theta \)? Since \(A/\theta \) is a partition of A, there are \(l\in {\mathbb {N}}\) with \(1\le l\le n\) and some disjoint \(A_i\in {\mathcal {P}}(A)\) with \(\bigcup _{i=1}^l A_i=A\) such that we can write \(A/\theta =\{A_1,\dots , A_l\}\). Fix \(1\le i\le l\) and \((\alpha _1,\dots , \alpha _{k-1})\in \{1,\dots , n\}^{k-1}\) and let \(a,b\in A_i\) (i.e. \(a\mathrel {\theta } b\)). If f preserves \(\theta \), we have \(f(a,\alpha _1,\dots ,\alpha _{k-1})\mathrel {\theta } f(b,\alpha _1,\dots ,\alpha _{k-1})\) and hence for some \(1\le j\le l\), \(f(a,\alpha _1,\dots ,\alpha _{k-1}), f(b,\alpha _1,\dots ,\alpha _{k-1})\in A_j\). Thus there are
ways to choose all values of \(f(a_,\alpha _1,\dots ,\alpha _{k-1})\) where \(a\in A_i\). Since this can be done for every \(1\le i\le l\), there are
ways to choose the values of \(f(a,\alpha _1,\dots , \alpha _{k-1})\) with \(a\in A\). Hence there are at most
algebras in \({\text {Alg}}_{\rho ,n}\) preserving \(\theta \). We will now find an upper bound for (3.1). Let \(m:=\text {max}\{|A_i|: A_i\in A/\theta \}\). Then
Thus
Since l is the number of equivalence classes and m the size of the equivalence class of maximal cardinality in \(A/\theta \), clearly \(1\le l\le n-m+1\) and hence \(n^l m^{n-l}\le n^{n-m+1}m^{m-1}\). Since \(\theta \) is a proper nontrivial equivalence, we have \(2\le m\le n-1\). Thus Lemma 2.3 yields \(n^{n-m+1}m^{m-1}\le n^2(n-1)^{n-2}\), and hence the number of algebras in \({\text {Alg}}_{\rho ,n}\) preserving \(\theta \) is bounded from above by \({(n^2(n-1)^{n-2})^{n^{k-1}}}\). Since every equivalence relation can be identified with its corresponding partition, by Lemma 2.4 there are at most \(n!\le n^n\) choices for \(\theta \). For every such \(\theta \) we have at most \((n^2(n-1)^{n-2})^{n^{k-1}}\) algebras preserving it and hence in total there are at most \(n^n(n^2(n-1)^{n-2})^{n^{k-1}}\) algebras in \({\text {Alg}}_{\rho ,n}\) admitting a nontrivial congruence relation. Since the number of all possible algebras is \(n^{n^k}\), we are interested in the fraction
which is an upper bound for \(P(\lnot S,{\text {Alg}}_{\rho , n})\), the fraction of n-element non-simple algebras of type \(\rho \). Using the fact that \((1-\tfrac{1}{n})^n\) converges to 1/e monotonically increasing, we get
Thus \(P( S,{\text {Alg}}_{\rho , n})\ge 1-{\text {exp}}(-n^{k-1}+2n^{k-2}+n{\text {ln}}(n))\), and hence for \(k\ge 3\) converges to 1 as \(n\rightarrow \infty \). \(\square \)
References
Bergman, C.: Universal Algebra, Fundamentals and Selected Topics. Pure and Applied Mathematics, vol. 301. CRC Press, Boca Raton (2012)
Davies, R.O.: On \(n\)-valued Sheffer functions. Zeitschr. Math. Logik Grundlagen Math. 25, 293–298 (1979)
Freese, R.: On the two kinds of probability in algebra. Algebra Univ. 27, 70–79 (1990)
Murskiĭ, V.L.: The existence of a finite basis of identities, and other properties of “almost all” finite algebras. Probl. Kibernet. 30, 43–56 (1975). (Russian)
Acknowledgements
The author would like to thank Erhard Aichinger for numerous discussions on the topic of the present note and lots of comments that greatly improved this manuscript.
Funding
Open access funding provided by Johannes Kepler University Linz.
Author information
Authors and Affiliations
Corresponding author
Additional information
Presented by Á. Szendrei.
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Supported by the Austrian Science Fund (FWF): P29931.
Rights and permissions
Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.
About this article
Cite this article
Aichinger, F. On the convergence rate of the fraction of simple algebras. Algebra Univers. 81, 58 (2020). https://doi.org/10.1007/s00012-020-00684-4
Published:
DOI: https://doi.org/10.1007/s00012-020-00684-4