Mobius aMUsements

[Avi Peretz]

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.

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 ?

Thanks,Avi



John Conway wrote:

> 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