Dirichlet Polynomials and Entropy

Abstract

A Dirichlet polynomial d in one variable $\mathrm{y}$ is a function of the form $d\left(\mathrm{y}\right)=a_n{n}^{\mathrm{y}}+\cdots +a_2{2}^{\mathrm{y}}+a_1{1}^{\mathrm{y}}+a_0{0}^{\mathrm{y}}$ for some $n,a_0,\dots ,a_n\in \mathbb{N}$. We will show how to think of a Dirichlet polynomial as a set-theoretic bundle, and thus as an empirical distribution. We can then consider the Shannon entropy $H\left(d\right)$ of the corresponding probability distribution, and we define its length (or, classically, its perplexity) by $L\left(d\right)=2^{H\left(d\right)}$. On the other hand, we will define a rig homomorphism $h:\mathsf{Dir}\to \mathsf{Rect}$ from the rig of Dirichlet polynomials to the so-called rectangle rig, whose underlying set is ${\mathbb{R}}_{⩾0}\times {\mathbb{R}}_{⩾0}$ and whose additive structure involves the weighted geometric mean; we write $h\left(d\right)=\left(A\right(d),W(d\left)\right)$, and call the two components area and width (respectively). The main result of this paper is the following: the rectangle-area formula $A\left(d\right)=L\left(d\right)W\left(d\right)$ holds for any Dirichlet polynomial d. In other words, the entropy of an empirical distribution can be calculated entirely in terms of the homomorphism h applied to its corresponding Dirichlet polynomial. We also show that similar results hold for the cross entropy.

1. Introduction

The purpose of this paper is simply to provide another categorical treatment of entropy of probability distributions, which turns out to be computed in terms of a rig homomorphism; our treatment also generalises to cross entropy (and thus to Kullback–Leibler divergence). What is particularly interesting about the treatment outlined here is that we can somewhat “visualise” the notion of entropy in terms of sizes of coding schemes (cf. Section 6). Not only that, but classical entropy is only homomorphic in the product of distributions, whereas the notion that we describe here is homomorphic in both the product and the sum.

A brief outline of this paper is as follows:

• Section 2: We recall the definitions of Dirichlet polynomials and set-theoretic bundles, along with their rig structures, from [1] (one important thing to note is the following: Dirichlet polynomials are well-studied objects in the setting of complex analysis, but we cannot apply tools from this area to our setting, because we have only natural number coefficients and non-negative exponents); we then study the equivalence between these two notions.
• Section 3: We explain how empirical probability distributions correspond to set-theoretic bundles (and thus to Dirichlet polynomials).
• Section 4: We define the rig homomorphism $h:\mathsf{Dir}\to \mathsf{Rect}$ that we wish to study, whose codomain is a rig encoding the weighted geometric mean; we prove some useful computational results and give some explicit examples.
• Section 5: We define the entropy $H\left(d\right)$ of a Dirichlet polynomial using the classical notion of Shannon entropy; we give some explicit examples; we prove the main result of this paper (Theorem 1), relating entropy to the rig homomorphism defined in the previous section.
• Section 6: We try to provide some intuition for the image $h\left(d\right)$ of a Dirichlet polynomial under the rig homomorphism, in terms of coding schemes.
• Section 7: We generalise Theorem 1 to the case of cross-entropy, or Kullback–Leibler divergence.

Prerequisites

We assume that the reader is familiar with the fundamentals of category theory, such as functors, natural transformations, and (co)products, as covered, for example, in [2] (Chapter 1).

2. Dirichlet Polynomials and Bundles

This section is simply a brief summary of content from [1], repeated here for the convenience of the reader.

Definition 1.

A Dirichlet polynomial d in one variable $\mathrm{y}$ is a function of the form

$$d\left(\mathrm{y}\right)=a_n{n}^{\mathrm{y}}+\dots +a_2{2}^{\mathrm{y}}+a_1{1}^{\mathrm{y}}+a_0{0}^{\mathrm{y}}$$

for some $n,a_0,\dots ,a_n\in \mathbb{N}$.

The set of Dirichlet polynomials is clearly closed under addition, and further under multiplication (using the distributive law along with the fact that $m^{\mathrm{y}}·n^{\mathrm{y}}={(m·n)}^{\mathrm{y}}$). In fact, it has the structure of a rig: a “ring without negatives” (or, to be pedantic, a monoid object in commutative monoids). We denote this rig by $\mathsf{Dir}$, where the additive unit is 0, and the multiplicative unit is $1^{\mathrm{y}}$.

Note that we can embed $\mathbb{N}$ as a sub-rig of $\mathsf{Dir}$, by $a\mapsto a·1^{\mathrm{y}}$; we often use this fact and simply write $a\in \mathsf{Dir}$.

Following [1], we can think of Dirichlet polynomials as functors ${\mathtt{FSet}}^{\mathrm{o}\mathrm{p}}\to \mathtt{FSet}$, where $\mathtt{FSet}$ is the category of finite sets. Indeed, given a natural number $n\in \mathbb{N}$, the exponential $n^{\mathrm{y}}$ can be thought of as the Yoneda embedding of the set with n elements, i.e.,

$$n^{\mathrm{y}}=\mathtt{FSet}(-,\underline{n})$$

where $\underline{n}=\{1,\dots ,n\}$. (For typographical convenience, we sometimes use the notation n and $\underline{n}$ interchangeably. In particular, we write e.g., $d\left(0\right)$ instead of $d\left(\underline{0}\right)$). Then the addition of exponentials corresponds to the coproduct of the corresponding representable functors (and so multiplication by a natural number $a_n$ corresponds to the $a_n$-fold coproduct of the representable functor with itself). This means that evaluating a Dirichlet polynomial at some natural number n corresponds to evaluating the corresponding functor on the finite set $\underline{n}$.

Note that $0^{\mathrm{y}}$ is not the initial object 0, since

$$0^{\underline{n}}=\left\{\begin{array}{cc}1\hfill & \mathrm{if}n=0;\hfill \\ 0\hfill & \mathrm{if}n⩾1\hfill \end{array}\right.$$

i.e., $0^{\mathrm{y}}\ne 0$.

Example 1.

The Dirichlet polynomial

$$d\left(\mathrm{y}\right)=4^{\mathrm{y}}+4·1^{\mathrm{y}}$$

evaluated at 0 gives

$$\begin{array}{cc}\hfill d\left(0\right)& =\mathtt{FSet}(\underline{0},\underline{4})\bigsqcup \left({\bigsqcup }_{i=1}^4\mathtt{FSet}(\underline{0},\underline{1})\right)\hfill \\ & \cong \underline{1}\bigsqcup \underline{4}\hfill \\ & \cong \underline{5},\hfill \end{array}$$

and, similarly,

$$\begin{array}{cc}\hfill d\left(1\right)& =\mathtt{FSet}(\underline{1},\underline{4})\bigsqcup \left({\bigsqcup }_{i=1}^4\mathtt{FSet}(\underline{1},\underline{1})\right)\hfill \\ & \cong \underline{4}\bigsqcup \underline{4}\hfill \\ & \cong \underline{8}.\hfill \end{array}$$

Note that, since $1^{\mathrm{y}}=1$, we can write $d\left(\mathrm{y}\right)=4^{\mathrm{y}}+4$.

Definition 2.

A morphism $\phi :d\to e$ of Dirichlet polynomials is a natural transformation of (contravariant) functors. Denote by $\mathtt{Dir}$ the category of Dirichlet polynomials (thought of as functors ${\mathtt{FSet}}^{\mathrm{o}\mathrm{p}}\to \mathtt{FSet}$), and by $\mathtt{Dir}(d,e)$ the set of all morphisms $d\to e$.

When we think of Dirichlet polynomials as functors ${\mathtt{FSet}}^{\mathrm{o}\mathrm{p}}\to \mathtt{FSet}$, addition is given by the coproduct (disjoint union of sets), and multiplication by the product (Cartesian product of sets). This means that working with Dirichlet polynomials in $\mathtt{Dir}$ really is like working with polynomials, in the sense that addition and multiplication are exactly “as expected”.

Example 2.

The only slightly confusing aspect of multiplication in $\mathsf{Dir}$ is how $0^{\mathrm{y}}$ behaves (since $0^{\mathrm{y}}\ne 0$): if $d\left(\mathrm{y}\right)$ is a Dirichlet polynomial, then

$$d\left(\mathrm{y}\right)·0^{\mathrm{y}}=d\left(0\right)·0^{\mathrm{y}},$$

as follows from the aforementioned fact that $0^{\underline{n}}$ is zero for $n\ne 0$, and 1 for $n=0$.

We can use this general fact for specific computations. For example, let

$$\begin{array}{cc}\hfill d\left(\mathrm{y}\right)& :=3·2^{\mathrm{y}}+1^{\mathrm{y}}\hfill \\ \hfill e\left(\mathrm{y}\right)& :=4^{\mathrm{y}}+2^{\mathrm{y}}+3·0^{\mathrm{y}}\hfill \end{array}$$

Then

$$\begin{array}{cc}\hfill (d·e)\left(\mathrm{y}\right)& =(3·8^{\mathrm{y}}+3·4^{\mathrm{y}}+9·0^{\mathrm{y}})+(4^{\mathrm{y}}+2^{\mathrm{y}}+3·0^{\mathrm{y}})\hfill \\ & =3·8^{\mathrm{y}}+4·4^{\mathrm{y}}+2^{\mathrm{y}}+12·0^{\mathrm{y}}.\hfill \end{array}$$

(and $d+e=4^{\mathrm{y}}+4·2^{\mathrm{y}}+1^{\mathrm{y}}+3·0^{\mathrm{y}}$).

There is a more geometric interpretation of objects of $\mathsf{Dir}$ as set-theoretic bundles, i.e., (isomorphism classes of) functions $E\to B$, where $E,B\in \mathtt{FSet}$, given as follows: to the Dirichlet polynomial $d:{\mathtt{FSet}}^{\mathrm{o}\mathrm{p}}\to \mathtt{FSet}$, we associate the function ${\pi }_d=d(!):d\left(1\right)\to d\left(0\right)$ induced by the unique function $!:\underline{0}\to \underline{1}$. (This vague statement can be upgraded to an equivalence of categories: ([1], [Theorem 4.6]) for more details).

For example, to the polynomial $d\left(\mathrm{y}\right)=4^{\mathrm{y}}+4·1^{\mathrm{y}}$, we associate the bundle

Note that bundles also form a rig, where the sum is given by disjoint union of sets, and the product is given by the Cartesian product of sets, both on the base and the total space. Further, the equivalence between Dirichlet polynomials and bundles respects the rig structures (cf. [1], Theorem 4.6). Because of this, we often switch freely between thinking of Dirichlet polynomials as functors $d:{\mathtt{FSet}}^{\mathrm{o}\mathrm{p}}\to \mathtt{FSet}$, as bundles ${\pi }_d:d\left(1\right)\to d\left(0\right)$, and simply as functions of the form ${\sum }_{j=0}^n{a}_j·j^{\mathrm{y}}$.

Example 3.

We can draw the bundle corresponding to $(2^{\mathrm{y}}+1)·(2^{\mathrm{y}}+1)$ as follows:

Lemma 1.

Let $d\left(\mathrm{y}\right){\sum }_{j=0}^n{a}_j·j^{\mathrm{y}}$ be a Dirichlet polynomial. Then

$$\begin{array}{cc}\hfill \left|d\right(0\left)\right|& ={\sum }_{j=0}^n{a}_j\hfill \\ \hfill \left|d\right(1\left)\right|& ={\sum }_{j=0}^n{a}_{j}j.\hfill \end{array}$$

Proof. 

This follows from the fact that $n^{\underline{0}}=1$ and $n^{\underline{1}}=n$, for all $n\in \mathbb{N}$. □

Definition 3.

Let $d\in \mathsf{Dir}$. For $i\in d\left(0\right)$, we define

$$d\left[i\right]{\pi }_d^{-1}\left(i\right)$$

where ${\pi }_d:d\left(1\right)\to d\left(0\right)$ is the bundle corresponding to d.

Using the fact that the sum of bundles is given by the disjoint union of sets, we can use this above definition to write any Dirichlet polynomial d as

$$d\left(\mathrm{y}\right)\cong \sum _{i\in d\left(0\right)}d{\left[i\right]}^{\mathrm{y}}$$

(where ∑ is the coproduct in $\mathtt{FSet}$).

Corollary 1.

Let $d\left(\mathrm{y}\right):={\sum }_{i\in d\left(0\right)}d{\left[i\right]}^{\mathrm{y}}$ be a Dirichlet polynomial. Then

$$\left|d\left(1\right)\right|={\sum }_{i\in d\left(0\right)}\left|d\left[i\right]\right|.$$

Proof. 

This is, again, simply the fact that $n^{\underline{1}}=n$ for all $n\in \mathbb{N}$. □

Lemma 2.

A morphism $\phi :d\to e$ of Dirichlet polynomials is exactly a morphism of the corresponding bundles, i.e., functions ${\phi }_0:d\left(0\right)\to e\left(0\right)$ and ${\phi }_1:d\left(1\right)\to e\left(1\right)$ such that

commutes.

Proof. 

This statement forms a specific part of ([1], Theorem 4.6), but the proof is simple enough that we give a direct version here. Writing $d\left(\mathrm{y}\right){\sum }_{i\in d\left(0\right)}d{\left[i\right]}^{\mathrm{y}}$ and $e\left(\mathrm{y}\right){\sum }_{i\in e\left(0\right)}e{\left[i\right]}^{\mathrm{y}}$, we see that

$$\begin{array}{cc}\hfill {Hom}_{[{\mathtt{FSet}}^{\mathrm{o}\mathrm{p}},\mathtt{FSet}]}(d,e)& \cong \prod _{i\in d\left(0\right)}{Hom}_{[{\mathtt{FSet}}^{\mathrm{o}\mathrm{p}},\mathtt{FSet}]}\left(d{\left[i\right]}^{\mathrm{y}},\sum _{j\in e\left(0\right)}e{\left[j\right]}^{\mathrm{y}}\right)\hfill \\ & \cong \prod _{i\in d\left(0\right)}\sum _{j\in e\left(0\right)}e{\left[j\right]}^{d\left[i\right]}\hfill \\ & =\prod _{i\in d\left(0\right)}\sum _{j\in e\left(0\right)}{Hom}_{\mathtt{FSet}}(d\left[i\right],e\left[j\right])\hfill \end{array}$$

(the first isomorphism is by the universal property of the coproduct; the second isomorphisms is the Yoneda lemma). However, an element of this set is exactly a bundle morphism: we have, for all $i\in d\left(0\right)$, some $j\in e\left(0\right)$ along with a function $d\left[i\right]\to e\left[j\right]$; ${\phi }_1$ is given by the disjoint union of all these $d\left[i\right]\to e\left[j\right]$, and ${\phi }_0$ is given by the the choice of j for each i. □

Definition 4.

Given Dirichlet polynomials $d,e\in \mathtt{Dir}$ such that $d\left(0\right)=e\left(0\right)$, we denote by ${\mathtt{Dir}}_{/d\left(0\right)}(d,e)$ the set of morphisms $({\phi }_0,{\phi }_1):d\to e$ such that ${\phi }_0=id$.

Given the correspondence between Dirichlet polynomials and bundles, we might rightly ask why we should prefer to work with the former over the latter. For one possible answer to this, see Section 6.

3. Bundles as Empirical Distributions

The interpretation of Dirichlet polynomials as bundles helps us to understand how they relate to probability theory. Imagine flipping a coin eight times and observing five heads and three tails; we refer to “heads” and “tails” as outcomes, and each of the eight flips as draws; every draw has an associated outcome.

Consider some bundle ${\pi }_d:d\left(1\right)\to d\left(0\right)$. We can think of $d\left(0\right)$ as the set of outcomes, and $d\left(1\right)$ as the set of draws; the fibre ${\pi }_d^{-1}\left(x\right)$ over an outcome $x\in d\left(0\right)$ corresponds to all the draws that lead to the outcome x, and so we obtain a probability distribution on $d\left(0\right)$ by setting $\mathbb{P}(X=x)=\frac{|{\pi }_d^{-1}\left(x\right)|}{\left|d\right(0\left)\right|}$. Conversely, any rational distribution (i.e., a distribution such that all probabilities are rational numbers ) on a finite set arises in this way: take the finite set as the set of outcomes; take the least common multiple of the denominators of all the probabilities as the cardinality of $d\left(1\right)$; and then take $\mathbb{P}(X=x)·\left|d\right(1\left)\right|$ many elements of $d\left(1\right)$ to be in the fibre of $x\in d\left(0\right)$.

Example 4.

Consider the set $S=\{x_1,x_2,x_3,x_4\}$, endowed with the probability distribution such that

$$\begin{array}{cc}\hfill \mathbb{P}\left(x_1\right)& =\frac{1}{5}\mathbb{P}\left(x_2\right)=\frac{1}{6}\hfill \\ \hfill \mathbb{P}\left(x_3\right)& =\frac{1}{2}\mathbb{P}\left(x_4\right)=\frac{2}{15}\hfill \end{array}$$

Define the sets $d\left(0\right)=\underline{4}$ and $d\left(1\right)=\underline{30}$, and define the function ${\pi }_d:d\left(1\right)\to d\left(0\right)$ by

$$\pi \left(n\right)=\left\{\begin{array}{cc}1\hfill & if0⩽n<6;\hfill \\ 2\hfill & if6⩽n<11;\hfill \\ 3\hfill & if11⩽n<26;\hfill \\ 4\hfill & if26⩽n<30.\hfill \end{array}\right.$$

Then the empirical probability distribution on the bundle $\pi :d\left(1\right)\to d\left(0\right)$ agrees exactly with the given distribution on S. As a Dirichlet polynomial, this bundle is given (up to relabelling the outcomes) by $d\left(\mathrm{y}\right):={15}^{\mathrm{y}}+6^{\mathrm{y}}+5^{\mathrm{y}}+4^{\mathrm{y}}$.

Note that any multiple $m^{\mathrm{y}}·d\left(\mathrm{y}\right)$ of d (for $m⩾1$) will correspond to the same probability distribution as d itself, but to a different empirical distribution, since it will have m times as many draws.

Under this interpretation of Dirichlet polynomials as empirical distributions, multiplication $d·e$ corresponds to taking the product distribution.

Remark 1.

For any $d\in \mathsf{Dir}$, and any $n\in \mathbb{N}$, we can give $\left|d\right(n\left)\right|$ a combinatorial interpretation: it is the number of ways of choosing n indistinguishable (in the sense that they have the same outcome) draws, i.e., the number of length-n lists of elements of $d\left[i\right]$ for some $i\in d\left(0\right)$.

To see this, note that $d\left(n\right)=\mathtt{Dir}(n^{\mathrm{y}},d)$ (by Yoneda), and so $d\left(n\right)$ is in bijection with the set of bundle morphisms $({\phi }_0,{\phi }_1):(n\to 1)\to (d\left(1\right)\to d\left(0\right))$, which are given exactly by choosing n (possibly repeated) elements of $d\left(1\right)$ that all lie in the same fibre (namely the fibre above the point specified by ${\phi }_0\left(1\right)$).

Remark 2.

Although we deal only with finite sets and rational probability distributions here, it seems likely that one could follow the methods of [3] and consider colimits of these to obtain analogous results for arbitrary probability distributions on discrete measurable spaces.

4. Area and Width

Definition 5.

Define the rig $\mathsf{Rect}$ as follows. The underlying set is ${\mathbb{R}}_{⩾0}\times {\mathbb{R}}_{⩾0}$. The multiplicative structure has unit $(1,1)$, and is given by component-wise multiplication:

$$(A_1,W_1)·(A_2,W_2):=(A_1{A}_2,W_1{W}_2).$$

The additive structure has unit $(0,0)$, and is given by real-number addition in the first component, and by weighted geometric mean in the second component:

$$(A_1,W_1)+(A_2,W_2):=\left(A_1+A_2,{\left(W_1^{A_1}{W}_2^{A_2}\right)}^{\frac{1}{A_1+A_2}}\right).$$

Given an element $(A,W)$ in $\mathsf{Rect}$, we call A its area and W its width.

The fact that $\mathsf{Rect}$ is indeed a rig follows from the fact that its multiplication distributes over its addition:

$$\begin{array}{cc}\hfill (A_1,W_1)·\left((A_2,W_2)+(A_3,W_3)\right)& =(A_1,W_1)·\left(A_2+A_3,{\left(W_2^{A_2}{W}_3^{A_3}\right)}^{\frac{1}{A_2+A_3}}\right)\hfill \\ & =\left(A_1(A_2+A_3),W_1{\left(W_2^{A_2}{W}_3^{A_3}\right)}^{\frac{1}{A_2+A_3}}\right)\hfill \\ & =\left(A_1{A}_2+A_1{A}_3,{\left(W_1^{A_2+A_3}{W}_2^{A_2}{W}_3^{A_3}\right)}^{\frac{1}{A_2+A_3}}\right)\hfill \\ & =\left(A_1{A}_2+A_1{A}_3,{\left({\left(W_1{W}_2\right)}^{A_2}{\left(W_1{W}_3\right)}^{A_3}\right)}^{\frac{1}{A_2+A_3}}\right)\hfill \\ & =\left(A_1{A}_2+A_1{A}_3,{\left({\left(W_1{W}_2\right)}^{A_1{A}_2}{\left(W_1{W}_3\right)}^{A_1{A}_3}\right)}^{\frac{1}{A_1{A}_2+A_1{A}_3}}\right)\hfill \\ & =(A_1{A}_2,W_1{W}_2)+(A_1{A}_3,W_1{W}_3)\hfill \\ & =(A_1,W_1)·(A_2,W_2)+(A_1,W_1)·(A_3,W_3).\hfill \end{array}$$

Proposition 1.

There exists a unique rig morphism $h:\mathsf{Dir}\to \mathsf{Rect}$ for which

$$h:n^{\mathrm{y}}\mapsto (n,n).$$

Proof. 

Since every Dirichlet polynomial is just a sum of exponentials, a rig homomorphism is fully determined by its action on exponentials, since it must respect addition. So we just need to show that h does indeed extend to a rig homomorphism, but this follows from the fact that $m^{\mathrm{y}}·n^{\mathrm{y}}={(m·n)}^{\mathrm{y}}$. □

Definition 6.

Given a Dirichlet polynomial d, we define its area $A\left(d\right)$ and its width $W\left(d\right)$ to be given by the components of $h\left(d\right)=\left(A\right(d),W(d\left)\right)$.

With this definition, along with Proposition 1, we see that

$$A\left(n^{\mathrm{y}}\right)=W\left(n^{\mathrm{y}}\right)=n.$$

Lemma 3.

Let $d\in \mathsf{Dir}$ and $a\in \mathbb{N}$. Then

1. 

$h\left(a\right)=(a,1)$;

2. 

$A(a·d)=aA\left(d\right)$;

3. 

$W(a·d)=W\left(d\right)$.

Proof. 

Recall that addition (and thus scalar multiplication) in $\mathsf{Rect}$ involves the weighted geometric mean in the second component. Then

$$\begin{array}{cc}h\left(a\right)& :=h(a·1^{\mathrm{y}})\hfill \\ & =a·h\left(1^{\mathrm{y}}\right)\hfill \\ & =a·(1,1)\hfill \\ & =(a,1)\hfill \end{array}$$

which proves (i). For (ii) and (iii), since h is a rig homomorphism (and thus respects addition), it suffices to consider the case where d is an exponential, say $d\left(\mathrm{y}\right)=n^{\mathrm{y}}$. However, then

$$\begin{array}{cc}\hfill h(a·d)& =a·h\left(d\right)\hfill \\ & =a·(n,n)\hfill \\ & =\left(an,{\left(\underset{atimes}{\underbrace{n^n{n}^n\dots n^n}}\right)}^{1/an}\right)\hfill \\ & =\left(an,{\left(n^{an}\right)}^{1/an}\right)\hfill \\ & =(an,n)\hfill \end{array}$$

i.e., $A(a·d)=aA\left(d\right)$ and $W(a·d)=W\left(d\right)$, as claimed. □

Corollary 2.

Let $d\in \mathsf{Dir}$. Then

$$\begin{array}{cc}\hfill A\left(d\right)& =\left|d\right(1\left)\right|\hfill \\ \hfill W{\left(d\right)}^{A\left(d\right)}& =\left|{\mathtt{Dir}}_{/d\left(0\right)}(d,d)\right|.\hfill \end{array}$$

Proof. 

Write $d\left(\mathrm{y}\right)=a_n·n^{\mathrm{y}}+\dots +a_1·1^{\mathrm{y}}+a_0·0^{\mathrm{y}}$. Using Lemma 3, along with Definition 5, we see that

$$\begin{array}{cc}\hfill h\left(d\right)& =(a_{n}n,n)+(a_{n-1}(n-1),n-1)+\dots +(a_1,1)\hfill \\ & =\left({\sum }_{i=0}^n{a}_{i}i,{\left({\prod }_{i=0}^n{i}^{a_{i}i}\right)}^{1/{\sum }_{i=0}^n{a}_{i}i}\right).\hfill \end{array}$$

By Lemma 1, the first component (i.e., $A\left(d\right)$) is equal to $\left|d\right(1\left)\right|$; by the same lemma, we can also rewrite the second component (i.e., $W\left(d\right)$) as

$$W\left(d\right)={\left({\prod }_{i=0}^n{i}^{a_{i}i}\right)}^{\frac{1}{A\left(d\right)}}$$

so it simply remains to justify why this is equal to ${\left|{\mathtt{Dir}}_{/d\left(0\right)}(d,d)\right|}^{\frac{1}{A\left(d\right)}}$. But a morphism in ${\mathtt{Dir}}_{/d\left(0\right)}(d,d)$ is exactly the data of an endomorphism of each fibre of ${\pi }_d:d\left(1\right)\to d\left(0\right)$; since there are $a_i$ fibres of size i, endomorphisms of these fibres are in bijection with the $a_i$-fold product of $i^i$, which is equal to $i^{a_{i}i}$, whence the claim. □

Corollary 3.

Let $d\in \mathsf{Dir}$. Then the width $W\left(d\right)$ is an algebraic number, i.e., the image of $h:\mathsf{Dir}\to \mathsf{Rect}$ lies in the sub-rig whose underlying set is $\mathbb{N}\times {\overline{\mathbb{Q}}}_{⩾0}$, where $\overline{\mathbb{Q}}$ is the algebraic closure of $\mathbb{Q}$.

Proof. 

By Corollary 2, both $W{\left(d\right)}^{A\left(d\right)}$ and $A\left(d\right)$ are equal to the cardinality of some sets, and thus integer. □

Example 5.

Reassuringly, if we start with a “rectangle”, then the area and width are exactly what we might expect. More concretely: consider $d\left(\mathrm{y}\right)=a·n^{\mathrm{y}}$ for some $a,n\in \mathbb{N}$; then, by Corollary 2,

$$A\left(d\right)=d\left(1\right)=an,$$

and, by direct calculation,

$$W\left(d\right)=n.$$

Comparing this to the picture of $a·n^{\mathrm{y}}$, we can explain why we chose the terminology “width” and “area”:

Indeed, the area is exactly the number of dots in the (upper) rectangle, and the width is its width.

However, this picture now leads us to consider the question of whether or not there is a good meaning we can give to the “length” of this rectangle (which, here, should be equal to a). Indeed, this has been our motivation all along; we will return to this question in Example 9.

Example 6.

The fact that $d\left(1\right)$ is “rectangular” in Example 5 makes the terminology look like a numerical coincidence, but we can try to hone our intuition of what this really “means” by considering another example.

Let’s consider $d\left(\mathrm{y}\right)=4^{\mathrm{y}}+4$, which has area $A\left(d\right)=d\left(1\right)=8$. We can calculate its width by using the fact that

$$\begin{array}{cc}\hfill h\left(4^{\mathrm{y}}\right)& =(4,4)\hfill \\ \hfill h\left(4\right)& =h\left(1^{\mathrm{y}}\right)+h\left(1^{\mathrm{y}}\right)+h\left(1^{\mathrm{y}}\right)+h\left(1^{\mathrm{y}}\right)\hfill \\ & =(4,1)\hfill \end{array}$$

whence

$$\begin{array}{cc}\hfill h\left(d\right)& =(4,4)+(4,1)\hfill \\ & =\left(8,{\left(4^4{1}^4\right)}^{\frac{1}{8}}\right)\hfill \\ & =(8,2)\hfill \end{array}$$

and so $W\left(d\right)=2$.

How, then, does the rectangle with area 8 and width 2 relate to our Dirichlet polynomial $d\left(\mathrm{y}\right)=4^{\mathrm{y}}+4$? That is, what is the process that takes us from d to $4·2^{\mathrm{y}}$? Looking at the pictures of the bundles, we see that the width tells us how our bundle would look if we had the same set ($d\left(1\right)$) of draws, but with different outcomes, now all equally likely:

Note that, in order to have equally sized fibres, we needed to have 4 outcomes, not 5 (since $8/2=4$). We make this idea more precise (as well as explain why the rectangle is of size $4\times 2$ instead of $2\times 4$) in Section 6.

Example 7.

We have just seen that $d\left(\mathrm{y}\right)=4^{\mathrm{y}}+4$ has $W\left(d\right)=2$ and $A\left(d\right)=8$, but now let’s look at an example where the numbers don’t divide so neatly.

Let $d\left(\mathrm{y}\right)=4^{\mathrm{y}}+3$. Then $A\left(d\right)=d\left(1\right)=7$, and, as in Example 6, we use the fact that

$$\begin{array}{cc}\hfill h\left(d\right)& =(4,4)+(3,1)\hfill \\ & =\left(7,{\left(4^4{1}^3\right)}^{\frac{1}{7}}\right)\hfill \\ & =(7,2\sqrt[7]{2})\hfill \\ & \approx (7,2.21)\hfill \end{array}$$

Of course, now we can’t draw a nice rectangle representing the evenly distributed bundle as we did in Example 6 for $4^{\mathrm{y}}+4$, since we would have to have an outcome set of size $7/2.21\approx 3.17$ elements, with fibres all of size $2.21$, but this should come as no surprise, since 7 is prime. One might be tempted to solve this problem using groupoid cardinality (cf. [4]), but there are some technical issues here.

5. Length

Remark 3.

We write log to mean ${log}_2$.

Definition 7.

Given a Dirichlet polynomial $d\left(\mathrm{y}\right):={\sum }_{i\in d\left(0\right)}d{\left[i\right]}^{\mathrm{y}}$, we define its entropy $H\left(d\right)$ by

$$H\left(d\right):=-\sum _{i\in d\left(0\right)}\frac{\left|d\right[i\left]\right|}{\left|d\right(1\left)\right|}log\left(\frac{\left|d\right[i\left]\right|}{\left|d\right(1\left)\right|}\right).$$

We then define its length (also called the perplexity) $L\left(d\right)$ by

$$L\left(d\right):=2^{H\left(d\right)}.$$

Readers might recognise $H\left(d\right)$ as being the Shannon entropy of the corresponding probability distribution (cf. [5]). The convention for naming the sides of a rectangle is from [6] (Figure 1).

Example 8.

Consider $d\left(\mathrm{y}\right)=n^{\mathrm{y}}$ for some $n\in \mathbb{N}$.

Then $d\left(0\right)=1$ and $d\left(1\right)=n$, and so

$$\begin{array}{cc}\hfill H\left(d\right)& =-\sum _{i\in \underline{1}}\frac{n}{n}log\left(\frac{n}{n}\right)\hfill \\ & =-log1\hfill \\ & =0\hfill \end{array}$$

whence $L\left(d\right)=2^0=1$.

In terms of distributions, this corresponds to the fact that the unique probability distribution on a single outcome has entropy equal to 0 (and so the same is true for any empirical distribution on a single outcome).

Example 9.

Continuing on from Example 5, we can calculate the entropy of a uniform distribution on a many outcomes $d\left(\mathrm{y}\right)=a·n^{\mathrm{y}}$ as

$$\begin{array}{cc}\hfill H(a·n^{\mathrm{y}})& =-\sum _{i\in \underline{a}}\frac{n}{an}log\left(\frac{n}{an}\right)\hfill \\ & =-log\left(\frac{1}{a}\right)\hfill \\ & =loga\hfill \end{array}$$

whence $L(a·n^{\mathrm{y}})=2^{loga}=a$, exactly as desired.

Example 10.

Continuing on from Example 7, recall that $d\left(\mathrm{y}\right)=4^{\mathrm{y}}+4$ has area $A\left(d\right)=8$ and width $W\left(d\right)=2$. We can further calculate that

$$\begin{array}{cc}\hfill H\left(d\right)& =-\sum _{i\in \underline{5}}\frac{\left|d\right[i\left]\right|}{8}log\left(\frac{\left|d\right[i\left]\right|}{8}\right)\hfill \\ & =-\frac{4}{8}log\left(\frac{4}{8}\right)-4·\frac{1}{8}log\left(\frac{1}{8}\right)\hfill \\ & =-\frac{1}{2}log\left(\frac{1}{16}\right)\hfill \\ & =2\hfill \end{array}$$

whence $L\left(d\right)=2^2=4$.

As for $d\left(\mathrm{y}\right)=4^{\mathrm{y}}+3$, recall that its area is $A\left(d\right)=7$ and its width is $2\sqrt[7]{2}$. Now, its entropy is

$$\begin{array}{cc}\hfill H\left(d\right)& =-\sum _{i\in \underline{4}}\frac{\left|d\right[i\left]\right|}{7}log\left(\frac{\left|d\right[i\left]\right|}{7}\right)\hfill \\ & =-\frac{4}{7}log\left(\frac{4}{7}\right)-3·\frac{1}{7}log\left(\frac{1}{7}\right)\hfill \\ & =\frac{log7}{log2}-\frac{8}{7}\hfill \end{array}$$

and so its length is

$$L\left(d\right)=2^{\frac{log7}{log2}-\frac{8}{7}}=\frac{7}{2\sqrt[7]{2}}.$$

Note that, in the above example, even though both $L\left(d\right)$ and $W\left(d\right)$ have non-integer values, the formula implied by our choice of nomenclature still holds: the area $A\left(d\right)$ is equal to the length $L\left(d\right)$ times the width $W\left(d\right)$. This leads us to our main theorem. It says that the Shannon entropy, which is only homomorphic in products of distributions, can be computed in terms of the width and area, which together are homomorphic in both sums and products of distributions. We will explain this in more detail in Section 6.

Theorem 1.

For all $d\in \mathsf{Dir}$, we have the rectangle-area formula

$$A\left(d\right)=L\left(d\right)W\left(d\right).$$

Proof. 

In the following, we omit absolute value signs, writing e.g., $d\left(1\right)$ instead of $\left|d\right(1)$.

First, write

$$d\left(\mathrm{y}\right):=\sum _{j=0}^n{a}_j{j}^{\mathrm{y}}\cong \sum _{i\in d\left(0\right)}d{\left[i\right]}^{\mathrm{y}}.$$

Now we can rewrite the length as

$$\begin{array}{cc}\hfill L\left(d\right)& =2^{H\left(d\right)}\hfill \\ & =2^{-{\sum }_{i\in d\left(0\right)}\frac{d\left[i\right]}{d\left(1\right)}log\left(\frac{d\left[i\right]}{d\left(1\right)}\right)}\hfill \\ & =\prod _{i\in d\left(0\right)}{2}^{-\frac{d\left[i\right]}{d\left(1\right)}log\left(\frac{d\left[i\right]}{d\left(1\right)}\right)}\hfill \\ & =\prod _{i\in d\left(0\right)}{\left(2^{-log\left(\frac{d\left[i\right]}{d\left(1\right)}\right)}\right)}^{\frac{d\left[i\right]}{d\left(1\right)}}\hfill \\ & =\prod _{i\in d\left(0\right)}{\frac{d\left(1\right)}{d\left[i\right]}}^{\frac{d\left[i\right]}{d\left(1\right)}}\hfill \\ & =\frac{{\prod }_{i\in d\left(0\right)}d{\left(1\right)}^{\frac{d\left[i\right]}{d\left(1\right)}}}{{\prod }_{i\in d\left(0\right)}d{\left[i\right]}^{\frac{d\left[i\right]}{d\left(1\right)}}}\hfill \end{array}$$

The numerator is then

$$\begin{array}{cc}\hfill {\prod }_{i\in d\left(0\right)}d{\left(1\right)}^{\frac{d\left[i\right]}{d\left(1\right)}}& =d{\left(1\right)}^{{\sum }_{i\in d\left(0\right)}\frac{d\left[i\right]}{d\left(1\right)}}\hfill \\ & =d\left(1\right)\hfill \\ & =A\left(d\right)\hfill \end{array}$$

since ${\sum }_{i\in d\left(0\right)}\left|d\left[i\right]\right|=\left|d\left(1\right)\right|$, by Corollary 1, and we can then apply Corollary 2. The denominator is exactly

$${\left({\prod }_{i\in d\left(0\right)}d{\left[i\right]}^{d\left[i\right]}\right)}^{\frac{1}{d\left(1\right)}}$$

and so, by Corollary 2, we only need to justify why ${\prod }_{i\in d\left(0\right)}d{\left[i\right]}^{d\left[i\right]}$ is equal to $|{\mathtt{Dir}}_{/d\left(0\right)}(d,d)|$. However, this follows from the definition of an element of the latter set: a choice of map $d\left[i\right]\to d\left[i\right]$ for all $i\in d\left(0\right)$. □

6. Interpreting Area, Length, and Width

We have mentioned many times that Dirichlet polynomials are equivalent to set-theoretic bundles, so the natural question to ask is “why, then, should we work with the former instead of the latter?”. One answer to this is question is the fact that entropy does not respect bundle morphisms: we cannot functorially assign a morphism between entropies to morphisms, since we are working with arbitrary morphisms of bundles. (If, however, we restrict to only morphisms given by pushforward, then [7] tells us (via Faddeev’s theorem) that the only possible functorial definition of entropy is given by the relative entropy, i.e., the difference of the entropies of the source and the target). This makes it seem rather bad to work with a category (such as that of bundles) instead of simply a rig (such as that of Dirichlet polynomials). Of course, this isn’t an entirely satisfactory answer, since we do care about the notion of morphisms for Dirichlet polynomials (for example, Corollary 2 tells us that the width can be expressed in terms of the number of certain morphisms). In light of Theorem 1, however, we might consider the following possibility: both area and length can be expressed in terms of $d\left(0\right)$, $d\left(1\right)$, and $d\left[i\right]$ (for $i\in d\left(0\right)$), and we could define the width by $W\left(d\right)A\left(d\right)/L\left(d\right)$.

A better answer to this question might be the following: the rig homomorphism $h:\mathsf{Dir}\to \mathsf{Rect}$ is incredibly simple, since it just maps $n^{\mathrm{y}}$ to $(n,n)$; from this computationally simple homomorphism, however, we can recover entropy (as $log\left(A\right(d)/W(d\left)\right)$), without making any reference to the classical equation that defines it (“negative the sum of probabilities of the log of the probabilities”), but instead relying on the fact that $\mathsf{Rect}$ encodes the weighted geometric mean. That is, $H\left(d\right)$ is only homomorphic in the product of distributions, whereas the pair $\left(A\right(d),W(d\left)\right)$ is homomorphic in both the product and the sum.

Now, the entropy $H\left(d\right)=logL\left(d\right)$ can be understood (via Huffman coding, cf. [8]) as the average number of bits needed to code a single outcome (over a long enough message). What is also true, however, is that the width (which is obtained purely “algebraically”, i.e., from the rig homomorphism $h:\mathsf{Dir}\to \mathsf{Rect}$) gives similar information: by Theorem 1, combined with the previous sentence, $logW\left(d\right)$ is the average number of bits needed to code the draw, given an outcome (in the same Huffman coding as before). This answers the question of “what is special about the bundle defined by the width and length” with “it describes the optimal encoding of draws, given outcomes”.

As for the picture in Example 6, we can now understand the hand-wavy explanation a bit better (but still just as hand-wavy-ly): we take our original “half-filled” rectangle $d\left(1\right)$ and pour its contents into a new rectangle, of length $L\left(d\right)$, and then “slosh the contents around” until they lie flat, and then put a lid on it; the rectangle will be perfectly filled up, and the placement of the lid will be given by $W\left(d\right)$.

We also mentioned, in Corollary 3, that the width $W\left(d\right)$ of any Dirichlet polynomial d is an algebraic number, but the actual result is slightly more interesting that this: Corollary 2 tells us that $W{\left(d\right)}^{A\left(d\right)}$ is equal to the cardinality of the set ${\mathtt{Dir}}_{/d\left(0\right)}(d,d)$. We already know how to understand endomorphisms of d that fix $d\left(0\right)$ as endomorphisms of $d\left(1\right)$ that fix the outcome; we can understand $W{\left(d\right)}^{A\left(d\right)}$ as maps from $A\left(d\right)$ to $W\left(d\right)$; roughly speaking, such a map $f:A\left(d\right)\to W\left(d\right)$ determines the remaining ambiguity in determining a draw, given its outcome.

7. Cross Entropy

Everything above can be viewed as a specific example of the analogous cross notions. That is, given two Dirichlet polynomials, we can define their cross area, cross width, etc. as follows.

Definition 8.

Let $d,e\in \mathsf{Dir}$ be Dirichlet polynomials such that $d\left(0\right)=e\left(0\right)$. Then we define thecross entropy $H(d,e)$ by

$$H(d,e)=-\sum _{i\in d\left(0\right)}\frac{\left|d\right[i\left]\right|}{\left|d\right(1\left)\right|}log\left(\frac{\left|e\right[i\left]\right|}{\left|e\right(1\left)\right|}\right)$$

and the cross area, cross width, and cross length by

$$\begin{array}{cc}\hfill A(d,e):=& \left|e\right(1\left)\right|\hfill \\ \hfill W(d,e):=& {\left|{\mathtt{Dir}}_{/d\left(0\right)}(d,e)\right|}^{\frac{1}{\left|d\right(1\left)\right|}}\hfill \\ \hfill L(d,e):=& 2^{H(d,e)}\hfill \end{array}$$

(respectively).

By definition, $X(d,d)=X\left(d\right)$ for $X\in \{A,W,H,L\}$. That is, just as cross entropy is a generalisation of entropy, the notions of cross width, etc., generalise the notions of width, etc.

Remark 4.

Note that we can recover the notion of relative entropy (also known as Kullback–Leibler divergence) $D_{\mathrm{KL}}(p\parallel q)$, as studied in [9], from cross entropy:

$$H(d,e)=H\left(d\right)+D_{\mathrm{KL}}(p\parallel q)$$

(which can also be seen to justify the fact that $H(d,d)=H\left(d\right)$).

Remark 5.

Although we have some idea of how to understand these cross notions (e.g., cross area can be understood as the number of “actual” draws, when we think of d as being a potentially inaccurate model for e), the choice of definitions in Definition 8 was chosen simply so that

1. 

we recover the “uncrossed” notions when we take $d=e$, and

2. 

Theorem 2 holds.

Theorem 2.

For all $d,e\in \mathsf{Dir}$, we have the cross rectangle-area formula

$$A(d,e)=L(d,e)W(d,e).$$

Proof. 

This proof follows exactly the same argument as the proof of Theorem 1. □