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.

  • $\begingroup$ 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". $\endgroup$ – Mark Meckes Dec 11 '09 at 0:35
  • $\begingroup$ Mark: He means that the total measure of A need not be 1, and the same for B. $\endgroup$ – Greg Kuperberg Dec 11 '09 at 14:41
  • $\begingroup$ Okay, so I guess $A,B,C$ are finite measures with finite support. Then what is $\Vert A \Vert_p$ supposed to be? $\endgroup$ – Mark Meckes Dec 11 '09 at 14:47
  • $\begingroup$ It's just what you think: $\|A\|_p = (\sum_{j=1}^d |a_j|^p )^{1/p}$. $\endgroup$ – Steve Flammia Dec 12 '09 at 2:28
  • $\begingroup$ 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. $\endgroup$ – Mark Meckes Dec 12 '09 at 15:12

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).

  • 1
    $\begingroup$ That's a very nice solution. I would have never guessed that expressing the p-norm in that way would be productive. $\endgroup$ – Steve Flammia Dec 21 '09 at 20:38
  • 2
    $\begingroup$ 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.) $\endgroup$ – Greg Kuperberg Dec 21 '09 at 21:11
  • $\begingroup$ 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) $\endgroup$ – Suvrit Aug 18 '12 at 10:30
  • 1
    $\begingroup$ For those (like me) who don't have an AMM subscription, Greg's preprint is on arXiv: arxiv.org/abs/1102.5026 $\endgroup$ – 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 ?

  • $\begingroup$ Perhaps this is an entirely rigorous approach, but I just don't see it. (Sorry if I'm slow... I'm not a mathematician.) $\endgroup$ – Steve Flammia Dec 14 '09 at 15:49
  • $\begingroup$ 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. $\endgroup$ – Mark Meckes Dec 15 '09 at 14:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.