Consider the vector space $\mathbb{R}^n$, the standard inner product $\langle \cdot,\cdot \rangle:\mathbb{R}^n\times\mathbb{R}^n\rightarrow \mathbb{R}$, and some $0<\epsilon\leq \frac{1}{\sqrt{n}}$. Is it possible to generate a set of $M$ vectors, say $\mathcal{S}$, in a deterministic fashion (not random), such that the vectors in $\mathcal{S}$ satisfy the following properties:


* all the entries of the vectors come from $\{\frac{-1}{\sqrt{n}},\frac{1}{\sqrt{n}}\}$, so that $||\mathbb{x}||\_2=1\,\,\forall \mathbb{x}\in\mathcal{S}$,
* $\mathbb{x},\mathbb{y}\in\mathcal{S}\Rightarrow|\langle \mathbb{x},\mathbb{y} \rangle| <\epsilon$, i.e., the vectors in $\mathcal{S}$ are almost orthogonal to each other.


Kindly note that a similar question was asked before ([Almost orthogonal vectors in subsets of euclidean space](https://mathoverflow.net/q/131554/26701)), but it asked for an upper bound on $M$ for given $n,\epsilon$ - the answer was $M\leq \frac{n(1-\epsilon^2)}{1-n\epsilon^2}$. I am interested in knowing if there is a deterministic way of constructing $\mathcal{S}$ of reasonable size.


Let me also explain an approach that I thought of (but got stuck) - consider $\mathcal{C}=[n, k, d]\_{2}$, a binary linear code with $\frac{n}{2}(1-\epsilon)\leq d <\frac{n}{2}(1+\epsilon)$, and map its codewords (of length $n$) to real-valued sequences in $\{\frac{-1}{\sqrt{n}},\frac{1}{\sqrt{n}}\}^n$ such that $0$ maps to $\frac{-1}{\sqrt{n}}$ and $1$ maps to $\frac{1}{\sqrt{n}}$. Then consider the set of real-valued sequences, say $\mathcal{T}$, corresponding to the subset of codewords in $\mathcal{C}$ whose Hamming weight is at least $d$ and at most $\frac{n}{2}(1+\epsilon)$. Then one can show that $\mathcal{T}$ is a candidate for $\mathcal{S}$; however I have not been able to design a linear code for which tight upper and lower bounds on $|\mathcal{T}|$ can be obtained (i.e., I don't have bounds/expression for $M$ in terms of $n,\epsilon$). 



Designing almost orthogonal vectors in a deterministic manner
In [1] a collection of $M$ binary vectors over $\{\pm 1\}^n$ is constructed such that:


$n=2^m-1$, $M=n(n+2) \approx n^2$ and their unnormalized inner products satisfy 


$|<v\_i,v\_j>|\leq 1+\sqrt{2(n+1)}$ 


whenever $i\neq j$ by taking the finite field $GF(2^m),$
letting $a$ be a primitive element in $GF(2^m)$ and defining the collection of vectors


$((-1)^{tr(a^t)})\_{t=0}^{2^m-1}$, $((-1)^{tr(a^{dt})})\_{t=0}^{2^m-1}$ and


$((-1)^{tr(a^{t+s}+a^{dt})})\_{t=0}^{2^m-1}$, for $s=0,1,\ldots,2^m-2.$ 


and all their cyclic shifts as $\{v\_i\}$ , provided $\gcd(d,2^n-1)=1$. Normalizing, as you require, by letting $x\_i=v\_i/\sqrt{n}$ yields


$|<x\_i,x\_j>|\leq (1+\sqrt{2(n+1)})/n={\cal O}(n^{-1/2})$
Since the construction exists for all $n\_m=2^m-1,$ $m\geq 2$ you can achieve any $\epsilon>0$ for $n$ large enough.


There has been more constructions since 1992, and the best ones have $M\approx n^{1+k}$ sequences ($n^k$ sequences and their cyclic shifts), and $|<x\_i,x\_j>|\leq 1+ k \sqrt{n+1}$. 


Intriguingly, over $C^n$, it is possible to construct a family with the same parameters as in [1], by using Galois Rings instead of Galois fields, and alphabet $\{\pm 1, \pm i\}$ where $i^2=-1$ but where the bound is now 


$|<v\_i,v\_j>|\leq 1+\sqrt{(n+1)}$


and that $\sqrt{2}$ magnitude difference is in practice very useful for CDMA communication systems since it reduces interference in wireless communications [2].


1. Gold, R. (October 1967). "Optimal binary sequences for spread spectrum multiplexing (Corresp.)". IEEE Transactions on Information Theory 13 (4): 619–621.
2. Boztas, S., Hammons, A.R., Kumar, P.V., "4-phase sequences with near-optimum correlation properties", Information Theory, IEEE Transactions on Information Theory 38 (3):1101-1113, 1992.


