The following problem has come up in my work. Any help would be appreciated.
Problem. Given $N \in \mathbb{N}$, find vectors $u_1, u_2, \cdots, u_N, v_1, v_2, \cdots, v_N \in \mathbb{R}^d$ which satisfy $$\forall i,j \in \{1, 2, \cdots, N\} ~~~~~~~~~~ \langle u_i, v_j \rangle = \left\{ \begin{array}{cl} 1 & \text{if } i \leq j \\ 0 & \text{if } i > j \end{array} \right.$$ and which minimize $$A := \max_{i,j \in \{1, 2, \cdots, N\}} \|u_i\|_2 \cdot \|v_j\|_2.$$ Let $A_*(N)$ denote the optimal value of $A$ for a given value of $N$.
I'm mainly interested in the asymptotic behavior of $A_*(N)$ as $N \to \infty$. I don't care what $d$ is.
(EDIT: To be clear, $A_*(N)$ is defined to be the infimum -- taken over all $d \in \mathbb{N}$ and all $u_1, \cdots, u_N, v_1, \cdots, v_N \in \mathbb{R}^d$ satisfying the constraint -- of the objective $A$. That is, I place no constraint on $d$.
Note that $d$ must depend on $N$; in particular, $d \geq N$ is necessary for the constraint to be satisfiable.
However, without loss of generality, $d = 2N$: If $d<2N$, we can add superfluous dimensions. If $d>2N$, then we can project the solution to the space spanned by $\{u_1, \cdots, u_N, v_1, \cdots, v_N\}$, which has dimension at most $2N$.)
Question. What is $A_*(N)$? In particular, what is $$c_* := \limsup_{N \to \infty} \frac{\log A_*(N)}{\log \log N}~~~?$$
The value $c_*$ is what I really want to know, as it governs the asymptotics. i.e. $A_*(N) \approx (\log N)^{c_*}$.
I can prove $0 \leq c_* \leq 1$. Any improved bounds (such as showing $c_*>0$ or showing $c_*<1$) would be really helpful.
By Cauchy-Schwartz, $A_*(N) \geq \|u_1\|_2 \cdot \|v_1\|_2 \geq \langle u_1, v_1 \rangle = 1$ and, hence, $c_* \geq 0$, but I have no nontrivial lower bound.
The obvious upper bound is to let $u_1, \cdots, u_N$ be the standard basis vectors and then let $v_j = \sum_{i=1}^j u_i$. Unfortunately, this only shows $A_*(N)\leq\sqrt{N}$; we can do better:
The following inductive construction shows $A_*(N) \leq \lceil \log_2 N \rceil + 1$ and, hence, $c_* \leq 1$.
We will construct a solution for powers of $2$ i.e. $N=2^n$ with $n \in \mathbb{N}$. The solution we construct will be denoted $u_1^n, \cdots, u_{2^n}^n, v_1^n, \cdots, v_{2^n}^n \in \mathbb{R}^{2^{n+1}-1}$.
The base case is $u_1^0 = v_1^0 = (1)$. For $n \geq 1$ and $1 \leq i \leq 2^{n-1}$, define $$u_i^{n} = \left( \begin{array}{c} 1 \\ u_i^{n-1} \\ 0^{2^{n}-1} \end{array} \right), ~~~~~~~~ u_{2^{n-1}+i}^{n} = \left( \begin{array}{c} 0 \\ 0^{2^{n}-1} \\ u_i^{n-1} \end{array} \right), ~~~~~~~~ v_i^{n} = \left( \begin{array}{c} 0 \\ v_i^{n-1} \\ 0^{2^{n}-1} \end{array} \right), ~~~~~~~~ v_{2^{n-1}+i}^{n} = \left( \begin{array}{c} 1 \\ 0^{2^{n}-1} \\ v_i^{n-1} \end{array} \right),$$ where $0^m \in \mathbb{R}^m$ denotes the $m$-dimensional zero vector.
It is easy to verify inductively that this construction satisfies the constraint and achieves $\|u_i^n\|_2 \leq \sqrt{n+1}$ and $\|v_i^n\|_2 \leq \sqrt{n+1}$ for $1 \leq i \leq 2^n$, as required to show $A_*(2^n)\leq n+1$.
Clearly, $A_*$ is an increasing function. Hence $A_*(N) \leq A_*\left(2^{\lceil \log_2 N \rceil}\right) \leq \lceil \log_2 N \rceil +1$ for all $N \in \mathbb{N}$, as desired.
I will prove the lower bound $A_{\ast}(N) \geq \tfrac{1}{2 \pi} \log N$, within a constant factor of the OP's upper bound.
Let $A$ and $B$ be the matrices whose columns are $u_i$ and $v_i$. Let $S$ be the $N\times N$ matrix $$ \begin{pmatrix} 1&1&1&1&1 \\ 0&1&1&1&1 \\ 0&0&1&1&1 \\ 0&0&0&1&1 \\ 0&0&0&0&1 \end{pmatrix} .$$ So $S=A^T B$. Let the singular values of $A$, $B$ and $S$ be $\alpha_i$, $\beta_i$ and $\sigma_i$ respectively, with $\alpha_1 \geq \alpha_2 \geq \cdots \geq \alpha_n \geq 0$ and likewise for the $\beta$'s and $\sigma$'s. We adopt the convention that $\alpha_M=\beta_M=\sigma_M=0$ for $M>N$.
We have $$ \max |A_i|^2 \geq \frac{1}{N} \sum |A_i|^2 = \frac{1}{N} \mathrm{Tr}(A^T A) = \frac{1}{N} \sum \alpha_i^2 $$ and similarly $$\max |B_j|^2 \geq \frac{1}{N} \sum \beta_j^2 . $$
So $$\max |A_i| |B_j| \geq \frac{1}{N} \left( \sum \alpha_i^2 \right)^{1/2} \left( \sum \beta_j^2 \right)^{1/2} \geq \frac{1}{N} \sum \alpha_i \beta_i$$ where the second inequality is Cauchy-Schwartz.
Now, the multiplicative version of Weyl's inequality says that $\alpha_i \beta_i \geq \sigma_{2i-1}$. I'm having trouble finding a reference for Weyl's inequality for singular values (as opposed to eigenvalues), especially with nonsquare matrices, so I may come back and write up the proof if you don't know/believe it. So $$\max |A_i| |B_j| \geq \frac{1}{N} \sum_{j \geq 1}^{\lfloor (N+1)/2 \rfloor} \sigma_{2j-1}.$$
Now, here is the amazing fact -- we can actually compute the singular values of $S$ explicitly!
Lemma The singular values of $S$ are $$ \sigma_k = \frac{1}{2 \sin \tfrac{(2k-1) \pi}{4N+2}}. $$
Proof: We note that $$ S^{-1} = \begin{pmatrix} 1&-1&0&0&0 \\ 0&1&-1&0&0 \\ 0&0&1&-1&0 \\ 0&0&0&1&-1 \\ 0&0&0&0&1 \end{pmatrix} $$ has singular values $\sigma_k^{-1}$ and $$C:=S^{-T} S^{-1} = \begin{pmatrix} 1&-1&0&0&0 \\ -1&2&-1&0&0 \\ 0&-1&2&-1&0 \\ 0&0&-1&2&-1 \\ 0&0&0&-1&2 \end{pmatrix}$$ has eigenvalues $\sigma_k^{-2}$, so it suffices to show that the eigenvalues of $C$ are $4 \sin^2 \tfrac{(2k-1) \pi}{4N+2} = 2-2 \cos \tfrac{(2k-1) \pi}{2N+1}$. Writing $\phi_N(\lambda)$ for the characteristic polynomial of $C$, we have $$ \phi_N(\lambda) = (\lambda-2) \phi_{N-1}(\lambda) - \phi_{N-2}(\lambda) $$ which is the appropriately shifted version of the recursion for Chebyshev polynomials. $\square$
So, we have $$\max |A_i| |B_j| \geq \frac{1}{N} \sum_{j=1}^{\lfloor (N+1)/2 \rfloor} \frac{1}{2 \sin \tfrac{(4j-3) \pi}{4N+2}}.$$ Bounding $\sin x < x$, this is $$ \geq \frac{4N+2}{2 \pi N} \sum_{j=1}^{\lfloor (N+1)/2 \rfloor} \frac{1}{4j-3} > \frac{1}{2\pi} \sum_{j=1}^{\lfloor (N+1)/2 \rfloor} \frac{2}{2j-3/2}.$$ We can view the last sum as a Riemann sum for $\int_{x=1}^N \tfrac{dx}{x}$, over rectangles of width $2$. I didn't write down the proof of this carefully, but the Riemman sums appear greater than the integral, and in any case are only off by $O(1)$, so we finally conclude $$\max |A_i| |B_j| > \frac{1}{2 \pi} \log N$$ as promised.