Skip to content →

# Tag: Dedekind

Last time we revisited Robin’s theorem saying that 5040 being the largest counterexample to the bound
$\frac{\sigma(n)}{n~log(log(n))} < e^{\gamma} = 1.78107...$ is equivalent to the Riemann hypothesis.

There’s an industry of similar results using other arithmetic functions. Today, we’ll focus on Dedekind’s Psi function
$\Psi(n) = n \prod_{p | n}(1 + \frac{1}{p})$
where $p$ runs over the prime divisors of $n$. It is series A001615 in the online encyclopedia of integer sequences and it starts off with

1, 3, 4, 6, 6, 12, 8, 12, 12, 18, 12, 24, 14, 24, 24, 24, 18, 36, 20, 36, 32, 36, 24, 48, 30, 42, 36, 48, 30, 72, 32, 48, 48, 54, 48, …

and here’s a plot of its first 1000 values

To understand this behaviour it is best to focus on the ‘slopes’ $\frac{\Psi(n)}{n}=\prod_{p|n}(1+\frac{1}{p})$.

So, the red dots of minimal ‘slope’ $\approx 1$ correspond to the prime numbers, and the ‘outliers’ have a maximal number of distinct small prime divisors. Look at $210 = 2 \times 3 \times 5 \times 7$ and its multiples $420,630$ and $840$ in the picture.

For this reason the primorial numbers, which are the products of the fist $k$ prime numbers, play a special role. This is series A002110 starting off with

1, 2, 6, 30, 210, 2310, 30030, 510510, 9699690, 223092870,…

In Patrick Solé and Michel Planat Extreme values of the Dedekind $\Psi$ function, it is shown that the primorials play a similar role for Dedekind’s Psi as the superabundant numbers play for the sum-of-divisors function $\sigma(n)$.

That is, if $N_k$ is the $k$-th primorial, then for all $n < N_k$ we have that the 'slope' at $n$ is strictly below that of $N_k$ $\frac{\Psi(n)}{n} < \frac{\Psi(N_k)}{N_k}$ which follows immediately from the fact that any $n < N_k$ can have at most $k-1$ distinct prime factors and $p \mapsto 1 + \frac{1}{p}$ is a strictly decreasing function.

Another easy, but nice, observation is that for all $n$ we have the inequalities
$n^2 > \phi(n) \times \psi(n) > \frac{n^2}{\zeta(2)}$
where $\phi(n)$ is Euler’s totient function
$\phi(n) = n \prod_{p | n}(1 – \frac{1}{p})$
This follows as once from the definitions of $\phi(n)$ and $\Psi(n)$
$\phi(n) \times \Psi(n) = n^2 \prod_{p|n}(1 – \frac{1}{p^2}) < n^2 \prod_{p~\text{prime}} (1 - \frac{1}{p^2}) = \frac{n^2}{\zeta(2)}$ But now it starts getting interesting.

In the proof of his theorem, Guy Robin used a result of his Ph.D. advisor Jean-Louis Nicolas

known as Nicolas’ criterion for the Riemann hypothesis: RH is true if and only if for all $k$ we have the inequality for the $k$-th primorial number $N_k$
$\frac{N_k}{\phi(N_k)~log(log(N_k))} > e^{\gamma}$
From the above lower bound on $\phi(n) \times \Psi(n)$ we have for $n=N_k$ that
$\frac{\Psi(N_k)}{N_k} > \frac{N_k}{\phi(N_k) \zeta(2)}$
and combining this with Nicolas’ criterion we get
$\frac{\Psi(N_k)}{N_k~log(log(N_k))} > \frac{N_k}{\phi(N_k)~log(log(N_k)) \zeta(2)} > \frac{e^{\gamma}}{\zeta(2)} \approx 1.08…$
In fact, Patrick Solé and Michel Planat prove in their paper Extreme values of the Dedekind $\Psi$ function that RH is equivalent to the lower bound
$\frac{\Psi(N_k)}{N_k~log(log(N_k))} > \frac{e^{\gamma}}{\zeta(2)}$
holding for all $k \geq 3$.

Dedekind’s Psi function pops up in lots of interesting mathematics.

In the theory of modular forms, Dedekind himself used it to describe the index of the congruence subgroup $\Gamma_0(n)$ in the full modular group $\Gamma$.

In other words, it gives us the number of tiles needed in the Dedekind tessellation to describe the fundamental domain of the action of $\Gamma_0(n)$ on the upper half-plane by Moebius transformations.

When $n=6$ we have $\Psi(6)=12$ and we can view its fundamental domain via these Sage commands:

 G=Gamma0(6) FareySymbol(G).fundamental_domain() 

giving us the 24 back or white tiles (note that these tiles are each fundamental domains of the extended modular group, so we have twice as many of them as for subgroups of the modular group)

But, there are plenty of other, seemingly unrelated, topics where $\Psi(n)$ appears. To name just a few:

• The number of points on the projective line $\mathbb{P}^1(\mathbb{Z}/n\mathbb{Z})$.
• The number of lattices at hyperdistance $n$ in Conway’s big picture.
• The number of admissible maximal commuting sets of operators in the Pauli group for the $n$ qudit.

and there are explicit natural one-to-one correspondences between all these manifestations of $\Psi(n)$, tbc.

Here’s a 5 move game from $\mathbb{C}$, the complex numbers game, annotated by Hendrik Lenstra in Nim multiplication.

$\begin{matrix} & \text{White} & \text{Black} \\ 1. & 3-2i & { 3_{\mathbb{R}} } \\ 2. & 3_{\mathbb{R}} & (22/7)_{\mathbb{Q}} \\ 3. & (-44_{\mathbb{Z}},-14_{\mathbb{Z}})? & { -44_{\mathbb{Z}} } \\ 4. & -44_{\mathbb{Z}} & ( 0_{\mathbb{N}},44_{\mathbb{N}} )! \\ 5. & \text{Resigns} & \\ \end{matrix}$

He writes : “The following 5 comments will make the rules clear.

1 : White selected a complex numbers. Black knows that $\mathbb{C} = \mathbb{R} \times \mathbb{R}$ by $a+bi = (a,b)$, and remembers Kuratowski’s definition of an ordered pair: $~(x,y) = { { x }, { x,y } }$. Thus black must choose an element of ${ { 3_{\mathbb{R}} }, { 3_{\mathbb{R}},-2_{\mathbb{R}} } }$. The index $\mathbb{R}$ here, and later $\mathbb{Q},\mathbb{Z}$ and $\mathbb{N}$, serve to distinguish between real numbers, rational numbers, integers and natural numbers usually denoted by the same symbol. Black’s move leaves White a minimum of choice, but it is not the best one.

2 : White has no choice. The Dedekind definition of $\mathbb{R}$ which the players agreed upon identifies a real number with the set of all strictly larger rational numbers; so Black’s move is legal.

3 : A rational number is an equivalence class of pairs of integers $~(a,b)$ with $b \not= 0$; here $~(a,b)$ represents the rational number $a/b$. The question mark denotes that White’s move is a bad one.

4 : The pair $~(a,b)$ of natural numbers represents the integer $a-b$. Black’s move is the only winning one.

5 : White resigns, since he can choose between ${ 0_{\mathbb{N}} }$ and ${ 0_{\mathbb{N}},44_{\mathbb{N}} }$. In both cases Black will reply by $0_{\mathbb{N}}$, which is the empty set” (and so wins because White has no move left).

These rules make it clear what we mean by the natural numbers $\mathbb{N}$ game, the $\mathbb{Z}$-game and the $\mathbb{Q}$ and $\mathbb{R}$ games. A sum of games is defined as usual (players are allowed to move in exactly one of the component games).

Here’s a 5 term exercise from Lenstra’s paper : Determine the unique winning move in the game $\mathbb{N} + \mathbb{Z} + \mathbb{Q} + \mathbb{R} + \mathbb{C}$

It will take you less than 5 minutes to solve this riddle. Some of the other ‘exercises’ in Lenstra’s paper may take you a lot longer, if not forever…

Exactly 5 years ago I wrote : “As it is probably better to run years behind than to stand eternally still, I’ll try out how much of a blogger I am in 2004.”

5 months ago this became : “from january 1st 2009, I’ll be moving out of here. I will leave the neverendingbooks-site intact for some time to come, so there is no need for you to start archiving it en masse, yet.”

5 minutes before the deadline, this will be my last post….

of 2008

less entropy in 2009!

Last time we tried to generalize the Connes-Consani approach to commutative algebraic geometry over the field with one element $\mathbb{F}_1$ to the noncommutative world by considering covariant functors

$N~:~\mathbf{groups} \rightarrow \mathbf{sets}$

which over $\mathbb{C}$ resp. $\mathbb{Z}$ become visible by a complex (resp. integral) algebra having suitable universal properties.

However, we didn’t specify what we meant by a complex noncommutative variety (resp. an integral noncommutative scheme). In particular, we claimed that the $\mathbb{F}_1$-‘points’ associated to the functor

$D~:~\mathbf{groups} \rightarrow \mathbf{sets} \qquad G \mapsto G_2 \times G_3$ (here $G_n$ denotes all elements of order $n$ of $G$)

were precisely the modular dessins d’enfants of Grothendieck, but didn’t give details. We’ll try to do this now.

For algebras over a field we follow the definition, due to Kontsevich and Soibelman, of so called “noncommutative thin schemes”. Actually, the thinness-condition is implicit in both Soule’s-approach as that of Connes and Consani : we do not consider R-points in general, but only those of rings R which are finite and flat over our basering (or field).

So, what is a noncommutative thin scheme anyway? Well, its a covariant functor (commuting with finite projective limits)

$\mathbb{X}~:~\mathbf{Alg}^{fd}_k \rightarrow \mathbf{sets}$

from finite-dimensional (possibly noncommutative) $k$-algebras to sets. Now, the usual dual-space operator gives an anti-equivalence of categories

$\mathbf{Alg}^{fd}_k \leftrightarrow \mathbf{Coalg}^{fd}_k \qquad A=C^* \leftrightarrow C=A^*$

so a thin scheme can also be viewed as a contra-variant functor (commuting with finite direct limits)

$\mathbb{X}~:~\mathbf{Coalg}^{fd}_k \rightarrow \mathbf{Sets}$

In particular, we are interested to associated to any {tex]k $-algebra$A $its representation functor :$\mathbf{rep}(A)~:~\mathbf{Coalg}^{fd}_k \rightarrow \mathbf{Sets} \qquad C \mapsto Alg_k(A,C^*) $This may look strange at first sight, but$C^* $is a finite dimensional algebra and any$n $-dimensional representation of$A $is an algebra map$A \rightarrow M_n(k) $and we take$C $to be the dual coalgebra of this image. Kontsevich and Soibelman proved that every noncommutative thin scheme$\mathbb{X} $is representable by a$k $-coalgebra. That is, there exists a unique coalgebra$C_{\mathbb{X}} $(which they call the coalgebra of ‘distributions’ of$\mathbb{X} $) such that for every finite dimensional$k $-algebra$B $we have$\mathbb{X}(B) = Coalg_k(B^*,C_{\mathbb{X}}) $In the case of interest to us, that is for the functor$\mathbf{rep}(A) $the coalgebra of distributions is Kostant’s dual coalgebra$A^o $. This is the not the full linear dual of$A $but contains only those linear functionals on$A $which factor through a finite dimensional quotient. So? You’ve exchanged an algebra$A $for some coalgebra$A^o $, but where’s the geometry in all this? Well, let’s look at the commutative case. Suppose$A= \mathbb{C}[X] $is the coordinate ring of a smooth affine variety$X $, then its dual coalgebra looks like$\mathbb{C}[X]^o = \oplus_{x \in X} U(T_x(X)) $the direct sum of all universal (co)algebras of tangent spaces at points$x \in X $. But how do we get the variety out of this? Well, any coalgebra has a coradical (being the sun of all simple subcoalgebras) and in the case just mentioned we have$corad(\mathbb{C}[X]^o) = \oplus_{x \in X} \mathbb{C} e_x $so every point corresponds to a unique simple component of the coradical. In the general case, the coradical of the dual coalgebra$A^o $is the direct sum of all simple finite dimensional representations of$A $. That is, the direct summands of the coalgebra give us a noncommutative variety whose points are the simple representations, and the remainder of the coalgebra of distributions accounts for infinitesimal information on these points (as do the tangent spaces in the commutative case). In fact, it was a surprise to me that one can describe the dual coalgebra quite explicitly, and that$A_{\infty} $-structures make their appearance quite naturally. See this paper if you’re in for the details on this. That settles the problem of what we mean by the noncommutative variety associated to a complex algebra. But what about the integral case? In the above, we used extensively the theory of Kostant-duality which works only for algebras over fields… Well, not quite. In the case of$\mathbb{Z} $(or more general, of Dedekind domains) one can repeat Kostant’s proof word for word provided one takes as the definition of the dual$\mathbb{Z} $-coalgebra of an algebra (which is$\mathbb{Z} $-torsion free)$A^o = { f~:~A \rightarrow \mathbb{Z}~:~A/Ker(f)~\text{is finitely generated and torsion free}~} $(over general rings there may be also variants of this duality, as in Street’s book an Quantum groups). Probably lots of people have come up with this, but the only explicit reference I have is to the first paper I’ve ever written. So, also for algebras over$\mathbb{Z} $we can define a suitable noncommutative integral scheme (the coradical approach accounts only for the maximal ideals rather than all primes, but somehow this is implicit in all approaches as we consider only thin schemes). Fine! So, we can make sense of the noncommutative geometrical objects corresponding to the group-algebras$\mathbb{C} \Gamma $and$\mathbb{Z} \Gamma $where$\Gamma = PSL_2(\mathbb{Z}) $is the modular group (the algebras corresponding to the$G \mapsto G_2 \times G_3 $-functor). But, what might be the points of the noncommutative scheme corresponding to$\mathbb{F}_1 \Gamma $??? Well, let’s continue the path cut out before. “Points” should correspond to finite dimensional “simple representations”. Hence, what are the finite dimensional simple$\mathbb{F}_1 $-representations of$\Gamma $? (Or, for that matter, of any group$G $) Here we come back to Javier’s post on this : a finite dimensional$\mathbb{F}_1 $-vectorspace is a finite set. A$\Gamma $-representation on this set (of n-elements) is a group-morphism$\Gamma \rightarrow GL_n(\mathbb{F}_1) = S_n $hence it gives a permutation representation of$\Gamma $on this set. But then, if finite dimensional$\mathbb{F}_1 $-representations of$\Gamma $are the finite permutation representations, then the simple ones are the transitive permutation representations. That is, the points of the noncommutative scheme corresponding to$\mathbb{F}_1 \Gamma $are the conjugacy classes of subgroups$H \subset \Gamma $such that$\Gamma/H \$ is finite. But these are exactly the modular dessins d’enfants introduced by Grothendieck as I explained a while back elsewhere (see for example this post and others in the same series).