6
$\begingroup$

Recently I stumbled upon the following theorem — I'd like to read a comprehensible (i.e. understandable for an engineer) proof for it:

Given a polynomial $F(t)$ of degree $n$, there exists a unique equivalent symmetric, multiaffine polynomial $f(u_1, u_2, \ldots, u_n)$ — $u_i$ all of degree $1$ — satisfying $f(t,t,\dots,t) = F(t)$. This $f(u_1,u_2,\ldots,u_n)$ is called the polar form of $F(t)$.

So for example,

$F(t) = 5t^3 + 6t^2 + 9t - 2$

Is equivalent to

$\begin{align}f(u,v,w) & = c_1 uvw + c_2 uv + c_3 uw + c_4 vw + c_5u + c_6v +c_7w + c_8 \\ & = 5uvw + 2uv + 2uw + 2vw + 3u + 3v + 3w -2 \end{align}$

Which is clearly symmetric (i.e. $f(u,v,w) = f(w,u,v) = f(v,w,u) = \ldots$). This multiaffine (in fact, triaffine) function is equal to $F(t)$ when $u,v,w$ all have value $t$, resulting in $f(t,t,\ldots,t)$.

What I understand, is that the "multiaffine" property says that when you keep every $u_i$ of $f(u_1,u_2,\ldots,u_n)$ constant, except for one $u_j$, then this $f$ is an affine function in this variable $u_j$. So then it would be just a line which is traversed with a constant speed, right?

For some reason, $f(t,t,\ldots,t)$ — which is equal to $F(t)$ as said before — is called the diagonal (form) of $f$. I can imagine a diagonal in a 3D (or 2D) coordinate system where $u=v=w$, this would in a certain sense be a diagonal of the coordinate system. Is this the reason why it's called "diagonal (form)"?

So my question, where can I find a good proof for the above theorem?

Edit: Furthermore, I'd like to refresh my knowledge of affine spaces, functions, combinations... (e.g. why is it that for an affine combination of points resulting in a new point, the coefficients have to add up to 1 — and when combining them into a vector, they have to add up to 0). Any recommendations for readable books/articles are most welcome!

Edit2: Although Gerry has provided a nice solution, I'd like to know why there is such a difference between his proof and Ramshaw's (the link to that proof is in the comments). For some reason, he uses multiple variables for the function $F$, and the multinomial coefficient. Why is that? Oh, and if anybody has some thoughts about accessible literature on affine things, please let me know.

$\endgroup$
1
  • $\begingroup$ Comment: I only found one proof for the theorem, given by Lyle Ramshaw. But as he already mentions himself, the article might be a little too mathematically involved for engineers. Indeed, the provided proof is too concise for me to understand. $\endgroup$
    – Ailurus
    May 31, 2012 at 23:33

4 Answers 4

5
$\begingroup$

I think you have the right idea as to why the term, "diagonal".

As for the theorem, suppose $$F(t)=a_0t^n+a_1t^{n-1}+\cdots+a_{n-1}t+a_n$$ with $a_0\ne0$. Now pick any term there, say, $a_{n-k}t^k$, and think of all the ways of choosing $k$ of the variables $u_1,u_2,\dots,u_n$, and forming their product; let's say there are $C$ ways to do this (more about $C$, later). Well, if you give each product the coefficient $a_{n-k}/C$, then the sum of these terms will be a symmetric sum of $C$ terms, each with coefficient $a_{n-k}/C$. Now when you let $u_j=t$ for all $j$, you get a sum of $C$ terms, each of which is $(a_{n-k}/C)t^k$, so in total you get $a_{n-k}t^k$, which is what you want.

In your example, $n=3$, let's look at the term $6t^2$. Now $C=3$ because there are 3 ways to choose 2 of the variables $u,v,w$ to form their product, namely, $uv$, $uw$, and $vw$, and $a_1$, the coefficient of $t^2$, is 6, and $6/3=2$, and that's why we want $2uv+2uw+2vw$ in the symmetric polynomial.

In general, what I've called $C$ is the binomial coefficient $n\choose k$ which has the simple formula, $${n\choose k}={n!\over k!(n-k)!}$$ where I take it you are au courant with factorials.

$\endgroup$
4
  • $\begingroup$ Thanks for your answer! It's quite clear, but when I compare it to Ramshaw's proof, it almost seems too easy. Because, for some reason, he involves multinomial coefficients (and multiple variables for the function $F$, while our $F(t)$ only uses $t$ as variable). His paper is called Blossoming: A Connect-the-Dots Approach to Splines, the proof is on page 10. Could you perhaps have a look at it? $\endgroup$
    – Ailurus
    Jun 1, 2012 at 7:27
  • $\begingroup$ You haven't given me any idea where to find this paper. $\endgroup$ Jun 1, 2012 at 7:31
  • $\begingroup$ Sorry, I should've included a link: www.cgl.uwaterloo.ca/~smann/Papers/SRC-019.pdf $\endgroup$
    – Ailurus
    Jun 2, 2012 at 11:33
  • $\begingroup$ I'll have a look, but it might be a few days. $\endgroup$ Jun 2, 2012 at 13:01
4
$\begingroup$

A shorter explanation ...

In your given polynomial, replace every term $t^r$ by the expression

$$S_r(t_1, \ldots, t_n)/{n \choose r}$$

where $S_r(t_1, \ldots, t_n)$ is the elementary symmetric polynomial of degree $r$ in the variables $t_1, \ldots, t_n$. So ...

$$ t \rightarrow (t_1 + \cdots + t_n)/n$$ $$ t^2 \rightarrow (t_1t_2 + t_1t_2 + \cdots + t_{n-1}t_n)/{n\choose 2} $$ $$ t^n \rightarrow t_1t_2 \ldots t_n$$

and so on. By construction, the resulting expression is symmetric and has the correct "diagonal". It's really very simple and elementary. Ramshaw's explanation is overly formal and notation-heavy (by my tastes, anyway).

The first uses of "blossoming" were by de Casteljau in the 1960's. His papers make heavy use of symmetric functions, but they are very difficult to read. Ramshaw's paper rediscovered the idea and gave it the name "blossoming". To a mathematician, a "blossom" is just a "polar form" (and, in fact, this is what de Casteljau called them). There are many newer accounts of blossoming that are much easier to read than Ramshaw's.

$\endgroup$
3
  • $\begingroup$ Thanks! The only thing that is still a little confusing are the multi-affine, or $n$-affine, maps. Any good references for that? Or for the newer accounts on blossoming? $\endgroup$
    – Ailurus
    Jun 3, 2012 at 13:08
  • $\begingroup$ cgafaq.info/wiki/Blossoming (despite the broken stuff). Farin's book is very good. Just google "blossom bezier". $\endgroup$
    – bubba
    Jun 4, 2012 at 2:37
  • $\begingroup$ The maps have to be multi-affine so that they correspond to the convex combination steps in the de Casteljau construction of a Bezier curve. Just think of the variables in the blossom as a clever and convenient way of labeling the points that are produced during the de Casteljau algorithm. $\endgroup$
    – bubba
    Jun 4, 2012 at 2:40
3
$\begingroup$

You may wish to check out Curves and Surfaces in Geometric Modeling by Jean Gallier. (See Chapter 4 especially.) The exposition there may be right at the level you're after, and since the book has gone out of print, the author has made a manuscript freely available at http://www.cis.upenn.edu/~jean/gbooks/geom1.html.

$\endgroup$
2
$\begingroup$

An Introduction to Polar Forms by Hans-Peter Seidel, University of Erlangen in Computer-Aided Geometric Design IEEE Computer Graphics & Applications p.39

Blossoming Principle

Polynomials F of degree n and symmetric multiaffine maps f are equivalent to each other.

In this situation f is called the multiaffine polar form or blossom of F, while F is called the diagonal of f.

Furthermore, the qth derivative of F can be given in terms of f.

$\endgroup$
1
  • $\begingroup$ In this 1999 paper, Seidel offers some encouragement, "Why are polar forms useful? Polar forms simplify the theory of Bezier curves and B-splines to such a state that most results become almost trivial." $\endgroup$
    – Model_Math
    Nov 5, 2014 at 13:16

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .