Random models of idempotent linear Maltsev conditions. I. Idemprimality

Abstract

We extend a well-known theorem of Murskiǐ to the probability space of finite models of a system ${\mathcal {M}}$ of identities of a strong idempotent linear Maltsev condition. We characterize the models of ${\mathcal {M}}$ in a way that can be easily turned into an algorithm for producing random finite models of ${\mathcal {M}}$, and we prove that under mild restrictions on ${\mathcal {M}}$, a random finite model of ${\mathcal {M}}$ is almost surely idemprimal. This implies that even if such an ${\mathcal {M}}$ is distinguishable from another idempotent linear Maltsev condition by a finite model $\mathbf {A}$ of ${\mathcal {M}}$, a random search for a finite model $\mathbf {A}$ of ${\mathcal {M}}$ with this property will almost surely fail.

Appendix A. Proof of Lemma 4.4

Let $\zeta _n(k)$ denote the k-th summand on the left hand side in (4.5), that is,

$$\begin{aligned} \zeta _n(k):=\left( {\begin{array}{c}n\\ k\end{array}}\right) \left( \frac{k}{n}\right) ^{\left( {\begin{array}{c}k\\ 2\end{array}}\right) }. \end{aligned}$$

Or goal is to prove that

$$\begin{aligned} \lim _{n\rightarrow \infty } \sum _{k=4}^{n-1}\zeta _n(k)=0. \end{aligned}$$

(A.1)

Claim A.1

For arbitrary constants $0<u<v<1$ we have that

$$\begin{aligned} \lim _{n\rightarrow \infty }\sum _{un\le k\le vn}\zeta _n(k)=0. \end{aligned}$$

Proof of Claim A.1

For $un\le k\le vn$,

$$\begin{aligned} \zeta _n(k) =\left( {\begin{array}{c}n\\ k\end{array}}\right) \left( \frac{k}{n}\right) ^{\left( {\begin{array}{c}k\\ 2\end{array}}\right) } \le 2^n v^{un(un-1)/2} =\Bigl (2(\sqrt{v})^{u(un-1)}\Bigr )^n. \end{aligned}$$

Since $(\sqrt{v})^{u(un-1)}<\frac{1}{3}$ for large enough n, we get that

$$\begin{aligned} \sum _{un\le k\le vn}\zeta _n(k)\le n\Bigl (\frac{2}{3}\Bigr )^n \rightarrow 0 \qquad \text {as }n\rightarrow \infty . \end{aligned}$$

$\square$

To establish (A.1), it remains to find u, v with $0<u<v<1$ such that

$$\begin{aligned} \sum _{4\le k< un}\zeta _n(k)\rightarrow 0 \quad \text {and}\quad \sum _{vn< k< n}\zeta _n(k)\rightarrow 0 \quad \text {as }n\rightarrow \infty . \end{aligned}$$

This will be accomplished in Claims A.2 and A.3 below.

Claim A.2

For $u=\frac{1}{2}$ we have that $\displaystyle \lim \nolimits _{n\rightarrow \infty }\sum \nolimits _{4\le k< un}\zeta _n(k)= 0.$

Proof of Claim A.2

The following estimates show that the sequence $\zeta _n(k)$ ($k=4,5,\ldots$) is decreasing for $4\le k\le \frac{1}{2}n$:

$$\begin{aligned} \frac{\zeta _n(k+1)}{\zeta _n(k)}= & {} \frac{n-k}{k+1}\cdot \left( \frac{k+1}{n}\right) ^k \cdot \left( \frac{k+1}{k}\right) ^{\left( {\begin{array}{c}k\\ 2\end{array}}\right) }\\= & {} \frac{n-k}{n}\cdot \left( \frac{k+1}{n}\right) ^{k-1} \cdot \left( \Bigl (1+\frac{1}{k}\Bigr )^k\right) ^{\frac{k-1}{2}} \le \left( \frac{k+1}{n}\right) ^{k-1}\cdot e^{\frac{k-1}{2}}\\&<\left( \frac{k+1}{n}\right) ^{k-1}\cdot 2^{k-1}\le 1 \qquad \text {if}\quad k+1\le \frac{n}{2}. \end{aligned}$$

The first term of the sequence is

$$\begin{aligned} \zeta _n(4)=\left( {\begin{array}{c}n\\ 4\end{array}}\right) \left( \frac{4}{n}\right) ^6 \le \frac{4^6}{4!}\cdot \frac{1}{n^2}, \end{aligned}$$

hence

$$\begin{aligned} \sum _{4\le k\le un}\zeta _n(k)\le un\cdot \frac{4^6}{4!}\cdot \frac{1}{n^2} \rightarrow 0 \qquad \text {as }n\rightarrow \infty . \end{aligned}$$

$\square$

Claim A.3

There exists a constant v with $\frac{1}{2}<v<1$ such that

$$\begin{aligned} \lim _{n\rightarrow \infty }\sum _{vn< k< n}\zeta _n(k)= 0. \end{aligned}$$

Proof of Claim A.3

As in the proof of [3, Lemma 6.22C], letting $\ell :=\lfloor vn\rfloor$ we have that

$$\begin{aligned} \left( {\begin{array}{c}n\\ \ell \end{array}}\right) <\sqrt{n}\left( \Bigl (v-\frac{1}{n}\Bigr )^{v} \Bigl (1-v\Bigr )^{1-v}\Bigl (1-v\Bigr )^{\frac{1}{n}}\right) ^{-n}. \end{aligned}$$

Now let k be such that $(\frac{n}{2}<)\,vn<k<n$. We may assume without loss of generality that $n>8$, so $k\ge 4$, and hence $\left( {\begin{array}{c}k\\ 2\end{array}}\right) \ge \frac{k^2}{3}$. Thus,

$$\begin{aligned} \left( \frac{k}{n}\right) ^{\left( {\begin{array}{c}k\\ 2\end{array}}\right) }&{}\le \left( \frac{n-1}{n}\right) ^{\left( {\begin{array}{c}k\\ 2\end{array}}\right) } \le \left( \frac{n-1}{n}\right) ^{\frac{k^2}{3}}\\&{}\le \left( \frac{n-1}{n}\right) ^{\frac{v^2n^2}{3}} =\left( \Bigl (1-\frac{1}{n}\Bigr )^{n}\right) ^{\frac{v^2n}{3}} <\left( \frac{1}{e}\right) ^{\frac{v^2n}{3}}. \end{aligned}$$

Since $k\ge vn\ge \ell$ and $vn>\frac{n}{2}$, it follows that $\left( {\begin{array}{c}n\\ k\end{array}}\right) \le \left( {\begin{array}{c}n\\ \ell \end{array}}\right)$. Therefore, by combining the previous estimates we obtain that

$$\begin{aligned} \zeta _n(k)=\left( {\begin{array}{c}n\\ k\end{array}}\right) \left( \frac{k}{n}\right) ^{\left( {\begin{array}{c}k\\ 2\end{array}}\right) }&{}\le \sqrt{n}\left( \Bigl (v-\frac{1}{n}\Bigr )^{v} \Bigl (1-v\Bigr )^{1-v}\Bigl (1-v\Bigr )^{\frac{1}{n}}\right) ^{-n} \left( \frac{1}{e}\right) ^{\frac{v^2n}{3}}\\&{}= \sqrt{n}\left( \frac{1}{\Bigl (v-\frac{1}{n}\Bigr )^{v} \Bigl (1-v\Bigr )^{1-v}e^{\frac{v^2}{3}}}\right) ^n(1-v)^{-1}\\&{}\le \sqrt{n}\left( \frac{1}{\Bigl (v-\frac{1}{16}\Bigr )^{v} \Bigl (1-v\Bigr )^{1-v}e^{\frac{v^2}{3}}}\right) ^n(1-v)^{-1}\\&\qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \text {if } n\ge 16. \end{aligned}$$

Let $w(v):=\Bigl (v-\frac{1}{16}\Bigr )^{v}\Bigl (1-v\Bigr )^{1-v}e^{\frac{v^2}{3}}$. Since $\lim _{v\rightarrow 1}w(v)=\frac{15}{16}e^{1/3}>1$, there exists v with $\frac{1}{2}<v<1$ such that $w(v)>1$; for example, $v=.95$ works. For any such choice of v,

$$\begin{aligned} \sum _{vn<k<n}\zeta _n(k)&{}\le \sum _{vn<k<n}\frac{\sqrt{n}}{1-v}\left( \frac{1}{w(v)}\right) ^n\\&{}\le n(1-v)\frac{\sqrt{n}}{1-v}\left( \frac{1}{w(v)}\right) ^n \rightarrow 0 \qquad \text {as }n\rightarrow \infty . \end{aligned}$$

$\square$

This completes the proof of Lemma 4.4.