cp's OEIS Frontend

Number of primitive sublattices of index n in generic 2-dimensional lattice; also index of Gamma_0(n) in SL_2(Z).

A generic 2-dimensional lattice L = consists of all vectors of the form mV + nW, (m,n integers). A sublattice S = has index |ad-bc| and is primitive if gcd(a,b,c,d) = 1. The generic lattice L has precisely a(2) = 3 sublattices of index 2, namely <2V,W>, and (which = ) and so on for other indices.

The sublattices of index n are in 1-to-1 correspondence with matrices [a b; 0 d] with a>0, ad=n, b in [0..d-1]. The number of these is Sum_{d|n} = sigma(n), which is A000203. A sublattice is primitive if gcd(a,b,d) = 1; the number of these is n * product_{p|n} (1+1/p), which is the present sequence.

SL_2(Z) = Gamma is the group of all 2 X 2 matrices [a b; c d] where a,b,c,d are integers with ad-bc = 1 and Gamma_0(N) is usually defined as the subgroup of this for which N|c. But conceptually Gamma is best thought of as the group of (positive) automorphisms of a lattice , its typical element taking V -> aV + bW, W -> cV + dW and then Gamma_0(N) can be defined as the subgroup consisting of the automorphisms that fix the sublattice of index N. - J. H. Conway, May 05 2001

Dedekind proved that if n = k_i*j_i for i in I represents all the ways to write n as a product, and e_i=gcd(k_i,j_i), then a(n)= sum(k_i / (e_i * phi(e_i)), i in I ) [cf. Dickson, History of the Theory of Numbers, Vol. 1, p. 123].

Also a(n)= number of cyclic subgroups of order n in an Abelian group of order n^2 and type (1,1) (Fricke). - Len Smiley, Dec 04 2001

The polynomial degree of the classical modular equation of degree n relating j(z) and j(nz) is psi(n) (Fricke). - Michael Somos, Nov 10 2006; clarified by Katherine E. Stange, Mar 11 2022

The Mobius transform of this sequence is A063659. - Gary W. Adamson, May 23 2008

The inverse Mobius transform of this sequence is A060648. - Vladeta Jovovic, Apr 05 2009

The Dirichlet inverse of this sequence is A008836(n) * A048250(n). - Álvar Ibeas, Mar 18 2015

The Riemann Hypothesis is true if and only if a(n)/n - e^gamma*log(log(n)) < 0 for any n > 30. - Enrique Pérez Herrero, Jul 12 2011

The Riemann Hypothesis is also equivalent to another inequality, see the Sole and Planat link. - Thomas Ordowski, May 28 2017

An infinitary analog of this sequence is the sum of the infinitary divisors of n (see A049417). - Vladimir Shevelev, Apr 01 2014

Problem: are there composite numbers n such that n+1 divides psi(n)? - Thomas Ordowski, May 21 2017

The sum of divisors d of n such that n/d is squarefree. - Amiram Eldar, Jan 11 2019

Psi(n)/n is a new maximum for each primorial (A002110) [proof in link: Patrick Sole and Michel Planat, Proposition 1 page 2]. - Bernard Schott, May 21 2020

From Jianing Song, Nov 05 2022: (Start)

a(n) is the number of subgroups of C_n X C_n that are isomorphic to C_n, where C_n is the cyclic group of order n. Proof: the number of elements of order n in C_n X C_n is A007434(n) (they are the elements of the form (a,b) in C_n X C_n where gcd(a,b,n) = 1), and each subgroup isomorphic to C_n contains phi(n) generators, so the number of such subgroups is A007434(n)/phi(n) = a(n).

The total number of order-n subgroups of C_n X C_n is A000203(n). (End)

The hexagonal lattice is the familiar 2-dimensional lattice in which each point has 6 neighbors. This is sometimes called the triangular lattice.

From Andrey Zabolotskiy, Mar 10 2018: (Start)

If only primitive sublattices are considered, we get A003050.

Here only rotations and reflections preserving the parent hexagonal lattice are allowed. If reflections are not allowed, we get A145394. If any rotations and reflections are allowed, we get A300651.

In other words, the parent lattice of the sublattices under consideration has Patterson symmetry group p6mm, and two sublattices are considered equivalent if they are related via a symmetry from that group [Rutherford]. For other 2D Patterson groups, the analogous sequences are A000203 (p2), A069734 (p2mm), A145391 (c2mm), A145392 (p4), A145393 (p4mm), A145394 (p6).

Rutherford says at p. 161 that his sequence for p6mm differs from this sequence, but it seems that with the current definition and terms of this sequence, this actually is his p6mm sequence, and the sequence he thought to be this one is actually A300651. Also, he says that a(n) != A300651(n) only when A002324(n) > 2 (first time happens at n = 49), but actually these two sequences differ at other terms, too, for example, at n = 42 (see illustration). (End)

From Andrey Zabolotskiy, Mar 12 2018: (Start)

If reflections are not allowed, we get A145392. If any rotations and reflections are allowed, we get A054346.

The parent lattice of the sublattices under consideration has Patterson symmetry group p4mm, and two sublattices are considered equivalent if they are related via a symmetry from that group [Rutherford]. For other 2D Patterson groups, the analogous sequences are A000203 (p2), A069734 (p2mm), A145391 (c2mm), A145392 (p4), A145394 (p6), A003051 (p6mm).

Rutherford says at p. 161 that a(n) != A054346(n) only when A002654(n) > 2, but actually these two sequence differ at other terms, too, for example, at n = 30 (see illustration). (End)

The hexagonal lattice is the familiar 2-dimensional lattice in which each point has 6 neighbors. This is sometimes called the triangular lattice.

Also the number of triangles with vertices on points of the hexagonal lattice that have area equal to n/2. - Amihay Hanany, Oct 15 2009 [Here the area is measured in the units of the lattice unit cell area; since the number of the triangles of different shapes with the same half-integral area is infinite, the triangles are probably counted up to the equivalence relation defined in the Davey, Hanany and Rak-Kyeong Seong paper. Also, this comment probably belongs to A003051, not here. - Andrey Zabolotskiy, Mar 10 2018 and Jul 04 2019]

Also number of 2n-vertex connected cubic vertex-transitive graphs which are Cayley graphs for a dihedral group [Potočnik et al.]. - N. J. A. Sloane, Apr 19 2014

From Andrey Zabolotskiy, Mar 12 2018: (Start)

The parent lattice of the sublattices under consideration has Patterson symmetry group p4, and two sublattices are considered equivalent if they are related via a symmetry from that group [Rutherford]. For other 2D Patterson groups, the analogous sequences are A000203 (p2), A069734 (p2mm), A145391 (c2mm), A145393 (p4mm), A145394 (p6), A003051 (p6mm).

If we count sublattices related by parent-lattice-preserving reflection as equivalent, we get A145393 instead of this sequence. If we count sublattices related by rotation of the sublattice only (but not parent lattice; equivalently, sublattices related by rotation by angle which is not a multiple of Pi/2; see illustration in links) as equivalent, we get A054345. If we count sublattices related by any rotation or reflection as equivalent, we get A054346.

Rutherford says at p. 161 that a(n) != A054345(n) only when A002654(n) > 1, but actually these two sequences differ at other terms, too, for example, at n = 15 (see illustration). (End)

If we count sublattices as equivalent only if they are related by a rotation, we get A054345 instead of this sequence. If we only allow rotations and reflections that preserve the parent (square) lattice, we get A145393; the first discrepancy is at n = 25 (see illustration), the second is at n = 30. If both restrictions are applied, i.e., only rotations preserving the parent lattice are allowed, we get A145392. The analog for the hexagonal lattice is A300651. - Andrey Zabolotskiy, Mar 12 2018

The hexagonal lattice is the familiar 2-dimensional lattice in which each point has 6 neighbors. This is sometimes called the triangular lattice.

If reflections are allowed, we get A300651. If only rotations that preserve the parent hexagonal lattice are allowed, we get A145394. The analog for square lattice is A054345. - Andrey Zabolotskiy, Mar 10 2018