2

Given are $x_1,\ldots, x_n\in \{0,1,\ldots,n\}$, $y_1,\ldots, y_n\in \{0,1,\ldots,n\}$ with the property that

$$\sum_{i=1}^{n}{x_i}\leq B,$$ $$\sum_{i=1}^{n}{y_i}\leq B$$

Let's assume that $B$ is smaller than $n^2$. This obviously means that if there is one (or a couple) very large $x_i$, then the remaining ones have to be much smaller.

Now I want to find a function $f$ s.t. $\sum_{\{i,j\}\in I}^{}{x_i\cdot y_j}\in O(f)$. The sum iterates over some $\{i,j\}$, but they are always at most $B$ many summands in this sum, in other words, $I:=\{\{i,j\}\mid i,j\in\{1,\ldots,n\}\}$ and $|I|\leq B$. Of course, the tighter the bound for the sum the better.

How can I bound this sum knowing everything above?

user181634
  • 13
  • 2

1 Answers1

1

You don't say what $f$ is allowed to depend on. I will assume it is a function of $B$ but not of $I$. Then the answer is: $f(B) = B^2$.

For an upper bound, notice that

$$ \sum_{(i,j) \in I} x_i y_j \le \sum_{1 \le i,j \le n} x_i y_j = \sum_i x_i \sum_j y_j = B^2. $$

To show that this bound is tight, choose $S=\{1,2,\dots,\sqrt{B}\}$, $I=S\times S$, and set $x_i=y_i=\sqrt{B}$ for $i \in S$ and $x_i=y_i=0$ for $i \notin S$. Notice that

$$ \sum_{(i,j) \in I} x_i y_j = \sum_{i \in S} x_i \sum_{j \in S} y_j = B^2. $$

Therefore, the upper bound is tight, and the best possible upper bound is $f(B) = B^2$.

D.W.
  • 4,540