September 2003 - mathfun@mailman.xmission.com

[math-fun] sigma/partition
by Jon Perry 24 Sep '03

24 Sep '03

From; http://www.research.att.com/projects/OEIS?Anum=A000203 we have; sigma(n) = n*P(n) - sum{i=1,n-1,a(i)*P(n-i)} , where P(n)=A000041(n) Examining sigma(n)-sigma(n-1), we find a few nice algebraic drop-outs, and end with; sigma(n)=n[P(n)-P(n-1)] + sigma(n-2) - sum{i=1,n-3,P(n-i-1)*[sigma(i+1)-sigma(i)]} which is just as useless as before, however the use of the differences is interesting... Jon Perry perry(a)globalnet.co.uk http://www.users.globalnet.co.uk/~perry/maths/ http://www.users.globalnet.co.uk/~perry/DIVMenu/ BrainBench MVP for HTML and JavaScript http://www.brainbench.com

1 0

Re: [math-fun] distinguishing groups
by Marc LeBrun 23 Sep '03

23 Sep '03

>=Richard Schroeppel > For finite groups, I can check isomorphism in time roughly N^(log2(N)). How's that? If you're given the groups in some reasonable form how can it take more than the N^2 required to completely compare them element-wise? Perhaps this time includes making the inputs presentable? By reasonable form I mean something like, say, labeling the elements / permuting the rows & columns so that some linear scan (for example row-major 1,1 ... 1,N ... N,N) is lexicographically minimized. For instance the two groups 1 2 3 4 1 2 3 4 2 3 4 1 and 2 1 4 3 3 4 1 2 3 4 1 2 4 1 2 3 4 3 2 1 (Z4 and A4?) might become 1 2 3 4 2 3 4 1 3 4 1 2 4 1 2 3 and ^ 1 2 3 4 2 1 4 3 3 4 1 2 4 3 2 1 ^ first differing ^ at the 2,2 = 6th element. Actually of course the first row and column belong to the identity element, so here the first difference must occur at N+2 or later, and the constraints of the group structure certainly requires it to occur sometime before N^2. (This raises the question of what the minimum and maximum are for a given N, and what scan order (row-major? anti-diagonal?) optimizes them.) In any case, if you can characterize a set of specific elements which are sufficient to distinguish groups pair-wise then you could certainly construct such a detector out of element-wise differences. Perhaps, like an error-detecting code checksum, it might even be a fairly efficient one. Admittedly compared to the "pretty fancy concepts" this may be an ugly concrete way to do the job (but then isn't one of your mottos "Nice algorithms finish last!"?<;-)

1 0

[math-fun] uniquely factored groups
by Richard Schroeppel 23 Sep '03

23 Sep '03

JHC> The only candidate for an isomorphism that these invariants leave is between 2xQ8 and 4 :^3 4, which is prohibited by the unique factorisation theorem for direct products, since it's easy to see that the latter of these two isn't a non-trivial direct product. John, could you state precisely the unique factorization theorem? I've never seen it written down. There seem to be some subtleties, such as checking that AxB = AxC implies B=C. (For groups, of course, we interpret "=" as isomorphism.) Is it also true for infinite groups? Rich

3 2

Re: [math-fun] non-square products of squares?
by Dan Hoey 23 Sep '03

23 Sep '03

John Conway writes: > Let me ask for the smallest group in which two squares can > multiply to a non-square.... It's nice to see this. I was going to look with Gap, and your analysis helped convince me. > Therefore, the smallest groups in which squares can multiply to > a non-square are A4 and Q12; indeed, they are the only such > groups with order < 16 (and probably the only ones with order < 20, > since I don't believe there will be any of order 16). I found two such groups of order 16, but I haven't figured out what their names are. A presentation for the first is <a,b : a^2 = b^4 = (b a b)^2 = (b^-1 a b a)^2 = 1> . Its squares are 1, b^2, and (a b)^2, and the product of the last two is not a square. The other group may be presented <a,b : a^4 = b^4 = a b a^-1 b = 1>. Its squares are 1, a^2, b^2, and again the product of the two non-identity squares is not a square. > A much harder and more interesting problem is: what's the > largest probability we can attain? The largest among groups up to order 255 is 5/6, in a 192-element group. Gap calls it SmallGroup([192,1022]), but again I don't know a name for it. The smallest presentation I've found is <a,b,c : a^3 = b^4 = c^4 = [b,c] = [a,b^2] = [a,c^2] = (a c)^3 = (a b)^3 = [c,a^-1 b^-1 a] = 1> where [x,y] means x y x^-1 y^-1. This is edged out by probability 27/32, in SmallGroup([384,572]), which I haven't looked at in detail. Dan

4 12

Re: [math-fun] non-square products of squares?
by Dan Hoey 23 Sep '03

23 Sep '03

John Conway writes: > Exactly what are these the probabilities of? I was using > the probability that a given triple a,b,ab should be of form > square,square,nonsquare. Are yours the conditional probability > that ab should be a non-square GIVEN that a,b are squares? > [I mention that there is a third natural probability around, > namely the probability that a^2.b^2 should be a nonsquare.] I see! I first calculated the second probability, and saw that it wasn't what you were describing. Also, the denominators aren't as pretty, because they reflect the somewhat flukey number of squares. So I switched to the third, and since it agreed with your number (1/6) for A4 (and since I overlooked the 1/36 you got for Q12) I thought that was what you meant. So the numbers I reported were the probability that aabb is a nonsquare. Looking at the first probability I see it can't exceed min(s^2,1-s) where s is the density of squares--that's at most tau^-2 ~ .382, and it's even less because not every product of squares can be a nonsquare. Up to order 255, the only group that exceeds 1/6 is SmallGroup(48,50), or <a,b,c : a^3 = b^2 = c^2 = (a b)^3 = (a c)^3 = (b c)^2 = (a b a^-1 c)^2 = 1> . It has a probability of 5/24 that a,b,ab are square,square,nonsquare. Dan

1 0

[math-fun] Groups of small degree (was order 16)
by MCKAY john 23 Sep '03

23 Sep '03

I cannot let the opportunity pass to remind an author of the paper Conway, Hulpke, & McKay - On transitive permutation groups - in J. Mathematics and Computation Vol 1 first paper (1996) of hid work. It contains much useful information including a naming scheme. John McKay

1 0

Re: [math-fun] non-square products of squares?
by MCKAY＠vax2.concordia.ca 23 Sep '03

23 Sep '03

From: IN%"math-fun(a)mailman.xmission.com" "math-fun" 23-SEP-2003 12:28:46.98 Received: from clyde.concordia.ca (clyde.Concordia.CA [132.205.1.1]) by vax2.concordia.ca (PMDF V6.2 #30759) with ESMTP id <01L105NGXJ4Q006D64(a)vax2.concordia.ca> for mckay(a)vax2.concordia.ca (ORCPT mckay(a)vax2.concordia.ca) Tue, 23 Sep 2003 12:28:46 -0400 (EDT) Received: from mailman.xmission.com (mailman.xmission.com [198.60.22.29]) by clyde.concordia.ca (8.12.10/8.12.10) with ESMTP id h8NGSak9449440 for <mckay(a)vax2.concordia.ca>; Tue, 23 Sep 2003 12:28:36 -0400 (EDT) Received: from localhost ([127.0.0.1] helo=mailman.xmission.com) by mailman.xmission.com with esmtp (Exim 3.35 #1 (Debian)) id 1A1q1b-0003se-03; Tue, 23 Sep 2003 10:28:27 -0600 Received: from mail.math.princeton.edu ([128.112.18.14]) by mailman.xmission.com with esmtp (Exim 3.35 #1 (Debian)) id 1A1q1Z-0003sL-00 for <math-fun(a)mailman.xmission.com>; Tue, 23 Sep 2003 10:28:25 -0600 Received: from localhost.localdomain (fine318b.math.princeton.edu [128.112.16.36])h8NGRrNs017817verify=NOT); Tue, 23 Sep 2003 12:27:53 -0400 Received: from fine318b.math.Princeton.EDU (localhost.localdomain [127.0.0.1]) h8NGRrnS007185; Tue, 23 Sep 2003 12:27:53 -0400 Received: from localhost (conway@localhost)h8NGRrfr007181; Tue, 23 Sep 2003 12:27:53 -0400 Date: Tue, 23 Sep 2003 12:27:53 -0400 (EDT) From: John Conway <conway(a)Math.Princeton.EDU> Subject: Re: [math-fun] non-square products of squares? In-reply-to: <Pine.LNX.4.44.0309231039460.5413-100000(a)fine318b.math.Princeton.EDU> Sender: math-fun-bounces(a)mailman.xmission.com To: math-fun <math-fun(a)mailman.xmission.com> Cc: Marc LeBrun <mlb(a)fxpt.com> Errors-to: math-fun-bounces(a)mailman.xmission.com Reply-to: math-fun <math-fun(a)mailman.xmission.com> Message-id: <Pine.LNX.4.44.0309231209450.6960-100000(a)fine318b.math.Princeton.EDU> MIME-version: 1.0 Content-type: TEXT/PLAIN; charset=US-ASCII Precedence: list X-BeenThere: math-fun(a)mailman.xmission.com X-Mailman-Version: 2.1.1 X-Scanned-By: MIMEDefang 2.35 List-Post: <mailto:math-fun@mailman.xmission.com> List-Subscribe: <http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun>, <mailto:math-fun-request@mailman.xmission.com?subject=subscribe> List-Unsubscribe: <http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun>, <mailto:math-fun-request@mailman.xmission.com?subject=unsubscribe> List-Archive: <http://mailman.xmission.com/cgi-bin/mailman/private/math-fun> List-Help: <mailto:math-fun-request@mailman.xmission.com?subject=help> List-Id: math-fun <math-fun.mailman.xmission.com> Original-recipient: rfc822;mckay(a)vax2.concordia.ca On Tue, 23 Sep 2003, John Conway wrote: > On Mon, 22 Sep 2003, Dan Hoey wrote: > > I found two such groups of order 16, but I haven't figured out what > > their names are. A presentation for the first is > > > > <a,b : a^2 = b^4 = (b a b)^2 = (b^-1 a b a)^2 = 1> . > > > > Its squares are 1, b^2, and (a b)^2, and the product of the last two is > > not a square. > > I don't immediately recognise this group in that presentation. > I'll play with it offline to see which one it is. I've now done so. As I expected, it's what I think of as "the last group" of order 16, which Coxeter calls (4,4|2,2) (except that I may have the wrong style of bracket or punctuation): 1 = a^4 = b^4 = (ab)^2 = (a^-1.b)^2. [This is more symmetrical than the presentation you give - my a can be taken as your ab.] The elements can be written a^i.b^j, and exactly half of them (those for which i+j is odd) have order 4. They are of two "sexes" according as i is odd and j even or i even and j odd, and any two elements of opposite sexes generate the group in the above presentation. The square of an element of order 4 is a^2 or b^2, depending only on its sex, so of course it's an example. [I remark that a^2 and b^2 generate the center.] > > The other group may be presented <a,b : a^4 = b^4 = a b a^-1 b = 1>. > > > > Its squares are 1, a^2, b^2, and again the product of the two > > non-identity squares is not a square. > > This group is called 4:4 in my system. [In general, A:B > denotes the split extension of a group of structure A by one > of structure B, and it is usually assumed that it's not the direct > product, since we'd call that A x B.] This group is much easier to think about, since it's that split extension. The square of a^i.b^j is a^(2i) if j is even, and b^2 if j is odd, so superficially it looks very like the other (in the new presentation) in respect of this behavior, though this time there's no symmetry between a and b. When I guessed there wouldn't be examples of order 16, I planned to check (4,4|2,2) just in case, because it's the most interesting one, but forgot. [I "learned" the groups of order 16 by heart long ago, though now I may be a bit shaky. The standard reference for them is a table in the back of Coxeter and Moser, but they describe them in ways that don't tell you the structure, so it's better to use ATLAS-type notations that do.] John Conway _______________________________________________ math-fun mailing list math-fun(a)mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun

1 0

[math-fun] groups of order 16
by Richard Schroeppel 23 Sep '03

23 Sep '03

JHC> [I'm a little bit scared that maybe I've missed one out and two of the above are isomorphic, but I don't think so.] My memory is that most of the order sixteen groups can be distinguished by looking at the spectrum of element orders, but there are one or two pairs that have the same spectrum and require additional properties to split. Specturm of element orders: for Z16, there is 1 element of order 1, 1 of order 2, 2 of order 4, 4 of order 8, 8 of order 16. [1 1 2 4 8]. Rich rcs(a)cs.arizona.edu

1 0

FW: [math-fun] Fax from "The Simpsons" TV show
by Schroeppel, Richard 22 Sep '03

22 Sep '03

More of a finger, really. --Rich -----Original Message----- From: David H Bailey To: 'math-fun' Sent: 9/22/2003 9:03 AM Subject: [math-fun] Fax from "The Simpsons" TV show I meant to say "I myself had a hand in the script for one episode of The Simpsons show...." DHB -----Original Message----- I confess that I myself had a in the script for one episode of the Simpsons show. On the 6 May 1993 episode is this line: Apu: In fact I can recite pi to 40,000 places. The last digit is one! The Simpson show writers got this digit from me. See this fax: http://crd.lbl.gov/~dhbailey/expmath/simpson-pi.pdf David H. Bailey david(a)dhbailey.com _______________________________________________ math-fun mailing list math-fun(a)mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun _______________________________________________ math-fun mailing list math-fun(a)mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun

1 0

[math-fun] Fax from "The Simpsons" TV show
by David H Bailey 22 Sep '03

22 Sep '03

I confess that I myself had a in the script for one episode of the Simpsons show. On the 6 May 1993 episode is this line: Apu: In fact I can recite pi to 40,000 places. The last digit is one! The Simpson show writers got this digit from me. See this fax: http://crd.lbl.gov/~dhbailey/expmath/simpson-pi.pdf David H. Bailey david(a)dhbailey.com

1 1