Popper's Dreamland: June 2012

HOMEWORK

The Fourier Transform and its Applications, Brad Osgood

Free Online Course, Stanford University {course home}

The complete course materials, including all problem sets and answers can be found on the course home page. I don't look at the answers. Comprehension. Comprehension. Comprehension. I'm also using the assignments to integrate SAGE into my math studies, to build worksheets and functioning code as I move forward.

QUESTION 1(a)

Find the sum of a geometric series for arbitrary start and end points:

$\sum_{n=p}^{q}w^n$

where w ≠ 1 is real or complex, p and q integers.

Consider the cases p = −∞ or q = ∞. What about (p = −∞ and q = +∞)?

A: Let S denote the sum.
$S = w^p + w^{p+1} +\; \ldots\; + w^{q-1} + w^q$
Then
$\begin{align*} &S - wS = \;\;w^p + w^{p+1} + w^{p+2}+\; \ldots \; + w^{q-1} + w^q\\ &\;\;\;\;\;\;\;\;\;\;\,\,\;\;\;\;\;\;\,\;\;\;\underline{\;\;\;\;-\!w^{p+1} - w^{p+2} - \; \ldots \; - w^{q-1} - w^{q}-w^{q+1}}\\ &\;\;\;\;\;\;\;\;\;\;\;\;=\;\;w^p \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; -w^{q+1}\\\\ &S(1-w) = w^p - w^{q+1}\\ \end{align*}$
And hence
$\small S\;=\; \sum_{n=p}^{q}w^n \;=\; \frac{w^p - w^{q+1}}{1-w}$
for real or complex w.

Limits at infinity:
i) w real
I have included unbounded limits.
p → −∞
• w > 1: Then w^p → 0. S = w^q+1/(w-1)
• 0 < w < 1: Then w^p → +∞. S = ∞ (S is unbounded. The series does not converge)
• −1< w < 0: Then w^p → ± ∞. S = ± ∞.
(Consecutive terms have opposite signs. The alternating sequences w^−2k, w^−(2k+1)approach +∞ and −∞ respectively.)
• w < −1 : Then w^p → 0.   S = w^q+1/(w-1)
(The alternating sequences of even and odd terms approach 0⁺ and 0⁻, respectively.)

q → +∞
• w > 1: Then w^q+1 → +∞. S = +∞
• 0 < w < 1: Then w^q → 0⁺. S = w^p/(1−w)
• −1< w < 0: Then w^q → 0^±. S = w^p/(1−w)
(Alternating sequences of terms w^2k, w^(2k+1)approach 0⁺ and 0⁻ respectively.)
• w < −1 : Then w^q → ± ∞. S = ± ∞
(The alternating sequences w^2k, w^(2k+1)approach +∞ and −∞, respectively)

  p → −∞ and   q → +∞
• w > 1: Then   w^p → 0, w^q+1 → +∞. S = +∞
• 0 < w < 1: Then   w^p → +∞, w^q → 0⁺.   S = +∞
• −1< w < 0: Then w^p → ± ∞, w^q → 0^±. S = ± ∞
• w < −1 : Then w^p → 0,   w^q → ± ∞.   S = ± ∞

ii) w complex: w = a + bi, b ≠ 0
Now that is a good question.
What are the conditions of convergence?
Magnitude:
• Case 1: |w| = √(a² + b²) > 1. Then  w^q → 0 as q → ∞,
• Case 2:  |w| < 1. Then   w^p → 0 as p → −∞
In both cases, whenever wⁿ does not go to zero, (I believe) both a and b → ± ∞. This is easy to see if we begin with w purely imaginary. For any four consecutive integral powers, the resulting single term will cycle through the four states of iⁿ: {+, +i, −, −i}. Both the sequence and series approach the limits ∞ −∞, ∞i, −∞i in four alternating sequences. I believe the series approaches the same four limits simultaneously for all |w| > 1, a≠0, b ≠0, by interleaved combinations of ±a and ±b. It should be possible to determine, for any particular w, the arrangement of those terms for sequential powers by examining the argument of w:
Arg(w) = θ,
where   a = cos θ, b = sin θ
It seems obvious that the series cannot converge to a particular angle measure, as even division of the circle length cannot be given by a rational expression. However, I have left off there; my impression is that this work is beyond the scope of the question.
For complex w there is also a
• Case 3:  |w| = 1. Then there is no limit for a or b. Arg(w) should likewise have no limit, as successive powers are polynomial expressions. However, |w^p|, and |w^q+1| = 1 for all values of p and q. The resultant vectors are rotations around the unit circle; each successive power should produce an angle different from all preceding angles.
I have not verified this, except for double-checking that it is impossible for any angle but zero to be preserved under squaring. Hard to know how much detail other people think is normal.

QUESTION 1(b)

Find the sum
$\sum_{n=0}^{N-1} e^{2\pi in/N}$
and explain your answer geometrically.
A: Let S denote the sum.
$S = 1 + e^{2\pi i/N} + e^{4\pi i/N} + e^{6\pi i/N} +\; \ldots \; + e^{2\pi i(N-1)/N} + e^{2\pi i}$
The ratio of consecutive terms is
$\small \dpi{150} \frac{e^\frac{2\pi i(n+1)}{N}}{e^\frac{2\pi in}{N}}\; =\; e^\frac{2\pi i(n+1) -2\pi in}{N} \; =\;e^\frac{2\pi i}{N}$
Then
$\begin{align*} S - e^{2\pi i/N}S \;&=\; 1 + e^{2\pi i/N} + e^{4\pi i/N} +\; \ldots \; + e^{2\pi i(N-1)/N}\\ &\;\;\;\;\;\underline{\;\;\;\; -e^{2\pi i/N} - e^{4\pi i/N} -\; \ldots \; - e^{2\pi i(N-1)/N} - e^{2\pi i}}\\ &=\;1\;\;\;\;\;\;\;\;\; \;\;\;\;\;\;\;\;\;\;\;\; \;\;\;\;\;\;\;\;\;\;\;\; \;\;\;\;\;\;\;\;\;\;\;\;\; \;\;\;\;\;\;\;\;\;\;\;\;-e^{2\pi i}\\ \\ S(1-e^{2\pi i/N}) &= 1 - e^{2\pi i} \end{align*}$
And hence
$\begin{align*} S &= \; \sum_{n=0}^{N-1}e^{2\pi in/N} \; = \; \frac{1-e^{2\pi i}}{1-e^{2\pi i/N}} \\ &\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \;=\; \frac{1-[\cos(2\pi)+i\sin(2\pi)]}{\textup{kaboodle}} = \frac{0}{\textup{kaboodle}}\\ & = 0 \end{align*}$
Geometrically, the situation is straightforward. By construction, the N terms are evenly spaced points along the arc [0, 2π) of the imaginary unit circle. The angle measure at each point is is the same as the arc length from zero; i.e.
• the cosine of each angle = the real component of each term = the projection of the point on the real axis
•the sine of each angle = the imaginary component = the projection onto the imaginary axis
Each of these sums (real and imaginary) is zero for all whole numbers N > 1.

QUESTION 1(c)

(c) Derive the formula

$\sum_{k=-N}^{N} e^{2\pi ikt} = \frac{\sin(2\pi t(N+ 1/2))}{\sin(\pi t)}$

A: Let S denote the sum
$\begin{align*} S &= \; \sum_{k=-N}^{N}e^{2\pi ikt} \end{align*}$
The ratio of consecutive terms is
$\begin{align*} &\frac{e^{2\pi i(k+1)t}}{e^{2\pi ikt}} \;=\; e^{2\pi ikt\; + \;2\pi it\;- \;2\pi ikt} \;=\;e^{2\pi it} \end{align*}$
Following the same procedure,
$\begin{align*} &S-e^{2\pi it}\!S \;= \;e^{-2\pi iNt}-e^{2\pi i(N+1)t}\\ \\ &S = \frac{e^{-2\pi iNt}-e^{2\pi i(N+1)t}}{1-e^{2\pi it}} \end{align*}$
This could get ugly. Preliminaries:
$\small \inline \begin{align*} S&= \frac{e^{-2\pi i Nt}-e^{2\pi iNt}e^{2\pi it}}{1-e^{2\pi it}} \\ &= \frac{\cos(2\pi\! Nt) - i\sin(2\pi \!Nt) - [\cos(2\pi \!Nt) +i\sin(2\pi \!Nt)][\cos(2\pi t)+i\sin(2\pi t)]} {1-\cos(2\pi t)- i\sin(2\pi t)}\\ \end{align*}$
Basic formulas:
cos(−θ) = cos(θ), sin(−θ) = −sin(θ)
sin(2θ) = 2sinθ cosθ,
cos(2θ) = 2cos²θ −1 = 1− 2sin²θ
the addition and subtraction formulas for sine and cosine
Collecting some terms,

$\small \inline \begin{align*} &= \frac{\cos(2\pi \!Nt)[{\color{DarkRed} 1\!-\!\cos(2\pi t)\!-\!i\sin(2\pi t)}] \;-\; i\sin(2\pi \!Nt)[1\!+\! \cos(2\pi t)\!+\! i\sin(2\pi t)]} {{\color{DarkRed} 1-\cos(2\pi t)- i\sin(2\pi t)}} \\ \\ &= \cos (2\pi \!Nt)+ \frac{ \;-\; i\sin(2\pi \!Nt)[1+ \cos(2\pi t)+ i\sin(2\pi t)]} {1-\cos(2\pi t)- i\sin(2\pi t)} \end{align*}$
Applying the double-angle formulas, and cleaning up a bit:
$\small \inline \begin{align*} &= \cos (2\pi \!Nt)+ \frac{ - i\sin(2\pi\!Nt)[1+ {\color{DarkBlue} (2\cos^2(\pi t) - 1)} + 2i\sin(\pi t)\cos(\pi t)]} {1-[{\color{DarkBlue} 1-2\sin^2(\pi t)}]- 2i\sin(\pi t)\cos(\pi t)} \\ \\ &= \cos (2\pi \!Nt)+ \frac{ - i\sin(2\pi\!Nt)[ 2\cos^2(\pi t) + 2i\sin(\pi t)\cos(\pi t)]} {2\sin^2(\pi t)- 2i\sin(\pi t)\cos(\pi t)} \\ \\ &= \cos (2\pi \!Nt)+ \frac{ - i\sin(2\pi\!Nt)\cos(\pi t)[{\color{DarkRed} \cos(\pi t) + i\sin(\pi t)}]} {\sin(\pi t)[{\color{DarkRed} \sin(\pi t)- i\cos(\pi t})]} \end{align*}$
Go away, Red guys. Move the leading −i into the square brackets:
$\small \inline \begin{align*} &= \cos (2\pi \!Nt)+ \frac{ \sin(2\pi\!Nt)\cos(\pi t)[{\color{DarkRed} -i\cos(\pi t) + \sin(\pi t)}]} {\sin(\pi t)[{\color{DarkRed} \sin(\pi t)- i\cos(\pi t)}]} \\ \\ &= \cos (2\pi \!Nt)+ \frac{ \sin(2\pi\!Nt)\cos(\pi t)} {\sin(\pi t)} \\\\ &= \frac{\cos(2\pi\!Nt)\sin(\pi t)+ \sin(2\pi\!Nt)\cos(\pi t)} {\sin(\pi t)} \end{align*}$
Which has the conspicuous form of an angle sum:
$\small \begin{align*} S&= \frac{\sin(2\pi\!Nt + \pi t)}{\sin(\pi t)}\, , \;\;\;\;\;\;\;\;=\; \frac{\sin(2\pi t(N+1/2))}{\sin(\pi t)} \end{align*}$
Tits. Maybe I missed an easier way. I'll look at the answers after I have posted mine.

QUESTION 2

Represent each of the figures (a) - (d) as the sum of two isosceles triangles, in the form,
$b1 Λ_{a1}(t−c1) + b2 Λ_{a2}(t−c2)$
where
$b\Lambda_a(t-c)\; =\; \left\{\begin{matrix} b\left(1 -\tfrac{1}{a}|t-c|\right) , &|t-c|\le a \\ 0, &|t-c| > a \end{matrix}\right.$
When the midpoints of the triangles do not coincide, call the leftmost triangle Λ_a1, and the rightmost, Λ_a2.

I have also written each figure as an adjacency list (a vector). Reading left-to-right, connecting adjacent points with straight lines gives the figure.

(a) [(-2, 0), (0, 1), (2, 1), (4, 0)] = Λ₂(t) + Λ₂(t −2)

(b) [(-2, 0), (0, 2), (1, 1), (2, 1), (3, 2), (5, 0)] = 2Λ₂(t) + 2Λ₂(t −3)

For both (c) and (d), let's invent a petit theorem:
Theorem: The apex of one (or both) of the triangles occurs at the maximum value of the envelope.
{Note that the maximum value is not restricted to occur only at the apex positions}.

PROOF: The maximum value of each triangle is the apex, at c_i. Consider their sum.
Case 1: Let the peaks of the two triangles coincide. The highest point of the sum is of course at this common point. In math,
Let c₁ = c₂
Then max(Λ_a1) + max(Λ_a2) = max(Λ_a1 + Λ_a2), at t = c₁ = c₂.
Case 2: Separate the peaks by a small amount, δ, so that c₁≠ c₂. For all t < c₁, and t > c₂, the direction of increasing Λ_a1 and Λ_a2is into the interval c₁ ≥ t ≥ c₂. The maximum value must then lie in c₁ ≥ t ≥ c₂.
Let the slopes of the two triangles be m₁ = (ΔΛ_a1/ Δt), and m₂ = (ΔΛ_a2/ Δt).
Now consider m₁+ m₂, only over the interval c₁ ≥ t ≥ c₂. The slopes have opposite sign: there is some α > 0 such that m₁ = −α m₂.
(I consider only the case where the triangles are sufficiently close that neither m₁ nor m₂ falls to zero in the interval. If the triangles are moved farther apart... oh, hell... the proof is even easier that way, but I will finish it this way, and it should be clear the proof always holds as the triangles are moved farther apart.)
Suppose α=1, then the maximum value of m₁+ m₂= 0. The sum is a horizontal line, with breakpoints at c₁ and c₂. Then max(Λ_a1 + Λ_a2) occurs at both c₁ and c₂ (and everywhere in between).
Suppose α ≠ 1. Then one of the two, |m₁| or |m₂| is greater. Suppose |m₁| > |m₂|. Now, the minimum value of Λ_a1 on the interval is at the rightmost point, c₂. Moving to the left, m₁ is positive, m₂ is negative, and |m₁| > |m₂| and therefore the sum m₁+m₂ is positive over the entire interval, to the maximum value of Λ_a1, at c₁.
If |m₂| > |m₁|, the procedure is the same, but moving from right to left.
Hence, the maximum value of Λ_a1+ Λ_a2 invariably coincides with the apex of one (or both) of the triangles.

(c) [(1, 0), (3, 6), (7, 0)] = 6Λ₂(t−3) + 3Λ₂(t −5)

(d) The question appears to be, "under what conditions is the sum a triangle with unequal sides?"

Working this out in Sage, I have a couple of clunky cases, with proofs. The answer is simple, and but piecewise functions make the algebraic arguments a bit messy. The main point is this: Each triangle has 3 corners where the slope changes: The function is zero; it goes up; it goes down. No mystery here: it's a triangle. The sum then has at most six corners. What are the conditions for a sum with only three? First, there are three corners if the x-coordinates of the three corners are identical for both triangles. That is,

Case 0: The sum is a triangle with equal sides. The two triangles have the same base, and the same center. a₁=a₂, c₁=c₂. That is, the peaks and base coincide. But we're really interested in the next two cases where,

The sum is a triangle with unequal sides.

Suppose only two of the three x-coordinates are shared between the triangles.

Consider the following diagram/solution:

Case 1:
The apex of each triangle coincides with an endpoint of the other: a₁=a₂.
Then c₂ divides the longer side into two equal segments. For the two sections to form an unbroken line, over the same change in t we must have:

rise(Λ₁) − rise(Λ₂) = rise(Λ₂)
rise(Λ₁) = 2 rise(Λ₂)
Hence b₁ = 2b₂. Equivalently, the slope of Λ₁ is twice that of Λ₂.
In terms of Lambda, the sum is
$\begin{align*} &\;\;\;\;\;\; 2b\Lambda_a(t-c)\, + \;\; b\Lambda_a(t-[c\!+\!a])\\ &\textrm{or}\;\;\;\,\, b\Lambda_a(t-c)\, + \; 2b\Lambda_a(t-[c\!+\!a]) \end{align*}$
where the first is a left-shouldered triangle, the second is right-shouldered.
case 2:

Here, the triangles share a common endpoint

Again, in terms of Lambda, we have

$\begin{align*} &\;\;\;\;\;\; b\Lambda_a(t-c)\, + \;\; b\Lambda_{2a}(t-[c\!+\!a])\\ &\textrm{or}\;\;\;\,\, b\Lambda_{2a}(t-c)\, + \; b\Lambda_a(t-[c\!+\!a]) \end{align*}$
What is common to both cases? The conditions are:
1) One of the triangles must have a slope twice that of the other.
2) the c_i satisfy c₂ = c₁ + a, independently of how we choose to construct the 2:1 slope ratio.
Synthetically, in the expression
$b\Lambda_a(t-c)\, + \;\; b\Lambda_a(t-[c\!+\!a])\\$
we can place the numeral 2 in one of four possible positions: before a or b in either of the bΛ_a.
{remaining to do: double check that it is not possible have a triangle sum with only one shared corner.}

There are a number of ways to assemble the same conclusion. Note, for example, that, by the little Theorem one of the triangles must have a peak at x₂. Its base can extend no further than x₁, and therefore the second triangle must have a base which extends to x₃. This insures that the peak of the second triangle must occur to the right of x₂. The furthest to the left c₂ may be is the midpoint of the base. There are two cases. Suppose c₂ lies on the midpoint. Then for the left endpoint we have c₁−a₁ = c₂−a₂.
Suppose c₂ lies to the right of the midpoint... etc.
{Document getting long. To be continued}

Popper's Dreamland

Pages

Saturday, June 9, 2012

The Fourier Transform

Tuesday, June 5, 2012

Blizzard, June

Labels

Followers

Blog Archive

About Me