From eunetde!faraday.clas.virginia.edu!gmm8n Thu Aug 15 13:03:42 1996 Return-Path: eunetde!faraday.clas.virginia.edu!gmm8n Received: from eunetde.UUCP (root@localhost) by eddie (8.6.11/8.6.11) with UUCP id MAA01265 for lh-systems.de!sillke; Thu, 15 Aug 1996 12:59:11 +0200 Received: by mail.Frankfurt.Germany.EU.net with ESMTP (8.6.5:29/EUnetPoP-1.1.9) via EUnet id JAA16654; Thu, 15 Aug 1996 09:18:11 +0200 Received: by mail.Germany.EU.net with ESMTP (5.59:24/EUnetD-2.5.4.c) via EUnet id JAA18092; Thu, 15 Aug 1996 09:19:42 +0200 Received: from optima.cs.arizona.edu by crash.Mathematik.Uni-Bielefeld.DE id JAA21551; Thu, 15 Aug 1996 09:19:23 +0200 Received: from cheltenham.cs.arizona.edu by optima.cs.arizona.edu (5.65c/15) via SMTP id AA02939; Thu, 15 Aug 1996 00:06:40 MST Received: from optima.CS.Arizona.EDU by cheltenham.cs.arizona.edu; Thu, 15 Aug 1996 00:07:59 MST Received: from virginia.edu by optima.cs.arizona.edu (5.65c/15) via SMTP id AA02928; Thu, 15 Aug 1996 00:06:20 MST Received: from faraday.clas.virginia.edu by mail.virginia.edu id aa11427; 15 Aug 96 1:19 EDT Received: from localhost (gmm8n@localhost) by faraday.clas.Virginia.EDU (8.7.5/8.6.6) with SMTP id BAA83578; Thu, 15 Aug 1996 01:19:41 -0400 Date: Thu, 15 Aug 1996 01:19:40 -0400 (EDT) From: "Gary M. Mcguire" Reply-To: "Gary M. Mcguire" To: Dan Hoey Cc: math-fun@cs.arizona.edu Subject: Re: Seven point seven line abstract geometric thing In-Reply-To: <9608142137.AA04847@sun13.aic.nrl.navy.mil> Message-Id: Mime-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Status: RO On Wed, 14 Aug 1996, Dan Hoey wrote: > What's this combinatorial object called? There are seven points, and > seven lines (where one of the lines is drawn as a triangle). > > (*) > /:\ > / : \ > / : \ > / : \ > /....:....\ > (*) : (*) > /: `-. : .-' :\ > / : (*) : \ > / :-' : `-: \ > / .-' : : : `-. \ > /.-' : : : `-.\ > (*)---------(*)---------(*) > > The geometric significance is that any two lines determine a point and > any two points determine a line. Nice picture! It is a projective plane of order 2, also known as the Fano plane. A projective plane of order n is a set of n^2+n+1 points, with the same number of lines, with the properties that any two points determine a line, any two lines determine a point, every point has n+1 lines on it and every line contains n+1 points. (Some of these properties are redundant.) Projective planes of order n are known to exist when n is a prime power, and a BIG question (one of the biggest in combinatorics) is whether any PPs exist of non prime-power order. Order 6 is fairly easy to rule out but order 10 was ruled out in 1989 only by massive computer calculations on top of some mathematics. I don't think anyone has any clue about order 12. (The remarkable Bruck-Ryser-Chowla theorem says if that a PP of order n exists, and n=1 or 2 (mod 4), then n is the sum of two squares. So this rules out n=6.) See American Mathematical Monthly, April 1991, an article by Lam for more on the n=10 case. The Fano plane is an example of lots of different things though. As you are suggesting, it can be viewed as (well, it is) an example of a Steiner system, or more generally a t-design. A Steiner system is a set X of v points, and a collection of subsets of X of size k, called blocks, such that any t points of X are in exactly one of the blocks. (For a PP, v=n^2+n+1, k=n+1, t=2, block=line) Nobody can find a Steiner system with t>5. > > I've found symmetric matrices for the incidence relation. Some are > almost symmetric along two diagonals, like > > 1 0 0 0 1 1 0 > 0 1 0 0 1 0 1 > 0 0 0 1 0 1 1 > 0 0 1 1 1 0 0 > 1 1 0 1 0 0 0 > 1 0 1 0 0 0 1 > 0 1 1 0 0 1 0 > > This is a special case of another kind of object. Is it some kind of > balanced block design? > > Dan > Symmetric incidence matrices are of interest...(geometers talk of absolute points and absolute blocks of a polarity). But beware: a so-called "symmetric design" is not a design with a symmetric incidence matrix. (A symmetric design by definition has the same number of blocks as points (for example a projective plane), bad terminology but too late to change maybe.) By the way, the binary code generated by the rows of your matrix is the Hamming code of length 7. Also, if you border with a row and column of 1's and change 0 to -1, you have a Hadamard matrix of size 8. -Gary McGuire From eunetde!faraday.clas.virginia.edu!gmm8n Thu Aug 15 22:58:45 1996 Return-Path: eunetde!faraday.clas.virginia.edu!gmm8n Received: from eunetde.UUCP (root@localhost) by eddie (8.6.11/8.6.11) with UUCP id WAA02693 for lh-systems.de!sillke; Thu, 15 Aug 1996 22:57:15 +0200 Received: by mail.Frankfurt.Germany.EU.net with ESMTP (8.6.5:29/EUnetPoP-1.1.9) via EUnet id WAA21211; Thu, 15 Aug 1996 22:03:44 +0200 Received: by mail.Germany.EU.net with ESMTP (5.59:24/EUnetD-2.5.4.c) via EUnet id WAA12424; Thu, 15 Aug 1996 22:05:07 +0200 Received: from optima.cs.arizona.edu by crash.Mathematik.Uni-Bielefeld.DE id WAA23980; Thu, 15 Aug 1996 22:04:53 +0200 Received: from cheltenham.cs.arizona.edu by optima.cs.arizona.edu (5.65c/15) via SMTP id AA13545; Thu, 15 Aug 1996 12:56:23 MST Received: from optima.CS.Arizona.EDU by cheltenham.cs.arizona.edu; Thu, 15 Aug 1996 12:57:52 MST Received: from virginia.edu by optima.cs.arizona.edu (5.65c/15) via SMTP id AA13537; Thu, 15 Aug 1996 12:56:12 MST Received: from faraday.clas.virginia.edu by mail.virginia.edu id aa00648; 15 Aug 96 15:56 EDT Received: from localhost (gmm8n@localhost) by faraday.clas.Virginia.EDU (8.7.5/8.6.6) with SMTP id PAA98734 for ; Thu, 15 Aug 1996 15:56:44 -0400 Date: Thu, 15 Aug 1996 15:56:43 -0400 (EDT) From: "Gary M. Mcguire" Reply-To: "Gary M. Mcguire" To: math-fun@cs.arizona.edu Subject: Fano Plane Message-Id: Mime-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Status: RO Another cute application of the Fano plane (below) is to guarantee a match two ticket in the Transylvania lottery: > (*)1 > /:\ > / : \ > / : \ > / : \ > /....:....\ > 6(*) : (*)2 > /: `-. :7.-' :\ > / : (*) : \ > / :-' : `-: \ > / .-' : : : `-. \ > /.-' : : : `-.\ > 5(*)---------(*)---------(*)3 > 4 The Translyvania lottery picks three numbers from the integers 1-14. Using two Fano planes we can guarantee to match two by playing just 14 times. Label the vertices of one Fano plane by the integers 1-7, the other plane by the integers 8-14. The 14 tickets to play are the 14 lines of the two planes. Then if (a,b,c) is the winning ticket, at least two of a,b,c are either in the interval [1,7] or [8,14]. These two numbers are on exactly one line of the corresponding plane, so one of our tickets matches them. -Gary McGuire From eunetde!math.berkeley.edu!asimov Thu Aug 15 22:58:44 1996 Return-Path: eunetde!math.berkeley.edu!asimov Received: from eunetde.UUCP (root@localhost) by eddie (8.6.11/8.6.11) with UUCP id WAA02695 for lh-systems.de!sillke; Thu, 15 Aug 1996 22:57:17 +0200 Received: by mail.Frankfurt.Germany.EU.net with ESMTP (8.6.5:29/EUnetPoP-1.1.9) via EUnet id WAA21572; Thu, 15 Aug 1996 22:54:46 +0200 Received: by mail.Germany.EU.net with ESMTP (5.59:24/EUnetD-2.5.4.c) via EUnet id WAA15743; Thu, 15 Aug 1996 22:56:18 +0200 Received: from optima.cs.arizona.edu by crash.Mathematik.Uni-Bielefeld.DE id WAA24103; Thu, 15 Aug 1996 22:56:15 +0200 Received: from cheltenham.cs.arizona.edu by optima.cs.arizona.edu (5.65c/15) via SMTP id AA14520; Thu, 15 Aug 1996 13:47:36 MST Received: from optima.CS.Arizona.EDU by cheltenham.cs.arizona.edu; Thu, 15 Aug 1996 13:49:05 MST Received: from math.berkeley.edu by optima.cs.arizona.edu (5.65c/15) via SMTP id AA14506; Thu, 15 Aug 1996 13:47:25 MST Received: from seastar.berkeley.edu by math.berkeley.edu (8.7.5/1.33(math)Ow.2) id NAA02311; Thu, 15 Aug 1996 13:49:00 -0700 (PDT) From: asimov@math.berkeley.edu (imovDaniel Asimov) Received: (asimov@localhost) by seastar.berkeley.edu (8.7.5/8.6.4) id NAA09687; Thu, 15 Aug 1996 13:48:53 -0700 (PDT) Date: Thu, 15 Aug 1996 13:48:53 -0700 (PDT) Message-Id: <199608152048.NAA09687@seastar.berkeley.edu> To: Hoey@AIC.NRL.Navy.Mil, conway@math.Princeton.EDU Subject: Re: Seven point seven line abstract geometric thing Cc: math-fun@cs.arizona.edu Status: RO This "projective plane of order 2" is especially neat among other reasons because its group of automorphisms (incidence-preserving bijections) is the simple group of order 168. --Dan Asimov From eunetde!AIC.NRL.Navy.Mil!hoey Mon Aug 19 09:15:40 1996 Return-Path: eunetde!AIC.NRL.Navy.Mil!hoey Received: from eunetde.UUCP (wittmann@localhost) by eddie (8.6.11/8.6.11) with UUCP id JAA00429 for lh-systems.de!sillke; Mon, 19 Aug 1996 09:13:58 +0200 Received: by mail.Frankfurt.Germany.EU.net with ESMTP (8.6.5:29/EUnetPoP-1.1.9) via EUnet id JAA00186; Sat, 17 Aug 1996 09:50:05 +0200 From: hoey@AIC.NRL.Navy.Mil Received: by mail.Germany.EU.net with ESMTP (5.59:24/EUnetD-2.5.4.c) via EUnet id JAA27635; Sat, 17 Aug 1996 09:51:40 +0200 Received: from optima.cs.arizona.edu by crash.Mathematik.Uni-Bielefeld.DE id JAA29030; Sat, 17 Aug 1996 09:51:37 +0200 Received: from cheltenham.cs.arizona.edu by optima.cs.arizona.edu (5.65c/15) via SMTP id AA13449; Sat, 17 Aug 1996 00:43:17 MST Received: from optima.CS.Arizona.EDU by cheltenham.cs.arizona.edu; Sat, 17 Aug 1996 00:44:47 MST Received: from Sun0.AIC.NRL.Navy.Mil by optima.cs.arizona.edu (5.65c/15) via SMTP id AA13441; Sat, 17 Aug 1996 00:43:06 MST Received: from sun13.aic.nrl.navy.mil by Sun0.AIC.NRL.Navy.Mil (4.1/SMI-4.0) id AA29871; Sat, 17 Aug 96 03:44:43 EDT Received: by sun13.aic.nrl.navy.mil; Sat, 17 Aug 96 03:44:42 EDT Date: Sat, 17 Aug 96 03:44:42 EDT Message-Id: <9608170744.AA06987@sun13.aic.nrl.navy.mil> To: math-fun@cs.arizona.edu Subject: Projective planes Status: O Thanks very much for all who have provided the interesting information on projective planes, Steiner systems, &c. Trying to pin down just what the parameters of block designs are, and I found Joe Fields' on-line combinatorics dictionary, http://zariski.math.uic.edu/~fields/comb_dic/index.html As with many amateur dictionaries, it's a mixture of interesting gems and the occasional inaccuracy or oversimplification (though this is not nearly as bad as most). In this case, he shows how projective planes of n^2+n+1 points arise from affine planes of n^2 points, which in turn arise from finite fields of size n. It's clear he's only talking about the prime-power orders, since those are the sizes of finite fields. And I'm wondering whether an irregular projective plane minus a line and its points would generally be called an affine plane, or whether that term only refers to arrangements generated by finite fields. Another question is whether anything is known about the possibility of irregular projective planes of prime power order, or is there some reason there can be only one projective planes a given order. It doesn't seem obvious to me that the automorphism groups of the known projective planes must be transitive on the lines, so that we can't form multiple "affine" planes by removing different lines. Quite likely that's because I know so little about them. On another tack, it's interesting to see the differing levels of abstraction in the various definitions. Gary McGuire defined a Steiner system as > ... a set X of v points, and a collection of subsets of X of size k, > called blocks, such that any t points of X are in exactly one of the > blocks. (For a PP, v=n^2+n+1, k=n+1, t=2, block=line) Joe Fields doesn't consider the parameter t, though he does include it as a parameter in the discussion of block designs. And Bill Dubuque calls the projective plane a (7,3,1) Steiner triple system. Here I assume the third parameter is lambda, the number of blocks containing each t-subset of X. Now I suppose I'll have to go chase some of those references. Thanks for all the good leads. Dan Hoey@AIC.NRL.Navy.Mil From eunetde!math.Princeton.EDU!conway Mon Aug 19 13:00:55 1996 Return-Path: eunetde!math.Princeton.EDU!conway Received: from eunetde.UUCP (root@localhost) by eddie (8.6.11/8.6.11) with UUCP id MAA00985 for lh-systems.de!sillke; Mon, 19 Aug 1996 12:57:41 +0200 Received: by mail.Frankfurt.Germany.EU.net with ESMTP (8.6.5:29/EUnetPoP-1.1.9) via EUnet id UAA07093; Sun, 18 Aug 1996 20:20:42 +0200 Received: by mail.Germany.EU.net with ESMTP (5.59:24/EUnetD-2.5.4.c) via EUnet id UAA25291; Sun, 18 Aug 1996 20:22:15 +0200 Received: from optima.cs.arizona.edu by crash.Mathematik.Uni-Bielefeld.DE id UAA01792; Sun, 18 Aug 1996 20:21:52 +0200 Received: from cheltenham.cs.arizona.edu by optima.cs.arizona.edu (5.65c/15) via SMTP id AA00414; Sun, 18 Aug 1996 11:12:09 MST Received: from optima.CS.Arizona.EDU by cheltenham.cs.arizona.edu; Sun, 18 Aug 1996 11:13:42 MST Received: from and.Princeton.EDU by optima.cs.arizona.edu (5.65c/15) via SMTP id AA00405; Sun, 18 Aug 1996 11:11:59 MST Received: from broccoli.princeton.edu (conway@broccoli.Princeton.EDU [128.112.16.16]) by and.Princeton.EDU (8.7.5/8.6.12) with SMTP id OAA07325; Sun, 18 Aug 1996 14:13:00 -0400 (EDT) Received: by broccoli.princeton.edu (4.1/Math-Client) id AA00666; Sun, 18 Aug 96 14:12:55 EDT Date: Sun, 18 Aug 1996 13:41:45 -0400 (EDT) From: John Conway Subject: Re: Projective planes To: hoey@AIC.NRL.Navy.Mil Cc: math-fun@cs.arizona.edu In-Reply-To: <9608170744.AA06987@sun13.aic.nrl.navy.mil> Message-Id: Mime-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Status: RO On Sat, 17 Aug 1996 hoey@AIC.NRL.Navy.Mil wrote: > Thanks very much for all who have provided the interesting information > on projective planes, Steiner systems, &c. Trying to pin down > just what the parameters of block designs are, and I found Joe Fields' > on-line combinatorics dictionary, > > http://zariski.math.uic.edu/~fields/comb_dic/index.html > > As with many amateur dictionaries, it's a mixture of interesting gems > and the occasional inaccuracy or oversimplification (though this is > not nearly as bad as most). In this case, he shows how projective > planes of n^2+n+1 points arise from affine planes of n^2 points, which > in turn arise from finite fields of size n. It's clear he's only > talking about the prime-power orders, since those are the sizes of > finite fields. And I'm wondering whether an irregular projective > plane minus a line and its points would generally be called an affine > plane, or whether that term only refers to arrangements generated by > finite fields. General affine planes are defined by axioms rather like those of general projective planes, but mentioning parallelism. A rather nice treatment appears in Seidel's chapter in what I think is the most recent edition of Rouse Ball's "Mathematical Recreations and Essays". I don't have it to hand, but essentially a "plane" has "points" and "lines" subject to 1) there are three non-collinear points 2) any two points lie on just one line 3) any two lines meet in at most one point, and are called "parallel" if they don't meet. 4) (I think) the number of parallels to a line through a point not on it is some constant. If the constant in 4) is 0, the plane is "elliptic" or "projective"; if it is 1 it is "Euclidean" or "affine", and if more than 1 it is "hyperbolic". The standard term for what you're calling the "regular" planes is "Desarguesian", since they are the only ones in which Desargues' theorem is true. > > Another question is whether anything is known about the possibility of > irregular projective planes of prime power order, or is there some > reason there can be only one projective planes a given order. It > doesn't seem obvious to me that the automorphism groups of the known > projective planes must be transitive on the lines, so that we can't > form multiple "affine" planes by removing different lines. Quite > likely that's because I know so little about them. > We still don't know whether there are any projective planes of non-prime-power order. All that's known is the celebrated Bruck-Ryser theorem already mentioned, and the fact that the order can't be 10 (this was established as the result of a massive computer search led by Clement Lam). The Bruck-Ryser theorem follows immediately from the theory of rational quadratic forms. There are several "popular" proofs which to my mind are bad, because they obscure this, and laboriously develop only those bits of the theory that are needed. In this way, the very simple basic idea gets lost, as does the opportunity to learn the wonderful (and very simple!) Hasse-Minkowski theorem. There's no compensating gain, either, because someone who learns only one of these "truncated" proofs won't ever be able to use the same method for anything else. You're right - it isn't obvious that the symmetry group of a projective plane must be transitive on the points or lines, because it isn't necessarily true. However, it IS true (and trivially so) for the Desarguesian planes. There can indeed be non-isomorphic projective planes of the same order - for instance there are 4 distinct planes of order 9. Rather more than 10 years ago I found a construction (written up in a joint paper with Kleidman and Wilson) that gives enormous numbers of distinct planes of order p^2 as the prime p increases, and a bit later a criterion by which one can fairly easily decide the isomorphism question for projective planes. My former student Chris Charnes has made quite an industry out of applying this criterion to the known planes. > On another tack, it's interesting to see the differing levels of > abstraction in the various definitions. Gary McGuire defined a > Steiner system as > > > ... a set X of v points, and a collection of subsets of X of size k, > > called blocks, such that any t points of X are in exactly one of the > > blocks. (For a PP, v=n^2+n+1, k=n+1, t=2, block=line) > > Joe Fields doesn't consider the parameter t, though he does include it > as a parameter in the discussion of block designs. And Bill Dubuque > calls the projective plane a (7,3,1) Steiner triple system. Here I > assume the third parameter is lambda, the number of blocks containing > each t-subset of X. > > Now I suppose I'll have to go chase some of those references. Thanks > for all the good leads. > > Dan > Hoey@AIC.NRL.Navy.Mil From eunetde!martigny.ai.mit.edu!wgd Tue Aug 20 12:05:26 1996 Return-Path: eunetde!martigny.ai.mit.edu!wgd Received: from eunetde.UUCP (nmueller@localhost) by eddie (8.6.11/8.6.11) with UUCP id MAA02956 for lh-systems.de!sillke; Tue, 20 Aug 1996 12:03:16 +0200 Received: by mail.Frankfurt.Germany.EU.net with ESMTP (8.6.5:29/EUnetPoP-1.1.9) via EUnet id UAA14116; Mon, 19 Aug 1996 20:25:58 +0200 Received: by mail.Germany.EU.net with ESMTP (5.59:24/EUnetD-2.5.4.c) via EUnet id UAA11464; Mon, 19 Aug 1996 20:27:31 +0200 Received: from optima.cs.arizona.edu by crash.Mathematik.Uni-Bielefeld.DE id UAA06248; Mon, 19 Aug 1996 20:27:14 +0200 Received: from cheltenham.cs.arizona.edu by optima.cs.arizona.edu (5.65c/15) via SMTP id AA15052; Mon, 19 Aug 1996 11:15:54 MST Received: from optima.CS.Arizona.EDU by cheltenham.cs.arizona.edu; Mon, 19 Aug 1996 11:17:10 MST Message-Id: <199608191815.AA15034@optima.cs.arizona.edu> Received: from martigny.ai.mit.edu by optima.cs.arizona.edu (5.65c/15) via SMTP id AA15034; Mon, 19 Aug 1996 11:15:25 MST Received: from berne.ai.mit.edu by martigny.ai.mit.edu with SMTP (1.40.112.4/16.2) id AA146098625; Mon, 19 Aug 1996 14:17:05 -0400 From: Bill Dubuque Received: by berne.ai.mit.edu (1.40.112.4/16.2) id AA163358623; Mon, 19 Aug 1996 14:17:03 -0400 Date: Mon, 19 Aug 1996 14:17:03 -0400 To: math-fun@cs.arizona.edu Cc: conway@math.Princeton.EDU, rkg@cpsc.ucalgary.ca, rdsilverman@qed.com, pmontgom@cwi.nl, jcl@research.att.com, cet1@cus.cam.ac.uk, ksbrown@seanet.com Subject: Steiner systems in Lehmer factorization algorithm Status: RO Is anyone familiar with this connection below between binary quadratic forms and Steiner systems? Is this now a standard result in combinatorics and, if so, where might I find a full exposition? Does this result have applications elsewhere? Any references would be greatly appreciated. In their paper "A New Factorization Technique Using Quadratic Forms", Math. Comp. 28 #126 1974 625-635 -- towards the goal of automating Mersenne's integer factorization method by representing N as the sum of two squares in two different ways -- the Lehmers prove the following THEOREM. Let N = p*q == n (mod 24) be the product of two primes. From among the equations (A),(B),...,(J) below, select the three that correspond to n by the following scheme n | 1 5 7 11 13 17 19 23 selection | BDI AHJ CDG BFH ADE ABC BDI CFJ (A) N = x^2+y^2 (F) -N = x^2-3*y^2 (B) N = x^2+2*y^2 (G) N = x^2+6*y^2 (C) N = x^2-2*y^2 (H) 2*N = x^2+6*y^2 (D) N = x^2+3*y^2 (I) N = x^2-6*y^2 (E) N = x^2-3*y^2 (J) -N = x^2-6*y^2 Then, at least one of the three selected equations has exactly two solutions with y satisfying the inequalities ... These two solutions determine p and q. The above theorem is related to the Fano plane -- what they call the Steiner triple system (7,3,1). For the above data may be presented in the following table whose nonzero entries are m where m*N=x^2-D*y^2 n 5 7 11 13 17 19 23 ------------------------------ D | -1 | 1 1 1 -2 | 1 1 1 2 | 1 1 1 -3 | 1 1 1 3 | -1 1 -1 -6 | 2 1 2 6 | -1 1 -1 Note that in each line (row or column) there are three nonzero elements and that every pair of parallel lines has just one nonzero element in common. They also mention in passing that the above theorem may be generalized to the case where N is a product of t distinct primes, which results in a Steiner system (2^(t+1)-1, 2^t-1, 2^(t-1)-1). -Bill P.S. This result is also mentioned in passing by Guy [1] p. 67, and Shanks [2] Exercise 5S p. 202, p. 238 (section 74 para. 1). [1] Guy, R. How to Factor a Number, Proc. Fifth Manitoba Conf. on Numerical Math., 1975, 49-89. [2] Shanks, D. Solved and Unsolved Problems in Number Theory, Third Edition, 1985. From eunetde!math.Princeton.EDU!conway Tue Aug 20 12:05:26 1996 Return-Path: eunetde!math.Princeton.EDU!conway Received: from eunetde.UUCP (nmueller@localhost) by eddie (8.6.11/8.6.11) with UUCP id MAA02958 for lh-systems.de!sillke; Tue, 20 Aug 1996 12:03:18 +0200 Received: by mail.Frankfurt.Germany.EU.net with ESMTP (8.6.5:29/EUnetPoP-1.1.9) via EUnet id UAA14250; Mon, 19 Aug 1996 20:57:13 +0200 Received: by mail.Germany.EU.net with ESMTP (5.59:24/EUnetD-2.5.4.c) via EUnet id UAA13344; Mon, 19 Aug 1996 20:58:47 +0200 Received: from optima.cs.arizona.edu by crash.Mathematik.Uni-Bielefeld.DE id UAA06314; Mon, 19 Aug 1996 20:58:43 +0200 Received: from cheltenham.cs.arizona.edu by optima.cs.arizona.edu (5.65c/15) via SMTP id AA15542; Mon, 19 Aug 1996 11:46:47 MST Received: from optima.CS.Arizona.EDU by cheltenham.cs.arizona.edu; Mon, 19 Aug 1996 11:48:21 MST Received: from and.Princeton.EDU by optima.cs.arizona.edu (5.65c/15) via SMTP id AA15532; Mon, 19 Aug 1996 11:46:36 MST Received: from broccoli.princeton.edu (conway@broccoli.Princeton.EDU [128.112.16.16]) by and.Princeton.EDU (8.7.5/8.6.12) with SMTP id OAA14645; Mon, 19 Aug 1996 14:40:31 -0400 (EDT) Received: by broccoli.princeton.edu (4.1/Math-Client) id AA00868; Mon, 19 Aug 96 14:40:27 EDT Date: Mon, 19 Aug 1996 14:19:59 -0400 (EDT) From: John Conway Subject: Re: Steiner systems in Lehmer factorization algorithm To: Bill Dubuque Cc: math-fun@cs.arizona.edu, rkg@cpsc.ucalgary.ca, rdsilverman@qed.com, pmontgom@cwi.nl, jcl@research.att.com, cet1@cus.cam.ac.uk, ksbrown@seanet.com In-Reply-To: <199608191817.OAA23465@math.Princeton.EDU> Message-Id: Mime-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Status: RO On Mon, 19 Aug 1996, Bill Dubuque wrote: > Is anyone familiar with this connection below between binary quadratic > forms and Steiner systems? Is this now a standard result in > combinatorics and, if so, where might I find a full exposition? Does > this result have applications elsewhere? Any references would be > greatly appreciated. > This isn't really "a connection between ... and Steiner systems", since the only such system involved is that for the elementary abelian 2-group C2 x C2 x C2 x ... , which we groupies just call "the group 2^n". What's going on here is that you can only hope to represent N by ax^2 - by^2 (supposing N is prime to a and b) if ab is a quadratic residue modulo N. Now in the theorem you quote, a and b belong to the multiplicative group generated by -1,2,3 modulo squares, which is a group 2^3. Now I can't see your message at this instant, so can't check, but I expect that each of the discriminants mentioned has class number 1, so that if a prime CAN be represented it WILL be, and uniquely, while a composite will be represented multiply. This might fail later, but it doesn't really matter - if the class number were 3, say, you'd just have to check for representability by one of 3 forms rather than 1. The theorem I'm quoting is one you probably know in the discriminant -4 case: an odd number is represented by the form x^2 + y^2 if and only if its prime factors are all 1 (mod 4), and the representation is unique if and only if the number is prime. In the general case, a number prime to the discriminant can be represented by f only if all its prime factors satisfy certain congruence conditions, and if they DO, it will be represented by some form in the class of f, though not necessarily by f itself, and uniquely if and only if it is prime. John Conway From eunetde!faraday.clas.virginia.edu!gmm8n Tue Aug 20 12:05:25 1996 Return-Path: eunetde!faraday.clas.virginia.edu!gmm8n Received: from eunetde.UUCP (nmueller@localhost) by eddie (8.6.11/8.6.11) with UUCP id MAA02967 for lh-systems.de!sillke; Tue, 20 Aug 1996 12:03:24 +0200 Received: by mail.Frankfurt.Germany.EU.net with ESMTP (8.6.5:29/EUnetPoP-1.1.9) via EUnet id EAA15839; Tue, 20 Aug 1996 04:43:54 +0200 Received: by mail.Germany.EU.net with ESMTP (5.59:24/EUnetD-2.5.4.c) via EUnet id EAA12059; Tue, 20 Aug 1996 04:45:28 +0200 Received: from optima.cs.arizona.edu by crash.Mathematik.Uni-Bielefeld.DE id EAA07236; Tue, 20 Aug 1996 04:44:33 +0200 Received: from cheltenham.cs.arizona.edu by optima.cs.arizona.edu (5.65c/15) via SMTP id AA21699; Mon, 19 Aug 1996 19:32:41 MST Received: from optima.CS.Arizona.EDU by cheltenham.cs.arizona.edu; Mon, 19 Aug 1996 19:34:03 MST Received: from virginia.edu by optima.cs.arizona.edu (5.65c/15) via SMTP id AA21689; Mon, 19 Aug 1996 19:32:19 MST Received: from faraday.clas.virginia.edu by mail.virginia.edu id aa13115; 19 Aug 96 22:33 EDT Received: from localhost (gmm8n@localhost) by faraday.clas.Virginia.EDU (8.7.5/8.6.6) with SMTP id WAA157134 for ; Mon, 19 Aug 1996 22:33:42 -0400 Date: Mon, 19 Aug 1996 22:33:42 -0400 (EDT) From: "Gary M. Mcguire" Reply-To: "Gary M. Mcguire" To: math-fun@cs.arizona.edu Subject: Re: Projective planes In-Reply-To: Message-Id: Mime-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Status: RO On Sun, 18 Aug 1996, John Conway wrote: > > The Bruck-Ryser theorem follows immediately from the theory of > rational quadratic forms. There are several "popular" proofs which to > my mind are bad, because they obscure this, and laboriously develop > only those bits of the theory that are needed. In this way, the very > simple basic idea gets lost, as does the opportunity to learn the > wonderful (and very simple!) Hasse-Minkowski theorem. There's no > compensating gain, either, because someone who learns only one of these > "truncated" proofs won't ever be able to use the same method for > anything else. > The proof I know of Bruck-Ryser has the Witt cancellation theorem as its main ingredient. [Allow me to sketch the argument: from the incidence matrix equation A*A^t=nI+J one gets that the quadratic forms in v+1 variables x_1^2 + x_2^2 + ... + x_v^2 - x_{v+1}^2 and nx_1^2 + nx_2^2 + ... + nx_v^2 - nx_{v+1}^2 are isometric over the rationals. Using Witt cancellation and Lagrange's 4-square theorem we "cancel" the x_i^2 and the nx_i^2 in fours to get down to a 4x4 situation which we can manage and find the equation.] But the Witt cancellation theorem is something we can use elsewhere, so I suppose I am wondering what you mean. (Not that I disagree with your Hasse-Minkowski comments, but why don't you like this argument?) -Gary McGuire From eunetde!math.Princeton.EDU!conway Tue Aug 20 12:05:26 1996 Return-Path: eunetde!math.Princeton.EDU!conway Received: from eunetde.UUCP (nmueller@localhost) by eddie (8.6.11/8.6.11) with UUCP id MAA02975 for lh-systems.de!sillke; Tue, 20 Aug 1996 12:03:29 +0200 Received: by mail.Frankfurt.Germany.EU.net with ESMTP (8.6.5:29/EUnetPoP-1.1.9) via EUnet id KAA17722; Tue, 20 Aug 1996 10:36:37 +0200 Received: by mail.Germany.EU.net with ESMTP (5.59:24/EUnetD-2.5.4.c) via EUnet id KAA12839; Tue, 20 Aug 1996 10:38:10 +0200 Received: from optima.cs.arizona.edu by crash.Mathematik.Uni-Bielefeld.DE id KAA07972; Tue, 20 Aug 1996 10:38:01 +0200 Received: from cheltenham.cs.arizona.edu by optima.cs.arizona.edu (5.65c/15) via SMTP id AA26335; Tue, 20 Aug 1996 01:27:11 MST Received: from optima.CS.Arizona.EDU by cheltenham.cs.arizona.edu; Tue, 20 Aug 1996 01:28:41 MST Received: from and.Princeton.EDU by optima.cs.arizona.edu (5.65c/15) via SMTP id AA26327; Tue, 20 Aug 1996 01:26:56 MST Received: from broccoli.princeton.edu (conway@broccoli.Princeton.EDU [128.112.16.16]) by and.Princeton.EDU (8.7.5/8.6.12) with SMTP id EAA11580; Tue, 20 Aug 1996 04:24:19 -0400 (EDT) Received: by broccoli.princeton.edu (4.1/Math-Client) id AA00989; Tue, 20 Aug 96 04:24:06 EDT Date: Tue, 20 Aug 1996 03:27:52 -0400 (EDT) From: John Conway Subject: Re: Projective planes To: "Gary M. Mcguire" Cc: math-fun@cs.arizona.edu In-Reply-To: Message-Id: Mime-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Status: RO On Mon, 19 Aug 1996, Gary M. Mcguire wrote: > > > On Sun, 18 Aug 1996, John Conway wrote: > > > > > The Bruck-Ryser theorem follows immediately from the theory of > > rational quadratic forms. There are several "popular" proofs which to > > my mind are bad, because they obscure this, and laboriously develop > > only those bits of the theory that are needed. In this way, the very > > simple basic idea gets lost, as does the opportunity to learn the > > wonderful (and very simple!) Hasse-Minkowski theorem. There's no > > compensating gain, either, because someone who learns only one of these > > "truncated" proofs won't ever be able to use the same method for > > anything else. > > > > The proof I know of Bruck-Ryser has the Witt cancellation theorem as its > main ingredient. > > [Allow me to sketch the argument: from the incidence matrix equation > A*A^t=nI+J one gets that the quadratic forms in v+1 variables > > x_1^2 + x_2^2 + ... + x_v^2 - x_{v+1}^2 > and > nx_1^2 + nx_2^2 + ... + nx_v^2 - nx_{v+1}^2 > are isometric over the rationals. Using Witt cancellation and Lagrange's > 4-square theorem we "cancel" the x_i^2 and the nx_i^2 in fours to get > down to a 4x4 situation which we can manage and find the equation.] > > But the Witt cancellation theorem is something we can use elsewhere, so I > suppose I am wondering what you mean. (Not that I disagree with your > Hasse-Minkowski comments, but why don't you like this argument?) > > -Gary McGuire > > I've written several paragraphs several times trying to say just why, but deleted them as giving a several wrong impressions! When Bruck and Ryser found their proof, they didn't do this, and they probably wouldn't have found it if they had had to! You can't just find on demand a clever argument cancelling variables in fours. What did they do? [I don't actually know, but am sure this guess is essentially correct.] They got to the rational equivalence of that pair of quadratic forms, and then said (possibly after consulting some number-theoretical colleague) "But the Hasse-Minkowski theorem tells us everything about rational equivalence of quadratic forms - for which q ARE those two forms actually equivalent?" Then after some calculation they found the answer: "just when ... and n is the sum of two squares". This way tells the student what to do in a similar situation. Bruck and Ryser weren't actually trying to prove that n must be the sum of two squares, but trying to see what information the known theory could give them. If ANYTHING had followed from that rational equivalence, they could have found it, and in fact they DID find EVERYTHING that so followed, which just happened to be the fact that n must be a sum of two squares. What makes this truncation such a pity is that the proof of the Hasse-Minkowski theorem is no harder. Unfortunately this is a bit obscured by the fact that the traditional statement of it involves the p-adic numbers. My own way to state and prove it is in terms of my "p-adic signatures" - I'll just tell you the definbition of these things: Diagonalize your form over the rationals to a shape diag [ p^a.A, p^b.B, ... ] where all the entries are integers and A,B,C,... are prime to p. Then its p-adic signature is the sum p^a + p^b + ... + 4k (mod 8) of all the p-parts together with 4 times the number (k) of ANTISQUARES - that is, terms p^a.A that fail to be square for the two reasons that a is odd and A is a non-square modulo p. [For p = 2 the definition is slightly different, and for p = -1 the p-signature is just "the sum of the -1-parts of the entries", namely Sylvester's signature.] The H-M theory then asserts that two non-singular forms are equivalent over the rationals if and only if they have the same determinant and the same p-signatures for all p. I could give you the proof in a page or two. Now whether you should actually students the H-M proof when proving the B-R theorem I don't know. But in my view you MUST tell them of its existence, and you SHOULD give them a statement. I've seen books that don't do either, which I think seriously deprives their readers. When I said "I don't know" above, I was really lying. In my heart of hearts I DO know! In fact I'd go so far as to say that if you haven't got time to prove both H-M and B-R, then you should jetison B-R, which after all is only an isolated result with no further application, rather than H-M, which is a complete, useful, and very powerful theory. John Conway