# McEliece's Theorem (Integer Functions)

## Theorem

Let $f: \R \to \R$ be a continuous, strictly increasing real function defined on an interval $A$.

Let:

- $\forall x \in A: \floor x \in A \text { and } \ceiling x \in A$

where:

Then:

- $\forall x \in A: \paren {\map f x \in \Z \implies x \in \Z} \iff \floor {\map f x} = \floor {\map f {\floor x} }$
- $\forall x \in A: \paren {\map f x \in \Z \implies x \in \Z} \iff \ceiling {\map f x} = \ceiling {\map f {\ceiling x} }$

## Proof

Let $x \in A$.

Hence by hypothesis we have that both $\floor x \in A$ and $\ceiling x \in A$.

### Necessary Condition

Let $\map f x \in \Z$.

Let:

- $\floor {\map f x} = \floor {\map f {\floor x} }$

Then:

\(\ds \map f x\) | \(=\) | \(\ds \floor {\map f x}\) | Real Number is Integer iff equals Floor | |||||||||||

\(\ds \) | \(=\) | \(\ds \floor {\map f {\floor x} }\) | by hypothesis |

Aiming for a contradiction, suppose $x \notin \Z$.

\(\ds \floor x\) | \(<\) | \(\ds x\) | Floor of Non-Integer | |||||||||||

\(\ds \leadsto \ \ \) | \(\ds \map f {\floor x}\) | \(<\) | \(\ds \map f x\) | as $f$ is strictly increasing | ||||||||||

\(\ds \leadsto \ \ \) | \(\ds \floor {\map f {\floor x} }\) | \(<\) | \(\ds \floor {\map f x}\) | as $\floor {\map f x} = \map f x$ by Real Number is Integer iff equals Floor | ||||||||||

\(\ds \leadsto \ \ \) | \(\ds \floor {\map f {\floor x} }\) | \(\ne\) | \(\ds \floor {\map f x}\) | which contradicts $\floor {\map f x} = \floor {\map f {\floor x} }$ |

Thus by Proof by Contradiction:

- $x \in \Z$

Similarly, let:

- $\ceiling {\map f x} = \ceiling {\map f {\ceiling x} }$

Then:

\(\ds \map f x\) | \(=\) | \(\ds \ceiling {\map f x}\) | Real Number is Integer iff equals Ceiling | |||||||||||

\(\ds \) | \(=\) | \(\ds \ceiling {\map f {\ceiling x} }\) | by hypothesis |

Aiming for a contradiction, suppose $x \notin \Z$.

\(\ds \ceiling x\) | \(>\) | \(\ds x\) | Ceiling of Non-Integer | |||||||||||

\(\ds \leadsto \ \ \) | \(\ds \map f {\ceiling x}\) | \(>\) | \(\ds \map f x\) | as $f$ is strictly increasing | ||||||||||

\(\ds \leadsto \ \ \) | \(\ds \ceiling {\map f {\ceiling x} }\) | \(>\) | \(\ds \ceiling {\map f x}\) | as $\ceiling {\map f x} = \map f x$ by Real Number is Integer iff equals Ceiling | ||||||||||

\(\ds \leadsto \ \ \) | \(\ds \ceiling {\map f {\ceiling x} }\) | \(\ne\) | \(\ds \ceiling {\map f x}\) | which contradicts $\ceiling {\map f x} = \ceiling {\map f {\ceiling x} }$ |

Thus by Proof by Contradiction:

- $x \in \Z$

Thus:

- $\forall x \in A: \floor {\map f x} = \floor {\map f {\floor x} } \implies \paren {\map f x \in \Z \implies x \in \Z}$

and:

- $\forall x \in A: \ceiling {\map f x} = \ceiling {\map f {\ceiling x} } \implies \paren {\map f x \in \Z \implies x \in \Z}$

$\Box$

### Sufficient Condition

Let $f$ be such that:

- $\map f x \in \Z \implies x \in \Z$

Aiming for a contradiction, suppose there exists $x \in A$ such that:

- $\floor {\map f x} \ne \floor {\map f {\floor x} }$

We have by definition of the floor function that $x \ge \floor x$.

As $f$ is strictly increasing, it cannot be the case that $\floor {\map f x} < \floor {\map f {\floor x} }$.

So it must be that:

- $\floor {\map f {\floor x} } < \floor {\map f x}$

Because $f$ is continuous:

- $\exists y \in A: \floor x < y \le x$

such that $\map f y \in \Z$

But by definition of the floor function, $y$ cannot be an integer.

Thus by Proof by Contradiction:

- $\paren {\map f x \in \Z \implies x \in \Z} \implies \floor {\map f x} = \floor {\map f {\floor x} }$

$\Box$

Aiming for a contradiction, suppose, similarly, that there exists $x \in A$ such that:

- $\ceiling {\map f x} \ne \ceiling {\map f {\ceiling x} }$

We have by definition of the ceiling function that $x \le \ceiling x$.

As $f$ is strictly increasing, it cannot be the case that $\ceiling {\map f x} > \ceiling {\map f {\ceiling x} }$.

So it must be that:

- $\ceiling {\map f {\ceiling x} } > \ceiling {\map f x}$

Because $f$ is continuous:

- $\exists y \in A: \ceiling x > y \ge x$

such that $\map f y \in \Z$

But by definition of the ceiling function, $y$ cannot be an integer.

Thus by Proof by Contradiction:

- $\paren {\map f x \in \Z \implies x \in \Z} \implies \ceiling {\map f x} = \ceiling {\map f {\ceiling x} }$

$\Box$

Thus we have:

- $\paren {\map f x \in \Z \implies x \in \Z} \iff \floor {\map f x} = \floor {\map f {\floor x} }$

and

- $\paren {\map f x \in \Z \implies x \in \Z} \iff \ceiling {\map f x} = \ceiling {\map f {\ceiling x} }$

Hence the result.

$\blacksquare$

## Source of Name

This entry was named for Robert James McEliece.

## Historical Note

Donald E. Knuth reports in *The Art of Computer Programming* that this generalisation of Conditions for $\floor {\log_b x}$ to equal $\floor {\log_b \floor x}$ was established by Robert James McEliece.

Knuth refers to it (in passing) as **McEliece's Theorem**.

Whiile this name for it is not backed up in the literature, it is convenient for $\mathsf{Pr} \infty \mathsf{fWiki}$, because of its unwieldy nature, to refer to it thus.

## Sources

- 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 $34$ (Answers to Exercises)