Mobius aMUsements

[John Conway]

On Sat, 5 May 2001, Avi Peretz wrote:

> Recently I contributed a comment about sequence A000203, which is sigma(n)
> the sum of the divisors of n.
> According to the reference of Lubotzky in sequence A000203:
>     [...]
> The number of sublattices of index n in Z^2 is sigma(n).

  OK, let me think this out, by doing the case  n = 4 (since almost
certainly the problem is one of primitivity).  I prefer to find the
superlattices of index 4 (which is the same problem, by duality).

   Such a thing is got from  <e,f>  by adjoining a vector  v  which
is of order  4  modulo  <e,f>,  or alternatively by adjoining two
independent vectors of order  2  theremodulo.

    In the first case,  the vector can be chosen to be  ae+bf,
where  a,b  are in  {0,1/4,1/2,3/4}  and at least one has
denominator 4.  This gives the possibilities for  (a,b):

    (1/4,0)    <-->  (3/4,0)
    (1/4,1/4)  <-->  (3/4,3/4)
    (1/4,1/2)  <-->  (3/4,1/2)
    (1/4,3/4)  <-->  (3/4,1/4)
    (0,1/4)    <-->  (0,3/4)
    (1/2,1/4)  <-->  (1/2,3/4)

which I've grouped in the pairs that give the same lattice.

    In the second case, the generators are any two of

     (1/2,0),(0,1/2),(1/2,1/2)

and since they generate the third, there's only one lattice.

   So we get  7 =  sigma(4)  lattices of index  4  in all,
of which  6 = phi+(4)  are primitive.

   I did all this just to "remind myself" what the answer was,
but it should be easy to prove: let me try...

   Yes, the sigma case at least is easy.  Namely we can suppose
that the first vector has the form  (1/k,*)  for some divisor
k  of  n,  and then that the second has form  (0,1/l)  for
the complementary divisor  l.  The number of possibilities
for  *  is  d(l)  (since they can be reduced mod 1/l),  which
gives the total answer.

   In fact the  phi+  case is much the same,  the difference
being just that one only counts "exact divisors", namely those
for which  (k,l) = 1.

    JHC