On the convergence rate of the fraction of simple algebras
- PDF / 278,753 Bytes
- 8 Pages / 439.37 x 666.142 pts Page_size
- 39 Downloads / 215 Views
Algebra Universalis
On the convergence rate of the fraction of simple algebras Florian Aichinger Abstract. We provide an improved lower bound for the convergence rate of the fraction of simple algebras using combinatorial arguments. Mathematics Subject Classification. 08A30. Keywords. Simple algebras, Probability, Fraction of algebras.
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 ρ (i.e., a type ρ consisting of finitely many operation symbols) and n ∈ N, we let Algρ,n be the set of algebras of type ρ with universe {1, . . . , n}. For any property Π of such algebras, we define |{A ∈ Algρ,n : A Π}| P (Π, Algρ,n ) := |Algρ,n | as the fraction of those algebras in Algρ,n that have property Π. We will be interested in the limit of P (Π, Algρ,n ) as n tends to infinity. To state this precisely, we set Algρ = n∈N Algρ,n , and define the fraction of finite algebras of type ρ having property Π by P (Π; Algρ ) := lim P (Π; Algρ,n ) n→∞
(1.1)
if this limit exists; P (Π; Algρ ) 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 ρ with at least one operation symbol of arity greater than 1, the fraction of finite algebras of type ρ that are idemprimal is 1. For a type ρ with at least two operation symbols, one at least unary and the other ´ Szendrei. Presented by A. Supported by the Austrian Science Fund (FWF): P29931.
58
Page 2 of 8
F. Aichinger
Algebra Univers.
at least binary, he showed that the fraction of finite algebras of type ρ 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, Algρ,n ) ≥ f (n), where limn→∞ f (n) = 1 but f (n) ≤ 1 − 4/n2 for all n ∈ 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 ≥ 3, and let ρ be a finite type that contains at least one operation symbol of arity k. Then P (S, Algρ,n ) ≥ 1 − exp(−nk−1 + 2nk−2 + n ln(n)). We note that this implies that for k ≥ 3, we have P (S, Algρ ) = 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 ∈ N, n > 1 and define fn := (1 + n1 )n , gn := (1 + n1 )n+1 , hn := (1 − n1 )n , in := (1 − n1 )n−2 . Then (fn )n∈N is an increasing sequence converging to e, (gn )n∈N is a decreasing sequence converging to e, (hn )n∈N is an increasing sequence converging to 1/e and (in )n∈N is a decreasing sequence converging to 1/e. Proof. It is a well known fact that (fn )n∈N a
Data Loading...
