Let me immodestly report on one of my own. I had just, with
Peter Kleidman and Robert Wilson, found a construction that seemed
to give a very large number of projective planes. The problem was
to determine just how many of them were really distinct.
As far as I knew, the only previous method was essentially to
try all possible ways to patch up an isomorphism between two planes,
an enormous computer backtracking job even for small examples, and
prohibitively large for most of ours. So I decided to try to dream
up a new method.
It was an afternoon in late winter, when it gets dark by about
4pm in England. I went home at about that time, and deliberately
decided to just sit and think in the dark, and in the event I did
so for 3 or 4 hours, thinking very hard indeed (so hard that I
sweated considerably!).
It's a bit hard to describe those thoughts. My first tactic
was (as it often is) to try to imagine the ways other people might
attack this problem, and be sure to avoid those, because they
obviously hadn't been successful! So I deliberately thought of
about half-a-dozen such lines of attack which had the sole purpose
of constraining my thoughts to be unlike those.
Now if your plane has order q (ie., q+1 points on each line),
then the number of points is q^2 + q + 1 (ie., roughly q^2)
and if you start to patch up an isomorphism between your two
planes, the powers of q grow quite rapidly - watch:
If A,B,C are three non-collinear points of your first plane,
there are already roughly q^6 possibilities for their images A',B',C'
in your second plane. But there's nothing the axioms of projective
planes say about one triangle that's different from what they say
aboth another, so we'll have to make another random guess D' for the
image of a fourth point D before we have any hope of seeing a
distinctive structure (and we might well not see it even then).
So isomorphism-patching was not something to improve, but rather
to avoid. I decided that what was needed was some kind of invariant
that could be computed with a much smaller amount of calculation, and
that it should be "algebraic" rather than merely combinatorial (such
as the number of "somethings" through a "something else"). The only
algebraic thing we had to start with was the incidence matrix.
But these incidence matrices themselves look much the same for all
planes - could I somehow add some more structure which might not?
I used the fact that if P is a point not on a line L, then the plane
gives an obvious 1-1 correspondence between the points on L and
the lines through P. Could I get something out of this?
Yes! If we fix randomly chosen orderings of ALL the points and
ALL the lines, then we get another such correspondence, namely the
order-preserving one, and we can compare the two. Of course the
result will depend on the random ordering we chose, but there's
a weak little something that doesn't depend too much on that, namely
the sign of the permutation that takes one ordering to another.
Well, even that DOES depend on the orderings, but in a controllable way.
If one considers the matrix M whose (P,L)-entry is the sign of this
permutation (or 0 if P is on L), then switching to different orderings
changes this matrix only to N = UMV , where U and V are permutation
matrices with signs, and so the entries of the products M.Mtranspose
and N.Ntranspose will be the same numbers, up to sign.
This was a possible invariant! To be more precise, it was certainly
an invariant, but maybe it would be TOO invariant, by being the same
for all planes? That's the way this sort of thing usually fails, but
I couldn't see why it must fail for this one, so was very keen to
"suck it and see"!
Everything turned out beautifully - the new invariant works like a
charm - my then student Chris Charnes programmed it up for translation
planes, for which there's a simplification that enables one to get
away with roughly q-by-q matrices rather than q^2-by-q^2 ones,
and it's never taken the same value for any two distinct planes, as
far as I know. Moreover, when it does take the same value, it gives
you an easy way to try to find an isomorphism between the two planes,
and again, that's always succeeded, as far as I know.
Well, I'm sorry for giving so much technical detail, but I've
always been distinctly pleased about this particular find. It's
not at all typical for me - in fact it's the ONLY case when I
just sat and thought for several hours without putting pen to paper
(for which I'd've had to turn the light on!). I think it's now
"the industry standard" for distinguishing projective planes, but
must admit that I'm not really up-to-date in that field, because
I never actually bothered to think about it any more - I just
handed the method over to Charnes who has made almost all the
applications of it, as far as I know. I was happy just to have
been able to produce the idea.
John Conway