6
$\begingroup$

Let $S$ be a subset of vectors in $\mathbb{F}_2^{3n}$ having Hamming weight $n$. Suppose that $S$ contains $m$ pairs of vectors having disjoint supports (that is, they are at Hamming distance $2n$ from each other). Then, is $|\text{Span}(S)| \ge m \cdot (2/3)^{3n}$?

If we take $S$ to be all vectors of weight $n$, $|\text{Span}(S)| = 2^{3n}$ if $n$ is odd and $2^{3n-1}$ if $n$ is even. In this case $m=\binom{3n}{n}\binom{2n}{n}$, and so by Stirling's inequality one checks that the bound holds (and is essentially tight for large $n$). Basically, the question is if one can beat this example.

$\endgroup$

1 Answer 1

1
$\begingroup$

Here is a sketch of a proof. Denoting the codimension of ${\rm{Span}}(S)$ in $\Bbb{F}_2^{3n}$ by $k$, one has $|{\rm{Span}}(S)|=2^{3n-k}$. So the desired inequality amounts to $2^{k}m\leq 3^{3n}$. Assessing the case of $k=0$, meaning when $S$ spans $\Bbb{F}_2^{3n}$, helps with understanding how powers of $3$ emerge. Each pair $(\mathbf{a},\mathbf{b})$ of binary codes in $\Bbb{F}_2^{3n}$ with disjoint supports amounts to a pair of disjoint subsets of $\{1,\dots,3n\}$. The number of the latter pairs is $3^{3n}$. Thus the maximum number of pairs $(\mathbf{a},\mathbf{b})$ with disjoint support (let alone the condition of having Hamming weight $n$) never exceeds $3^{3n}$.

In general, the idea is to assign to each of the $m$ pairs of binary codes from $S$ (or even from ${\rm{Span}}(S)$) with prescribed properties a pair $({\rm{supp}}(\mathbf{a}),{\rm{supp}}(\mathbf{b}))$ of disjoint subsets of $\{1,\dots,3n\}$. Here $\rm{supp}$ denotes the support, meaning indices of $1$ entries. The assignment is clearly injective. The total number of pairs of disjoint subsets of $\{1,\dots,3n\}$ is $3^{3n}$. One should argue that a positive codimension $k={\rm{Span}}(S)>0$ imposes constraints on the pairs $({\rm{supp}}(\mathbf{a}),{\rm{supp}}(\mathbf{b}))$ of disjoint subsets which result in $2^km\leq 3^{3n}$. To see where the limitations on pairs $({\rm{supp}}(\mathbf{a}),{\rm{supp}}(\mathbf{b}))$ come from, describe the subspace ${\rm{Span}}(S)$ of $\Bbb{F}_2^{3n}$ as $$ \{\mathbf{x}\mid\mathbf{x}\cdot\mathbf{x}_1=\dots=\mathbf{x}\cdot\mathbf{x}_k=0\} $$ where for $\mathbf{x}_1,\dots,\mathbf{x}_k\in\Bbb{F}_2^{3n}$ are linearly independent and $\cdot$ denotes the dot product modulo two. For any of the $m$ pair $(\mathbf{a},\mathbf{b})$ with prescribed properties, the sizes of intersections ${\rm{supp}}(\mathbf{a})\cap{\rm{supp}}(\mathbf{x}_i)$ and ${\rm{supp}}(\mathbf{b})\cap{\rm{supp}}(\mathbf{x}_i)$ must be even, thus $k$ restrictions imposed on pairs $({\rm{supp}}(\mathbf{a}),{\rm{supp}}(\mathbf{b}))$ of disjoint subsets. These "restrictions" should be independent of each other since no equality among $\mathbf{x}\cdot\mathbf{x}_1=0,\dots,\mathbf{x}\cdot\mathbf{x}_k=0$ is implied by the others.

Let us look at the first two cases:

  • $k=1$) The pairs $(\mathbf{a},\mathbf{b})$ are subjected to $2\mid |{\rm{supp}}(\mathbf{a})\cap{\rm{supp}}(\mathbf{x}_1)|,\,|{\rm{supp}}(\mathbf{b})\cap{\rm{supp}}(\mathbf{x}_1)|$. For pairs $({\rm{supp}}(\mathbf{a}),{\rm{supp}}(\mathbf{b}))$ of disjoint subsets of $\{1,\dots,3n\}$ whose intersections with the non-empty subset ${\rm{supp}}(\mathbf{x}_1)$ each has an even number of elements, the number of possibilities is at most the number of pairs of disjoint subsets of even orders of ${\rm{supp}}(\mathbf{x}_1)$ times the number of pairs of disjoint subsets of $\{1,\dots,3n\}\setminus{\rm{supp}}(\mathbf{x}_1)$; that is, no more than $\left(\frac{1}{2}\,3^{|{\rm{supp}}(\mathbf{x}_1)|}\right)3^{3n-|{\rm{supp}}(\mathbf{x}_1)|}=\frac{3^{3n}}{2^k}$.
  • $k=2$) Here we have $2\mid |{\rm{supp}}(\mathbf{a})\cap{\rm{supp}}(\mathbf{x}_i)|,\,|{\rm{supp}}(\mathbf{b})\cap{\rm{supp}}(\mathbf{x}_i)|$ for $i=1,2$. Now $\{1,\dots,3n\}$ can be written as the disjoint union of ${\rm{supp}}(\mathbf{x}_1)\cap{\rm{supp}}(\mathbf{x}_2)$, ${\rm{supp}}(\mathbf{x}_1)\setminus{\rm{supp}}(\mathbf{x}_2)$, ${\rm{supp}}(\mathbf{x}_2)\setminus{\rm{supp}}(\mathbf{x}_1)$, and $\{1,\dots,3n\}\setminus({\rm{supp}}(\mathbf{x}_1)\cup{\rm{supp}}(\mathbf{x}_2))$. Therefore, through taking intersection with them, the pair $({\rm{supp}}(\mathbf{a}),{\rm{supp}}(\mathbf{b}))$ amounts to four pairs of disjoint subsets, each contained in one of the preceding four subsets. But the constraints on the parity of intersections with ${\rm{supp}}(\mathbf{x}_1)$ and ${\rm{supp}}(\mathbf{x}_2)$ cause the total number $3^{3n}$ of disjoint pairs to be divided by $2^k=4$. To see this, condition on the parities of $|{\rm{supp}}(\mathbf{a})\cap({\rm{supp}}(\mathbf{x}_1)\cap{\rm{supp}}(\mathbf{x}_2))|$ and $|{\rm{supp}}(\mathbf{b})\cap({\rm{supp}}(\mathbf{x}_1)\cap{\rm{supp}}(\mathbf{x}_2))|$. They should coincide with those of $|{\rm{supp}}(\mathbf{a})\cap({\rm{supp}}(\mathbf{x}_1)\setminus{\rm{supp}}(\mathbf{x}_2))|$ and $|{\rm{supp}}(\mathbf{b})\cap({\rm{supp}}(\mathbf{x}_1)\setminus{\rm{supp}}(\mathbf{x}_2))|$. Once the parities are specified, $\frac{1}{2}\,3^{|{\rm{supp}}(\mathbf{x}_1)\setminus{\rm{supp}}(\mathbf{x}_2)|}$ becomes an upper bound for the number of pairs of disjoint subsets. A similar statement is true when it comes to intersection with ${\rm{supp}}(\mathbf{x}_2)\setminus{\rm{supp}}(\mathbf{x}_1)$. Consequently: $$ \small m\leq 3^{|{\rm{supp}}(\mathbf{x}_1)\cap{\rm{supp}}(\mathbf{x}_2)|}\left(\frac{1}{2}\,3^{|{\rm{supp}}(\mathbf{x}_1)\setminus{\rm{supp}}(\mathbf{x}_2)|}\right)\left(\frac{1}{2}\,3^{|{\rm{supp}}(\mathbf{x}_2)\setminus{\rm{supp}}(\mathbf{x}_1)|}\right)3^{|\{1,\dots,3n\}\setminus({\rm{supp}}(\mathbf{x}_1)\cup{\rm{supp}}(\mathbf{x}_2))|} =\frac{3^{3n}}{4}. $$

The general case should follow from these arguments with some ironing. In that case, ${\rm{supp}}(\mathbf{a})$ and ${\rm{supp}}(\mathbf{b})$ should be considered in terms of their intersections with disjoint subsets $\{1,\dots,3n\}\setminus\bigcup_{i\in\{1,\dots,k\}}{\rm{supp}}(x_i)$, and with subsets of the form $\bigcap_{i\in S}{\rm{supp}}(x_i)\setminus\bigcup_{i\in\{1,\dots,k\}\setminus S}{\rm{supp}}(x_i)$ $\emptyset\neq S\subseteq\{1,\dots,k\}$.

Added) The only thing used was the disjointness of the supports, not that the questions is phrased for pairs of binary codes of length $3n$ with Hamming weight $n$ and of Hamming distance $n$. Hence one can write the result as $2^km\leq 3^N$ for any subspace $V$ of $\Bbb{F}_2^N$ where $k$ is the codimension and $m$ is the maximum number of pairs $(\mathbf{a},\mathbf{b})\in V\times V$ with ${\rm{supp}}(\mathbf{a})\cap{\rm{supp}}(\mathbf{b})=\emptyset$. Even further improvement is possible through replacing $2$ with a bigger number. The argument above was based on introducing a factor of $\frac{1}{2}$ for each one unit of increase in the codimension due to the following fact: Given a non-empty finite set $P$, the number of pairs $(R,T)$ of disjoint subsets of $P$ with $|R|,|T|\,{\rm{mod}}\,2$ specified is at most $\frac{1}{2}\,3^{p}$ where $p:=|P|>0$. Looking at this more carefully, for given $\epsilon_1,\epsilon_2\in\{0,1\}$, this number is: $$ \begin{split} &\sum_{0\leq r\leq p,\,r\stackrel{2}{\equiv}\epsilon_1} \binom{p}{r}(\#\text{ number of subsets of a set of size }p-r\text{ with parity }\epsilon_2)\\ &=\sum_{0\leq r\leq p,\,r\stackrel{2}{\equiv}\epsilon_1} \binom{p}{r}2^{p-r-1}=2^{p-1}\left(\sum_{0\leq r\leq p,\,r\stackrel{2}{\equiv}\epsilon_1}\binom{p}{r}2^{-r}\right) =\frac{3^p\pm 1}{4}\leq\frac{1}{3}\,3^p. \end{split} $$ In view of this, $2^km\leq 3^N$ may be replaced with $3^km\leq 3^N$.

For any subspace $V$ of $\Bbb{F}_2^N$, one has $$ m\leq |V|^{\log_23} $$ where $m$ denotes the number of pairs $(\mathbf{a},\mathbf{b})$ of binary codes belonging to $V$ whose supports are disjoint.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .