Note

[olympiad_subtasks] Maximizing a Floor Sum Expression Involving Harmonic Numbers

By Fizzy

floor functionharmonic numbersnumber theoryoptimization

1Proof Plan

  1. Let

    En(x):=⌊nx⌋−∑k=1n⌊kx⌋k.\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} E_n(x):=\lfloor nx\rfloor-\sum_{k=1}^n \frac{\lfloor kx\rfloor}{k}.

    Since ⌊k(x+t)⌋=⌊kx⌋+kt\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} \lfloor k(x+t)\rfloor=\lfloor kx\rfloor+kt for integers t\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} t, the function En\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} E_n is 1\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} 1-periodic. Thus it suffices to maximize En\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} E_n on [0,1)\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} [0,1).

  2. On the top slab [(n−1)/n,1)\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} [(n-1)/n,1) one has ⌊kx⌋=k−1\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} \lfloor kx\rfloor=k-1 for every 1≤k≤n\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} 1\le k\le n, so

    En(x)=n−1−∑k=1nk−1k=Hn−1,Hn:=∑k=1n1k.\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} E_n(x)=n-1-\sum_{k=1}^n \frac{k-1}{k}=H_n-1, \qquad H_n:=\sum_{k=1}^n \frac1k.

    This gives the candidate maximum and candidate maximizers.

  3. For each slab Im=[m/n,(m+1)/n)\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} I_m=[m/n,(m+1)/n), the verified child result from subtask 0001 shows that

    max⁡x∈ImEn(x)=Fn(m):=m−∑k=1n⌊km/n⌋k=∑k=1n{km/n}k.\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} \max_{x\in I_m}E_n(x)=F_n(m):=m-\sum_{k=1}^n\frac{\lfloor km/n\rfloor}{k} =\sum_{k=1}^n\frac{\{km/n\}}{k}.

    So the continuous problem reduces to a discrete optimization over m=0,…,n−1\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} m=0,\dots,n-1.

  4. The verified child result from subtask 0002 proves the sharp discrete bound

    Fn(m)≤Hn−1\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} F_n(m)\le H_n-1

    for all 0≤m≤n−1\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} 0\le m\le n-1, with equality if and only if m=n−1\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} m=n-1.

  5. Combining the slab reduction with the discrete maximization, the maximizers on [0,1)\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} [0,1) are exactly the points in [(n−1)/n,1)\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} [(n-1)/n,1). By periodicity, the full set of maximizers is

    ⋃a∈Z[a+n−1n,a+1),\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} \bigcup_{a\in\mathbb Z}\left[a+\frac{n-1}{n},a+1\right),

    and the maximal value is Hn−1=∑k=2n1k\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} H_n-1=\sum_{k=2}^n \frac1k.

2Proof Body

Let

En(x):=⌊nx⌋−∑k=1n⌊kx⌋k,Hn:=∑k=1n1k.\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} E_n(x):=\lfloor nx\rfloor-\sum_{k=1}^n \frac{\lfloor kx\rfloor}{k}, \qquad H_n:=\sum_{k=1}^n \frac1k.

We determine all real numbers x\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} x for which En(x)\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} E_n(x) is maximal.

We first remove the integer part of x\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} x. The argument is a direct cancellation after shifting by an integer.

Lemma 2.1.

For every real number x\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} x and every integer t\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} t, one has

En(x+t)=En(x).\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} E_n(x+t)=E_n(x).

Consequently it is enough to maximize En\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} E_n on [0,1)\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} [0,1).

Proof.

For each integer t\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} t and each 1≤k≤n\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} 1\le k\le n,

⌊k(x+t)⌋=⌊kx+kt⌋=⌊kx⌋+kt.\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} \lfloor k(x+t)\rfloor=\lfloor kx+kt\rfloor=\lfloor kx\rfloor+kt.

Therefore

En(x+t)=⌊nx⌋+nt−∑k=1n⌊kx⌋+ktk=⌊nx⌋−∑k=1n⌊kx⌋k=En(x).\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} E_n(x+t) =\lfloor nx\rfloor+nt-\sum_{k=1}^n \frac{\lfloor kx\rfloor+kt}{k} =\lfloor nx\rfloor-\sum_{k=1}^n \frac{\lfloor kx\rfloor}{k} =E_n(x).

Hence En\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} E_n is 1\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} 1-periodic, so it suffices to work on [0,1)\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} [0,1).

The next step identifies a full interval on which the value is constant. This produces the candidate extremal value immediately.

Lemma 2.2.

If x∈[(n−1)/n,1)\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} x\in[(n-1)/n,1), then

⌊kx⌋=k−1for every 1≤k≤n.\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} \lfloor kx\rfloor=k-1 \qquad\text{for every }1\le k\le n.

Consequently,

En(x)=Hn−1.\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} E_n(x)=H_n-1.
Proof.

Fix x∈[(n−1)/n,1)\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} x\in[(n-1)/n,1) and 1≤k≤n\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} 1\le k\le n. Since x<1\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} x<1, we have kx<k\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} kx<k. Also

kx≥k(n−1)n=k−kn≥k−1.\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} kx\ge \frac{k(n-1)}{n}=k-\frac{k}{n}\ge k-1.

Thus k−1≤kx<k\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} k-1\le kx<k, so ⌊kx⌋=k−1\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} \lfloor kx\rfloor=k-1.

Substituting into the definition of En\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} E_n gives

En(x)=(n−1)−∑k=1nk−1k=(n−1)−∑k=1n(1−1k)=Hn−1.\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} E_n(x) =(n-1)-\sum_{k=1}^n \frac{k-1}{k} =(n-1)-\sum_{k=1}^n\left(1-\frac1k\right) =H_n-1.

To control the other slabs, we use the verified output of child subtask 0001. The main point is that on a fixed slab Im=[m/n,(m+1)/n)\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} I_m=[m/n,(m+1)/n) the term ⌊nx⌋\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} \lfloor nx\rfloor is frozen at m\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} m, and the remaining floor terms are minimized at the left endpoint.

Lemma 2.3.

For each integer m\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} m with 0≤m≤n−1\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} 0\le m\le n-1, define

Im:=[mn,m+1n),Fn(m):=m−∑k=1n⌊km/n⌋k.\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} I_m:=\left[\frac{m}{n},\frac{m+1}{n}\right), \qquad F_n(m):=m-\sum_{k=1}^n \frac{\lfloor km/n\rfloor}{k}.

Then every x∈Im\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} x\in I_m satisfies

En(x)≤Fn(m).\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} E_n(x)\le F_n(m).

Moreover:

  • if 0≤m≤n−2\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} 0\le m\le n-2, then equality is attained at x=m/n\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} x=m/n;

  • if m=n−1\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} m=n-1, then equality holds for every x∈In−1\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} x\in I_{n-1}.

Finally,

Fn(m)=∑k=1n{km/n}k.\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} F_n(m)=\sum_{k=1}^n \frac{\{km/n\}}{k}.
Proof.

Fix m∈{0,…,n−1}\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} m\in\{0,\dots,n-1\} and x∈Im\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} x\in I_m. Then ⌊nx⌋=m\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} \lfloor nx\rfloor=m. Also x≥m/n\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} x\ge m/n, so for each 1≤k≤n\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} 1\le k\le n we have

kx≥kmn,\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} kx\ge \frac{km}{n},

hence by monotonicity of the floor function,

⌊kx⌋≥⌊kmn⌋.\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} \lfloor kx\rfloor\ge \left\lfloor \frac{km}{n}\right\rfloor.

After dividing by k\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} k and summing over k=1,…,n\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} k=1,\dots,n, we obtain

∑k=1n⌊kx⌋k≥∑k=1n⌊km/n⌋k.\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} \sum_{k=1}^n\frac{\lfloor kx\rfloor}{k} \ge \sum_{k=1}^n\frac{\lfloor km/n\rfloor}{k}.

Subtracting from ⌊nx⌋=m\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} \lfloor nx\rfloor=m yields

En(x)=m−∑k=1n⌊kx⌋k≤m−∑k=1n⌊km/n⌋k=Fn(m).\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} E_n(x) =m-\sum_{k=1}^n\frac{\lfloor kx\rfloor}{k} \le m-\sum_{k=1}^n\frac{\lfloor km/n\rfloor}{k} =F_n(m).

If 0≤m≤n−2\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} 0\le m\le n-2, then m/n∈Im\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} m/n\in I_m, and direct substitution gives

En(m/n)=⌊n⋅mn⌋−∑k=1n⌊k(m/n)⌋k=m−∑k=1n⌊km/n⌋k=Fn(m).\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} E_n(m/n) =\left\lfloor n\cdot \frac{m}{n}\right\rfloor -\sum_{k=1}^n\frac{\lfloor k(m/n)\rfloor}{k} =m-\sum_{k=1}^n\frac{\lfloor km/n\rfloor}{k} =F_n(m).

Thus equality is attained at x=m/n\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} x=m/n.

If m=n−1\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} m=n-1 and x∈In−1=[(n−1)/n,1)\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} x\in I_{n-1}=[(n-1)/n,1), then by Lemma 2.2,

⌊kx⌋=k−1for every 1≤k≤n.\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} \lfloor kx\rfloor=k-1 \qquad\text{for every }1\le k\le n.

Also

⌊k(n−1)n⌋=k−1for every 1≤k≤n,\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} \left\lfloor \frac{k(n-1)}{n}\right\rfloor=k-1 \qquad\text{for every }1\le k\le n,

so

En(x)=(n−1)−∑k=1nk−1k=(n−1)−∑k=1n⌊k(n−1)/n⌋k=Fn(n−1).\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} E_n(x) =(n-1)-\sum_{k=1}^n \frac{k-1}{k} =(n-1)-\sum_{k=1}^n \frac{\lfloor k(n-1)/n\rfloor}{k} =F_n(n-1).

Hence equality holds for every x∈In−1\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} x\in I_{n-1}.

Finally, using {y}=y−⌊y⌋\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} \{y\}=y-\lfloor y\rfloor,

∑k=1n{km/n}k=∑k=1nkm/nk−∑k=1n⌊km/n⌋k=∑k=1nmn−∑k=1n⌊km/n⌋k=m−∑k=1n⌊km/n⌋k=Fn(m).\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} \sum_{k=1}^n \frac{\{km/n\}}{k} =\sum_{k=1}^n \frac{km/n}{k}-\sum_{k=1}^n \frac{\lfloor km/n\rfloor}{k} =\sum_{k=1}^n \frac{m}{n}-\sum_{k=1}^n \frac{\lfloor km/n\rfloor}{k} =m-\sum_{k=1}^n \frac{\lfloor km/n\rfloor}{k} =F_n(m).

The last ingredient is the verified output of child subtask 0002, which solves the discrete optimization. We reproduce the argument because the equality case matters for the final set of maximizers.

Lemma 2.4.

For every integer m\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} m with 0≤m≤n−1\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} 0\le m\le n-1,

Fn(m)≤Hn−1.\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} F_n(m)\le H_n-1.

Moreover,

Fn(m)=Hn−1⟺m=n−1.\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} F_n(m)=H_n-1 \quad\Longleftrightarrow\quad m=n-1.
Proof.

Since {nm/n}=0\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} \{nm/n\}=0, we may write

Fn(m)=∑k=1n−1{km/n}k.\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} F_n(m)=\sum_{k=1}^{n-1}\frac{\{km/n\}}{k}.

For 1≤k≤n−1\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} 1\le k\le n-1, let

rk:=n{kmn}.\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} r_k:=n\left\{\frac{km}{n}\right\}.

Then rk\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} r_k is the least nonnegative residue of km\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} km modulo n\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} n, and

Fn(m)=1n∑k=1n−1rkk.\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} F_n(m)=\frac1n\sum_{k=1}^{n-1}\frac{r_k}{k}.

Let d=gcd⁡(m,n)\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} d=\gcd(m,n), and write n=db\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} n=db and m=da\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} m=da with gcd⁡(a,b)=1\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} \gcd(a,b)=1. We first determine the multiset of residues {rk:1≤k≤n−1}\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} \{r_k:1\le k\le n-1\}. Every k∈{1,…,n−1}\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} k\in\{1,\dots,n-1\} can be written uniquely as

k=tb+s\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} k=tb+s

with 0≤t≤d−1\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} 0\le t\le d-1 and 0≤s≤b−1\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} 0\le s\le b-1.

If s=0\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} s=0, then k=tb\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} k=tb and

km=(tb)(da)=tda b\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} km=(tb)(da)=tda\,b

is divisible by db=n\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} db=n, so rk=0\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} r_k=0. Hence 0\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} 0 occurs exactly d−1\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} d-1 times, corresponding to t=1,…,d−1\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} t=1,\dots,d-1.

Now fix 1≤s≤b−1\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} 1\le s\le b-1. Modulo n=db\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} n=db we have

km=(tb+s)da≡sda(moddb),\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} km=(tb+s)da\equiv sda \pmod{db},

so

rk=dρs,\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} r_k=d\rho_s,

where ρs\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} \rho_s is the least positive residue of as\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} as modulo b\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} b. Because gcd⁡(a,b)=1\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} \gcd(a,b)=1, multiplication by a\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} a permutes the nonzero residue classes modulo b\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} b. Therefore, as s\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} s runs through 1,…,b−1\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} 1,\dots,b-1, the values ρs\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} \rho_s run through 1,…,b−1\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} 1,\dots,b-1 exactly once. For each fixed s\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} s, the residue rtb+s\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} r_{tb+s} is independent of t\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} t, and t\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} t has exactly d\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} d possible values. Thus the multiset {rk:1≤k≤n−1}\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} \{r_k:1\le k\le n-1\} consists of

d,2d,…,(b−1)d\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} d,2d,\dots,(b-1)d

each repeated exactly d\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} d times, together with 0\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} 0 repeated exactly d−1\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} d-1 times.

Let

z1≥z2≥⋯≥zn−1\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} z_1\ge z_2\ge \cdots \ge z_{n-1}

be the decreasing rearrangement of r1,…,rn−1\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} r_1,\dots,r_{n-1}. Then the preceding description shows that

n−d,…,n−d⏟d times,n−2d,…,n−2d⏟d times,…,d,…,d⏟d times,0,…,0\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} \underbrace{n-d,\dots,n-d}_{d\text{ times}}, \underbrace{n-2d,\dots,n-2d}_{d\text{ times}}, \dots, \underbrace{d,\dots,d}_{d\text{ times}}, 0,\dots,0

is exactly the sequence (z1,…,zn−1)\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} (z_1,\dots,z_{n-1}).

We next use the elementary ordering principle that for fixed nonnegative numbers, the weighted sum with weights 1,1/2,…,1/(n−1)\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} 1,1/2,\dots,1/(n-1) is maximized by placing the numbers in decreasing order. Indeed, if a sequence (u1,…,un−1)\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} (u_1,\dots,u_{n-1}) has an inversion ui<uj\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} u_i<u_j with i<j\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} i<j, then swapping ui\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} u_i and uj\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} u_j changes ∑uk/k\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} \sum u_k/k by

uji+uij−uii−ujj=(uj−ui)(1i−1j)>0.\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} \frac{u_j}{i}+\frac{u_i}{j}-\frac{u_i}{i}-\frac{u_j}{j} =(u_j-u_i)\left(\frac1i-\frac1j\right)>0.

Repeatedly removing inversions yields the decreasing rearrangement, so

∑k=1n−1rkk≤∑k=1n−1zkk.\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} \sum_{k=1}^{n-1}\frac{r_k}{k}\le \sum_{k=1}^{n-1}\frac{z_k}{k}.

Therefore

Fn(m)≤1n∑k=1n−1zkk.\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} F_n(m)\le \frac1n\sum_{k=1}^{n-1}\frac{z_k}{k}.

We now compare zk\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} z_k with the extremal profile n−k\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} n-k. Fix i∈{1,…,n−1}\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} i\in\{1,\dots,n-1\}. If i≤n−d\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} i\le n-d, then i=(j−1)d+r\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} i=(j-1)d+r for some 1≤j≤b−1\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} 1\le j\le b-1 and 1≤r≤d\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} 1\le r\le d, so

zi=n−jd.\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} z_i=n-jd.

Since i≤jd\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} i\le jd, we obtain

zi=n−jd≤n−i.\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} z_i=n-jd\le n-i.

If i≥n−d+1\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} i\ge n-d+1, then zi=0≤n−i\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} z_i=0\le n-i. Hence

zi≤n−ifor every 1≤i≤n−1.\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} z_i\le n-i \qquad\text{for every }1\le i\le n-1.

Consequently,

Fn(m)≤1n∑i=1n−1n−ii=∑i=1n−11i−n−1n=Hn−1.\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} F_n(m)\le \frac1n\sum_{i=1}^{n-1}\frac{n-i}{i} =\sum_{i=1}^{n-1}\frac1i-\frac{n-1}{n} =H_n-1.

This proves the upper bound.

It remains to determine when equality holds. If d>1\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} d>1, then

z1=n−d<n−1,\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} z_1=n-d<n-1,

so the inequality z1≤n−1\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} z_1\le n-1 is strict, and therefore

1n∑i=1n−1zii<1n∑i=1n−1n−ii.\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} \frac1n\sum_{i=1}^{n-1}\frac{z_i}{i} < \frac1n\sum_{i=1}^{n-1}\frac{n-i}{i}.

Hence equality in Fn(m)≤Hn−1\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} F_n(m)\le H_n-1 is impossible unless d=1\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} d=1.

Assume now that Fn(m)=Hn−1\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} F_n(m)=H_n-1. Then necessarily d=1\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} d=1. In that case the multiset of residues is exactly {1,2,…,n−1}\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} \{1,2,\dots,n-1\}, so the decreasing rearrangement is

zi=n−ifor every 1≤i≤n−1.\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} z_i=n-i \qquad\text{for every }1\le i\le n-1.

These values are pairwise distinct. Equality in the rearrangement step

∑k=1n−1rkk≤∑k=1n−1zkk\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} \sum_{k=1}^{n-1}\frac{r_k}{k}\le \sum_{k=1}^{n-1}\frac{z_k}{k}

can therefore occur only if there are no inversions to remove, that is,

rk=zk=n−kfor every 1≤k≤n−1.\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} r_k=z_k=n-k \qquad\text{for every }1\le k\le n-1.

Taking k=1\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} k=1 gives

m=r1=n−1,\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} m=r_1=n-1,

because 0≤m≤n−1\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} 0\le m\le n-1 and r1\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} r_1 is the least nonnegative residue of m\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} m modulo n\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} n.

Conversely, if m=n−1\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} m=n-1, then

Fn(n−1)=∑k=1n−1{k(n−1)/n}k=∑k=1n−11−k/nk=Hn−1.\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} F_n(n-1)=\sum_{k=1}^{n-1}\frac{\{k(n-1)/n\}}{k} =\sum_{k=1}^{n-1}\frac{1-k/n}{k} =H_n-1.

Thus

Fn(m)=Hn−1⟺m=n−1.\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} F_n(m)=H_n-1 \quad\Longleftrightarrow\quad m=n-1.

Conclusion.   By Lemma 2.1, it suffices to maximize En\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} E_n on [0,1)\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} [0,1). For each m∈{0,…,n−1}\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} m\in\{0,\dots,n-1\}, let

Im=[mn,m+1n).\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} I_m=\left[\frac{m}{n},\frac{m+1}{n}\right).

If x∈Im\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} x\in I_m, then Lemma 2.3 gives

En(x)≤Fn(m).\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} E_n(x)\le F_n(m).

By Lemma 2.4,

Fn(m)≤Hn−1,\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} F_n(m)\le H_n-1,

with equality if and only if m=n−1\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} m=n-1. Hence

En(x)≤Hn−1for all x∈[0,1).\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} E_n(x)\le H_n-1 \qquad\text{for all }x\in[0,1).

Moreover, if x∈[(n−1)/n,1)=In−1\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} x\in[(n-1)/n,1)=I_{n-1}, then Lemma 2.2 gives

En(x)=Hn−1.\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} E_n(x)=H_n-1.

Thus the maximizers in [0,1)\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} [0,1) are exactly the points of [(n−1)/n,1)\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} [(n-1)/n,1), and the maximal value is

Hn−1=∑k=2n1k.\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} H_n-1=\sum_{k=2}^n \frac1k.

Using Lemma 2.1, the full set of maximizers in R\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} \mathbb R is

⋃a∈Z[a+n−1n,a+1).\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} \bigcup_{a\in\mathbb Z}\left[a+\frac{n-1}{n},a+1\right).

Therefore the expression

⌊nx⌋−∑k=1n⌊kx⌋k\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} \lfloor nx\rfloor-\sum_{k=1}^n\frac{\lfloor kx\rfloor}{k}

has maximal value Hn−1\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} H_n-1, attained exactly for those real numbers x\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} x whose fractional part lies in [(n−1)/n,1)\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} [(n-1)/n,1).

3History

Cycle 1.   Started the prover state from scratch. Proved the periodicity reduction and the explicit value on the top slab [(n−1)/n,1)\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} [(n-1)/n,1). Introduced exactly two subtasks: one to reduce the optimization on each slab to the discrete quantity Fn(m)\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} F_n(m), and one to prove that Fn(m)\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} F_n(m) is uniquely maximized at m=n−1\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} m=n-1 with value Hn−1\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} H_n-1.

Cycle 2.   Incorporated the verified outputs of child subtasks 0001 and 0002 into the parent proof body. Replaced the conditional conclusion by full lemmas proving the slab reduction and the discrete maximization, removed the subtask placeholders, and completed the proof that the maximal value is Hn−1\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} H_n-1 and that the maximizers are exactly the real numbers with fractional part in [(n−1)/n,1)\newcommand{\Mbegin}{\left[ \begin{matrix}} \newcommand{\Mend}{\end{matrix} \right]} \newcommand{\norm}[1]{\left\| #1 \right\|} \newcommand{\Q}{\mathbb{Q}} \newcommand{\Otil}{\widetilde{O}} \newcommand{\poly}{\mathrm{poly}} \newcommand{\diag}{\mathsf{diag}} \newcommand{\col}{\mathrm{col}} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} [(n-1)/n,1).