<p>Consider $p=2q$, $q\ge 1$.</p>

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

<p>First, let's prove a lemma of general interest.</p>

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

<p><em>Proof:</em> 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$</p>

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

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

<p>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}$.)</p>

<p>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$.</p>

<p>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.</p>

<p><em>Disclaimer:</em> 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.</p>

<p><strong>Reference:</strong></p>

<ul>
<li>Herbert Robbins, <em>A remark on Stirling's formula</em>, The American Mathematical Monthly <strong>62</strong>(1), 1955, 26–29.  doi:<a href="http://dx.doi.org/10.2307/2308012" rel="nofollow">10.2307/2308012</a></li>
</ul>

CC BY-SA 3.0
2013-06-18T22:49:59.283Z
I wrote a comment to @sdcvvc under the question. Thank you for all the
details. What is the result that lets you determine the two sets of
boolean vectors. Could you suggest something to read on the web ?
Sorry for sounding naive.
babou
CC BY-SA 3.0
2013-06-18T23:00:13.610Z
It is simple enumeration: the number of vectors that have precisely $k$ 1's and $n-k$ 0's is $\binom{n}{k}$, and this is also the number of vectors that have Hamming distance exactly $k$ from the all-zero vector.
András Salamon
CC BY-SA 3.0
2013-06-18T23:53:09.857Z
I understand that. But what makes you choose these 2 sets of vectors for obtaining the largest product. It does make intuitive sense, but I would not be able to pull a formal argument.
babou
CC BY-SA 3.0
2013-06-19T08:23:54.823Z
For a lower bound, you just want _any_ set of 2 vectors.  I just picked ones that are easy to analyze, and fulfil the criterion of starting as far away from each other as possible.  It turns out this is actually asymptotically optimal (and may even be optimal, I don't know).
András Salamon
CC BY-SA 3.0
2013-06-19T09:20:51.420Z
I did not realize you were also looking at that CF problem (I forget names).  My
question comes from an attempt at using the interchange lemma. But I
just learned of it and my attempt is too simple minded (no intuition) and
inconclusive. I half expected it.  It may well have been tautological,
and thus inconclusive. Or possibly the definition of the language
mimics too closely the structure of the interchange lemma - at least
with the conditions I chose so far.
babou
CC BY-SA 3.0
2013-06-18T21:03:30.283Z
2013-06-18T23:03:25.970Z
2013-06-18T23:03:25.970Z
András Salamon
<p>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$.</p>

<p>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$.</p>

<p>To make it hopefully more precise :<br>
$$\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\}.$$</p>

CC BY-SA 3.0
2013-06-18T16:56:45.440Z
Which way round are your quantifiers?  For $p = 2q$, $q \ge 1$ one can achieve $(\sum_{i=0}^{q-1} \binom{p}{i})^2$, by taking $U$ to be the $p$-bit Boolean vectors within Hamming distance at most $q-1$ from $0\dots 0$, and $V$ to be the vectors within distance $q-1$ from $1\dots 1$.  This is $((2^{2q} - \binom{2q}{q})/2)^2$.
András Salamon
CC BY-SA 3.0
2013-06-18T17:57:40.090Z
There seems to be an extra universal quantifier in the last line over U and V.
Kaveh
CC BY-SA 3.0
2013-06-18T18:01:30.913Z
Btw, I think it would be more readable to write it as $\max\{ |U\times V| \mid U,V\subseteq \{0,1\}^p, 2\leq d(U,V)\}$ where $d(U,V)$ is $\min_{u\in U, v\in V} d_H(u,v)$.
Kaveh
CC BY-SA 3.0
2013-06-18T18:06:16.793Z
@AndrásSalamon I am not sure which quantifiers you talk about. Is it clearer now.
Essentially I want to know how big the product can get for two string
sets meeting the condition.  If you can give me some hints on how you
reason and compute it, I would love it ...  I have not played these
games for a very long time. I think I can probably do without the odd
case, $p=2q+1$ (it is probably less than for $p=2q+2$ if needed).
But I have to look at other variations.
babou
CC BY-SA 3.0
2013-06-18T18:10:22.027Z
@Kaveh Sure ... I was trying to answer quickly, and I was not sure what the problem was.
babou
CC BY-SA 3.0
2013-06-18T21:14:39.860Z
It is trivial to show $2^{2p-4} \leq \max\{|U \times V|:d(U,V)>1\} \leq 2^{2p}$. Do you want something more precise than that?
sdcvvc
CC BY-SA 3.0
2013-06-18T21:48:21.390Z
@sdcvvc Thank you. I can feel it is probably not too hard, but whatever knowledge I had in this is pretty much gone. I need that for a proof I am writing. It seems however that I have a lot of slack with the bounds, which may mean that there are simpler ways to achieve the result. I would like to understand so that I can analyse other cases  ... else il will leave the proof for someone else to finish. It may be on stackexchange and is about CF languages.
babou
CC BY-SA 3.0
2013-06-18T23:14:31.960Z
@babou: http://cs.stackexchange.com/questions/11585/is-this-strange-language-context-free? I doubt cardinality estimates will help you there. Anyway, you can obtain the trivial estimates I mentioned when $U$, $V$ are sets of strings beginning with 00 and 11, respectively.
sdcvvc
CC BY-SA 3.0
2013-06-19T00:55:46.960Z
Yes, that problem. But you are correct, it does not seem to be
helping. Why did you think it would not? It is very possible that my
attempt is too simple minded. I was aware of that, but I was mainly
trying to get a feeling for the interchange lemma.
babou
CC BY-SA 3.0
2013-06-19T14:30:23.160Z
@babou - I don't feel that looking into cardinality gives any insight into the structure of the problem. There should be CFLs and non-CFLs whose associated cardinalities have similar behavior to this language.
sdcvvc
<co.combinatorics><coding-theory><upper-bounds>
Upperbound on cardinality of product of two string sets at pairwise Hamming distance $> 1$
babou
# Upperbound on cardinality of product of two string sets at pairwise Hamming distance $> 1$

(Asked by: username_0 on 2013-06-18)

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\}.$$

**Tags:** co.combinatorics, coding-theory, upper-bounds
> **Comments:**
> **username_1**: Which way round are your quantifiers?  For $p = 2q$, $q \ge 1$ one can achieve $(\sum_{i=0}^{q-1} \binom{p}{i})^2$, by taking $U$ to be the $p$-bit Boolean vectors within Hamming distance at most $q-1$ from $0\dots 0$, and $V$ to be the vectors within distance $q-1$ from $1\dots 1$.  This is $((2^{2q} - \binom{2q}{q})/2)^2$.  
> **username_2**: There seems to be an extra universal quantifier in the last line over U and V.  
> **username_2**: Btw, I think it would be more readable to write it as $\max\{ |U\times V| \mid U,V\subseteq \{0,1\}^p, 2\leq d(U,V)\}$ where $d(U,V)$ is $\min_{u\in U, v\in V} d_H(u,v)$.  
> **username_0**: @AndrásSalamon I am not sure which quantifiers you talk about. Is it clearer now. Essentially I want to know how big the product can get for two string sets meeting the condition.  If you can give me some hints on how you reason and compute it, I would love it ...  I have not played these games for a very long time. I think I can probably do without the odd case, $p=2q+1$ (it is probably less than for $p=2q+2$ if needed). But I have to look at other variations.  
> **username_0**: @Kaveh Sure ... I was trying to answer quickly, and I was not sure what the problem was.  
> **username_3**: It is trivial to show $2^{2p-4} \leq \max\{|U \times V|:d(U,V)>1\} \leq 2^{2p}$. Do you want something more precise than that?  
> **username_0**: @sdcvvc Thank you. I can feel it is probably not too hard, but whatever knowledge I had in this is pretty much gone. I need that for a proof I am writing. It seems however that I have a lot of slack with the bounds, which may mean that there are simpler ways to achieve the result. I would like to understand so that I can analyse other cases  ... else il will leave the proof for someone else to finish. It may be on stackexchange and is about CF languages.  
> **username_3**: @babou: http://cs.stackexchange.com/questions/11585/is-this-strange-language-context-free? I doubt cardinality estimates will help you there. Anyway, you can obtain the trivial estimates I mentioned when $U$, $V$ are sets of strings beginning with 00 and 11, respectively.  
> **username_0**: Yes, that problem. But you are correct, it does not seem to be helping. Why did you think it would not? It is very possible that my attempt is too simple minded. I was aware of that, but I was mainly trying to get a feeling for the interchange lemma.  
> **username_3**: @babou - I don't feel that looking into cardinality gives any insight into the structure of the problem. There should be CFLs and non-CFLs whose associated cardinalities have similar behavior to this language.  

---

## 1 answers

### Answer by username_1 on 2013-06-18. Score: 3 | Accepted answer

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 < \binom{2q}{q} < 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) < r\_n < 1/(12n)$.
This gives
$$
\binom{2q}{q} = 2^{2q}e^{r\_{2q}}/\sqrt{\pi q}e^{2r\_q} >
\left(2^{2q}/\sqrt{\pi q}\right)/c
$$
where $c = e^{(18q + 1)/(6q(24q+1))} < e^{19/150} < 1.136$.
Further,
$$
\binom{2q}{q} < \left(2^{2q}/\sqrt{\pi q}\right)/d
$$
where $d = e^{(36q - 1)/(24q(12q+1))} > 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 < \alpha < 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 > 0.1899$.
It follows that the quantity you are interested in is $\beta 2^{4q-2}$, where $0.1899 < \beta < 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](http://dx.doi.org/10.2307/2308012)

> **Comments:**
> **username_0**: I wrote a comment to @sdcvvc under the question. Thank you for all the details. What is the result that lets you determine the two sets of boolean vectors. Could you suggest something to read on the web ? Sorry for sounding naive.  
> **username_1**: It is simple enumeration: the number of vectors that have precisely $k$ 1's and $n-k$ 0's is $\binom{n}{k}$, and this is also the number of vectors that have Hamming distance exactly $k$ from the all-zero vector.  
> **username_0**: I understand that. But what makes you choose these 2 sets of vectors for obtaining the largest product. It does make intuitive sense, but I would not be able to pull a formal argument.  
> **username_1**: For a lower bound, you just want _any_ set of 2 vectors.  I just picked ones that are easy to analyze, and fulfil the criterion of starting as far away from each other as possible.  It turns out this is actually asymptotically optimal (and may even be optimal, I don't know).  
> **username_0**: I did not realize you were also looking at that CF problem (I forget names).  My question comes from an attempt at using the interchange lemma. But I just learned of it and my attempt is too simple minded (no intuition) and inconclusive. I half expected it.  It may well have been tautological, and thus inconclusive. Or possibly the definition of the language mimics too closely the structure of the interchange lemma - at least with the conditions I chose so far.  

---

