The Floor Function

Until a few decades ago, $[x]$ was a customary notation for the whole part of a real number $x.$ Nowadays, the floor function notation $\lfloor x\rfloor$ is at least as widely spread. The latter notation for the floor function and its companion for the ceiling function $\lceil x\rceil$ (which is the least integer not less than $x)$ were introduced by Kenneth Iverson in the early 1960s. Because of the extreme utility and frequency of use, the notations made inroads in mathematics literature. (PS: In the old version of the page I wrote: "If it were not for the difficulty of typesetting in HTML, I would follow the crowd. As it is, and for the time being, I shall be using the older $[x]$ notation." However, the development of JavaScript and the MathJax library made using the new notations as easy as using the old ones. Hence, what follows is the renovated variant of the old page.)

For a given real $x,$ $\lfloor x\rfloor$ denotes the largest integer $n$ that does not exceed $x.$ From the definition, $\lfloor x\rfloor + 1$ is always greater than $x.$ $\lfloor x\rfloor = x,$ for all integer $x.$ For non-integer numbers, $\lfloor x\rfloor$ is strictly less than $x.$ The inequality $\lfloor x\rfloor \le x \lt\lfloor x\rfloor +1$ always holds. We can now define other functions via formulas that include $\lfloor x\rfloor.$ Take, for example, $f(x) = \lfloor\sin (x)\rfloor.$ Can you draw the graph of this function?

There are many curiosities related to the floor function. Here are a few spurious examples drawn from an old Russian magazine (Mathematics Education, n1, 1934):

$\lfloor e\rfloor ^{\lfloor \pi\rfloor } + \lfloor \pi\rfloor = \lfloor \pi\rfloor ^{\lfloor e\rfloor } + \lfloor e\rfloor,$

$\lfloor \sqrt{2}\rfloor + \lfloor \sqrt{2}\rfloor = \lfloor \sqrt{4}\rfloor,$

$\lfloor \sqrt{3}\rfloor + \lfloor \sqrt{3}\rfloor = \lfloor \sqrt{6}\rfloor,$

$\lfloor \sqrt{8}\rfloor + \lfloor \sqrt{8}\rfloor = \lfloor \sqrt{16}\rfloor.$

The function has sensible uses as well. Following is a couple of examples where the floor function plays a very meaningful role. In the analysis of Wythoff's game, we had encountered two integer sequences: $A$ and $B$. The $n^{th}$ terms in the sequences $A$ and $B$ are expressed as $\lfloor n\phi\rfloor$ and $\lfloor n\phi^{2}\rfloor,$ respectively, where $\phi$ is the golden ratio $(\sqrt{5} + 1)/2.$ The Beatty squences generalize this construction.

There is a well known problem whose formulation, perhaps even existence itself, depends on the floor function. In [Ref. 2], it has been designated as a *-problem, to indicate an increased level of difficulty.

Let integer $p$ and $q$ be coprime. Prove that

$\displaystyle\bigg\lfloor\frac{p}{q}\bigg\rfloor + \bigg\lfloor\frac{2p}{q}\bigg\rfloor + \bigg\lfloor\frac{3p}{q}\bigg\rfloor + \ldots + \bigg\lfloor\frac{ (q-1)p}{q}\bigg\rfloor =\frac{(p-1)(q-1)}{2}.$

However, the solution that appeals to a geometric interpretation is extremely simple.

Let, for example, $p = 7$ and $q = 16.$ Consider a system of Cartesian coordinates. Draw the line connecting the origin with point $(q, p).$ Note that since $p$ and $q$ are assumed to be coprime, the point $(q, p)$ is visible (from the origin.) That is to say that between the origin and the point $(q, p),$ that line contains no other grid points, points with integer coordinates. The number of such integer points inside the rectangle formed by points $(0, 0),$ $(0, p),$ $(q, 0),$ and $(q, p)$ is $(p - 1)(q - 1).$ $(p - 1)(q - 1)/2$ is half that quantity.

The equation of the diagonal line is $y = (p/q)x.$ It only remains to note that for an integer $0\lt n,$ $\lfloor np/q\rfloor$ is the number of integer points $(n, m)$ below that line. For example, for $n = 8,$ there are $\lfloor 8\cdot 7/16\rfloor = 3$ points, $(8, 1),$ $(8, 2),$ and $(8, 3).$ Since no integer point within the rectangle lies on the diagonal, all such points are either below or above the line. The left-hand side in the required identity counts the number of integer points below the diagonal. As we just saw, the number of such points is $(p - 1)(q - 1)/2.$

Curiously, from the symmetry (in $p$ and $q$) of the right side, we also have

$\displaystyle\bigg\lfloor\frac{q}{p}\bigg\rfloor + \bigg\lfloor\frac{2q}{p}\bigg\rfloor + \bigg\lfloor\frac{3q}{p}\bigg\rfloor + \ldots + \bigg\lfloor\frac{ (p-1)q}{p}\bigg\rfloor =\frac{(p-1)(q-1)}{2}.$

The graph of the floor function consists of a sequence of unit intervals parallel to the $x$-axis.

The dot at the right end of each segment indicates that the point itself is excluded from the graph. The segments include the left end points but not the right end points. Indeed, $\lfloor x\rfloor$ is obtained by omitting the fractional part of $x,$ if any. For an integer $n$ and $x$ satisfying $n \le x \lt n+1,$ $\lfloor x\rfloor = n.$ Therefore, $\lfloor x\rfloor$ is constant in semi-open intervals $[n, n+1).$ Note the behavior for negative numbers. For example, $\lfloor -3.5\rfloor = -4$ in accordance with the definition.

$\lfloor x\rfloor$ has the property $\lfloor x + n\rfloor = \lfloor x\rfloor + n.$ So that integer pieces can be taken in and out of the brackets. The graph of $y = \lfloor\sin (x)\rfloor$ is shown below.

The graph has solitary points (in red) where sine takes value $1$ but, otherwise, consists of line segments, some with excluded endpoints (in blue.) The function inherits from $\sin (x)$ its period, $2\pi.$ You may try to figure out the graph of the function $y =\sin\lfloor x\rfloor$ which is not that nice at all.

To give another application, recollect a remark to the effect that the domain $\mathbb{Z}[\sqrt{m}\space]$ is dense on the real line. The proof can be obtained from two observations. First, for a real $x,$ $x - \lfloor x\rfloor$ is the fractional part of $x,$ a number between $0$ and $1.$ Apply this to $x = \sqrt{m}$ to obtain a member of $\mathbb{Z}[\sqrt{m}\space]$ that lies in the open interval $(0, 1).$

Second, for any number a, $0 \lt a \lt 1,$ $a^{n}$ tends to $0$ as $n$ grows. Therefore, $\mathbb{Z}[\sqrt{m}\space]$ contains (positive) numbers arbitrarily close to $0.$ Picking up suitably small numbers and their integer multiples, we may prove that numbers from $\mathbb{Z}[\sqrt{m}\space]$ are dense in the interval $[0, 1]\;$ and, since $\mathbb{Z}[\sqrt{m}\space]$ contains all the integers, on the whole axis.

References

  1. J. Cofman, What To Solve?, Oxford Science Publications, 1996.
  2. D. O. Shklarsky, N. N. Chentzov, I. M. Yaglom, The USSR Olympiad Problem Book, Freeman, 1962

|Contact| |Front page| |Contents| |Algebra| |Store|

Copyright © 1996-2017 Alexander Bogomolny

 61164268

Search by google: