Monday Math: Finite Fourier
Aug. 20th, 2012 07:36 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
stoutfellowI'm hoping that systematizing things - setting Monday as "the day I post about math" - will help keep me on the ball. For the moment, I'll stick with my research on polygons, but later I'll also use this slot to talk about interesting bits of math I've encountered over the years.
Last time I talked about polygons, I described a different set of numbers that characterize a polygon, instead of the coordinates of the vertices. This time, I'm going to try to justify using those numbers, and discuss how to compute them. Under the cut, if you will....
As before, I'll stick to quadrilaterals; the same basic ideas apply to n-gons with any number of sides. I defined four special quadrilaterals: Q0, all of whose vertices lie at the point 1 (i.e., (1,0)); Q1, with vertices 1,i,-1,-i (i.e., (1,0), (0,1), (-1,0), (0,-1)); Q2, with vertices 1,-1,1,-1; and Q3, with vertices 1,-i,-1,i. Any quadrilateral Q can be written as
Another, more subtle, payoff is this. Remember we also talked about changing a polygon by picking a different vertex is "vertex 0", and proceeding around in the same order. For example, if we apply this to the quadrilateral 0,2,2+i,i - a rectangle with length 2 and height 1 - we get the quadrilateral 2,2+i,i,0 - "the same" quadrilateral, but a different set of four complex numbers. What happens if we apply this to our special quadrilaterals? Nothing happens to Q0 (which we're not interested in anyway). Q1 changes from (1,i,-1,-i) to (i,-1,-i,1), which is iQ1! Similarly, Q2 turns into -Q2, and Q3 into -iQ3. In technical language, we have diagonalized the vertex-shift operation. So, this operation turns a quadrilateral with z-numbers z1, z2, z3 into one with numbers iz1, -z2, -iz3.
Now, we're (eventually) going to define our classes of polygons by means of polynomials in the z-numbers. Well, almost; we have to throw in their conjugates as well. For ease of writing in LJ, we'll call the conjugates of z1, z2, z3 the w-numbers, w1, w2, w3 respectively. The vertex-shift operation changes w1, w2, w3 into -iw1, -w2, iw3 - the multipliers are, naturally enough, the conjugates of the multipliers for the z-numbers.
Here's the payoff. We want to know what effect the vertex-shift operation has on our functions, and by writing them in terms of the z- and w-numbers, we make this easy. For example, the function z1w1 is multiplied by i (because of the z1) and by -i (because of the w1), for a net effect of no change: i(-i)=1. Similarly, z3w1 is multiplied by (-i)(-i)=-1, and so forth. Just look at the exponents of each of the z-functions, multiply each by the subscript, and add them up; do likewise with the exponents of the w-functions; subtract the second number from the first, and take the result modulo 4. If the remainder is 0, the function isn't changed; if it's 1, it's multiplied by i, and so on.
One last thing I should mention. Shifting from the vertices v to the z-numbers is achieved by means of the "finite Fourier transform". If anybody wants to know how this is connected to the Fourier transform taught in classes on differential equations, I can do a technical post on that; but for the moment I'll just say that it means the z-numbers are easy to compute from the v-numbers (the vertices, thought of as complex numbers, as above). Here are the formulas:
We've set up some machinery; next Monday, we'll start using it.
Last time I talked about polygons, I described a different set of numbers that characterize a polygon, instead of the coordinates of the vertices. This time, I'm going to try to justify using those numbers, and discuss how to compute them. Under the cut, if you will....
As before, I'll stick to quadrilaterals; the same basic ideas apply to n-gons with any number of sides. I defined four special quadrilaterals: Q0, all of whose vertices lie at the point 1 (i.e., (1,0)); Q1, with vertices 1,i,-1,-i (i.e., (1,0), (0,1), (-1,0), (0,-1)); Q2, with vertices 1,-1,1,-1; and Q3, with vertices 1,-i,-1,i. Any quadrilateral Q can be written as
z0Q0+z1Q1+z2Q2+z3Q3for some choice of complex numbers z0, z1, z2, z3. Why are these z-numbers better than the coordinates of the vertices? There are several reasons. First, one immediate payoff is this. The number z0 is the center of gravity of the vertices; it carries no information except the location of the quadrilateral. To put it another way, if two quadrilaterals have the same z-numbers except for z0, then you can turn one into the other just by sliding it on top - by translating it. Since two quadrilaterals which are related in this way are, for most purposes, "the same", we can simply ignore z0. All of the useful information about the quadrilateral is contained in the other z-numbers.
Another, more subtle, payoff is this. Remember we also talked about changing a polygon by picking a different vertex is "vertex 0", and proceeding around in the same order. For example, if we apply this to the quadrilateral 0,2,2+i,i - a rectangle with length 2 and height 1 - we get the quadrilateral 2,2+i,i,0 - "the same" quadrilateral, but a different set of four complex numbers. What happens if we apply this to our special quadrilaterals? Nothing happens to Q0 (which we're not interested in anyway). Q1 changes from (1,i,-1,-i) to (i,-1,-i,1), which is iQ1! Similarly, Q2 turns into -Q2, and Q3 into -iQ3. In technical language, we have diagonalized the vertex-shift operation. So, this operation turns a quadrilateral with z-numbers z1, z2, z3 into one with numbers iz1, -z2, -iz3.
Now, we're (eventually) going to define our classes of polygons by means of polynomials in the z-numbers. Well, almost; we have to throw in their conjugates as well. For ease of writing in LJ, we'll call the conjugates of z1, z2, z3 the w-numbers, w1, w2, w3 respectively. The vertex-shift operation changes w1, w2, w3 into -iw1, -w2, iw3 - the multipliers are, naturally enough, the conjugates of the multipliers for the z-numbers.
Here's the payoff. We want to know what effect the vertex-shift operation has on our functions, and by writing them in terms of the z- and w-numbers, we make this easy. For example, the function z1w1 is multiplied by i (because of the z1) and by -i (because of the w1), for a net effect of no change: i(-i)=1. Similarly, z3w1 is multiplied by (-i)(-i)=-1, and so forth. Just look at the exponents of each of the z-functions, multiply each by the subscript, and add them up; do likewise with the exponents of the w-functions; subtract the second number from the first, and take the result modulo 4. If the remainder is 0, the function isn't changed; if it's 1, it's multiplied by i, and so on.
What I just described actually only applies to monomials - products of powers of the zs and ws - but we'll usually stick to sums of monomials which all give the same result, as we'll see later on.
One last thing I should mention. Shifting from the vertices v to the z-numbers is achieved by means of the "finite Fourier transform". If anybody wants to know how this is connected to the Fourier transform taught in classes on differential equations, I can do a technical post on that; but for the moment I'll just say that it means the z-numbers are easy to compute from the v-numbers (the vertices, thought of as complex numbers, as above). Here are the formulas:
z0=(v0+v1+v2+v3)/4They're easy to compute! For example, for the 2x1 rectangle 0,2,2+i,i, we get
z1=(v0-iv1-v2+iv3)/4
z1=(v0-v1+v2-v3)/4
z1=(v0+iv1-v2-iv3)/4
z0=(0+2+2+i+i)/4=1+1/2 i,Note that z2=0; that's because this quadrilateral is a parallelogram. As I mentioned before, z2 measures half the distance between the midpoints of the diagonals, and those coincide for parallelograms and only parallelograms.
z1=(0-2i-2-i-1)/4=-3/4-3/4 i,
z2=(0-2+2+i-i)/4=0,
z3=(0+2i-2-i+1)/4=-1/4-1/4 i
We've set up some machinery; next Monday, we'll start using it.
