Re: What am I studying here?

From: Paul Chapman (paul_at_igblan.free-online.co.uk)
Date: 08/23/04 

Date: Mon, 23 Aug 2004 11:30:12 +0100

Chas,

> > {a c)(i) modulo (D,D) where D=ad-bc
> > {b d)(j)
>
> I'd think of it as group theory problem.

Yes, that's what I was doing. :)

> Instead of thinking "Z x Z", let Z_D be the cyclic group of order D,
> and think of G = Z_D x Z_D with group operation pointwise addition,
> being generated by <(0,1),(1,0)>. Note that for any g,h in Z_D x Z_D,
> A(g+h) = Ag + Ah; so A induces an endomorphism of Z_D x Z_D.

"Endomorphism" is a useful term to know.

> Thus, since g in G > g = n(1,0) + m(0,1), Ag = nA(1,0)+mA(0,1); i.e.,
> AG is the subgroup of elements of the form
>
> m(a,b)+n(c,d)
>
> for integers m,n. Use the fact that gcd(ad,D) = gcd(bc,D) and
> resulting facts to figure out the exact form of AG, which will be
> isomorphic to either Z_i or Z_i x Z_j, where i,j divide D.

I had figured this out (and of course that ij=D in the latter case), but
haven't yet figured out a simple way to determine when it can be the former.
At the very least, I have now discovered for myself that Z_i x Z_j is
isomorphic to Z_{ij} when gcd(i,j)=1. :)

I hope your hint that gcd(ad,D) = gcd(bc,D) will enable me to find (i,j).

---------------

The "application", BTW, is the enumeration of two-glider collisions in CA
Rule 110. Of course I could trivially enumerate them just by defining a
dull algorithm which lists all of the members of AG in some arbitrary order
according to some fixed algorithm. But the mathematician in me wants to
find the simplest possible parametrization of a "canonical" enumeration
(with as much elegant symmetry as possible), ie a short list of parameters
and a fixed formula which allows me to map from (my) (i,j) to the
corresponding ordinal (or perhaps pair of ordinals) in the enumeration of
AG.

I am *not* asking for anyone to solve my problem. The fun is doing it for
myself. :)

Cheers, Paul