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

$$\begin{aligned} P(\Pi ,\text {Alg}_{\rho , n}) := \frac{|\{\varvec{A}\in \text {Alg}_{\rho , n}:\, \varvec{A} \vDash \Pi \}|}{|\text {Alg}_{\rho , n}|} \end{aligned}$$

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

$$\begin{aligned} P(\Pi ;\text {Alg}_{\rho }) := \lim \limits _{n \rightarrow \infty } P(\Pi ;\text {Alg}_{\rho , n}) \end{aligned}$$
(1.1)

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

$$\begin{aligned} P(S,{\text {Alg}}_{\rho , n})\ge 1-{\text {exp}}(-n^{k-1}+2n^{k-2}+n{\text {ln}}(n)). \end{aligned}$$

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

$$\begin{aligned} f_n:=(1+\tfrac{1}{n})^n, g_n:=(1+\tfrac{1}{n})^{n+1}, h_n:=(1-\tfrac{1}{n})^{n}, i_n:=(1-\tfrac{1}{n})^{n-2}. \end{aligned}$$

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:

$$\begin{aligned} \begin{aligned} \frac{f_{n+1}}{f_n} {}&=\frac{(1+\frac{1}{n+1})^{n+1}}{(1+\frac{1}{n})^n}=\frac{n+2}{n+1}\left( \frac{n(n+2)}{(n+1)^2}\right) ^n=\frac{n+2}{n+1}\left( 1-\frac{1}{(n+1)^2}\right) ^n\\&\ge \frac{n+2}{n+1}\left( 1-\frac{n}{(n+1)^2}\right) =\frac{(n+2)(n^2+n+1)}{(n+1)^3}\\&=\frac{n^3+3n^2+3n+2}{n^3+3n^2+3n+1}>1 \end{aligned} \end{aligned}$$

We show that \((g_n)_{n\in {\mathbb {N}}}\) is decreasing:

$$\begin{aligned} \begin{aligned} \frac{g_n}{g_{n+1}} {}&=\frac{(1+\frac{1}{n})^{n+1}}{(1+\frac{1}{n+1})^{n+2}}=\left( \frac{(n+1)^2}{n(n+2)}\right) ^{n+1}\frac{1}{1+\frac{1}{n+1}}\\&=\left( 1+\frac{1}{n^2+2n}\right) ^{n+1}\frac{1}{1+\frac{1}{n+1}}>1 \end{aligned} \end{aligned}$$

The above inequality holds since, using Bernoulli’s inequality, we have

$$\begin{aligned} \left( 1+\frac{1}{n^2+2n}\right) ^{n+1}\ge 1+\frac{n+1}{n^2+2n}>1+\frac{n+1}{(n+1)^2}=1+\frac{1}{n+1}. \end{aligned}$$

We show that \((h_n)_{n\in {\mathbb {N}}}\) is increasing:

$$\begin{aligned} \frac{h_{n+1}}{h_n}=\frac{(1-\frac{1}{n+1})^{n+1}}{(1-\frac{1}{n})^n}=\frac{(\frac{n}{n+1})^{n+1}}{(\frac{n-1}{n})^n}\ge \frac{\frac{n(1-\frac{1}{n})+1}{n+1}}{((1-\frac{1}{n})^n\cdot 1)^{\frac{1}{n+1}}}>1 \end{aligned}$$

Here we have used the inequality of arithmetic and geometric means. It remains to show that \((i_n)_{n\in {\mathbb {N}}}\) is decreasing:

$$\begin{aligned} \begin{aligned} \frac{i_n}{i_{n+1}} {}&=\frac{(1-\frac{1}{n})^{n-2}}{(1-\frac{1}{n+1})^{n-1}}=\frac{(\frac{n-1}{n})^{n-2}}{(\frac{n}{n+1})^{n-1}}\\&=\frac{n+1}{n}\left( \frac{n^2-1}{n^2}\right) ^{n-2}=\frac{n+1}{n}\left( 1-\frac{1}{n^2}\right) ^{n-2}\\&\ge \frac{n+1}{n}\left( 1-\frac{n-2}{n^2}\right) =\frac{n+1}{n}\frac{n^2-n+2}{n^2}=\frac{n^3+n+2}{n^3}>1 \end{aligned} \end{aligned}$$

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.:

$$\begin{aligned} (\tfrac{n}{e}+1)^{n/e}\cdot n^{n-n/e-1}\cdot (n-1)^{2-n}\ge (\tfrac{n+1}{e}+1)^{(n+1)/e}\cdot (n+1)^{n-(n+1)/e}\cdot n^{1-n} \end{aligned}$$

or equivalently

$$\begin{aligned} \frac{f_n}{f_{n+1}}=\frac{\left( \frac{n}{e}+1 \right) ^{n/e}}{\left( \frac{n+1}{e}+1 \right) ^{(n+1)/e}}\cdot \frac{n^{n-n/e-1}}{(n+1)^{n-(n+1)/e}}\cdot \frac{(n-1)^{2-n}}{n^{1-n}}\ge 1. \end{aligned}$$

We can find a lower bound for the first factor, since

$$\begin{aligned} \begin{aligned} \frac{\left( \frac{n}{e}+1 \right) ^{n/e}}{\left( \frac{n+1}{e}+1 \right) ^{(n+1)/e}} {}&=\frac{\left( \frac{n}{e}+1 \right) ^{n/e}}{\left( \frac{n+1}{e}+1 \right) ^{n/e}\cdot (\frac{n+1}{e}+1)^{1/e}}\\&=(\frac{n+1}{e}+1)^{-1/e}\cdot \left( \frac{\frac{n}{e}+1+\frac{1}{e}}{\frac{n}{e}+1}\right) ^{-n/e} \\&=(\frac{n+1}{e}+1)^{-1/e}\cdot \left( 1+\frac{1}{e\cdot (\frac{n}{e}+1)}\right) ^{-n/e}\\&\ge \left( \frac{n+1}{e}+1 \right) ^{-1/e}\cdot \left( 1+\frac{1}{n}\right) ^{-n/e}. \end{aligned} \end{aligned}$$

For the second factor we have

$$\begin{aligned} \begin{aligned} \frac{n^{n-n/e-1}}{(n+1)^{n-(n+1)/e}} {}&=\frac{n^{-1}\cdot n^{n-n/e}}{(n+1)^{-1/e}\cdot (n+1)^{n-n/e}}\\&=n^{-1}\cdot (n+1)^{1/e}\cdot \left( \frac{n}{n+1}\right) ^{n-n/e}\\&=n^{-1}\cdot (n+1)^{1/e}\cdot (1+\frac{1}{n})^{-n}\cdot (1+\frac{1}{n})^{n/e}\\&\ge n^{-1}\cdot (n+1)^{1/e}\cdot \frac{1}{e}\cdot \left( 1+\frac{1}{n}\right) ^{n/e}. \end{aligned} \end{aligned}$$

And for the third factor we get

$$\begin{aligned} \begin{aligned} \frac{(n-1)^{2-n}}{n^{1-n}} {}&=n\cdot \left( \frac{n-1}{n}\right) ^{2-n}=n\cdot \frac{1}{\left( 1-\frac{1}{n}\right) ^{n-2}}\\&\ge n\cdot \frac{1}{\left( 1-\frac{1}{7}\right) ^5}=\left( \frac{7}{6}\right) ^{5}\cdot n, \end{aligned} \end{aligned}$$

since \(\left( 1-\frac{1}{n}\right) ^{n-2}\) is decreasing and \(n\ge 7\). Thus for the product we have

$$\begin{aligned} \begin{aligned} \frac{f_n}{f_{n+1}} {}&=\frac{\left( \frac{n}{e}+1 \right) ^{n/e}}{(\frac{n+1}{e}+1)^{(n+1)/e}}\cdot \frac{n^{n-n/e-1}}{(n+1)^{n-(n+1)/e}}\cdot \frac{(n-1)^{2-n}}{n^{1-n}}\\&\ge {\left( \frac{n+1}{e}+1 \right) ^{-1/e}\cdot \left( 1+\frac{1}{n}\right) ^{-n/e}\cdot \frac{1}{n}\cdot (n+1)^{1/e}\cdot \frac{1}{e}\cdot \left( 1+\frac{1}{n}\right) ^{n/e}\cdot \left( \frac{7}{6}\right) ^{5} n}\\&={\left( \frac{7}{6}\right) ^{5}\cdot \frac{1}{e}\cdot (n+1)^{1/e}\cdot \left( \frac{n+1}{e}+1 \right) ^{-1/e}}=\left( \frac{7}{6}\right) ^{5}\cdot \frac{1}{e}\cdot \left( \frac{n+1}{\frac{n+1}{e}+1}\right) ^{1/e}\\&=\left( \frac{7}{6}\right) ^{5}\cdot \frac{1}{e}\cdot \left( \frac{e\cdot (n+1)}{(n+1)+e}\right) ^{1/e} =\left( \frac{7}{6}\right) ^{5}\cdot \frac{1}{e}\cdot e^{1/e}\cdot \left( \frac{n+1}{n+1+e}\right) ^{1/e}. \end{aligned} \end{aligned}$$

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

$$\begin{aligned} (\tfrac{7}{6})^{5}\cdot e^{-1}\cdot e^{1/e}\cdot \left( \tfrac{n+1}{n+1+e}\right) ^{1/e}\ge \left( \tfrac{7}{6}\right) ^{5}\cdot e^{1/e-1}\cdot \left( \tfrac{8}{8+e}\right) ^{1/e}\ge 1.03>1. \end{aligned}$$

\(\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

$$\begin{aligned} \tfrac{n}{m}\le e(\tfrac{m-1}{m})\le (\tfrac{m+1}{m})^{m+1}(\tfrac{m-1}{m})=(\tfrac{m+1}{m})^m(\tfrac{m^2-1}{m^2})\le (\tfrac{m+1}{m})^m. \end{aligned}$$

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\),

$$\begin{aligned} a_m=m^{m-1}n^{n-m+1}\le (\tfrac{n}{e}+1)^{(n/e+1)-1}\cdot n^{n-n/e+1}=(\tfrac{n}{e}+1)^{n/e}\cdot n^{n-n/e+1}. \end{aligned}$$

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

$$\begin{aligned} (\sigma _1),\dots , (\sigma _k)\mapsto \{\{\sigma _1\},\dots , \{\sigma _k\}\}. \end{aligned}$$

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

$$\begin{aligned} P(\lnot S,{\text {Alg}}_{\rho , n})\le {\text {exp}}\left( -n^{k-1}+2n^{k-2}+n{\text {ln}}(n)\right) . \end{aligned}$$

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

$$\begin{aligned} N(f_1,\dots ,f_{m})\le N(f_1)\cdot \dots \cdot N(f_{m})\le N(f_1)\prod _{i=2}^{m} n^{n^{\text {ar}(f_i)}}. \end{aligned}$$

Hence for the fraction of such algebras we get

$$\begin{aligned} \frac{N(f_1,\dots ,f_{m})}{|\text {Alg}_{\rho ,n}|}=\frac{N(f_1,\dots ,f_{m})}{\prod _{i=1}^{m} n^{n^{\text {ar}(f_i)}}}\le \frac{N(f_1)\prod _{i=2}^{m} n^{n^{\text {ar}(f_i)}}}{\prod _{i=1}^{m} n^{n^{\text {ar}(f_i)}}}=\frac{N(f_1)}{n^{n^{k}}}. \end{aligned}$$

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

$$\begin{aligned} \sum \limits _{j=1}^{l} |A_j|^{|A_i|} \end{aligned}$$

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

$$\begin{aligned} \prod \limits _{i=1}^l\sum \limits _{j=1}^l |A_j|^{|A_i|} \end{aligned}$$

ways to choose the values of \(f(a,\alpha _1,\dots , \alpha _{k-1})\) with \(a\in A\). Hence there are at most

$$\begin{aligned} \prod \limits _{\alpha \in \{1,\dots ,n\}^{k-1}}\prod \limits _{i=1}^l\sum \limits _{j=1}^l |A_j|^{|A_i|}=\left( \prod \limits _{i=1}^l\sum \limits _{j=1}^l |A_j|^{|A_i|}\right) ^{n^{k-1}} \end{aligned}$$
(3.1)

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

$$\begin{aligned} \sum \limits _{j=1}^{l} |A_j|^{|A_i|}\le \sum \limits _{j=1}^{l} |A_j|\cdot m^{|A_i|-1}=m^{|A_i|-1} \sum \limits _{j=1}^{l} |A_j|=n m^{|A_i|-1}. \end{aligned}$$

Thus

$$\begin{aligned} \prod \limits _{i=1}^l\sum \limits _{j=1}^l |A_j|^{|A_i|}\le \prod \limits _{i=1}^l n m^{|A_i|-1}=n^l m^{\sum \limits _{i=1}^l |A_i|-l}=n^l m^{n-l}. \end{aligned}$$

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

$$\begin{aligned} \frac{n^n(n^2(n-1)^{n-2})^{n^{k-1}}}{n^{n^k}} \end{aligned}$$

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

$$\begin{aligned} \begin{aligned} P(\lnot S,{\text {Alg}}_{\rho , n}) {}&\le \frac{n^n(n^2(n-1)^{n-2})^{n^{k-1}}}{n^{n^k}}=n^n\frac{(n-1)^{(n-2)n^{k-1}}}{n^{(n-2)n^{k-1}}}\\&=n^n\left( \frac{n-1}{n}\right) ^{(n-2)n^{k-1}}=n^n \left( \left( 1-\frac{1}{n}\right) ^n\right) ^{(n-2)n^{k-2}} \\&\le n^n e^{(2-n)n^{k-2}}=e^{-n^{k-1}+2n^{k-2}+n\text {ln}(n)} \end{aligned} \end{aligned}$$

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 \)