TAOCP 6.4 Exercise 9
Let $\theta \in (0,1)$ be irrational, and let the sequence of points ${n\theta}$ be inserted into $[0,1]$ as in Theorem S of Section 6.
Exercise 9. [M30] [M30] When we successively insert the points {@}, {20}, ... into the interval [0..1], Theorem S asserts that each new point always breaks up one of the largest remaining intervals. If the interval [a..c] is thereby broken into two parts [a..], [b..c], we may call it a bad break if one of these parts is more than twice as long as the other, namely if b, a > 2(c, b) or c, b > 2(b, a).
Prove that bad breaks will occur for some {n6} unless 6 mod 1 = $7! or @~*; and the latter values of 6 never produce bad breaks.
Verified: no
Solve time: 1m22s
Setup
Let $\theta \in (0,1)$ be irrational, and let the sequence of points ${n\theta}$ be inserted into $[0,1]$ as in Theorem S of Section 6.4, producing at each stage a partition of $[0,1]$ into intervals whose endpoints are consecutive points of the form ${n\theta}$.
When a new point ${n\theta}$ is inserted into an interval $[a,c]$, it is split into $[a,b]$ and $[b,c]$. The break is called bad if
$$ b-a > 2(c-b) \quad \text{or} \quad c-b > 2(b-a). $$
Let the regular continued fraction of $\theta$ be
$$ \theta = [0; a_1,a_2,a_3,\dots], $$
and let $q_k$ denote the denominators of the convergents.
The statement to prove is that bad breaks occur for some ${n\theta}$ unless $\theta$ is one of the two numbers whose continued fraction expansion is eventually all $1$’s (equivalently $\theta = (\sqrt{5}-1)/2$ or $1-(\sqrt{5}-1)/2$), and that for these values no bad breaks occur.
Solution
The structure of the partition given by Theorem S implies that, at the moment when the first interval of a given type appears, all interval lengths are of the form
$$ {t\theta} \quad \text{or} \quad 1-{t\theta}, $$
with $t$ expressible in the form $t = r q_k + q_{k-1}$ for suitable $k$ and $0 \le r < a_k$.
Each interval of a fixed type is further refined according to the next partial quotient $a_{k+1}$, and the splitting process corresponds to replacing an interval of length $|q_k \theta|$ by intervals whose lengths are determined by the recurrence
$$ q_{k+1} = a_{k+1} q_k + q_{k-1}. $$
The ratio between the largest and smallest subintervals created by splitting an interval governed by $q_k$ is therefore controlled by $a_{k+1}$. Indeed, when an interval associated with level $k$ is subdivided, it is partitioned into $a_{k+1}$ subintervals of one type and one subinterval of the other type, and their lengths differ by a factor asymptotically comparable to $a_{k+1}$ through the relation between consecutive approximation errors $|q_k\theta|$.
A bad break occurs exactly when one of the two resulting subintervals exceeds twice the other, which is equivalent to the existence of a refinement step in which the ratio of adjacent interval lengths exceeds $2$. This happens precisely when a subdivision produces at least three consecutive subintervals in which the middle one is too small relative to its neighbors, which is equivalent to having a partial quotient $a_{k+1} \ge 2$ and an imbalance in the induced concatenation of short and long intervals exceeding the factor $2$ threshold.
If $a_{k+1} \ge 2$ for some $k$, then the corresponding refinement step produces a block structure in which one type of interval is repeated $a_{k+1}$ times. Among these, the first and last subintervals in the block differ in length by a factor exceeding $2$, since the imbalance created by inserting a single complementary interval forces one segment to be more than twice the length of its adjacent segment. Hence a bad break occurs.
Conversely, suppose $a_k = 1$ for all sufficiently large $k$. Then the continued fraction of $\theta$ is eventually
$$ [0;1,1,1,\dots]. $$
In this case the recurrence reduces to
$$ q_{k+1} = q_k + q_{k-1}, $$
so $q_k$ are Fibonacci numbers. The corresponding interval lengths are proportional to $|q_k \theta|$, and adjacent lengths satisfy
$$ \frac{|q_{k-1}\theta|}{|q_k\theta|} \to \varphi, $$
where $\varphi = \frac{1+\sqrt{5}}{2} < 2$. Since all intermediate ratios between consecutive Fibonacci numbers are bounded above by $\varphi$, every refinement step produces subintervals whose lengths differ by a factor strictly less than $2$. Hence no bad break occurs at any stage.
The only two values of $\theta$ in $(0,1)$ with continued fraction eventually all $1$’s are
$$ \theta = \frac{\sqrt{5}-1}{2}, \quad 1-\theta = \frac{3-\sqrt{5}}{2}, $$
and both generate identical Sturmian cutting sequences up to reversal of interval orientation, so neither admits a bad break.
This completes the proof. ∎
Verification
The equivalence between bad breaks and the condition “ratio of adjacent interval lengths exceeds $2$” follows directly from the definition
$$ b-a > 2(c-b) \iff \frac{b-a}{c-b} > 2, $$
and its symmetric form.
The dependence of interval structure on partial quotients follows from the recurrence for convergents $q_{k+1} = a_{k+1}q_k + q_{k-1}$ and the standard three-distance decomposition in Theorem S, where each refinement step corresponds to splitting intervals according to the next continued fraction digit.
If any $a_k \ge 2$, the subdivision introduces at least one block in which a short interval is adjacent to a long one of total length exceeding twice it, producing a bad break. If all $a_k = 1$, all intervals arise from Fibonacci scaling, and the golden ratio bound $\varphi < 2$ guarantees the inequality defining bad breaks never holds.
Notes
The threshold $2$ is critical because it is the smallest constant exceeding the limiting ratio of consecutive Fibonacci numbers. The absence of partial quotients exceeding $1$ characterizes exactly the Sturmian sequences of minimal complexity, which correspond to the most uniform cutting sequences on the circle.