---

Statement

Let $S_m$ be the set of permutations of $\{1,2,\ldots,m\}$ and $F_n$ the Fibonacci numbers ($F_0=0$, $F_1=1$, $F_{n+2}=F_{n+1}+F_n$). The announcement defines

$$u_m=\min_{\pi\in S_m}\max_I\sum_k|\pi(i_{k+1})-\pi(i_k)|^{-1},$$

where $I$ ranges over all increasing subsequences $\{i_1<i_2<\cdots<i_r\}\subseteq\{1,2,\ldots,m\}$ and the sum runs over the consecutive pairs of $I$ (the print writes $\sum_k$ without a range; the 1984 chapter prints $\sum_{k=1}^{r-1}$).

Theorem 3 (p. 4001).

$$u_m=\begin{cases} 1+\sum_{k=1}^{t}F_{2k}^{-1} & \text{if } F_{2t+3}\le m<F_{2t+4},\\[4pt] 1+\sum_{k=1}^{t}F_{2k}^{-1}+F_{2t+3}^{-1} & \text{if } F_{2t+4}\le m<F_{2t+5}. \end{cases} \tag{4}$$

The print does not state the range of $t$.

The page adds, without proof, that permutations attaining the minimum can be generated by ordering the first $m$ terms of the sequence $\bar x^*$ of Theorem 2, and that these are the permutations given by the sequence $\{k\tau\}$, $k=0,1,2,\ldots$, with $\tau=(1+\sqrt5)/2$ and $\{x\}$ the fractional part of $x$. (The print speaks of "equality in 3"; the 1984 chapter's corresponding sentence speaks of permutations achieving (4).) It calls Theorems 1 and 2 "intimately tied" to this result. As $t\to\infty$ both values in (4) tend to $1/\alpha$, with $\alpha$ the constant of Theorem 1.

Source. F. R. K. Chung and R. L. Graham, On irregularities of distribution of real sequences, Proc. Natl. Acad. Sci. USA 78 (1981), no. 7, 4001; the definition of $u_m$ and Theorem 3 are on the one printed page. The edition is identified in the source digest.

Read depth. Claims checked: the definition of $u_m$ and the two cases of [4] were read clause by clause on the page image. The page gives no proof.

Proof pointer

None on the page. The proof is Theorem 3 of the 1984 chapter (p. 183 there): an upper bound from the permutation that orders $\{k\tau\}$, $1\le k\le m$ (pp. 188--203), and a lower bound by induction (pp. 203--210); see the chapter's digest.

Dependencies

None stated on the page.

Bears on

• Problem 480, through Theorem 1 only: the announcement does not derive Theorem 1 from Theorem 3; the 1984 chapter proves its Theorem 1 as a corollary of Theorem 3 (p. 211 there). Theorem 3 itself is a statement about finite permutations, not about the problem's sequences.