Put and . If the assertion is immediate. Otherwise, suppose
Since , this makes , so is sufficiently small to apply the maximum-influence logarithmic lower bound once is large. That bound gives
For all sufficiently large , the last quantity exceeds , contradicting . The choice of sufficiently large is independent of . Therefore