# Proving that $S_1+S_2 \leq f^{-\omega(1)}$

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.

• If $$S_1, S_2, f^{-c} = 1$$, your weaker version holds but the proof fails. Sep 14 '19 at 14:45
• 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$? Sep 14 '19 at 14:54
• Also, if $f(x,y,z) > 1$ and $S \leq f(x,y,z)^{-c}$ for all $c$, then $S \leq 0$. Sep 14 '19 at 14:55
• @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.
– Root
Sep 14 '19 at 15:04
• Perhaps you should tell us more about your actual problem. 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.
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}.$$