Hamming Distance

Question

I have a another question about calculating the size of a subset of codes. $n := 2^q$ for a natural number $q$
$d_H(v,w) := \left| \{ i \in \{1,\ldots,n\} \; | \; v_i \neq w_i\}\right|$ for
$v:=(v_1,\ldots,v_n),w:=(w_1,\ldots,w_n) \in \{0,1\}^n$

I have the following sets:

$V_i := \{ v \in \{0,1\}^n \; | \; d_H(v,w_i) = \frac{n}{2}\}$ for $i \in \{0, \ldots, q \}$

where

$w_0 := (0,0,\ldots,0) \in \{0,1\}^n$,
$w_1 := (0,1,0,1,0,1,\ldots) \in \{0,1\}^n$,
$w_2 := (0,0,1,1,0,0,1,1\ldots) \in \{0,1\}^n$,
$w_3 := (0,0,0,0,1,1,1,1,0,0,0,0,1,1,1,1,\ldots) \in \{0,1\}^n$,
and so on.. i hope you understand what i mean by $w_i$, they have $2^{i-1}$ zeros, then $2^{i-1}$ ones, then $2^{i-1}$ zeros and so on and $i \in \{0, \ldots, q\}$. I could formulate it with a definition, but i think this should be more understandable.

and i want to calculate

$\left| \bigcup_{i = 0}^{k} V_i\right|$, $k \in \{0, \ldots, q\}$

So for instance for $n=8$ we have the following:
$w_0 = (0,0,0,0,0,0,0,0)$
$w_1 = (0,1,0,1,0,1,0,1)$
$w_2 = (0,0,1,1,0,0,1,1)$
$w_3 = (0,0,0,0,1,1,1,1)$
and $|V_i| = \binom{8}{4}$ but what is $\left| \bigcup_{i = 0}^{k} V_i\right|$, $k \in \{0, \ldots, q\}$? For that i need to know the intersection between the $V_i$'s, but what is it?

EDIT: An analogous problem which is practically the same is to calculate the following:

$\left|\bigcap_{i=0}^{k} \; \{ v \in \{0,1\}^n \; | \; d_H(v,w_i) < \frac{n}{2}\}\right|$

I think this is even much harder to solve, but when i have this solution i can figure out the other.

Any solution with "inaccuracy" $\mathcal{O}(h)$ for a function $h$ is also fine (better than nothing. :D), so for instance

$\left| \bigcup_{i = 0}^{k} V_i\right| = k \cdot \binom{n}{\frac{n}{2}} + \mathcal{O}(h)$, $k \in \{0, \ldots, q\}$

But this $h$ should be smaller than the first function $k \cdot \binom{n}{\frac{n}{2}}$.

I would appreciate any help. :) Thanks,

Answer 1

EDIT: Computer calculations have shown that my idea was wrong. I initially deleted the answer, but then I realized that the first part of it was correct, and might be useful, so I'm leaving it.

We know that $V_0$ is just the set of vectors with $4\text{ } 1-$bits. What about the other $V_i?$ Let $v$ be a vector at Hamming distance $4$ from some $w_i, i >0.$ Say $v$ has $k$ one-bits at the $0$ positions of $w_i.$ Then $v$ must have $4-k$ zero-bits at the $1$ positions of $w_i,$ so $k$ one-bits at those positions, and $2k$ one-bits in all. That is, every member of the union has an even number of one-bits (and an even number of zero-bits.)

Now, does the reverse inclusion hold? It's easy to see that it does in the example case ($n=8.)$ At this point, I jumped to the conclusion that it would hold in general, but this is FALSE. Still, we know that there are no vectors with an odd number of one-bits in the union.

Answer 2

I have written only few examples calculated via computer. Maybe they'll help to figure out general formula.

If $n=2^q$, then denote $$M_n(k) = \left| \bigcup_{i = 0}^{k} V_i\right|, \quad k \in \{0, 1, \ldots, q\}.$$

---

$n=4 \quad (q=2):$

$w_0=0000,$
$w_1=0101,$
$w_2=0011;$

$M_4(0) = 6 = \binom{n}{n/2}$;
$M_4(1) = 8$;
$M_4(2) = 8 \quad(=50 \%)$;

---

$n=8\quad (q=3):$

$w_0=0000\;0000,$
$w_1=0101\;0101,$
$w_2=0011\;0011;$
$w_3=0000\;1111;$

$M_8(0) = 70 = \binom{n}{n/2}$;
$M_8(1) = 104$;
$M_8(2) = 120$;
$M_8(3) = 128 \quad(=50\%)$;

---

$n=16\quad (q=4):$

$w_0=0000\;0000\;0000\;0000,$
$w_1=0101\;0101\;0101\;0101,$
$w_2=0011\;0011\;0011\;0011;$
$w_3=0000\;1111\;0000\;1111;$
$w_4=0000\;0000\;1111\;1111;$

$M_{16}(0) = 12870 = \binom{n}{n/2}$;
$M_{16}(1) = 20840$;
$M_{16}(2) = 25720$;
$M_{16}(3) = 28672$;
$M_{16}(4) = 30432 \quad(\approx 46.4355 \%)$;

---

$n=32\quad (q=5):$

$w_0=0000\;0000\;0000\;0000\;0000\;0000\;0000\;0000,$
$w_1=0101\;0101\;0101\;0101\;0101\;0101\;0101\;0101,$
$w_2=0011\;0011\;0011\;0011\;0011\;0011\;0011\;0011\;$
$w_3=0000\;1111\;0000\;1111\;0000\;1111\;0000\;1111;$
$w_4=0000\;0000\;1111\;1111\;0000\;0000\;1111\;1111;$
$w_5=0000\;0000\;0000\;0000\;1111\;1111\;1111\;1111;$

$M_{32}(0) = 601080390 = \binom{n}{n/2}$;
$M_{32}(1) = 1036523880 $;
$M_{32}(2) = 1351246968$;
$M_{32}(3) = 1578186752$;
$M_{32}(4) = 1741440992$;
$M_{32}(5) = 1858600192 \quad(\approx 43.2739\%)$.