euler

MATHS BITE: Apéry’s Constant

Apéry’s constant is defined as the number

${\begin{aligned}\zeta (3)&=\sum _{n=1}^{\infty }{\frac {1}{n^{3}}}\\&=\lim _{n\to \infty }\left({\frac {1}{1^{3}}}+{\frac {1}{2^{3}}}+\cdots +{\frac {1}{n^{3}}}\right)\end{aligned}}$

where ζ is the Riemann Zeta Function.

This constant is named after the French mathematician Roger Apéry who proved that it was irrational in 1978. However it is still unknown whether or not it is transcendental.

History

The Basel Problem asked about the convergence of the following sum:
Screen Shot 2017-06-10 at 2.16.05 PM.png

In the 18th century, Leonhard Euler proved that in fact it did – to π^2/6. However, the limit of the following sum remained unknown: Screen Shot 2017-06-10 at 2.19.28 PM.png

Although mathematicians made some progress, including Euler who calculated the first 16 decimal digits of the sum, it was not known whether the number was rational or irrational, until Apéry.

Furthermore, it is currently not known specifically whether any other particular ζ(n), for n odd, is irrational. “The best we’ve got is from Wadim Zudilin, in 2001, who showed that at least one of ζ(5), ζ(7), ζ(9), ζ(11) must be irrational, and Tanguy Rivoal, in 2000, who showed that infinitely many of the ζ(2k+1) must be irrational.”

M x

Prime Number Theorem

Today I thought I’d quickly discuss a extremely important theorem in one of my favourite areas in mathematics: Number Theory (as you can probably tell by the number of posts that I’ve published about primes!).

Perhaps the first property of π(x) – the number of primes less than or equal to x – is that π(x) tends to infinity as x tends to infinity. In other words, the prime numbers are infinite, which was proved by Euclid in “Elements”. A more precise result, established by Euler in 1737, was that the series of reciprocals of the prime numbers:

Screen Shot 2016-10-19 at 6.09.35 PM.png

is a divergent series. In doing so, Euler found an alternative way to prove that there was an infinite number of primes, as if there wasn’t then the series would have a finite value.

The Prime Number Theorem states that if π(x) is the number of primes less than or equal to x, then

Although the notation ~ may be unfamiliar, it simply means that π(x) is asymptotically equal to x/lnx, i.e.

Note that the prime number theorem is equivalent to saying that the nth prime number p_n satisfies the following relationship:

The PNT was proposed by Gauss in 1792 when he was only 15 years old! (Makes you wonder what you’ve been doing with your life so far…) He later refined this estimate to

$\begin{displaymath}\pi(x) \sim \int_2^x \frac{d u}{\ln{u}}.\end{displaymath}$

HAPPY HALLOWEEN! M x

MATHS BITE: The Bridges of Königsberg

In 1735, the city of Königsberg in Prussia (which is now Kaliningrad, Russia) was divided into four sections by the Pregel River. These four sections where connected by seven bridges.

Source: Wikipedia

The Königsberg bridge problem asked whether there was a walk through the city that would cross each bridge once and only once.

In 1736 Euler proved that this walk was not possible, achieving this by inventing a kind of diagram called a network, that is made up of vertices (dots where lines meet) and arcs (lines). His solution was presented to the St. Petersburg Academy in August 1735, and was published in the journal Commentarii academiae scientiarum Petropolitanae in 1741.

Screen Shot 2016-09-16 at 11.19.49 AM.png

Source: Wolfram MathWorld

This was a novel idea; Euler discovered that the physical positions of the sections do not matter, but rather it’s the connections made by the bridges that matters. Hence, by having this intuition Euler opened up a new branch of mathematics: graph theory. Euler describes how:

“. . . this type of solution bears little relationship to mathematics, and I do not understand why you expect a mathematician to produce it, rather than anyone else, for the solution is based on reason alone, and its discovery does not depend on any mathematical principle.”

So why is such a walk not possible?

Euler showed that the possibility of this walk existing – called a Eulerian path – is dependant on the degrees of the nodes. The degree of a node is how many edges touch it. He found that the necessary condition for this walk to exist is that should have exactly 0 or 2 nodes with an odd degree.

As all four of the nodes in the network of Königsberg have an odd degree, the walk does not exist.

M x

Euler’s Conjecture

The Sum of Powers Conjecture was proposed by Euler in 1769. It states that:

“for all integers $n$ and $k$ greater than 1, if the sum of $n$ $k$ th powers of non-zero integers is itself a $k$ th power, then $n$ is greater than or equal to $k$ .”

This can be more concisely written as:

If $\sum _{i=1}^{n}a_{i}^{k}=b^{k}$ , where $n > 1$ and $a 1, a 2, \dots, a n, b$ are non-zero integers, then $n \geq k$ .

Fermat’s Last Theorem is simply a special case of this conjecture: if, when n=2, $a 1 k + a 2 k = b k$ , then $2 \geq k. Hence, this conjecture can be seen to represent an attempt to generalise Fermat’s Last Theorem.$

Although it is true for n = 3, it was disproved for k = 4 and k = 5. Mathematicians still do not know whether it is true for $k \geq 6$ .

In 1966, L.J. Lander and T. R. Parkin disproved this conjecture in the shortest article in any ‘serious’ mathematical journal (Source), which consisted of merely 2 lines.

Screen Shot 2016-09-06 at 12.45.09 PM.png

This counterexample for k = 5 was found by a direct computer search on a CDC 6600 (a “flagship mainframe supercomputer”).

CDC 6600 | Source: Wikipedia

M x

The Knight’s Tour

A Knight’s Tour is a sequence of moves of a knight on a chessboard such that the knight lands on every square only once. If the knight’s tour ends on the square that it began on, then the tour path is closed. Otherwise, it is open.

Knight’s Tour | Source: Wikipedia

The Knight’s Tour is a common mathematical problem given to computer science students; it is a more general Hamiltonian path problem in graph theory. The Hamiltonian path problem is a problem of “determining whether a Hamiltonian path (a path in an undirected or directed graph that visits each vertex exactly once) exists in a given graph.”

One of the first mathematicians to analyse this problem was Euler. However, the first procedure for completing the Knight’s Tour was Warnsdorf’s rule, which was described by H.C. von Warnsdorf in 1823.

Warnsdorf’s Rule states that the knight should always move to the square from which the knight will have the “fewest onward moves”. There can be, of course, two squares which have the same number of onward moves, and consequently there are ways to break such ties, for example the methods devised by Pohl and Squirrel.

Is a Knight’s Tour always possible?

Allen Schwenk proved that for any m x n boards, where m is smaller or equal to n, a closed knight tour is always possible if one of the following conditions is met:

m and n are both odd
m = 1, 2 or 4
m=3 and n = 4, 6 or 8

Hope you enjoyed today’s post. M x

The Basel Problem

The Basel Problem is a problem in number theory posed by Pietro Mengoli in 1644, and solved by Leonhard Euler in 1734. As the problem remained open for 90 years, Euler’s solution brought him immediate fame at the age of 28.

The Basel Problem asks the result of the sum

$1+\frac{1}{4}+\frac{1}{9}+\frac{1}{16}+\frac{1}{25}+\frac{1}{36}+...$

i.e. the sum of the inverse of the square numbers.

Screen Shot 2016-08-06 at 10.52.38 AM.png

As there are infinitely many square numbers, this sum has infinitely many terms. It is possible to find the ‘result’ of this sum due to the fact that the sum converges to a particular limiting value as the denominator approaches infinity. Part of the difficulty of solving this series is because it converges very slowly; when n = 10⁶, the result is only accurate to 5 decimal places.

Euler found that the result had the value of:

Screen Shot 2016-08-06 at 10.55.45 AM.png

But how did he do this?

Firstly, recall the Taylor series expansion of sin(x):

$\sin(x)=x-{\frac {x^{3}}{3!}}+{\frac {x^{5}}{5!}}-{\frac {x^{7}}{7!}}+\cdots .$

If we divide by x, this gives us:

${\frac {\sin(x)}{x}}=1-{\frac {x^{2}}{3!}}+{\frac {x^{4}}{5!}}-{\frac {x^{6}}{7!}}+\cdots .$

Applying the Weierstrass factorisation theorem, which states that “entire functions can be represented by a product involving their zeroes” we obtain the expression:

${\begin{aligned}{\frac {\sin(x)}{x}}&=\left(1-{\frac {x}{\pi }}\right)\left(1+{\frac {x}{\pi }}\right)\left(1-{\frac {x}{2\pi }}\right)\left(1+{\frac {x}{2\pi }}\right)\left(1-{\frac {x}{3\pi }}\right)\left(1+{\frac {x}{3\pi }}\right)\cdots \\&=\left(1-{\frac {x^{2}}{\pi ^{2}}}\right)\left(1-{\frac {x^{2}}{4\pi ^{2}}}\right)\left(1-{\frac {x^{2}}{9\pi ^{2}}}\right)\cdots .\end{aligned}}$

If we multiply out this product and collect all x² terms we get:

$-\left({\frac {1}{\pi ^{2}}}+{\frac {1}{4\pi ^{2}}}+{\frac {1}{9\pi ^{2}}}+\cdots \right)=-{\frac {1}{\pi ^{2}}}\sum _{n=1}^{\infty }{\frac {1}{n^{2}}}.$

In the expansion of sin(x)/x the coefficient of x² is -1/(3!). By comparing coefficients and noting that they must be equal on each side, we can equate this as:

$-{\frac {1}{6}}=-{\frac {1}{\pi ^{2}}}\sum _{n=1}^{\infty }{\frac {1}{n^{2}}}.$

Hence, reaching a final result of

$\sum _{n=1}^{\infty }{\frac {1}{n^{2}}}={\frac {\pi ^{2}}{6}}.$

Sources: 1 | 2 | 3

M x

Maths Bite: Perfect Numbers

A perfect number is a positive integer that is equal to the sum of its proper divisors (positive divisors excluding the number itself). Equivalently, it is half the sum of all of its positive divisors.

An example of a perfect number is 6.

Source: Wikipedia

The definition of a perfect number dates back to Euclid’s Elements:

“If as many numbers as we please beginning from a unit be set out continuously in double proportion, until the sum of all becomes a prime, and if the sum multiplied into the last make some number, the product will be perfect.”

Euclid gave a rigorous proof of the connection between these numbers and Mersenne Primes, i.e. primes of the form $2 n - 1$ . This is called the formation rules and started that $q(q+1)/2$ is a perfect number whenever q is a prime of the form $2^{p}-1$ . Euler later proved that all even perfect numbers are of that form, which is now known as the Euclid-Euler theorem.

—

Proof of the Euclid-Euler Theorem: adapted from Wikipedia

The proof is short, and depends of the fact that the function of the sum of divisors is multiplicative, i.e. σ(ab) = σ(a)σ(b). For this to be valid, the divisors of a number must include the number itself, not just the proper divisors. As discussed above, a number is perfect if and only if its sum of divisors is twice its value.

Looking at the theorem in one direction:

When 2^{p − 1} is prime,

σ(2^{p − 1}(2^p − 1)) = σ(2^{p − 1})σ(2^p − 1) = (2^p − 1)2^p = 2(2^p−1(2^p − 1))

In the other direction:

Suppose that an even perfect number is given. Let us partially factor it as 2^kx where x is odd. For 2^kx to be perfect, its sum of divisors must be twice its value, thus 2^{k + 1}x = σ(2^kx) = (2^{k + 1} − 1)σ(x).

The odd factor 2^{k + 1} − 1 on the right hand side is at least three (as k is a positive integer), and it must divide or equal x. So, y = x/(2^{k + 1} − 1) is a proper divisor of x. Dividing both sides of by the common factor 2^{k + 1}− 1, and taking into account the known divisors x and y of x, gives

2^{k + 1}y = σ(x)

= x + y + other divisors

= 2^{k + 1}y + other divisors.

For this equality to be true, there can be no other divisors. Therefore, y must be 1, and x must be a prime of the form 2^{k + 1} − 1.

—

Today 46 perfect numbers are known, 2⁸⁸(2⁸⁹– 1) being the last to be discovered by hand calculations in 1911 (all the other have been found using computers).

M x

mathsbyagirl

new posts monday and thursday