Is $ x \log x = O(x^{1+\epsilon})$ for every $\epsilon > 0$?

Question

I am an amateur.

Claim
$$ x \log x = O(x^{1+\epsilon}) \qquad (A) $$ for every $\epsilon > 0$, $x \in \mathbb{R} \;, x > 2$.

Tried to disproof this, but doubt the proof is correct.

Basic idea: Define $f(x,\epsilon)= \frac{x \log x}{x^{1+\epsilon}}$, show that $f(x,\epsilon)$ is unbounded.

I suppose if $a(x)/b(x,\epsilon)$ is unbounded it is impossible $a(x)=O(b(x,\epsilon))$

Solving $x \log x = x^{1+\epsilon} $ gives $\epsilon_0 = -{\frac {\log \left( x \right) -\log \left( x\log \left( x \right) \right) }{\log \left( x \right) }}$.

$\epsilon_0$ is positive for $x$ large enough.

Consider $$f(x,\epsilon / 10) = {\frac {{x}^{1/10}\log \left( x \right) }{ \left( x\log \left( x \right) \right) ^{1/10}}} \qquad (B) $$

(B) is unbounded and the limit at infinity is infinity for positive epsilon.

I suppose this shows (A) is false.

Is this correct? In particular "Basic idea" in case of typos.

A correct proof or disproof of (A)?

What is the limit of $(\log x)/x^{\epsilon}$ when $x$ goes to 0 and $\epsilon$ is fixed? — user37238, Dec 10 '13 at 15:16
@user37238 I don't know. Anyway I edited the question with $x > 2$. Thank you. — elluser, Dec 10 '13 at 15:31

Jean-Claude Arbaut · Accepted Answer · 2013-12-10T16:14:21.197

Basically, you want to know if, when $\alpha>0$,

$$\lim_{x\to\infty} \frac{\log x}{x^\alpha} = 0$$

It's true.

Let $x^\alpha=y$, or $x=y^{1/\alpha}$. Then the limit is the same as

$$\lim_{y\to\infty} \frac{\log \left(y^{1/\alpha} \right)}{y} = \frac 1 \alpha\lim_{y\to\infty} \frac{\log y }{y} $$

Now, you have only one case to check. Let $f(x)=\frac{\log{x}}{x}$, on $[1, +\infty[$, then

$$f'(x)=\frac{1-\log(x)}{x^2}$$

So $f' \leq 0$ and $f\geq 0$, thus $f$ has a limit when $x\to+\infty$.

If this limit is $A$, we already know that $\lim_{x\to\infty} \frac{\log x}{x^\alpha}=\frac{A}{\alpha}$

Then

$$\frac{\log x}{x}=\frac{1}{\sqrt{x}}\frac{\log x}{\sqrt{x}}$$

The first factor tends to $0$ when $x\to+\infty$, and the second to $2A$.

Hence, for any $\alpha>0$,

$$\lim_{x\to\infty} \frac{\log x}{x} =\lim_{x\to\infty} \frac{\log x}{x^\alpha}=0$$

And you can conclude that

$$\log x = o(x^{\alpha}) = O(x^{\alpha})$$

So

$$x \log x = o(x^{1+\alpha}) = O(x^{1+\alpha})$$

The little-o is slightly stronger here, but, it adds not much.

Note: you could of course have differentiated directly

$$\left(\frac{\log x}{x^\alpha}\right)' = \frac{1-\alpha \log x}{x^{\alpha+1}}$$

And you would finish the proof as easily.

Thank you. Will check this tomorrow. What is the first critical error in my proof? — elluser, Dec 10 '13 at 17:44
$\varepsilon$ may be any positive value, but it must be fixed once and for all, not a function of $x$. — Jean-Claude Arbaut, Dec 10 '13 at 18:10

score 1 · Answer 2 · answered Dec 10 '13 at 16:26

1

It's slightly more efficient to use l'Hopital's rule:

$$\lim_{n\to\infty} \frac{\log n}{n^\alpha}=\lim_{n\to\infty} \frac{1/n}{\alpha n^{\alpha-1}}=\lim_{n\to\infty} \frac{1}{\alpha n^\alpha}=0.$$

answered Dec 10 '13 at 16:26

Mikhail Katz

42,112
3
66
131

Thank you. Will check this tomorrow. What is the first critical error in my proof? – elluser Dec 10 '13 at 17:45
The assumption (A) does not imply that $x \log x = x^{1+\epsilon}$. – Mikhail Katz Dec 10 '13 at 17:48

Is $ x \log x = O(x^{1+\epsilon})$ for every $\epsilon > 0$?

2 Answers2