Given two sets; $X = \{x_i : x_i \geq 0; i \in [\sqrt{n}]\}$ and $A = \{a_i : |a_i| \leq 1; i \in [\sqrt{n}]\}$ of size $n^{\frac{1}{2}}$ each, with the following properties
\begin{equation}\label{eq1}
\sum_{i=1}^{\sqrt{n}}x_i \leq 1;
\end{equation}
\begin{equation}\label{eq2}
\left\lvert\sum_{i=1}^{j}a_i\right\rvert \leq 1; \forall 1\leq j \leq \sqrt{n}.
\end{equation}
Define $$f(X,A) := \min_{1\leq j\leq k \leq n^{\frac{1}{2}} } \left\{{\left(\sum_{i=j}^k {x_i}\right)^2} \times \left|\sum_{i=j}^k {a_i}\right|\right\}. $$
Also define $$f_n := \max f(X,A);$$ where the maximum is taken over all possible sets $X$, $A$ satisfying the properties. A trivial upper bound would be the following $$f(X,A) \leq \min_{1\leq j\leq k \leq n^{\frac{1}{2}} } \left\{{\left(\sum_{i=j}^k {x_i}\right)^2} \right\} \ll n^{-1};$$
where $a \ll b$ means there exists an absolute constant $\delta$ such that $a \leq \delta b$. Hence $$f_n \ll n^{-1}.$$
I am interested in finding non-trivial upper bound for $f_n$. For example something like $n^{-\frac{5}{4}}$ would be great.
This problem basically generated from a geometry problem I was trying. After using some Erdős–Szekeres type estimates I am stuck with this type of equation which I don't know how to estimate nicely. As the $a_i$'s can take negative values most inequalities I know of are not applicable.
Best Answer
We have $\frac{1}{2n} \le f_n \le \frac{1}{n}$. So there is no asymptotically sharper upper bound.
To see the lower bound, consider $x_i = 1/\sqrt n$ and $a_i = b_i-b_{i-1}$, where $b_i$ is defined as follows. Let $d_k(i)$ be the $k$th binary digit (corresponding to $2^k$) of the integer $i$. For example, $d_1(2) = 1$. Then, let $$b_i = \frac{3}{4}\sum_{k=0}^\infty 4^{-k} d_k(i).$$ So, $\{b_i\}_{i=0}^\infty = \{0, \frac{3}{4}, \frac{3}{16}, \frac{15}{16}, \frac{1}{16}, \dots\}$. The construction of $b$ gives $0 \le b_i \le 1$ for $i \ge 0$, which means $|a_i| \le 1$ and $\left|\sum_{i=1}^j a_i\right| \le 1$ as required.
Next, pick two indices $i \ne j$. There is some $k \ge 0$ such satisfying $2^k \le |i-j| < 2^{k+1}$. Also, there is a first position $l \le k$ where $i$ and $j$ differ in binary. That is, $d_l(i) \ne d_l(j)$. Furthermore, $b$ was constructed such that this means $|b_i-b_j| \ge \frac{1}{2}4^{-l}$. Hence, for all $i \ne j$, we have $|b_i-b_j| \ge \frac{1}{2}4^{-l} \ge \frac{1}{2}4^{-k} \ge \frac{1}{2(i-j)^2}$.
Now we can compute the bound $$f_n \ge f(X,A) = \min_{1\le j\le k\le \sqrt n} \left(\sum_{i=j}^k x_i\right)^2 \times \left|\sum_{i=j}^k a_i\right| = \min_{1\le j\le k\le \sqrt n} \frac{(k-j+1)^2}{n} |b_k-b_{j-1}| \ge \min_{1\le j\le k\le \sqrt n} \frac{(k-j+1)^2}{n} \frac{1}{2(k-j+1)^2} = \frac{1}{2n}.$$