Examples of norms essentially different from $p$-norms

I'm looking for examples of norms that can be applied to finite-dimensional vectors but are not just $p$-norms or trivial variations of them. The ones I've found - the norms in James' space or Tsirelson's space - only make sense for infinite dimensions.

To be more precise, I'm looking for norms which are not of the form $\|v\| := \|Av\|_p$ for some positive definite matrix $A$, or $\|v\| := \lambda \|v\|_p + (1-\lambda)\|v\|_q$.

The only example I've found so far is the norm defined as $$\|v\|^{(k)} := \sum_{i=1}^k \max_j{}^{\!(i)} |v_j|,$$ where $\max^{(i)}$ is the $i$th largest element.

There must be more interesting norms. Any ideas?

• Have you considered the various matrix norms? Matrices are finite-dimensional vectors, after all. Feb 28 '18 at 12:04
• Yes, I have. But to get an interesting matrix norm you'd need to reshape the vector into a rectangular matrix, which will only work if the dimension is not a prime number, or if you pad the vector with zeroes until the dimension is nice. I was hoping for something less contrived. Feb 28 '18 at 13:18

A norm is uniquely determined by its unit ball, and conversely, you can define a norm to have any unit ball you like. The construction goes like this. Let $K\subset \mathbb{R}^n$ be a closed, bounded, convex, and symmetric set ($x\in K$ if and only if $-x\in K$). Define

$$\|x\|_K = \inf\{\lambda > 0 \, |\, x \in \lambda K\}.$$

This is called the Minkowski functional, and $\|\cdot \|_K$ is a semi-norm. If you also assume $K$ contains an open neighborhood of the origin, then $\|\cdot \|_K$ is a norm, and the unit ball for the norm is exactly $K$.

So basically you can select any $K$ (within reason) and define a norm for which $K$ is the unit ball. Every norm can be constructed in this way, so it is very general and generates "new" norms that are not just $p$ norms.

As an example, let $X_m$ be a collection of $m$ independent and identically distributed random variables $\mathbb{R}^n$ with a Lebesgue density, and set

$$K_m = \text{ConvexHull} (-X_m \cup X_m).$$

Then define the norm $\|x\|_{K_m}$. This is a norm with a unit ball that is a random convex polytope (provided $2m \geq n+1$).

A concrete example is the $n$-dimensional polytope with vertices of the form $$\frac{1}{\sqrt k} \sum_{i=1}^k s_{\sigma(i)} e_{\sigma(i)}$$ for all $k \le n$, all signs $s$ and permutations $\sigma$. It has $\sum_{i=1}^n {n \choose i}2^i$ vertices.

• Can you add a concrete example of an interesting $K$? Mar 1 '18 at 12:52
• There are an infinity of possible examples; I don't know what you find interesting. I added an example where the unit ball is a random polytope.
– Jeff
Mar 1 '18 at 14:58
• Yes, there is an infinity of possible examples, this is exactly the problem. "Interesting" is left for you to decide, but I had something more concrete in mind than a random polytope. Mar 1 '18 at 15:30
• @MateusAraújo Jeff answered exactly your question as it was formulated above. Even more, he gave you a tool to find all norms. Which are "essentially different" or "interesting" is up to you. Almost all norms described this way are unlike the $p$-norms, e.g. taking as unit circle a regular polygon on even many sides. Either you edit the question or you post a new qustion with your actual restriction. Because I see no way to answer this one other than Jeff did. Mar 4 '18 at 2:00
• I suppose then you do not consider $\|x\|_p:= (\sum |x_i|^p)^{1/p}$ an example of a norm until it is instantiated by choosing a value for $p$?
– Jeff
Mar 4 '18 at 19:50

Take any norm $\nu$ on a function space and then define $$\Vert(a_1,\ldots,a_n)\Vert=\nu\left(t\mapsto\sum_{k=1}^na_kt^{k-1}\right).$$ For example $$\Vert(a_1,\ldots,a_n)\Vert=\sup_{t\in[0,1]}\left\vert\sum_{k=1}^na_kt^{k-1}\right\vert$$ Or $$\Vert(a_1,\ldots,a_n)\Vert=\int_{0}^1\left\vert\sum_{k=1}^na_kt^{k-1}\right\vert \omega(t) dt$$ For some positive weight $\omega$.

• I haven't done a proof, but I'm pretty sure both your examples reduce to $\|v\|=\|Av\|_p$ for some positive definite matrix $A$. Mar 1 '18 at 13:25
• I doubt this is the case, especially with the first example where $\nu$ is arbitrary.
– Jeff
Mar 1 '18 at 15:51
• I think you missed the "both of your examples" part of my sentence. Mar 1 '18 at 16:02
• I still doubt either example is in the form you suggested. If you think it is, give a proof.
– Jeff
Mar 1 '18 at 16:09
• Well, Felix Klein is the one proposing this as an example of a norm which is not of the undesired form, I think the burden of proof lies with him. Mar 1 '18 at 17:07

I still would like to have some more "natural" examples of such norms, specifically those with smooth and permutation-symmetric unit balls. Using the Minkowski functional, as explained by Jeff, allows me to define a norm from any convex body which is closed, convex, and symmetric. Playing around I found two nice unit balls. One is

$$K_\text{exp} = \{x \in \mathbb R^n: \frac{1}{e+n-1}\sum_{i=1}^n e^{x_i^2} \le 1\},$$ for which it is really difficult to calculate the corresponding norm $\|\cdot\|_\text{exp}$ for any non-trivial vector. The cases I could solve analytically are $$\|1^{(n)}\|_\text{exp} = \frac{1}{\sqrt{\log(1+(e-1)/n)}}$$ where $1^{(n)}$ is the vector of all ones, and for the vector $(1,\sqrt{2})$ we have $$\|(1,\sqrt{2})\|_\text{exp} = \frac{1}{\sqrt{\log(-\frac12+\frac12\sqrt{5+4e})}}.$$ The other unit ball is $$K_\text{log} = \{x \in \mathbb R^n: \frac12\prod_{i=1}^n(1+x_i^2)\le 1\},$$ for which I also couldn't get a general formula for an arbitrary vector. For the vector of all ones we have $$\|1^{(n)}\|_\text{log} = \frac{1}{\sqrt{\sqrt[n]{2}-1}},$$ and for an arbitrary 2-dimensional vector $(x,y)$ we have $$\|(x,y)\|_\text{log} = \frac1{\sqrt2}\sqrt{x^2+y^2+\sqrt{x^4+6x^2y^2+y^4}}.$$