User max - MathOverflow

Answer by Max for Projective Plane of Order 12

2010-09-14T16:12:31Z

I am actually not aware of many results on planes of order 12 in the vein of what Lam et. al. did (I list the few I know of below). There seems to be a plethora of papers proving restrictions on the collineation group of a hypothetical such plane, but I am not aware of how any of these could be used to settle the existence problem.

Moreover, I am quite skeptical that disproving the existence of planes of order 12 by a computer search would help for the general theory much. Though it certainly would be nice to know, and if one actually found a plane of order 12, that would be quite exciting; but it's hard to gain deep insights from these combinatorial brute force searches.

Extending the approach by Lam et. al. to planes of order 12 is in principle possible. But probably still not feasible with today's computers, as the search space is a lot bigger than for order 10. Anyway, here are some reasons why I think that, and at the same time a sketch of things that would have to be done. But my personal belief is that one will need some substantially new ideas to make progress on this. Then again, only by actually trying to do it can one be sure... :)

From here on, I'll assume you are familiar with Lam's "The Search for a Finite Projective Plane of Order 10" and the notation used within.

A crucial point was the reduction of the (non-)existence to the value of certain weight enumerator coefficients $w_0$ to $w_{n^2+n+1}$ (a good exposition can be found in "On the existence of a projective plane of order 10" by MacWilliams, Sloane and Thompson). But the real breakthrough was when Assmus and Mattson proved that one only needs to know $w_{12},w_{15},w_{16}$ to determine all others. I'll refer to these as essential weight enumerator coefficients.

Some steps towards this for order 12 have been executed in "Ternary and binary codes for a plane of order $12$" by Hall and Wilkinson. Yet many nice properties and theorems will be hard to recover for order 12. E.g. for orders of the form $8m+2$, one knows the $\mathbb{F}_2$-rank of the incidence matrix. Not so for order 12, where working with a ternary code is in some ways more "natural." In particular, the $\mathbb{F}_3$-rank of the incidence matrix is known, but, alas, working with a ternary code means losing the natural identification of codewords with point sets, so tons of new machinery would be needed to exploit the ternary code. Thus I'll focus on the binary code case here.

Anyway, let's assume we reduced the number of essential weight enumerator coefficients as much as we can (Hall and Wilkinson pushed it down to 16; remember, for $n=10$ we had only 3). We must compute the essential coefficients.

According to Lam, for $n=10$ and the case $w_{12}$, they estimated, using a Monte-Carlo method (before doing it) that $4\times 10^{11}$ configuration had to be checked. I don't have a good means to compute a good estimate for $n=12$, but for that there are 16 coefficients to determine, and I'd hazard to guess that some of them are much, much harder than the three cases for $n=10$ put together. Several orders of magnitude. However, this is just gut feeling.

So let's assume we had somehow managed to overcome this and had computed all essential weight enumerator coefficients. We then would have the full weight enumerator at hand (and no projective plane arose as a byproduct of our search). Now, the hard part starts (corresponding roughly to the second half of Lam's paper), the one that took them 2 years for $n=10$: We have to somehow derive a contradiction (or construct a plane). A lot of ground work needs to be done (extending stuff from $n=10$), before one can even start writing code...

Ah well. To anybody who wants to try out this strategy on $n=12$, I would recommend to first try reproducing the $n=10$ result -- with modern computers it should be possible to do this much, much quicker than it took Lam et. al. originally (this verification might already interest some people on its own). Actually, at the very start, try it with even smaller examples ($n=6,8$), then go up.

Answer by Max for My output of a group and inverse-closed subset in MAGMA is no longer inverse-closed when entered as input to GAP.

2013-02-12T23:05:23Z

(I meant to post this as a comment, but that doesn't seem to allow me to format code, so I'll post it as an answer instead)

Note that GAP also has the database of small groups built in, so you can also directly access the group in question and obtain a presentation for it:

gap> G:=SmallGroup(20,3);
<pc group of size 20 with 3 generators>
gap> F:=Image(IsomorphismFpGroup(G));
<fp group of size 20 on the generators [ F1, F2, F3 ]>
gap> RelatorsOfFpGroup(F);
[ F1^2*F2^-1, F2^-1*F1^-1*F2*F1, F3^-1*F1^-1*F3*F1*F3^-1, F2^2, F3^-1*F2^-1*F3*F2*F3^-3, F3^5 ]

Answer by Max for Finite groups admitting free isometric actions on round spheres

2012-05-09T15:27:21Z

EDIT 2: My original and the following revised answer were nonsense; I'll just leave this edited, and very incomplete "answer" dealing with even $n$, just in case it helps somebody avoid to repeat my mistakes :(.

The isometry group of the standard sphere $S^n$ is the orthogonal group $G:=O_{n+1}(\mathbb{R})$. Each element of $G$ is either a rotation, a reflection or the product of a rotation and a reflection. Every reflection fixes a hyperplane, hence also a point on the sphere. Thus a group $H$ acting freely and isometrically cannot contain reflections.

Now if $n$ is even (and hence $n+1$ odd), then every rotation of $G$ fixes a point. (Its eigenvalues have absolute value 1, and it must have at least one real eigenvalue, hence 1 or -1. But the complex eigenvalues come in pairs $\lambda,\overline\lambda$. Since rotations have determinant 1, we conclude that the eigenvalue $-1$ must occur an even time. Hence there is an eigenvector with eigenvalue 1.)

This leaves products of a reflection and a rotation (such as the antipodal map $x\mapsto -x$). One can then show that at most one such non-trivial element can be contained in $H$ (as otherwise, we would get reflections or rotations inside $H$), and in fact, only the antipodal map can occur as non-trivial element of $H$.

Thus only the trivial group and the cyclic group of order 2 can act freely and isometrically on $S^n$ for even $n$.

On the other hand, for odd $n$, more possibilities arise, e.g. any cyclic group admits a free isometric action on $S^n$ for odd $n$.

Answer by Max for Cosets representatives of congruence subgroups

2011-12-19T15:17:33Z

Here is another attempt, this time hopefully with a correct answer. First off, the problem gets worse for e.g. N=24, where the index is 48, yet we only get 44 coset representatives.

For $N=12$, representatives for the two missing cosets are for example $(1,9)=(5,9)=(7,3)=(11,3)$ and $(1,8)=(5,4)=(7,8)=(11,4)$ (here with equality I mean that the pairs represent the same coset).

To find these, I first claim that there is a natural bijection beween $\Gamma/\Gamma_0(N)$ and the "projective line" $P^1(R)$, where $R:=\mathbb{Z}/N\mathbb{Z}$, which consists of the "1-dimensional subspaces of $R^2$". That is, subsets of $R^2$ of the form $(c,d) \cdot R^\times$ and of size $\lvert R^\times \rvert$. Indeed, it is easy to very that $\Gamma$ acts transitively (say, from the right) on $P^1(R)$, and the stabilizer of $(0,1)\cdot R^\times$ then equals $\Gamma_0(N)$. The claim follows.

Thus we just have to find representatives for the orbits $A:=(c,d)\cdot R^\times$ of $P^1(R)$. If $d$ is a unit, we can divide by $d$ and thus we certainly can choose the pairs $(c,1)$ as one type of coset representative. It remains to consider the pairs $(c,d)$ where $d$ is not a unit. Note that we may choose $1\leq c,d\leq N$ such that $gcd(c,d)=1$ (for either the gcd is invertible mod $N$, and so we can divide it out; or else it is a non-unit $x$, but then $x\cdot R^\times$ is strictly smaller than $R^\times$, and so $A$ is not an element of $P^1(R)$).

Looking at the formula you give (and attribute to Shimura), this is exactly what happens there: The element $d$ is either 1, or else $gcd(d,N)\neq 1$, in which case $d$ corresponds to a non-unit of $R$; one can in fact show that the $R^\times$-orbits (action by multiplication) on $R$ have the divisors of $N$ as representants.

However, the formula you describe is then to restrictive on what values for $c$ are used. Unfortunately, I cannot tell you a good closed formula as alternative right now, but with the above description, it is still relatively easy to compute representatives for all orbits: Let $d$ vary as described, but then do not only consider $c\leq N/d$, but rather study the orbits of $Stab_{R^\times}(d)$ on $R$ to find all possible values for $c$. In our example $N=12$, for example, the orbits of $R^\times$ on $R$ are $[ [ 0 ], [ 1, 5, 7, 11 ], [ 2, 10 ], [ 3, 9 ], [ 4, 8 ], [ 6 ] ]$. The stabilizer of e.g. $d=3$ is the subgroup of $R^\times$ containing $1$ and $5$. Its orbits on $R$ are $[ [ 0 ], [ 1, 5 ], [ 2, 10 ], [ 3 ], [ 4, 8 ], [ 6 ], [ 7, 11 ], [ 9 ] ]$. Hence we get the pairs $(1,3), (2,3), (4,3), (7,3)$ as the desired coset representatives with $d=3$. (The other values for $c$ are not allowed, as then $gcd(c,d)\neq 1$, which means that $(c,d)\cdot R^\times$ will be too small).

Answer by Max for algorithms for comparing two simplicial complexes

2011-12-14T16:38:21Z

A special case of this problem is the graph isomorphism problem. Interestingly, for this it is unknown whether it is solvable in polynomial time (relative to the number of vertices, so $n$ in your case), and also unknown whether or not it is $NP$-complete. As far as I know, Luks' algorithm is still state of the art (though I might be wrong), and that has runtime $O(2^{\sqrt{n \log(n)}})$.

Since this is a special case of your problem, its general worst case runtime will be unknown, too. Of course in this special case, one has only subsets of size 2 / simplices of dimension 1; as you point out, as soon as we allow arbitrary rank simplices, the above runtime cannot be achieved anymore, as the input alone has size $O(2^n)$.

EDIT: Actually, looking at the Wikipedia link I give, I discovered that there is a paper by Babai and Codenotti (2008), "Isomorhism of Hypergraphs of Low Rank in Moderately Exponential Time", where they give an algorithm that works in the same general time as Luks' algorithm for hypergraphs (and thus in particular simplical complexes) of bounded rank that has roughly the same general run time as Luks' algorithm for graph isomorphism. Of course that still does not answer the general question.

Answer by Max for Does -I belong to Weyl group?

2011-11-25T10:31:41Z

Depends on what you mean with $-I$...

If you mean an element $w\in W$ such that $w\Phi^+=\Phi^-$, then this does always exist and is always the longest element $w_0$. See for example Section 1.8 in "Reflection Groups and Coxeter Groups" by Humphreys (who is also a regular here ;).

If you meant to ask whether $w\in W$ exists such that $w$ acts like $-I$ on the natural geometric representation of $W$ (as defined in Section, then this is the case if and only if $W$ has non-trivial center, in which case the center has just two elements, $w_0$ and $1$, and you want $w=w_0$. Now obviously $w_0$ is in the center if and only if conjugation by $w_0$ is trivial. But in many cases, conjugation by $w_0$ induces a diagram automorphism. With some computations one can thus verify that $w_0$ is in the center for types $A_1$, $BC_n$, $D_{2n}$, $E_7$, $E_8$ and $F_4$. While you get a trivial center for type $A_n$ ($n>1$), $D_{2n+1}$ and $E_6$.

Answer by Max for Nilpotency class of a certain finite 2-group

2011-11-07T14:51:16Z

The nilpotency class of $G_d$ is indeed always 3. One way to see this is to rewrite the presentation of $G_d$ in such a way to exhibit that it is a polycyclic group. For this purpose, let $z:=[x,y]$ and $w:=y^{2^{d-1}}=x^{2^d}$. Clearly $w$ lies in the center of $G_d$. With a little more effort we see that $$ G_d \cong \langle x, y, z, w\mid x^4 = y^2, y^{2^{d-1}} = w, z^2 = w^2 = 1 ; y^x = yz, z^x = zw, z^y = z, w^x=w^y=w^z=w \rangle $$

This is indeed a polycyclic presentation, with relative order $4, 2^{d-1}, 2, 2$. (Thus the group has order $4* 2^{d-1}* 2* 2=2^{d+3}$).

But now it is easy to read off that $[G_d,G_d] = \langle z, w\rangle$, and thus $[[G_d,G_d],G_d]=\langle w \rangle$, which is central. Hence the nilpotency class is 3.

(Non-)existence of skew fields satisfying a SGPI (=skew generalized polynomial identity)

2011-08-19T09:26:58Z

Let $K$ be a skew-field, infinite dimensional over its center $F$.

From Kaplansky's PI-theorem it then follows that $K$ cannot satisfy a polynomial identity (the theorem says that primitive PI-algebras have finite dimension over their center).

There, a GPI (generalized polynomial identity) has coefficients from the center $F$. If the coefficients are arbitrary, one has a GI (generalized identity), and a theorem by Amitsur describing the possible structure of $K$.

In my research, I now came upon skew-fields which might satisfy a "skew" GPI in the following sense: Let $\sigma$ be an involutory antiautomorphism of $K$ and $\gamma$ an automorphism of $K$ of order 1 or 2. For simplicity, let's restrict to the case that $\sigma$ and $\gamma$ commute.

Is it possible that $K$ satisfy an "skew" GPI, meaning that coefficients are arbitrary from $K$, and the GPI contains not just $x$, but also $x^\gamma$, $x^\sigma$ and $x^{\gamma\sigma}$ ? The case with a single unknown is all that interests me.

I actually kinda hope these skew fields don't exist respectively must be finite dimensional over their center.

Answer by Max for Finitely generated subgroup

2011-07-12T07:55:58Z

If $G$ is polycyclic, then every subgroup is finitely generated. In fact, one of several ways to define a polycyclic group is to demand that it is a solvable group for which all subgroups are finitely generated. So, this might seem kind of tautological, but polycyclic groups have other definitions and they come up quite a bit in various areas.

This is a special case of the class of Noetherian groups, also known as slender groups, in which are defined by having the property that every subgroup is finitely generated. You can find some more information on this subject in this MO question.

Answer by Max for Finding groups of odd order without non-cyclic nilpotent quotients

2011-06-24T12:39:34Z

Hi Tom,

the answer (at least to your second, refined question) is "Yes! or at least "Yes, soon!" :). I first wanted to post this as a comment, but since it is rather lengthy, I figured it made more sense to give this as an answer, even though it might not be completely satisfying.

There are algorithms that can generate all groups up to a given order; those were used to create the database of small groups. Indeed, I am currently working on a refined set of such algorithms. We plan to use this to extend the database to small groups to orders up to 10,000 (excluding multiples of 1024 and $3^7$ or $3^8$). As part of this, I am working on algorithms that allow constructing all extensions of a group $A$ by another group $B$; but also allow restriction to say all metabelian groups of a given order; etc.

Of course you can just generate all groups up to a given order, and then remove all you don't need, but that's very wasteful. A first refinement is to restrict to generating all groups of odd order, that's already considerably better.

But you can do more: Say a group $G$ has property * if it has odd order, is solvable and has no non-cyclic nilpotent quotients. To find all these groups up to order $n$, it suffices to compute all extensions $E$ (up to isomorphism) of a solvable group $N$ by a cyclic group $Q$, both of odd order, for which $[E,N]=N$.

This is sufficient because the quotients of $E$ by its lower central series are all nilpotent, so must all be cyclic if property * is to hold. But then we can assume $N$ to be the last term of the lower central series (last here means: the term from which on the series becomes stable). And have that $E/N$ is cyclic, and $[E,N]=N$.

The condition that $[E,N]=N$ translates into a restriction on the action of $Q$ on $N/N'$. For it implies (with some handwaving) that $N/N' = [E,N]/N' = [Q,Q] [Q,N/N'] [N/N', N/N'] = [Q,N/N']$ (as $Q$ and $N/N'$ are abelian). This can now be used to effectively cut down on what groups and couplings between them are possible for $Q$ and $N$.

This is indeed a special case of an algorithm we (Bettina Eick and me) are planning to include in our new GAP package. As of now, though, I have not yet turned to working on this algorithm, but it'll happen in the forseeable future.

Answer by Max for Relative Hirsch number

2011-06-08T12:11:39Z

What you are asking is about a generalization of the Hirsch length for polycyclic(-by-finite) groups. Of course, a finitely generated nilpotent group is polycyclic, so the special case that mainly interests you is quite classic.

For a polycyclic group (and more generally, for a polycyclic-by-finite group), the Hirsch length $h(g)$ is a well-known invariant, and it coincides with your "relative Hirsch number" for the pair $(G,1)$. Basic information about this can be found via Google, e.g. on Wikipedia. If you want a book, look at "Polycyclic Groups" by Daniel Segal. Unfortunately I am not aware of a reference for your relative Hirsch length.

Answers

I don't know an answer to your first question in the general case, and already in the polycyclic case such series won't exist in general. But if your group $G$ is nilpotent (as in your special case), you can do the following to prove that such a series always exists: Start with the series $$ G=HG^{(0)}, HG^{(1)}, HG^{(2)}, \ldots , H $$ where $G^{(0)}:=G$ and $G^{(i+1)}=[G,G^{(i)}]$; since $G$ is nilpotent, there is $k\in\mathbb{N}$ such that $G^{(k)}=1$. One now verifies that the series from $G$ to $H$ I described is actually a subnormal abelian series. You can now refine it to a series in which all factors are cyclic. Since we are in the polycyclic setting (where all subgroups are finitely generated), this will result in a series of finite length.
For polycyclic groups, $h(G)$ is well-defined. It is not hard to extend the standard proof for this to your settings, answering your second question in the affirmative: If two subnormal cyclic series from $G$ down to $H$ exist, then by the Schreier refinement theorem, they have equivalent refinements (i.e. the factors $H_i/H_{i+1}$ which occur in the two refinements are the same, just possibly ordered differently). But a refinement of one of these subnormal cyclic series cannot change the number of infinite cyclic factors (easy exercise, also used in the "standard" proof). Hence the relative Hirsch length is well-defined.
Your third question also has a positive answer: Any subnormal cyclic series from $G$ to $H$ induces such a series from $G/H$ to $1=H/H$, and vice-versa, and the cyclic factors occurring obviously are the same in both cases. So you have $h(G,H)=h(G/H)$, and if $H$ also is polycyclic (as in your special case), you even have $h(G,H)=h(G/H)=h(G)-h(H)$.
As I already mentioned, I don't know a good reference for this in the literature, only references to polycyclic(-by-finite) groups.

Does "all points rational" imply "constant" for this "cubic" curve over an arbitrary field?

2011-06-07T12:53:32Z

Let $\mathbb{K}$ be an arbitrary field with a subfield $\mathbb{F}$ of index 2. Let $a,b\in\mathbb{K}[X]$ be univariate non-vanishing polynomials over $\mathbb{K}$ of degree $\leq 3$ each. Edit: Due to how this problem arises, one may assume that $a,b$ have no common zeros and at least one has degree exactly 3. However, I am also interested in what happens without this extra assumption, but instead the assumption that $char\mathbb{K}\neq2$. The latter to avoid the counterexamples described in the comments.

Consider the set of points $T:=\{(a(x),b(x)) \mid x\in\mathbb{K}\}$, a subset of $\mathbb{K}^2$.

Prove (or give a counterexample) for the following:

Claim: Assume every point $T$ is projectively equivalent to a point in $\mathbb{F}\times\mathbb{F}$ (i.e. for every $x\in\mathbb{K}$ we have $a(x)=b(x)\cdot f_x$ for some $f_x\in\mathbb{F}$). Then either $\lvert\mathbb{K}\rvert=4$ or 9, or all points in $T$ are projectively equivalent (that is, $T$ is contained in a one-dimensional $\mathbb{K}$-subspace of $\mathbb{K}^2$); put another way, $a/b$ is a constant.

Since we assumed $a,b$ to have no common zeros, we can think of this in terms of projective coordinates. Then the question becomes: If all points on the curve $T$ are $\mathbb{F}$-rational, does this imply that $T$ consists of a single point?

For finite fields, this can be shown using a simple counting argument (had to check the field with 9 elements manually, and found an exception over the field with four elements). It is also not hard to see that the condition of the claim implies that $a,b$ must have coefficients in $\mathbb{F}$.

For $\mathbb{K}=\mathbb{C}$ and $\mathbb{F}=\mathbb{R}$ I have an argument involving the topology and metric of these fields. For the general case, I tried various approaches, and one of them might still work out (but all my ideas seem at some point to end up in heavy, uninsightful and simply ugly computations)...

But I keep wondering if this isn't a problem that somebody with a better background in number theory or algebraic geometry or something like that could quickly solve with "standard" methods.... so before I keep going on with my little knowledge, I though it best to ask here for any pointer or even solutions :).

Lastly, here is one thing I was trying, but couldn't quite complete. It's quite possibly a dead end, so you may not want to get yourself overly distracted by it :): Pick $\alpha\in\mathbb{K}\setminus\mathbb{F}$. For each $t\in\mathbb{K}$, define a polynomial $p_t(x):=a(x+t)b(\alpha+t)-a(\alpha+t) b(x+t)$. They all have $\alpha$ as a zero. And (up to some rescaling), the coefficients of $p_t$ are in $\mathbb{F}$ by hypothesis.

Now if any of the $p_t$ vanishes everywhere, then all do, and $a/b$ is constant. So assume the $p_t$ do not vanish. Then every $p_t$ is divisible by the minimal polynomial of $\alpha$, and so has degree 2 or 3. Indeed, looking at the coefficients, for at most three $t$ can $p_t$ have degree 2, so for almost all it has degree 3, and is divisible by the minimal polynomial of $\alpha$. This sounds quite improbable to me (but that proves nothing, only that I lack imagination ;). So we could now compare several of the $p_t$, and try to derive a contradiction, but this (at least in the naive ways I tried) quickly gets very messy, uninsightful and ugly ;).

Answer by Max for Proof of an 'easy' exercise in a book of Tits

2011-04-19T11:01:14Z

(1) implies (2): Indeed, the left side of (2) is obviously contained in the right side. So pick an arbitrary $h=g_2g_3=g_1 \in (G_2G_3)\cap G_1$. Now, $g_3=g_2^{-1}g_1$ is contained in $G_2G_1$ but also in $G_3G_1$ and hence by (1) in $(G_2\cap G_3)G_1$. So there is $g_{23}\in G_2\cap G_3$ and $\tilde{g}_1\in G_1$ such that $g_3=g_2^{-1}g_1=g_{23}\tilde{g}_1$. Thus $g_2g_{23}=g_1\tilde{g}_1^{-1}\in G_1\cap G_2$ and $g_{23}^{-1}g_3=\tilde{g}_1\in G_1\cap G_3$, therefore $h=g_2g_3 = (g_2g_{23})(g_{23}^{-1}g_3)\in (G_1\cap G_2)\cdot(G_1\cap G_3)$.

(2) implies (3): Wlog assume x=1. From $G_1\cap yG_2\neq\emptyset$ follows $y\in G_1G_2$; similarly we find $z\in G_1G_3$.
Thus $y=g_1g_2$, $z=\tilde{g_1}g_3$ for suitable elements $\tilde{g_1},g_1\in G_1$, $g_2\in G_2$, $g_3\in G_3$.

From $yG_2\cap zG_3\neq\emptyset$ we get $y^{-1}z\in G_2G_3$, hence $$ g_2^{-1} g_1^{-1} \tilde{g_1}g_3 \in G_2 G_3 \implies g_1^{-1} \tilde{g_1} \in (G_2 G_3) \cap G_1. $$ But using (2), wlog we may assume $g_1\in G_1\cap G_2$ and $\tilde{g}_1\in G_1\cap G_3$. Thus $y\in G_2$ and $z\in G_3$, and so $xG_1\cap yG_2 \cap zG_3 = G_1\cap G_2 \cap G_3 \neq \emptyset$.

(3) implies (1): The right side of (1) is clearly contained in the left side, so we just need to prove the reverse inclusion. So assume $h\in G_2 G_1 \cap G_3 G_1$. Then $h \in G_2 y \cap G_3 z$ for suitable $y,z\in G_1$. Thus $y\in G_1\cap yG_2$ and $z\in G_1\cap zG_3$. Thus by (3) there exists $g_1 \in G_1 \cap G_2 y \cap G_3 z$, and we have $1 \in G_2 y g_1^{-1} \cap G_3 z g_1^{-1}$. This implies $yg_1^{-1} \in G_2$ and $zg_1^{-1}\in G_3$. Therefore $hg_1^{-1} \in G_2 yg_1^{-1} \cap G_3 zg_1^{-1} = G_2 \cap G_3$, and thus $h\in (G_2 \cap G_3) G_1$ as claimed.

Answer by Max for how many semi direct products are there?

2011-03-18T12:26:25Z

You are asking for isomorphism classes of split extensions $H$ of the module $N:=\mathbb{Z}/n\mathbb{Z}$ by the group $G:=\mathbb{Z}/2\mathbb{Z}$. This is a special case of a metacyclic group, by the way.

A first approximation is to determine all homomorphisms from $\mathbb{Z}/2\mathbb{Z}$ into the automorphism group $Aut(N)$ of $N$; each of these corresponds to a semidirect product (but we still might get some isomorphism classes multiple times). Now, it is well-known that $Aut(N)\cong \mathbb{Z}/\phi(n)\mathbb{Z}$, where $\phi$ denotes Euler's totient function.

Using the above (and the links I gave), it is not difficult to see that the 2-Sylow-subgroup $P$ of $Aut(N)$ is isomorphic to $(\mathbb{Z}/2\mathbb{Z})^m \times Aut(\mathbb{Z}/2^k\mathbb{Z})$, where $m$ equals the number of distinct odd primes divisors of $n$, and $2^k$ is the largest power of $2$ dividing $n$. If $k=0$ or $k=1$, then $P\cong(\mathbb{Z}/2\mathbb{Z})^m$. If $k>1$, then $P\cong (\mathbb{Z}/2\mathbb{Z})^{m+1} \times \mathbb{Z}/2^{k-2}\mathbb{Z}$.

Counting the number of homomorphisms from $G$ into this, then for $k=0$ or $k=1$ we get $2^m$; for $k=2$ we get $2^{m+1}$ and for $k>2$ we get $2^{m+2}$.

With some more effort, one proceeds to verify that each of these homomorphisms leads to a unique isomorphism class; for that, you essentially have to verify that $G$ either acts trivially or non-trivially on each $p$-Sylow-subgroups; and that it really has four non-isomorphic actions on $\mathbb{Z}/2^k\mathbb{Z}$ if $k>2$ (once you get an action like in a dihedral group, once like in a semidihedral / quasidihedral group; once as in the direct product; and one more).

Answer by Max for An algorithm to find non-trivial linear dependencies

2011-02-08T22:30:38Z

I am not quite sure what precisely your question is. But I'll assume that it is this: Given a set of $v$ vectors inside $F^n$, what is the complexity of computing the set of all minimal circuits in the set of vectors?

Now note that complexity depends on what one considers to be the input size. In this case, one cannot just look at $n$, rather $v$ must be taken into account, too. For one can construct arbitrarily large sets where every subset of size $n$ forms a basis (e.g. for $n=2$, take the set of vectors $(1,x)$ where $x$ is arbitrary). So then minimal circuits are precisely the subsets of size $n+1$. Hence the output size is $\binom{v}{n+1}$. For fixed $n$ this is clearly unbounded as $v$ increases. Therefore the complexity can't even be in $O(2^n)$, or in $O(f(n))$ for any real-valued function $f$.

On the other hand, if you consider only $v$ as input and assume $n$ to be fixed, then exhaustive search involves computing the determinant of a number of matrices. The exact number is bounded above by $\sum_{i=2}^n \binom{v}{i}$, which is a polynomial in $v$ of degree $n$. Hence the complexity of this approach is in $O(v^n)$ (we can neglect the time to compute the determinants, as it only depends on $n$, which here is a constant).

This is also essentially the answer (modulo a now non-constant factor for computing the determinants) if you consider both $v$ and $n$ as input sizes, by the example above: Since the output can have size $\binom{v}{n+1}$, there can't be an algorithm asymptotically "faster" than $O(v^n)$.

You may want to argue that one can modify the output, e.g. by not outputting the minimal circuits of size $n+1$ (these can be easily identified if all smaller minimal circuits are known). But that won't help, as you can e.g. construct examples where the minimal circuits are all subsets of size $k$, for any $2\leq k\leq n+1$.

Answer by Max for Row reduction of sparse matrices

2011-01-10T20:47:04Z

The LinBox project provides a C++ library which can effectively compute the rank of sparse matrices over finite fields.

You could also look at Sage which should also allow this, but I am not sure whether they have effective implementations for this particular case. If you have access to it, then Magma can also do this.

Infinite subfields of division algebras with finite center

2010-12-04T18:18:02Z

Assume we are given a non-commutative division algebra $D$ over a finite field $\mathbb F_q$, with the center of $D$ equal to $\mathbb F_q$. Clearly $D$ must be infinite dimensional over its center.

Does $D$ necessarily contain an element of infinite multiplicative order? I.e. an element $x$ such that $x^n\neq 1$ for all positive integers $n$ ?

Any hints on a proof or a counterexample would be appreciated.

If there are examples where all elements have finite order, I wonder about the following weaker question:

Does $D$ contain an infinite subfield? (Here subfield of course means that it must be commutative.)

Infinite dimensional division algebras with finite center, and their involutions

2010-12-03T14:06:12Z

Let $q$ be a prime power, and $D$ a non-commutative division algebra (skew field) over $\mathbb{F}_q$ (the finite field with $q$ elements) such that the center $C(D)$ equals $\mathbb{F}_q$.

Question 1: Do such division algebras exist? Are there "simple" examples?

The only non-commutative division algebras over finite fields I know are skew Laurent series. E.g. $D=\mathbb F_{q^2}((t))$, where $t$ induces by conjugation on the coefficients $c\in\mathbb F_{q^2}$ the unique involutory field automorphism, i.e. $tc = c^qt$.

Then $\mathbb F_q$ embeds into $D$, but $C(D)$ is infinite as it contains all even powers of $t$. Maybe the construction can be modified to make the center finite? I am not quite sure where to look for more information or examples. All literature I found so far deals primarily with finite-dimensional division algebras.

Question 2: What are good references on infinite dimensional division algebras? Books, articles, surveys, anything?

Based on an example for such an object, I hope to get a better feeling for the following problem: We now also have an automorphism $\gamma$ of $D$ of order 1 or 2, and an involutory anti-automorphism $\sigma$ of $D$.

Call a (commutative!) subfield $\mathbb K$ of $D$ nice if $\gamma$ and $\sigma$ restrict to it, i.e. if $\mathbb K^\sigma = \mathbb K = \mathbb K^\gamma$.

Question 3: What can be said about the nice subfields of $D$? In particular, how large can one make nice subfields; are there infinite ones?

Clearly the (finite) center is nice. And I think that one can always find a nice subfield with $q^2$ elements, but beyond that... ? Maybe looking at some special cases helps:

Question 4: What can we say if $\gamma$ is trivial?

If $D$ contains an element $t$ of infinite (multiplicative) order, then we get an infinite nice subfield: Either $t+t^\sigma$ has infinite order and then we can adjoin that to the center; or else, let $n$ be its finite order. Then $1=(t+t^\sigma)^{np}=t^{np}+(t^{np})^\sigma$, hence $t^{np}$ (which has infinite order) commutes with $(t^{np})^\sigma$ can we can adjoin that to the center. This motivates

Question 5: Does $D$ necessarily contain an element of infinite (multiplicative) order?

Of course one can now look at further special cases of my problem, e.g. the case that $\gamma$ and $\sigma$ commute seems to be in reach. But this still seems pretty far from the general question.

Finding minimal subsets of a finite integer set with gcd equal to the whole set

2010-11-07T23:51:28Z

Given a finite non-empty set $N$ of integers, call a subset $M$ of $N$ good if $gcd(M)=gcd(N)$. The other subsets are called bad.

Does there exist an algorithm which computes a good subset of minimal size in polynomial time (polynomial in $|N|$)?

Using a greedy strategy, it is easy to find good subsets $M$ which are minimal with respect to inclusion (i.e. every proper subset of $M$ is bad). But it is not difficult to construct examples where such a greedy strategy may fail to find a set of globally minimal size. Take for example N={6=2*3, 10=2*5, 15=3*5, 1}. Then $gcd(N)=1$, and both {6,10,15} and {1} are good subsets. Both are minimal good subset wrt to inclusion. This can be easily generalized.

So, something more advanced would needed. Obviously, one can test all subsets, but then one gets exponential runtime. Is there a better way? Or can one prove that there isn't? Maybe this is equivalent to efficiently factoring primes? As it is, I am not even sure whether this problem is in NP...

(Note that this question is about an important special case of an earlier question of mine; I hope it'll attract a few more people by being less technical).

Finding globally minimal row subsets of an integer matrix which generate the full row span

2010-11-04T22:48:24Z

Given a $n\times m$ integer matrix $A$, we can consider its row span $span(A)$, that is, the minimal sublattice of $\mathbb{Z}^m$ containing all rows of $A$.

Given a subset of the rows of $A$ it is possible to check in polynomial time whether they already span $span(A)$. Hence one can determine whether a given row subset is minimal (with regard to inclusion) with the property that it spans the row space of $A$ (simply try removing any row and see if the result still spans the row space of $A$). But since we work over the integers, it is possible that there are other, strictly smaller row subsets with the same property. As an example, consider the "vectors" 2, 3 and 1. Then {2,3} and {1} both are minimal generating sets for $\mathbb{Z}$ of differing size. This leads to my first question:

Is there a polynomial time algorithm to verify whether a given subset of rows spanning the row space of $A$ is globally minimal with this property?

With "globally" minimal I mean that no other subset of smaller size with the desired property exists. And regarding "polynomial time", I know that I am a bit vague here; but I'd already be happy if there was something polynomial in $nm$, never mind the size of the coefficients in $A$.

I have the suspicion that this is the not the case. But if it is, then the natural next questions is:

Is there a polynomial time algorithm which, given $A$, computes a globally minimal subset of rows which span the full row space of $A$?

An interesting special case arises for $m=1$:

Given a set $N$ of integers, is there a polynomial algorithm for computing a globally minimal subset $M$ of $N$ such that $gcd(N)=gcd(M)$ ?

The context where this problem arises for me is that of abelian groups: Given a set of generators of an abelian group, how can one find a globally minimal subset of these generators which still generate the whole group? Finding a minimal generating set in this case is easy, but the restriction that I need to use a subset of the original generators seems to make things quite a bit more difficult.

Answer by Max for classification of small complete groups

2010-10-01T01:26:00Z

Here's a very partial "experimental" result, using some GAP computations and the library of small groups in GAP. I am afraid this does not provide any deep theoretical insight, but it might at least give some ideas and starting points.

There is not really an efficient way to check whether a group is complete, I think; however, one thing is sure: It can't be nilpotent (as nilpotent groups have non-trivial center). The small groups library knows for every group in it whether it is nilpotent, so we can filter those out. There are 1048 groups of order 1 to 100; of these 464 are not nilpotent, as the fol.owing code verifies:

gap> Sum(List([1..100],NumberSmallGroups));
1048
gap> grps:=AllSmallGroups([1..100], IsNilpotentGroup, false);;              
gap> Length(grps);
464

Computing the center of a group is also relatively efficient, so let's remove all with non-trivial center:

gap> grps:=Filtered(grps,g->IsTrivial(Center(g)));;
gap> Length(grps);
72

Finally, the condition on the automorphism group:

gap> grps:=Filtered(grps,g->Size(g)=Size(AutomorphismGroup(g)));;
gap> Length(grps);
5

So what are these groups? If we just print "grps", we don't see much, but we can ask GAP to try to come up with "nice" labels for the groups (they just give a rough idea of the group's structure; they are not enough to recover the group):

gap> List(grps, StructureDescription);
[ "S3", "C5 : C4", "S4", "(C7 : C3) : C2", "(C9 : C3) : C2" ]

Note that GAP denotes semidirect products by "N : H", where N is normal. Also note that in general there are many ways to write a group as, say, a semidirect product, and GAP may not pick the most "natural" one -- after all what is "natural" is highly subjective.

Anyway, so we get $S_3$, $S_4$ and the holomorphs of the cyclic groups of order 5, 7 and 9. The last one is not in your list (but almost)... Continuing with a slightly more elaborate program (looping over the orders instead of grabbing all groups of a lot of orders at once, as that will easily overflow memory), we find 27 complete groups up to and including order 500:

$S_3$
$Hol(C_5)$
$S_4 \cong Hol(C_2^2)$
$Hol(C_7)$
$Hol(C_9)$
$Hol(C_{11})$
$S_5$
$S_3 \times Hol(C_5)$
$((C_3^2) : C_8) : C_2$
$S_3 \times S_4$
$Hol(C_{13})$
$((C_2^3) : C_7) : C_3 < Hol(C_2^3)$
$(((C_2^2) : C_9) : C_3) : C_2$
$S_3 \times Hol(C_7)$
$Hol(C_{17})$
$((C_2^4) : C_5) : C_4$
$S_3 \times Hol(C_9)$
$PSL(3,2) : C_2$
$Hol(C_{19})$
$((((C_4^2) : C_3) : C_2) : C_2) : C_2$
$((((C_2^4) : C_3) : C_2) : C_2) : C_2$
$(((C_3^2) : C_3) : Q_8) : C_2$
$(((C_6^2) : C_3) : C_2) : C_2$
$(((C_3^2) : Q_8) : C_3) : C_2 \cong Hol(C_3^3)$
$Hol(C_5) \times S_4$
$Hol(C_{27})$
$Hol(C_{25})$ (order 500)

So, besides the classes you named, we also get holomorphs of cyclic groups of prime-power order; direct products of complete groups, plus some other groups which one should study a bit closer to understand.

Answer by Max for Computer power in plane geometry

2010-08-18T01:05:35Z

First off, I would be skeptical of the claim that computer programs "may prove any theorem in elementary Euclidean geometry", simply because it is so wide and general that is prone to be false. Secondly, I am not directly an expert in this field myself, but I hope my references are not too much off.

However, modern automatic geometric theorem proving is definitely capable of dealing with a large number of geometric problems, including those which involve geometric inequalities. The older methods (going back to Wu), translate a geometric statement is translated into an implication of the form $$ \bigwedge_{i=1}^n f_i(x_1,\ldots,x_m) \implies f_0(x_1,\ldots,x_m)$$ where the $f_i$ are polynomials. From this, with various methods one then obtains a prove of the statement, or a counter example. I am suppressing here that often you need to specify further side conditions for a proof to be possible, e.g. that a triangle is non-degenerate; in fact, Wu's approach and the Gröbner basis even allow deducing sufficient conditions to make a theorem true in retrospect. The Wikipedia page for Wu's method gives some more details and a few references to relevant papers; you can easily google more.

Anyway, this allows encoding things like multiple points being collinear, points being contained on a circle, intersection of lines, perpendicularity of lines, and so on. However, this does indeed not allow encoding inequalities effectively; e.g. just specifying that a point is 'inside' a triangle, or that one value is less than another, in general is not possible.

But since Wu's original work, there have been many advances. If one looks a bit closer, then one notices that the above techniques actually prove theorems about complex geometry, as we are arguing about zeros of polynomials, and this all happens over an algebraically closed field. But we are usually interested in real geometry only. There are surprisingly many classical theorems from "real" geometry which remain true in the complex case, and this somewhat surprising (and as far as I know rather mysterious) fact ensures that nevertheless Wu's method and its relatives are quite successful. Still, people have worked on overcoming this limitation, as well as that of inequalities.

One approach is described "A New Approach for Automatic Theorem Proving in Real Geometry", by Dolzmann, Sturm & Weispfenning, who use quantifier elimination (from logic) to prove theorems in real geometry (as the title suggests), using their Reduce package Redlog. They use that, for example, to prove Pedoe's inequality. I am, however, not sure if this can be used to prove the Erdős–Mordell inequality; one could ask them. I think Sturm wrote his PhD thesis on the subject.

Another paper to look at is "A Practical Program of Automated Proving for a Class of Geometric Inequalities" by Lu Yang and Ju Zhang. There they describe a Maple package "Bottema" (unfortunately, this does not seem to be available on the net, at least I couldn't find it). They use it to prove a load of inequalities, and give many examples involving inequalities. To give you a flavor, here is an example (which they proved using their package):

Example 4. By $m_a$, $m_b$, $m_c$ and $2 s$ denote the three medians and perimeter of a triangle, show that $$\frac{1}{m_a}+\frac{1}{m_b}+\frac{1}{m_c}\geq \frac{5}{2}.$$

And here is another excerpt (I included it as it also goes back to Erdős).

A. Oppenheim studied the following inequality in order to answer a problem proposed by P. Erdös.

Example 9. Let $a$, $b$, $c$ and $m_a$, $m_b$, $m_c$ denote the side lengths and medians of a triangle, respectively. If $c = \min\{a, b, c\}$, then $$2m_a+2m_b+2m_c \leq 2a+2b+(3\sqrt{3}-4)c.$$

This all does not answer your question about the Erdős–Mordell inequality. And I am afraid I don't know the answer! But I hope my above explanations at least made it plausible that the answer could be yes, however vague that statement is.

Answer by Max for Does subgroup structure of a finite group characterize isomorphism type?

2010-08-17T13:10:21Z

The answer is no in general. I.e, there are finite non-isomorphic groups G and H such that there exists a bijection between their elements which also induces a bijection between their subgroups.

For this, I used two non-isomorphic groups which not only have the same subgroup lattice (which certainly is necessary), but also have the same conjugacy classes. There are two such groups of size 605, both a semidirect product $(C_{11}\times C_{11}) \rtimes C_5$ (see this site for details on the construction). In the small group library of GAP, these are the groups with id [ 605, 5 ] and. [ 605, 6 ]. These are provably non-isomorphic (you can construct the groups as described in the reference I gave, and then use GAPs IdSmallGroup command to verify that the groups described there are the same as the ones I am working with here). With a short computer program, one can now construct a suitable bijection.

First, let us take the two groups:

gap> G:=SmallGroup(605, 5);    
<pc group of size 605 with 3 generators>
gap> H:=SmallGroup(605, 6);
<pc group of size 605 with 3 generators>

The elements of these groups are of order 1, 5 or 11, and there are 1, 484 and 120 of each. We will sort them in a "nice" way (that is, we try to match each subgroup of order 5 to another one, element by element) and obtain a bijection from this. First, a helper function to give us all elements in "nice" order:

ElementsInNiceOrder := function (K)
    local elts, cc;
    elts := [ One(K) ];
    cc := ConjugacyClassSubgroups(K, Group(K.1));
    Append(elts, Concatenation(List(cc, g -> Filtered(g,h->Order(h)=5))));
    Append(elts, Filtered(Group(K.2, K.3), g -> Order(g)=11));
    return elts;
end;;

Now we can take the elements in the nice order and define the bijection $f$:

gap> Gelts := ElementsInNiceOrder(G);;
gap> Helts := ElementsInNiceOrder(H);;
gap> f := g -> Helts[Position(Gelts, g)];;

Finally, we compute the sets of all subgroups of $G$ resp. $H$, and verify that $f$ induces a bijection between them:

gap> Gsubs := Union(ConjugacyClassesSubgroups(G));;          
gap> Hsubs := Union(ConjugacyClassesSubgroups(H));;
gap> Set(Gsubs, g -> Group(List(g, f))) = Hsubs;
true

Thus we have established the claim with help of a computer algebra system. From this, one could now obtain a pen & paper proof for the claim, if one desires so. I have not done this in full detail, but here are some hints.

Say $G$ is generated by three generators $g_1,g_2,g_3$, where $g_1$ generates the $C_5$ factor and $g_2,g_3$ generate the characteristic subgroup $C_{11}\times C_{11}$. We choose a similar generating set $h_1,h_2,h_3$ for $H$. We now define $f$ in two steps: First, for $0\leq n,m <11$ it shall map $g_2^n g_3^m$ to $h_2^n h_3^m$.

This covers all elements of order 1 or 11, so in step two we specify how to map the remaining elements, which all have order 5. These are split into four conjugacy classes: $g_1^G$, $(g_1^2)^G$, $(g_1^3)^G$ and $(g_1^4)^G$. We fix any bijection between $g_1^G$ and $h_1^H$ and extend that to a bijection on all elements of order 5 by the rule $f((g_1^g)^n)=f(g_1^g)^n$. With some effort, one can now verify that this is a well-defined bijection between $G$ and $H$ with the desired properties. You will need to determine the subgroup lattice in each case; linear algebra helps a bit, as well as the fact that all subgroups have order 1, 5, 11, 55, 121 (unique) or 605. I'll leave the details to the reader, as I myself am happy enough with the computer result.

Answer by Max for What can be said about a group from its presentation?

2010-08-16T11:50:33Z

If you have a finite presentation of a group $G$, then you can easily derive its abelianization $G^{ab}$ from that, by standard techniques: Basically, you create an integer matrix, with one column for each generator, and one row for each relation, noting in entry $a_{ij}$ how often the generator $g_j$ occurred in the relator $r_i$. Then, compute the Smith normal form of this and you can read of the isomorphism type of $G^{ab}$.

If this happens to be non-trivial, you immediately have a proof that your group is non-trivial. Of course, the converse fails.

Answer by Max for Mathematical software for computing in integral group rings of discrete groups?

2010-08-10T16:06:44Z

You can do this with GAP. The example below assumes that you have the polycyclic package installed.

First, you tell GAP which group you want to work with. Luckily, Heisenberg groups are polycyclic, and the polycyclic package provides a command to obtain them:

gap> G:=HeisenbergPcpGroup(1);
Pcp-group with orders [ 0, 0, 0 ]

Note that we could have also defined it by some other means if polycyclic was not available (e.g. as a matrix group), but this way is the most convenient. Now let's form the integral group ring:

gap> ZG:=GroupRing(Integers,G);
<free left module over Integers, and ring-with-one, with 6 generators>

The extra three generators come from the inverses of x, y and z (note that internally it calls them g1,g2,g3; it would be possible to change that with some effort, but that's beyond the scope here). Let's assign the corresponding generators of the group ring to variables x, y, z, and verify the relations you have given:

gap> x:=ZG.1;; y:=ZG.2;; z:=ZG.3;;
gap> x*z=z*x and y*z=z*y and y*x=x*y*z;
true

Here is an example of powering a group element (this works with more complicated ones, too, but I picked a small one to keep the output readable).

gap> (x+7*y)^2;
(1)*g1^2+(7)*g1*g2*g3+(7)*g1*g2+(49)*g2^2

I hope this helps.

Comment by Max

2012-08-29T19:16:56Z

For what it's worth, I just verified with GAP that the statement holds for all groups of order at most 511.

Comment by Max

2012-08-26T21:44:48Z

The symbol has the same meaning as in other areas of math: I.e. $L$ (as a set) equals the union of the sets $T^g$. Group theory doesn't redefine this notation.

Comment by Max

2012-08-22T09:54:56Z

Some googling for news about Thurston in the past 24 hours also reveals several obituaries, e.g. obituaries.pressherald.com/obituaries/…

Comment by Max

2012-07-18T11:16:20Z

@J.J. Green: In many fonts, the difference between some of 1, l, I, i, | is hard to tell. Even with glasses, which I wear since childhood. Worse, indices tend to occur in subscripts, in smaller font. Classic example: l and I in Computer Modern, the default (La)TeX font. I find $C_I$ and $C_l$ difficult to distinguish there (and on this website, too). Yes I can distinguish them when focusing, but a single mixup when reading can cause lots of confusion. Hence many people use \ell instead of l. If you have a better solution (note that you usually can't choose fonts in journals), please tell!

Comment by Max

2012-06-27T15:47:51Z

Anyway, this indeed doesn't answer your question (which is why I am only posting comments ;), but it still might help a little bit, as it means that while your group doesn't admit a BN-pair, it contains a group with BN-pair as a lattice, and there are various rigidity results by now about these lattices; and one can then use those to study the group $G^+$, to e.g. study (topological) simplicity etc.

Comment by Max

2012-06-27T15:45:03Z

Now, I think the distinction between $SL_n$ and $GL_n$ is really a red herring -- you can generate $GL_n$ from $SL_n$ by adding some diagonal matrices, where the top left entry runs through all non-zero elements of your field, and the others are 0. In other words, you simply get a bigger torus.

Comment by Max

2012-06-27T15:42:55Z

Actually, the paper by Caprace still might be relevant to you. Say your local field is $\mathbb{F}_q((t))$ (Laurent polynomials over a finite field). Then this one of two possible completions of the ring of Laurent polynomials $\mathbb{F}_q[t,t^{-1}]$. Now, it turns out that the group $G^+ :=SL_n( \mathbb{F}_q((t)) )$ is a (topological) completion of the affine Kac-Moody group $G:=SL_n(\mathbb{F}_q[t,t^{-1}])$. Moreover, $G$ in general embeds as a lattice into $G^+\times G^-$, where $G^- :=SL_n( \mathbb{F}_q((t^{-1})) )$.

Comment by Max

2012-06-27T14:35:30Z

Note that the center of a group with BN-pair always acts trivially on the associated building. So in a sense, the building theoretic part (and hence the BN-pair) only ``sees'' the original group modulo its center. So this "cheap trick" indeed seems quite sensible, I guess... Well, depending on what exactly you want to do ;).

Comment by Max

2012-06-27T14:31:26Z

Actually, a group with a root group datum always also has a (twin) BN-pair (Theorem 4.1 in loc.cit). So I personally would rather say that group with BN-pairs generalize groups with root group datum... ?

Comment by Max

2012-05-27T09:46:04Z

This sounds like a special case of a $(n,k)$-threshold scheme. Such a scheme can be used to share a secrete among $n$ individuals, such that any subset of at least $k$ of them can recover the secret. You are interested in the case $k=1$. There are tons of material on that in the literature; indeed, the Wikipedia page might be a good starting point: en.wikipedia.org/wiki/Secret_sharing

Comment by Max

2012-05-09T17:26:13Z

Hm, doesn't $\mathbb{Z}$ acts freely and isometrically on e.g. $S^1$, too? E.g. by any rotation $\begin{pmatrix} \cos t & -\sin t \cr \sin t & \cos t\end{pmatrix}$ where $t$ is not a rational multiple of $2\pi$, e.g. $t=1$. This then extends to $S^n$ for any odd $n$. Am I missing something again?

Comment by Max

2012-05-09T16:03:52Z

sigh yes, of course, thank you. Quite embarrassing. Will edit once more.

Comment by Max

2012-05-09T15:52:41Z

You are right of course, I only am guaranteed fixed points (= real eigenvalues) if the matrices are of odd dimension, i.e. n is even. I'll edit my (clearly inadequate) answer correspondingly, and leave it around to help others avoid my mistake.

Comment by Max

2012-05-09T15:35:59Z

But is that an isometric action?

Comment by Max

2012-04-05T10:28:43Z

You can use the Lazard correspondence on any $p$-group of class less than $p$. So, in particular, you can also use it on $p$-groups of maximal class, as long as $p$ is larger than the class. This is useful for "asymptotic" statements, but if you are interested in results for a fixed $p$, or for all $p$, then you will have to bound the order $p^n$ of your group quite severely.