This post is an echo to Davide Ravotti’s brilliant talk one week ago.

Equidistribution has already been discussed here on this blog (during the good old epoch of francophony…) and it is a fascinating property. It must be observed that it isn’t the property of a countable set but of a rational sequence; in other words it depends crucially on the order in which the terms are considered.

The rationals between 0 and 1 are countable for instance. The usual way to see it is, as Cantor did, to naturally embed \mathbb{Q} in \mathbb{Z}^2 and to order the couples of positive integers (p,q) by increasing p+q. But number theorists know that the right way to order rationals is by increasing denominator. Indeed, in diophantine approximation, the denominator determines the quality of the approximation. The fractions p/q, at fixed q, follow each other at distance 1/q so these produce sequences which are of course evenly distributed and denser and denser. So let’s introduce the Farey sequence which is the most relevant ordering of the rationals.

The Farey sequence

We denote \beta_{q,i} for 1\leq q , 1\leq i\leq \phi(q) the fractions a_i(q)/q, where 1=a_1(q) < a_2(q) < a_{\phi(q)}=q-1 are the integers coprime to and smaller than q. This yields an enumeration of the rationals: 1,1/2,1/3,2/3,1/4,3/4,1/5,2/5,3/5,4/5,1/6… In other words, our sequence is defined by \alpha_k=\beta_{q,i} where q is the only integer such that \sum_{n=1}^{q-1}\phi (n) < k\leq \sum_{n=1}^q\phi (n) and i=k-\sum_{n=1}^{q-1}\phi (n). We may want to add \alpha_0=0. The Farey sequence of order n is \mathcal{F}_n=(\alpha_k)_{1\leq k\leq \sum_{q\leq n}\phi (k)}. Every rational appears in \mathcal{F} because every rational can be put in lowest terms p/q with (p,q)=1.

The Farey sequence of order n yields a dissection of the unit interval (or rather of the circle if you want to identify both ends, which we do in the end if we use Weyl’s characterisation of equidistribution) in the following way: we look at all the mediants \frac{h+h'}{k+k'} of successive pairs. The intervals between two mediants will be our Farey arcs and each fraction of the Farey sequence will be contained in one arc. For instance 0=1=1/1 is between the points 1-1/n and 1/n so that the mediants formed with them and 1/1 are \frac{n}{n+1} and \frac{1}{n+1}, hence the arc containing 0 is (\frac{n}{n+1},\frac{1}{n+1}). It is easy to see that the arc containing h/k\in \mathcal{F}_n  is made of two parts (one at each side of the Farey fraction conatined in it) both of length between \frac{1}{k(2n-1)} and \frac{1}{k(n+1)}. This denotes a certain uniformity. It also provides again another proof of Liouville’s theorem by the way (see Hardy & Wright).

Neville indeed proved in 1949 that the Farey sequence \mathcal{F} satisfies Weyl’s criterion and hence is indeed equidistributed. In fact the equidistribution remains true however we order the people inside each \beta_q sequence.

Connection to Riemann’s hypothesis

Jérôme Franel observed in 1924 that Riemann’s hypothesis would imply (and is equivalent to the fact) that on average the i-th fraction a_{i,n} of \mathcal{F}_n is very close to i/m_n where m_n=\sum_{q\leq n}\phi(q). So the Farey sequence is quite close to the evenly spaced sequence of fractions of the same length. Precisely, putting d_{i,n}=a_{i,n}-i/m_n, Riemann’s hypothesis is equivalent to \sum d_{i,n}^2=O(n^{-1+\epsilon}) for all \epsilon >0.

Other sequences of rationals and generalisations to higher dimensions

Ordering the elements \alpha=1/q(p_1,\cdots,p_n) \in \mathbb{Q}^n\cap [0,1]^n amounts to ordering the elements \alpha=(p_1,\cdots, p_n,q)\in\mathbb{Z}^{n+1}\cap \text{Cone}([0,1]^n\times\{1\}) (in both case we want to restrict to (p_1,\cdots, p_n,q)=1 which we call primitive tuples). Here an « optical » description is useful, as strikingly it is already in the theory of Farey sequences to prove that if two elements p/q,p'/q'\in\mathcal{F}_n are consecutive, then p'q-pq'=1.

Farey8

As the picture of the Farey sequence of order 8 above shows, one can imagine an eye looking from the origin into to the first quadrant. He only sees the first integer point on each line; hence 2/8 is hidden from its sight by 1/4, its primitive form. Two fractions p/q,p'/q' are successive if and only if there’s no point in the parallelogram between both vectors, which happens only if it has area 1, which implies p'q-pq'=1.

To order the elements, we use a piecewise linear function u : \mathbb{R}^{n+1}\rightarrow \mathbb{R} with integer coefficients. Thus the Farey case is u(x_1,\cdots,x_{n+1})=x_{n+1} and the « Cantor » case is u(x_1,\cdots,x_{n+1})=\sum x_i. Given such a function, we order the integral points according to the value of the function on them; in order words we partition the integral points of the cone into level sets of u. So we need that each of this level set have a compact intersection with the cone, so that we have a finite number of integral points on each level set…

The cone of [0,1]x{1}, and some level sets of some piecewise linear functions

The cone of [0,1]x{1}, and some level sets of some piecewise linear functions

Goal: given a simplex S\subset [0,1]^n, compute

\lim \frac{\lvert \{k\leq N\mid \alpha_k\in \text{Cone} (S)\}\rvert}{N}

If this is proportional to the volume of S, this means that we have equidistribution of the sequence. Indeed it’s the generalisation of case n=1, where simplices are simply intervals.

From now, we restrict without loss of generality to a linear u. The key step is to compute

P_{S_1(t)}=\lvert\{a\in\mathbb{Z}^{n+1}\cap tS_1, a\text{ primitive}\}\rvert

for t integer, where S_t=\{u=t\}\cap \text{Cone}(S). We can in fact drop the primitivity condition, and retrieve the cardinality searched by Moebius inversion.

Ehrhart’s theory

This is precisely the scope of Ehrhart theory, dealing with things such as L_P(t)=\lvert\{a\in\mathbb{Z}^{n}\cap tP\}\rvert for P\subset\mathbb{R}^n a rational polyhedron (=with rational vertices).

Notice that Eugène Ehrhart was an alsacian high-school teacher who didn’t complete his PhD before his 60th birthday…

Examples

  • P=[0,1]^n then L_p(t)=(t+1)^n
  • if P is the standard simplex then a classical counting argument yields L_p(t)=\binom{t+n}{t}
  • if P is a convex polygon of the plane with integral vertices then Pick’s formula says that L_P(t)=\text{Area}(P)t^2+\frac{\lvert\{\text{integral points in } \partial P\}\rvert}{2}t+1

This looks polynomial and it isn’t a coincidence.

Ehrhart’s theorems:

  1. If P\subset\mathbb{R}^n is integral polyhedron of dimension d, then L_P(t) is a rational polynomial of degree d, whose dominating coefficient is the relative volume \nu(P) of the polyhedron.
  2. If P\subset\mathbb{R}^n is integral polyhedron of dimension d, then L_P(t) is a rational quasi-polynomial of degree d, i.e. there exist functions c_i : \mathbb{Z}\rightarrow\mathbb{Q} which are periodic, of periods divising the lcm of the denominators of the vertices such that L_P(t)=\sum c_i(t)t^d.

The second statement comprises the first. The relative volume \nu(P) is defined as follows: there exists an affine isomorphism \psi : \text{Aff}(P)\rightarrow \mathbb{R^d} such that \psi(\mathbb{Z}^{n+1}\cap \text{Aff}(P))=\mathbb{Z}^d and then \nu (P):=\text{Vol} (\psi(P)), which doesn’t depend on the choice of \psi, because two possible choices differ by a transformation of determinant 1, hence give same volume.

Notice that for a general convex set C\subset\mathbb{R}^n of non-zero volume, the arguments from Tao-Vu’s book Additive combinatorics or Green-Tao’s Linear equations in primes (appendix A) give that L_C(t)=\text{Vol}(C)t^{n}+O(t^n). It is for instance quite well known (Gauss circle problem) how many integral points there are asymptotically in a big disc of Radius R: about \pi R^2.

Finally, performing the Moebius inversion:

P_{S_1}(t)=\sum_{s\mid t}\mu(t/s)L_{S_1}(s)=\sum \mu(t/s)(\nu(S_1)s^d+O(s^{d-1}))

and finally P_{S_1}(t) =\nu(S_1) Ct^{d+1}+O(t^d) where Ct^{d+1}=\sum_{s\mid t}\mu(t/s)s^d according to some number theory (cf the exercises of Murty).

In the end of the day, we get that \lim \frac{\lvert \{k\leq N\mid \alpha_k\in \text{Cone} (S)\}\rvert}{N}=\frac{\nu (S_1)}{\nu ([0,1]^n)}. To be quite honest, it isn’t exactly the case when S is not integral but simply rational. Indeed, the leading coefficient c_d(t) in Ehrhart’s (quasi)-polynomial of a polyhedron P is not always constantly equal to the relative volume \nu(p). To see this, take S=[0,1]\times \{1/2\}\subset\mathbb{Z}^2. This is a nice rational polyhedron of dimension 1 and relative volume 1 (morally it’s the volume when seen in its « natural environment », its affine hull). Then tS contains an integral point if and only if t is even, so L_P(t)=1_{t\equiv 0[2]}(t+1). So instead of \nu (S_1), we should get here \nu(bS_1)/b^{d+1} where b is the first integer so that bS_1 contains an integral point.

When do we get equirepartition? Probably essentially when \nu(S_1)=\nu(S) for all simplices S. This is certainly only the case when S_1=S all the time, which seems to imply that u=x_{n+1}, in other words the Farey case.

Publicités