38
$\begingroup$

Young's inequality states that if $a, b \geq 0$, $p, q > 0$, and $\frac{1}{p} + \frac{1}{q} = 1$, then $$ab\leq \frac{a^p}{p} + \frac{b^q}{q}$$ (with equality only when $a^p = b^q$). Back when I was in my first course in real analysis, I was assigned this as homework, but I couldn't figure it out. I kept trying to manipulate the expressions algebraically, and I couldn't get anywhere. But every proof that I've seen since uses calculus in some way to prove this. For example, a common proof is based on this proof without words and integration. The proof on Wikipedia uses the fact that $\log$ is concave, which I believe requires the analytic definition of the logarithm to prove (correct me if I'm wrong).

Can this be proven using just algebraic manipulations? I know that that is a somewhat vague question, because "algebraic" is not well-defined, but I'm not sure how to make it more rigorous. But for example, the proof when $p = q = 2$ is something I would consider to be "purely algebraic":

$$0 \leq (a - b)^2 = a^2 + b^2 - 2ab,$$ so $$ab \leq \frac{a^2}{2} + \frac{b^2}{2}.$$

  • 0
    By the way, I wasn't quite sure how to properly tag this question. Apparently `proof` is not allowed.2012-12-16
  • 0
    I think fundamentally, there is no algebraic definition of $x^p$ in general when $p,q$ are real. But Ben's proof is good for when $p,q$ are rational.2012-12-16
  • 0
    @ThomasAndrews yes, I know that, but it still satisfies certain algebraic properties, which I would take for granted. For example, conditions on $x$ or $p$ for $x^p < x$ to hold.2012-12-16
  • 0
    @asmeurer I've retagged. The original tags you chose are a bit too specialized. The closest I can find to a tag that match your interpretation of "algebraic" is (algebra-precalculus), where the tag-wiki explicitly mentions symbolic manipulations, which is probably similar to what you had in mind.2012-12-17

4 Answers 4

36

This proof is from "Mathematical Toolchest" published by the Australian Mathematics Trust (image).

Example. If $p$ and $q$ are positive rationals such that $\frac1p + \frac1q = 1$, then for positive $x$ and $y$ $$\frac{x^p}p + \frac{y^q}q \ge xy.$$

Since $\frac1p + \frac1q = 1$, we can write $p = \frac{m+n}m$, $q = \frac{m+n}n$ where $m$ and $n$ are positive integers. Write $x = a^{1/p}$, $y = b^{1/q}$. Then $$\frac{x^p}p + \frac{y^q}q = \frac a{\frac{m+n}m} + \frac b{\frac{m+n}n} = \frac{ma + nb}{m + n}.$$

However, by the AM–GM inequality, $$\frac{ma + nb}{m + n} \ge (a^m \cdot b^n)^{\frac1{m+n}} = a^{\frac1p} b^{\frac1q} = xy,$$ and thus $$\frac{x^p}p + \frac{y^q}q \ge xy.$$

  • 6
    That assumes $p,q$ are rational, of course.2012-12-16
  • 0
    Cool. I didn't know of this inequality at the time, so it wouldn't have occurred to me. Apparently Young's Inequality actually is a special case of the [weighted AM-GM inequality](http://en.wikipedia.org/wiki/Inequality_of_arithmetic_and_geometric_means#Generalizations).2012-12-16
  • 0
    Which also means that one just has to believe the weighted AM-GM inequality for arbitrary real weights. Or one could use a limit/density argument to extend the inequality for rationals to arbitrary reals.2012-12-16
  • 0
    This shows that Young's inequality is equivalent to the weighted AM-GM inequality. It doesn't show how that is proven for rational weights from $\sqrt{ab}\le\frac{a+b}{2}$.2013-03-11
  • 1
    @robjohn What do you mean? All that's used is plain old AM–GM?2014-01-27
  • 1
    @Ben: it depends on what you consider the "plain old AM-GM" inequality: the basic AM-GM is $\sqrt{xy}\le\frac{x+y}{2}$. The version $x^\alpha y^{1-\alpha}\le\alpha x+(1-\alpha)y$ with $0\le\alpha\le1$ can be proven for [dyadic](http://en.wikipedia.org/wiki/Dyadic_fraction) $\alpha$ by induction on the basic case. Other $\alpha\in\mathbb{Q}$ can be achieved separately using algebra, or after establishing the inequality for all $\alpha\in\mathbb{R}$ using analysis.2014-01-27
  • 1
    @robjohn I see, thank you. I would consider plain AM–GM to be $\frac{x_1 + x_2 + \cdots + x_n}{n} \ge \sqrt[n]{x_1x_2 \cdots x_n}$ which can be shown with backward induction.2014-01-27
  • 0
    @Ben: as far as I know, to prove that version of AM-GM, you essentially need to first prove the integer version of Bernoulli's Inequality (as done at the end of [this answer](http://math.stackexchange.com/a/306245)), then use induction starting with $\sqrt{ab}\le\frac{a+b}{2}$.2014-01-28
21

Yes, at least for rational $p, q$. There is a general statement here, which can be summarized as follows:

Every polynomial inequality is a consequence of the trivial inequality $x^2 \ge 0$.

In more detail, to prove Young's inequality for general $p, q$, it suffices by a continuity argument to prove it for $p, q$ rational. By making an appropriate substitution of the form $a = x^n, b = y^m$ where $n, m$ are even integers, Young's inequality for a fixed choice of rational $p, q$ becomes equivalent to the statement that a certain polynomial with real coefficients always takes on non-negative real values when fed real inputs.

By Artin's solution to Hilbert's 17th problem, a polynomial with this property is a sum of squares of rational functions. An expression of this polynomial as a sum of squares of rational functions constitutes a proof of the corresponding case of Young's inequality from repeated application of the trivial inequality.

I don't see how you could avoid analysis for irrational $p, q$, since you can't even define the relevant functions without analysis.

  • 0
    I don't understand your statement "Every polynomial inequality is a consequence of the trivial inequality $x^2 \geq 0$." This seems to contradict the following statement in the wiki article you have cited. "The formulation of the question takes into account that there are polynomials, for example $$x^6 + x^4 y^2 + x^2 y^4 - 3x^2 y^2 z^2$$ which are non-negative over reals and yet which cannot be represented as a sum of squares of other polynomials, as Hilbert had shown in $1888$ but without giving an example: the first explicit example was found by Motzkin in $1966$."2012-12-16
  • 0
    @Marvis: Artin showed that any such polynomial can still be written as a sum of squares of _rational_ functions.2012-12-16
  • 0
    Ok. I did not pay attention to the important word ***rational functions*** in the statement of Hilbert's $17^{th}$ problem. Thanks!2012-12-16
  • 0
    Could you give insight on how the polynomial $$x^6 + x^4y^2 + x^2 y^4 - 3x^2 y^2 z^2$$ cannot be written as a sum of squares of polynomials but can be written as a sum of squares of rational functions? If not, can you show this in the context of some other example where a polynomial inequality cannot be written as a sum of squares of polynomials but as sum of squares of rational functions? Thanks.2012-12-16
  • 0
    @Marvis: I am not familiar with the details; either way this would be best asked as a separate question.2012-12-16
  • 0
    Cool. Of course, this doesn't actually prove that a proof exists, because the exponents in this case are symbolic, so there's no guarantee *a priori* that a general sum of squares formula can be found for arbitrary $p$. But the AM-GM argument gives hope that it does. I would be very interested if it could be determined.2012-12-17
  • 0
    "Every polynomial inequality is a consequence..." OK, that and the other facts of inequalities, namely the basic poset relations, and also the algebraic properties (like $a < b$, $c < d$ $\implies$ $a + c < b + d$), which are important to assert that a sum of squares is nonnegative.2012-12-17
  • 0
    @asmeurer: it guarantees that for every choice of $p, q$ there exists a sum of squares that proves Young's inequality for that choice of $p$ and $q$. It does not guarantee that these sums of squares behave nicely as you vary $p, q$, but this isn't necessary to prove Young's inequality.2012-12-17
  • 0
    Young's inequality holds for any $p$ and $q$, so one would need to find a pattern for any exponent. According to Wikipedia, explicit algorithms exist to find these. I wonder if any of them are efficient, and if so, if they are implemented anywhere.2012-12-17
  • 1
    @asmeuer: it is not necessary to find them to prove that they exist, which Artin showed.2012-12-17
  • 1
    I thought the point here was to find them to prove the inequality. Artin's theorem tells us that our search is a reasonable direction to take (and that purely algebraic proofs are possible, at least modulo choosing rational exponents only).2012-12-17
  • 0
    @asmeurer: Artin's theorem tells us that they exist. That already suffices to prove the statement "if Young's inequality is true, then there exists a proof of Young's inequality via sum of squares." It does not provide an independent proof of Young's inequality in the sense that you need to know that Young's inequality is true by some other method.2012-12-17
  • 2
    On this topic, see also http://andrescaicedo.wordpress.com/2008/11/11/275-positive-polynomials/2012-12-23
  • 1
    @AndresCaicedo excellent blog post!2012-12-24
15

With $\dfrac1p+\dfrac1q=1$, $u=x^p$, $v=y^q$, and $1+pt=u/v$, the following are equivalent: $$ \begin{align} xy&\le\frac{x^p}{p}+\frac{y^q}{q}\\ u^{1/p}v^{1/q}&\le\frac{u}{p}+\frac{v}{q}\\ (u/v)^{1/p}&\le\frac{u/v}{p}+\frac{1}{q}\\ (1+pt)^{1/p}&\le\frac{1+pt}{p}+\frac{1}{q}\\ 1+pt&\le(1+t)^p\tag{1} \end{align} $$ Where $(1)$ is the rational version of the Bernoulli inequality, proven below.


Bernoulli's Inequality for Rational Exponents

Using the integral version of the Bernoulli Inequality, proven at the end of this answer, we get that for $x\gt-n$, $$ \begin{align} \frac{\left(1+\frac{x}{n+1}\right)^{n+1}}{\left(1+\frac{x}{n}\right)^n} &=\left(\frac{(n+x+1)n}{(n+1)(n+x)}\right)^{n+1}\frac{n+x}{n}\\ &=\left(1-\frac{x}{(n+1)(n+x)}\right)^{n+1}\frac1{1-\frac{x}{n+x}}\\ &\ge\left(1-\frac{x}{n+x}\right)\frac1{1-\frac{x}{n+x}}\\[8pt] &=1\\[8pt] \left(1+\frac{x}{n+1}\right)^{n+1} &\ge\left(1+\frac{x}{n}\right)^n\tag{2} \end{align} $$ where the inequality is strict if $x\ne0$ and $n\ge1$.

Applying induction with $(2)$, we get that for $x\gt-m$ and integers $n\ge m$, $$ \left(1+\frac{x}{n}\right)^n\ge\left(1+\frac{x}{m}\right)^m\tag{3} $$ Letting $t=\frac{x}{n}\gt-\frac{m}{n}$ and taking $m^\text{th}$ roots gives $$ \left(1+t\right)^{n/m}\ge1+\frac{n}{m}t\tag{4} $$ Note that $(4)$ is trivially true for $-1\le t\le-\frac{m}{n}$. Thus, for all $t\ge-1$ and rational $p\ge1$, $$ \left(1+t\right)^p\ge1+pt\tag{5} $$ where the inequality is strict if $t\ne0$ and $p\gt1$.


Negative Exponents

As shown in $(2)$, both $\left(1+\frac xn\right)^n$ and $\left(1-\frac xn\right)^n$ are increasing in $n$, as long as $|x|\le n$. Thus, for $m=\max(k,n)$, $$ \begin{align} \left(1+\frac xk\right)^k\left(1-\frac xn\right)^n &\le\left(1+\frac xm\right)^m\left(1-\frac xm\right)^m\\ &=\left(1-\frac{x^2}{m^2}\right)^m\\[3pt] &\le1\tag6 \end{align} $$ Thus, substituting $x\mapsto kx$, and taking $n^\text{th}$ roots, we get $$ (1+x)^{k/n}\left(1-\tfrac knx\right)\le1\tag7 $$ Finally, setting $p=\tfrac kn$ yields $$ 1-px\le(1+x)^{-p}\tag8 $$ where the inequality is strict when $x\ne0$ and $p\gt0$.

8

It might be essentially easier to write $x=a^p,y=b^q$ and $t=\frac 1 p$. Then you want to prove the inequality:

$$x^{t}y^{1-t}\leq tx + (1-t)y$$

for $0 and with equality only when $x=y$.

First, we prove the general AM-GM for any $2^k$ variables. The case $k=1$ is the obvious case:

$$(x+y)^2-4xy = (x-y)^2\geq 0$$

With equality only when $x=y$.

Now assume we have proven AM-GM for $n$ terms, we will prove it for $2n$ terms.

If $x_1,...,x_{2n}$ are real, assume they are in linear order. Then:

$$\begin{align}\sqrt[2n]{x_1...x_{2n}} &= \sqrt{\sqrt[n]{x_1...x_n}\sqrt[n]{x_{n+1}...x_{2n}}}\\ &\leq \frac{1}{2}\sqrt[n]{x_1...x_n}+\frac{1}{2}\sqrt[n]{x_{n+1}...x_{2n}} \\ &\leq \frac{1}{2n}(x_1+...+x_n)+\frac{1}{2n}(x_{n+1}+...+x_{2n}) \end{align}$$

Since we linearly ordered them, the equality holds only if all the $x_i$ are equal. (Check yourself here.)

So, by induction, the AM/GM applies to any set of $2^k$ variables. If $t=r/2^k$, we can choose $x_1=x_2=..=x_r=x$ and $x_{r+1}=...=x_s=y$. Then $$\sqrt[2^k]{x^ry^{2^k-r}}\leq \frac{r}{2^k} x + \frac{2^k-r}{2^k} y$$

Which is just $$x^ty^{1-t}\leq tx + (1-t)y$$

(That was just Ben's argument above, but restricted to the $2^k$ case.)

Since the set of $t$ of the form $r/2^k$, $r,k\in\mathbb Z$ is dense in $(0,1)$, you have this inequality everywhere (although density does not obviously let you conclude that equality only occurs when $x=y$ for the arbitrary real $t$.)

  • 0
    This *does* prove the inequality for the case of $t:t\,2^k\in\mathbb{Z}$. (+1)2013-03-11
  • 0
    Yeah, to get for all rationals, you need the full AM/GM. And to get for all real $t$, you need continuity and the density of the rationals in the reals. @robjohn2013-03-11
  • 1
    I think my proof works for all rationals. It uses a pretty simply proven extension of Bernoulli's Inequality.2013-03-11