6

Is there a function $h$ and a constant $c$ to satisfy $h(x-c) \neq O(h(x))$?

My attempt:

This claim isn't true. we shall show an equivalent claim to the negation of our claim. We will show that for each function $h(x)$ and a constant $c$, from a certain $x$, we get $h(x-c)\le c_1\cdot h(x)$. Now I don't know how to proceed, however, my intuition says that $h(x-c)$ is the same function $h(x)$ but when you move it horizontally $c$, so by that fact we can pick $c_1$ such that will be big enough to overcome $h(x-c)$, because we have a bigger slope of $h(x)$. Therefore, we get that: $$h(x-c)\le c_1\cdot h(x)$$

I am not sure that this is formal, and probably I am missing details, so I will be glad to get some help. Thanks!

Chopin
  • 872

1 Answers1

3

Do we allow $c<0$? In that case maybe pick $h(x) = e^{x^2}$, then

$$ h(x-c) = e^{x^2 -2cx + c^2} > e^{2|c|x} e^{x^2} \neq O(h(x)). $$

In fact, for $c>0$ simply pick $h(x) = e^{-x^2}$, then

$$ h(x-c) = e^{-x^2 +2cx - c^2} = e^{-c^2} e^{2cx} e^{-x^2} \neq O(h(x)).$$ To see why this is true, recall that $f(x) = O(g(x))$ iff there are constants $x_0$ and $M$ such that for all $x\geq x_0$ we have $f(x) \leq M g(x)$. Suppose for contradiction that $h(x-c) = O(h(x))$, and let $x_0$ and $M$ be the corresponding constants. Then for all $x\geq x_0$ we have $$ e^{-c^2 }e^{2cx} e^{ -x^2}\leq M e^{-x^2}. $$ Cancelling $e^{-x^2}$ from both sides, we now have constants $x_0$ and $M$ such that $x\geq x_0$ implies $e^{-c^2 }e^{2xc} \leq M$, but the left hand side of this goes to infinity! So this is a contradiction, and indeed we have $h(x-c) \neq O(h(x))$.

I think some of the confusion may come from the fact that $h(x)$ and $h(x-c)$ both go to zero as $x\to \infty$. But in this example $h(x-c)$ goes to infinity much slower, as there is an additional $e^{2cx}$ term which will be quite large.

Another counter example: This is kinda fun so I thought of another example of $h(x)$ and $c$ with $h(x-c) \neq O(h(x))$. Let $h(x)$ defined as $$h(x) = \begin{cases}0 &\text{ if }x\in \mathbb{Q},\\ x& \text{otherwise}.\end{cases} .$$ If $c$ is any irrational number then for all rational $x$ we have $h(x-c)=x-c$ while $h(x) = 0$. So, fixing such an irrational $c$, there are rational $x > c$ for which $h(x-c)-h(x)$ exceeds any bound.

Similarly, we can use e.g. $h(x)= 1/(\sin (\pi x) + 1.1)$ to achieve a similar effect.

Slugger
  • 5,556
  • But if I want to show it more generally such as I wanted to do, how do I do that? If I could... – Chopin Mar 21 '21 at 19:15
  • 3
    If the question is: Does there exists a function $h$ and constant $c$ with $h(x-c) \neq O(h(x))$, then this answer is in full generality. In particular, the line of reasoning that you are trying to undertake will not work, because, as I showed, such functions do in fact exist. – Slugger Mar 21 '21 at 19:17
  • Ok, and one more question, is there a more simple way to demonstrate that? – Chopin Mar 21 '21 at 19:21
  • Well, the demonstration above is a two-liner. It could only be simpler if someone thinks of a function for which the result is even easier to demonstrate. This might be possible, but giving a simple example is typically the easiest type of proof. – Slugger Mar 21 '21 at 19:22
  • got you thanks! – Chopin Mar 21 '21 at 19:26
  • No problem! Was an interesting question – Slugger Mar 21 '21 at 19:27
  • Now I see that your $C'$ isn't true because you are stating that $e^{−x^2+2cx−c^2}>C′e^{2cx}e^{−x^2}$ but if $C′=e^{-c^2}$ then it is the same expression. I will be glad for an explanation here. – Chopin Mar 21 '21 at 22:23
  • Ah apologies, that should be an equality instead of an inequality, I have updated the answer. – Slugger Mar 21 '21 at 23:12
  • One more thing, can you elaborate more about equality? because I'm not that familiar with Orders of $e$ functions... – Chopin Mar 21 '21 at 23:14
  • I think you are wrong... if we take $c=\frac{1}{4}$ for instance, then we do have that your claim is false... There isn't such a positive constant, and for a big value of the constant, we get that the function will move left and we have the function goes to zero, for positive values of $x$, and still that means that your claim is false... In addition, I can't understand how you pick a function that isn't monotonic increasing. – Chopin Mar 22 '21 at 12:57
  • I have updated my answer. I hope everything is clearer now. – Slugger Mar 22 '21 at 15:02
  • Now I got it. I have returned you the V. Thank you for putting a lot of effort into writing an answer! – Chopin Mar 22 '21 at 16:07