This question is connected with my previous question: [Union of Hamming balls](https://mathoverflow.net/questions/247159/union-of-hamming-balls)


Let $V \subseteq \{0,1\}^n$, $\log|V| = k < 0.9n$. 


Harper's theorem states that the set $V\_r:= \bigcup\_{x \in V} V\_r(x)$ has rather large cardinality ($V\_r(x)$ is a Hamming full-ball of radius $r$ and center $x$, $|V\_r|$ is the smallest when $V$ is a Hamming full-ball).


Now consider a set $V\_r^a$ with the following property: $|V\_r^a \bigcap V\_r(x)| \ge a \cdot|V\_r(x)|$ for every $x \in V$. For explicitness we may assume that $a = \frac{1}{100}$.


What is a lower bound for $|V\_r^a|$? Is it true that $\log|V\_r^a| - \log|V| = \Omega(n)$ for $k, r = \Omega(n)$ and constant $a$? 


UPD. Why this question is interesting? Let $x \in \{0,1\}^n$ be a string of Kolmogorov complexity $k$, where $k < n$. Change $r$ random symbols of $x$ and get a string $x'$. It seems that with high probability the complexity of $x'$ is greater than the complexity of $x$, but how to prove it? In fact this question is equivalent to the question above.



Union of almost Hamming balls
Unfortunately the life is not that good. Take the Hamming ball $B\_R$ of radius $R=\beta n$ (where $\beta$ is small but positive) centered at $(0,0,\dots,0)$ and take the union of the Hamming balls of radius $r\ll n$ centered at the points from that ball. Not surprisingly you'll get the Hamming ball of radius $R+r$ and that is the worst case scenario for the full balls. Now notice that if you take a point $x\in B\_R$ with at least $R-r\approx\beta n$ ones in it and try to flip $r$ random entries, in the typical case you'll flip $\beta r$ ones and only $(1-\beta)r$ zeroes, so at least one half or so of the Hamming ball of radius $r$ centered at $x$ lies within the Hamming ball centered at the origin of radius $R+(1-2\beta)r$, which has the volume about $\left(\frac{1-\beta}\beta\right)^{2\beta r}$ times smaller than the ball of radius $R+r$ and that factor is exponential in $n$ if $r$ is a small multiple of $n$.


***Edit*** To answer the modified question, let us restate it in the following way. Assume that a set $F$ has measure ($2^{-n}$ times the number of points) $\mu(F)\le e^{-sn}$. Consider $r=\frac{1-t}{1+t}n$ with $t\in(0,1)$. Then the set $G$ of points $x$ such that $\mu(V\_r(x)\cap F)\ge a\mu(V\_r(x))$ has measure $\mu(G)\le e^{-c(s,t)n}\mu(F)$. 


To prove it, consider the convolution of the characteristic function $f$ of the set $F$ with the kernel $K\_t(x)=\prod\_{j=1}^n (1+tx\_j)$ (I assume that the cube is $\{-1,1\}^n$ and the convolution is multiplicative and associated to the natural group structure on the cube given by the coordinate-wise multiplication). This kernel has total mass $1$ out of which a noticeable part ($1/(n+1)$ for sure but much better bounds are possible) lies on the boundary of $V\_r(\pmb 1)$ (that is why we chose such a strange parameterization for $r/n$). Since that boundary also is where $\min K\_t$ is attained in $V\_r(\pmb 1)$, we conclude that $g=f\*K\_t\ge \frac an$ on $G$.


On the other hand, this convolution corresponds to the multiplier $t^{|S|}$ in the Fourier-Walsh representation. So, if $f=\sum\_{k=0}^n f\_k$ is the Fourier-Walsh orthogonal decomposition, we have $g=\sum\_k t^k f\_k$. Now observe that $\|f\_k\|\_\infty\le {n\choose k}\mu(F)$, which is below $e^{-sn/2}\ll \frac an$ for $k\le \gamma(s,t)n$. Thus, the large values of $g$ on $G$ are due to the tail. However, the $L^2$-norm of that tail is exponentially small compared to the $L^2$-norm of $f$ and the desired result follows.


Of course, you can try to choose a better kernel to get sharper bounds though in that case the computation of the corresponding multiplier will be more difficult. I do not know if this simple approach can give you an asymptotically sharp bound however.


