6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Yemon Choi Aug 10 '16 at 12:18
  • $\begingroup$ @YemonChoi it is any subset satisfying the given inequality $\endgroup$ – Alexey Milovanov Aug 10 '16 at 12:20
4
+25
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you, indeed, my exceptions were overvalued. However the lower bound for $|V_r^a|$ is still unclear - I have corrected my question. $\endgroup$ – Alexey Milovanov Aug 16 '16 at 8:54
  • $\begingroup$ @Alexey OK, I modified the answer :-) $\endgroup$ – fedja Aug 23 '16 at 3:12
  • $\begingroup$ 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 ? $\endgroup$ – Alexey Milovanov Sep 5 '16 at 12:31
  • $\begingroup$ 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. $\endgroup$ – fedja Sep 5 '16 at 14:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.