0
$\begingroup$

Consider the following sequences of length $n$. We are given $\sum_{i=1}^{n} c_i = \omega(n^{3/2})$ and $\sum_{i=1}^{n} d_i = \omega(n^{3/2})$ where each $c_i$ and $d_i$ is greater than 1 and at most $n$. The omega notation is to say that the sums are strictly greater than $O(n^{3/2})$ asymptotically, i.e, both the sums are $O(n^{3/2 + \epsilon})$ for some small $\epsilon > 0$.

I wish to prove that the inner product of the two sequences $\sum_{i=1}^{n} c_i d_i = \omega(n^2)$. Note that if all $c_i = d_i = \sqrt{n}$, then $\sum_{i=1}^{n} c_i d_i = O(n^2)$. I feel there is some straightforward reverse cauchy schwarz inequality that should show this. I am aware of Polya-Szego’s inequality but it gives a weaker bound.

$\endgroup$
0
$\begingroup$

If $$ c_i = \left\{ \begin{array}{lr} 1 & : i \text{ even}\\ i^{\frac{1}{2}+\epsilon} & : i \text{ odd} \end{array} \right. $$ and $$ d_i = \left\{ \begin{array}{lr} 1 & : i \text{ odd}\\ i^{\frac{1}{2}+\epsilon} & : i \text{ even} \end{array} \right. $$

Then $\sum_{i=1}^n c_i$, $\sum_{i=1}^n d_i$ are on the order of $n^{3/2+\epsilon}$, but so is $\sum_{i=1}^n c_id_i$.

$\endgroup$

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.