14
$\begingroup$

Fix $\alpha\in\mathbb R$ and $N\in \mathbb N$, consider the set $S(\alpha,N)$ of $\{k\alpha\},k=1,\dots,N$, where $\{x\}$ denotes the fractional part of $x$. Let $a_1,\ldots a_N$ be the elements of $S(\alpha, N)$ arranged in increasing order, and consider the gaps sizes $$ |a_{i+1}-a_i|, i=1,\dots,N-1. $$ The well-known Three Gap Theorem tells us that the number of distinct gap sizes is at most three for any $\alpha$ and $N$.

There are many proofs and generalisations of this theorem, but I haven't gained any intuition regarding the statement. In particular, is there any heuristic/intuitive reason as to why the theorem should be true?

$\endgroup$
5
  • 12
    $\begingroup$ Do you have intuition why it should be true when $\alpha$ is very small? Imagine walking round the circle marking off successive multiples of $\alpha$. $\endgroup$
    – Ben Barber
    Apr 16, 2018 at 15:06
  • 2
    $\begingroup$ Could you say more? I'm not asking for a proof of the statement—I know a couple off hand. I don't see how looping around in multiples of $\alpha$, let's say small and irrational, explains why the differences shoud be finite, and in fact exactly three. $\endgroup$
    – Tian An
    Apr 16, 2018 at 17:16
  • $\begingroup$ there is an article in the March maa Monthly, pages 264-266, called A Footnote to the Three Gaps Theorem. Some references. $\endgroup$
    – Will Jagy
    Apr 16, 2018 at 17:39
  • 4
    $\begingroup$ I agree with Ben Barber's implication: actually working through a specific example by hand—say with $\alpha=0.11$ or $\alpha=0.13$—will increase your intuition quite a bit. $\endgroup$ Apr 16, 2018 at 18:45
  • 6
    $\begingroup$ One can view this theorem as an approximate version of the One Gap Theorem: in a subgroup of the unit circle, the number of distinct gap sizes is 1. From the perspective of modern additive combinatorics, an arithmetic progression such as $\{ \{k\alpha\}: k=1,\dots,N\}$ should be thought of as an approximate version of a subgroup of the unit circle (it is approximately closed under addition). $\endgroup$
    – Terry Tao
    May 25, 2021 at 16:15

2 Answers 2

11
$\begingroup$

I'm in something of the opposite situation to you. I'd never heard of the three distances/gaps theorem a week ago, since when I've come across it three times. I think the first person to introduce it to me was trying to convey how surprising it was, but as soon as I understood the statement I thought "isn't that obvious?". I'm now convinced that it isn't obvious, in the sense that I'm unable to make up a proof off the top of my head that I know will work, but perhaps my initial thought process will help your intuition.

Fix some moderately small $\alpha$. It's clear that things work well for the first few steps. In fact, we get by with only two distances until we're about to overtake the start point.

                 enter image description here

At the very next step we only create one new distance. We cut an interval in half, but we know by symmetry that one of the distances created will agree with the new distance we made at the previous step.

enter image description here

The next step cuts another interval, but into the same parts that we've just seen. This carries on for the whole of our second lap round the circle, until we're about to cross the start point again, at which point we would have to stop and think again about what is going to happen.

enter image description here                  enter image description here

For other $\alpha$ the picture might look different, but (presumably) the same principles apply: we keep cutting old gaps in two, always eliminating an old distance before we need to use a new one.

enter image description here

$\endgroup$
0
2
$\begingroup$

Its all about modular arithmetic. Draw $n$ points $P_0 = 0, P_1, \ldots, P_{n-1}$, with the largest $P_{max}$, and smallest (non-zero) $P_{min}$, with $min, max \in \{1, \dots, n-1\}$. Now, the initial gap, $a = P_{min} - P_0$, is repeated for every point with at least $min$ successors, i.e. the first $n - min$ points. Similarly, the final gap, $b = P_0 - P_{max}$, is repeated for every point with at least $max$ predecessors, i.e. the final $n - max$ points.

There is also a middle group of $min + max - n$ points/gaps that get bisected into an $a$ and $b$ every time $n$ increments until $n = min + max$, and no more mid-points remain. The next time that $n$ increments, the new point $P_{min + max} = a - b$ bisects the larger of the initial $a$ and final $b$, and it all starts over.

There are usually three gaps, $a$, $b$ and $a + b$, that reduce to two, $a$ and $b$, every time $n = min + max$.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.