I am trying to show for every c, there exists $M\text{ such that }(x,y,z)\geq M$ then $S_1(x,y,z) + S_2(x,y,z) \leq ( f (x,y,z))^{-c} $ . For a particular $S_1,S_2,f$. Does it suffice to prove there exists M1, for corresponding $S_1$, with $S_1(x,y,z) \leq (f(x,y,z))^{-c} $ and $M_2$ for $S_2({x,y,z)} \leq (f(x,y,z) )^{-c} $?

This is in the same spirit as showing $O(S_1+S_2) \leq T$ can be done by showing individual upper bounds.

All functions are strictly positive increasing functions. In particular, $f$ is not a constant.

I am trying to show that there for large enough $x,y,z$, $S_1 + S_2$ is smaller than the inverse of any polynomial in $f$.

I am looking to solve it for a particular case of $f=x^2 y^2+xz\ log (xz)$ but general answers are also appreciated.

  • $\begingroup$ If $$S_1, S_2, f^{-c} = 1$$, your weaker version holds but the proof fails. $\endgroup$ Sep 14 '19 at 14:45
  • $\begingroup$ It doesn't suffice. Consider $f(x,y,z) = 1$. If you show $S_1,S_2 \leq 1$, does it follow that $S_1+S_2 \leq 1$? $\endgroup$ Sep 14 '19 at 14:54
  • $\begingroup$ Also, if $f(x,y,z) > 1$ and $S \leq f(x,y,z)^{-c}$ for all $c$, then $S \leq 0$. $\endgroup$ Sep 14 '19 at 14:55
  • $\begingroup$ @Yuval Filmus what when neither of them are constants. For a particular problem I'm looking at, I am trying to show that S1 + S2 is smaller than inverse of every polynomial in f under the proposed assumptions. $\endgroup$
    – Root
    Sep 14 '19 at 15:04
  • $\begingroup$ Perhaps you should tell us more about your actual problem. $\endgroup$ Sep 14 '19 at 16:00

Let's consider the simpler case in which $f$ only has one input — the general case is the same, given that you use the correct definitions.

Here is what we want to prove:

Suppose that $\lim_{n\to\infty} f(n) = \infty$.

If for all $c \geq 0$ there exists $N$ such that for all $n \geq N$, $S_1(n) \leq f(n)^{-c}$ and $S_2(n) \leq f(n)^{-c}$, then for all $c \geq 0$ there exists $N$ such that for all $n \geq N$, $S_1(n) + S_2(n) \leq f(n)^{-c}$.

Let us be given $c \geq 0$. Let $N_1$ be such that $f(n) \geq 2$ for all $n \geq N_1$, and let $N_2$ be such that for all $n \geq N_2$, $S_1(n),S_2(n) \leq f(n)^{-(c+1)}$. Let $N = \max(N_1,N_2)$. Then for $n \geq N$, $$ S_1(n) + S_2(n) \leq 2f(n)^{-(c+1)} = \frac{2}{f(n)} f(n)^{-c} \leq f(n)^{-c}. $$


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.