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)

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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.

Improve this answer
$\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$
    – Jukka Kohonen
    Commented 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$
    – Aaron Meyerowitz
    Commented 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
    Commented 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$
    – Aaron Meyerowitz
    Commented Apr 1, 2021 at 5:51

You must log in to answer this question.

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