I will show, with some non-rigorous steps, that a bound of this form that is valid for arbitrary tensors and useful for sparse tensors (fewer than $n^{k/2}$ nonvanishing entries) does not exist.

First note that there is a problem with using the $\ell^2$ norm to define the spectral norm for very sparse tensors $A$, regardless of how you try to bound it. The reason is that, assuming the nonzero entries of $A$ are normalized to have size $\approx 1$, the minimum value you could possibly hope to bound the spectral norm to is $\approx 1$, by choosing some nonzero entry $A_{n_1n_2 \dots n_k}$ of $A$ and choosing $x$ a sparse vector supported on $n_1,\dots, n_k$.

This means if $x$ is a vector of support of size $m$ and average size $1$, then the $\ell^2$ norm of $x$ is $m^{1/2}$, so the best bound you could hope for on $\langle A, x^{\otimes k} \rangle$ from the spectral norm is $m^{k/2}$. But the trivial bound for $\langle A, x^{\otimes k} \rangle$ is $md$ where $d$ is the maximum degree of $A$ (the maximum number of nonzero entries in a hyperplane slice of $A$). So to get a nontrivial bound you want $m < d^{ \frac{2}{k-2}}$, which is pretty small if $d$ is large!

So I'll use the $\ell^p$ norm instead for the remainder, for some $p\geq k$.

Let $W = \mathbb R^n$ be a real vector space of dimension $n$. Suppose that $f$ is a homogeneous polynomial in the entries of a tensor $A$ in $W^{ \otimes k}$ where we have an inequality of the form
$$ \left(\sup \frac{ \langle A, x^{\otimes k} \rangle}{ |x|_p^k} \right)^{d} \leq f(A) $$

(One could think we should allow absolute values on the right side but we can just square both sides to remove them.)

I will argue rigorously that the coefficient of some monomial in $f$ has size at least $n^{ dk (1/2-1/p)}/ O_{d,k}(1)$ and heuristically that no $f$ with such a large coefficient gives a good bound for highly sparse tensors.

Translating $f$ by any matrix $g$ in the group $ (\mathbb Z/2) \rtimes S_n$ produces a tensor with the same spectral norm. So the minimum of $f( g\cdot A)$ for $g \in (\mathbb Z/2) \rtimes S_n$ for also bounds the spectral norm. It follows that the average of $f(g\cdot A)$ over $g \in (\mathbb Z/2) \rtimes S_n$ also bounds the spectral norm. This average cannot increase the largest coefficient of a monomial in $f$, so we may as well assume $f$ is $(\mathbb Z/2) \rtimes S_n$-invariant.

By scaling, certainly $f$ must be homogeneous of degree $d$.

We can write $f$ as a sum over monomials of the form $\prod_{i=1}^d A_{a_{i,1} \dots a_{i,k}}$ for some tuple $a_{i,j}$ of numbers from $1$ to $n$ indexed by $i$ from $1$ to $d$ and $j$ from $1$ to $k$.

The $(\mathbb Z/2)^n$-invariance implies the coefficient of a monomial vanishes if any number appears an odd number of times among the $a_{i,j}$. The $S_n$-invariance says the coefficients of a monomial depend only on the choice of $a_{i,j}$ up to permutation. We can express this as the claim that $f$ is a linear combination of the polynomials of the form

$$ \sum_{ a \colon [m] \to [n] \textrm{ injective}} \prod_{i=1}^d A_{ a (l_{i,1}) a(l_{i,2}) \dots a(l_{i,j})}$$ for some fixed tuple $l_{i,j}$ of integers from $1$ to $m$ indexed by $i$ from $1$ to $d$ and $j$ from $1$ to $k$, where each number appears an even number of times among the $l_{i,j}$ (which we may assume is at least twice). The sum is over injective maps from the numbers $1$ to $m$ to the numbers $1$ to $n$. We could, if we chose, drop the "injective" condition.

Now let's consider what happens when we apply this inequality to the all-$1$s tensor. This tensor has spectral norm $\frac{n^k}{ n^{ k/p}}$, so the left side is $n^{d k (1-1/p)}$.

The value of the invariant polynomial $\sum_{ a \colon [m] \to [n] \textrm{ injective}} \prod_{i=1}^d A_{ a (l_{i,1}) a(l_{i,2}) \dots a(l_{i,j})} $ is just the number of injective maps from $[m]$ to $n$, which is at most $n^m$.

Because each $\ell$ occurs at least twice among the $\ell_{i,j}$, we have $m \leq d k / 2$.

Thus the sum of the coefficients of these various polynomials in the linear expression for $f$ must be at least $n^{ d k (1/2-1/p)}$. Since the number of different polynomials that can appear depends only on $d$ and $k$, the coefficient of one of the monomials must be at least $n^{ d k (1/2-1/p)}/ (dk)^{dk}$.

Now consider a sparse tensor $A$, say with $N$ nonvanishing entries, each of size $1$. Assuming $A$ comes from some tricky mathematical construction, we are unlikely to get an estimate for $f(A)$ with error term smaller than the largest coefficient of a monomial in $f$ as that would require getting an estimate for a difficult sum with error term less than a single term of the sum.

Thus, we won't expect to get a bound for the spectral norm of $A$ better than $n^{ k (1/2-1/p)}/ (dk)^k \approx n^{ k(1/2-1/p)}$ (assuming $d,k$ grow slowly, which is reasonable).

If we plug a "typical" vector $x$ into $A$, whose entries have size around $1$, we will therefore not get a bound for $\langle A, x^{\otimes k} \rangle$ better than $n^{ k /2}$. But if $N < n^{k/2}$, this is worse than the trivial bound for the sum, so our spectral norm estimate will be useless for such vectors.

One can actually construct an explicit polynomial bound for the spectral norm where the coefficients of the monomials have size $\approx n^{1/2 - 1/p}$ by proving a bound for the $\ell^2$-spectral norm using Cauchy-Schwarz a bunch and then bounding the $\ell^2$ norm trivially via the $\ell^p$ norm.

For $p<1/2$, the lower bound is instead $1$, which I think you can also achieve by using Holder's inequality repeatedly.

An example of the Cauchy-Schwarz argument, for an $n \times n \times n$ tensor:

We have

$$ \left(\sum_{i_1,i_2,i_3 \in [n]} A_{i_1i_2i_3} x_{i_1} x_{i_2} x_{i_3}\right)^8 \leq |x|_2^8 \left( \sum_{i_1 \in [n]} \left( \sum_{i_2, i_3 \in [n]} A_{i_1 i_2 i_3} x_{i_2} x_{i_3} \right)^2 \right)^4 = |x|_2^8 \left( \sum_{i_1 ,i_2 ,i_3,i_4,i_5\in [n]} A_{i_1 i_2 i_3} A_{i_1 i_4 i_5} x_{i_2} x_{i_3} x_{i_4} x_{i_5} \right)^4 \leq |x|_2^{16} \left( \sum_{i_2, i_4\in [n]} \left( \sum_{i_1,i_3,i_5\in [n]} A_{i_1 i_2 i_3} A_{i_1 i_4 i_5} x_{i_3} x_{i_5} \right)^2 \right)^2 =|x|_2^{16} \left(\sum_{ i_1, i_2, i_3,i_4, i_5, i_6, i_7, i_8 \in [n]} A_{i_1 i_2 i_3} A_{i_1 i_4 i_5} A_{i_6 i_2 i_7} A_{i_6 i_4 i_8} x_{i_3} x_{i_5} x_{i_7} x_{i_8} \right)^2 \leq |x|_2^{24} \sum_{i_3, i_5 ,i_7, i_8 \in [n ] } \left( \sum_{i_1, i_2, i_4, i_6 \in [n]} A_{i_1 i_2 i_3} A_{i_1 i_4 i_5} A_{i_6 i_2 i_7} A_{i_6 i_4 i_8} \right)^2$$

which, when you expand it out, should have an elegant symmetric structure where the eight copies of $A$ correspond to the vertices of the cube and the various $i$ indices to edges.

8more comments