# Union of almost Hamming balls

This question is connected with my previous question: 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.

• Does your set $V_r^a$ have to satisfy any structural restrictions, like being a ball? Or is it purely any subset of $\{0,1\}^n$ satisfying the given inequality? – Yemon Choi Aug 10 '16 at 12:18
• @YemonChoi it is any subset satisfying the given inequality – Alexey Milovanov Aug 10 '16 at 12:20

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.

• Thank you, indeed, my exceptions were overvalued. However the lower bound for $|V_r^a|$ is still unclear - I have corrected my question. – Alexey Milovanov Aug 16 '16 at 8:54
• @Alexey OK, I modified the answer :-) – fedja Aug 23 '16 at 3:12
• Thank you! Some comments: 1) I think $t$ should be equals to $1 - 2\frac{r}{n}$. 2) Can we get the same result without a guess that $\mu(F)$ is small? 3) Could you send me your e-mail on almas239@gmail.com ? – Alexey Milovanov Sep 5 '16 at 12:31
• 2) Certainly not: take half the cube $\sum_i x_i\le 0$ for $F$. Then each Hamming ball centered in $F$ has about half of it in $F$, so there is no gain whatsoever. 3) OK. – fedja Sep 5 '16 at 14:50