ELECTRONIC RESEARCH ANNOUNCEMENTS OF THE AMERICAN MATHEMATICAL SOCIETY Volume 10, Pages 21–28 (March 30, 2004) S 1079-6762(04)00126-X

ON APPROXIMATION OF LOCALLY COMPACT GROUPS BY FINITE ALGEBRAIC SYSTEMS

L. YU. GLEBSKY AND E. I. GORDON

(Communicated by Efim Zelmanov)

Abstract. We discuss the approximability of locally compact groups by finite semigroups and finite quasigroups (latin squares). We show that if a locally compact group G is approximable by finite semigroups, then it is approximable by finite groups, and thus many important groups are not approximable by finite semigroups. This result implies, in particular, the impossibility to simulate the field of reals in computers by finite associative rings. We show that a locally compact group is approximable by finite quasigroups iff it is unimodular.

1. Introduction

In this paper we discuss the approximability of locally compact groups by finite algebraic systems with given properties, with respect to the following definition of approximability.

Let G be a locally compact group. We will denote by · the multiplication in G and use the usual notation

XY = {x · y | x ∈ X, y ∈ Y },
X^{−1} = {x^{−1} | x ∈ X},
gX = {g · x | x ∈ X}

for X, Y ⊂ G, g ∈ G.

Definition 1.1. Let C ⊂ G be a compact set, U a relatively compact neighborhood of the unity in G, and (H, ⊙) a finite universal algebra with one binary operation.

(1) We say that a set M ⊂ G is an U-grid of C iff C ⊂ MU.

(2) A map j : H → G is called a (C, U)-homomorphism if

∀x, y ∈ H ((j(x), j(y), j(x) · j(y) ∈ C) ⇒ (j(x ⊙ y) ∈ j(x)j(y)U))

(3) We say that the pair ⟨H, j⟩ is a (C, U)-approximation of G if j(H) is an U-grid of C and j : H → G is a (C, U)-homomorphism.

Received by the editors June 16, 2003. 2000 Mathematics Subject Classification. Primary 26E35, 03H05; Secondary 28E05, 42A38. Key words and phrases. Approximation, group, quasigroup. The first author was supported in part by CONACyT-NSF Grant #E120.0546 y PROMEP,

PTC-62; the second author was supported in part by NSF Grant DMS-9970009.

\begin{matrix}c \\ ◯ \end{matrix}2004 American Mathematical Society

(4) Let K be a class of finite algebras. We say that G is approximable by the systems of the class K if for any compact C ⊂ G and for any neighborhood U of the unity there exists a (C, U)-approximation ⟨H, j⟩ of G such that H ∈ K and j is an injection.

Remark 1.2. Since in item (2) the elements j(x ⊙ y) and j(x) · j(y) are U-close in the left uniformity on G, it may seem that the definition of approximability of G by systems of K depends on which of two uniformities we consider. However, this is not so. Indeed it is clear from the definition that we deal only with the restrictions of the uniformities on compacts. But it is well known that the restrictions of the left uniformity and of the right uniformity on any compact are equivalent.

Remark 1.3. It is easy to see that a similar definition can be formulated for any topological universal algebra, and it is not necessary to assume that approximated algebras are finite. For example, the approximations of discrete groups by amenable groups have been introduced in [2].

This definition of approximability by finite groups was introduced by the second author in [6], where the approximability of locally compact abelian groups by finite abelian groups was investigated. The cases of discrete groups and locally compact nilpotent groups were considered in [15]. The possibility to approximate a locally compact group G by finite groups implies some important corollaries. In [1] some new finite dimensional approximations of pseudodifferential operators in L_{2}(G) for an abelian group G were constructed using approximations of G by finite abelian groups. Approximations of discrete groups have some interesting applications in the ergodic theory of group actions [15], [2] and in symbolic dynamics [8]. In fact, approximations of discrete algebraic system (finite embeddability) were considered by T. Evans [3].

On the other hand, many results about the nonapproximabilty of locally compact groups by finite groups were obtained. For example, a discrete finitely presented group G is approximable by finite groups in the sense of Definition 1.1 iff G is residually finite. So, a group with undecidable word problem is not approximable by finite ones; see [4].

It was proved in [7] that all approximable locally compact groups are unimodular (the left and right Haar measures coincide). This condition is not sufficient—we have already mentioned that there exist nonapproximable discrete groups. It was proved in [2] that the simple Lie groups are not approximable by finite groups as topological groups.

The nonapproximability of some important groups, such as the group SO(3), by finite groups make it of interest to investigate more general classes of finite universal algebras with one binary operation that approximate some locally compact groups nonapproximable by finite groups.

The most important and well investigated extensions of the class of finite groups are the classes of finite semigroups (see, for example, [13]) and the class of finite quasigroups, which are the same as latin squares (see, for example, [12] and [14]).

Definition 1.4. (1) We say that an algebra (A, ∘) is a right quasigroup (left quasigroup) iff for every a, b ∈ A the equation a ∘ x = b (x ∘ a = b) has the unique solution x = /(b, a) (x = \(b, a)).

(2) An algebra (A, ∘) is a quasigroup iff it is a right quasigroup and left quasigroup. A quasigroup A with a unity (an element e ∈ A such that that ∀ a ∈ A, a ∘ e = e ∘ a = a) is called a loop.

(3) We say that an algebra (A, ∘) is a semigroup if the operation ∘ satisfies the law of associativity.

2. Approximation of locally compact groups by finite semigroups

The following theorem holds.

Theorem 2.1. A locally compact group is approximable by finite semigroups iff it is approximable by finite groups.

The proof of Theorem 2.1 is based on some results about the structure of finite semigroups from [13]. We use also the language of nonstandard analysis (cf. for example [11]) that allows us to simplify the proofs essentially.

Theorem 2.1 has an interesting corollary about approximability of the field R by finite rings.

Theorem 2.2. The field R is not approximable by finite associative rings.

Proof. Let us sketch the proof of this theorem.

Consider the matrix group

G = \{( \begin{matrix}a & b \\ 0 & 1 \end{matrix} ) | a ≠ 0, b ∈ R\}.

It is well known that this group is nonunimodular and thus by the above-mentioned result from [7] is not approximable by finite groups. By Theorem 2.1 G is not approximable by finite semigroups. On the other hand, if we could approximate R by finite associative rings, then G would be approximable by semigroups of matrices of the same type with the elements of finite rings that approximate R, a contradiction. □

Theorem 2.2 has the following interpretation.

Consider some examples of approximation of the field R in the signature σ = ⟨+, ·⟩. Since any compact C ⊂ R is contained in the interval [−a, a] for an appropriate a and the sets U_{ε} = {x ∈ R | |x| < ε}, ε > 0 form a base of the neighborhoods of zero in R, it is enough to consider only the ([−a, a], U_{ε})-approximations of R. We will call these approximations the (a, ε)-approximations.

Example 1. Recall that the normal (computer) form of a real α is its representation:

(1)  α = ±10^{p} · 0.a_{1}a_{2} …,

where p ∈ Z, and a_{1}a_{2} … is a finite or infinite sequence of decimal digits 0 ≤ a_{n} ≤ 9, and a_{1} ≠ 0. The integer p is called the exponent of α, and a_{1}a_{2} …, its mantissa.

Fix two natural numbers P > Q and consider the finite set A_{P Q} of reals in the form (1) such that the exponent p of α satisfies the inequality |p| ≤ P and its mantissa contains no more than Q decimal digits. Define two binary operations ⊕ and ⊙ on A_{P Q}. Let α, β ∈ A_{P Q} and the normal form of α × β, where × is either + or ·, is

(2)  α × β = ±10^{r} · 0.c_{1}c_{2} ….

Notice that the mantissa of α × β may contain more than Q digits. Now

α ⊗ β = \{ \begin{matrix}±10^{r} · 0.c_{1}c_{2} … c_{Q} & if |r| ≤ P, \\ ±10^{P} · 0. \underbrace{99 … 9}_{Q digits} & if r > P, \\ 0 & if r < −P. \end{matrix}

In the case that the mantissa of α × β contains fewer than Q digits we complete it to a Q-digit mantissa by zeros.

We will denote by A_{P Q} the universal algebra ⟨A_{P Q}, σ⟩ such that the interpretations of the functional symbols + and · are the functions ⊕ and ⊙, respectively.

It is easy to see that for any positive a and ε there exist natural numbers P and Q such that the universal algebra A_{P Q} is an (a, ε)-approximation of R.

The described systems A_{P Q} are implemented in working computers. What properties of addition and multiplication of reals hold for ⊕ and ⊙?

It is easy to see that the operations ⊕ and ⊙ are commutative, ξ ⊕ (−ξ) = 0 and ξ + 0 = ξ for any ξ ∈ A_{P Q}.

Let α = β = 0.60 … 06 and γ = 0.60 … 5 (with Q digits after the decimal point). Then α ⊕ β = α ⊕ γ, so the cancellation law fails for ⊕, and thus the law of associativity fails for ⊕.

It is easy to construct examples that show that the laws of associativity for ⊙ and distributivity in A_{P Q} fail also.

Example 2. Fix a natural number M and a positive ε. Put A′_{Mε} = {kε | k = −M … M}. Let N = 2M + 1. For any n ∈ Z we will denote by n(mod N) the element of the set {−M, …, M}, congruent to n modulo N. The operations ⊕ and ⊙ on A′_{M,ε} are defined as follows:

(3)  kε ⊕ mε = (k + m)(mod N)ε,
(4)  kε ⊙ mε = [kmε](mod N)ε.

We will denote by A′_{M,ε} the universal algebra in the signature σ with the underlying set A′_{M,ε} and the interpretation of the functional symbols defined by formulas (3) and (4).

It is easy to see that A′_{Mε} is an (Mε, ε)-approximation of R.

It is obvious that A′_{M,ε} is an abelian group with respect to ⊕ (see (3)). However, one can easily construct examples which show that for any big enough M and small enough ε the multiplication ⊙ satisfies neither the law of associativity, nor the law of distributivity.

This example shows that it is possible to implement in computers a numerical system that simulate reals, which is an abelian group with respect to addition, while by Theorem 2.2 it is impossible to implement such system that would be an associative ring (even noncommutative).

It is an interesting question whether it is possible to approximate R by any finite nonassociative rings.

3. Approximation of locally compact groups by finite quasigroups

In this section we discuss the following theorem.

Theorem 3.1. A locally compact group G is unimodular iff it is approximable by finite quasigroups.

As far as we know, no characterization of unimodularity in algebraic and topological terms has been known up to now.

The sufficiency is more or less easy. Suppose that G is approximable by left (right) quasigroups.

We will construct a left (right) invariant mean on G using left (right) quasigroups that approximate G.

Let H be the family of all pairs ⟨C, U⟩ such that C ⊆ G is a compact set and U is a relatively compact neighborhood of the unity on G. Let ≤ be the partial order on H such that

⟨C_{1}, U_{1}⟩ ≤ ⟨C_{2}, U_{2}⟩ ⟺ C_{1} ⊇ C_{2} ∧ U_{1} ⊆ U_{2}.

Given a pair ⟨C, U⟩ ∈ H let H(C, U) = {⟨C′, U′⟩ | ⟨(C′, U′⟩ ≤ ⟨C, U⟩}. It is easy to see that the family M = {H(C, U) | ⟨C, U⟩ ∈ H} of subsets of H has the finite intersection property. Thus there exists an ultrafilter F on H such that F ⊇ M. Fix an arbitrary such ultrafilter F.

Recall that if α : H → X is an arbitrary map, X is a Hausdorf space and a ∈ X, then lim_{F} α(C, U) = a if {⟨C, U⟩ |α(C, U) ∈ Y } ∈ F for any neighborhood Y ∋ a. It is known that if α(H) is relatively compact, then the lim_{F} α(C, U) exists.

For each ⟨C, U⟩ fix a finite algebra H_{C,U} that is a (C, U)-approximation of G. Without loss of generality we may assume that H_{C,U} ⊂ G as a set. Fix also a compact set V ⊆ G with nonempty interior.

As usual, let C_{0}(G) be the space of all continuous functions with compact support on G. For an arbitrary f ∈ C_{0}(G) put

(5)  Λ(f) = lim_{F} |H_{C,U} ∩ V |^{−1} ∑_{h∈H_{C,U}} f(h)

if this limit exists.

Theorem 3.2. If for any ⟨C, U⟩ ∈ H the algebra H_{C,U} is a left (right) quasigroup, then the limit on the right hand side of formula (5) exists for all f ∈ C_{0}(G). In this case the functional Λ : C_{0}(G) → R is a positive nonzero left (right) invariant functional on C_{0}(G)

Obviously this theorem implies the sufficiency of condition of Theorem 3.1. The following theorem is also true.

Theorem 3.3. Any locally compact group G is approximable by finite l-quasigroups (r-quasigroups).

Theorems 3.2 and 3.3 together give a proof of the existence of Haar measure. This proof is close by ideas to the proof of the existence of Haar measure due to von Neumann, which is based on equidistributed sets [10]. For example, in the proof of the existence of equidistributed sets as well as in the proof of Theorem 3.3, the Marriage Lemma is used.

The proof of necessity in Theorem 3.1 involves more complicated combinatorics. For the case of discrete groups it follows immediately from the fact that any

n × n latin subsquare with k distinct elements can be completed to an r × r latin square, where r = max{2n, k}.

Recall that n × n-table is a latin subsquare iff all elements in each row and in each column are distinct. An n×n-latin subsquare with n different elements is said to be a latin square. It is easy to see that the operation table of a finite quasigroup is a latin square.

Theorem 3.1 is now a corollary of the following

Proposition 3.4. Any nondiscrete locally compact unimodular group G is approximable by finite quasigroups.

The proof of this proposition that will be discussed in the paper is rather complicated. We outline the main ideas of this proof here only for the case of a compact group G. The case of locally compact groups requires some technical modifications. Nontrivial combinatorial arguments about latin squares are involved in the proof. These arguments are based on a generalization of a result by Hilton [9] and discussed in [5].

We assume in this section that G is a nondiscrete compact group. All subsets of G we deal with are assumed to be measurable with respect to the Haar measure ν that is assumed to be normalized, ν(G) = 1. Recall that any compact group is unimodular and thus ν is left and right invariant. Let U be a neighborhood of the unit in G, and P a finite partition of G. We say that P is U-fine if ∀P ∈ P ∃g ∈ G (P ⊆ gU), and P is equisize if all sets in P have the same Haar measure.

Theorem 3.5. There exists a U-fine equisize partition for any neighborhood of the unit U ⊆ G.

Let P = {P_{1}, …, P_{n}} be a partition that satisfies the assumptions of this theorem for some U. Consider the three-index matrix w = ⟨w_{ijk} | 1 ≤ i, j, k ≤ n⟩, where

w_{ijk} = ∫∫_{G×G} χ_{i}(xy^{−1})χ_{j}(y)χ_{k}(x)dν(x)dν(y);

χ_{m}(x) = χ_{P_{m}}(x) is the characteristic function of a set P_{m}, m ≤ n.

Obviously w_{ijk} ≥ 0. Let S = supp w = {⟨i, j, k⟩ | w_{ijk} > 0}.

Lemma 3.6. The three-index matrix w_{ijk} has the following properties: (1) ∑_{i} w_{ijk} = ∑_{j} w_{ijk} = ∑_{k} w_{ijk} = \frac{1}{n^{2}} ;

(2) S ⊆ {⟨i, j, k⟩ | ν(P_{i} · P_{j} ∩ P_{k}) > 0}.

To motivate the following consideration we use an analogy with two-index matrices. Recall that an n × n matrix B = ∥p_{ij}∥ is bistochastic if p_{ij} ≥ 0 and ∑_{i=1}^{n} p_{ij} = ∑_{j=1}^{n} p_{ij} = 1. According to a well-known G. Birkhoff’s theorem (cf., for example, [14]) in this case B is a convex hull of permutations—the matrices that consist of zeros and ones and contain a unique one in each row and in each column. Then there exists a permutation T such that supp T ⊆ supp B. Assume for a moment that the similar fact holds for the three-indexed matrices. We say that a three-index matrix is three-stochastic if it is nonnegative and the sum of elements in each line is equal to one. We call a line any set L of triples of elements of {1, …, n} such that in all triples in L two indexes are fixed and the third runs over {1, …, n}. Notice that if w_{ijk} satisfies Lemma 3.6, then n^{2}w_{ijk} is three-stochastic. So we assume that the following statement is true.

(A) If w_{ijk} satisfies Lemma 3.6, then there exists a matrix δ_{ijk} that consists of zeros and ones, contains a unique one in each line and such that supp δ_{ijk} ⊆ supp w_{ijk}.

By the properties of δ_{ijk} it is easy to see that supp δ_{ijk} is the graph of the operation ∘ on {1, …, n} such that i ∘ j = k iff γ_{ijk} = 1. Denote by Q the algebra {1, …, n} with the operation ∘. Since for any i and k there exists a unique j such that γ_{ijk} = 1, and for any j and k there exists a unique i such that γ_{ijk} = 1, we have that the left and right cancellation laws hold in Q, and thus Q is a quasigroup.

Fix an arbitrary injection α : Q → G such that for any i ≤ n, α(i) ∈ P_{i}. Notice that if i ∘ j = k then ⟨i, j, k⟩ ∈ supp γ_{ijk} ⊆ supp w_{ijk} and thus P_{i} · P_{j} ∩ P_{k} ≠ ∅ by Lemma 3.6 (2).

Thus, we have proved, under assumption (A), the following

Lemma 3.7. For any neighborhood of the unit U of a compact group G and for any U-fine equisize partition P of G there exist a finite quasigroup Q and an injection α : Q → G such that

(1) ∀P ∈ P∃q ∈ Q (α(q) ∈ P);

(2) ∀q_{1}, q_{2} ∈ Q (α(q_{1}) ∈ P_{1} ∈ P ∧ α(q_{2}) ∈ P_{2} ∈ P ∧ α(q_{1} ∘ q_{2}) ∈ P_{3} ∈ P ⟹

P_{1} · P_{2} ∩ P_{3} ≠ ∅).

It is easy to see that Proposition 3.4 follows from Lemma 3.7.

Unfortunately the statement (A) is not true in general (see, for example, [5]), and a proof of Lemma 3.7 follows from a weaker analogue of statement (A) due to Hilton [9] (Theorem 3.8).

Let Q be a quasigroup and σ an equivalence relation on Q which we will identify with the partition of Q by the equivalence classes. Then σ = {Q_{1}, …, Q_{n}}. Denote by Q/σ the subset of {1, …, n}^{3} such that ⟨ijk⟩ ∈ Q/σ iff there exist q ∈ Q_{i} and q′ ∈ Q_{j} with q ∘ q′ ∈ Q_{k}. Notice that if σ is a congruence relation on Q (i.e. it preserves the operation ∘), then the introduced set is exactly the graph of the operation in the quotient quasigroup Q by σ, and so we will call the set Q/σ a generalized quotient quasigroup (gqq).

Theorem 3.8. Let a nonnegative three-index matrix u = ⟨u_{ijk} | 1 ≤ i, j, k ≤ n⟩ satisfy the following condition

∑_{i} u_{ijk} = ∑_{j} u_{ijk} = ∑_{k} u_{ijk} = l

for some positive l. Then there exist a finite quasigroup Q and its partition σ = {Q_{1}, …, Q_{n}} such that the gqq Q/σ ⊆ supp u.

The case of an arbitrary locally compact group G requires some generalization of Hilton’s result, which is contained in [5].

References

[1] S. Albeverio, E. Gordon, A. Khrennikov, Finite dimensional approximations of operators in the spaces of functions on locally compact abelian groups, Acta Applicandae Mathematicae 64(1), 33–73, October 2000. MR 2002f:47030

[2] M. A. Alekseev, L. Yu. Glebskii, E. I. Gordon, On approximations of groups, group actions and Hopf algebras, Representation Theory, Dynamical Systems, Combinatorial and Algebraic Methods. III, A. M. Vershik editor, Russian Academy of Sciences, St. Petersburg Branch of Steklov Mathematical Institute, Zapiski Nauchn. Seminarov POMI 256 (1999), 224–262; English transl., Journal of Mathematical Sciences, 107, No. 5 (2001), 4305–4332. MR 2000j:20050

[3] T. Evans, Some connection between residual finiteness, finite embeddability and the word problem, J. Lond. Math. Soc. (2), 1 (1969), 399–403. MR 40:2589

[4] T. Evans, Word problems, Bull. American Math. Soc., 84, No. 5 (1978), 789–802. MR 58:16240 [5] L. Yu. Glebsky, Carlos J. Rubio, Latin squares, partial latin squares and its generalized

quotients, preprint math.CO/0303356, http://xxx.lanl.gov/, submitted to Combinatoric and Graphs.

[6] E. Gordon, Nonstandard Methods in Commutative Harmonic Analysis, AMS, Providence, Rhode Island, 1997. MR 98f:03056

[7] E. I. Gordon, O. A. Rezvova, On hyperfinite approximations of the field R, Reuniting the Antipodes—Constructive and Nonstandard Views of the Continuum, Proceedings of the Symposium in San Servolo/Venice, Italy, May 17–20, 2000. B. Ulrich, H. Ossvald and P. Schuster, editors. Synthése Library, volume 306, Kluwer Academic Publishers, Dordrecht, 2001. MR 2003c:03128

[8] M. Gromov, Endomorphisms of symbolic algebraic varieties, J. Eur. Math. Soc. 1 (1999), 109–197. MR 2000f:14003

[9] A. J. W. Hilton, Outlines of latin squares, Ann. Discrete Math. 34 (1987), 225–242. MR 89a:05037

[10] J. von Neumann, Invariant Measures, AMS, Providence, RI, 1998. MR 2002b:28012

[11] Nonstandard Analysis for the Working Mathematicians, P. A. Loeb and M. P. H. Wolff, editors. Mathematics and Applications, volume 510, Kluwer Academic Publishers, Dordrecht/Boston/London, 2000. MR 2001e:03006

[12] Quasigroups and Loops. Theory and Applications, O. Chein, H. O. Pfulgfelder and J. D. H. Smith, editors. Sigma Series in Pure Mathematica, volume 8, Heldermann Verlag, Berlin, 1990. MR 93g:20133

[13] J. Rhodes, B. Tilson, Theorems on local structure of finite semigroups, Algebraic theory of machines, languages and semigroups, M. A. Arbib, ed., Acad. Press, New York & London, 1968. MR 38:1198

[14] H. J. Ryser, Combinatorial Mathematics, The Carus Mathematical Monographs, 15, The Mathematical Association of America, 1963. MR 27:51

[15] A. M. Vershik, E. I. Gordon, Groups locally embedded into the class of finite groups, Algebra i Analiz 9 (1997), no. 1, 71–97; English transl., St. Petersburg Math. J. 9 (1998), no. 1, 49–67. MR 98f:20025

IICO-UASLP, Av. Karakorum 1470, Lomas 4ta Session, SanLuis Potosi SLP 78210, Mexico

E-mail address: glebsky@cactus.iico.uaslp.mx

Department of Mathematics and Computer Science, Eastern Illinois University, 600 Lincoln Avenue, Charleston, IL 61920-3099

E-mail address: cfyig@eiu.edu