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.



Reference for a local density theorem for binary vectors
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.$


