When does a group have a geometric realization? I came across the following question in a set of lecture notes:
If $(G, *)$ is a group, when, in general, is it true that there exists $X \subset \mathbb{R}^n$ such that $G \cong \text{Sym}(X)$? Or, less formally, when does an abstract group have a geometric realization?
In this context, $\text{Sym}(X)$ is the group of isometries of $\mathbb{R}^n$ that permute $X$.
I'm quite confused about this. As far as I understand, the elements of the group act on the vertices by some group action. I suppose in order for $G$ to be identified with the group of symmetries, the action should be faithful, and transitive. But I know far too little about groups in order to be able to say anything more general or detailed about what we can deduce about the group structure. I also don't understand the importance of the $X$ being elements of $\mathbb{R}^n$, although this is a key part of the question.
So, summing up: what conditions does such a group need to satisfy, and how would the answer differ if we drop the condition that $X \subset \mathbb{R}^n$?
 A: Even the question about existence of $n$ and $X\subset {\mathbb R}^n$ such that $G< Sym(X)$ has negative answer. The reason is that $Sym(X)$ is a subgroup of the group of Euclidean isometries, which, in turn, is isomorphic to a subgroup of the general linear group $GL(n+1, {\mathbb R})$ consisting  of matrices of the block-diagonal form
$$
\left[\begin{array}{cc}
A& b\\
0 & 1\end{array}\right]
$$
where $A$ is a square $n\times n$ orthogonal matrix and $b$ is a column-vector. Here the corresponding Euclidean isometry is
$$
{\mathbf x}\mapsto A{\mathbf x} + b. 
$$
At the same time, there are many examples of groups (even finitely generated ones) which are not isomorphic to subgroups of $GL(N, {\mathbb R})$ for any $N$, see for instance here. My personal favorite is BS(2,3) from the answer given by user1729.
A: The group of isometries of $\mathbb{R}^n$ is a semidirect product $\mathbb{R}^n\rtimes O(\mathbb{R}^n)$, where $O(\mathbb{R}^n)$ are the orthogonal matrices and $\mathbb{R}^n$ acts by translation.  (If you haven't seen semidirect products, don't worry!  It's just a slightly-less-commutative generalization of the direct product.)  To see the semidirect decomposition, first note that, by the polarization identity, any isometry must preserve dot products.  Thus a isometry fixing the origin is orthogonal.  Now choose any specific isometry $g$; $g(0)$ is some point, so we can find a translation $t$ such that $(tg)(0)=0$.  Thus $tg\in O(\mathbb{R}^n)$ and the claim follows.
Now $O(\mathbb{R}^n)$ is itself the semidirect product $\{\pm1\}\rtimes\text{SO}(\mathbb{R}^n)$.  Thus your group must be a subgroup of $\mathbb{R}^n\rtimes\{\pm1\}\rtimes\text{SO}(\mathbb{R}^n)$.
If $n$ is fixed and small, then this imposes a rather strict restriction on the sort of groups that one can encounter.  A very accessible reference (for undergrads!) is Chapters 4 & 5 of Artin's Algebra, which essentially classify all discrete subgroups in 2 and 3 dimensions.  The upshot is that the discrete subgroups of $\text{SO}(\mathbb{R}^n)$ are cyclic groups, dihedral groups, and a few sporadic examples corresponding to the platonic solids; if we allow translations, then one obtains the classical crystallographic space groups as well.
As $n$ increases, more and more sporadic examples appear, so that one might hope that every group can be a geometric symmetry in high enough dimensions.  Certainly, if a group can be the symmetries of an $n$-dimensional set, then it is certainly the symmetries of an $m>n$-dimensional set, just by adding randomly chosen asymmetric points to cut off the extra dimensions.  I claim that if $n$ is allowed to grow without bound, then every finite group can be constructed via a similar process.  (Infinite groups that are symmetries of points in $\mathbb{R}^n$ are much harder to classify; my guess is that without further structure they are "undecidable" in the sense that no countable set of invariants can do the trick.  This is also why my answer is consistent with Moishe Kohan's: Moishe Kohan's counterexamples are all infinite.)
Before I begin, note that the isometries of $\mathbb{R}^n$ are generically $(n+1)$-faithful: if we know where $(n+1)$-many affinely-independent points $C$ are mapped, then we can recover the image of each element of $\mathbb{R}^n$ by measuring its distances to $C$ and applying triangulation.  (Conversely, as long as we preserve distances and angles, then the isometries can take any $(n+1)$-dimensional set to another; thus $\text{Isom}(\mathbb{R}^n)$ is almost sharply $(n+1)$-transitive.)
Suppose $G$ is a finite group.  Then $G$ acts on itself via left-multiplication; this gives an isomorphism to a permutation group.  We can consider those permutations as acting on basis vectors of $\mathbb{R}^{|G|}$ and extended by linearity; such actions are clearly isometries.  So we can construct $X\subseteq\mathbb{R}^{|G|}$ such that $G\leq\text{Sym}{(X)}$; can we ensure the reverse inequality?
If $G$ is the full symmetric group $S_k$, then the answer is clearly yes: let $X=\{\vec{0},\vec{e_1},\vec{e_2},\dots,\vec{e_k}\}\subseteq\mathbb{R}^k$.  Any symmetry of $X$ must fix $0$ (what else is distance $1$ away from all the other points?), and so acts as a permutation on the $k$-element remainder.  This gives a homomorphism $\text{Sym}(X)\to S_k$; since the isometries of $\mathbb{R}^k$ are $(k+1)$-faithful, said homomorphism is injective.  We can clearly make all transpositions (rotate the corresponding axes by $90^{\circ}$) to generate $S_k$, so the homomorphism is surjective too.
Likewise if $G=\{1\}$, then it is clear that $G$ is the symmetries of some set.  We now assume that $G>\{1\}$.
Suppose we can construct a permutation group $H>G$ as the symmetries of some finite set $Y\subseteq\mathbb{R}^n$ containing an affinely-independent set of size $n+1$ and such that all $H$ fixes some $y_0\in Y$.  Our first step is to show that we can add points to $Y$ without adding more symmetries.
Let $D(A)$ denote the set of distances between distinct points in $A$, i.e. $D(A)=\{|a-b|:a\neq b\in A\}$.  (For any point $x$, the sets $D(Y)$ and $D(Gx)$ are nonempty since $|Y|\geq n+1$ and $G>\{1\}$.)  Since $Y$ is finite, so is $D(Y)$; by choosing $x$ sufficiently far from $y_0$, we may ensure that the elements of $D(Gx)$ are sufficiently large, and thus ensure $D(Y)$ and $D(Gx)$ are disjoint.  But then any $r\in\text{Sym}(Y\cup Gx)$ must preserve the partition $Y\sqcup Gx$.  Thus there is an element $h\in H$ whose action on $Y$ is the same as $r$.  But $Y$ contains $(n+1)$-many affinely-independent points and the isometries of $\mathbb{R}^n$ are $(n+1)$-faithful.  So we must have $h=r$.
Thus $G\leq\text{Sym}(Y\sqcup Gx)\leq H$ for any $x$ so chosen.  So far, we only require $x$ far from $y_0$; in particular, we do not care about its "angle".  Now fix $h\in H\setminus G$: it is time to pin down that angle.  For each $g\in G$, since $h\neq g$, the vector space $\ker{(g-h)}\neq\mathbb{R}^n$.  Thus $\bigcup_{g\in G}{\ker{(g-h)}}\neq\mathbb{R}^n$ too.  So there is some $x$ far from $y_0$ that does not lie in that union.  Choose such an $x$; then we never have $hx=gx$ for any $g\in G$.  Equivalently, $hx\notin Gx$, so that $h\notin\text{Sym}(Y\sqcup Gx)$.
Thus we can choose $x$ so that $\text{Sym}(Y\sqcup Gx)<H$.  If $G<\text{Sym}(Y\sqcup Gx)$, then we can replace $H$ with $Y\sqcup Gx$ and induct on $|H|$, so eventually $G=\text{Sym}(Y\sqcup Gx)$ as desired.
