3
$\begingroup$

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

$\endgroup$
10
  • 3
    $\begingroup$ 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$. $\endgroup$ – András Salamon Jun 18 '13 at 16:56
  • $\begingroup$ There seems to be an extra universal quantifier in the last line over U and V. $\endgroup$ – Kaveh Jun 18 '13 at 17:57
  • 3
    $\begingroup$ 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? $\endgroup$ – sdcvvc Jun 18 '13 at 21:14
  • 1
    $\begingroup$ @babou: cs.stackexchange.com/questions/11585/…? 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. $\endgroup$ – sdcvvc Jun 18 '13 at 23:14
  • 2
    $\begingroup$ @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. $\endgroup$ – sdcvvc Jun 19 '13 at 14:30
3
$\begingroup$

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
$\endgroup$
5
  • $\begingroup$ 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. $\endgroup$ – babou Jun 18 '13 at 22:49
  • $\begingroup$ 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. $\endgroup$ – András Salamon Jun 18 '13 at 23:00
  • $\begingroup$ 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. $\endgroup$ – babou Jun 18 '13 at 23:53
  • $\begingroup$ 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). $\endgroup$ – András Salamon Jun 19 '13 at 8:23
  • $\begingroup$ 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. $\endgroup$ – babou Jun 19 '13 at 9:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.