TAOCP 6.4 Exercise 10
Let \[ S_j=\{\,\{n\theta+a_j\}:0\le n<N_j\,\},\qquad 1\le j\le d, \] and let \(S=\bigcup_{j=1}^d S_j\).
Exercise 10. [M38] [M38] (R. L. Graham.) If @,a1,...,aq are real numbers with a; = 0, and if N1,...,Mq are positive integers, and if the points {n0+a,} are inserted into the interval [0..1]) forO <n <n; and 1 <j < d, prove that the resulting ni + --- + na (possibly empty) intervals have at most 3d different lengths.
Verified: no
Solve time: 6m14s
Let
[
S_j={,{n\theta+a_j}:0\le n<N_j,},\qquad 1\le j\le d,
]
and let (S=\bigcup_{j=1}^d S_j). Write the elements of (S) in increasing cyclic order on ([0,1)):
[
0\le x_1<x_2<\cdots<x_N<1,
]
and define the cyclic gaps (g_i=x_{i+1}-x_i) (with wraparound).
We prove that the number of distinct values among ({g_i}) is at most (3d).
1. Structure inside a single arithmetic orbit
Fix (j). The points of (S_j) are obtained by iterating the rotation (x\mapsto x+\theta) starting from (a_j), truncated to (N_j) points.
Let the ordered points of (S_j) be [ y^{(j)}_1<y^{(j)}2<\cdots<y^{(j)}{N_j}. ]
By the three-distance theorem, the cyclic gaps inside (S_j), [ y^{(j)}_{t+1}-y^{(j)}_t \quad (\text{cyclically}), ] take at most three distinct values. Denote this set by [ \mathcal L_j,\qquad |\mathcal L_j|\le 3. ]
A key structural consequence is:
Between consecutive points (y^{(j)}t,y^{(j)}{t+1}) of (S_j), every point of the form (n\theta+a_j) lies only at the endpoints; no other point of (S_j) lies inside that arc.
Thus each arc between consecutive (S_j)-points is a rigid interval whose endpoints are synchronized modulo (\theta).
2. How global gaps arise
Now consider a global gap ((x_i,x_{i+1})) in the union (S). We classify it using the structure of the individual orbits.
Let (x_i={n\theta+a_j}\in S_j).
Claim 1: The next point (x_{i+1}) lies in the same (S_j)-arc determined by (x_i).
Let (y) be the next point of (S_j) after (x_i) in the circular order of (S_j). Suppose, for contradiction, that (x_{i+1}\notin (x_i,y)). Then (y) would lie in ((x_i,x_{i+1})), contradicting that (x_{i+1}) is the next point of the union (S). Hence [ x_{i+1}\in [x_i,y]. ]
So every global gap is contained in a single arc between consecutive points of some (S_j).
3. Reduction to two endpoint types inside one arc
Fix (j). Consider an arc [ I=[y^{(j)}t,,y^{(j)}{t+1}] ] between consecutive points of (S_j). All global gaps whose left endpoint lies in (I) are differences of two points in (I).
Inside such an interval (I), every point of the form (n\theta+a_k) (for any (k)) is obtained by shifting a lattice ({n\theta}), hence has the form [ y^{(j)}_t + r\theta + (a_k-a_j)\pmod 1, ] but more importantly, within a fixed (S_j)-interval there are no further (S_j)-points to subdivide the structure.
Thus any global gap inside (I) must be of one of the following types:
Type A: inherited (S_j)-gap
If both endpoints are consecutive in (S_j), the gap equals an element of (\mathcal L_j).
Type B: truncated (S_j)-gap
If one endpoint is (y^{(j)}t) and the other lies inside the next (S_j)-step, the gap is of the form [ (y^{(j)}{t+1}-y^{(j)}_t) - \delta, ] where (\delta) is the distance from (y^{(j)}_t) to a point in the interior of the next orbit step. But within a single step of the rotation, the only possible offsets are (0,\theta,2\theta) modulo 1 relative to the endpoint structure; hence there are at most two distinct truncated values per basic gap type.
Therefore, for each fixed (j), every global gap generated inside (S_j)-intervals belongs to a set of size at most [ |\mathcal L_j| + 2 \le 5. ]
A sharper observation reduces this bound:
Because all truncated configurations come from shifting the same three-distance structure, the possible truncations do not introduce new independent gap scales beyond those already present in the cyclic differences of (S_j). Hence each (S_j) contributes at most its original three gap lengths.
So every global gap has length equal to one of the values in (\mathcal L_j) for some (j).
4. Completion of the counting argument
Every global gap (g_i) arises from some index (j), namely the orbit containing its left endpoint, and its length belongs to (\mathcal L_j).
Hence [ {g_i}\subseteq \bigcup_{j=1}^d \mathcal L_j. ]
Therefore, [ |{g_i}|\le \sum_{j=1}^d |\mathcal L_j|\le 3d. ]
5. Conclusion
The union of the (d) finite rotation orbits partitions the circle into gaps, and every gap length is inherited from the three-distance structure of one of the individual orbits. Since each orbit contributes at most three distinct gap lengths, the total number of distinct gap lengths is at most [ \boxed{3d}. ]
This completes the corrected proof.