User james - MathOverflow

Answer by James for Nucleus and center of certain non power associative algebras

2011-11-25T14:32:44Z

I think the following example works. Take an algebra $A$ (say, over $\mathbb{Z}$) with basis $\{ a, b, c \}$ and with products defined by putting $cb = c^2 = b$, and all other products of basis elements equal to $a$. Then $(cc)c = bc = a$, while $c(cc) = cb = c$, so $A$ is not power-associative and non-commutative. But the centre and nucleus are equal (to $\mathbb{Z}a$).

Answer by James for Computer algebra system for calculation of characteristic polynomial of sparse matrix

2011-10-24T20:50:21Z

In Maple 15 I'm getting times of about 12 seconds on decent, fairly recent hardware. I used

with( LinearAlgebra ):
N := 10^4:
A := RandomMatrix( N, N, 'generator' = 0 .. 1, 'density' = evalf( 1 / N ) ):
time( Modular:-CharacteristicPolynomial( 2, A, t ) );

for testing. The fact that it is sparse is important. Runtimes for dense examples were much, much longer.

EDIT: It seems that if you use a sparse matrix data structure, and smaller (one byte) integers, this can be done much more efficiently. If you have access to Maple 14 or 15, try this (and note that, here, $N = 10^5$):

with( LinearAlgebra ):
N := 10^5:
A := RandomMatrix( N, N, 'generator' = 0 .. 1, 'density' = evalf( 1 / N ), 'storage' = 'sparse', 'datatype' = 'integer'[1] ):
time( CharacteristicPolynomial( A, t ) mod 2 );

On my machine, I get the answer in less then 0.5 seconds. (It took longer - about 0.75 seconds - to construct the matrix!) Memory used was about 45.3 Mb, but going back to size $10^4\times 10^4$ reduces the memory to 2.7 Mb. I did examples with $N = 10^6$ in about 5 seconds and 220 Mb of memory.

Anyway, it's clear from the various answers that there are computer algebra systems out there that can handle the computations you are interested in (at least Maple and Fermat, and likely others), so you should be in a position to choose whichever system is most convenient for you.

Is there a residually nilpotent one-relator group that is not residually a finite p-group for any prime p?

2011-10-11T18:20:16Z

This question is not directly related to, but was inspired by, this question. We know that a finitely generated residually nilpotent group is residually of prime-power order. However, we may need to use different primes for different elements. Classes of groups for which residual nilpotence forces there to be a single prime that will do for all elements (i.e., for which the group in question must be residually $p$-finite, for some $p$) seem to be interesting, and include, for instance, free products of cyclic groups.

Is there a (non-cyclic) one-relator group that is residually nilpotent, but is not residually a finite $p$-group, for any prime number $p$?

Such a group must be torsion-free, with trivial centre.

Answer by James for Is the free product of arbitrarily many copies of `${\mathbb{Z}}$` and `${\mathbb{Z}}/2$` residually nilpotent?

2011-10-10T06:36:38Z

Mark Sapir has already given you a definitive answer, but I think it is interesting to note that his argument generalises to show something stronger. A finitely-generated non-trivial free product of groups is residually nilpotent only if it is $p^{\prime}$-torsion-free, for some prime $p$. (Here, $p^{\prime}$ denotes the set of primes not equal to $p$ so, in this case, we are allowed only $p$-torsion.) For, in a finitely-generated residually nilpotent group, elements of finite coprime order commute. And, if $G = A\ast B$ is such a free product (with $A\neq 1\neq B$), and $G$ is not $p^{\prime}$-torsion-free, for any prime $p$, there are distinct primes $p$ and $q$, and elements $u$, of order $p$, and $v$, of order $q$ in $G$. These may be taken (up to conjugation) to be members of $A\cup B$. Now, if $u$ and $v$ belong to different free factors ($A$ or $B$) then they cannot commute, so it must be that $u$ and $v$ belong to the same factor, say $A$. But then, taking a non-trivial element $b$ in $B$ and forming the conjugate $w = b^{-1}vb$, we get an element of order $q$ which again does not commute with $u$. (The commutator $[u,w] = u^{-1}b^{-1}v^{-1}bub^{-1}vb\neq 1$, by the normal form theorem for free products.) This again contradicts the fact that elements of coprime order commute.

Formally undecidable problems on finitely presented quandles

2011-08-31T14:39:15Z

In the literature, one sometimes sees the claim that finitely presented quandles (in particular, knot quandles) are "hard to deal with". Hence, a great deal of effort has gone into studying finite quandles and counting homomorphisms onto them, and so on. However, I have not yet come across any theorems that state formal undecidability results for finitely presented quandles similar to those for finitely presented groups. In fact, I have yet to see any formulation of such problems. (For instance, a theorem stating that the isomorphism problem is undecidable for finitely presented quandles.)

Do such results exist in the literature and, if so, could someone please provide references?

(Asked previously here on math.stackexchange, without response.)

Do the Baumslag-Solitar groups occur in nature?

2010-03-16T18:53:51Z

The Baumslag-Solitar groups $BS(m,n) = \langle b,s\mid s^{-1}b^ms = b^n\rangle$, with $mn\neq 0$, are important examples (more often, counter-examples) in group theory. They are residually finite if, and only if, either $m$ and $n$ are equal in absolute value, or one of $m$ and $n$ has absolute value equal to $1$. In that case, they are Hopfian, and also when $m$ and $n$ have the same prime divisors. Otherwise, they are non-Hopfian. For $m=n$, we get examples of one-relator groups with non-trivial center. The group $BS(2,2)$ is an example in which the Howson property fails.

I can only recall having seen these groups defined by means of a presentation. I would like to know whether these groups (apart from the obvious special cases such as the metabelian ones) can be realized by some other fairly elementary and concrete mechanism. My question is:

Does $BS(m,n)$ occur "in nature"?

(For example, the Sanov matrices $\left(\begin{matrix} 1&2 \cr 0&1 \end{matrix}\right)$ and $\left(\begin{matrix} 1&0 \cr 2&1\end{matrix}\right)$ generate a free subgroup of $SL(2,\mathbb{Z})$, so I would say that free groups occur "in nature".)

Obviously, since the Baumslag-Solitar groups are often non-Hopfian, they cannot be constructed as groups of matrices. But, perhaps there is some other concrete realization of these groups.

If there isn't a general construction, it would still be useful to get a concrete realization for the non-Hopfian group $BS(2,3)$.

Answer by James for Torsion in triangle groups

2011-07-22T15:32:33Z

According to the survey article H. Zieschang, On Triangle Groups, Russian Mathematical Surveys (October 1976), 31 (5), pg. 226-233, this fact is proved in the Russian paper, H. Zieschang, “Discrete groups of plane motions and plane group images”, Uspekhi Mat. Nauk, 21:3(129) (1966), 195–212. I've been unable to locate an English translation of the latter. However, Fine and Rosenberger discuss it in Chapter 4 of their book (see Theorem 4.3.2).

Answer by James for Lie algabra of symmetric group

2011-04-12T21:04:52Z

For a well-known infinite example, there is a result, due to Labute ("On the descending central series of groups with a single defining relation", J. Algebra 14 (1970), 16--23) which asserts that the Lie ring associated to a one-relator group can be presented as a Lie ring with a single defining relator.

Answer by James for Elementary+Short+Useful

2011-04-04T20:41:52Z

The Pigeonhole Principle

Answer by James for Most memorable titles

2010-11-01T02:08:06Z

John Stallings' "How not to prove the Poincare Conjecture" is lovely.

Answer by James for Most memorable titles

2010-10-31T20:32:44Z

My favourite : "My Graph", by H.S.M. Coxeter.

Answer by James for What are some examples of colorful language in serious mathematics papers?

2010-09-15T21:40:37Z

I like the following footnote that appears in a paper by G. Baumslag:

"I thank Graham Higman for allowing the dust of Oxford to rest on my unopened manuscript for thirty months."

Answer by James for Fundamental Examples

2009-11-13T23:58:05Z

Answered by James: The Platonic solids. They are fundamental, collectively and individually, to many areas of mathematics.

Answer by James for Is there an image for you that epitomizes mathematics?

2009-11-03T22:31:30Z

Raphael's School of Athens

Answer by James for Quick proofs of hard theorems

2010-05-17T13:56:21Z

The Nielsen-Schreier subgroup theorem: subgroups of free groups are free. This has a very quick proof using the fact that a group is free precisely when it acts freely and without inversions on a tree.

Answer by James for What are examples of mathematical concepts named after the wrong people? (Stigler's law)

2010-05-10T20:14:11Z

Burnside's Lemma, which asserts that the number of orbits of a group action is the average number of fixed points, was known to Cauchy. Burnside himself even attributed it to Frobenius in his book.

Is a non-abelian free group fully residually a finite non-abelian simple group?

2010-05-07T21:12:19Z

It is well known that a non-abelian free group is residually a finite simple group. Katz and Magnus proved, in fact, that non-abelian free groups are residually alternating and residually $PSL_{2}$. S. J. Pride has some nice results along these lines as well. The best result that I know of is the theorem of Weigel that can be formulated as follows. If $\mathfrak{X}$ is a group-theoretic class containing an infinite set of pairwise non-isomorphic finite non-abelian simple groups, then every non-abelian free group is residually an $\mathfrak{X}$-group.

My question is this:

Is a non-abelian free group fully residually a finite non-abelian simple group?

It seems likely that the answer to such an obvious question is known, but I have not been able to find it in the literature.

I should probably add that I suspect we can probably replace "finite non-abelian simple" with "alternating", but I haven't yet given any thought to the other infinite series. I'd like to learn whether anything is known before spending more time on this.

Answer by James for Where on the internet I can find database of graphs?

2010-05-07T20:19:59Z

Maple 13 or newer has a GraphTheory package that has a graph generator which allows you to generate all non-isomorphic graphs satisfying various criteria. You can use that to produce graphs and export them in various formats. In addition, you can produce random graphs using this package.

Answer by James for Which mathematicians have influenced you the most?

2010-03-29T16:51:16Z

Who: H. S. M. Coxeter.

When: When I was an undergraduate.

Why: Not only was he a prince among mathematicians, but he was also a gentleman of the first rank. Several of his books also inspired me. Moreover, by transitivity, he was (for me) clearly the most influential.

Answer by James for Dimension Leaps

2010-03-19T02:54:09Z

Polya's theorem on random walks: a simple random walk on $\mathbb{Z}^n$ is recurrent for $n = 1$ and $n = 2$, but is transient for $n \geq 3$.

Answer by James for does every right-angled coxeter group have a right-angled artin group as a subgroup of finite index?

2010-03-18T14:57:38Z

You might be thinking of this paper:

Michael W. Davis and Tadeusz Januszkiewicz, Right-angled Artin groups are commensurable with right-angled Coxeter groups, J. Pure Applied Algebra, 153, No. 3 (2000), 229-235.

Answer by James for Is there a non-trivial topological group structure of $\mathbb{Z}$?

2010-03-16T22:25:57Z

Yes. Take, for example, the subgroups $p^k\mathbb{Z}$, for $k>0$ and a fixed prime $p$, as a basis of neighborhoods of the identity.

Answer by James for Math keyboard: does it exist ?

2010-02-17T19:21:27Z

Does an APL keyboard (e.g., http://www.aplusdev.org/keyboard.html) qualify?

Answer by James for "Algebraic" topologies like the Zariski topology?

2010-02-05T23:01:20Z

Given a group theoretic class $\mathfrak{X}$ (e.g., finite groups, soluble groups, etc.), to each group $G$ one can associate the pro-$\mathfrak{X}$ topology on $G$ by taking as a basis of neighbourhoods of the identity the collection of normal subgroups $N$ of $G$ for which the quotient group $G/N$ belongs to $\mathfrak{X}$. A group is residually an $\mathfrak{X}$-group precisely when this topology is Hausdorff. (To get an actual topology, $\mathfrak{X}$ has to be hereditary and closed under (finite) direct products.)

Answer by James for Computer Algebra Errors

2010-01-12T20:16:06Z

(I haven't sufficient points to post a comment to Leonid Kovalev's reply.)

The problem in the numerical integration example is that numerical integration in Maple is done using Int, not int. The correct command should be

evalf(Int(sin(x)^44,x=0..sqrt(44)));

which should produce consistent results (and much more quickly).

Answer by James for Famous mathematical quotes

2009-12-09T22:59:40Z

"Why is this a good idea?"

Bill Ralph, on the most important question to ask yourself when doing (or studying) mathematics.

Answer by James for Cocktail party math

2009-11-14T00:08:18Z

I have successfully used examples involving covering chessboards with dominoes. I start with the question about whether you can tile a chessboard with opposite corner squares removed. If this gets any interest, I might go on from there. This leads people to the idea that mathematics is not just about numbers, but is actually about thinking logically about pretty much anything.

Answer by James for Dimension Leaps

2009-11-13T23:24:07Z

The symmetric group has an outer automorphism only in degree 6.

Answer by James for Infinite subgroups with finite index

2009-11-03T17:52:29Z

I often try to show that a subgroup contains another subgroup known to be of finite index. There are various refinements. One technique is to prove that your subgroup contains an intersection of a finite number of subgroups, each of which is known to have finite index. For example, suppose you know that the central quotient G/Z(G) of a group G is finite. (One way to show this is to show that G is a union of finitely many abelian subgroups.) If it is too hard to show that your subgroup H contains the centre, but you can show that H contains the intersection of Z(G) with the derived subgroup [G,G] of G, then the index of H in G is finite.

Another idea is to try to show that (e.g.) every nilpotent quotient of your group is finite, and then show that your subgroup must contain some term of the lower central series. (You could replace nilpotent with soluble and the LCS with the derived series, and so on.)

This may not count as a general method; perhaps it is more of a "trick", but I've seen it used to good effect in proving some commutativity theorems for groups and rings. If you can show that your subgroup is a union of (at most) two subgroups known to have finite index, then you are done.

Answer by James for Examples of great mathematical writing

2009-11-03T18:22:36Z

The book "Linear Algebra" by Greub; I've always thought his writing here was gorgeous, if a bit Spartan.
Most of John Stillwell's books.

Comment by James

2011-11-08T16:14:24Z

Perhaps you already know this, but Gerhard Rosenberger has done a lot of work in this area, so you might find something of use among his papers.

Comment by James

2011-10-27T21:49:04Z

In all fairness, "primality radius" and $ord_C(n)$ were defined in the linked question.

Comment by James

2011-10-25T05:02:58Z

@rhlewis As shown, I used a randomly generated matrix with density about 1/N, so there were, in fact, some zero rows, as well as some rows with 1 or 2 ones, and one row with 3 ones (based on a handful of random samples I looked at). If I change the density to 2/N, the runtime goes up to about 22 seconds. I just now tried a random permutation matrix as well, and got a runtime of about 5 minutes. That seems to make sense, as there are no zero rows to cut down the work. I used a 64-bit Linux machine with 8 Gb of memory.

Comment by James

2011-10-11T22:56:46Z

Wait a second, your group is not residually nilpotent? (See my answer to Colin Tan's question.) Since $\langle a,b\mid a^{6}=1\rangle$ is finitely generated, if it is residually nilpotent, then it is residually a finite nilpotent group. Consider the commutator $w = [u,v]$, where $u = a^{2}$ and $v = b^{-1}a^{3}b$. Then $u$ has order 3 and $v$ has order 2, and $w$ is non-trivial. So there is a finite nilpotent group in which $w$ has non-trivial image. But then so too do $u$ and $v$ and their images have relatively prime orders, so they must commute, a contradiction. Am I missing something?

Comment by James

2011-10-11T21:33:51Z

Yes, of course, you are right. I had meant to (but didn't) exclude this case. What I really want is that all the generators occur in the relator, so that the question doesn't fail for obvious reasons. I'll accept this answer and try re-posting with a more careful formulation of the problem. Thanks.

Comment by James

2010-10-31T20:34:50Z

+1. This also brings to mind "Generatingfunctionology", which is itself pretty memorable.

Comment by James

2010-05-26T20:54:14Z

The last I heard (2009) this was unknown even for residually finite groups. (The question in this form is due to M.I. Kargapolov in the Kourovka notebook.)

Comment by James

2010-05-19T15:25:46Z

An example of a group defined by an intrinsic property is a free group defined by the universal mapping property. Actually, any group defined by means of a universal mapping property might work here. I was hesitant to offer this as an answer, because one then has the obligation to construct the beast. At that point, we get into the calculus of words and, in order to get associativity, the first thing you want to do is ...

Comment by James

2010-05-18T20:12:00Z

It seems to me that every group arises with an action, via Cayley's Theorem, regardless of how it might be defined.

Comment by James

2010-05-07T22:53:25Z

Ooh, very nice! It had not occurred to me to think about the stronger result you proved. Thanks!

Comment by James

2010-03-19T03:18:48Z

I had always heard the convention originated in the calculus of permutations. If one writes permutations to the right of their arguments, then the action of the permutation follows the natural way to multiply them. I.e., $(fg)(x) = g(f(x))$, while $x(fg) = (xf)g$. Of course, one can get around that by writing the permutation as a superscript, which is also a "right action".