1
$\begingroup$

Say I would like a collection of k "almost-parallel" boolean vectors $X_1,...,X_k \in \{\pm 1\}^n$, such that $(X_i,X_j)/n \approx 1-\epsilon$ for some small $\epsilon$. How many ways are there to pick such a collection? Or even how large of $k$ until this is impossible? Has this been studied before? (Seems related to coding theory)

In particular, the scaling I am interested in is: $k = k(n) \to \infty$ and $\epsilon = k/n$. The growth of $k$ is essential; the other condition less so. By "$\approx$", say I mean up to a tolerance of order $1/n$, if it matters.

(Note that this question is quite different from the common question about packing many almost orthogonal vectors in high dimensions)

$\endgroup$

1 Answer 1

2
$\begingroup$

This is mainly an attempt to clarify the question. Let $t=\epsilon n$, then you want each pair $X_i,X_j$ to differ in $t$ places with a tolerance of $1$. So , for $t \in \mathbb{N},$ a length $n$ binary code with $k$ codewords where every pair has one of three distances $t-1,t$ or $t+1.$ Otherwise two distances $\lfloor t \rfloor$ and $\lceil t \rceil.$ In addition, you clarify that the case of interest to you is $t=k.$ So, specializing to $\epsilon=0.01,$ you want $X_1,...,X_k \in \{\pm 1\}^{100k}$, each pair differing in $k$ places (with a tolerance of $1$). That seems easily obtained, and nothing changes for other small $\epsilon$, so I must be missing something.

$\endgroup$
4
  • 1
    $\begingroup$ It seems easy to obtain such a collection of $k$ vectors, but the question is asking "how many ways are there to pick such a collection?" Is this counting thing the key part here? $\endgroup$ Mar 31, 2021 at 5:18
  • $\begingroup$ What would count as different? It seems likely that the vectors would be identical on a set of at least $(1-2\epsilon)n$ positions. Just picking which those are would be a huge number.. $\endgroup$ Mar 31, 2021 at 6:25
  • $\begingroup$ The counting is the key part. I agree that (unless there are some algebraic constraints that make this task impossible, which seems unlikely) there will be a huge number of such collections. I am trying to understand whether the number grows like $2^{n +k^2}$ or $2^{n+k}$. Also, thanks for the replies! $\endgroup$
    – DJA
    Mar 31, 2021 at 17:05
  • $\begingroup$ Depending on what you count as different, it might grow like $n^{\epsilon n}$ or faster. So $2^{cn \log n} $ which outstrips what you mentioned. You can get a factor of $2^n$ just by flipping signs. Now you could squash all this by saying “up to permutations of positions, sign flips and order of the $X_i$” But the question is wildly under specified. $\endgroup$ Apr 1, 2021 at 5:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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