Archive

Archive for June, 2013

Sympy should suffice

June 6, 2013 Leave a comment

I have just received a copy of Instant SymPy Starter, by Ronan Lamy—a no-nonsense guide to the main properties of SymPy, the Python library for symbolic mathematics. This short monograph packs everything you should need, with neat examples included, in about 50 pages. Well-worth its money.

To celebrate, I would like to pose a few coding challenges on the use of this library, based on a fun geometric puzzle from cut-the-knot: Rhombus in Circles

Segments \overline{AB} and \overline{CD} are equal. Lines AB and CD intersect at M. Form four circumcircles: (E)=(ACM), (F)=(ADM), (G)=(BDM), (H)=(BCM). Prove that the circumcenters E, F, G, H form a rhombus, with \angle EFG = \angle AMC.

rhombusincircles

Note that if this construction works, it must do so independently of translations, rotations and dilations. We may then assume that M is the origin, that the segments have length one, A=(2,0), B=(1,0), and that for some parameters a>0, \theta \in (0, \pi), it is C=(a+1) (\cos \theta, \sin\theta), D=a (\cos\theta, \sin\theta). We let SymPy take care of the computation of circumcenters:

import sympy
from sympy import *

# Point definitions
M=Point(0,0)
A=Point(2,0)
B=Point(1,0)
a,theta=symbols('a,theta',real=True,positive=True)
C=Point((a+1)*cos(theta),(a+1)*sin(theta))
D=Point(a*cos(theta),a*sin(theta))

#Circumcenters
E=Triangle(A,C,M).circumcenter
F=Triangle(A,D,M).circumcenter
G=Triangle(B,D,M).circumcenter
H=Triangle(B,C,M).circumcenter

Finding that the alternate angles are equal in the quadrilateral EFGH is pretty straightforward:

In [11]: P=Polygon(E,F,G,H)

In [12]: P.angles[E]==P.angles[G]
Out[12]: True

In [13]: P.angles[F]==P.angles[H]
Out[13]: True

To prove it a rhombus, the two sides that coincide on each angle must be equal. This presents us with the first challenge: Note for example that if we naively ask SymPy whether the triangle \triangle EFG is equilateral, we get a False statement:

In [14]: Triangle(E,F,G).is_equilateral()
Out[14]: False

In [15]: F.distance(E)
Out[15]: Abs((a/2 - cos(theta))/sin(theta) - (a - 2*cos(theta) + 1)/(2*sin(theta)))

In [16]: F.distance(G)
Out[16]: sqrt(((a/2 - cos(theta))/sin(theta) - (a - cos(theta))/(2*sin(theta)))**2 + 1/4)

Part of the reason is that we have not indicated anywhere that the parameter theta is to be strictly bounded above by \pi (we did indicate that it must be strictly positive). The other reason is that SymPy does not handle identities well, unless the expressions to be evaluated are perfectly simplified. For example, if we trust the routines of simplification of trigonometric expressions alone, we will not be able to resolve this problem with this technique:

In [17]: trigsimp(F.distance(E)-F.distance(G),deep=True)==0
Out[17]: False

Finding that \angle EFG = \angle AMC with SymPy is not that easy either. This is the second challenge.

How would the reader resolve this situation?


Instant SymPy Starter

Advertisements

A nice application of Fatou’s Lemma

June 1, 2013 Leave a comment

Let me show you an exciting technique to prove some convergence statements using exclusively functional inequalities and Fatou’s Lemma. The following are two classic problems solved this way. Enjoy!

Exercise 1 Let {(X, \mathcal{F}, \mu)} be a measurable space and suppose {\{f_n\}_{n\in \mathbb{N}}} is a sequence of measurable functions in {L_1(\mu)} that converge almost everywhere to a function {f \in L_1(\mu)}, and such that the sequence of norms {\big\{ \lVert f_n \rVert_1 \big\}_{n \in \mathbb{N}}} converges to {\lVert f \rVert_1}. Prove that the sequence of integrals {\int_E \lvert f_n \rvert\, d\mu} converges to the integral {\int_E \lvert f \rvert\, d\mu} for every measurable set {E}.

Proof: Note first that

\displaystyle  \begin{array}{rcl}  \lvert f_n - f\rvert\, \boldsymbol{1}_E \leq \lvert f_n - f \rvert \leq \lvert f_n \rvert + \lvert f \rvert. \end{array}

Set then {g_n = \lvert f_n \rvert + \lvert f \rvert - \lvert f_n-f \rvert\, \boldsymbol{1}_E} (which are non-negative functions) and apply Fatou’s Lemma to that sequence. We have then

\displaystyle  \begin{array}{c}  \int_X \liminf_n g_n\, d\mu \leq \liminf_n \int_X g_n\, d\mu \\ \\ \int_X \liminf_n \big( \lvert f_n \rvert + \lvert f \rvert - \lvert f_n - f \rvert\, \boldsymbol{1}_E \big)\, d\mu \leq \liminf_n \int_X \big( \lvert f_n \rvert + \lvert f \rvert - \lvert f_n - f \rvert\, \boldsymbol{1}_E \big)\, d\mu \\ \\ \int_X \big( 2\lvert f \rvert - \limsup_n \lvert f_n-f \rvert\, \boldsymbol{1}_E\big)\, d\mu \leq \liminf_n \int_X \lvert f_n \rvert\, d\mu + \lVert f \rVert_1 - \limsup_n \int_E \lvert f_n -f \rvert\, d\mu \\ \\ 2\lVert f\rVert_1 \leq 2\lVert f \rVert_1 - \limsup_n \int_E \lvert f_n - f\rvert\, d\mu, \end{array}

which implies

\displaystyle  \begin{array}{rcl}  0 \leq \liminf_n \int_E \lvert f_n-f \rvert\, d\mu \leq \limsup_n \int_E \lvert f_n-f \rvert\, d\mu \leq 0. \end{array}

It must then be {\int_E \lvert f_n - f \rvert\, d\mu = 0}. But this proves the statement, since

\displaystyle  \begin{array}{c}  \bigg\lvert \int_E \lvert f_n\rvert\, d\mu - \int_E \lvert f \rvert\, d\mu \bigg\rvert = \bigg\lvert \int_E \big( \lvert f_n \rvert - \lvert f \rvert \big)\, d\mu \bigg\rvert \\  \leq \int_E \Big\lvert \lvert f_n \rvert - \lvert f \rvert \Big\rvert\, d\mu \leq \int_E \lvert f_n - f \rvert\, d\mu \end{array}

\Box

Exercise 2 Let {(X, \mathcal{F}, \mu)} be a finite measure space and let {1<p<\infty}. Suppose that {\{ f_n \}_{n \in \mathbb{N}}} is a sequence of measurable functions in {L_p(\mu)} whose norms are uniformly bounded in {n} and which converge almost everywhere to a function {f}. Prove that the sequence {\big\{ \int_X f_ng\, d\mu \big\}_{n \in \mathbb{N}}} converges to {\int_x fg\, d\mu} for all {g \in L_q(\mu)} where {q} is the conjugate exponent of {p}.

Proof: The proof is very similar to the previous problem. We start by noticing that under the hypotheses of the problem,

\displaystyle  \begin{array}{c}  \bigg\lvert \int_x f_ng\, d\mu - \int_X fg\, d\mu \bigg\rvert = \bigg\lvert \int_X (f_n -f)g\, d\mu \bigg\rvert \\ \leq \lVert (f_n-f)g \rVert_1 \leq \lVert f_n - f \rVert_p\, \lVert g \rVert_q. \end{array}

If we prove that {\lim_n \lVert f_n-f \rVert_p = 0}, we are done.

We will achieve this by using the convexity of {\lvert \cdot \rvert^p}, since in that case it is

\displaystyle  \begin{array}{rcl}  \frac{\lvert f_n - f \rvert^p}{2^p} \leq \tfrac{1}{2} \lvert f_n \rvert^p + \tfrac{1}{2} \lvert f \rvert^p. \end{array}

hence,

\displaystyle  \begin{array}{rcl}  \lvert f_n -f \rvert^p \leq 2^{p-1} \big( \lvert f_n \rvert^p + \lvert f \rvert^p \big). \end{array}

Set then {g_n = 2^{p-1} \big( \lvert f_n\rvert^p + \lvert f \rvert^p\big) - \lvert f_n-f \rvert^p} (which are non-negative functions) and apply Fatou’s Lemma as before. \Box

%d bloggers like this: