Characteristics of Floor and Ceiling Function
Theorem
Let $f: \R \to \Z$ be an integer-valued function which satisfies both of the following:
- $(1): \quad \map f {x + 1} = \map f x + 1$
- $(2): \quad \forall n \in \Z_{> 0}: \map f x = \map f {\dfrac {\map f {n x} } n}$
Then either:
- $\forall x \in \Q: \map f x = \floor x$
or:
- $\forall x \in \Q: \map f x = \ceiling x$
Real Domain
Let $f: \R \to \Z$ be an integer-valued function which satisfies both of the following:
- $(1): \quad \map f {x + 1} = \map f x + 1$
- $(2): \quad \forall n \in \Z_{> 0}: \map f x = \map f {\dfrac {\map f {n x} } n}$
Then it is not necessarily the case that either:
- $\forall x \in \R: \map f x = \floor x$
or:
- $\forall x \in \R: \map f x = \ceiling x$
Proof
From $(1)$, by induction we have:
- $\forall n \in \N: \map f {x + n} = \map f x + n$
and
- $\forall n \in\N: \map f {x - n} = \map f x - n$
and therefore, in particular:
- $(3): \quad \forall n \in \Z: \map f n = \map f 0 + n$
From $(2)$, we get
\(\ds \map f 0\) | \(=\) | \(\ds \map f {\map f 0}\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \map f 0 + \map f 0\) | using $(3)$ and $f$ being integer valued |
Hence
- $\map f 0 = 0$
Thus from $(3)$ it follows that:
- $\forall n \in \Z: \map f n = n$
Suppose that $\map f {\dfrac 1 2} = k \le 0$.
Then:
\(\ds k\) | \(=\) | \(\ds \map f {\dfrac 1 {1 - 2 k} \map f {\dfrac 1 2 - k} }\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \map f {\dfrac 1 {1 - 2 k} \paren {\map f {\dfrac 1 2} - k} }\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \map f 0\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds 0\) |
We show that in this case, by induction:
- $\map f {\dfrac 1 n} = 0$ for all $n \in \N$
Induction hypothesis:
- $\map f {\dfrac 1 {n - 1} } = 0$
Then from $(1)$:
- $\map f {\dfrac n {n - 1} } = \map f {\dfrac 1 {n - 1} + 1} = 0 + 1 = 1$
so:
\(\ds \map f {\dfrac 1 n}\) | \(=\) | \(\ds \map f {\dfrac 1 n \map f {\dfrac n {n - 1} } }\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \map f {\dfrac 1 {n - 1} }\) | using $(2)$ | |||||||||||
\(\ds \) | \(=\) | \(\ds 0\) |
Finally, we show by induction on $m$ that even:
- $\map f {\dfrac m n} = 0$
for $m \in \set {1, \ldots, n - 1}$.
Above we have shown this for $m = 1$.
Let $1 \le m < n$.
If $m \divides n$, then
- $\map f {\dfrac m n} = \map f {\dfrac 1 {n / m} } = 0$
Otherwise, write:
- $n = \paren {k - 1} m + r$
Then:
- $k > 1$
and:
- $1 \le r \le m - 1$
We therefore have:
- $k m = n + m - r$
so by the induction hypothesis:
- $\map f {\dfrac {k m} n} = \map f {1 + \dfrac {m - r} n} = 1 + \map f {\dfrac {m - r} n} = 1$
Then:
\(\ds \map f {\dfrac m n}\) | \(=\) | \(\ds \map f {\dfrac 1 m \map f {\dfrac {m k} n} }\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \map f {\dfrac 1 m}\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds 0\) |
By $(1)$, this shows that
- $\map f {\dfrac 1 2} \le 0 \implies \map f x = \floor x$
for all rational $x$.
Suppose that $\map f {\dfrac 1 2} = k > 0$.
Then the integer-valued function $g: \R \to \Z$ satisfies:
- $\map g x = -\map f {-x}$
satisfies $(1)$ and $(2)$, and also:
\(\ds \map g {\dfrac 1 2}\) | \(=\) | \(\ds 1 - \map f {\dfrac 1 2}\) | ||||||||||||
\(\ds \) | \(\ge\) | \(\ds 0\) | ||||||||||||
\(\ds \leadsto \ \ \) | \(\ds \map f x\) | \(=\) | \(\ds -\map g {-x}\) | |||||||||||
\(\ds \) | \(=\) | \(\ds -\floor {-x}\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \ceiling x\) | Floor of Negative equals Negative of Ceiling |
Thus:
- $\map f {\dfrac 1 2} > 0 \implies \map f x = \ceiling x$
for all rational $x$.
$\blacksquare$
Historical Note
The result Characteristics of Floor and Ceiling Function was presented by Peter Eisele and Karl Peter Hadeler in $1990$.
The previous work done in $1905$ by Georg Hamel to establish that the result does not necessarily hold in the real domain is to be noted.
Sources
- 1990: P. Eisele and K.P. Hadeler: Games of cards, dynamical systems, and a characterization of the floor and ceiling functions (Amer. Math. Monthly Vol. 97: pp. 466 – 477) www.jstor.org/stable/2323829
- 1997: Donald E. Knuth: The Art of Computer Programming: Volume 1: Fundamental Algorithms (3rd ed.) ... (previous) ... (next): $\S 1.2.4$: Integer Functions and Elementary Number Theory: Exercise $49$