Take the 2-minute tour ×

Let A, B and C be finitely supported probability distributions with at most d nonzero probabilities each. Now consider the following simultaneous equations using p-norms, for each value of p≥1, given by

||A||p + ||B||p = ||C||p

where A, B and C are still non-negative, but we relax normalization on A and B. Imagine that C is fixed and, without loss of generality, normalized. We want to solve for A and B.

First, note that one obvious family of solutions is

A = (1-x) C , B = x C , 0≤x≤1 .

Question: Ignoring the obvious permutation symmetries, are these the only solutions?

Edit: By p-norm, I mean the vector p-norm: ||A||p = (∑j |aj|p )1/p. Although we don't really need the absolute values, since the aj are all non-negative.

share|improve this question
Can you clarify somewhat? I'm not sure I understand what you mean A, B, and C to be. I thought at first you meant A, B, C to be discrete random variables taking on at most d values, and $\Vert A \Vert_p = (E |A|^p)^{1/p}$, but then I have no idea what you mean by "relax normalization on A and B". –  Mark Meckes Dec 11 '09 at 0:35
Mark: He means that the total measure of A need not be 1, and the same for B. –  Greg Kuperberg Dec 11 '09 at 14:41
Okay, so I guess $A,B,C$ are finite measures with finite support. Then what is $\Vert A \Vert_p$ supposed to be? –  Mark Meckes Dec 11 '09 at 14:47
It's just what you think: $\|A\|_p = (\sum_{j=1}^d |a_j|^p )^{1/p}$. –  Steve Flammia Dec 12 '09 at 2:28
That's actually completely different from what I originally thought. I was confused because that's not the kind of p-norm one usually sees in probability. –  Mark Meckes Dec 12 '09 at 15:12

2 Answers 2

up vote 11 down vote accepted

Here is a proof that Steve's rescaling gives you all solutions, together with the trivial operation of permuting the components of $A$, $B$, and $C$ if you view them as vectors with positive coeifficients. (If you view them this way, then Steve's notation $||A||_p$ is just the usual $p$-norm.)

I first tried what Alekk tried: You can take the limit as $p \to \infty$ and eventually obtain certain power series expansions in $1/p$. Or you can take the limit $p \to 0$ and obtain certain power series expansions in $p$. The problem with both approaches is that the information in the terms of these expansions is complicated. To help understand the second limit, I observed that the two sides of Steve's equation are analytic in $p$, but it only helped so much.

Then I realized that when you have a complex analytic function of one variable, you can get a lot of information from looking at singularities. So let's look at that. Let $\alpha_k = \ln a_k$, so that $$||A||_p = \exp\left( \frac{\ln \bigl[\exp(\alpha_1 p) + \exp(\alpha_2 p) + \cdots + \exp(\alpha_d p) \bigr]}{p} \right).$$ The expression inside the logarithm has been called an exponential polynomial in the literature, which I'll call $a(p)$. As indicated, $||A||_p$ has a logarithmic singularity when $a(p) = 0$. $||A||_p$ has another kind of singularity when $p = 0$, but won't matter for anything. Also $a(p)$ is an entire function, which means in particular that it is univalent and has isolated zeroes. Also, none of the zeroes of $a(p)$ are on the real axis. Let $b(p)$ and $c(p)$ be the corresponding exponential polynomials for $B$ and $C$.

Suppose that you follow a loop that starts on the positive real axis, encircles an $m$-fold zero of $a(p)$ at $p_0$, and then retraces to its starting point. Then the value of $||A||_p$, which is non-zero for $p > 0$, gains a factor of $\exp(2m\pi i/p_0)$. Thus Steve's equation is not consistent unless all three of $a(p)$, $b(p)$ and, $c(p)$ have the same zeroes with the same multiplicity. (Since $\exp(2m\pi i/p_0)$ cannot have norm 1, geometric sequences with this ratio but with different values of $m$ are linearly independent.)

At this point, the problem is solved by a very interesting paper of Ritt, On the zeros of exponential polynomials. Ritt reviews certain results of Tamarkin, Polya, and Schwengler, which imply in particular that if an exponential polynomial $f(z)$ does not have any zeroes, then it is a monomial $f_\alpha \exp(\alpha z)$. Ritt's own theorem is that if $f(z)$ and $g(z)$ are exponential polynomials, and if the roots of $f(z)$ are all roots of $g(z)$ (with multiplicity), then their ratio is another exponential polynomial. Thus in our situation $a(p)$, $b(p)$, and $c(p)$ are all proportional up to a constant and an exponential factor. Thus, $A$, $B$, and $C$ must be the same vectors up to permutation, repetition, and rescaling of the coordinates. Repetition is an operation that hasn't yet been analyzed. If $A^{\oplus n}$ denotes the $n$-fold repetition of $A$, then $||A^{\oplus n}||_p = n^{1/p}||A||_p$. Again, since geometric sequences with distinct ratios are linearly independent, Steve's equation is not consistent if $A$, $B$, and $C$ are repetitions of the same vector by different amounts.

The same argument works for the generalized equation $$x_1||A_1||_p + x_2||A_2||_p + \cdots + x_n||A_n||_p = 0.$$ The result is that any such linear dependence trivializes, after rescaling the vectors and permuting their coordinates.

Update (by J.O'Rourke): Greg's paper based on this solution was just published:

"Norms as a function of $p$ are linearly independent in finite dimensions," Amer. Math. Monthly, Vol. 119, No. 7, Aug-Sep 2012, pp. 601-3 (JSTOR link).

share|improve this answer
That's a very nice solution. I would have never guessed that expressing the p-norm in that way would be productive. –  Steve Flammia Dec 21 '09 at 20:38
Thanks for saying so! Note that the driving idea is analytic continuation in $p$. In my thinking, the specific expression appeared only as a corollary of that strategy. (On the other hand, there isn't any other direct definition of exponentiation with an irrational exponent.) –  Greg Kuperberg Dec 21 '09 at 21:11
Somehow the claim that "norms as a function of $p$ are linearly independent" reminds me of this question: mathoverflow.net/questions/31458/… Maybe your approach can actually also answer that question? (I might be wrong because I've read both only superficially) –  Suvrit Aug 18 '12 at 10:30
For those (like me) who don't have an AMM subscription, Greg's preprint is on arXiv: arxiv.org/abs/1102.5026 –  Willie Wong Aug 22 '12 at 12:12

if you suppose that all the $a_i$, all the $b_i$, and all the $c_i$ are distinct, can't you do that by induction ? One can assume wlog that $a_1 > \ldots > a_d > 0$ and $b_1 > \ldots > b_d > 0$ etc.. so that taking $p \to \infty$ you can see that $a_1+b_1=c_1$. Hence $$a_1\left(1+\sum_2^d \left(\frac{a_k}{a_1}\right)^p\right)^{1/p} + b_1\left(1+\sum_2^d \left(\frac{b_k}{b_1}\right)^p\right)^{1/p} = c_1\left(1+\sum_2^d \left(\frac{c_k}{c_1}\right)^p\right)^{1/p}$$ and a Taylor expansion for $p \to \infty$ tells you that $\frac{a_2}{a_1}=\frac{b_2}{b_1}=\frac{c_2}{c_1}$. Continuing this way, one can see that the only family of solutions is $A=\lambda C$ and $B=(1-\lambda) C$. Too simple to be true ?

share|improve this answer
Perhaps this is an entirely rigorous approach, but I just don't see it. (Sorry if I'm slow... I'm not a mathematician.) –  Steve Flammia Dec 14 '09 at 15:49
There's probably a way to make something like this approach work, but I don't know what Alekk means by "a Taylor expansion for $p\to \infty$" here. –  Mark Meckes Dec 15 '09 at 14:46

Your Answer


