Upperbound on cardinality of product of two string sets at pairwise Hamming distance $> 1$ I am considering products $U\times V$ of subsets $U, V\subset \{0, 1\}^p$ with a pairwise Hamming distance greater than 1 : $\forall uv\in U\times V, D(u,v) \geq 2$.

Given $p$, I am looking for a good asymptotic upperbound on $\mid U\times V\mid$, the cardinality of the products, for all possible choices of $U$ and $V$.

To make it hopefully more precise :
$$\max \{\operatorname{Card} \ (U\times V) \mid \ U, V\subset \{0, 1\}^p\mbox{ such that  }\forall uv\in U\times V, D(u,v) \geq 2\}.$$
Consider $p=2q$, $q\ge 1$.

Asymptotically, the quantity you are after is $2^{4q-2}$.

First, let's prove a lemma of general interest.

Lemma $(2^{2q}/\sqrt{\pi q})/1.136 &lt; \binom{2q}{q} &lt; 2^{2q}/\sqrt{\pi q}$.

Proof: Recall the Robbins bounds
$$
n! = \sqrt{2\pi}n^{n+1/2}e^{-n}e^{r_n},
$$
where $1/(12n+1) &lt; r_n &lt; 1/(12n)$.
This gives
$$
\binom{2q}{q} = 2^{2q}e^{r_{2q}}/\sqrt{\pi q}e^{2r_q} &gt;
\left(2^{2q}/\sqrt{\pi q}\right)/c
$$
where $c = e^{(18q + 1)/(6q(24q+1))} &lt; e^{19/150} &lt; 1.136$.
Further,
$$
\binom{2q}{q} &lt; \left(2^{2q}/\sqrt{\pi q}\right)/d
$$
where $d = e^{(36q - 1)/(24q(12q+1))} &gt; 1$.$\qquad\qquad\Box$

Corollary $\binom{2q}{q} = \Theta(2^{2q-(\log_2 q)/2})$.

A first pass upper bound is $\left(2^{2q-1}\right)^2 = 2^{4q-2}$, since $U$ and $V$ cannot overlap.

For a lower bound.  By the symmetry of the binomial expansion one can achieve
$$
\left(\sum_{i=0}^{q−1}\binom{p}{i}\right)^2
= \left(\left(2^{2q} - \binom{2q}{q}\right)/2\right)^2
= 2^{4q-2}\left(1-1/\left(\alpha\sqrt{\pi q}\right)\right)^2
$$
where $1 &lt; \alpha &lt; 1.136$ by the lemma.
This expression can be obtained by taking $U$ to be the set of $p$-bit Boolean vectors within Hamming distance $q−1$ from $0\dots 0$, and $V$ to be the vectors within distance $q−1$ from $1\dots 1$.
These sets both have the same size.
(Note that the number of $p$-bit Boolean vectors which have Hamming distance exactly $i$ from the all-zero vector is $\binom{p}{i}$.)

Now note that $\alpha\sqrt{\pi q}$ is smallest when $q = 1$, taking a value that exceeds $\sqrt{\pi}$.  Hence $\left(1 - 1/(\alpha\sqrt{\pi q})\right)^2 &gt; 0.1899$.
It follows that the quantity you are interested in is $\beta 2^{4q-2}$, where $0.1899 &lt; \beta &lt; 1$.

The case for $p$ odd seems a bit more involved, but the same idea might apply.  The "buffer zone" between $U$ and $V$ is now going to consist of vectors of two different Hamming weights instead of just one, so it has roughly double the impact.  This probably calls for a more careful analysis of the error, and the lower bound might leave a bit of slack.

Disclaimer: I wrote the above fairly quickly, so there may be some errors in the derivation.  Please check the details if you plan to use this elsewhere.  Such a natural question has probably also been studied in the coding theory literature.

Reference:


Herbert Robbins, A remark on Stirling's formula, The American Mathematical Monthly 62(1), 1955, 26–29.  doi:10.2307/2308012