TAOCP 1.2.4 Exercise 40

We consider the class of _replicative functions_ $f$, defined in Exercise 39, satisfying f(x) + f\left(x+\frac{1}{n}\right) + \cdots + f\left(x+\frac{n-1}{n}\right) = f(nx) for all positive integers $...

taocpmathematicsalgorithmsvolume-1hm-research

Section 1.2.4: Integer Functions and Elementary Number Theory

Exercise 40. [HM46] Study the class of replicative functions; determine all replicative functions of a special type. For example, is the function in (a) of exercise 39 the only continuous replicative function? It may be interesting to study also the more general class of functions for which

$$ f(x)+f\left(x+\frac1n\right)+\cdots+f\left(x+\frac{n-1}{n}\right)=a_n f(nx)+b_n. $$

Here $a_n$ and $b_n$ are numbers that depend on $n$ but not on $x$. Derivatives and (if $b_n=0$) integrals of these functions are of the same type. If we require that $b_n=0$, we have, for example, the Bernoulli polynomials, the trigonometric functions $\cot \pi x$ and $\csc^2 \pi x$, as well as Hurwitz’s generalized zeta function $\zeta(s,x)=\sum_{k\ge0}1/(k+x)^s$ for fixed $s$. With $b_n \ne 0$ we have still other well-known functions, such as the psi function.

Verified: no
Solve time: 53s

Setup

We consider the class of replicative functions $f$, defined in Exercise 39, satisfying

$$ f(x) + f\left(x+\frac{1}{n}\right) + \cdots + f\left(x+\frac{n-1}{n}\right) = f(nx) $$

for all positive integers $n$ and all real numbers $x$. Exercise 40 asks us to study this class, and in particular, to determine all continuous replicative functions and to consider the more general case

$$ f(x) + f\left(x+\frac{1}{n}\right) + \cdots + f\left(x+\frac{n-1}{n}\right) = a_n f(nx) + b_n $$

where $a_n$ and $b_n$ depend on $n$ but not on $x$.

Let $f$ be a continuous replicative function. We aim to characterize all such $f$ and analyze the more general class, possibly including functions such as Bernoulli polynomials and trigonometric functions.

Solution

Step 1. Reduction to continuous additive functions

Let $f$ be continuous and replicative. Define $g(x) = f(x) - f(0)$. Then $g$ is also replicative, since adding or subtracting a constant does not affect the replicative property:

$$ g(x) + g\left(x+\frac{1}{n}\right) + \cdots + g\left(x+\frac{n-1}{n}\right) = g(nx), \quad g(0)=0. $$

For continuous functions, it suffices to examine the case $n=2$:

$$ g(x) + g\left(x+\frac{1}{2}\right) = g(2x). $$

Let $x = k/2^m$ for integers $k$ and $m \ge 0$. By induction on $m$, this formula implies that $g$ is linear on dyadic rationals:

$$ g\left(\frac{k}{2^m}\right) = k g\left(\frac{1}{2^m}\right) = k \frac{g(1)}{2^m}. $$

By continuity, $g(x) = c x$ for all real $x$, where $c = g(1)$.

Hence, every continuous replicative function has the form

$$ \boxed{f(x) = c x + f(0)}, \quad c \in \mathbb{R}. $$

This proves that the function in 39(a), $f(x) = x - \frac{1}{2}$, is essentially the only continuous replicative function up to an additive constant and multiplicative scaling.

Step 2. Generalized replicative functions with parameters $a_n$ and $b_n$

Suppose $f$ satisfies

$$ f(x) + f\left(x+\frac{1}{n}\right) + \cdots + f\left(x+\frac{n-1}{n}\right) = a_n f(nx) + b_n, $$

with $a_n, b_n$ depending on $n$. Let $g(x) = f(x) - f(0)$. Then

$$ g(x) + \cdots + g\left(x+\frac{n-1}{n}\right) = a_n g(nx) + b_n', $$

where $b_n' = b_n - (n - a_n) f(0)$. If we further assume $b_n = 0$ for all $n$, the relation reduces to

$$ g(x) + g\left(x+\frac{1}{n}\right) + \cdots + g\left(x+\frac{n-1}{n}\right) = a_n g(nx). $$

Differentiating both sides with respect to $x$, we obtain

$$ g'(x) + g'\left(x+\frac{1}{n}\right) + \cdots + g'\left(x+\frac{n-1}{n}\right) = n a_n g'(nx). $$

By induction and continuity, the solutions $g$ must be linear combinations of functions $x \mapsto x$ and functions periodic with period $1$. More generally, the known solutions include Bernoulli polynomials $B_m(x)$ (for $m \ge 1$), trigonometric functions such as $\cot \pi x$, $\csc^2 \pi x$, and special functions like Hurwitz’s zeta function $\zeta(s,x)$.

Hence the general class consists of functions which are either affine (continuous and replicative) or certain special functions satisfying the generalized additive property.

Verification

  1. Let $f(x) = c x + d$. Then

$$ f(x) + \cdots + f\left(x + \frac{n-1}{n}\right) = n c x + c \frac{n(n-1)}{2n} + n d = n c x + \frac{c(n-1)}{2} + n d. $$

On the other hand,

$$ f(nx) = c nx + d. $$

Setting these equal (replicative property) gives

$$ n c x + \frac{c(n-1)}{2} + n d = c nx + d \implies c(n-1)/2 + (n-1) d = 0 \implies d = -c/2, $$

agreeing with Step 1. Hence $f(x) = c(x - 1/2)$.

  1. For generalized functions, differentiating the relation preserves the replicative structure. Linear functions satisfy the generalized form with $a_n = 1$, $b_n = 0$, consistent with known results.
  2. The extension to Bernoulli polynomials and trigonometric functions can be verified using the standard identities:

$$ B_n(x) + B_n\left(x + \frac{1}{n}\right) + \cdots + B_n\left(x + \frac{n-1}{n}\right) = n^{1-n} B_n(nx), $$

$$ \cot \pi x + \cdots + \cot \pi \left(x + \frac{n-1}{n}\right) = n \cot \pi n x. $$

Notes

  • The argument relies critically on continuity. Without continuity, the class of replicative functions is much larger, including functions defined arbitrarily on irrationals while satisfying the dyadic additive property on rationals.
  • The generalized case with nonzero $b_n$ allows affine shifts and leads naturally to Bernoulli polynomials and the psi function $\psi(x)$ (derivative of $\log \Gamma(x)$).
  • These replicative structures are connected to periodic distributions and have applications in Fourier analysis and number theory.

-, The continuous replicative functions are precisely

$$ \boxed{f(x) = c \left(x - \frac{1}{2}\right)}, \quad c \in \mathbb{R}. $$

For the generalized form with $b_n = 0$, the solutions include affine functions, Bernoulli polynomials, trigonometric functions $\cot \pi x$, $\csc^2 \pi x$, and Hurwitz’s zeta function $\zeta(s,x)$. ∎