counting vector pairs with a given hamming distance

125 Views Asked by At

Let $\mathbb{F}_2$ denote the binary field. For integer $t\geq 0$, define $W_t = \{(x,y)\in \mathbb{F}_2^n\times \mathbb{F}_2^n: d_H(x,y)=t\}$, where $d_H(\cdot,\cdot)$ denotes the Hamming distance.

Suppose that $S,T\subseteq \mathbb{F}_2^n$ ($n$ is large) and consider $S\times T$. Note that $|W_1| = 2^n n$. My question is, if we know that $(S\times T)\cap W_1$ is large, say, $|(S\times T)\cap W_1| \geq 2^n n^{1-\epsilon}$ for some small constant $\epsilon > 0$, what can we say about $(S\times T)\cap W_t$ for other $t$? I'd like to have a lower bound in terms of $|(S\times T)\cap W_1|$.

It is easy to see that $(S\times T)\cap W_t$ could be the empty set when $t$ is even (see an answer below). So assume that $t$ is odd.

Specifically, will we have $|(S\times T)\cap W_3|\gtrsim n^2|(S\times T)\cap W_1|$, or weaker, $|(S\times T)\cap W_3|\gtrsim n^{2-\eta}|(S\times T)\cap W_1|$, where $\eta$ is a constant depending on $\epsilon$? If this is still impossible, will we have $|(S\times T)\cap W_3|\gtrsim n^{f(t,\epsilon)}|(S\times T)\cap W_3|$ for some function $f$ (which can take negative value)? I could show that $f(t,\epsilon)=-6$ or so works. But it is apparently very weak. Any idea for stronger bound?

1

There are 1 best solutions below

1
On

There is no such lower bound when $t$ is even. Indeed, take $S$ to be the set of elements of $\Bbb F_2^n$ with even Hamming weight and $T$ the set of elements with odd Hamming weight. Then $\#((S\times T)\cap W_1) = 2^{n-1}n$, yet $(S\times T)\cap W_t$ is empty for every even $t$.

I don't know whether such a lower bound exists for $t$ odd.