Editing Floor and ceiling functions (section)

==Definition and properties==
Given real numbers ''x'' and ''y'', integers ''m'' and ''n'' and the set of [[integer]]s <math>\mathbb{Z}</math>, floor and ceiling may be defined by the equations

:<math> \lfloor x \rfloor=\max \{m\in\mathbb{Z}\mid m\le x\},</math>

:<math> \lceil x \rceil=\min \{n\in\mathbb{Z}\mid n\ge x\}.</math>

Since there is exactly one integer in a [[half-open interval]] of length one, for any real number ''x'', there are unique integers ''m'' and ''n'' satisfying the equation
:<math>x-1<m\le x \le n <x+1.</math>

where <math>\lfloor x \rfloor = m</math>&nbsp;and <math>\lceil x \rceil = n</math>&nbsp;may also be taken as the definition of floor and ceiling.

===Equivalences===
These formulas can be used to simplify expressions involving floors and ceilings.<ref>Graham, Knuth, & Patashink, Ch. 3</ref>

:<math>
\begin{alignat}{3}
\lfloor x \rfloor &= m \ \ &&\mbox{ if and only if } &m &\le x < m+1,\\
\lceil x \rceil &= n     &&\mbox{ if and only if } &\ \ n -1 &< x \le n,\\

\lfloor x \rfloor &= m   &&\mbox{ if and only if } &x-1 &< m \le x,\\
\lceil x \rceil &= n    &&\mbox{ if and only if }  &x &\le n < x+1.
\end{alignat}
</math>

In the language of [[order theory]], the floor function is a [[residuated mapping]], that is, part of a [[Galois connection]]: it is the upper adjoint of the function that embeds the integers into the reals.

:<math>
\begin{align}
x<n &\;\;\mbox{ if and only if } &\lfloor x \rfloor &< n, \\
n<x &\;\;\mbox{ if and only if } &n &< \lceil x \rceil, \\
x\le n &\;\;\mbox{ if and only if } &\lceil  x \rceil &\le n, \\
n\le x &\;\;\mbox{ if and only if } &n &\le \lfloor x \rfloor.
\end{align}
</math>

These formulas show how adding an integer {{mvar|n}} to the arguments affects the functions:

:<math>
\begin{align}
\lfloor x+n \rfloor &= \lfloor x \rfloor+n,\\
\lceil x+n \rceil &= \lceil x \rceil+n,\\
\{ x+n \} &= \{ x \}.
\end{align}
</math>

The above are never true if {{mvar|n}} is not an integer; however, for every {{mvar|x}} and {{mvar|y}}, the following inequalities hold:

:<math>\begin{align}
\lfloor x \rfloor + \lfloor y \rfloor &\leq \lfloor x + y \rfloor \leq \lfloor x \rfloor + \lfloor y \rfloor + 1,\\[3mu]
\lceil x \rceil + \lceil y \rceil -1 &\leq \lceil x + y \rceil \leq \lceil x \rceil + \lceil y \rceil.
\end{align}</math>

=== Monotonicity ===
Both floor and ceiling functions are [[Monotonic function|monotonically non-decreasing functions]]:

:<math>
\begin{align}
x_{1} \le x_{2} &\Rightarrow \lfloor x_{1} \rfloor \le \lfloor x_{2} \rfloor, \\
x_{1} \le x_{2} &\Rightarrow \lceil  x_{1} \rceil  \le \lceil  x_{2} \rceil.  
\end{align}
</math>

===Relations among the functions===
It is clear from the definitions that
:<math>\lfloor x \rfloor \le \lceil x \rceil,</math>  with equality if and only if ''x'' is an integer, i.e.
:<math>\lceil x \rceil - \lfloor x \rfloor = \begin{cases}
0&\mbox{ if } x\in \mathbb{Z}\\
1&\mbox{ if } x\not\in \mathbb{Z}
\end{cases}</math>

In fact, for integers ''n'', both floor and ceiling functions are the [[identity function|identity]]:
:<math>\lfloor n \rfloor = \lceil n \rceil = n.</math>

Negating the argument switches floor and ceiling and changes the sign:
:<math> \begin{align}
\lfloor x \rfloor +\lceil -x \rceil &= 0 \\
-\lfloor x \rfloor &= \lceil  -x \rceil \\
-\lceil  x \rceil  &= \lfloor -x \rfloor
\end{align}
</math>

and:
:<math>\lfloor x \rfloor + \lfloor -x \rfloor = \begin{cases}
0&\text{if } x\in \mathbb{Z}\\
-1&\text{if } x\not\in \mathbb{Z},
\end{cases}</math>

:<math>\lceil x \rceil + \lceil -x \rceil = \begin{cases}
0&\text{if } x\in \mathbb{Z}\\
1&\text{if } x\not\in \mathbb{Z}.
\end{cases}</math>

Negating the argument complements the fractional part:

:<math>\{ x \} +  \{ -x \} = \begin{cases}
0&\text{if } x\in \mathbb{Z}\\
1&\text{if } x\not\in \mathbb{Z}.
\end{cases}</math>

The floor, ceiling, and fractional part functions are [[Idempotence|idempotent]]:

:<math>
\begin{align}
\big\lfloor \lfloor x \rfloor \big\rfloor &= \lfloor x \rfloor, \\
\big\lceil \lceil x \rceil \big\rceil &= \lceil x \rceil, \\
\big\{ \{ x \} \big\} &= \{ x \}.
\end{align}
</math>

The result of nested floor or ceiling functions is the innermost function:
:<math>
\begin{align}
\big\lfloor \lceil x \rceil \big\rfloor &= \lceil x \rceil, \\
\big\lceil \lfloor x \rfloor \big\rceil &= \lfloor x \rfloor
\end{align}
</math>
due to the identity property for integers.

===Quotients===
If ''m'' and ''n'' are integers and ''n'' ≠  0,
:<math>0 \le \left\{ \frac{m}{n} \right\} \le 1-\frac{1}{|n|}.</math>

If ''n'' is positive<ref>Graham, Knuth, & Patashnik, p. 73</ref>
:<math>\left\lfloor\frac{x+m}{n}\right\rfloor = \left\lfloor\frac{\lfloor x\rfloor +m}{n}\right\rfloor,
</math>

:<math>\left\lceil\frac{x+m}{n}\right\rceil = \left\lceil\frac{\lceil x\rceil +m}{n}\right\rceil.
</math>

If ''m'' is positive<ref>Graham, Knuth, & Patashnik, p. 85</ref>

:<math>n=\left\lceil\frac{n\vphantom1}{m}\right\rceil + \left\lceil\frac{n-1}{m}\right\rceil +\dots+\left\lceil\frac{n-m+1}{m}\right\rceil,
</math>

:<math>n=\left\lfloor\frac{n\vphantom1}{m}\right\rfloor + \left\lfloor\frac{n+1}{m}\right\rfloor +\dots+\left\lfloor\frac{n+m-1}{m}\right\rfloor.
</math>

For ''m'' = 2 these imply

:<math>n= \left\lfloor \frac{n\vphantom1}{2}\right \rfloor + \left\lceil\frac{n\vphantom1}{2}\right \rceil.</math>

More generally,<ref>Graham, Knuth, & Patashnik, p. 85 and Ex. 3.15</ref> for positive ''m'' (See [[Hermite's identity]])

:<math>\lceil mx \rceil =\left\lceil x\right\rceil  + \left\lceil x-\frac{1}{m}\right\rceil +\dots+\left\lceil x-\frac{m-1}{m}\right\rceil,
</math>

:<math>\lfloor mx \rfloor=\left\lfloor x\right\rfloor + \left\lfloor x+\frac{1}{m}\right\rfloor +\dots+\left\lfloor x+\frac{m-1}{m}\right\rfloor.
</math>

The following can be used to convert floors to ceilings and vice versa (with ''m'' being positive)<ref>Graham, Knuth, & Patashnik, Ex. 3.12</ref>

:<math>\left\lceil \frac{n\vphantom1}{m} \right\rceil = \left\lfloor \frac{n+m-1}{m} \right\rfloor = \left\lfloor \frac{n - 1}{m} \right\rfloor + 1, </math>

:<math>\left\lfloor \frac{n\vphantom1}{m} \right\rfloor = \left\lceil \frac{n-m+1}{m} \right\rceil = \left\lceil \frac{n + 1}{m} \right\rceil - 1, </math>

For all ''m'' and ''n'' strictly positive integers:<ref>Graham, Knuth, & Patashnik, p. 94.</ref>

:<math>\sum_{k = 1}^{n - 1} \left\lfloor \frac{k m}{n} \right\rfloor = \frac{(m - 1)(n - 1)+\gcd(m,n)-1}2,</math>

which, for positive and [[coprime]]  ''m'' and ''n'', reduces to

:<math>\sum_{k=1}^{n-1} \left\lfloor \frac{km}{n} \right\rfloor = \tfrac{1}{2}(m - 1)(n - 1) ,</math>

and similarly for the ceiling and fractional part functions (still for positive and [[coprime]]  ''m'' and ''n''),

:<math>\sum_{k=1}^{n-1} \left\lceil \frac{km}{n} \right\rceil = \tfrac{1}{2}(m + 1)(n - 1),</math>

:<math>\sum_{k=1}^{n-1} \left\{ \frac{km}{n} \right\} = \tfrac{1}{2}(n - 1).</math>


Since the right-hand side of the general case is symmetrical in ''m'' and ''n'', this implies that

:<math>\left\lfloor \frac{m\vphantom1}{n} \right \rfloor + \left\lfloor \frac{2m}{n} \right \rfloor + \dots + \left\lfloor \frac{(n-1)m}{n} \right \rfloor =
\left\lfloor \frac{n\vphantom1}{m} \right \rfloor + \left\lfloor \frac{2n}{m} \right \rfloor + \dots + \left\lfloor \frac{(m-1)n}{m} \right \rfloor.
</math>

More generally, if ''m'' and ''n'' are positive,

:<math>\begin{align}
&\left\lfloor \frac{x\vphantom1}{n} \right \rfloor +
\left\lfloor \frac{m+x}{n} \right \rfloor +
\left\lfloor \frac{2m+x}{n} \right \rfloor +
\dots +
\left\lfloor \frac{(n-1)m+x}{n} \right \rfloor\\[5mu]
=
&\left\lfloor \frac{x\vphantom1}{m} \right \rfloor +
\left\lfloor \frac{n+x}{m} \right \rfloor +
\left\lfloor \frac{2n+x}{m} \right \rfloor +
\cdots +
\left\lfloor \frac{(m-1)n+x}{m} \right \rfloor.
\end{align}
</math>

This is sometimes called a [[#Quadratic reciprocity|reciprocity law]].<ref>Graham, Knuth, & Patashnik, p. 94</ref>

Division by positive integers gives rise to an interesting and sometimes useful property. Assuming <math>m,n >0</math>,

:<math> m \leq \left\lfloor \frac{x}{n} \right \rfloor \iff n \leq  \left\lfloor \frac{x}{m} \right \rfloor \iff n \leq  \frac{ \lfloor x \rfloor }{m}. </math>

Similarly,

:<math> m \geq \left\lceil \frac{x}{n} \right \rceil \iff n \geq  \left\lceil \frac{x}{m} \right \rceil \iff n \geq  \frac{ \lceil x \rceil }{m}. </math>

Indeed,

:<math> m \leq \left\lfloor \frac{x}{n} \right \rfloor \implies m \leq \frac{x}{n} \implies n \leq \frac{x}{m} 
\implies n \leq \left \lfloor \frac{x}{m}\right \rfloor \implies \ldots \implies m \leq \left\lfloor \frac{x}{n} \right \rfloor,</math> 
keeping in mind that <math display=inline> \left\lfloor \frac{x}{n} \right\rfloor = \left\lfloor \frac{\lfloor x \rfloor}{n} \right\rfloor.</math>
The second equivalence involving the ceiling function can be proved similarly.

===Nested divisions===
For a positive integer ''n'', and arbitrary real numbers ''m'' and ''x'':<ref>Graham, Knuth, & Patashnik, p. 71, apply theorem 3.10 with {{sfrac|''x''|''m''}} as input and the division by ''n'' as function</ref>

: <math>\begin{align}
\left\lfloor \frac{\left\lfloor \frac{x}{m} \right\rfloor}{n} \right\rfloor &= \left\lfloor \frac{x}{mn} \right\rfloor \\[4px]
\left\lceil  \frac{\left\lceil  \frac{x}{m} \right\rceil }{n} \right\rceil  &= \left\lceil  \frac{x}{mn} \right\rceil.
\end{align}</math>

===Continuity and series expansions===
None of the functions discussed in this article are [[continuous function|continuous]], but all are [[piecewise linear function|piecewise linear]]: the functions <math>\lfloor x \rfloor</math>, <math>\lceil x \rceil</math>, and <math>\{ x\}</math> have discontinuities at the integers.

<math>\lfloor x \rfloor</math> is [[semi-continuity|upper semi-continuous]] and <math>\lceil x \rceil</math> and <math>\{ x\}</math> are lower semi-continuous.

Since none of the functions discussed in this article are continuous, none of them have a [[power series]] expansion. Since floor and ceiling are not periodic, they do not have uniformly convergent [[Fourier series]] expansions.  The fractional part function has Fourier series expansion<ref>Titchmarsh, p. 15, Eq. 2.1.7</ref>
<math display="block">
\{x\}= \frac{1}{2} - \frac{1}{\pi} \sum_{k=1}^\infty
\frac{\sin(2 \pi k x)} {k}
</math>
for {{mvar|x}} not an integer.

At points of discontinuity, a Fourier series converges to a value that is the average of its limits on the left and the right, unlike the floor, ceiling and fractional part functions: for ''y'' fixed and ''x'' a multiple of ''y'' the Fourier series given converges to ''y''/2, rather than to ''x''&nbsp;mod&nbsp;''y''&nbsp;=&nbsp;0. At points of continuity the series converges to the true value.

Using the formula <math>\lfloor x\rfloor = x - \{x\}</math> gives
<math display="block">
\lfloor x\rfloor = x - \frac{1}{2} + \frac{1}{\pi}  \sum_{k=1}^\infty \frac{\sin(2 \pi k x)}{k}
</math> 
for {{mvar|x}} not an integer.