5
$\begingroup$

I was reading lecture notes for MIT 18.S096 and came across the following open problem in discrepancy theory known as the Komlós Conjecture:

Given $n$, let $K(n)$ denote the infimum over all real numbers such that: for all sets of $n$ vectors $u_1,\ldots,u_n\in\mathbb{R}^n$ satisfying $\| u_i\|_2\leq 1$, there exists signs $\epsilon_i=\pm 1$ such that \begin{equation} \| \epsilon_1u_1+\epsilon_2u_2\ldots+\epsilon_nu_n\|_{\infty}\leq K(n). \end{equation} There exists a universal constant $K$ such that $K(n)\leq K$ for all $n$.

The author asserts that it is not too difficult to show the simpler claim that $K(n)\leq \sqrt{n}$; however, I'm having some difficulty showing this. The $\sqrt{n}$ is fairly suggestive of using Cauchy-Schwartz, but it's not immediately clear to me how one could use it; once can write the above problem in matrix form as $\min_{x\in \{-1,1\}^n} \|Ux\|_{\infty}$, where the columns of $U$ are the $u_i$, but the fundamental problem is that bounds on the row norms don't seem helpful. Any help would be appreciated; I feel like I'm missing something obvious. Thanks!

$\endgroup$

1 Answer 1

4
$\begingroup$

We want to show that if $\|u_i\|_2 \le 1$ for all $i\in\{1,\dots,n\}$ then there exists $\epsilon\in\{-1,+1\}^n$ such that $\|\epsilon_1u_1+\cdots+\epsilon_nu_n\|_\infty \le \sqrt n$. Since this is an existence statement for an upper bound, it's helpful to think of it as if we took the minimum over all $\epsilon\in\{-1,+1\}^n$ it must be less than the right hand side. Squaring both sides, we will show that $$\min_{\epsilon\in\{-1,+1\}^n}\|\epsilon_1u_1+\cdots+\epsilon_nu_n\|_\infty^2 \le n.$$ We could try to show this by constructing a favorable $\epsilon$ in terms of $u_1,\dots,u_n$. Instead, we'll show the bound holds on average. Let $\varepsilon = (\varepsilon_1,\dots,\varepsilon_n)$ be $n$ iid Rademacher variables, i.e. they each take values $-1,+1$ independently and equiprobably. We have \begin{align*} \min_{\epsilon\in\{-1,+1\}^n}&\|\epsilon_1u_1+\cdots+\epsilon_nu_n\|_\infty^2 \\ &\le \mathbb E\left[\|\varepsilon_1u_1+\cdots+\varepsilon_nu_n\|_\infty^2\right] && \text{min less than avg} \\ &\le \mathbb E\left[\|\varepsilon_1u_1+\cdots+\varepsilon_nu_n\|_2^2\right] && \text{monotonicity of $p$-norms} \\ &= \sum_i\underbrace{\mathbb E\left[\varepsilon_i^2\right]}_{=1}\|u_i\|_2^2 + \sum_{j\ne k}\underbrace{\mathbb E\left[\varepsilon_j \varepsilon_k\right]}_{=0}u_j\cdot u_k \\ &=\sum_i\|u_i\|_2^2 \le n. \end{align*} I hope this helps.

$\endgroup$
1
  • $\begingroup$ Awesome, thanks! I had tried relating the value to the expectation because of the natural connection to Rademacher complexity, but for some reason didn't think to proceed... $\endgroup$
    – J.G
    Commented Jun 26, 2017 at 12:29

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .