You are currently browsing the monthly archive for février 2015.

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 in and to order the couples of positive integers by increasing . 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 , at fixed q, follow each other at distance 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 for the fractions , where are the integers coprime to and smaller than . This yields an enumeration of the rationals: … In other words, our sequence is defined by where is the only integer such that and . We may want to add . The Farey sequence of order n is . Every rational appears in because every rational can be put in lowest terms with .

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 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 and so that the mediants formed with them and 1/1 are and , hence the arc containing 0 is . It is easy to see that the arc containing is made of two parts (one at each side of the Farey fraction conatined in it) both of length between and . 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 satisfies Weyl’s criterion and hence is indeed equidistributed. In fact the equidistribution remains true however we order the people inside each 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 of is very close to where . So the Farey sequence is quite close to the evenly spaced sequence of fractions of the same length. Precisely, putting , Riemann’s hypothesis is equivalent to for all .

**Other sequences of rationals and generalisations to higher dimensions**

Ordering the elements amounts to ordering the elements (in both case we want to restrict to 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 are consecutive, then .

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 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 .

To order the elements, we use a piecewise linear function with integer coefficients. Thus the Farey case is and the « Cantor » case is . 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 . 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…

Goal: given a simplex , computeIf this is proportional to the volume of , this means that we have equidistribution of the sequence. Indeed it’s the generalisation of case , where simplices are simply intervals.

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

for integer, where . 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 for 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

- then
- if P is the standard simplex then a classical counting argument yields
- if P is a convex polygon of the plane with integral vertices then Pick’s formula says that

This looks polynomial and it isn’t a coincidence.

Ehrhart’s theorems:

- If is integral polyhedron of dimension d, then is a rational polynomial of degree , whose dominating coefficient is the relative volume of the polyhedron.
- If is integral polyhedron of dimension d, then is a rational quasi-polynomial of degree , i.e. there exist functions which are periodic, of periods divising the lcm of the denominators of the vertices such that .

The second statement comprises the first. The relative volume is defined as follows: there exists an affine isomorphism such that and then , which doesn’t depend on the choice of , because two possible choices differ by a transformation of determinant 1, hence give same volume.

Notice that for a general convex set 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 . 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 .

Finally, performing the Moebius inversion:

and finally where according to some number theory (cf the exercises of Murty).

In the end of the day, we get that . To be quite honest, it isn’t exactly the case when is not integral but simply rational. Indeed, the leading coefficient in Ehrhart’s (quasi)-polynomial of a polyhedron is not always constantly equal to the relative volume . To see this, take . 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 contains an integral point if and only if is even, so . So instead of , we should get here where b is the first integer so that contains an integral point.

When do we get equirepartition? Probably essentially when for all simplices S. This is certainly only the case when all the time, which seems to imply that , in other words the Farey case.

## Commentaires récents