# Are all free groups linear, i.e., admit a faithful representation to GL(n,K) for some field K ?

All free groups of finite or infinite countable rank are subgroups of the free non-abelian group $F_2$, which is linear. However, a free group of infinite uncountable rank will not be a subgroup of $F_2$. Is it linear, too ? This might easily follow from model theory, but I could not find a proof in the literature so far.

-
I believe that instead of using ultrafilters one can prove this by the compactness of first order logic by interpreting existence of a faithful representation as an infinite collection of first order statements in the theory of algebraically closed fields of characteristic 0 and then using compactness because any finite subset of these statements is satisfied by using the finitely generated case. Hopefully a model theorist will pipe in. – Benjamin Steinberg Mar 19 '13 at 18:08
Aren't ultraproducts and compactness of first logic are pretty much the same with different points of view? – YCor Mar 19 '13 at 18:49
Yes, but there are proofs of compactness of first order logic that don't explicitly go through ultraproducts such as the original one via Godel's completeness theorem. But it is true that the compactness of first order logic is equivalent to the existence of non-principal ultrafilters if I understand correctly. – Benjamin Steinberg Mar 19 '13 at 19:35

Free group of rank $c$ embeds in $Sl(2, F(t))$ where $F$ is a field of cardinality $c$.

Edit: Here is the detailed argument which, as Yves noted in his comment, proves a stronger result.

Theorem. Let $L$ be a field which is not an algebraic extension of a finite field and let $c$ be the cardinality of $L$. Then the free group of rank $c$ embeds in $SL(2, L)$.

Proof. Let $P$ be the prime field of $L$; then $L$ has the form $$P\subset E \subset L$$ where $E$ is a purely transcendenetal extension of $P$ and $L$ is an algebraic extension of $E$. Under our assumptions, $E$ and $L$ have the same cardinality, thus, it suffices to consider the case when $L=E$. Then $L$ is isomorphic to the functional field $L=F(t)$, where $F$ is a subfield of $L$. I will consider the case when $F$ is infinite since otherwise $L$ is countable and everything is clear (as the question reduces to the case of free groups of finite rank). Thus, $F$ has the same cardinality $c$ as $L$.

Let $T$ be the Bruhat-Tits building associated with $G=SL(2, L)$: This building is a simplicial tree with the path-metric $d$, where every edge has unit length. The group $G$ acts on $T$ by simplicial automorphisms with the kernel $\pm 1$. Detailed description and properties of $T$ and the action of $G$ are in Serre's book "Trees."

Let $v\in T$ be the vertex stabilized by $K=SL(2, O)$, where $O=F[t]$ is the ring of polynomial functions in $t$. Then the link $L_v$ of $v$ in $T$ is naturally identified with the projective line over $F$ (so that $K$ acts on $L_v$ by linear-fractional transformations). In particular, the group $K$ acts transitively on pairs of distinct points in $L_v$. Let $g\in G\setminus K$ be a diagonal matrix with the axis $\gamma\subset T$. Then $\gamma$ contains $v$ and $g$ acts on $\gamma$ as a translation by some even integer distance $\ge 2$. In view of transitivity of the action of $K$ on pairs noted above, there exists a subset $K_o\subset K$ of cardinality $c$ so that the elements $g_k=kgk^{-1}$, $k\in K_o$ have axes $k(\gamma)$ with the property that the 2-point sets $$k(\gamma) \cap L_v, k\in K_o,$$ are pairwise disjoint. (Call this property D.) Now, I claim that the elements $g_k, k\in K_o$, are free generators of a free subgroup of $G$. The proof is rather standard. For each $k\in K_o$ let $D_k\subset T$ denote the Dirichlet fundamental domain for the cyclic group $\langle g_k \rangle$: $$D_k=\{ x\in T: d(x, g_k^m(v))> d(x, v), \forall m\in {\mathbb Z} \setminus 0\}.$$ Since each $g_v$ translates $v$ at least by $2$, and in view of Property D above, the domains $D_k$ have pairwise disjoint complements. Thus, Tits' ping-pong argument (from his proof of the Tits alternative) applies in this setting and the subgroup of $G$ generated by the elements $g_k$ is indeed free with free generators $g_k$. qed.

Note that one has to exclude fields $L$ with are algebraic extensions of finite fields, since in this case the group $GL(n, L)$ is torsion (for every finite $n$) and, hence, cannot contain a free subgroup.

-
I guess you mean "any field $F$ of cardinality $c$". You don't need $t$, by the way, if you exclude $F$ algebraic over a finite field. – YCor Mar 19 '13 at 19:05
Yves: Yes, I meant "any" field. The proof I have in mind is the same ping-pong on trees that one uses in the p-adic case, so I need a functional field $F(t)$ (or any discrete valued field whose residue field has cardinality $c$). – Misha Mar 19 '13 at 20:01

Yes, it's a simple application of ultraproducts. Suppose that for fixed $d$, every finitely generated subgroup $H$ of a group $G$ has a faithful representation $j_H$ in $G_H=\text{GL}_d(K_H)$ for some field $K_H$. Then $G$ has a faithful representation into $\text{GL}(K)$, where $K$ is an ultraproduct of the $K_H$. Argue as follows: consider the lattice $I$ of all finitely generated subgroup. Consider an ultrafilter $\omega$ on $I$ containing, for every f.g. subgroup $H$, the set of subgroups containing $H$.

Then map $G$ into the ultraproduct $\ast^\omega(G_H)$ as follows: first extend $j_H$ to $G$ by defining $j_H(g)$ to be equal to 1 if $g\notin H$ (note that $j_H$ is a homomorphism only in restriction to $H$). Map $G$ into the product $\prod_H G_H$ by mapping $g$ to $(j_H(g))_H$. This is certainly not a homomorphism, but the composite map into the ultraproduct $\ast^\omega(G_H)$ is an injective homomorphism.

Now the ultraproduct $\ast^\omega(G_H)$ is canonically isomorphic to the group $\text{GL}_d(\ast^\omega K_H)$.

Finally this applies to free groups, but to many other groups, e.g. locally free groups and subgroups of ultraproducts of free groups, aka locally fully residually free groups. Note that if your group $G$ has a certain infinite cardinality, you can end up with a field of the same cardinality by restricting to the field generated by matrix entries of the image of your representation.

-
This argument shows that locally linear (of bounded degree) implies linear. In fact if I'm not mistaken, one can replace locally' here by fully residually': an easy modification of the argument establishes this. – shane.orourke Mar 20 '13 at 21:35
One clarification: locally fully residually free groups account for all subgroups of ultrapowers of free groups, however not all subgroups of the latter are fully residually free: in particular ${}^\ast F_2$ itself is not residually free. – shane.orourke Mar 20 '13 at 21:35
Thanks for the correction, I added "locally" before "fully residually free". – YCor Mar 21 '13 at 9:10
The fact that 'locally fully residually linear' implies linear was noticed by Tarski. – HJRW Mar 13 at 4:36
@HJRW: it it a typo? fully residually linear is the same as linear, and the same as residually finite. You mean in some given dimension? – YCor Mar 13 at 7:24

Linearity of uncountable free groups can be easily deduced from linearity of free groups of countable rank using basic set theory and algebra only, without using compactness theorem, or ultraproducts, or non-trivial arguments of Misha Kapovich. Here is the simple proof.

Proposition. Let $K$ be a field, $n\ge 2$, and $S$ a subset of ${GL}_n(K)$. Suppose all elements of all matrices from $S$ are distinct and algebraically independent in $K$. Then $S$ is a free subset of ${GL}_n(K)$.

Proof. Suppose not. Then there exist distinct matrices $A_1,\dots,A_m$ from $S$ and a non-trivial reduced group word $w(x_1,\dots,x_m)$ such that $w(A_1,\dots,A_m)=E$.

For any field $F$ and matrix $C=(c_{ij})$ in $GL_n(F)$, the inverse of $C$ can be found using a formula of the form $C^{-1}=(f_{ij}(c_{11},\dots,c_{nn})),$ where all $f_{ij}$ are certain rational functions over $\mathbb Z$ in $n^2$ variables, which do not depend on the choice of $F$ and $C$. Therefore, for any field $F$ and matrices $C_1,\dots,C_m$ in $GL_n(F)$, where $C_k=(c^k_{ij})$, we have $$w(C_1,\dots,C_m)= (g_{ij}(c^1_{11},\dots,c^1_{nn},\dots,c^m_{11},\dots,c^m_{nn})),$$ for some rational functions $g_{ij}$ over $\mathbb Z$ in $mn^2$ variables; these $g_{ij}$ do not depend on the choice of $F$ and $C_1,\dots,C_m$.

Let $A_k=(a^k_{ij})$. Since $w(A_1,\dots,A_m)=E$, the algebraic independence of all $a^k_{ij}$ implies the $g_{ij}\equiv 0$ for $i\ne j$, and $g_{ij}\equiv 1$ for $i=j$, for any field of characteristic $p$, where $p={\rm char}(K)$ (zero or prime). Hence $w(C_1,\dots,C_m)=E$ for any field $F$ of characteristic $p$ and matrices $C_1,\dots,C_m$ in $GL_n(F)$. Hence, for any field $F$ of characteristic $p$, in $GL_n(F)$ there is no free subgroup of rank $\ge m$. This contradicts to the known fact that free subgroups of countable rank embed into $GL_n(\mathbb Q)$ and $GL_n({\bf F}_q(t))$, for any prime $q$. $\square$

Corollary. If $\lvert K\rvert=\kappa>\aleph_0$ then the free group of rank $\kappa$ embeds into ${GL}_n(K)$.

Proof. Since $\kappa>\aleph_0$, any transcendence basis $B$ of $K$ is of power $\kappa$. Then there is a subset $S$ of $M_n(K)$ of power $\kappa$ such that all elements of matrices from $S$ belong to $B$ and are distinct. Since the elements of $B$ are algebraically independent, for $A\in S$ we have ${\rm det}(A)\ne 0$ and so $A\in {GL}_n(K)$. By Proposition, $S$ is free. $\square$

EDITED VERSION. In his answer Misha Kapovich proved, using his non-trivial geometric arguments, that for any field $K$ of uncountable power $\kappa$, the free group of rank $\kappa$ embeds into $SL_n(K)$, for any $n\ge 2$. In my answer I gave an elementary proof of a weaker result, with $GL$ instead of $SL$. However, my proof can be easily modified to the case of $SL$. Here is this modified proof.

For a non-singular square matrix $A$ denote by $\bar A$ the matrix obtained from $A$ by replacing any element $a$ in the first row of $A$ with $a/{\rm det}(A)$. Clearly, ${\rm det}(\bar A)=1$, and $\bar A=A$ if ${\rm det}(A)=1$.

Proposition. Let $K$ be a field, $n\ge 2$, and $S$ a subset of ${GL}_n(K)$. Suppose all elements of all matrices from $S$ are distinct and algebraically independent in $K$. Then ${\bar S} =\{{\bar A}: A\in S\}$ is a free subset of ${SL}_n(K)$.

Proof. Suppose not. Then there exist distinct matrices $A_1,\dots,A_m$ from $S$ such that $w({\bar A}_1,\dots,{\bar A}_m)=E$ for some non-trivial reduced group word $w(x_1,\dots,x_m)$.

As above, for any field $F$ and matrices $C_1,\dots,C_m$ in $GL_n(F)$, where $C_k=(c^k_{ij})$, we have $$w({\bar C}_1,\dots,{\bar C}_m)= (g_{ij}(c^1_{11},\dots,c^1_{nn},\dots,c^m_{11},\dots,c^m_{nn})),$$ for some rational functions $g_{ij}$ over $\mathbb Z$ in $mn^2$ variables; these $g_{ij}$ do not depend on the choice of $F$ and $C_1,\dots,C_m$.

Let $A_k=(a^k_{ij})$. Since $w({\bar A}_1,\dots,{\bar A}_m)=E$, the algebraic independence of all $a^k_{ij}$ implies the $g_{ij}\equiv 0$ for $i\ne j$, and $g_{ij}\equiv 1$ for $i=j$, for any field of characteristic $p$ , where $p={\rm char}(K)$ (zero or prime). Hence $w({\bar C}_1,\dots,{\bar C}_m)=E$ for any field $F$ of characteristic $p$ and matrices $C_1,\dots,C_m$ in $GL_n(F)$. In particular, $w(C_1,\dots, C_m)=E$ for any field $F$ of characteristic $p$ and matrices $C_1,\dots,C_m$ in $SL_n(F)$. Hence, for any field $F$ of characteristic $p$, in $SL_n(F)$ there is no free subgroup of rank $\ge m$. This contradicts to the fact that free subgroups of countable rank embed into $SL_n(\mathbb Q)$ and $SL_n({\bf F}_q(t))$, for any prime $q$. $\square$

Corollary. If $\lvert K\rvert=\kappa>\aleph_0$ then the free group of rank $\kappa$ embeds into ${SL}_n(K)$.

Proof. Since $\kappa>\aleph_0$, any transcendence basis $B$ of $K$ is of power $\kappa$. Then there is a subset $S$ of $M_n(K)$ of power $\kappa$ such that all elements of matrices from $S$ belong to $B$ and are distinct. Since the elements of $B$ are algebraically independent, for $A\in S$ we have ${\rm det}(A)\ne 0$ and so $A\in {GL}_n(K)$. Clearly, $\lvert \bar S\rvert=\kappa$. By Proposition, $\bar S$ is free in $SL_n(K)$. $\square$

-
You use a transcendence basis, whose existence makes use of the axiom of choice, which is not really different from using ultraproducts. However, in the field, say, of real numbers, you can construct uncountable (continuum) algebraically independent families without the use of the axiom of choice and this indeed provides free subgroups of uncountable rank in $GL_2(\mathbf{R})$. – YCor Mar 18 at 7:54
I wouldn't agree that using axiom of choice is not really different from using ultraproducts: ultraproduct is a special non-obvious construction, but axiom of choice is used everywhere as an obvious statement. On the other hand, for set-theoretists the following is a natural and typical problem : "Can be proven in ZF that uncountable free groups are linear?". Probably, the answer is "no". – owb Mar 18 at 17:56
First in ZF you should careful on what is the meaning of "uncountable", probably you should assume the countable (dependent?) axiom of choice. Second, you definitely have a proof in ZF that the free group over an arbitrary set $X$ is linear: consider the field $K$ of fractions over indeterminates $t_{x,i}$ indexed by $X\times\{1,2,3,4\}$ and consider for $x\in X$ the $2\times 2$ matrices $A_x$ with entries $t_{x,1},t_{x,2},t_{x,3},t_{x,4}$; then they freely generate a free subgroup of $GL_2(K)$. – YCor Mar 18 at 20:35
Yes, you are right, the question I formulated in the comment does not make sense, and the proof I suggested in the answer shows linearity of all free groups without axiom of choice. – owb Mar 18 at 20:56