# Probabilistic bounds on best rank-one approximation ratio

Khazhgali Kozhasov, Josué Tonelli-Cueto

<figure><img src="image_1.png" /></figure>

To cite this version:

Khazhgali Kozhasov, Josué Tonelli-Cueto. Probabilistic bounds on best rank-one approximation ratio. Linear and Multilinear Algebra, 2024, pp.1-29. 10.1080/03081087.2024.2304146. hal-03517267

HAL Id: hal-03517267

https://inria.hal.science/hal-03517267

Submitted on 7 Jan 2022

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Probabilistic bounds on best rank-one approximation ratio

Khazhgali Kozhasov
Institut für Mathematik
Universität Osnabrück
Osnabrück, GERMANY
khazhgali.kozhasov@uni-osnabrueck.de

Josué Tonelli-Cueto*
Inria Paris & IMJ-PRG
Sorbonne Université
Paris, FRANCE
josue.tonelli.cueto@bizkaia.eu

Abstract

We provide new upper and lower bounds on the minimum possible ratio of the spectral and Frobenius norms of a (partially) symmetric tensor. In the particular case of general tensors our result recovers a known upper bound. For symmetric tensors our upper bound unveils that the ratio of norms has the same order of magnitude as the trivial lower bound $1/\sqrt{n^{d-1}}$, when the order of a tensor $d$ is fixed and the dimension of the underlying vector space $n$ tends to infinity. However, when $n$ is fixed and $d$ tends to infinity, our lower bound is better than $1/\sqrt{n^{d-1}}$.

# 1 Introduction

Representation of data sets in compact and simple formats is an important problem of data science with numerous applications. Vectors, matrices and, more generally, tensors are used to naturally model data points. It is often necessary to retain only some key properties of a data set, that corresponds to an approximation of a tensor by another one with a simpler structure. There are several different models, based on tensor decompositions, that are used for this purpose, see [13, 9] and references therein. An important special case is an approximation of a given “data”-tensor with a *rank-one tensor*, see [8].

For $K = \mathbb{R}$ or $K = \mathbb{C}$ let $K^n = K^{n_1} \otimes \cdots \otimes K^{n_d}$ denote the $K$-vector space of $n$-tensors with $n = (n_1, \dots, n_d)$. A natural way to measure distance between tensors is given by the norm associated to the *Frobenius (also known as Hilbert-Schmidt) product*, which is defined by the formula

$$ \langle T, T' \rangle := \sum_{i_j=1}^{n_j} \overline{t_{i_1 \dots i_d} t'_{i_1 \dots i_d}}, \quad T = (t_{i_1 \dots i_d}), \quad T' = (t'_{i_1 \dots i_d}). \qquad (1.1) $$

A tensor $T = (t_{i_1 \dots i_d})$ is said to be of *rank one*, if there exist unit vectors $x^j \in \mathbb{S}(K^{n_j})$ and a scalar $\lambda \in K$ such that $t_{i_1 \dots i_d} = \lambda x_{i_1}^1 \dots x_{i_d}^d$. In this case we write $T = \lambda x^1 \otimes \cdots \otimes x^d$. The problem of best rank-one approximation of a tensor $T$ consists in finding a closest rank-one tensor to $T$, i.e.,

$$ \min_{\lambda \in K, x^j \in \mathbb{S}(K^{n_j})} \|T - \lambda x^1 \otimes \cdots \otimes x^d\|, \qquad (1.2) $$

<footnote>*Supported by a postdoctoral fellowship of the 2020 “Interaction” program of the Fondation Sciences Mathématiques de Paris. Partially supported by the ANR JCJC GALOP (ANR-17-CE40-0009), the PGMO grant ALMA, and the PHC GRAPE.</footnote>
where $\| \cdot \| := \sqrt{\langle \cdot, \cdot \rangle}$ is the Frobenius norm of a tensor. This problem is essentially equivalent (see (1.4)) to computing the spectral norm of $T$,

$$ \|T\|_{\infty} := \max_{\mathbf{x}^j \in S(\mathbb{K}^{n_j})} |\langle T, \mathbf{x}^1 \otimes \cdots \otimes \mathbf{x}^d \rangle|, \quad (1.3) $$

and is known to be NP-hard [10, Thm. 1.13]. If $\lambda \mathbf{x}^1 \otimes \cdots \otimes \mathbf{x}^d$ is a best rank-one approximation of $T$, then (the square of) the relative best rank-one approximation error equals (see, e.g., [19, Thm. 2.19])

$$ \frac{\|T - \lambda \mathbf{x}^1 \otimes \cdots \otimes \mathbf{x}^d\|^2}{\|T\|^2} = 1 - \frac{\|T\|_{\infty}^2}{\|T\|^2}. \quad (1.4) $$

The smallest possible ratio of the spectral and the Frobenius norms

$$ \mathcal{A}(\mathbb{K}^{\mathbf{n}}) := \min_{T \in \mathbb{K}^{\mathbf{n}}} \frac{\|T\|_{\infty}}{\|T\|} \quad (1.5) $$

is known as the best rank-one approximation ratio of the space $\mathbb{K}^n$ (see [18] and also [15]). Computing $\mathcal{A}(\mathbb{K}^n)$ is equivalent to finding the largest (worst) relative best rank-one approximation error (1.4). Note also that $0 < \mathcal{A}(\mathbb{K}^n) \le 1$ and $\mathcal{A}(\mathbb{K}^n)$ is just the largest constant $c > 0$ so that $\|T\|_{\infty} \ge c\|T\|$ holds for all $T \in \mathbb{K}^n$. The number (1.5) is an attribute of a tensor space and thus depends only on the underground field $\mathbb{K}$ and dimensions $n_1, \dots, n_d$. On the application side, the best rank-one approximation ratio governs the convergence rate of greedy rank-one update algorithms, see [18, 23].

A tensor $T = (t_{i_1 \dots i_d})$ of format $(n, \dots, n)$ is called symmetric, if $t_{i_{\sigma_1} \dots i_{\sigma_d}} = t_{i_1 \dots i_d}$ holds for any permutation on $d$ elements $\sigma$. A best rank-one approximation to a symmetric tensor $T$ can be chosen among symmetric rank-one tensors $\lambda \mathbf{x} \otimes \cdots \otimes \mathbf{x}$, see [2]. The best rank-one approximation ratio of the space $\text{Sym}^d(\mathbb{K}^n)$ of symmetric tensors is defined as

$$ \mathcal{A}(\text{Sym}^d(\mathbb{K}^n)) := \min_{T \in \text{Sym}^d(\mathbb{K}^n)} \frac{\|T\|_{\infty}}{\|T\|} \quad (1.6) $$

Computing $\mathcal{A}(\text{Sym}^d(\mathbb{K}^n))$ is equivalent to finding the largest (worst) relative best rank-one approximation error (1.4) among symmetric tensors in $\text{Sym}^d(\mathbb{K}^n)$. Also, by definition, one has $1 \ge \mathcal{A}(\text{Sym}^d(\mathbb{K}^n)) \ge \mathcal{A}(\mathbb{K}^n) \ge 0$ for $\mathbf{n} = (n, \dots, n)$.

Finding explicit values for (1.5) and (1.6) is a beautiful mathematical problem with interesting connections to composition algebras [16] and Chebyshev polynomials [1]. The exact value of $\mathcal{A}(\mathbb{K}^n)$ and of $\mathcal{A}(\text{Sym}^d(\mathbb{K}^n))$ remains unknown for most $\mathbf{n} = (n_1, \dots, n_d)$, $d$ and $n$. One has a naive lower bound

$$ \mathcal{A}(\mathbb{K}^{\mathbf{n}}) \ge \frac{1}{\sqrt{\min_{j=1,\dots,d} \prod_{i \ne j} n_i}}, \quad (1.7) $$

see, e.g., [16]. The equality holds only if so called orthogonal ($\mathbb{K} = \mathbb{R}$) or, respectively, unitary ($\mathbb{K} = \mathbb{C}$) tensors exist in the tensor space $\mathbb{K}^n$ (see [16]). For example, if $\mathbb{K} = \mathbb{R}$ and for $\mathbf{n} = (n, \dots, n)$ this happens only if $n = 1, 2, 4$ or $8$, which are dimensions of the four composition $\mathbb{R}$-algebras. It is known that (at least for $\mathbb{K} = \mathbb{R}$) the trivial bound (1.7) gives the correct order of magnitude when $d$ is fixed. Specifically, using probabilistic estimates of the uniform norm of random tensors from [22], the authors of [16] prove that the right inequality in
$$ \frac{1}{\sqrt{\min_{j=1,...,d} \prod_{i \neq j} n_i}} \leq \mathcal{A}(\mathbb{R}^n) \leq \frac{\|T\|_{\infty}}{\|T\|} \leq \frac{C \sqrt{d \ln d}}{\sqrt{\min_{j=1,...,d} \prod_{i \neq j} n_i}} $$

holds with positive probability in $T$, where $C$ is some constant and the entries of $T$ are independent standard Gaussians. With similar techniques it was proven earlier [4] that

$$ \frac{1}{n} \leq \mathcal{A}(\mathbb{C}^n \otimes \mathbb{C}^n \otimes \mathbb{C}^n) \leq \frac{3\sqrt{\pi}}{n} $$

In this work we reprove these probabilistic upper bounds giving explicit values for the constant $C$ and extend them to real and complex tensors of arbitrary format as well as to their (partially) symmetric counterparts. For the space of real symmetric tensors we give an alternative upper bound, by looking at random harmonic forms. Furthermore, using an integral representation (4.1) of the Frobenius norm of a symmetric tensor, we provide lower bounds on $\mathcal{A}(\text{Sym}^d(\mathbb{K}^n))$, which are (when $d$ is sufficiently large compared to $n$) better than the naive bound $\mathcal{A}(\text{Sym}^d(\mathbb{K}^n)) \geq 1/\sqrt{n^{d-1}}$.

We summarize our main results in the following two theorems. The first one concerns the general case and the second one the symmetric case.

**Theorem 1.1.** For any $d \geq 3$ and $n = (n_1, ..., n_d)$ with $n_1, ..., n_d \geq 2$ we have

$$ \frac{1}{\sqrt{\min_j \prod_{i \neq j} n_j}} \leq \mathcal{A}(\mathbb{K}^n) \leq \frac{32\sqrt{d \ln d}}{\sqrt{\min_j \prod_{i \neq j} n_j}}. \quad (1.8) $$

**Theorem 1.2.** For any $d \geq 3$ and $n \geq 2$ we have

$$ \begin{aligned} \max \left\{ \frac{1}{\sqrt{2^d}} \binom{d+n-1}{n-1}^{-1/2}, \frac{1}{\sqrt{n^{d-1}}} \right\} &\leq \mathcal{A}(\text{Sym}^d(\mathbb{R}^n)) \leq 24 \frac{\sqrt{d! \ln d \Gamma(\frac{n}{2}) n}}{\sqrt{2^d \Gamma(d+\frac{n}{2})}}, \\ \max \left\{ \binom{d+n-1}{n-1}^{-1/2}, \frac{1}{\sqrt{n^{d-1}}} \right\} &\leq \mathcal{A}(\text{Sym}^d(\mathbb{C}^n)) \leq \frac{36 \sqrt{n \ln d}}{\sqrt{\binom{n+d-1}{d}}}. \end{aligned} \quad (1.9) $$

In particular, we have that

$$ \frac{1}{\sqrt{n^{d-1}}} \leq \mathcal{A}(\text{Sym}^d(\mathbb{K}^n)) \leq 36 \sqrt{\frac{d! \ln d}{n^{d-1}}}, \quad (1.10) $$

and, for a fixed $n$ and $d \to \infty$, we have

$$ \begin{aligned} \sqrt{\frac{(n-1)!}{2^d d^{n-1}}} \left(1 + \mathcal{O}\left(\frac{1}{d}\right)\right) &\leq \mathcal{A}(\text{Sym}^d(\mathbb{R}^n)) \leq 48 \sqrt{\frac{\left(\frac{n}{2}\right)! \ln d}{2^d d^{\frac{n}{2}-1}}} \left(1 + \mathcal{O}\left(\frac{1}{d}\right)\right), \\ \sqrt{\frac{(n-1)!}{d^{n-1}}} \left(1 + \mathcal{O}\left(\frac{1}{d}\right)\right) &\leq \mathcal{A}(\text{Sym}^d(\mathbb{C}^n)) \leq 36 \sqrt{\frac{n! \ln d}{d^{n-1}}} \left(1 + \mathcal{O}\left(\frac{1}{d}\right)\right) \end{aligned} \quad (1.11) $$

where $(\frac{n}{2})! := \Gamma(\frac{n}{2} + 1)$ allows a better and easier comparison of the bounds.
The bound (1.10) shows that $\mathcal{A}(\mathrm{Sym}^d(\mathbb{K}^n))$ has the same order of magnitude as the trivial lower bound $1/\sqrt{n^{d-1}}$ for a fixed $d$ and $n \to \infty$. In particular, for $d=3$ and $\mathbb{K}=\mathbb{R}$ we have $\mathcal{A}(\mathrm{Sym}^3(\mathbb{R}^n)) = \mathcal{O}(1/n)$. The previously known bound

$$ \mathcal{A}(\mathrm{Sym}^3(\mathbb{R}^n)) \le \frac{1.5}{n^{\frac{\ln 1.5}{\ln 2}}} \le \mathcal{O}(n^{-0.584}) $$

on this quantity was obtained in [17, Thm. 5.3]. For a fixed $n > 2$ and a sufficiently large $d$, the lower bounds on the minimal ratio of norms of symmetric tensors in (1.9) are better than the trivial lower bound $1/\sqrt{n^{d-1}}$ by an exponential factor, see asymptotic formulas (1.11) and Section 4.

**Acknowledgments.** We thank Erik Lundberg for pointing out a reference for (4.3). The second author is grateful to Evgenia Lagoda for moral support and Gato Suchen for suggestions regarding the proof of Theorem 3.4.

# 2 Preliminaries

In this section we state and recall some auxiliary results and facts, as well as define our probabilistic models.

## 2.1 Symmetric tensors and homogeneous polynomials

The space $\mathrm{Sym}^d(\mathbb{K}^n)$ of symmetric tensors is identified with the space $P_{d,n} \simeq \mathbb{K}^N$, where $N := \binom{d+n-1}{n-1}$, of $n$-variate homogeneous polynomials (or forms) of degree $d$:

$$ T \in \mathrm{Sym}^d(\mathbb{K}^n) \longleftrightarrow f \in P_{d,n}, \quad f(\mathbf{x}) = \langle T, \mathbf{x} \otimes \cdots \otimes \mathbf{x} \rangle = \sum_{i_j=1}^{n} t_{i_1 \cdots i_d} x_{i_1} \cdots x_{i_d}. \quad (2.1) $$

It is convenient to write the form $f$ in the basis of monomials, $f(\mathbf{x}) = \sum_{|\alpha|=d} f_\alpha \mathbf{x}^\alpha$, where, by symmetry, $f_\alpha = \binom{d}{\alpha} t_{i_1 \cdots i_d}$ and $\alpha_i$ is the number of $j=1, \dots, d$ with $i_j = i$. Under the identification (2.1), the Frobenius product (1.1) is the Bombieri-Weyl product of forms,

$$ \langle T, T' \rangle = \langle f, f' \rangle := \sum_{|\alpha|=d} \binom{d}{\alpha}^{-1} \overline{f_\alpha f'_\alpha}, \quad T \sim f, T \sim f'. \quad (2.2) $$

By a result of Banach [2], a best rank-one approximation to a symmetric tensor $T$ can be chosen among symmetric rank-one tensors $\lambda \mathbf{x} \otimes \cdots \otimes \mathbf{x}$. In particular, the spectral norm (1.3) of $T$ equals the uniform norm $\|f\|_\infty$ of the restriction of $f$ to the unit sphere $S(\mathbb{K}^n) = \{\mathbf{x} \in \mathbb{K}^n : \|\mathbf{x}\|_2^2 = |x_1|^2 + \cdots + |x_n|^2 = 1\}$,

$$ \|T\|_{\infty} = \max_{\mathbf{x}^j \in S(\mathbb{K}^n)} |\langle T, \mathbf{x}^1 \otimes \cdots \otimes \mathbf{x}^d \rangle| = \max_{\mathbf{x} \in S(\mathbb{K}^n)} |\langle T, \mathbf{x} \otimes \cdots \otimes \mathbf{x} \rangle| =: \|f\|_{\infty}. \quad (2.3) $$

The best rank-one approximation ratio of the space $\mathrm{Sym}^d(\mathbb{K}^n)$ is then defined by

$$ \mathcal{A}(\mathrm{Sym}^d(\mathbb{K}^n)) := \min_{T \in \mathrm{Sym}^d(\mathbb{K}^n)} \frac{\|T\|_{\infty}}{\|T\|} = \min_{f \in P_{d,n}} \frac{\|f\|_{\infty}}{\|f\|}, $$

where $\|f\| := \sqrt{\langle f, f \rangle}$ is the Bombieri-Weyl norm of $f \in P_{d,n}$.
A common generalization of spaces $K^n$ and $Sym^d(K^n)$ is the space $\bigotimes_{j=1}^m Sym^{d_j}(K^{n_j})$ of partially symmetric tensors or, equivalently, the space $P_{d,n} \simeq \bigotimes_{j=1}^m P_{d_j,n_j}$ of multi-homogeneous polynomials. An element $F$ of $P_{d,n}$ can be written as

$$F(\boldsymbol{x}^1, \dots, \boldsymbol{x}^m) = \sum_{|\alpha(j)|=d_j} F_{\alpha}(\boldsymbol{x}^1)^{\alpha(1)} \dots (\boldsymbol{x}^m)^{\alpha(m)},$$

where $F_{\alpha} \in K$, $\alpha = (\alpha(1), \dots, \alpha(m))$, $|\alpha(j)| = d_j$, are the coefficients of $F$ in the basis of multi-homogeneous monomials. Then the Bombieri-Weyl product and the uniform norm can be defined via

$$\langle F, F' \rangle := \sum_{|\alpha(j)|=d_j} \left(\frac{\boldsymbol{d}}{\alpha}\right)^{-1} F_{\alpha} F'_{\alpha}, \quad \left(\frac{\boldsymbol{d}}{\alpha}\right) = \left(\frac{d_1}{\alpha(1)}\right) \cdots \left(\frac{d_m}{\alpha(m)}\right) \quad (2.4)$$

$$\|F\|_{\infty} := \max_{\boldsymbol{x}^j \in S(K^{n_j})} |F(\boldsymbol{x}^1, \dots, \boldsymbol{x}^m)|, \quad (2.5)$$

and the best rank-one approximation of the space $\bigotimes_{j=1}^m Sym^{d_j}(K^{n_j})$ is defined by (see [7])

$$A \left( \bigotimes_{j=1}^{m} \mathrm{Sym}^{d_j}(\mathbb{K}^{n_j}) \right) := \min_{F \in P_{d,n}} \frac{\|F\|_{\infty}}{\|F\|},$$

where $\|F\| := \sqrt{\langle F, F \rangle}$ is given by (2.4). Moreover, it is important to keep in mind that the action via changes of variables of the product of unitary groups $U(n_1) \times \dots \times U(n_d)$ on $P_{d,n}$ preserves both the inner product (2.4) and the norm (2.5). In the real case ($K = \mathbb{R}$) the invariance holds with respect to orthogonal changes of variables.

## 2.2 Harmonic polynomials

A form $h \in P_{d,n}$ is called harmonic, if it is annihilated by the Laplace operator, that is,

$$\frac{\partial^2 h}{\partial x_1^2} + \dots + \frac{\partial^2 h}{\partial x_n^2} = 0.$$

We denote by $H_{d,n} \subseteq P_{d,n}$ the subspace consisting of real harmonic $n$-variate forms of degree $d$. This space is an irreducible representation of the group $O(n)$ of orthogonal matrices, which acts on $H_{d,n}$ via change of variables. By [14, Sect. 4.5] any $O(n)$-invariant scalar product on $H_{d,n}$ is a positive multiple of the $L^2(\mathbb{S}^{n-1})$-product defined as

$$\langle h, h' \rangle_{L^2(\mathbb{S}^{n-1})} := \int_{\mathbb{S}^{n-1}} h(\boldsymbol{x})h'(\boldsymbol{x}) \, d\mathbb{S}^{n-1}, \quad h, h' \in H_{d,n}, \quad (2.6)$$

where $d\mathbb{S}^{n-1}$ is the Riemannian volume measure on the unit sphere $\mathbb{S}^{n-1} = S(\mathbb{R}^n)$ obtained from its standard embedding in $\mathbb{R}^n$. In particular, this is true for the Bombieri product (2.2) restricted to $H_{d,n}$. We now relate these two scalar products to each other.

**Lemma 2.1.** For any $h, h' \in H_{d,n}$ we have

$$\langle h, h' \rangle = \frac{2^{d-1} \Gamma(d + \frac{n}{2})}{\sqrt{\pi}^n \Gamma(d + 1)} \langle h, h' \rangle_{L^2(\mathbb{S}^{n-1})}.$$
Proof. It is convenient to write the $L^2(\mathbb{S}^{n-1})$-product as

$$ \langle h, h' \rangle_{L^2(\mathbb{S}^{n-1})} = \frac{1}{\sqrt{2}^{2d+n-2} \Gamma(d+\frac{n}{2})} \int_{\mathbb{R}^n} h(\mathbf{x})h'(\mathbf{x})e^{-\frac{|\mathbf{x}|^2}{2}} d\mathbf{x}, \quad h, h' \in \mathrm{H}_{d,n}. \quad (2.7) $$

Since orthogonally invariant scalar products on $H_{d,n}$ are all proportional, we can recover the constant of proportionality by looking at $h = h' \in H_{d,2} \subseteq H_{d,n}$ defined by

$$ h(x_1, x_2) := \frac{(x_1 + ix_2)^d + (x_1 - ix_2)^d}{2} = r^d \cos(d\theta), \quad x_1 = r \cos \theta, \ x_2 = r \sin \theta. $$

By [1, Thm. 1.1] we have $\|h\|^2 = \langle h, h \rangle = 2^{d-1}$. Since $h$ depends just on $x_1$ and $x_2$, the representation (2.7) implies that the $L^2(\mathbb{S}^{n-1})$-norm of $h$ satisfies

$$ \begin{aligned} \|h\|_{L^2(\mathbb{S}^{n-1})}^2 &= \frac{\sqrt{2\pi}^{n-2}}{\sqrt{2}^{2d+n-2} \Gamma(d+\frac{n}{2})} \int_{\mathbb{R}^2} h(x_1, x_2)^2 e^{-\frac{x_1^2+x_2^2}{2}} dx_1 dx_2 \\ &= \frac{\sqrt{2\pi}^{n-2} \sqrt{2}^{2d} \Gamma(d+1)}{\sqrt{2}^{2d+n-2} \Gamma(d+\frac{n}{2})} \int_0^{2\pi} \cos(d\theta)^2 d\theta = \frac{\sqrt{\pi}^n \Gamma(d+1)}{2^{d-1} \Gamma(d+\frac{n}{2})} \|h\|^2, \end{aligned} $$

which completes the proof. □

The self-duality of $(H_{d,n}, \langle \cdot, \cdot \rangle_{L^2(\mathbb{S}^{n-1})})$ implies that for any $\mathbf{x} \in \mathbb{S}^{n-1}$ there is a unique harmonic form $Z_{\mathbf{x}} \in H_{d,n}$ with

$$ h(\mathbf{x}) = \langle h, Z_{\mathbf{x}} \rangle_{L^2(\mathbb{S}^{n-1})} \quad \text{for all} \quad h \in H_{d,n}. \quad (2.8) $$

The function $Z_{\mathbf{x}} \in H_{d,n}$ is called *zonal harmonic with pole* $\mathbf{x}$. By [21, Cor. 2.9] the $L^2(\mathbb{S}^{n-1})$-norm of $Z_{\mathbf{x}}$ satisfies

$$ \|Z_{\mathbf{x}}\|_{L^2(\mathbb{S}^{n-1})}^2 = Z_{\mathbf{x}}(\mathbf{x}) = \frac{D_{d,n}}{|\mathbb{S}^{n-1}|}, \quad (2.9) $$

where $D_{d,n} = \dim H_{d,n}$ and $|\mathbb{S}^{n-1}| = 2\sqrt{\pi}^n/\Gamma(\frac{n}{2})$ is the volume of the unit sphere.

## 2.3 Probabilistic models

We consider real and complex random polynomials and tensors. Recall first that a complex random variable $t$ is called *standard complex Gaussian*, if its real and imaginary parts are independent centered Gaussians with variance $1/2$. Let $V$ be a (complex) inner product space. Then the *Gaussian distribution* on $V$ is modelled via the vector $\mathbf{v} = \sum_{i=1}^N t_i \mathbf{v}_i$, where $t_1, \dots, t_N$ are independent standard (complex) Gaussians and $\mathbf{v}^1, \dots, \mathbf{v}^N$ form an orthonormal (respectively, unitary) basis of $V$. A remarkable property of the Gaussian distribution on $V$ is its orthogonal (respectively, unitary) invariance. This means that the random vector $U\mathbf{v}$ has Gaussian distribution for any orthogonal (unitary) transformation $U$ on $V$.

As spaces $\mathbb{K}^n$, $P_{d,n}$, $P_{d,n}$ and $H_{d,n}$ are endowed with inner products (1.1), (2.2), (2.4) and (2.7) respectively, the Gaussian distribution is naturally defined for each of them. For example, a real (respectively, complex) tensor $\mathcal{T} = (t_{i_1 \dots i_d})$ is *Gaussian*, if its entries $t_{i_1 \dots i_d}$ are independent standard (complex) Gaussians. Under the standard action of the product of unitary groups $U(\mathbf{n}) := U(n_1) \times \dots \times U(n_d)$ on $\mathbb{C}^n$ the inner product (1.1) and hence
the Gaussian distribution on $\mathbb{C}^n$ are invariant. In particular, the inner product space $\mathbb{R}^n$ of real tensors and the Gaussian distribution on it are invariant under the product $O(\mathbf{n}) := O(n_1) \times \cdots \times O(n_d) \subset U(\mathbf{n})$ of orthogonal groups.

The Gaussian distribution on $P_{d,n}$ is also known as Kostlan distribution. Specifically, an $n$-variate real (respectively, complex) homogeneous polynomial $f(\mathbf{x}) = \sum_{|\alpha|=d} f_\alpha \mathbf{x}^\alpha$ of degree $d$ is called Kostlan, if its normalized coefficients $f_\alpha/\sqrt{\binom{d}{\alpha}}$ are independent standard (complex) Gaussians. Similarly, a multi-homogeneous polynomial $\mathcal{F}(\mathbf{x}^1, \dots, \mathbf{x}^m) = \sum_{|\alpha(j)|=d_j} \mathcal{F}_\alpha(\mathbf{x}^1)^{\alpha(1)} \cdots (\mathbf{x}^m)^{\alpha(m)}$ of multi-degree $\mathbf{d} = (d_1, \dots, d_m)$ is Kostlan (that is, Gaussian), if its normalized coefficients $\mathcal{F}_\alpha/\sqrt{\binom{d}{\alpha}}$ are independent standard (complex) Gaussians. The notion of Kostlan (partially) symmetric tensor is then unambiguously defined through isomorphisms $\mathrm{Sym}^d(\mathbb{K}^n) \simeq P_{d,n}$ and $\bigotimes_{j=1}^m \mathrm{Sym}^{d_j}(\mathbb{K}^{n_j}) \simeq P_{d,n}$. Since the inner products on spaces $P_{d,n}$, $P_{d,n}$ and $H_{d,n}$ are invariant with respect to orthogonal (unitary) changes of variables, so are Gaussian distributions on each of them.

### 3 Upper bounds

In this section we prove upper bounds stated in main Theorems 1.1 and 1.2. These are obtained by combining Corollaries 3.6, 3.8, 3.9 and 3.10, which in turn follow from Theorem 3.4. We first derive some auxiliary results. In the sequel we assume that $d \ge 3$ and $n, n_1, \dots, n_d \ge 2$. The following proposition is found in [5, Proposition 4.24], we include its proof in the appendix for the sake of completeness.

**Proposition 3.1.** Let $t \in \mathbb{R}$ be a random variable, $C \ge 1$ and $K \ge 0$.

1. If for all even integers $\ell > 0$, $(\mathbb{E}_t |t|^{\ell})^{\frac{1}{\ell}} \le K\sqrt{\ell}$, then for all $t > 0$, $\mathbb{P}(|t| \ge t) \le 2e^{-\frac{t^2}{8K^2}}$.

2. If for all $t > 0$, $\mathbb{P}(|t| \ge t) \le C e^{-\frac{t^2}{K^2}}$, then for all $\ell \ge 1$,

$$ \left( \mathbb{E}_t |t|^{\ell} \right)^{\frac{1}{\ell}} \le K \left( \sqrt{\frac{\pi}{2}} + \sqrt{2 \ln C} \right) \sqrt{\ell}. $$

In the next result we estimate the tail probability of the ratio of norms of two vectors, one of which is the image of the other under an orthogonal projection.

**Proposition 3.2.** Let $P: \mathbb{R}^N \to V$ be an orthogonal projection onto a $k$-dimensional subspace $V \subseteq \mathbb{R}^N$ and let $\mathbf{r} \in \mathbb{R}^N$ be a standard Gaussian vector. Then the random variable $\frac{\|P\mathbf{r}\|_2}{\|\mathbf{r}\|_2}$ satisfies

$$ \mathbb{P}_{\mathbf{r}} \left( \frac{\|P\mathbf{r}\|_2}{\|\mathbf{r}\|_2} \ge t \right) \le 2 \exp \left( - \frac{N}{4e^{k+\frac{1}{6N}} t^2} \right) \quad \text{for all } t \ge 0. \quad (3.1) $$

*Proof.* Recall that if $\eta$ and $\zeta$ are independent random variables with $\chi^2$-distribution with, respectively, $k$ and $N-k$ degrees of freedom, then $\frac{\eta}{\eta+\zeta}$ has a $\beta$-distribution with parameters $k/2$ and $(N-k)/2$. In this way, $\frac{\|P\mathbf{r}\|_2}{\|\mathbf{r}\|_2}$ has a $\beta$-distribution with parameters $k/2$ and $(N-k)/2$, and so its density reads

$$ \frac{1}{\beta\left(\frac{k}{2}, \frac{N-k}{2}\right)} s^{\frac{k}{2}-1} (1-s)^{\frac{N-k}{2}-1}, \quad s \in [0, 1]. $$
Doing a change of variables $s = t^2$, we obtain that

$$ \frac{2}{\beta\left(\frac{k}{2}, \frac{N-k}{2}\right)} t^{k-1}(1-t^2)^{\frac{N-k}{2}-1}, \quad t \in [0, 1], $$

is the density of $\frac{\|P_{\mathfrak{r}}\|_2}{\|\mathfrak{r}\|_2}$. Then a straightforward computation implies that for all $\ell > 0$

$$ \left( \mathbb{E} \frac{\|P_{\mathfrak{r}}\|_2^\ell}{\|\mathfrak{r}\|_2^\ell} \right)^{\frac{1}{\ell}} = \left( \frac{\Gamma\left(\frac{k+\ell}{2}\right)}{\Gamma\left(\frac{k}{2}\right)} \frac{\Gamma\left(\frac{N}{2}\right)}{\Gamma\left(\frac{N+\ell}{2}\right)} \right)^{\frac{1}{\ell}}. \quad (3.2) $$

We fix $\ell$ to be a positive even integer. To bound (3.2) we treat each fraction separately. For the first fraction,

$$ \begin{aligned} \frac{\Gamma\left(\frac{k+\ell}{2}\right)}{\Gamma\left(\frac{k}{2}\right)} &= \prod_{i=1}^{\frac{\ell}{2}} \left(\frac{k+\ell}{2} - i\right) && (\Gamma(x) = (x-1)\Gamma(x-1)) \\ &\le \left(\frac{k-1}{2} + \frac{\ell}{4}\right)^{\frac{\ell}{2}} && (\text{AM-GM inequality}) \\ &= \left(1 + \frac{2(k-1)}{\ell}\right)^{\frac{\ell}{2}} \left(\frac{\ell}{4}\right)^{\frac{\ell}{2}} \le e^{k-1} \left(\frac{\ell}{4}\right)^{\frac{\ell}{2}}. \end{aligned} $$

Using Stirling's approximation [3, Eq. 2.14], we bound the second fraction,

$$ \begin{aligned} \frac{\Gamma\left(\frac{N}{2}\right)}{\Gamma\left(\frac{N+\ell}{2}\right)} &\le \frac{N+\ell}{N} \frac{\sqrt{2\pi} \left(\frac{N}{2}\right)^{\frac{N+1}{2}} e^{-\frac{N}{2} + \frac{1}{6N}}}{\sqrt{2\pi} \left(\frac{N+\ell}{2}\right)^{\frac{N+\ell+1}{2}} e^{-\frac{N+\ell}{2}}} \\ &= e^{\frac{\ell}{2} + \frac{1}{6N}} \left(\frac{2}{N}\right)^{\frac{\ell}{2}} \left(1 + \frac{\ell}{N}\right)^{-\frac{N+\ell-1}{2}} \\ &\le e^{\frac{\ell}{2} + \frac{1}{6N}} \left(\frac{2}{N}\right)^{\frac{\ell}{2}}. \qquad \left(1 + \frac{\ell}{N} \ge 1\right) \end{aligned} $$

Putting the obtained bounds together, we have that for all even integers $\ell > 0$

$$ \left( \mathbb{E} \frac{\|P_{\mathfrak{r}}\|_2^\ell}{\|\mathfrak{r}\|_2^\ell} \right)^{\frac{1}{\ell}} \le e^{\frac{k-1}{\ell}} \sqrt{\frac{\ell}{4}} e^{\frac{1}{2} + \frac{1}{6N\ell}} \sqrt{\frac{2}{N}} \le e^{\frac{k}{2} + \frac{1}{12N}} \frac{\sqrt{\ell}}{\sqrt{2N}}. $$

Hence by Proposition 3.1 the desired claim follows. $\square$

**Remark 3.3.** Let $P: \mathbb{C}^N \to V$ be a unitary projection onto a $k$-dimensional (complex) subspace $V \subseteq \mathbb{C}^N$ (that is, $\langle P(z), z - P(z) \rangle_2 = 0$ for all $z \in \mathbb{C}^N$). Then it corresponds to an orthogonal projection between real vector spaces,

$$ P^{\mathbb{R}}: \mathbb{R}^{2N} \to V^{\mathbb{R}}, \\ (\mathbf{x}, \mathbf{y}) \mapsto (\Re(P(\mathbf{x} + i\mathbf{y})), \Im(P(\mathbf{x} + i\mathbf{y}))), $$

where the $2k$-dimensional real subspace $V^{\mathbb{R}} \subseteq \mathbb{R}^{2N}$ is the realification of $V \subseteq \mathbb{C}^N$. Moreover, if $\mathfrak{z} = \mathfrak{r} + i\mathfrak{y} \in \mathbb{C}^N$ is a standard complex Gaussian vector, then $\sqrt{2}(\mathfrak{r}, \mathfrak{y}) \in \mathbb{R}^{2N}$ is a standard real Gaussian vector and, by Proposition 3.2, we obtain for $t \ge 0$ that

$$ \mathbb{P}_{\mathfrak{z}} \left( \frac{\|P_{\mathfrak{z}}\|_2}{\|\mathfrak{z}\|_2} \ge t \right) = \mathbb{P}_{\mathfrak{r}, \mathfrak{y}} \left( \frac{\|P^{\mathbb{R}}(\mathfrak{r}, \mathfrak{y})\|_2}{\|(\mathfrak{r}, \mathfrak{y})\|_2} \ge t \right) \le 2 \exp \left( - \frac{N}{2e^{2k+\frac{1}{12N}} t^2} \right). $$
We need this “complex” version of (3.1) to obtain bounds on the ratio of norms in case of complex tensors and forms.

We consider the sum-geodesic distance on $\prod_{k=1}^{d} \mathbb{S}^{n_k-1}$, given by

$$ \mathrm{dist}_{\mathbb{S}}(\mathbf{x}, \mathbf{y}) := \sum_{k=1}^{d} \mathrm{dist}_{\mathbb{S}}(\mathbf{x}_k, \mathbf{y}_k) = \sum_{k=1}^{d} \arccos\langle\mathbf{x}_k, \mathbf{y}_k\rangle_2 $$

for $\mathbf{x}, \mathbf{y} \in \prod_{k=1}^{d} \mathbb{S}^{n_k-1}$.

**Theorem 3.4.** Let $n_1, \dots, n_d \ge 2$ and $\mathfrak{F} : \prod_{k=1}^{d} \mathbb{S}^{n_k-1} \to [0, \infty)$ be a random Lipschitz function whose Lipschitz constant, $\mathrm{Lip}(\mathfrak{F})$, satisfies for some $L \ge 1$,

$$ \mathrm{Lip}(\mathfrak{F}) \le L \max_{\mathbf{x} \in \prod_{k=1}^{d} \mathbb{S}^{n_k-1}} \mathfrak{F}(\mathbf{x}). \quad (3.3) $$

Then for all $t > 0$,

$$ \mathbb{P}_{\mathfrak{F}} \left( \max_{\mathbf{x} \in \prod_{k=1}^{d} \mathbb{S}^{n_k-1}} \mathfrak{F}(\mathbf{x}) \ge t \right) \le C(L, d; n_1, \dots, n_d) \max_{\mathbf{x} \in \prod_{k=1}^{d} \mathbb{S}^{n_k-1}} \mathbb{P}_{\mathfrak{F}} \left( \mathfrak{F}(\mathbf{x}) \ge \frac{t}{2} \right) \quad (3.4) $$

where $C(L, d; n_1, \dots, n_d)$ satisfies

$$ \ln C(L, d; n_1, \dots, n_d) \le (2 + \ln(dL)) \left( \sum_{k=1}^{d} n_k \right) - \frac{1}{2} \sum_{k=1}^{d} \ln(n_k - 1) - d \ln(dL). $$

*Proof.* If $\max_{\mathbf{x} \in \prod_{k=1}^{d} \mathbb{S}^{n_k-1}} \mathfrak{F}(\mathbf{x}) \ge t$, then, by the Lipschitz property and our assumption (3.3) on the Lipschitz constant, we have that

$$ \left\{ \mathbf{x} \in \prod_{k=1}^{d} \mathbb{S}^{n_k-1} \mid \mathfrak{F}(\mathbf{x}) \ge \frac{t}{2} \right\} \supseteq B_{\mathbb{S}}(\mathfrak{r}_*, (2L)^{-1}), $$

where $\mathfrak{r}_* \in \prod_{k=1}^{d} \mathbb{S}^{n_k-1}$ is the maximizer of $\mathfrak{F}$ and $B_{\mathbb{S}}$ is the ball with respect to the sum-geodesic distance on $\prod_{k=1}^{d} \mathbb{S}^{n_k-1}$ that is centered at $\mathfrak{r}_*$ and has radius $(2L)^{-1}$. In this way, $\max_{\mathbf{x} \in \prod_{k=1}^{d} \mathbb{S}^{n_k-1}} \mathfrak{F}(\mathbf{x}) \ge t$ implies that for a uniformly sampled $\mathfrak{r} \in \prod_{k=1}^{d} \mathbb{S}^{n_k-1}$ we obtain

$$ \mathbb{P}_{\mathfrak{r} \in \prod_{k=1}^{d} \mathbb{S}^{n_k-1}} \left( \mathfrak{F}(\mathfrak{r}) \ge \frac{t}{2} \right) \ge \frac{\mathrm{vol} \, B_{\mathbb{S}}(\mathfrak{r}_*, (2L)^{-1})}{\prod_{k=1}^{d} \mathrm{vol} \, \mathbb{S}^{n_k-1}}. $$

Therefore, we have

$$ \begin{align*} & \mathbb{P}_{\mathfrak{F}} \left( \max_{\mathbf{x} \in \prod_{k=1}^{d} \mathbb{S}^{n_k-1}} \mathfrak{F}(\mathbf{x}) \ge t \right) \\ & \le \mathbb{P}_{\mathfrak{F}} \left( \mathbb{P}_{\mathfrak{r} \in \prod_{k=1}^{d} \mathbb{S}^{n_k-1}} \left( \mathfrak{F}(\mathfrak{r}) \ge \frac{t}{2} \right) \ge \frac{\mathrm{vol} \, B_{\mathbb{S}}(\mathfrak{r}_*, (2L)^{-1})}{\prod_{k=1}^{d} \mathrm{vol} \, \mathbb{S}^{n_k-1}} \right) \quad \text{(Implication bound)} \\ & \le \frac{\prod_{k=1}^{d} \mathrm{vol} \, \mathbb{S}^{n_k-1}}{\mathrm{vol} \, B_{\mathbb{S}}(\mathfrak{r}_*, (2L)^{-1})} \mathbb{E}_{\mathfrak{F}} \left[ \mathbb{P}_{\mathfrak{r} \in \prod_{k=1}^{d} \mathbb{S}^{n_k-1}} \left( \mathfrak{F}(\mathfrak{r}) \ge \frac{t}{2} \right) \right] \quad \text{(Markov's inequality)} \\ & = \frac{\prod_{k=1}^{d} \mathrm{vol} \, \mathbb{S}^{n_k-1}}{\mathrm{vol} \, B_{\mathbb{S}}(\mathfrak{r}_*, (2L)^{-1})} \mathbb{E}_{\mathfrak{r} \in \prod_{k=1}^{d} \mathbb{S}^{n_k-1}} \left[ \mathbb{P}_{\mathfrak{F}} \left( \mathfrak{F}(\mathfrak{r}) \ge \frac{t}{2} \right) \right] \quad \text{(Tonelli's theorem)} \\ & \le \frac{\prod_{k=1}^{d} \mathrm{vol} \, \mathbb{S}^{n_k-1}}{\mathrm{vol} \, B_{\mathbb{S}}(\mathfrak{r}_*, (2L)^{-1})} \max_{\mathbf{x} \in \prod_{k=1}^{d} \mathbb{S}^{n_k-1}} \mathbb{P}_{\mathfrak{F}} \left( \mathfrak{F}(\mathbf{x}) \ge \frac{t}{2} \right). \end{align*} $$
It remains to bound $\frac{\prod_{k=1}^{d} \text{vol} \, \mathbb{S}^{n_k-1}}{\text{vol} \, B_{\mathbb{S}}(\mathbf{r}_*, (2L)^{-1})}$. By applying orthogonal transformations to each sphere, we can assume that $\mathbf{x}_* = \mathbf{e}_1 := (\mathbf{e}_1, \dots, \mathbf{e}_1) \in \prod_{k=1}^{d} \mathbb{S}^{n_k-1}$. Consider the map

$$ \text{IO}: \prod_{k=1}^{d} \mathbb{R}^{n_k-1} \to \prod_{k=1}^{d} \mathbb{S}^{n_k-1} \\ \left( \begin{matrix} \mathbf{z}_1 \\ \vdots \\ \mathbf{z}_d \end{matrix} \right) \mapsto \left( \begin{matrix} \frac{1}{\sqrt{1+\|\mathbf{z}_1\|_2^2}} & \begin{pmatrix} 1 \\ \mathbf{z}_1 \end{pmatrix} \\ \vdots & \\ \frac{1}{\sqrt{1+\|\mathbf{z}_d\|_2^2}} & \begin{pmatrix} 1 \\ \mathbf{z}_d \end{pmatrix} \end{matrix} \right). $$

Then, by the result in the appendix A.2, we have that

$$ |\det D_{\mathbf{z}} \text{IO}| = \prod_{k=1}^{d} (1 + \|\mathbf{z}_k\|_2^2)^{-\frac{n_k}{2}}, \quad \mathbf{z} = (\mathbf{z}_1, \dots, \mathbf{z}_d) \in \prod_{k=1}^{d} \mathbb{R}^{n_k-1}. \qquad (3.5) $$

Now, we do a sequence of changes of variables as follows:

$$ \begin{align*} \operatorname{vol} B_{\mathbb{S}}(\mathbf{e}_1, R) &= \int \prod_{k=1}^{d} (1 + \|\mathbf{z}_k\|_2^2)^{-\frac{n_k}{2}} \, d\mathbf{z}_1 \cdots d\mathbf{z}_d \\ &= \prod_{k=1}^{d} \operatorname{vol} \mathbb{S}^{n_k-2} \int \prod_{k=1}^{d} \rho_k^{n_k-2} (1 + \rho_k^2)^{-\frac{n_k}{2}} \, d\rho_1 \cdots d\rho_d \\ &= \prod_{k=1}^{d} \operatorname{vol} \mathbb{S}^{n_k-2} \int \prod_{k=1}^{d} (\sin \phi_k)^{n_k-2} \, d\phi_1 \cdots d\phi_d \\ &= \left(\frac{R}{\eta}\right)^{\sum_{k=1}^{d} n_k - d} \prod_{k=1}^{d} \operatorname{vol} \mathbb{S}^{n_k-2} \int \prod_{k=1}^{d} \frac{t_k^{n_k-2}}{\sqrt{1 - R^2 \eta^{-2} t_k^2}} \, dt_1 \cdots dt_d \\ &= \left(\frac{R}{\eta}\right)^{\sum_{k=1}^{d} n_k - d} \prod_{k=1}^{d} \operatorname{vol} \mathbb{S}^{n_k-2} \int_{\sum_{k=1}^{d} \arcsin(R\eta^{-1}t_k) \le R} \prod_{k=1}^{d} \frac{t_k^{n_k-2}}{\sqrt{1 - R^2 \eta^{-2} t_k^2}} \, dt_1 \cdots dt_d \end{align*} $$

where we use $x = \text{IO}(z)$ in the first line, $z_k = \rho_k \theta_k$ with $\rho_k \ge 0$ and $\theta_k \in \mathbb{S}^{n_k-2}$ in the second line, $\rho_k = \tan \phi_k$ in the third line, and $\sin \phi_k = R\eta^{-1}t_k$ in the fourth line.

Observe that the domain of integration of the last integral is contained in $[0, \eta]^d$. In this way, we have for each $k$, $\arcsin(R\eta^{-1}t_k) \le R\eta^{-1}t_k/\sqrt{1-R^2}$, and so the domain of integration contains $\sum_{k=1}^d t_k \le \eta\sqrt{1-R^2}$. Since $1/\sqrt{1-R^2\eta^{-2}t_k^2} \ge 1$, we obtain the following lower bound:

$$ \operatorname{vol} B_{\mathbb{S}}(\mathbf{e}_1, R) \ge \left(R\sqrt{1-R^2}\right)^{\sum_{k=1}^{d} n_k - d} \prod_{k=1}^{d} \operatorname{vol} \mathbb{S}^{n_k-2} \int_{\sum_{k=1}^{d} t_k \le 1} \prod_{k=1}^{d} t_k^{n_k-2} \, dt_1 \cdots dt_d $$
where we took $\eta^{-1} = \sqrt{1 - R^2}$. Therefore, taking $R = \frac{1}{2L}$, we obtain

$$C(L, d; n_1, \dots, n_d) \le \frac{\left( \frac{2L}{\sqrt{1-\frac{1}{4L^2}}} \right)^{\sum_{k=1}^d n_k - d} \prod_{k=1}^d \frac{\text{vol} \, \mathbb{S}^{n_k-1}}{\text{vol} \, \mathbb{S}^{n_k-2}}}{\int \prod_{k=1}^d t_k^{n_k-2} \, \mathrm{d}t_1 \cdots \mathrm{d}t_d} \quad (3.6)$$

We now bound the three parts of the logarithm of the right-hand side separately.

First, we have that $\ln \frac{1}{\sqrt{1-\frac{1}{4L^2}}} \le \frac{1}{6L^2}$ since $L \ge 1$. Thus

$$\ln \left( \frac{2L}{\sqrt{1 - \frac{1}{4L^2}}} \right)^{\sum_{k=1}^{d} n_k - d} \le \left( \sum_{k=1}^{d} n_k - d \right) \left( \ln 2 + \frac{1}{6L^2} + \ln L \right). \quad (3.7)$$

Second, for $n_1, \dots, n_d \ge 2$, Lemma 2.25 from [3] gives

$$\frac{\text{vol} \, \mathbb{S}^{n_k-1}}{\text{vol} \, \mathbb{S}^{n_k-2}} \le \frac{\sqrt{2\pi n_k}}{n_k-1} \le \frac{2\sqrt{\pi}}{\sqrt{n_k-1}}$$

and hence

$$\ln \prod_{k=1}^{d} \frac{\text{vol} \, \mathbb{S}^{n_k-1}}{\text{vol} \, \mathbb{S}^{n_k-2}} \le d \ln(2\sqrt{\pi}) - \frac{1}{2} \sum_{k=1}^{d} \ln(n_k - 1). \quad (3.8)$$

Third, we have that

$$
\begin{align*}
& \ln \left( \int_{\substack{t_1, \dots, t_d \ge 0, \\ \sum_{k=1}^d t_k \le 1}} \prod_{k=1}^d t_k^{n_k-2} \, \mathrm{d}t_1 \cdots \mathrm{d}t_d \right) \\
&= -\ln d! + \ln \left( d! \int_{\substack{t_1, \dots, t_d \ge 0, \\ \sum_{k=1}^d t_k \le 1}} \prod_{k=1}^d t_k^{n_k-2} \, \mathrm{d}t_1 \cdots \mathrm{d}t_d \right) \\
&\ge -\ln d! + \sum_{k=1}^d d!(n_k-2) \int_{\substack{t_1, \dots, t_d \ge 0, \\ \sum_{k=1}^d t_k \le 1}} \ln t_k \, \mathrm{d}t_1 \cdots \mathrm{d}t_d \quad \text{(Jensen's inequality)} \\
&= -\ln d! + \sum_{k=1}^d d(n_k-2) \int_0^1 (1-t_k)^{d-1} \ln t_k \, \mathrm{d}t_k \quad \text{(Integrate over } \sum_{i \ne k} t_i \le 1-t_k \text{)} \\
&= -\ln d! - \left( d \int_0^1 \sum_{l=1}^\infty \frac{(1-t)^{d+l-1}}{l} \, \mathrm{d}t \right) \left( \sum_{k=1}^d n_k - 2d \right) \quad \left( \ln t = - \sum_{l=1}^\infty \frac{(1-t)^l}{l} \right) \\
&= -\ln d! - \left( d \sum_{l=1}^\infty \int_0^1 \frac{(1-t)^{d+l-1}}{l} \, \mathrm{d}t \right) \left( \sum_{k=1}^d n_k - 2d \right) \quad \text{(Monotone convergence)}
\end{align*}
$$
$$
\begin{align*}
&= -\ln d! - \left(\sum_{l=1}^{\infty} \frac{d}{l(d+l)}\right) \left(\sum_{k=1}^{d} n_k - 2d\right) \\
&= -\ln d! - \left(\sum_{k=1}^{d} \frac{1}{k}\right) \left(\sum_{k=1}^{d} n_k - 2d\right). \quad \left(\frac{d}{l(d+l)} = \frac{1}{l} - \frac{1}{d+l}\right).
\end{align*}
$$

Now, Stirling’s bound [3, Eq. 2.14] gives

$$
\ln d! \le \frac{1}{2} \ln(2\pi) + d \ln d + \frac{1}{2} \ln d - d + \frac{1}{12d}.
$$

Formula (3) in [12, 1.2.7], whose proof is contained in [12, 1.2.11.2], yields

$$
\sum_{k=1}^{d} \frac{1}{k} \leq \ln d + \gamma + \frac{1}{2d},
$$

where $\gamma := \lim_{n \to \infty} (-\ln n + \sum_{k=1}^n 1/k) = 0.57721566...$ is the Euler–Mascheroni constant. Thus, we have that

$$
- \ln \left( \int_{\substack{t_1, \dots, t_d \ge 0, \\ \sum_{k=1}^d t_k \le 1}} \prod_{k=1}^d t_k^{n_k-2} \mathrm{d}t_1 \cdots \mathrm{d}t_d \right) \le \left( \sum_{k=1}^d n_k \right) \left( \ln d + \gamma + \frac{1}{2d} \right) - d \ln d - d, (3.9)
$$

since $\frac{1}{2}\ln(2\pi) - 1 < 0$ and $\frac{1}{2}\ln d + \frac{1}{12d} - 2\gamma d < 0$.

Finally, applying the logarithm to (3.6) and using the inequalities (3.7), (3.8) and (3.9),
we obtain the desired bound after noticing that $\gamma + \frac{1}{2d} + \ln 2 + \frac{1}{6L^2} \le 2$. $\square$

Remark 3.5. If the random function $\mathfrak{F}: \prod_{k=1}^d \mathbb{S}^{n_k-1} \to [0, \infty)$ is invariant under orthogonal changes of variables on $\mathbb{S}^{n_1-1}, \dots, \mathbb{S}^{n_d-1}$, the probability $P_{\mathfrak{F}}(\mathfrak{F}(\mathbf{x}) \ge \frac{t}{2})$ does not depend on the point $\mathbf{x} \in \prod_{k=1}^d \mathbb{S}^{n_k-1}$ and hence we can omit maximum in (3.4).

We now apply Theorem 3.4 to give bounds on (1.5) and (1.6).

**Corollary 3.6.** Let $\mathcal{T} \in \mathbb{K}^n$ be a Gaussian tensor. Then

$$
\mathbb{E}_{\mathcal{T}} \frac{\|\mathcal{T}\|_{\infty}}{\|\mathcal{T}\|} \le 32 \sqrt{\ln d} \sqrt{\frac{\sum_{j=1}^{d} n_j}{\prod_{j=1}^{d} n_j}} \quad (3.10)
$$

and, in particular,

$$
\frac{1}{\sqrt{\min_j \prod_{i \neq j} n_j}} \le \mathcal{A}(\mathbb{K}^n) \le \frac{32\sqrt{d \ln d}}{\sqrt{\min_j \prod_{i \neq j} n_j}}.
$$

*Proof.* Let us consider a random Lipschitz function

$$
\begin{align}
\mathfrak{F}: \mathbb{S}(\mathbb{K}^{n_1}) \times \cdots \times \mathbb{S}(\mathbb{K}^{n_d}) &\to [0, \infty), \nonumber \\
\mathbf{x} = (\mathbf{x}^1, \dots, \mathbf{x}^d) &\mapsto \frac{|\langle \mathcal{T}, \mathbf{x}^1 \otimes \cdots \otimes \mathbf{x}^d \rangle|}{\|\mathcal{T}\|}. \tag{3.11}
\end{align}
$$
Its Lipschitz constant satisfies Lip($\mathfrak{F}$) ≤ max$_{x_j \in \mathbb{S}(\mathbb{K}^{n_j})}$ $\mathfrak{F}(x) = \frac{\|\mathcal{T}\|_{\infty}}{\|\mathcal{T}\|}$, since

$$
\begin{align*}
|\mathfrak{F}(\mathbf{x}) - \mathfrak{F}(\mathbf{y})| &\le \frac{|\langle \mathcal{T}, \mathbf{x}^1 \otimes \dots \otimes \mathbf{x}^d - \mathbf{y}^1 \otimes \dots \otimes \mathbf{y}^d \rangle|}{\|\mathcal{T}\|} \\
&\le \sum_{j=1}^d \frac{|\langle \mathcal{T}, \mathbf{x}^1 \otimes \dots \otimes \mathbf{x}^{j-1} \otimes (\mathbf{x}^j - \mathbf{y}^j) \otimes \mathbf{y}^{j+1} \otimes \dots \otimes \mathbf{y}^d \rangle|}{\|\mathcal{T}\|} \\
&\le \left( \max_{\mathbf{z}^j \in \mathbb{S}(\mathbb{K}^{n_j})} \mathfrak{F}(\mathbf{z}) \right) \sum_{j=1}^d \|\mathbf{x}^j - \mathbf{y}^j\|_2 \le \left( \max_{\mathbf{z}^j \in \mathbb{S}(\mathbb{K}^{n_j})} \mathfrak{F}(\mathbf{z}) \right) \mathrm{dist}_{\mathbb{S}}(\mathbf{x}, \mathbf{y}) \tag{3.12}
\end{align*}
$$

holds for any $\mathbf{x}, \mathbf{y} \in \mathbb{S}(\mathbb{K}^{n_1}) \times \dots \times \mathbb{S}(\mathbb{K}^{n_d})$. By Theorem 3.4, we have for all $t > 0$,

$$
\mathbb{P}_{\mathcal{T}} \left( \frac{\|\mathcal{T}\|_{\infty}}{\|\mathcal{T}\|} \ge t \right) \le C(d, \mathbf{n}) \mathbb{P}_{\mathcal{T}} \left( \mathfrak{F}(e_1, \dots, e_1) \ge \frac{t}{2} \right), \quad (3.13)
$$

where $\ln C(d, \mathbf{n}) \le (2+\ln d) \left( \sum_{j=1}^d k n_j \right) - \frac{1}{2} \sum_{j=1}^d \ln(k n_j - 1) - d \ln d$ with $k$ being either 1 ($\mathbb{K} = \mathbb{R}$) or 2 ($\mathbb{K} = \mathbb{C}$). Since $\mathfrak{F}(e_1, \dots, e_1) = \|\langle \mathcal{T}, e_1 \otimes \dots \otimes e_1 \rangle e_1 \otimes \dots \otimes e_1\| / \|\mathcal{T}\|$, Proposition 3.2 and Remark 3.3 applied to the orthogonal (unitary, if $\mathbb{K} = \mathbb{C}$) projection $T \mapsto \langle T, e_1 \otimes \dots \otimes e_1 \rangle e_1 \otimes \dots \otimes e_1$ give

$$
\mathbb{P}_{\mathcal{T}} \left( \mathfrak{F}(e_1, \dots, e_1) \ge \frac{t}{2} \right) \le 2 \exp \left( - \frac{k n_1 \cdots n_d}{4 e^{\frac{k+1}{6 k n_1 \cdots n_d}}} \frac{t^2}{4} \right).
$$

Combining this inequality with (3.13) and applying Proposition 3.1, we finally have

$$
\begin{align*}
& \mathbb{E}_{\mathcal{T}} \frac{\|\mathcal{T}\|_{\infty}}{\|\mathcal{T}\|} \\
\le {} & \frac{\sqrt{16e^{\frac{k+1}{6kn_1\cdots n_d}}}}{\sqrt{kn_1\cdots n_d}} \left( \sqrt{\frac{\pi}{2}} + \sqrt{2\ln 2 + 2(2+\ln d) \left( \sum_{j=1}^d k n_j \right) - \sum_{j=1}^d \ln(k n_j - 1) - 2d \ln d} \right) \\
\le {} & 32\sqrt{\ln d} \frac{\sqrt{\sum_{j=1}^d n_j}}{\sqrt{\prod_{j=1}^d n_j}} \le \frac{32\sqrt{d \ln d}}{\sqrt{\min_j \prod_{i \ne j} n_j}}.
\end{align*}
$$

□

Remark 3.7. When all dimensions $n_1 = \cdots = n_d = n$ are equal, one has

$$
\frac{1}{\sqrt{n^{d-1}}} \le \mathcal{A}(\mathbb{K}^{\mathbf{n}}) \le \mathbb{E}_{\mathcal{T}} \frac{\|\mathcal{T}\|_{\infty}}{\|\mathcal{T}\|} \le \frac{32\sqrt{d \ln d}}{\sqrt{n^{d-1}}}.
$$

Next we derive a bound for the expected ratio of norms in the case of symmetric
tensors. We formulate everything in the equivalent terms of homogeneous polynomials,
see Section 2.1.

**Corollary 3.8.** Let $f \in P_{d,n}$ be a Kostlan form. Then
$$ \mathbb{E}_{f} \frac{\|f\|_{\infty}}{\|f\|} \le \frac{36\sqrt{n \ln d}}{\sqrt{\binom{n+d-1}{d}}} \quad (3.14) $$

and, in particular,

$$ \frac{1}{\sqrt{n^{d-1}}} \le \mathcal{A}(\mathrm{Sym}^d(\mathbb{K}^n)) \le \frac{36\sqrt{d! \ln d}}{\sqrt{n^{d-1}}}. $$

*Proof.* Let us consider a random Lipschitz function

$$ \begin{gathered} \mathfrak{F} : \mathbb{S}(\mathbb{K}^n) \to [0, \infty), \\ \boldsymbol{x} \mapsto \frac{|\boldsymbol{f}(\boldsymbol{x})|}{\|\boldsymbol{f}\|}. \end{gathered} $$

Note that it is the restriction of the function (3.11) to the diagonally embedded sphere $\mathbb{S}(\mathbb{K}^n) \hookrightarrow \mathbb{S}(\mathbb{K}^n) \times \cdots \times \mathbb{S}(\mathbb{K}^n)$. By (3.12) and (2.3) the Lipschitz constant of $\mathfrak{F}$ satisfies

$$ \mathrm{Lip}(\mathfrak{F}) \le d \max_{\boldsymbol{x} \in \mathbb{S}(\mathbb{K}^n)} \mathfrak{F}(\boldsymbol{x}) = d \frac{\|\boldsymbol{f}\|_{\infty}}{\|\boldsymbol{f}\|}. \quad (3.15) $$

By Theorem 3.4 we have for all $t > 0$,

$$ \mathbb{P}_f \left( \frac{\|\boldsymbol{f}\|_{\infty}}{\|\boldsymbol{f}\|} \ge t \right) \le C(d,n) \mathbb{P}_f \left( \mathfrak{F}(e_1) \ge \frac{t}{2} \right) = C(d,n) \mathbb{P}_f \left( \frac{|\boldsymbol{f}(d,0,\dots,0)|}{\|\boldsymbol{f}\|} \ge \frac{t}{2} \right), \quad (3.16) $$

where $\ln C(d,n) \le (2 + \ln d)kn - \frac{1}{2}\ln(kn - 1) - \ln d$ with $k$ being either 1 ($\mathbb{K} = \mathbb{R}$) or 2 ($\mathbb{K} = \mathbb{C}$). Since $f$ is a Kostlan form, that is, $f_{\alpha} = \sqrt{\binom{d}{\alpha}}\tilde{f}_{\alpha}$, where variables $\tilde{f}_{\alpha}$ are independent standard (complex) Gaussians, its Bombieri-Weyl norm satisfies

$$ \|\boldsymbol{f}\|^2 = \sum_{|\alpha|=d} \left(\binom{d}{\alpha}\right)^{-1} |\tilde{f}_{\alpha}|^2 = \sum_{|\alpha|=d} |\tilde{f}_{\alpha}|^2. $$

We apply Proposition 3.2 and Remark 3.3 to the projection $\pi_1$ onto the first coordinate axis in $\mathbb{K}^N$ and, using $\|\pi_1(f)\|_2 = |\tilde{f}_{(d,0,\dots,0)}| = |\tilde{f}_{(d,0,\dots,0)}|$, obtain that

$$ \mathbb{P}_f \left( \frac{|\tilde{f}_{(d,0,\dots,0)}|}{\|\tilde{f}\|} \ge \frac{t}{2} \right) \le 2 \exp \left( - \frac{kN}{4e^{k+\frac{1}{6kN}} \frac{t^2}{4}} \right). $$

This, together with inequality (3.16) and Proposition 3.1, finally implies that

$$ \begin{align*} \mathbb{E}_{f} \frac{\|\boldsymbol{f}\|_{\infty}}{\|\boldsymbol{f}\|} &\le \frac{\sqrt{16e^{k+\frac{1}{6kN}}}}{\sqrt{kN}} \left( \sqrt{\frac{\pi}{2}} + \sqrt{2\ln 2 + 2(2 + \ln d)kn - \ln(kn - 1) - 2\ln d} \right) \\ &\le \frac{36\sqrt{n \ln d}}{\sqrt{\binom{n+d-1}{d}}} \le \frac{36\sqrt{d! \ln d}}{\sqrt{n^{d-1}}}. \end{align*} $$

□
Similarly, one can derive the following bound on the expectation of the ratio of norms for random partially symmetric tensors. We state it in equivalent terms of multi-homogeneous polynomials.

**Corollary 3.9.** Let $\mathcal{F} \in \mathrm{P}_{d,n}$ be a Kostlan multi-homogeneous polynomial, where $\mathbf{n} = (n_1, \dots, n_m)$ and $\mathbf{d} = (d_1, \dots, d_m)$. Then

$$ \mathcal{A} \left( \bigotimes_{j=1}^{m} \mathrm{Sym}^{d_j}(\mathbb{K}^{n_j}) \right) \leq \mathbb{E}_{\mathcal{F}} \frac{\|\mathcal{F}\|_{\infty}}{\|\mathcal{F}\|} \leq 36 \sqrt{\ln \left( m \max_{j=1,\dots,m} d_j \right)} \sqrt{\frac{\sum_{j=1}^{m} n_j}{\prod_{j=1}^{m} \binom{n_j+d_j-1}{n_j-1}}} $$

When $d_1 = \dots = d_m = 1$ (that is, in the case of general tensors of format $(n_1, \dots, n_m)$) this bound agrees (up to a factor) with (3.10), while when $m = 1$ (that is, in the case of symmetric tensors) we recover (3.14).

It is interesting to investigate the bound on $\mathcal{A}(\mathrm{Sym}^d(\mathbb{R}^n))$ given by the expected ratio of norms of a random harmonic polynomial.

**Corollary 3.10.** Let $\mathfrak{h} \in \mathrm{H}_{d,n}$ be a Gaussian harmonic form. Then

$$ \mathcal{A}(\mathrm{Sym}^d(\mathbb{R}^n)) \leq \mathbb{E}_{\mathfrak{h}} \frac{\|\mathfrak{h}\|_{\infty}}{\|\mathfrak{h}\|} \leq 24 \frac{\sqrt{d! \ln d \Gamma\left(\frac{n}{2}\right) n}}{\sqrt{2^d \Gamma\left(d + \frac{n}{2}\right)}} \leq 24 \frac{\sqrt{d! \ln d}}{\sqrt{n^{d-1}}}. \quad (3.17) $$

*Proof.* Given a Gaussian harmonic form $\mathfrak{h} \in \mathrm{H}_{d,n}$, we consider a random Lipschitz function

$$ \begin{gathered} \mathfrak{F} : \mathbb{S}^{n-1} \to [0, \infty)], \\ \boldsymbol{x} \mapsto \frac{|\mathfrak{h}(\boldsymbol{x})|}{\|\mathfrak{h}\|}. \end{gathered} $$

The bound (3.15) implies that the Lipschitz constant of $\mathfrak{F}$ satisfies

$$ \mathrm{Lip}(\mathfrak{F}) \leq d \max_{\boldsymbol{x} \in \mathbb{S}^{n-1}} \mathfrak{F}(\boldsymbol{x}) = d \frac{\|\boldsymbol{h}\|_{\infty}}{\|\boldsymbol{h}\|}. $$

By Theorem 3.4 we have for all $t > 0$ that

$$ \mathbb{P}_{\mathfrak{h}} \left( \frac{\|\mathfrak{h}\|_{\infty}}{\|\mathfrak{h}\|} \geq t \right) \leq C(d, n) \max_{\boldsymbol{x} \in \mathbb{S}^{n-1}} \mathbb{P}_{\mathfrak{h}} \left( \mathfrak{F}(\boldsymbol{x}) \geq \frac{t}{2} \right) \quad (3.18) $$

with $\ln C(d, n) \leq (2 + \ln d)n - \frac{1}{2}\ln(n-1) - \ln d$. Since the inner product (2.6) of two harmonic forms is invariant under orthogonal changes of variables and since, by Lemma 2.1, it is proportional to (2.2), the random variables $\mathfrak{F}(\boldsymbol{x})$ and $\mathfrak{F}(\boldsymbol{x}')$ have the same distribution for any $\boldsymbol{x}, \boldsymbol{x}' \in \mathbb{S}^{n-1}$. In particular, in the right-hand side of (3.18) we can drop the maximum and consider any point $\boldsymbol{x} \in \mathbb{S}^{n-1}$.

The evaluation of $h \in \mathrm{H}_{d,n}$ at a point $\boldsymbol{x} \in \mathbb{S}^{n-1}$ does not anymore correspond to an orthogonal projection in $(\mathrm{H}_{d,n}, \langle \cdot, \cdot \rangle_{L^2(\mathbb{S}^{n-1})})$, as it was in the case of Kostlan polynomials. However, the formula (2.8) implies that it is given by taking inner product with $Z_{\boldsymbol{x}}$. So,

$$ \begin{gathered} P : \mathrm{H}_{d,n} \to \mathbb{R} Z_{\boldsymbol{x}}, \\ h \mapsto \frac{h(\boldsymbol{x})}{\|Z_{\boldsymbol{x}}\|_{L^2(\mathbb{S}^{n-1})}} \frac{Z_{\boldsymbol{x}}}{\|Z_{\boldsymbol{x}}\|_{L^2(\mathbb{S}^{n-1})}}, \end{gathered} $$
is an orthogonal projection on the line through $Z_x$ and Proposition 3.2 gives

$$ \mathbb{P}_h \left( \frac{|\mathfrak{h}(\boldsymbol{x})|}{\|Z_x\|_{L^2(\mathbb{S}^{n-1})} \|\mathfrak{h}\|_{L^2(\mathbb{S}^{n-1})}} \ge t \right) \le 2 \exp \left( - \frac{D_{d,n}}{4e^{\frac{1}{6D_{d,n}}}} t^2 \right), \quad t \ge 0. $$

This and Lemma 2.1 imply that for all $t \ge 0$,

$$ \begin{aligned} \mathbb{P}_h \left( \mathfrak{F}(\boldsymbol{x}) \ge \frac{t}{2} \right) &= \mathbb{P}_h \left( \frac{|\mathfrak{h}(\boldsymbol{x})|}{\|Z_x\|_{L^2(\mathbb{S}^{n-1})} \|\mathfrak{h}\|_{L^2(\mathbb{S}^{n-1})}} \ge \frac{t \sqrt{\Gamma(d+\frac{n}{2})} \sqrt{2}^{d-1}}{2 \|Z_x\|_{L^2(\mathbb{S}^{n-1})} \sqrt{\Gamma(d+1)} \pi^{n/4}} \right) \\ &\le 2 \exp \left( - \frac{D_{d,n} \Gamma(d+\frac{n}{2}) 2^{d-5}}{e^{\frac{1}{6D_{d,n}}} \|Z_x\|_{L^2(\mathbb{S}^{n-1})}^2 \Gamma(d+1) \sqrt{\pi}^n} t^2 \right). \end{aligned} $$

Finally, combining this with (3.18) and applying Proposition 3.1, we derive

$$ \begin{aligned} \mathbb{E}_h \frac{\|\mathfrak{h}\|_{\infty}}{\|\mathfrak{h}\|} &\le K \left( \sqrt{\frac{\pi}{2}} + \sqrt{2 \ln(2C(d,n))} \right) \\ &\le K \left( \sqrt{\frac{\pi}{2}} + \sqrt{2(2+\ln d)n} \right), \end{aligned} \quad (3.19) $$

where

$$ K = \frac{e^{\frac{1}{2} + \frac{1}{12D_{d,n}}} \|Z_x\|_{L^2(\mathbb{S}^{n-1})} \sqrt{\Gamma(d+1)} \pi^{n/4}}{\sqrt{D_{d,n}} \sqrt{\Gamma(d+\frac{n}{2})} \sqrt{2}^{d-5}}. $$

By (2.9) and the formula $|\mathbb{S}^{n-1}| = 2\sqrt{\pi}^n/\Gamma(\frac{n}{2})$ for the volume of the sphere, we simplify:

$$ K = \frac{e^{\frac{1}{2} + \frac{1}{12D_{d,n}}} \sqrt{d!} \sqrt{\Gamma(\frac{n}{2})}}{\sqrt{2}^{d-4} \sqrt{\Gamma(d+\frac{n}{2})}}. $$

We combine this expression for $K$ with (3.19) and finally obtain

$$ \begin{aligned} \mathbb{E}_h \frac{\|\mathfrak{h}\|_{\infty}}{\|\mathfrak{h}\|} &\le 4e^{\frac{1}{2} + \frac{1}{12D_{d,n}}} \left( \sqrt{\frac{\pi}{2}} + \sqrt{2(2+\ln d)n} \right) \frac{\sqrt{d! \Gamma(\frac{n}{2})}}{\sqrt{2^d \Gamma(d+\frac{n}{2})}} \\ &\le 24 \frac{\sqrt{d! \ln d \Gamma(\frac{n}{2}) n}}{\sqrt{2^d \Gamma(d+\frac{n}{2})}} \le 24 \frac{\sqrt{d! \ln d}}{\sqrt{n^{d-1}}}. \end{aligned} $$

□

Remark 3.11. When $n$ is large compared to $d$, bounds (3.17) and (3.14) coincide up to a constant. Let us now study the case of a fixed $n$ and large $d$. Applying the asymptotic formula for the ratio of Gamma functions (see [6, (1)]) to (3.17) we have

$$ \begin{aligned} \mathcal{A}(\mathrm{Sym}^d(\mathbb{R}^n)) &\le 24 \sqrt{n \Gamma(\frac{n}{2})} \sqrt{\frac{\ln d}{2^d}} \sqrt{\frac{\Gamma(d+1)}{\Gamma(d+\frac{n}{2})}} \quad (3.20) \\ &= 48 \sqrt{\Gamma(\frac{n}{2}+1)} \sqrt{\frac{\ln d}{2^d d^{\frac{n}{2}-1}}} \left(1+\mathcal{O}\left(\frac{1}{d}\right)\right). \end{aligned} $$
Similarly, one bounds (3.14) as

$$ 
\begin{aligned}
\mathcal{A}(\mathrm{Sym}^d(\mathbb{R}^n)) &\le 36\sqrt{n!}\sqrt{\ln d}\sqrt{\frac{d\Gamma(d)}{\Gamma(d+n)}} \quad (3.21) \\
&= 36\sqrt{n!}\sqrt{\frac{\ln d}{d^{n-1}}\left(1+\mathcal{O}\left(\frac{1}{d}\right)\right)}.
\end{aligned}
$$

This shows that the bound (3.17) coming from random harmonic forms is better by an exponential factor than the bound (3.14) obtained from Kostlan forms. Finally, comparing (3.20) with the lower bound (4.5) on $\mathcal{A}(\mathrm{Sym}^d(\mathbb{R}^n))$ derived in the next section, we obtain

$$ \frac{\sqrt{(n-1)!}}{\sqrt{2^d d^{n-1}}} \left(1 + \mathcal{O}\left(\frac{1}{d}\right)\right) \le \mathcal{A}(\mathrm{Sym}^d(\mathbb{R}^n)) \le 48 \sqrt{\Gamma\left(\frac{n}{2}+1\right)} \sqrt{\frac{\ln d}{2^d d^{\frac{n}{2}-1}}} \left(1 + \mathcal{O}\left(\frac{1}{d}\right)\right). $$

In particular, for a fixed $n$ the two bounds differ by the factor $C_n d^{\frac{n}{2}} \sqrt{\ln d}$, that grows not faster than a polynomial in $d$.

# 4 Lower bounds

In the case of forms (equivalently, symmetric tensors) we provide seemingly new lower bounds on the best rank-one approximation ratio (1.6), which are (when the degree $d$ is large enough compared to the dimension $n$) better than the trivial bound (1.7). In particular, this implies validity of lower bounds in Theorem 1.2. For $d > 2$ it is shown in [1, Cor. 1.8] that the inequality $\mathcal{A}(\mathrm{Sym}^d(\mathbb{R}^n)) > 1/\sqrt{n^{d-1}} = \mathcal{A}(\mathbb{R}^n)$, $\mathbf{n} = (n, \dots, n)$, is strict when $n = 4$ or $n = 8$. Beyond this result we are not aware of any general lower bounds on $\mathcal{A}(\mathrm{Sym}^d(\mathbb{K}^n))$, that are different from the trivial bound (1.7).

The Bombieri-Weyl product (2.2) admits an integral representation

$$ \langle f, f' \rangle = \binom{d+n-1}{n-1} \int_{S(\mathbb{C}^n)} \overline{f(z)} f'(z) \, dS(\mathbb{C}^n), \quad f, f' \in P_{d,n}, $$

where $dS(\mathbb{C}^n)$ is the normalized volume form of the sphere $S(\mathbb{C}^n)$ so that $\mathrm{Vol}(S(\mathbb{C}^n)) = 1$. In particular, bounding under the integral sign gives

$$ \|f\|^2 = \binom{d+n-1}{n-1} \int_{S(\mathbb{C}^n)} |f(z)|^2 dS(\mathbb{C}^n) \le \binom{d+n-1}{n-1} \|f\|_{\infty}^2, \quad f \in P_{d,n}. \quad (4.1) $$

This yields the following lower bound on the best rank-one approximation ratio of the space of complex symmetric tensors.

**Proposition 4.1.** For any $d \ge 1$ and $n \ge 2$

$$ \mathcal{A}(\mathrm{Sym}^d(\mathbb{C}^n)) \ge \max \left\{ \binom{d+n-1}{n-1}^{-1/2}, \frac{1}{\sqrt{n^{d-1}}} \right\}. \quad (4.2) $$

*Remark 4.2.* For a fixed $n$ the bound (4.2) is better than (1.7) when $d$ is sufficiently large,

$$ 
\begin{aligned}
\mathcal{A}(\mathrm{Sym}^d(\mathbb{C}^n)) &\ge \binom{d+n-1}{n-1}^{-1/2} = \sqrt{(n-1)!} \sqrt{\frac{\Gamma(d+1)}{\Gamma(d+n)}} \\
&= \frac{\sqrt{(n-1)!}}{\sqrt{d^{n-1}}} \left(1 + \mathcal{O}\left(\frac{1}{d}\right)\right) \gg \frac{1}{\sqrt{n^{d-1}}}, \quad d \to \infty.
\end{aligned}
$$
Similar bounds can be derived for real forms. A result from [20] (see also [11, (17.5)]) asserts that the complex and the real uniform norms of $f \in P_{d,n}$ are linked by

$$ \|f\|_{\infty, \mathbb{C}} = \max_{z \in \mathbb{S}(\mathbb{C}^n)} |f(z)| \le \sqrt{2^d} \max_{x \in \mathbb{S}(\mathbb{R}^n)} |f(x)| = \sqrt{2^d} \|f\|_{\infty, \mathbb{R}}. \quad (4.3) $$

Combining this with (4.1) gives

$$ \|f\|^2 \le \binom{d+n-1}{n-1} \|f\|^2_{\infty, \mathbb{C}} \le 2^d \binom{d+n-1}{n-1} \|f\|^2_{\infty, \mathbb{R}}, \quad f \in P_{d,n}(\mathbb{R}), $$

and hence we obtain the following bound on the best rank-one approximation ratio for real symmetric tensors.

**Proposition 4.3.** For any $d \ge 1$ and $n \ge 2$,

$$ \mathcal{A}(\mathrm{Sym}^d(\mathbb{R}^n)) \ge \max \left\{ \frac{1}{\sqrt{2^d}} \binom{d+n-1}{n-1}^{-1/2}, \frac{1}{\sqrt{n^{d-1}}} \right\}. \quad (4.4) $$

*Remark 4.4.* For a fixed $n > 2$ and a large $d$ the bound (4.4) is still better than (1.7),

$$ \begin{aligned} \mathcal{A}(\mathrm{Sym}^d(\mathbb{R}^n)) &\ge \frac{1}{\sqrt{2^d}} \binom{d+n-1}{n-1}^{-1/2} = \frac{\sqrt{(n-1)!}}{\sqrt{2^d}} \sqrt{\frac{\Gamma(d+1)}{\Gamma(d+n)}} \quad (4.5) \\ &= \frac{\sqrt{(n-1)!}}{\sqrt{2^d d^{n-1}}} \left(1 + O\left(\frac{1}{d}\right)\right) \gg \frac{1}{\sqrt{n^{d-1}}}, \quad d \to \infty. \end{aligned} $$

## References

[1] A. Agrachev, Kh. Kozhasov, and A. Uschmajew. Chebyshev polynomials and best rank-one approximation ratio. *SIAM J. Matrix Anal. Appl.*, 41(1):308–331, 2020.

[2] S. Banach. Über homogene Polynome in $(L^2)$. *Studia Math.*, 7:36–44, 1938.

[3] P. Bürgisser and F. Cucker. *Condition*, volume 349 of *Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences]*. Springer, Heidelberg, 2013. The geometry of numerical algorithms.

[4] F. Cobos, T. Kühn, and J. Peetre. On $\mathfrak{G}_p$-classes of trilinear forms. *Journal of the London Mathematical Society*, 59(3):1003–1022, 1999.

[5] F. Cucker, A. A. Ergür, and J. Tonelli-Cueto. Functional norms, condition numbers and numerical algorithms in algebraic geometry, 2021. arXiv:2102.11727.

[6] A. Erdélyi and F. G. Tricomı. The asymptotic expansion of a ratio of gamma functions. *Pacific Journal of Mathematics*, 1(1):133 – 142, 1951.

[7] S. Friedland. Best rank one approximation of real symmetric tensors can be chosen symmetric. *Frontiers of Mathematics in China*, 8, 10 2011.

[8] S. Friedland, V. Mehrmann, R. Pajarola, and S. K. Suter. On best rank one approximation of tensors. *Numer. Linear Algebra Appl.*, 20:942–955, 2013.
[9] S. Friedland and V. Tammali. Low-rank approximation of tensors. In P. Benner, M. Bollhöfer, D. Kressner, C. Mehl, and T. Stykel, editors, *Numerical Algebra, Matrix Theory, Differential-Algebraic Equations and Control Theory*. Springer, Cham., 2015.

[10] C. J. Hillar and L.-H. Lim. Most tensor problems are NP-hard. *J. ACM*, 60(6), 2013.

[11] D. Khavinson and E. Lundberg. *Linear Holomorphic Partial Differential Equations and Classical Potential Theory*. Mathematical surveys and monographs. American Mathematical Society, 2018.

[12] D. E. Knuth. *The art of computer programming. Vol. 1*. Addison-Wesley, Reading, MA, 1997. Fundamental algorithms, Third edition [of MR0286317].

[13] T. G. Kolda and B. W. Bader. Tensor decompositions and applications. *SIAM Review*, 51(3):455–500, 2009.

[14] E. Kostlan. On the expected number of real roots of a system of random polynomial equations. *Foundations of Computational Mathematics*, pages 149–188, 2000.

[15] T. Kühn and J. Peetre. Embedding constants of trilinear Schatten-von Neumann classes. *Proc. Est. Acad. Sci. Phys. Math.*, 55(3):174–181, 2006.

[16] Z. Li, Y. Nakatsukasa, T. Soma, and A. Uschmajew. On orthogonal tensors and best rank-one approximation ratio. *SIAM J. Matrix Anal. Appl.*, 39(1):400–425, 2018.

[17] Z. Li and Y. B. Zhao. On norm compression inequalities for partitioned block tensors. *Calcolo*, 57(11), 2020.

[18] L. Qi. The best rank-one approximation ratio of a tensor space. *SIAM J. Matrix Anal. Appl.*, 32(2):430–442, 2011.

[19] L. Qi and Z. Luo. *Tensor Analysis: Spectral Theory and Special Tensors*. Society for Industrial and Applied Mathematics, Philadelphia, PA, 2017.

[20] J. Siciak. Holomorphic continuation of harmonic functions. *Ann. Polon. Math.*, 29:67–73, 1974. Collection of articles dedicated to the memory of Tadeusz Waźewski.

[21] E.M. Stein and G. Weiss. *Introduction to Fourier Analysis on Euclidean Spaces*. Mathematical Series. Princeton University Press, 1971.

[22] R. Tomioka and T. Suzuki. Spectral norm of random tensors, 2014. arXiv:1407.1870.

[23] A. Uschmajew. Some results concerning rank-one truncated steepest descent directions in tensor spaces. *2015 International Conference on Sampling Theory and Applications*, pages 415–419, 07 2015.

[24] R. Vershynin. *High-dimensional probability: An introduction with applications in data science*, volume 47 of *Cambridge Series in Statistical and Probabilistic Mathematics*. Cambridge University Press, Cambridge, 2018.

# A Appendix

For the sake of completeness we include a proof of Proposition 3.1 and of the formula (3.5). The latter is needed in the proof of Theorem 3.4.
## A.1 Proof of Proposition 3.1

The proof follows the lines of [24, Proposition 2.5.2]. We give a more detailed proof than the one given in [5, Proposition 4.24].

We begin with the first statement. Fix $\lambda > 0$. Then Markov's inequality implies that

$$ \mathbb{P}(|t| \ge t) = \mathbb{P} \left( e^{\lambda^2 t^2} \ge e^{\lambda^2 t^2} \right) \le e^{-\lambda^2 t^2} \mathbb{E} e^{\lambda^2 t^2}. $$

Now, the Taylor expansion of the exponential function, standard facts from calculus and our assumptions yield

$$ \mathbb{E} e^{\lambda^2 t^2} = \sum_{p=0}^{\infty} \frac{\lambda^{2p} \mathbb{E} t^{2p}}{p!} \le \sum_{p=0}^{\infty} \frac{(\lambda^2 2p K^2)^p}{p!}. $$

With $\lambda = \frac{1}{\sqrt{8K}}$ we obtain that

$$ \mathbb{P}(|t| \ge t) \le e^{-\frac{t^2}{8K^2}} \sum_{p=0}^{\infty} \frac{(p/4)^p}{p!}. $$

Now, by direct computation, $\sum_{p=0}^{\infty} \frac{(p/4)^p}{p!} \approx 1.5561...$, which proves the first assertion. For the second statement, by [24, Lemma 1.2.1] we write

$$ \mathbb{E} |t|^p = \int_0^\infty \mathbb{P}(|t|^p \ge u) \, du = \int_0^\infty p t^{p-1} \mathbb{P}(|t| \ge t) \, dt. $$

The assumptions imply that for $t \ge K\sqrt{2\ln C}$ we have

$$ \mathbb{P}(|t| \ge t) \le e^{\ln C - \frac{t^2}{K^2}} \le e^{-\frac{t^2}{2K^2}}. \quad (A.1) $$

Therefore,

$$ \begin{aligned} \mathbb{E} |t|^p &= \int_0^{K\sqrt{2\ln C}} p t^{p-1} \mathbb{P}(|t| \ge t) \, dt + \int_{K\sqrt{2\ln C}}^{\infty} p t^{p-1} \mathbb{P}(|t| \ge t) \, dt \\ &\le K^p (2 \ln C)^{\frac{p}{2}} + \int_0^{\infty} p t^{p-1} e^{-\frac{t^2}{2K^2}} \, dt \\ &\le K^p (2 \ln C)^{\frac{p}{2}} + p K^p 2^{\frac{p}{2}-1} \Gamma(\frac{p}{2}), \end{aligned} $$

where in the first integral we estimate $\mathbb{P}(|t| \ge t)$ by 1 and to bound the second integral we apply (A.1) and then extend the domain of the integration.

Using induction on $p$ we bound $p2^{\frac{p}{2}-1}\Gamma(p/2)$ by $(\pi p/2)^{\frac{p}{2}}$, which gives

$$ \mathbb{E} |t|^p \le K^p \left( (2 \ln C)^{\frac{p}{2}} + \left(\frac{\pi p}{2}\right)^{\frac{p}{2}} \right) \le K^p \left( (2 \ln C)^{\frac{p}{2}} + \left(\frac{\pi}{2}\right)^{\frac{p}{2}} \right) p^{\frac{p}{2}}. $$

Finally, the claim follows from the inequality comparing the $\ell_p$- and $\ell_1$-norms.
## A.2 Proof of (3.5)

Because of the “product”-like structure of $\mathrm{IO}$ it is enough to consider the case $d = 1$,

$$ \mathrm{IO}: \mathbb{R}^{n-1} \to \mathbb{S}^{n-1} \\ x \mapsto \frac{1}{\sqrt{1 + \|x\|_2^2}} \begin{pmatrix} 1 \\ x \end{pmatrix}, $$

and to prove

$$ |\det D_x \mathrm{IO}| = (1 + \|x\|_2^2)^{-\frac{n}{2}}, \quad x \in \mathbb{R}^{n-1}, \qquad (A.2) $$

where $D_x \mathrm{IO}$ is written in some orthonormal bases of $T_x \mathbb{R}^{n-1}$ and $T_{\mathrm{IO}(x)} \mathbb{S}^{n-1}$.

We fix $x \neq 0$, as for $x = 0$ the claim follows by continuity. Let us consider an orthonormal basis of $T_x \mathbb{R}^{n-1}$ given by

$$ \frac{x}{\|x\|_2}, v_1, \dots, v_{n-2}, $$

where $v_1, \dots, v_{n-2}$ form a basis of the orthogonal complement of the line $\mathbb{R}x \subset \mathbb{R}^{n-1}$. Then vectors

$$ \frac{1}{\sqrt{1 + \|x\|_2^2}} \begin{pmatrix} -\|x\|_2 \\ x/\|x\|_2 \end{pmatrix}, \begin{pmatrix} 0 \\ v_1 \end{pmatrix}, \dots, \begin{pmatrix} 0 \\ v_{n-2} \end{pmatrix} $$

form an orthogonal basis of $T_{\mathrm{IO}(x)} \mathbb{S}^{n-1}$. A direct computation shows that

$$ \begin{aligned} D_x \mathrm{IO} \left( \frac{x}{\|x\|_2} \right) &= \left. \frac{d}{dt} \right|_{t=0} \mathrm{IO} \left( x + t \frac{x}{\|x\|_2} \right) \\ &= \left. \frac{d}{dt} \right|_{t=0} \left[ \frac{1}{\sqrt{1 + \|x\|_2^2 + 2t\|x\|_2 + t^2}} \left( x + t \frac{x}{\|x\|_2} \right) \right] \\ &= \frac{1}{1 + \|x\|_2^2} \frac{1}{\sqrt{1 + \|x\|_2^2}} \left( \frac{-\|x\|_2}{x/\|x\|_2} \right), \end{aligned} $$

$$ \begin{aligned} D_x \mathrm{IO} (v_i) &= \left. \frac{d}{dt} \right|_{t=0} \mathrm{IO} (x + t v_i) = \left. \frac{d}{dt} \right|_{t=0} \left[ \frac{1}{\sqrt{1 + \|x\|_2^2 + t^2}} \begin{pmatrix} 1 \\ x + t v_i \end{pmatrix} \right] \\ &= \frac{1}{\sqrt{1 + \|x\|_2^2}} \begin{pmatrix} 0 \\ v_i \end{pmatrix}, \quad i = 1, \dots, n-2. \end{aligned} $$

Finally, the desired formula (A.2) follows from the fact that in the chosen orthonormal bases of $T_x \mathbb{R}^{n-1}$ and $T_{\mathrm{IO}(x)} \mathbb{S}^{n-1}$ the differential $D_x \mathrm{IO}$ is given by the matrix

$$ \begin{pmatrix} \frac{1}{1+\|x\|_2^2} & & 0 \\ & \frac{1}{\sqrt{1+\|x\|_2^2}} & \\ 0 & & \frac{1}{\sqrt{1+\|x\|_2^2}} \end{pmatrix}. $$