Feeds:
Posts

## Update

I put up a post over at the StackOverflow blog describing a little of what I’ve been up to this summer.

Curiously enough, the Zipf distribution which shows up in that post is the same as the zeta distribution that shows up when trying to motivate the definition of the Riemann zeta function. I’m sure there is a conceptual explanation of this connection somewhere, probably coming from statistical mechanics, but I don’t know it. I suppose the approximate scale invariance of the zeta distribution is relevant to its appearance in many real-life statistics, as described in Terence Tao’s blog post on the subject here.

Read Full Post »

## A little more about zeta functions and statistical mechanics

In the previous post we described the following result characterizing the zeta distribution.

Theorem: Let $a_n = \mathbb{P}(X = n)$ be a probability distribution on $\mathbb{N}$. Suppose that the exponents in the prime factorization of $n$ are chosen independently and according to a geometric distribution, and further suppose that $a_n$ is monotonically decreasing. Then $a_n = \frac{1}{\zeta(s)} \left( \frac{1}{n^s} \right)$ for some real $s > 1$.

I have been thinking about the first condition, and I no longer like it. At least, I don’t like how I arrived at it. Here is a better way to conceptualize it: given that $n | X$, the probability distribution on $\frac{X}{n}$ should be the same as the original distribution on $X$. By Bayes’ theorem, this is equivalent to the condition that

$\displaystyle \frac{a_{mn}}{a_n + a_{2n} + a_{3n} + ...} = \frac{a_m}{a_1 + a_2 + ...}$

which in turn is equivalent to the condition that

$\displaystyle \frac{a_{mn}}{a_m} = \frac{a_n + a_{2n} + a_{3n} + ...}{a_1 + a_2 + a_3 + ...}$.

(I am adopting the natural assumption that $a_n > 0$ for all $n$. No sense in excluding a positive integer from any reasonable probability distribution on $\mathbb{N}$.) In other words, $\frac{a_{mn}}{a_m}$ is independent of $m$, from which it follows that $a_{mn} = c a_m a_n$ for some constant $c$. From here it already follows that $a_n$ is determined by $a_p$ for $p$ prime and that the exponents in the prime factorization are chosen geometrically. And now the condition that $a_n$ is monotonically decreasing gives the zeta distribution as before. So I think we should use the following characterization theorem instead.

Theorem: Let $a_n = \mathbb{P}(X = n)$ be a probability distribution on $\mathbb{N}$. Suppose that $a_{nm} = c a_n a_m$ for all $n, m \ge 1$ and some $c$, and further suppose that $a_n$ is monotonically decreasing. Then $a_n = \frac{1}{\zeta(s)} \left( \frac{1}{n^s} \right)$ for some real $s > 1$.

More generally, the following situation covers all the examples we have used so far. Let $M$ be a free commutative monoid on generators $p_1, p_2, ...$, and let $\phi : M \to \mathbb{R}$ be a homomorphism. Let $a_m = \mathbb{P}(X = m)$ be a probability distribution on $M$. Suppose that $a_{nm} = c a_n a_m$ for all $n, m \in M$ and some $c$, and further suppose that if $\phi(n) \ge \phi(m)$ then $a_n \le a_m$. Then $a_m = \frac{1}{\zeta_M(s)} e^{-\phi(m) s}$ for some $s$ such that the zeta function

$\displaystyle \zeta_M(s) = \sum_{m \in M} e^{-\phi(m) s}$

converges. Moreover, $\zeta_M(s)$ has the Euler product

$\displaystyle \zeta_M(s) = \prod_{i=1}^{\infty} \frac{1}{1 - e^{- \phi(p_i) s}}$.

Recall that in the statistical-mechanical interpretation, we are looking at a system whose states are finite collections of particles of types $p_1, p_2, ...$ and whose energies are given by $\phi(p_i)$; then the above is just the partition function. In the special case of the zeta function of a Dedekind abstract number ring, $M = M_R$ is the commutative monoid of nonzero ideals of $R$ under multiplication, which is free on the prime ideals by unique factorization, and $\phi(I) = \log N(I)$. In the special case of the dynamical zeta function of an invertible map $f : X \to X$, $M = M_X$ is the free commutative monoid on orbits of $f$ (equivalently, the invariant submonoid of the free commutative monoid on $X$), and $\phi(P) = \log |P|$, where $|P|$ is the number of points in $P$.

Read Full Post »

## Zeta functions, statistical mechanics and Haar measure

An interesting result that demonstrates, among other things, the ubiquity of $\pi$ in mathematics is that the probability that two random positive integers are relatively prime is $\frac{6}{\pi^2}$. A more revealing way to write this number is $\frac{1}{\zeta(2)}$, where

$\displaystyle \zeta(s) = \sum_{n \ge 1} \frac{1}{n^s}$

is the Riemann zeta function. A few weeks ago this result came up on math.SE in the following form: if you are standing at the origin in $\mathbb{R}^2$ and there is an infinitely thin tree placed at every integer lattice point, then $\frac{6}{\pi^2}$ is the proportion of the lattice points that you can see. In this post I’d like to explain why this “should” be true. This will give me a chance to blog about some material from another math.SE answer of mine which I’ve been meaning to get to, and along the way we’ll reach several other interesting destinations.

Read Full Post »

## Newton’s sums, necklace congruences, and zeta functions II

In a previous post I gave essentially the following definition: given a discrete dynamical system, i.e. a space $X$ and a function $f : X \to X$, and under the assumption that $f^n$ has a finite number of fixed points for all $n$, we define the dynamical zeta function to be the formal power series

$\displaystyle \zeta_X(t) = \exp \sum_{n \ge 1} (\text{Fix } f^n) \frac{t^n}{n}$.

What I didn’t do was motivate this definition, mostly because I hadn’t really worked out the motivation myself. Now that we have an important special case worked out, we can discuss the general case, which will give a purely combinatorial proof of the second half of the Newton-Girard identities.

Read Full Post »

## The cyclotomic identity and Lyndon words

In number theory there is a certain philosophy that $\mathbb{F}_q[x]$ is a good toy model for the integers $\mathbb{Z}$. The two rings share an important property: they are basically the canonical examples of Euclidean domains, hence PIDs, hence UFDs. However, many number-theoretic questions involving prime factorization over $\mathbb{F}_q[x]$ are much easier than their corresponding questions over $\mathbb{Z}$. One way to see this is to look at their zeta functions.

The usual zeta function $\zeta(s) = \sum_{n \ge 1} \frac{1}{n^s}$ reflects the structure of prime factorization through its Euler product

$\displaystyle \zeta(s) = \prod_p \frac{1}{1 - p^{-s}}$

where the product runs over all primes; this is essentially equivalent to unique factorization. Since we know that monic polynomials over $\mathbb{F}_q[x]$ also enjoy unique factorization, it’s natural to ask whether there’s a sum over monic polynomials that would give a similar Euler product.

In fact, there is such a product, and investigating it leads naturally to a seemingly unrelated subject: the combinatorics of words.

Read Full Post »

## Newton’s sums, necklace congruences, and zeta functions

The goal of this post is to give a purely combinatorial proof of Newton’s sums which would have interrupted the flow of the previous post. Recall that, in the notation of the previous post, Newton’s sums (also known as the first Newton-Girard identity) state that

$\displaystyle p_k - e_1 p_{k-1} \pm ... = (-1)^{k+1} ke_k$.

One way to motivate a combinatorial proof is to recast the generating function interpretation appropriately. Given a polynomial $C(t)$ with non-negative integer coefficients and $C(0) = 0$, let $r_1, ... r_n$ be the reciprocals of the roots of $C(t) - 1 = 0$. Then

$\displaystyle \frac{t C'(t)}{1 - C(t)} = \sum_{k \ge 1} p_k(r_1, ... r_n) t^k$.

The left hand side of this identity suggests a particular interpretation in terms of the combinatorial species described by $C(t)$. Today we’ll describe this species when $C(t)$ is a polynomial with non-negative integer coefficients and then describe it in the general case, which will handle the extension to the symmetric function case as well.

The method of proof used here is closely related to a post I made previously about the properties of the Frobenius map, and at the end of the post I’ll try to discuss what I think might be going on.

Read Full Post »