1

The question came up under comments to this YT presentation on FFT as a point taken as self evident, and Math SE seems like a natural place to answer it.

The idea is to evaluate a polynomial of degree $n$ at $\pm x_1, \pm x_2, \dots, \pm x_{n/2}$ points.

The example given is $P(x)= 3x^5 + 2x^4 + x^3 + 7 x^2 + 5x +1$ split as $P(x) = (2x^4+7x^2+ 1 x^0) + x (3x^4 + x^2 + 5).$

The next relabeling is confusing:

$$P(x) = (2x^4+7x^2+ 1 x^0) + x (3x^4 + x^2 + 5)=P_{\text{even}}(x^2) + xP_{\text{odd}}(x^2).$$

These even and odd degree polynomials are functions of $x^2$ and hence polynomials of degree $2.$

Here is the transcription of the YT presentation at this time:

... a bonus fact is that since these even and odd polynomials are functions of $x^2$ they are polynomials of degree $2,$ which is a much simpler problem than our original degree $5$ polynomial.

This is totally in line with the points made in comments about the author making reference to the specific example polynomial above. However, it does go on:

Generalizing these observations if we have an $n-1$ degree polynomial that we want to evaluate at $n$ points, we can split the polynomial into even and odd terms with these two smaller polynomials now having degree $n/2 - 1.$

This is also pointed out in the comments, and makes complete sense.

Evidently, the claim is not that $x^4$ is of degree $2,$ or anything outrageous like that. The observation is that this decomposition into even and odd polynomials can be regarded as functions of $x^2$ to make sure it matches the appropriate coefficients, as explained also in this MIT lecture at this juncture:

If the generic polynomial in which the idea is to evaluate sample points is

$$P(x) = a_nx^n+ a_{n-1}x^{n-1}+\cdots+ a_1 x^1+a_0 x^0$$

Then this can be split into

$$P_{\text{even}}(x^2)=\sum_{k=0}^{n/2} a_{2k}(x^2)^k$$

and

$$P_{\text{odd}}(x^2)=\sum_{k=0}^{n/2-1} a_{2k+1}(x^2)^k$$

but to match the coefficients with the powers of $x,$ these even and odd polynomials (of half the degree of the original polynomial) have to be evaluated at $x^2$ when combined as

$$P(x) =P_{\text{even}}(x^2) + xP_{\text{odd}}(x^2).$$

For instance, considering the even polynomial, at $k=n/2,$ the input $x$ would be raised to $(x^2)^{n/2}=x^n$ and this would be matched with the coefficient $a_{n}.$ On the odd side, at $k=n/2-1,$ the coefficient to be matched with $x^{2(n/2-1)}=x^{n-2}$ (of course multiplied by the $x$ in front, yielding $x^{n-1})$ is $a_{2(n/2-1)+1}=a_{n-1}.$

Antoni Parellada
  • 8,889

1 Answers1

2

These even and odd degree polynomials are functions of $x^2$ and hence polynomials of degree $2.$

NO.

If $P(x)$ has degree $d$, then $P(x^2)$ has degree $2d$.

In particular, if $$P(x)=a_nx^n + a_{n-1}x^{n-1}+\cdots + a_0,$$

then

$$P(x^2)=a_nx^{2n} + a_{n-1}x^{2n-2}+\cdots + a_1x^2 + a_0$$

What the solution you cite is doing is using the following fact:

If $P$ is a polynomial such that all coefficients of odd powers of $x$ are zero, then there exists some polynomial $Q$ such that, for all $x$, $P(x)=Q(x^2)$ (in other words, $P=Q\circ S$ where $S$ is the polynomial defined as $S(x)=x^2$.

This fact can very easily be shown to be correct by just writing the polynomial $P$ out.

Example:

What the step does is it decomposes the polynomial. To make it more clear, look at a simple example of a fourth degree polynomial. Let's say

$$P(x) = x^4+4x^3 + 9x^2-3x-19\tag{1}$$

Then, the presentation you link simply rewrites the polynomial like so:

$$P(x)=(x^4+9x^2-19) + x(4x^2-3)$$

Now, they define two polynomials, $P_e$ and $P_o$, like so: $$P_e(x)=x^2+9x-19\\ P_o(x) = 4x-3\tag{2}$$

These definitions are such that the following equality holds:

$$P(x) = P_e(x^2) + x\cdot P_o(x^2).\tag{3}$$

You can easily check that this equality holds by just substituting the values and writing everything out.

5xum
  • 123,496
  • 6
  • 128
  • 204
  • @FredericBell Read it any time you want. I advise you to first verify for yourself that equation $(3)$ follows directly from definitions $(1)$ and $(2)$. Also note that in that particular example, $P_o$ is not of degree $2$ :) – 5xum Nov 29 '21 at 15:57
  • In the lecture I link a few comments above, the following splitting formula appears: $A_{\text{even}}(x^2) + x A_{\text{odd}}(x^2)$ at specifically this point in an attempt at generalizing all polynomials with the understanding that the $x^2$ will be raised to $k$ as in $(x^2)^k$. This is no contradiction to your answer, but explains why $x^2$ can be used to keep track of the index values in the expressions $A_{\text{even}}(x) = \sum_{k=0}^{n/2 -1} a_{2k}x^k$ and $A_{\text{odd}}(x) = \sum_{k=0}^{n/2} a_{2k+1}x^k.$ – Antoni Parellada Nov 29 '21 at 17:24
  • @FredericBell Yes, what you say is exactly what I say in my answer just before the example (the part where I say "What the solution you cite is doing is using the following fact:"). – 5xum Nov 30 '21 at 07:13