Mobius aMUsements

[John Conway]

On Mon, 7 May 2001, Avi Peretz wrote:

> Hello, thanks for the explanation.
> The sigma(n) has a higher dimensional version for example in A038999:
> and if f(m,n) is the total number of sublattices of index n in Z^m the recursion
> is:
> f(m,n)=Sum d*f(m-1,d), d|n.

   You're very welcome.

   I noticed a mistake at the end of my message.  Namely I said
that in the  phi+  case, the sum was restricted to exact divisors.
The appropriate restriction is in fact to the  (k,l)  for which
k is squarefree  (or maybe that should be  l - I've forgotten the
notation I used.

> But I did not find in the database the higher dimensional version of phi+(n),
> i.e the number of primitive sublattices of index n in Z^m for m>=3 .
> Is there a familiar formula for this ?

   I don't know.  I thought at first that this should be an easy
problem, but now I'm not so sure.   It is certainly a multiplicative
function of  n,  so that one only has to do the case  n = p^s.
The trouble there is, when m = 3, say,  that the quotient group of the two
lattices can be  C(p^i) x C^(p^j) x C(p^k)  (i =< j =< k) for a general
sublattice,  with  i = 0  for a primitive one, and the sum over various
values of  j  and  k  might be troublesome.

   You describe this as "the higher dimensional version of  phi+", but
in fact there's a better candidate, which is "sublattices of cyclic index"
(ie., having  C(n) for their quotient group).  These are much more readily
enumerated, since all one has to do is count the number of vectors of
order  p^s  modulo the lattice.  Such a thing is specified by a
string of coordinates whose values have the form  a/p^s, with at least
one denominator exactly  p^s, and where the coordinates only matter
mod 1.  The number of such strings is therefore

        (p^s)^m - (p^{s-1))^m

(the first term counting all strings with denominators dividing p^s,
and the second removing those whose denominators all divide  p^{s-1}).
This tells us that the number of such cyclic sublattices is

       ms        ms-m
      p     -   p           ms-s    ms-s-1          ms-m-s+1
     -----------------  =  p     + p       + ... + p
         s       s-1
        p   -   p

(since the  phi(p^s) =  p^s - p^{s-1}  multiples of a vector by numbers
prime to p all give the same lattice).

    Let me check this for  m=2.   It gives

         p^s + p^{s-1}  =   p^s.( 1 + 1/p )  =  phi+(p^s),

and so is probably correct.

    Hmm.  I've just been thinking about the other problem; I
could certainly do it for  m = 3,  but without another idea
can't see an easy way to do the general case, and suspect it
may be a mess.  I'll have a go at  m = 3, to see if it suggests
a pattern.

    JHC