Sawtooth and replicative functions

Posted on by John

Here’s something I ran across in Volume 2 of Donald Knuth’s The Art of Computer Programming.

Knuth defines the sawtooth function by

((x)) = x − (⌊x⌋ + ⌈x⌉)/2.

Here’s a plot.

This is an interesting way to write the sawtooth function, one that could make it easier to prove things about, such as the following theorem. For positive integers n, we have

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

It’s not at all obvious, at least to me, that this should be true.

Knuth does not give a proof but leaves the proof to Exercise 2 in Section 3.3.3. I suppose you could prove it by slugging it out with floor and ceiling identities, but I looked at the solutions to see whether Knuth has a more elegant proof.

The solution for Exercise 2 says to see exercises 38 and 39 in Volume 1, section 1.2.4. These exercises break the problem of proving the theorem above into smaller parts. They also generalize the problem, defining a function f to be replicative if it satisfies the equation

f(nx) = \sum_{i=0}^{n-1} f\left(x + \frac{i}{n} \right )

The theorem above says that the sawtooth function is replicative. Other examples of replicative functions include the floor function and the function that takes x to x − ½.

Related posts

3 thoughts on “Sawtooth and replicative functions”

  1. Markus

    This replicative identity comes from the corresponding identity for Bernoulli polynomials (scaled by a suitable factor) as the saawtooth function is more or less the first Bernoulli polynomial: https://en.wikipedia.org/wiki/Bernoulli_polynomials#Multiplication_theorems

    An analogous identity, with the sum replaced by a product holds for the Gamma function as well (scaled by a factor as well): https://en.wikipedia.org/wiki/Gamma_function#Pi_function

    Both identities (and presumably many more!) boil down to a identity coming from the geometric series and the exponential function, see this paper from Granville & Zun on p. 123 (7th page in the PDF file): https://projecteuclid.org/journals/pacific-journal-of-mathematics/volume-172/issue-1/Values-of-Bernoulli-polynomials/pjm/1102366187.full

    (They refer to Lerch “Zur Theorie des Fermatschen Quotienten” in Math. Ann. 60 (1905), 471-490, but I couldn’t find the identity there ad hoc.)

  3. Diethard Michaelis

    Quite obvious but not seen in TAOCP:
    For replicative f always f(1/2) = 0.

    There is some text on replicative functions in the ProofWiki,
    BUT they did not even get the definition right:
    ForAll integers n >= 0: f(nx) = …
    instead of correctly n > 0.

Comments are closed.