# Almost-parallel corners of the hypercube in high dimensions

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)

## 1 Answer

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.

• 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? – Jukka Kohonen Mar 31 at 5:18
• 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.. – Aaron Meyerowitz Mar 31 at 6:25
• 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! – DJA Mar 31 at 17:05
• 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. – Aaron Meyerowitz Apr 1 at 5:51