Reference for a local density theorem for binary vectors

Question

I have the following theorem written on my whiteboard, but have misplaced the reference. I believe the probabilistic method may be involved in the proof. Any pointers appreciated.

Theorem Let $v\in\{0,1\}^n$ be nonzero. Let $k=v_1+\ldots+v_n$ be its Hamming weight. Then there exists $i\leq j$ such that $$v_i+v_{i+1}+\cdots+v_j\geq \frac{1}{14}\frac{k}{(1+\log_2(n/k))},$$ and $$\min\{i-1,n-j\}\geq j-i,$$ for $n$ large enough. Note that this implies $$2i\geq j+1,\quad 2j\leq n-i$$ so that there is a locally dense interval not too near to the two ends of the vector.

Answer 1

I've found the paper the result is from. It is Lemma 3.1 in

"The unbounded error communication complexity of symmetric functions", by A. A. Shertsov, Combinatorica 31 (5) (2011) 583–614.

Since there was an upvote for the question, I will give an outline of the proof below.

By symmetry, we can assume that $v_1 + v_2 + ··· + v_m \geq \frac{1}{2}k$ for some index $m \leq \lfloor n/2\rfloor$. Let $\alpha\in (0,1/2)$ be a parameter to be fixed later. Let $T\geq 0$ be the smallest integer such that $$v_1 +\cdots + v_{\lfloor m/2^T \rfloor} < (1 − α)^T(v_1 + \cdots + v_m )\quad(1).$$ Clearly, $T\geq 1.$ Since $v_1 + \cdots + v_{\lfloor m/2^T \rfloor}\leq m/2^T,$ we further obtain $$1\leq T\leq 1+ \frac{1+\log(n/k)}{\log(2-2\alpha)}.$$

The argument concludes by writing $$v_{1+\lfloor m/2^T \rfloor} + \cdots + v_{\lfloor m/2^{T-1} \rfloor}$$ as the difference $$ (v_1+\cdots+v_{\lfloor m/2^{T-1} \rfloor})-(v_1+\cdots+v_{\lfloor m/2^{T} \rfloor})\quad (2) ,$$ using the minimality of $T$ in (1) for lower bounding the first and upper bounding the second term on the RHS of (2), and applying a series of inequalities, giving $$v_{1+\lfloor m/2^T \rfloor} + \cdots + v_{\lfloor m/2^{T-1} \rfloor}\geq \frac{1}{2} \alpha \left(1-\alpha\cdot \frac{1+\log(n/k)}{\log(2-2\alpha)}\right)k,$$ followed by judicious choices of $\alpha=0.23/(1+\log(n/k)),$ $i=\lfloor m/2^{T} \rfloor+1, $ and $j =\lfloor m/2^{T-1} \rfloor.$