Maximize function on orthogonal matrices

Consider the function $f$ from the set of $n \times n$ real matrices taking $A=(a_{ij})$ to $f(A):= \prod_{(i,j) \neq (k,l)}(a_{ij}-a_{kl}) $.

Edit: Note that $f(A) \ge 0$ for all $A$, since grouping pairs we have $$f(A):=(-1)^{\frac{n^2(n^2-1)}{2}}\prod_{(i,j) \lt_ {lex} (k,l)}(a_{ij}-a_{kl})^2$$ and $ n^2(n^2-1) \equiv 0 \, \text{mod} \, 4$ for all $n$, end edit.

Is there a way to compute $M:=\text{max}\{ f(A) : A A^{t}=I \}$ ?. I know that, since $A$ orhogonal implies $\mid a_{ij} \mid \leq 1$ for all $ 1\leq i,j \leq n $, we have that $2^{2 {n^2 \choose 2}}=2^{n^2(n^2-1)}$ is a trivial upper bound on M, but for example if $n=2$ we have that actually $M=0$ because every $2 \times 2$ orthogonal matrix has at least two equal entries.

So if we can't compute $M$ can we at least give a better upper bound?.

Following your advice. I estimated $M$ using random orthogonal matrices for $n \le 6$. Here are the results I've got:

\begin{array}{|c|c|c|c|} \hline n & \text{# of orth. Matrices} & \text{Estimated} \, M \\ \hline 2 & \infty & 0 \\ \hline 3 & 5\times 10^4 & 1.13762 \times 10^{-17} \\ \hline 4 & 5\times 10^4 & 3.10228 \times 10^{-80} \\ \hline 5 & 1 \times 10^3 & 5.71162 \times 10^{-248} \\ \hline 6 & 1\times 10^3 & 2.80541 \times 10^{-588}\\ \hline. \end{array}

for example this is what the graphic for $n=3$ looks like:

So it seems that $M$ is much more smaller than the trivial bound. Does anyone has an idea of how to construct a formal proof?. I'll be offering a bounty as soon as is allowed.

Solution 1:

There is a bound like $e^{-\frac{n^4}{2}\ln n}$ by elementary means (AM-GM) by exploiting the orthogonality, but it's still far from the numerical results you have (and somewhat worse than the computation with Legendre polynomials, although it should be better in the long run according to Dap's comment).

By AM-GM $$f(A)^{\frac{1}{\binom{n^2}{2}}}\le \frac{\sum_{(i,j)<(k,l)}(a_{ij}-a_{kl})^2}{\binom{n^2}{2}}=\frac{(n^2-1)\sum_{(i,j)} a_{ij}^2-2\sum_{(i,j)<(k,l)}a_{ij}a_{kl}}{\binom{n^2}{2}}.$$ Now $\sum a_{ij}^2=|A|^2=n$. As for the second term $$2\sum_{(i,j)<(k,l)} a_{ij}a_{kl}= \Big(\underbrace{\sum_{(i,j)} a_{ij}}_{S(A)}\Big)^2 -\sum_{(i,j)} a_{ij}^2$$ and therefore $$f(A)^{\frac{1}{\binom{n^2}{2}}}\le \frac{n^3-S(A)}{\binom{n^2}{2}}.$$ From e.g. this question we have that for an orthogonal matrix $A$ $$|S(A)|=\left|\sum a_{ij}\right|\le n\qquad (*)$$ and thus $$f(A)^{\frac{1}{\binom{n^2}{2}}}\le \frac{n^3+n}{\binom{n^2}{2}}=\frac{2(n^2+1)}{n(n^2-1)}\approx \frac{2}{n}.$$ Taking the logarithm $$\ln(f(A))\le \binom{n^2}{2} \ln\left(\frac{2(n^2+1)}{n(n^2-1)}\right)\approx -\frac12 n^4\ln n. $$ For instance for $n=5$ we obtain $1.11\times 10^{-109}$ and for $n=6$ we obtain $4.14\times 10^{-286}$.

$(*)$ This is obtained by applying Cauchy-Schwartz in a slick way and is slightly better than applying it in the more obvious way, which gives $n^{3/2}$. This is not really relevant in the asymptotics above though.