TAOCP 1.2.4 Exercise 39
Let S_n(f;x)=\sum_{k=0}^{n-1}f\!
Section 1.2.4: Integer Functions and Elementary Number Theory
Exercise 39. [HM35] A function $f$ for which
$$f(x)+f\left(x+\frac1n\right)+\cdots+f\left(x+\frac{n-1}{n}\right)=f(nx),$$
whenever $n$ is a positive integer, is called a replicative function. The previous exercise establishes the fact that $\lfloor x \rfloor$ is replicative. Show that the following functions are replicative:
a) $f(x)=x-\tfrac12$;
b) $f(x)=[x \text{ is an integer}]$;
c) $f(x)=[x \text{ is a positive integer}]$;
d) $f(x)=[\text{there exists a rational number } r \text{ and an integer } m \text{ such that } x=r\pi+m]$;
e) three other functions like the one in (d), with $r$ and/or $m$ restricted to positive values;
f) $f(x)=\log|2\sin \pi x|$, if the value $f(x)=-\infty$ is allowed;
g) the sum of any two replicative functions;
h) a constant multiple of a replicative function;
i) the function $g(x)=f(x-\lfloor x \rfloor)$, where $f(x)$ is replicative.
Verified: no
Solve time: 5m26s
Let
$$ S_n(f;x)=\sum_{k=0}^{n-1}f!\left(x+\frac{k}{n}\right). $$
A function $f$ is replicative iff
$$ S_n(f;x)=f(nx) $$
for every real $x$ and every positive integer $n$.
We verify this property in each case.
(a) $f(x)=x-\frac12$
$$ S_n(f;x) = \sum_{k=0}^{n-1} \left(x+\frac{k}{n}-\frac12\right) = nx+\frac1n\sum_{k=0}^{n-1}k-\frac n2. $$
Since
$$ \sum_{k=0}^{n-1}k=\frac{n(n-1)}2, $$
we obtain
$$ S_n(f;x) = nx+\frac{n-1}{2}-\frac n2 = nx-\frac12 = f(nx). $$
Hence $f$ is replicative.
(b) $f(x)=[x\text{ is an integer}]$
Suppose first that $nx\notin\mathbb Z$. If some
$$ x+\frac{k}{n} $$
were an integer $m$, then
$$ nx=nm-k\in\mathbb Z, $$
a contradiction. Therefore every summand is $0$, and
$$ S_n(f;x)=0=f(nx). $$
Now suppose $nx=t\in\mathbb Z$. Then
$$ x+\frac{k}{n}\in\mathbb Z \iff \frac{t+k}{n}\in\mathbb Z \iff t+k\equiv0\pmod n. $$
Among $k=0,\ldots,n-1$ there is exactly one solution of this congruence. Hence exactly one summand equals $1$, so
$$ S_n(f;x)=1=f(nx). $$
Therefore $f$ is replicative.
(c) $f(x)=[x\text{ is a positive integer}]$
If $nx\notin\mathbb Z$, part (b) shows that none of
$$ x,\ x+\frac1n,\ \ldots,\ x+\frac{n-1}{n} $$
is an integer. Hence
$$ S_n(f;x)=0=f(nx). $$
Now assume $nx=t\in\mathbb Z$.
Case 1: $t\le 0$
For every $k$,
$$ x+\frac{k}{n}=\frac{t+k}{n}. $$
Since $0\le k<n$,
$$ t+k<n. $$
If $(t+k)/n$ were a positive integer, then $t+k\ge n$, which is impossible. Thus none of the summands equals $1$, and
$$ S_n(f;x)=0=f(nx). $$
Case 2: $t>0$
By part (b), exactly one value of $k$ makes $(t+k)/n$ an integer. Since $t>0$ and $k\ge0$, that integer is positive. Hence exactly one summand equals $1$, and
$$ S_n(f;x)=1=f(nx). $$
Therefore $f$ is replicative.
(d)
Let
$$ A={,r\pi+m:r\in\mathbb Q,\ m\in\mathbb Z,}, $$
and let $f$ be the indicator function of $A$.
First suppose $x+\frac{k}{n}\in A$. Then
$$ x+\frac{k}{n}=r\pi+m $$
for some $r\in\mathbb Q$, $m\in\mathbb Z$. Hence
$$ x=r\pi+\left(m-\frac{k}{n}\right). $$
Since $m-\frac{k}{n}\in\mathbb Q$, write it as $q$. Then
$$ nx=(nr)\pi+nq. $$
Because $nr\in\mathbb Q$ and $nq\in\mathbb Q$, write $nq=t+s$ with
$t\in\mathbb Z$, $s\in\mathbb Q$. Then
$$ nx=(nr+s)\pi+t, $$
since $s\pi$ may be absorbed into the rational coefficient of $\pi$. Thus $nx\in A$.
Conversely, suppose
$$ nx=r\pi+m, \qquad r\in\mathbb Q,\ m\in\mathbb Z. $$
Then
$$ x=\frac r n,\pi+\frac m n. $$
Choose the unique $k\in{0,\ldots,n-1}$ such that
$$ m+k\equiv0\pmod n. $$
Then
$$ x+\frac{k}{n} = \frac r n,\pi+\frac{m+k}{n}, $$
and $(m+k)/n\in\mathbb Z$. Hence $x+\frac{k}{n}\in A$.
If two distinct values $k_1,k_2$ gave points of $A$, then subtracting the two representations would yield
$$ \frac{k_1-k_2}{n}\in\mathbb Z. $$
Since $|k_1-k_2|<n$, this forces $k_1=k_2$. Therefore there is exactly one such $k$.
Hence
$$ S_n(f;x)= \begin{cases} 1,& nx\in A,\ 0,& nx\notin A, \end{cases} =f(nx). $$
Thus $f$ is replicative.
(e)
The three analogous indicator functions are
$$ [x=r\pi+m,\ r\in\mathbb Q_{>0},\ m\in\mathbb Z], $$
$$ [x=r\pi+m,\ r\in\mathbb Q,\ m\in\mathbb Z_{>0}], $$
$$ [x=r\pi+m,\ r\in\mathbb Q_{>0},\ m\in\mathbb Z_{>0}]. $$
The proof of part (d) applies with only minor changes.
If
$$ x+\frac{k}{n}=r\pi+m, $$
then
$$ nx=(nr)\pi+nm-k. $$
Positivity of $r$ is preserved because $nr>0$ whenever $r>0$.
Conversely, if
$$ nx=r\pi+m, $$
with the required restrictions, choose $k$ so that
$$ m+k\equiv0\pmod n. $$
Then
$$ x+\frac{k}{n} = \frac r n,\pi+\frac{m+k}{n}. $$
If $r>0$, then $r/n>0$. If $m>0$, then $m+k>0$, so $(m+k)/n$ is a positive integer. The uniqueness argument is exactly the same as in part (d).
Hence each of these three functions is replicative.
(f) $f(x)=\log|2\sin\pi x|$
Allow the value $-\infty$.
Using $\log(ab)=\log a+\log b$,
$$ S_n(f;x) = \log!\prod_{k=0}^{n-1} \left|2\sin\pi\left(x+\frac{k}{n}\right)\right|. $$
The classical identity
$$ \prod_{k=0}^{n-1} 2\sin!\left(\pi\left(x+\frac{k}{n}\right)\right) = 2\sin(n\pi x) $$
implies
$$ \prod_{k=0}^{n-1} \left|2\sin\pi\left(x+\frac{k}{n}\right)\right| = |2\sin(n\pi x)|. $$
Therefore
$$ S_n(f;x) = \log|2\sin(n\pi x)| = f(nx). $$
Hence $f$ is replicative.
(g) The sum of two replicative functions
Let $f$ and $g$ be replicative. Then
$$ S_n(f+g;x) = S_n(f;x)+S_n(g;x) = f(nx)+g(nx) = (f+g)(nx). $$
Therefore $f+g$ is replicative.
(h) A constant multiple of a replicative function
Let $c$ be constant and let $f$ be replicative. Then
$$ S_n(cf;x) = c,S_n(f;x) = c,f(nx) = (cf)(nx). $$
Hence $cf$ is replicative.
(i) $g(x)=f(x-\lfloor x\rfloor)$
Let
$$ {x}=x-\lfloor x\rfloor $$
denote the fractional part, and define
$$ g(x)=f({x}). $$
We must prove that $g$ is replicative.
Write
$$ x=m+\theta, \qquad m\in\mathbb Z, \qquad 0\le\theta<1. $$
Then
$$ g!\left(x+\frac{k}{n}\right) = f!\left(\left{\theta+\frac{k}{n}\right}\right). $$
Hence
$$ S_n(g;x) = \sum_{k=0}^{n-1} f!\left(\left{\theta+\frac{k}{n}\right}\right). $$
Set
$$ a={n\theta}. $$
We now prove the crucial reindexing fact.
For each $k$,
$$ n\left{\theta+\frac{k}{n}\right} = {,n\theta+k,} = {n\theta} = a. $$
Therefore
$$ \left{\theta+\frac{k}{n}\right} = \frac{a+j_k}{n} $$
for some integer $j_k\in{0,\ldots,n-1}$.
If
$$ \frac{a+j_{k_1}}{n} = \frac{a+j_{k_2}}{n}, $$
then $j_{k_1}=j_{k_2}$. Hence distinct fractional parts correspond to distinct $j$'s. But the numbers
$$ \left{\theta+\frac{k}{n}\right}, \qquad k=0,\ldots,n-1, $$
are distinct modulo $1$, because
$$ \left{\theta+\frac{k_1}{n}\right} = \left{\theta+\frac{k_2}{n}\right} $$
would imply
$$ \frac{k_1-k_2}{n}\in\mathbb Z, $$
and therefore $k_1=k_2$. Thus the $j_k$ are distinct. Since there are $n$ of them and each lies in ${0,\ldots,n-1}$, they form a permutation of ${0,\ldots,n-1}$.
Consequently,
$$ S_n(g;x) = \sum_{j=0}^{n-1} f!\left(\frac{a+j}{n}\right). $$
Now apply the replicative property of $f$ with
$$ y=\frac{a}{n}. $$
Then
$$ \sum_{j=0}^{n-1} f!\left(\frac{a}{n}+\frac{j}{n}\right) = f(a). $$
Since
$$ \frac{a}{n}+\frac{j}{n} = \frac{a+j}{n}, $$
the left-hand side is exactly $S_n(g;x)$. Hence
$$ S_n(g;x)=f(a). $$
Finally,
$$ nx=nm+n\theta, $$
so
$$ {nx}={n\theta}=a. $$
Therefore
$$ g(nx) = f({nx}) = f(a). $$
Combining the last two equations gives
$$ S_n(g;x)=g(nx). $$
Thus $g$ is replicative.
$$ \boxed{\text{All functions in (a)-(i) are replicative.}} $$