# Useful conditions for proving super polynomial lower bound for some kind of recurrences

Given a recurrence of the form $$\forall n,m.\ \ T(n,m)=\begin{cases}1,&,m=1\\\sum_i{T(n_i,m_i)}&,\text{else}\end{cases}$$

Note: both $$n_i$$ and $$m_i$$ are dependent on $$n,m$$ so they should have been written above as $$n_{i,n,m}$$ and $$m_{i,n,m}$$, but they are written above as $$n_i$$ and $$m_i$$ in a way of abbreviation for more readablity.

Let us assume that $$T$$ is non-decreasing w.r.t $$n$$, and non-increasing w.r.t $$m$$.

I am looking for a useful, necessary and sufficient condition so that $$\exists k. T(n,m)=O\bigg(\Big(\log(m)+n\Big)^k\bigg)$$

The importance of such conditions stems from their applicabilty in concluding super-polynomial lower bounds on complex recurrences of the above-mentioned form.