2
$\begingroup$

What kind of a function $f$ must be to satisfy the following?

If $\sum_{i=1}^{n} y_i \leq \sum_{j=1}^{n} x_j$, where $x_j, y_i \in [0,1],\forall i,j$ then $$ \sum_{i=1}^{n} f(y_i) \leq \sum_{j=1}^{n} f(x_j).$$

Any help would be appreciated. Thanks in advance!

Preferably $f$ must be convex and increasing.

$f$ is linear from the answer given by the user grand_chat. What if the above inequalities($\leq$) are replaced by the strict inequality ($<$)?

$\endgroup$
3
$\begingroup$

The only solutions are linear, i.e. $f(x) = cx + b$.

Wlog we can assume $f(0)=0$ by considering $g(x):=f(x)-f(0)$. Also, $f$ is nondecreasing; this follows from applying the stated property with $n=1$.

Taking $x_1+x_2 = y_1+y_2$ and applying the stated property twice (in both directions of inequality) we obtain: $$f(y_1)+f(y_2) = f(x_1) + f(x_2)\qquad\text{whenever $y_1+y_2=x_1+x_2$.}\tag1 $$

Finally note that $(x+y) + 0 = x + y$ so (1) gives $$f(x+y) = f(x) + f(y).\tag2$$ Equation (2) is the famous Cauchy functional equation. Property (2) along with the monotonicity of $f$ implies that $f(x)=cx$ for some $c\ge0$ (since $f$ is nondecreasing).


EDIT: If we relax the inequality $(\le)$ to a strict inequality $(<)$, the same result follows except we rule out the possibility $c=0$. This follows from a continuity argument:

  1. First show that (2) holds whenever $y$ is a continuity point for $f$, by considering $$x+(y-\epsilon) < (x+y) + 0 < x + (y+\epsilon).$$

  2. $f$ is monotone, so has only countably many discontinuities. Let $x_0$ be a continuity point for $f$, and let $\{ y_n \}$ be a sequence of continuity points tending to $0$. We have for all $n$ $$ f(y_n) = f(x_0+y_n) - f(x_0). $$ Since $f$ is continuous at $x_0$, we have $\lim f(y_n)=0$. Monotonicity of $f$ forces $f$ to be continuous at zero.

  3. Lastly, let $x$ be arbitrary and let $\{ y_n\}$ be a sequence of continuity points tending to zero. Letting $n\to\infty$ in the identity $$ f(x+y_n)=f(x) + f(y_n) $$ shows that $f$ is continuous at $x$. Hence every point is a continuity point for $f$, and therefore (2) holds everywhere.

$\endgroup$
  • $\begingroup$ Agreed. What if I have $<$ instead of $\leq$ in both the hypothesis and the implication property? Thanks for the earlier answer! $\endgroup$ – rookie May 10 '17 at 5:29
  • 1
    $\begingroup$ Shouldn't $c$ be a non-negative real number? $\endgroup$ – PN Karthik May 10 '17 at 5:52
  • $\begingroup$ And a small error. Since $f$ is nondecreasing, $c$ must be positive. $\endgroup$ – rookie May 10 '17 at 6:16
  • 1
    $\begingroup$ @Karthik Yes, $c\ge0$. I've made that correction. $\endgroup$ – grand_chat May 10 '17 at 13:46
  • 1
    $\begingroup$ @stud_iisc Nope. For example, $f(x):=x^2$ is strictly convex but it is not true that $0^2 + 3^2 < 2^2 + 2^2$. $\endgroup$ – grand_chat May 10 '17 at 15:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.