Mathematics

#6: Post edited by $user avatar$ Derek Elkins‭ · 2024-04-07T10:57:20Z (about 1 month ago)
Had my adjunction backward which made the proof nonsense

Copy Link

Raw

Markdown

This is definitely more complicated than it needs to be.
First, we can rewrite the inequality as $$\lfloor x^2 + 1\rfloor \geq \lfloor rx \rfloor$$
### Proof 1
~~(This is the first proof I wrote, but the second one is nicer. I find this often happens when I'm more deliberate about taking a categorical perspective.)~~
$\lfloor x^2 + 1 \rfloor = 1$ for $|x| < 1$ so choosing $x$ to be the opposite sign of $r$ leads to $|x||r| < 2$ on the same domain. Since $|x|$ gets arbitrarily close to $1$, this implies that $|r| \leq 2$. (If you want to formalize this more, you can take the limit with $|x| = 1-1/n$ as $n \to \infty$.) This gives the left to right implication.
Since floor is monotonic, we also have $x^2 + 1 \geq rx$ implies $\lfloor x^2 + 1 \rfloor \geq \lfloor rx \rfloor$. Thus we have the constraint $$x^2 - rx + 1 \geq 0$$ We know the minimum of this function is at $x = r/2$ and substituting that into the inequality gives $$r^2/4 - r^2/2 + 1 \geq 0$$ which can easily be solved for $r^2 \leq 4$ or $|r| \leq 2$ giving the right to left implication. (The change of order for the inequality is because we end up multiplying both sides by $-4$.)
----
I wanted to make a second proof that leveraged a(n even) more categorical perspective. To that end, in addition to noting that floor is functorial, i.e. monotonic, we also know that it is a left adjoint via $\lfloor{-} floor \dashv \iota$ where $\iota : \mathbb Z \hookrightarrow \mathbb R$ is the inclusion which I'll suppress going forward. Explicitly, we have $\lfloor x floor \leq m \iff x \leq m$ for any $x \in \mathbb R$ and $m \in \mathbb Z$. Finally, we have the full and faithfulness of the (contravariant) Yoneda embedding, which is to say $x \leq y \iff \forall z. y \leq z \to x \leq z$. Using these in our problem leads to the following proof.
### Proof 2
For the $\implies$ direction:
$$\begin{align}
\lfloor rx \rfloor \leq \lfloor x^2 + 1 \rfloor
~~& \iff \forall m. \lfloor x^2 + 1 floor \leq m \to \lfloor rx floor \leq m \\\\~~
& \iff \forall m. x^2 + 1 \leq m \to rx \leq m
\end{align}$$
~~We now simply choose $m = 2$ and $x = \pm 1$ with sign opposite of $r$ and we're done.~~
For the $\impliedby$ direction: If we can show that $rx \leq x^2 + 1$ then monotonicity would finish the proof. If $r$ and $x$ have opposite signs, this easily holds, so assume they have the same sign and, without loss of generality, they're both positive. We then have $2 \leq x + 1/x$, but the right hand sides' minimum (with positive $x$) which you can find using the usual calculus approach occurs when $x = 1$, finishing the proof.

This is definitely more complicated than it needs to be.
First, we can rewrite the inequality as $$\lfloor x^2 + 1\rfloor \geq \lfloor rx \rfloor$$
### Proof 1
(This is the first proof I wrote, but the second one is nicer and takes a more categorical perspective.)
$\lfloor x^2 + 1 \rfloor = 1$ for $|x| < 1$ so choosing $x$ to be the opposite sign of $r$ leads to $|x||r| < 2$ on the same domain. Since $|x|$ gets arbitrarily close to $1$, this implies that $|r| \leq 2$. (If you want to formalize this more, you can take the limit with $|x| = 1-1/n$ as $n \to \infty$.) This gives the left to right implication.
Since floor is monotonic, we also have $x^2 + 1 \geq rx$ implies $\lfloor x^2 + 1 \rfloor \geq \lfloor rx \rfloor$. Thus we have the constraint $$x^2 - rx + 1 \geq 0$$ We know the minimum of this function is at $x = r/2$ and substituting that into the inequality gives $$r^2/4 - r^2/2 + 1 \geq 0$$ which can easily be solved for $r^2 \leq 4$ or $|r| \leq 2$ giving the right to left implication. (The change of order for the inequality is because we end up multiplying both sides by $-4$.)
----
I wanted to make a second proof that leveraged a(n even) more categorical perspective. To that end, in addition to noting that floor is functorial, i.e. monotonic, we also know that it is a right adjoint via $\iota \dashv \lfloor{-} floor$ where $\iota : \mathbb Z \hookrightarrow \mathbb R$ is the inclusion which I'll suppress going forward. Explicitly, we have $m \leq \lfloor x floor \iff m \leq x$ for any $x \in \mathbb R$ and $m \in \mathbb Z$. Finally, we have the full and faithfulness of the Yoneda embedding, which is to say $x \leq y \iff \forall z. z \leq x \to z \leq y$. Using these in our problem leads to the following proof.
### Proof 2
For the $\implies$ direction:
$$\begin{align}
\lfloor rx \rfloor \leq \lfloor x^2 + 1 \rfloor
& \iff \forall m. m \leq \lfloor rx floor \to m \leq \lfloor x^2 + 1 floor \\\\
& \iff \forall m. m \leq rx \to m \leq x^2 + 1 \\\\
& \iff \forall m. m > x^2 + 1 \to m > rx
\end{align}$$
We now choose $m = 2$ and $|x| \in (0,1)$ with the sign of $x$ opposite of $r$. We then have $2/|x| > |r|$ and thus $|r|$ is bounded by the greatest lower bound of $\{2/|x|\mid x \in (0,1)\}$ which is $2$.
For the $\impliedby$ direction: If we can show that $rx \leq x^2 + 1$ then monotonicity would finish the proof. If $r$ and $x$ have opposite signs, this easily holds, so assume they have the same sign and, without loss of generality, they're both positive. We then have $2 \leq x + 1/x$, but the right hand sides' minimum (with positive $x$) which you can find using the usual calculus approach occurs when $x = 1$, finishing the proof.

#5: Post edited by $user avatar$ Derek Elkins‭ · 2024-04-06T07:58:53Z (about 1 month ago)
Nicer proof by being more categorically inspired

Copy Link

Raw

Markdown

This is definitely more complicated than it needs to be.
First, we can rewrite the inequality as $$\lfloor x^2 + 1\rfloor \geq \lfloor rx \rfloor$$
$\lfloor x^2 + 1 \rfloor = 1$ for $|x| < 1$ so choosing $x$ to be the opposite sign of $r$ leads to $|x||r| < 2$ on the same domain. Since $|x|$ gets arbitrarily close to $1$, this implies that $|r| \leq 2$. (If you want to formalize this more, you can take the limit with $|x| = 1-1/n$ as $n \to \infty$.) This gives the left to right implication.
Since floor is monotonic, we also have $x^2 + 1 \geq rx$ implies $\lfloor x^2 + 1 floor \geq \lfloor rx floor$. Thus we have the constraint $$x^2 - rx + 1 \geq 0$$ We know the minimum of this function is at $x = r/2$ and substituting that into the inequality gives $$r^2/4 - r^2/2 + 1 \geq 0$$ which can easily be solved for $r^2 \leq 4$ or $|r| \leq 2$ giving the right to left implication. (The change of order for the inequality is because we end up multiplying both sides by $-4$.)

This is definitely more complicated than it needs to be.
First, we can rewrite the inequality as $$\lfloor x^2 + 1\rfloor \geq \lfloor rx \rfloor$$
### Proof 1
(This is the first proof I wrote, but the second one is nicer. I find this often happens when I'm more deliberate about taking a categorical perspective.)
$\lfloor x^2 + 1 \rfloor = 1$ for $|x| < 1$ so choosing $x$ to be the opposite sign of $r$ leads to $|x||r| < 2$ on the same domain. Since $|x|$ gets arbitrarily close to $1$, this implies that $|r| \leq 2$. (If you want to formalize this more, you can take the limit with $|x| = 1-1/n$ as $n \to \infty$.) This gives the left to right implication.
Since floor is monotonic, we also have $x^2 + 1 \geq rx$ implies $\lfloor x^2 + 1 floor \geq \lfloor rx floor$. Thus we have the constraint $$x^2 - rx + 1 \geq 0$$ We know the minimum of this function is at $x = r/2$ and substituting that into the inequality gives $$r^2/4 - r^2/2 + 1 \geq 0$$ which can easily be solved for $r^2 \leq 4$ or $|r| \leq 2$ giving the right to left implication. (The change of order for the inequality is because we end up multiplying both sides by $-4$.)
----
I wanted to make a second proof that leveraged a(n even) more categorical perspective. To that end, in addition to noting that floor is functorial, i.e. monotonic, we also know that it is a left adjoint via $\lfloor{-}\rfloor \dashv \iota$ where $\iota : \mathbb Z \hookrightarrow \mathbb R$ is the inclusion which I'll suppress going forward. Explicitly, we have $\lfloor x\rfloor \leq m \iff x \leq m$ for any $x \in \mathbb R$ and $m \in \mathbb Z$. Finally, we have the full and faithfulness of the (contravariant) Yoneda embedding, which is to say $x \leq y \iff \forall z. y \leq z \to x \leq z$. Using these in our problem leads to the following proof.
### Proof 2
For the $\implies$ direction:
$$\begin{align}
\lfloor rx \rfloor \leq \lfloor x^2 + 1 \rfloor
& \iff \forall m. \lfloor x^2 + 1 \rfloor \leq m \to \lfloor rx \rfloor \leq m \\\\
& \iff \forall m. x^2 + 1 \leq m \to rx \leq m
\end{align}$$
We now simply choose $m = 2$ and $x = \pm 1$ with sign opposite of $r$ and we're done.
For the $\impliedby$ direction: If we can show that $rx \leq x^2 + 1$ then monotonicity would finish the proof. If $r$ and $x$ have opposite signs, this easily holds, so assume they have the same sign and, without loss of generality, they're both positive. We then have $2 \leq x + 1/x$, but the right hand sides' minimum (with positive $x$) which you can find using the usual calculus approach occurs when $x = 1$, finishing the proof.

#4: Post undeleted by $user avatar$ Derek Elkins‭ · 2024-04-06T01:43:52Z (about 1 month ago)

Copy Link

Raw

Markdown

#3: Post edited by $user avatar$ Derek Elkins‭ · 2024-04-06T01:42:49Z (about 1 month ago)
Correct mistake

Copy Link

Raw

Markdown

This is definitely more complicated than it needs to be.
First, we can rewrite the inequality as $$\lfloor x^2 + 1\rfloor \geq \lfloor rx \rfloor$$
The first interesting value of $x^2 + 1$ to consider is $m = 2$ corresponding to $x = \pm 1$. Choosing $x$ to be the opposite sign of $r$ leads to $2 \geq \lfloor |r| \rfloor$ and thus $|r| \leq 2$. This gives the left to right implication.
Since floor is monotonic, we also have $x^2 + 1 \geq rx$ implies $\lfloor x^2 + 1 \rfloor \geq \lfloor rx \rfloor$. Thus we have the constraint $$x^2 - rx + 1 \geq 0$$ We know the minimum of this function is at $x = r/2$ and substituting that into the inequality gives $$r^2/4 - r^2/2 + 1 \geq 0$$ which can easily be solved for $r^2 \leq 4$ or $|r| \leq 2$ giving the right to left implication. (The change of order for the inequality is because we end up multiplying both sides by $-4$.)

This is definitely more complicated than it needs to be.
First, we can rewrite the inequality as $$\lfloor x^2 + 1\rfloor \geq \lfloor rx \rfloor$$
$\lfloor x^2 + 1 \rfloor = 1$ for $|x| < 1$ so choosing $x$ to be the opposite sign of $r$ leads to $|x||r| < 2$ on the same domain. Since $|x|$ gets arbitrarily close to $1$, this implies that $|r| \leq 2$. (If you want to formalize this more, you can take the limit with $|x| = 1-1/n$ as $n \to \infty$.) This gives the left to right implication.
Since floor is monotonic, we also have $x^2 + 1 \geq rx$ implies $\lfloor x^2 + 1 \rfloor \geq \lfloor rx \rfloor$. Thus we have the constraint $$x^2 - rx + 1 \geq 0$$ We know the minimum of this function is at $x = r/2$ and substituting that into the inequality gives $$r^2/4 - r^2/2 + 1 \geq 0$$ which can easily be solved for $r^2 \leq 4$ or $|r| \leq 2$ giving the right to left implication. (The change of order for the inequality is because we end up multiplying both sides by $-4$.)

#2: Post deleted by $user avatar$ Derek Elkins‭ · 2024-04-06T01:18:52Z (about 1 month ago)

Copy Link

Raw

Markdown

#1: Initial revision by $user avatar$ Derek Elkins‭ · 2024-04-06T01:14:56Z (about 1 month ago)

Copy Link

Raw

Markdown

This is definitely more complicated than it needs to be.

First, we can rewrite the inequality as $$\lfloor x^2 + 1\rfloor \geq \lfloor rx \rfloor$$

The first interesting value of $x^2 + 1$ to consider is $m = 2$ corresponding to $x = \pm 1$. Choosing $x$ to be the opposite sign of $r$ leads to $2 \geq \lfloor |r| \rfloor$ and thus $|r| \leq 2$. This gives the left to right implication.

Since floor is monotonic, we also have $x^2 + 1 \geq rx$ implies $\lfloor x^2 + 1 \rfloor \geq \lfloor rx \rfloor$. Thus we have the constraint $$x^2 - rx + 1 \geq 0$$ We know the minimum of this function is at $x = r/2$ and substituting that into the inequality gives $$r^2/4 - r^2/2 + 1 \geq 0$$ which can easily be solved for $r^2 \leq 4$ or $|r| \leq 2$ giving the right to left implication. (The change of order for the inequality is because we end up multiplying both sides by $-4$.)

Communities

Post History