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…
If 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.
Laisser un commentaire
Comments feed for this article