User ndkrempel - MathOverflow

Deformations of semisimple Lie algebras

2010-11-26T18:42:08Z

In the questions http://mathoverflow.net/questions/9661/is-semisimple-a-dense-condition-among-lie-algebras and http://mathoverflow.net/questions/9719/what-is-the-zariski-closure-of-the-space-of-semisimple-lie-algebras, something equivalent to the following is mentioned: if you have a smoothly varying family of semisimple Lie algebras, all the Lie algebras in the family are isomorphic. e.g. the following quote:

"Because the Cartan classification of isomorphism classes of semisimples is discrete (no continuous families), connected components of the space of semisimples are always contained within isomorphism classes."

I can't see how this follows just from the discreteness of the classification. Can anyone explain why it's true or give a counterexample?

e.g. could you not have a $\mathbb{P}^1$ of semisimple Lie algebras which are generically isomorphic to $\mathfrak{d}_7 \oplus \mathfrak{a}_1$ say, but at one point you get $\mathfrak{e}_8$, or something similar?

Answer by ndkrempel for A set for which it is hard to determine whether or not it is countable.

2011-03-22T03:06:17Z

The set of isomorphism classes of n-dimensional simple Lie algebras over some field.

The set of isomorphism classes of n-dimensional Hopf algebras over some field.

Answer by ndkrempel for Irreducible representation flipping two elements

2011-03-08T13:34:17Z

[I assume characteristic 0, and then I can extend the scalars to an algebraically closed field, which I can take to be $\mathbb{C}$ as $G$ is finite and $V$ is finite dimensional. It may appear that I then need the starting $V$ to be absolutely irreducible for the argument below, but actually since the eigenvector $e_1 - e_2$ is rationally defined, just irreducible is enough.]

$\rho(g)$ has a single $-1$ eigenvalue, and the rest are $1$, i.e. it is a (complex) symmmetry in the sense of Serre's book Complex Semisimple Lie Algebras. Let $v$ be a $-1$ eigenvector. Since $V$ is irreducible, the orbit of $v$ spans $V$. So the orbit forms a (complex) root system, where the symmetry corresponding to the root $\rho(h)(v)$ is $\rho(hgh^{-1})$ (note we've dropped the integrality hypothesis from Serre's definition of root system). Now complex root systems in this sense correspond to complexifications of real root systems. So the image under $\rho$ of the subgroup of $G$ generated by these symmetries is isomorphic to a (possibly reducible) finite real reflection group of rank $n$. Since reducible Coxeter groups are direct products of their parts, we need only check that irreducible finite Coxeter groups have order at least $2^r$, where $r$ is the rank, which is true by the classification, or by using the normal form for words in Coxeter groups to show that the $2^r$ words formed from omitting any subset of simple reflections from $s_1 s_2 s_3 \dots s_r$ give distinct elements.

Rank of sum of Galois conjugates of a matrix

2011-02-25T16:49:38Z

Given an invertible square matrix $M$ with entries from some number field $K$ which is Galois over $\mathbb{Q}$, sum the Galois conjugates of $M$ to form a new matrix $M' = \Sigma_{\sigma \in \mathrm{Gal}(K/\mathbb{Q})} M^\sigma$. What can one say about the rank of $M'$? It seems like both zero and full rank can occur. Are there any theorems related to this, perhaps with further conditions on $M$, that provide some information about the rank?

Answer by ndkrempel for Rank of sum of Galois conjugates of a matrix

2011-02-25T20:33:08Z

Here is one way to get a theorem about this situation:

Although $M'$ may not be invertible, you can always adjust by a scalar $\lambda \in K^\times$ to ensure that $(\lambda M)'$ is invertible. This can be seen as follows: let ${\alpha_1, \dots, \alpha_n}$ be a basis for $K/\mathbb{Q}$. Write $M = \alpha_1 M_1 + \dots + \alpha_n M_n$ for rational matrices $M_i$. Now $\mathrm{det}(x_1 M_1 + \dots + x_n M_n)$ is a polynomial in $\mathbb{Q}[x_1,\dots,x_n]$ which has non-zero value at the point $(\alpha_1, \dots, \alpha_n) \in K^n$, and so is non-zero. Since $\mathbb{Q}$ is infinite, there is also a rational point $(\beta_1, \dots, \beta_n) \in \mathbb{Q}^n$ at which it is non-zero. Now by the nondegeneracy of the trace form, we can pick a $\lambda \in K$ such that $\mathrm{tr}_{K/\mathbb{Q}}(\lambda \alpha_i) = \beta_i$ for all $i$. Then $\mathrm{det}(\mathrm{tr}_{K/\mathbb{Q}}(\lambda M)) \neq 0$ as desired.

Answer by ndkrempel for How many elements does it take to normally generate a group?

2011-02-14T00:41:03Z

Although it doesn't directly answer your question, it seems interesting to consider groups in which every normal generating set is already a generating set.

At least in the finitely generated world, this is equivalent to "every maximal subgroup is normal", which is also equivalent to $G' \leq \Phi(G)$. For finite groups, this is equivalent to being nilpotent, but for finitely generated groups it may be a strictly weaker condition than nilpotence (I don't know an example however.)

In any case, such a group (for example, any f.g. nilpotent group) necessarily has $\mathrm{nr}(G) = \mathrm{rank}(G)$.

Answer by ndkrempel for Superfluous definitions

2011-02-13T23:28:34Z

Common axioms for groups are associativity, existence of two-sided identity and existence of two-sided inverses. (Sometimes even uniqueness is required too.) However, it is enough to require associativity, existence of right identity and existence of right inverses.

If we mix directions and require right identity and left inverses, we get something not too far removed from a group (I'll leave it as an exercise...)

Answer by ndkrempel for Isomorphism of semidirect products

2011-02-05T13:31:20Z

Aside from the two ways you've mentioned, I think there are just two other ways of getting an isomorphism (i.e. any isomorphism of semidirect products with same $N$ and $H$ is some combination of all four):

Change $H$ to a different complement. This corresponds to multiplying $\phi$ pointwise by inner automorphisms of $N$. These are classified by (non-abelian) 1-cocycles $\mathrm{Z}^1(H,N)$, or since you've already incorporated global conjugations in $N$, you can use the non-abelian cohomology $\mathrm{H}^1(H,N)$. This coincides with the usual cohomology if $N$ is abelian. Note that this doesn't affect the induced map $\tilde{\phi}: H \to \mathrm{Out}(N)$.
Change $N$ to a different normal subgroup of the total group which happens to be isomorphic (and have isomorphic complement.) Edit: This case is hard to deal with in general, but one situation it can be avoided is if you only consider semidirect products in which $N$ plays some special role, like being the derived subgroup. Derek elaborates more on this case in his answer.

Answer by ndkrempel for Signatures on the infinite symmetric group

2011-02-04T23:22:44Z

Here is a direct way to see the answer is 'no'.

Let our countable set be the set of all integers $\mathbb{Z}$.

What is the sign of $(1,2)(3,4)(5,6)(7,8)\dots$? (Note that we're fixing all nonpositive integers here.)

Whatever it is, you can multiply by the transposition $(1,2)$ to get a permutation with the opposite sign, then you can conjugate, which doesn't affect the sign, by $(\dots,-3,-2,-1,0,1,2,3,\dots)^{-2}$ giving back the element you started with. Contradiction.

Answer by ndkrempel for Does any research mathematics involve solving functional equations?

2011-01-27T14:23:50Z

In enumerative combinatorics, you often end up with a functional equation for the generating function of the thing you're trying to count. These can involve compositions of the function with itself (and differentiation, exponential functions, ...) Often these don't have closed-form solutions, and you use them to get recurrences or asymptotics. Try searching for generating functions for labelled and unlabelled trees for some simple examples.

Answer by ndkrempel for Hard Cube Puzzle

2011-01-19T21:03:18Z

This is a variation on a classic card trick (audience pick 5 cards, magician A removes a card of his choosing and hands the rest to magician B, who then names the missing card.)

There are two ways you can view the process - from the point of view of the cube-orienter, or from the point of view of the final guesser.

It turns out to be more useful to consider the cube-orienter's job.

Given a cube, he has to pick an orientation to leave it in. Let's view this as a function from the set of possible cubes to the set of 'visible orientations', i.e. we ignore what's on the bottom face. Then this function must be a bijection, and it must satisfy the constraint that the image of a cube under this function does give a valid 'visible orientation' of that cube.

This constraint can be represented as a bipartite graph, where there are $\frac{1}{24}n(n-1)(n-2)(n-3)(n-4)(n-5) = 30\binom{n}{6}$ vertices on the left representing the different cubes, $n(n-1)(n-2)(n-3)(n-4)$ vertices on the right representing the 'visible orientations', and each cube has $24$ edges linking it to its valid 'visible orientations'. Conversely, each 'visible orientation' has $n-5$ edges linking back to the cubes it could have arisen from. In this context, the bijective function we seek is a matching in this graph.

Hence the original problem is equivalent to the existence of a matching in this bipartite graph. A necessary and sufficient condition for such a matching to exist is given by Hall's Marriage Theorem. We need to check that for any set of $k$ cubes, the cardinality of the union of 'visible orientations' linked to these cubes is greater than or equal to $k$. But $k$ cubes give rise to $24k$ edges, which give rise to at least $24k/(n-5)$ 'visible orientations', which is greater than or equal to $k$ for $n \leq 29$.

So there is a strategy for $n = 29$, and conversely this is the best possible just by comparing the number of vertices on either side.

Update: An explicit strategy was requested, so here is an adaptation of the standard card trick strategy:

Let's assume we're working with numbers from $0$ to $28$ for convenience.

The cube-orienter adds up the numbers on all the faces of the cube modulo $6$. Call the result $i$, with $0 \leq i \leq 5$. Now if $i=0$, put the smallest face face-down, if $i=1$, put the second smallest face-down, and so on. Later on, the guesser will be able to add up all the visible faces modulo $6$, and a little thought shows that the hidden face will be congruent to the negative of this modulo $6$, provided the guesser renumbers the unseen numbers from $0$ to $23$. This means the guesser will know the answer is one of $4$ cards, and these remaining $4$ degrees of freedom can be communicated by the $4$ possible rotations the cube-orienter can leave the cube in (with a fixed face down). E.g. of the side-faces, the largest can be pointing left/forward/right/backward.

Answer by ndkrempel for Sphere packing in a sphere

2011-01-18T18:16:40Z

Although the book "Sphere packings, lattices and groups" by Conway and Sloane deals mostly with infinite packings, it has an extensive bibliography that gives some references for the problem you're interested in too. Here are some entries that looked relevant, although I haven't read them:

Gritzmann and Wills, "Finite packing and covering", in Gruber and Wills, "Handbook of Convex Geometry"
Wills, "Finite sphere packings and sphere coverings"
Wills, "Finite sphere packings and the methods of Blichfeldt and Rankin"
Fejes Toth, "Packing and covering", in Goodman and O'Rourke, "Handbook of Discrete and Computational Geometry"
Nuermela and Ostergard, "Dense packings of congruent circles in a circle"
Melissen, "Densest packing of eleven congruent circles in a circle"
Melissen, "Packing and Covering with Circles"
Chow, "Penny-packings with minimal second moments"
Fejes Toth, Gritzmann and Wills, "Finite sphere packing and sphere covering"
Borcherds and Wills, "Finite sphere packing and critical radii"

Answer by ndkrempel for Semi-simple matrices over fields of finite characteristic

2011-01-13T15:48:55Z

Well, distinct eigenvalues over the algebraic closure is enough to ensure semisimplicity, so the discriminant of the characteristic polynomial is a polynomial in the matrix entries whose non-vanishing ensures semisimplicity. If you prefer a closed set, you could require it to have a specific non-0 value, say 1. Whether this qualifies as a "shape" is another matter.

Answer by ndkrempel for Non-split extensions of $GL_n(F_q)$ by $F_q^n$ ?

2011-01-13T15:35:55Z

There is a famous non-split extension called the "Dempwolff group", $2^5 \cdot GL_5(2) = 2^5 \cdot SL_5(2)$. And apparently this is the largest case for which it happens, as you can see from the Wikipedia page http://en.wikipedia.org/wiki/Dempwolff_group.

If you consider $SL_n$ rather than $GL_n$, there are more non-split extensions, for example $5^3 \cdot SL_3(5)$.

Answer by ndkrempel for Can the I-fold direct product be free?

2010-12-10T11:03:57Z

~~I believe it is also free for the p-adic integers $\mathbb{Z}_p$.~~

By restricting to the underlying additive group $G$ of the ring, you certainly require any Cartesian product of copies of $G$ to be isomorphic to some direct sum of copies of $G$, and this itself is an interesting question. For finitely generated abelian groups, I believe it holds if and only if the group has rank 0 (i.e. is torsion), this should follow easily from things you've mentioned already.

(Incidentally, in the world of non-abelian groups, I'm not sure if it holds for $Q_8$ or $D_8$.)

Answer by ndkrempel for More open problems

2010-12-09T00:21:39Z

Many PhD supervisors have lists of open problems in their subject, often hidden somewhere on their web site. Here are some from my university:

Here are 27 research problems in group theory from Rob Wilson: http://www.maths.qmul.ac.uk/~raw/resprob.html

Here are many problems in combinatorics and group theory from Peter Cameron: http://www.maths.qmul.ac.uk/~pjc/oldprobidx.html

(And also his links to other lists of problems: http://www.maths.qmul.ac.uk/~pjc/bcc/links.html#prob)

Answer by ndkrempel for How many finite simple groups of order $p+1$?

2010-12-08T13:58:20Z

The philosophical point here is that if all you know about a group $G$ is its order $\lvert G \rvert$, then by far the most relevant information is the prime factorization of that order. (Back when sporadic groups were still being discovered, there are anecdotes about phoning John Thompson with the order of your hypothetical new group, and after some calculations he would tell you whether it 'checked out' or not - and of course he would just be using the knowledge of which primes divided the order and to which exponents). So questions about the prime factorization of $\lvert G \rvert - 1$ are going to be dominated by the (generally unsolved) number theoretical problems that relate the prime factorization of $n$ and $n+1$, e.g. the existence of infinitely many Sophie Germain primes, Mersenne primes, or primes $p$ for which $\frac{p^2+1}{2}$ is also prime, etc.

Answer by ndkrempel for Why are this operator's primes the Sophie Germain primes?

2010-12-08T13:37:54Z

In answer to your first question:

As you hinted at, it simplifies things to make the change of variable $x \mapsto x+1$.

Then the product becomes $x \star y = \lceil\frac{xy+1}{2}\rceil$. And we want to find $z$ that can't be expresed as $x \star y$ where $x,y > 2$.

Well that's equivalent to $z$ such that you can't solve $2z=xy+1$ with $x,y>2$, and also you can't solve $2z-1=xy+1$ with $x,y>2$.

The first condition is equivalent to $2z-1$ being prime, since the oddness of $2z-1$ makes the constraint on $x$ and $y$ irrelevant.

The second condition is equivalent to $z-1$ being prime, since it's saying that $2z-2=2(z-1)$ has no non-trivial factorizations beyond the obvious two involving the factor $2$.

Hence overall, we see that $z$ prime in the new sense $\Leftrightarrow$ $z-1$ Sophie Germain prime. Changing variables back, we get the answer to the original question.

Answer by ndkrempel for Is there any way to check whether a group is residually solvable?

2010-12-08T13:09:59Z

This problem is undecidable. If it were not, you could use it to construct an algorithm for testing if a given f.p. group is trivial or not, which is well known to be undecidable:

Input: f.p. group G


Test if G is residually solvable.
If it is not, output "non-trivial".
If it is, find the abelianization of G.
If the abelianization is trivial, output "trivial".

Otherwise output "non-trivial".

Direct proof of special case of Hasse's theorem for elliptic curves

2010-12-02T04:48:29Z

Consider the elliptic curve $y^2 = x^3 + x$ over $\mathbb{F}_p$, where $p \equiv 1 \pmod 4$.

If memory serves correctly, the number of points (excluding the point at infinity) is $p - a$ where $a$ is the residue of the binomial coefficient $\binom{\frac{p-1}{2}}{\frac{p-1}{4}}$ modulo $p$ of smallest absolute value.

Therefore, Hasse's bound implies that $a \leq 2\sqrt{p}$, which for large $p$ is quite a strong statement about a number you might otherwise expect to be anything mod $p$.

My question is:

Is there a direct simple proof of this fact about $\binom{\frac{p-1}{2}}{\frac{p-1}{4}}$ being small mod $p$? Could one try to unwind the proof of Hasse's theorem or more generally a proof of the Riemann hypothesis for curves to get such a proof?

On a related sidenote: of course the $(\frac{p-1}{2})!$ occuring here is a primitive fourth root of unity. The other relevant term is $(\frac{p-1}{4})!$. This leaves me to wonder if there is any useful connection with the $p$-adic $\Gamma$ function evaluated at $\frac{1}{4}$, and hence with some kind of $p$-adic analogue of the Chowla-Selberg formula...? (I don't know anything about this, so I could be clutching at straws here.) If there is anything interesting to say about this part, I should perhaps make it a separate question.

Answer by ndkrempel for does this group have a name?

2010-12-03T01:38:55Z

The first two relations alone give a polycyclic group of Hirsch length 2 ($a^2$ is central, quotienting by it gives the infinite dihedral group $D_\infty$), which, thanks to Denis Osin's answer, is already the whole group. Even without that knowledge, it is still a quotient of this group, and so polycyclic of Hirsch length $\leq 2$. In particular, it is far too small to be the lamplighter.

Answer by ndkrempel for Can a problem be simultaneously polynomial time and undecidable?

2010-12-02T09:21:26Z

It seems to me there are two levels operating here.

For any given minor-closed class of graphs, there is some finite set of excluded minors, and hence there is a polynomial time algorithm for testing membership of that class (we don't need to explicity know what the algorithm is, we simply know it exists.)

However, on the level above, writing out that algorithm explicitly involves finding a finite set of excluded minors explicitly, and that might be hard/undecidable.

Answer by ndkrempel for Integers in a triangle, and differences

2010-12-01T21:10:11Z

For small values of $n$, there is a relatively small state space to search.

In the most naive way possible, I found the following (showing the top row of triangle only):

1: 1 way: [1]
2: 4 ways: [1,3], [2,3], [3,1], [3,2]
3: 8 ways: [1,6,4], [2,6,5], [4,1,6], [4,6,1], [5,2,6], [5,6,2], [6,1,4], [6,2,5]
4: 8 ways: [6,1,10,8], [6,10,1,8], [8,1,10,6], [8,3,10,9], [8,10,1,6], [8,10,3,9] [9,3,10,8], [9,10,3,8]
5: 2 ways: [6,14,15,3,13], [13,3,15,14,6]
6: no ways

In particular, it is possible for $n = 5$, but not possible for $n = 6$.

The computation for $n = 7$ seems entirely feasible, and I'm happy to carry it out.

Comment by ndkrempel

2011-10-07T23:58:07Z

This already exists as a game at least, there's a page about it on Sensei's Library for example (senseis.xmp.net)

Comment by ndkrempel

2011-10-07T23:53:57Z

I've been meaning to watch that movie for fun for quite a while now... might have to reconsider!

Comment by ndkrempel

2011-03-31T13:49:26Z

In fact, throwing away the off-axis points which are fixed by everything, the derived subgroup is the full finitary alternating group.

Comment by ndkrempel

2011-03-22T23:07:20Z

@Poove: Must be a problem at your end. I meant conditions on G. Another possible condition would be to require G to be torsion-free, I think that's enough for the result to hold... It would be helpful if you gave more details about your particular G, if possible.

Comment by ndkrempel

2011-03-22T19:57:22Z

I suspect you will need stronger assumptions on $G$, for example that any quotient of $G$ by one of its finite normal subgroups is Hopfian.

Comment by ndkrempel

2011-03-22T04:20:03Z

If a degree four hypersurface in $\mathbb{P}^3$ contains a line (and is irreducible and not rational), then it has an elliptic fibration (to $\mathbb{P}^1$) - consider the pencil of hyperplanes passing through that line.

Comment by ndkrempel

2011-03-22T03:38:37Z

Just some quick dimension counts: degree 4 hypersurfaces in $\mathbb{P}^3$ form a 34-dimensional (projective) variety. Such hypersurfaces containing a fixed line form a 29-dimensional subvariety. The Grassmannian $\mathrm{Gr}_{1,3}$ is 4-dimensional. Putting this together, the subvariety of such hypersurfaces which contain any line at all must have codimension at least $34 - (29 + 4) = 1$ (and probably exactly 1.) In particular, the generic such hypersurface contains no lines, and with some work you could find a polynomial in the coefficients which has to be satisfied to contain a line.

Comment by ndkrempel

2011-03-21T14:59:01Z

Certainly, this number is invariant within each double coset, and each number from $0$ to $k$ occurs (this is the bit that requires $k \leq n-k$). In the other direction, we can pick $e, (1,k+1), (1,k+1)(2,k+2), \ldots, (1,k+1)(2,k+2)(3,k+3)\ldots(k,2k)$ as our $k+1$ representatives, since given any $g \in G$ we can first permute $[1,k]$ such that the numbers sent to the $[k+1,n]$ range occur first, then we can permute the $[k+1,n]$ range so that the numbers coming from $[1,k]$ occur first and in the same order, then we can apply one of our representatives above to get an element lying in $H$.

Comment by ndkrempel

2011-03-21T14:54:21Z

Let $G = S_n$ act on $[1,n]$. We're considering the parabolic subgroup $H = S_k \times S_{n-k}$, wlog $k \leq \frac{n}{2}$, where the first summand acts on $[1,k]$ and the second on $[k+1,n]$ say. Now given any element $g \in G$, I claim that the $(H,H)$-double coset which $g$ lies in is completely determined by how many numbers in $[1,k]$ it sends to the $[k+1,n]$ range. ...

Comment by ndkrempel

2011-03-14T17:28:01Z

A minor improvement: any nilpotent group with this property is cyclic.

Comment by ndkrempel

2011-03-14T16:36:13Z

Surely the terminology was imported from the study of polyhedra/polytopes?

Comment by ndkrempel

2011-03-09T16:15:52Z

Yes, that's right.

Comment by ndkrempel

2011-03-09T00:24:16Z

Well, not exactly a normal form. But two words representing the same element both lead to some common word upon making a sequence of replacements of the forms $s_a s_a \mapsto 1$ and $s_a s_b s_a s_b s_a \dots \mapsto s_b s_a s_b s_a s_b \dots$. But since the words I used don't contain more than one of a given simple reflection, you can never make the first type of replacement (so in particular, they are minimum length representatives), and the second type of replacement merely changes the ordering. Hence they represent distinct elements of the Coxeter group.

Comment by ndkrempel

2011-03-08T19:16:28Z

@Dan: I think Daniel's referring to the typo $N_d$ on the RHS.

Comment by ndkrempel

2011-03-01T16:15:58Z

@Emil: You can say it must be divisible by either 8 or 12. (And Burnside went one step further: it must be divisible by 12, 16 or 56.)