4
$\begingroup$

The initial motivation for this question is a very practical problem: I need to find the absolute minimum of a function on a very large symmetric group $\Sigma_N$ (with $N$ 10000 or more). So if anyone knows some method to do this which is unrelated to the question, please tell.

What I thought to try is this: embed the group (which I will denote by $\Sigma$) into a compact Riemannian manifold $M$, extend the function to a smooth function on $M$ (my function is such that I am confident I can do it in a satisfactory way), find its minima using analytic methods, and then find group elements closest to these minima.

For this to work, the embedding $\Sigma\hookrightarrow M$ must be uniform in some sense. There are several versions, and in each case I want to find $M$ of dimension as small as possible.

Version "$1$": each faithful orthogonal representation $V$ of $\Sigma$ gives an embedding $\Sigma\hookrightarrow O(V)$ into the compact Lie group $O(V)$. Let $m_1(\Sigma)$ be the smallest among the dimensions of the $O(V)$;

Version "$1'$": given a representation as above, there might be subgroups $H$ of $O(V)$ which do not intersect the image of $\Sigma\hookrightarrow O(V)$. Then the composite $\Sigma\hookrightarrow O(V)\twoheadrightarrow O(V)/H$ will give an embedding of $\Sigma$ into a homogeneous space. Let $m_{1'}(\Sigma)$ be the smallest among the dimensions of the $O(V)/H$;

Version "$2$": consider embeddings $i:\Sigma\hookrightarrow M$ into compact Riemannian manifolds which have the property $$ d(i(\sigma\sigma'),i(\sigma'))=d(i(\sigma),i(1)) $$ for any $\sigma,\sigma'\in\Sigma$, where $d$ is distance in $M$, and furthermore there exists a group $G$ of isometries of $M$ which sends $i(\Sigma)$ to itself and the resulting action of $G$ on $\Sigma$ is transitive. Let $m_2(\Sigma)$ be the smallest among the dimensions of such $M$.

Version "$2'$": same as "$2$" except that we fix a generating set $\Gamma\subseteq\Sigma$ and only require the above distance equality in the case when $\sigma\in\Gamma$ (whereas $\sigma'$ is still arbitrary). Let $m_{2'}(\Sigma)$ be the corresponding smallest dimension.

I think it is easy to show that $m_1\geqslant m_{1'}\geqslant m_2\geqslant m_{2'}$. Of these, $m_1$ is easy to find as soon as one knows representations of $\Sigma$. The question is

Do any of the other modifications give any advantage, or are all these numbers actually equal? In case they are not, how could one find minimal embeddings with dimension smallest in all of the above senses?

Concerning $2'$ - it can be viewed as a task of isometrically embedding a Cayley graph of $\Sigma$; I found a related question on MO, isometric embeddings of Cayley graphs in "nice" spaces, but that focuses on infinite groups...

In case the question for general finite groups seems to you hopeless, - as I said I only need to deal with very large symmetric groups.

(Later edit)

In view of the comment by YCor below, it seems that I have to restrict the manifolds I mention in $2$ and $2'$.

Version "$3/2$": same as in "$2$" but $M$ restricted to be of constant positive curvature; thus it is either a(n exotic) sphere, or its quotient by a finite discontinuous group action. The corresponding minimal numbers thus sit between cases $1$ and $2$.

$\endgroup$
3
  • 1
    $\begingroup$ Every finite group embeds in the isometry group of a compact hyperbolic surface. Hence $m'_2(\Sigma)\le m_2(\Sigma)\le 2$ for every finite group $\Sigma$. But most likely this is useless for combinatorial optimization purposes. $\endgroup$
    – YCor
    Sep 13, 2014 at 14:30
  • $\begingroup$ @YCor Thank you, spectacular. The reference seems to be L.Greenberg, Maximal groups and signatures, Ann. Math. Studies 79 (1974) 207–226, and in fact if I am not mistaken it also can be even realized as the group of all isometries! (Except I do not quite see whether there always is a free orbit.) I have to think whether this can be used for my purposes. Maybe I should add positive curvature condition or some homogeneity or something like that... $\endgroup$ Sep 13, 2014 at 21:25
  • 1
    $\begingroup$ You get a free orbit as follows: for every $g\in G$, the set of fixed points of $G$ is a $\le 1$-dimensional submanifold, and so is the union over the finite group $G$. Thus any point outside this union is in a free orbit. $\endgroup$
    – YCor
    Sep 13, 2014 at 23:02

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.