1
$\begingroup$

Let $r$ and $h$ be a real numbers and $n>0$. Write the fractional parts $\{k*r+h\}$, for $k = 1,2, . . . n$, in increasing order as $$ a_1 < a_2 < \cdots < a_n.$$ Let $D_n$ be the set of all the differences $a_{i+1} - a_i$ for $k = 1,2, \ldots, n-1.$ Can someone cite a reference or give a proof that $D_n$ contains at most $3$ elements for every $n$?

For the case $h = 0$, a certain paper calls this a "somewhat surprising and apparently little-known fact", without proof or reference. The proposition appears to be factual even when $h$ isn't $0$.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

The case $h=0$ is known as the "Three-Distance Theorem"; just google for numerous references or look here for discussion and nice pictures, or here for an interesting historical comment.

A standard reformulation of the theorem is as follows: if, for an irrational $\alpha$, the unit-length circle is partitioned "in the natural way" into $n$ arcs by the points $\alpha k$ with $k\in[1,n]$, then the lengths of these $n$ arcs take just two or three distinct values. This easily implies the case $h\ne 0$ where you basically select one of the arcs (that containing the point corresponding to $h$) and confine to the lengths of the remaining $n-1$ arcs.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thanks - however, it appears that the three-distance theorem, alias "three-gap theorem", is only for $h=0$. I still need a reference or proof that answers the question (where $h$ is an arbitrary real number). $\endgroup$
    – Clark Kimberling
    Commented Jun 30, 2015 at 20:22
  • $\begingroup$ Isn't the extension to general $h$ trivial? Doesn't it fall out of the usual proofs? $\endgroup$
    – Gerry Myerson
    Commented Jul 1, 2015 at 0:05
  • $\begingroup$ @Clark Kimberling: I expanded my answer a little to address the general case of $h\ne 0$. Does this answer your question? $\endgroup$
    – Seva
    Commented Jul 3, 2015 at 6:36

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .