Hi everybody!

This semester for me is the dreaded exam term… Because of this I’ll be going on a hiatus until June.

See you all in 2 months!

M x

Skip to content
# mathsbyagirl

## Hiatus

## Rings: The Basics

### What is a ring?

### Subring

### Examples

## Maths in Buildings?

#### The Great Pyramid of Giza – Cairo, Egypt

#### Taj Mahal – Agra, India

#### The Eden Project – Cornwall, UK

#### Parthenon – Athens, Greece

#### Chichen Itza – Mexico

#### Sagrada Familia – Barcelona, Spain

## F.T.A. via Complex Analysis

### Proof

## MATHS BITE: Pinwheel Tiling

### Conway Tessellation

### Tiling

### Architecture

## Catalan’s Conjecture

## Proving the Conjecture

## Video

## Algorithms: PART 2

### QR Algorithm

**Quicksort**

### Fast Fourier Transform

### Integer Relation Detection Algorithm

### Fast Multipole Algorithm

new posts monday and thursday

Hi everybody!

This semester for me is the dreaded exam term… Because of this I’ll be going on a hiatus until June.

See you all in 2 months!

M x

Advertisements

Last year, on first learning about groups I created two blog posts introducing the group axioms and subgroups. This year, I was introduced to **rings**, so I thought I’d create a blog post on these!

A *ring* is a quintuple (R, +, *, 0_{R}, 1_{R}) where 0_{R}, 1_{R} ∈ R and +, *: R x R –> R are binary operations such that:

- (R, +,0
_{R}) is an abelian group - The operation *: RxR –> R satisfies:
- associativity – a*(b*c) = (a*b)*c;
- identity – 1
_{R}*r = r*1_{R}= r.

- Multiplication distributes over addition
- r
_{1}* (r_{2}+ r_{3}) = (r_{1}* r_{2}) + (r_{1}* r_{3}) - (r
_{1}+ r_{2}) * r_{3}= (r_{1}* r_{3}) + (r_{2}* r_{3})

- r

We say that a ring is **commutative** if a*b = b*a for all a,b ∈ R. These types of rings are much easier to study.

Let (R, +, *, 0_{R}, 1_{R}) be a ring and S ⊆ R is a subset. We say that S is a **subring** of R if 0_{R}, 1_{R} ∈ S and the operations +,* make S into a ring in its own right. We normally denote this by S ≤ R.

- The familiar number systems are all rings: Z ≤ Q ≤ R ≤ C, under the usual 0, 1, +, *.
- Q[√2] = {a + b√2 ∈ R: a,b ∈ Q} ≤ R.
- The set Z[i] = {a + bi: a, b ∈ Z} ≤ C is the
**Gaussian integers**, which is a ring.

M x

Maths and architecture are very closely linked. In today’s blog post I thought I would talk about some famous buildings and describe how maths is related to them.

The Great Pyramid of Giza, one of the Seven Wonders of the Ancient World, is the **largest** and the **oldest** of the three pyramids and was the **tallest** man-made structure in the world for 3,800 years.

In cubits (the first recorded unit of length) the pyramid’s perimeter is 365.24, which is the number of days in the year! Also, if you divide the pyramid’s perimeter by twice its height, you will get **pi**! The last amazing fact is that the measurements in the King’s chamber are based on the famous **Pythagorean triangle** 3, 4, 5.

The main mathematical feature of the Taj Mahal is its impeccable **symmetry**. It is symmetric about a vertical line down the middle, as well as a horizontal line along the waterline, as one can see its reflection in the water.

The Eden project opened in 2001 and is composed of two biomes containing plants from many different climates and environments.

The greenhouses are geodesic domes made up of hexagonal and pentagonal cells.

Furthermore, in 2005 an education centre was built. This building draws inspiration from plants, using **Fibonacci numbers** to reflect the nature onsite. Also, the structure of is derived from phyllotaxis which is the mathematical basis for most plant growth – a pattern of opposing spirals.

The Parthenon was constructed in 430/440 BC on the Ancient Greek ideals of harmony, which is shown in the perfect proportions of the building, for example the width to height ratio of 9:4, the spacing of the columns, etc.

In the Ancient Greek’s quest for beauty, they wanted to make their columns appear completely straight. However, to achieve this they made their columns slightly thicker in the middle due to the fact that if they had not, an optical illusion would make them seem thinner in the middle.

In addition, it’s been suggested that the Parthenon’s proportions are based on the Golden Ratio.

The Mayan civilisation were incredible mathematicians. The structure shown above, called El Castillo, within Chichen Itza is based on the **astrological system:**

- The 52 panels on each side of the pyramid represent the number of years in the Mayan cycle;
- The stairways dividing the 18 tiers correspond to the Mayan calendar of 18 months;
- The steps within El Castillo mirror the solar year, with a total of 365 steps i.e. 1 step for each day of the year.

This structure was designed by Antoni Gaudi and is one of Spain’s top tourist destinations. Gaudi used hyperbolic paraboloid structures, which can be seen within particular façades.

This quadratic and doubly ruled surface given by the Cartesian equation:

What does this look like? **Pringles **resemble a hyperbolic paraboloid!

Additionally, the Sagrada Familia features a **magic square** within the Passion façade. This is an arrangement where the number in all columns, rows and diagonals add up to the same sum, which in this case is 33. The **magic constant** M is the constant sum in every row, column and diagonal and can be represented by the following formula:

M = n(n^{2}+1)/2

(All pictures from Wikipedia)

M x

Although this requires a bit of knowledge on Complex Anlaysis, I recently discovered this new way to prove the Fundamental Theorem of Algebra and I couldn’t help but share it.

First of all, what is the **Fundamental Theorem of Algebra (FTA)**? This very important (hence the name!) result states that:

Every non-constant polynomial with complex coefficients has a complex root.

In order to prove this, we must first be aware of Liouville’s Theorem:

Every bounded, entire function is constant.

**Definitions**

Bounded: a function on a set X is said to be bounded if there exists a real number *M* such that

for all *x* in *X*.

Entire: An entire function is a holomorphic function on the entire complex plane.

Liouville’s theorem is proved using the Cauchy integral formula for a disc, one of the most important results in Complex Analysis. Although I will not describe how to prove it or what it states in this blog post, I encourage you to read about here it as it is truly a remarkable result.

Now armed with Liouville’s Theorem we can prove the FTA.

Let P(z) = z^{n} + c_{n-1}z^{n-1} + … + c_{1}z + c_{0} be a polynomial of degree *n* > 0. Then |P(z)| –> ∞ as |z| –> ∞, so there exists R such that |P(z)| > 1 for all z with |z| > R.

Consider f(z) = 1/P(z). If P has no complex zeros then f is entire. So, as f is continuous, f is bounded on {|z| ≤ R}.

As |f(z)| < 1 when |z| > R, f is a bounded entire function, so by **Liouville’s Theorem **f is constant, which is a contradiction.

The only thing we assumed was that P had no complex zeros, and so we contradicted this fact. Hence, P must have at least **one **complex zero. Amazing right!

M x

Pinwheel tiling is a type non-periodic tiling that was defined by American mathematician Charles Radin based on a construction by John Conway. They are the first known non-periodic tilings where the tiles appear in infinitely many orientations.

Given a right angle triangle T with side lengths 1, 2 and , Conway noticed that we can divide it into five copies of its image by the dilation of factor

By rescaling, translating and rotating, we can iterate this to obtain and infinite increasing sequence of growing triangles. If we take the union of these triangles, we obtain T. It is this increasing sequence of triangles that defines the Conway tiling.

We observe that the triangles appear in infinitely many orientations. (This is because arctan(1/2) and arctan(2), two angles in the triangles, are both not proportionate to ). Extraordinarily, despite this all the vertices have rational coordinates!

Based on this tessellation, Radin defined a tiling:

Federation Square, a building complex in Melbourne, Australia has this pinwheel tiling.

M x

Although popularly known as Catalan’s *conjecture*, this is in fact a theorem in number theory, proven by Preda Mihăilescu in 2002, 158 years after it was conjecture in 1844 by French and Belgian mathematician Eugène Charles Catalan.

The theorem states that the only solution in the natural numbers of

for a,b>1; x,y>0 is **x = 3, a=2, y=2, b=3.**

**Catalan ‘Near Misses’** (i.e. x^{a} – y^{b} <= 10; 2 <= x,y,a,b <= 100; a,b prime)

- 3
^{3}– 5^{2}= 2 - 2
^{7}– 5^{3}= 3 - 2
^{3}– 2^{2}= 6^{2}– 2^{5}= 5^{3}– 11^{2}= 4 - 2
^{5}– 3^{3}= 5 - 2
^{5}– 5^{2}= 4^{2}– 3^{2}= 2^{7}– 11^{2}= 7 - 4
^{2}– 2^{3}= 8 - 5
^{2}– 4^{2}= 6^{2}– 3^{3}= 15^{2}– 6^{3}= 9 - 13
^{3}– 3^{7}= 10

Similarly to Fermat’s last theorem, the solution to this conjecture was assembled over a long period of time. In 1850, Victor Lebesgue established that b cannot equal 2. But then it was only after around 100 years, in 1960, that Chao Ko constructed a proof for the other quadratic case: a cannot equal 2 unless x = 3.

Hence, this left a,b odd primes. Expressing the equation as (x-1)(x^{a}-1)/(x-1) = y^{b} one can show that the greatest common divisor of the two left hand factors is either 1 or a. The case where the gcd = 1 was eliminated by J.W.S Cassels in 1960. Hence, only the case where gcd = a remained.

It was this “*last, formidable, hurdle*” that Mihailescu surmounted. In 2000, he showed that a and b would have to be a ‘*Wieferich pair*’, i.e. they would have to satisfy a^{b-1 }≡ 1 (mod b^{2}) and b^{a-1 }≡ 1 (mod a^{2}). In 2002, he showed that such solutions were impossible!

M x

Read part 1 here!

From 1959-1961, John G.F Francis worked on finding a stable method to compute eigenvalues and thus created the QR algorithm. Eigenvalues are one of the most essential numbers associated with matrices, however they can be quite difficult to compute.

This algorithm is based on the fact that is relatively easy to transform a square matrix into a matrix that is *almost* upper triangular (one extra set of no-zero entries just below the main diagonal). Based on QR decomposition, which writes a matrix A as a product of an orthogonal matrix Q and an upper triangular matrix R, the QR algorithm iteratively changes *A*_{i} = Q_{i}*R*_{i} to *A*_{i+1} = *R*_{i}Q_{i}

“The algorithm is numerically stable because it proceeds by orthogonal similarity transforms.”-Wikipedia

Under certain conditions,^{} the matrices *A*_{i} converge to a triangular matrix and the eigenvalues of a triangular matrix are listed on the diagonal so the eigenvalue problem is solved.

By the mid-1960s, the QR algorithm had turned once-formidable eigenvalue problems into routine calculations.

The Quicksort algorithm was developed by Tony Hoare in 1962. It puts N things in numerical or alphabetical order by using a recursive strategy:

- Pick one element as a
*pivot* - Separate the rest into piles of
*big*and*small*elements, as compared with the pivot - Repeat this procedure on each pile

Although you can get stuck doing all N(N-1)/2 comparisons, on average Quicksort runs on average with O(N logN) efficiency, which is very fast. Its simplicity has made Quicksort a “*poster child of computational complexity*“.

The fast Fourier Transform was developed by James Cooley and John Tukey in 1965. The FFT revolutionised signal processing. Although the idea can be traced back to Gauss, it was a paper by Cooley and Tukey that made it clear how easily Fourier transforms can be computed. It relies on a ‘*divide-and-conquer*‘ strategy and hence reduces it from an O(N^2) to an O(N logN) computation.

Given real numbers x1, …, xn, are there integers a1, …, an (not all 0) for which a1x1 + … + anxn = 0? Helaman Ferguson and Rodney Forcade found an algorithm – the Integer Relation Detection Algorithm – to answer this question. This is easily solved in the case where n = 2 by Euclid’s algorithm, computing terms in the continued-fraction expansion of x1/x2 – if x1/x2 is rational, then the expansion terminates.

The detection algorithm has, for example, been used to find the precise coefficients of the polynomials satisfied by the third and fourth bifurcation points of the logistic map.

It has also proved useful in simplifying calculations with Feynman diagrams in quantum field theory.

This algorithm overcomes one of the biggest problems of N-body simulations, which is the fact that accurate calculations of the motions of N particles interaction via gravitational or electrostatic forces seemingly requires O(*N^2*) calculations, i.e. one for each pair of particles. This algorithm, developed in 1987 by Leslie Greengard and Vladimir Rokhlin, does it with O(*N*) computations.

**How does it do this?** It uses multipole expansions to approximate the effects of a distant group of particles on a local group. Then we define ever-larger groups as distances increase. One of the big advantages of the fast multipole algorithm is that it comes with rigorous error estimates, a feature that a lot of other methods lack.

M x