Matrices

by aoum, Apr 21, 2025, 9:11 PM

Matrices: Foundations, Operations, and Applications

Matrices are fundamental mathematical objects used to represent and manipulate data in a structured way. In its simplest form, a matrix is a rectangular array of numbers arranged in rows and columns. Matrices are essential in linear algebra, and they appear in nearly every area of mathematics and its applications, including computer science, physics, and statistics.

1. Definition of a Matrix

A matrix of size $m \times n$ is an array of numbers with $m$ rows and $n$ columns:

$A = \begin{bmatrix} a_{11} & a_{12} & \cdots & a_{1n} \\ a_{21} & a_{22} & \cdots & a_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{m1} & a_{m2} & \cdots & a_{mn} \end{bmatrix}$
Each $a_{ij}$ is an element of the matrix, called the $(i,j)$ -th entry.

2. Types of Matrices

Row matrix: One row, multiple columns.
Column matrix: One column, multiple rows.
Square matrix: Same number of rows and columns.
Zero matrix: All entries are zero.
Identity matrix $I_n$ : A square matrix with $1$ on the diagonal and $0$ elsewhere.
Diagonal matrix: Nonzero entries only on the diagonal.
Symmetric matrix: A matrix $A$ such that $A = A^T$ .

3. Matrix Operations

Addition: $A + B$ is defined if $A$ and $B$ have the same dimensions:
$(A + B)_{ij} = a_{ij} + b_{ij}$
Scalar Multiplication: $cA$ scales each entry by $c$ :
$(cA)_{ij} = c \cdot a_{ij}$
Matrix Multiplication: If $A$ is $m \times n$ and $B$ is $n \times p$ , then $AB$ is $m \times p$ :
$(AB)_{ij} = \sum_{k=1}^n a_{ik} b_{kj}$
Transpose: The transpose $A^T$ switches rows and columns:
$(A^T)_{ij} = a_{ji}$

4. Determinants

For a square matrix $A$ , the determinant $\det(A)$ (or $|A|$ ) is a scalar value that reflects various properties such as invertibility. For example:

For a $2 \times 2$ matrix:
$A = \begin{bmatrix} a & b \\ c & d \end{bmatrix}, \quad \det(A) = ad - bc$
A square matrix is invertible if and only if $\det(A) \ne 0$ .

5. Inverse of a Matrix

If $A$ is an $n \times n$ invertible matrix, then its inverse $A^{-1}$ satisfies:

$A A^{-1} = A^{-1} A = I_n$
The inverse can be computed via row reduction, the adjugate matrix formula, or using Gauss–Jordan elimination.

6. Solving Linear Systems with Matrices

A system of linear equations can be written in matrix form as:

$AX = B$
Where:

$A$ is the coefficient matrix,
$X$ is the column vector of variables,
$B$ is the column vector of constants.

If $A$ is invertible, the solution is:

$X = A^{-1}B$
Alternatively, methods such as Gaussian elimination or LU decomposition can be used.

7. Eigenvalues and Eigenvectors

Let $A$ be a square matrix. A nonzero vector $v$ is an eigenvector of $A$ if:

$Av = \lambda v$
for some scalar $\lambda$ , called the eigenvalue associated with $v$ . The eigenvalues of $A$ are roots of the characteristic polynomial:

$\det(A - \lambda I) = 0$
8. Applications of Matrices

Geometry: Matrices represent rotations, reflections, and projections.
Computer Graphics: Transformations of objects in 2D/3D.
Physics: Quantum mechanics, relativity, and systems of equations.
Statistics: Covariance matrices and multivariate data analysis.
Markov Chains: State transition matrices describe probability evolution.
Network Theory: Adjacency matrices represent graphs.

9. Matrix Representations in Graph Theory

Adjacency Matrix: $A_{ij} = 1$ if there is an edge from vertex $i$ to $j$ .
Incidence Matrix: Describes relationships between vertices and edges.

10. References

Wikipedia: Matrix (mathematics)
Gilbert Strang – Linear Algebra and Its Applications
AoPS Wiki: Matrix
Axler – Linear Algebra Done Right

Matrices

Hilbert’s Hotel

by aoum, Apr 21, 2025, 9:06 PM

Hilbert’s Hotel: A Paradox of the Infinite

The Hilbert Hotel is a famous thought experiment proposed by the German mathematician David Hilbert to illustrate the strange and counterintuitive properties of infinite sets. Specifically, it demonstrates how a hotel with infinitely many rooms—all occupied—can still accommodate new guests, or even infinitely many new guests.

This scenario is not only a whimsical paradox, but also a profound insight into the nature of infinite cardinalities, particularly the size of the set $\mathbb{N}$ of natural numbers.

1. The Setup

Imagine a hotel with countably infinitely many rooms: Room $1$ , Room $2$ , Room $3$ , and so on. Each room is already occupied by one guest.

The paradox arises when new guests arrive and we must find room for them without kicking anyone out. Intuitively, a “full” hotel should not be able to accept more guests—but the infinite case is quite different.

2. Accommodating One New Guest

Suppose one new guest arrives. To make room, the hotel manager moves each guest from Room $n$ to Room $n+1$ :

$\text{Guest in Room } n \to \text{Room } n+1$
Now Room $1$ is free for the new guest. Despite being "full," the hotel accommodated another person. This works because $\mathbb{N}$ is an infinite set with no largest element.

3. Accommodating Infinitely Many New Guests

Now suppose countably infinitely many new guests arrive, numbered $1', 2', 3', \dots$

The manager shifts the current guest in Room $n$ to Room $2n$ , thus vacating all the odd-numbered rooms:

$\text{Guest in Room } n \to \text{Room } 2n$
Now Rooms $1, 3, 5, 7, \dots$ are free for the new guests. Assign guest $k'$ to Room $2k - 1$ .

4. Accommodating Countably Infinite Buses

Suppose now we have countably infinite buses, each with countably infinite guests. Let’s denote the passenger in Seat $m$ of Bus $n$ as $(n, m)$ .

The idea is to assign each pair $(n, m)$ to a unique room. One elegant method is to use the Cantor pairing function, or more simply:

$\text{Room Number} = 2^n \cdot 3^m$
Because of the Fundamental Theorem of Arithmetic, every natural number has a unique prime factorization, so this maps every pair $(n, m)$ to a unique natural number (room number). Thus, countable × countable = countable.

5. Infinite Cardinalities

The Hilbert Hotel shows that the cardinality of $\mathbb{N}$ (called $\aleph_0$ or $\aleph_0$ ) has the property:

$\aleph_0 + 1 = \aleph_0 \\ \aleph_0 + \aleph_0 = \aleph_0 \\ \aleph_0 \cdot \aleph_0 = \aleph_0$
This is completely different from finite arithmetic. For example, $10 + 1 > 10$ , but $\aleph_0 + 1 = \aleph_0$ .

6. Uncountably Many New Guests?

If uncountably many guests arrive—say, one for each real number in $[0, 1]$ —we cannot accommodate them, since the reals are uncountable, and the hotel only has countably infinite rooms.

Thus:

$|\mathbb{R}| > |\mathbb{N}|$
This shows the distinction between different “sizes” of infinity: $\aleph_0 < \mathfrak{c}$ (the cardinality of the continuum).

7. Mathematical Formalism

Hilbert’s Hotel illustrates that:

The set of natural numbers $\mathbb{N}$ is infinite.
There exist bijections between $\mathbb{N}$ and proper subsets of $\mathbb{N}$ .
Infinite cardinalities behave differently from finite ones.

A bijection $f : \mathbb{N} \to \mathbb{N} \setminus \{1\}$ exists (e.g., $f(n) = n+1$ ), so these two sets have the same cardinality.

8. Philosophical and Practical Relevance

Mathematics: Key to understanding infinite sets and cardinal arithmetic.
Set Theory: Illustrates how bijections define cardinality.
Philosophy: Challenges intuition about "completeness" and infinity.
Theoretical Computer Science: Plays a role in understanding infinite state spaces.

9. Visual Representation

To visualize Hilbert’s Hotel, think of an infinite list of rooms on a hallway. When new guests arrive, everyone “shifts over” to a new room using a deterministic rule (like $n \to n+1$ or $n \to 2n$ ), leaving infinitely many vacancies behind.

10. References

Wikipedia: Hilbert’s Paradox of the Grand Hotel
Georg Cantor – Founder of Set Theory
David Hilbert – On the Infinite
AoPS Wiki: Infinite Sets
Rudy Rucker – Infinity and the Mind

Hilberts Hotel

paradoxes

infinity

The Chicken McNugget Theorem

by aoum, Apr 21, 2025, 8:55 PM

The Chicken McNugget Theorem: Frobenius Numbers in Action

The Chicken McNugget Theorem, also known as the Frobenius Coin Problem in two variables, is a fun and famous result in elementary number theory. It gives a formula for the largest number that cannot be expressed as a non-negative integer combination of two relatively prime positive integers.

It gets its name from a problem involving McDonald's Chicken McNuggets, which used to be sold in packs of 6, 9, and 20. The classic version focuses on just two pack sizes.

1. Statement of the Chicken McNugget Theorem

Let $m$ and $n$ be two relatively prime positive integers. Then the largest integer that cannot be expressed in the form:

$am + bn, \quad \text{where } a, b \in \mathbb{Z}_{\geq 0}$
is given by:

$\boxed{mn - m - n}$
This number is known as the Frobenius number $g(m, n)$ for two variables.

2. Examples

For $m = 6$ and $n = 9$ : Since $\gcd(6, 9) = 3 \ne 1$ , the theorem does not apply.
For $m = 5$ and $n = 7$ : Since $\gcd(5, 7) = 1$ , they are coprime. The largest number not expressible as $5a + 7b$ is:

$5 \cdot 7 - 5 - 7 = 35 - 5 - 7 = \boxed{23}.$
Indeed, 23 cannot be expressed using non-negative integer combinations of 5 and 7, but all integers greater than 23 can.
For $m = 6$ and $n = 9$ and $r = 20$ : With more than two numbers, no closed formula exists, but the largest number not obtainable from combinations of 6, 9, and 20 McNuggets is $43$ .

3. Proof Sketch of the Chicken McNugget Theorem

Suppose $m$ and $n$ are positive integers with $\gcd(m, n) = 1$ . Then we are considering all numbers of the form:

$S = \{am + bn \mid a, b \in \mathbb{Z}_{\geq 0}\}.$
It turns out that all integers greater than or equal to $mn - m - n + 1$ can be expressed this way, and $mn - m - n$ is the largest integer that cannot.

The core idea involves:

The fact that because $\gcd(m, n) = 1$ , the equation $am + bn = c$ has an integer solution for all sufficiently large $c$ (by the Linear Diophantine Theorem).
Showing that for $c \ge mn - m - n + 1$ , one can always find a non-negative solution.

A rigorous proof uses the Sylvester’s theorem or the concept of the semigroup generated by $m$ and $n$ .

4. Generalization: The Frobenius Problem

For more than two integers $a_1, a_2, \dots, a_k$ , the Frobenius problem seeks the largest integer not representable as a non-negative integer combination of the $a_i$ . For $k \ge 3$ , there is no known general formula. The problem is NP-hard in general.

Notation: Let $g(a_1, a_2, \dots, a_k)$ denote the Frobenius number. Then:

$g(m, n) = mn - m - n$ when $\gcd(m, n) = 1$ .
No formula exists for $g(a_1, a_2, \dots, a_k)$ when $k \ge 3$ .

5. Applications

Number Theory: The study of semigroups and additive monoids.
Combinatorics: Integer partition problems.
Optimization and Operations Research: Coin change and resource allocation.
Computer Science: Related to NP-completeness and integer programming.

6. Related Theorems

Sylvester's Theorem: For two relatively prime positive integers $m$ and $n$ , the number of positive integers that cannot be expressed as $am + bn$ is:

$\frac{(m-1)(n-1)}{2}.$
Erdős–Graham Theorem: On linear Diophantine equations and sums of unit fractions.
Curtis's Algorithm: An algorithm for computing Frobenius numbers.

7. Visualization

One can visualize the Chicken McNugget Theorem using lattice points $(a, b)$ in the first quadrant such that $am + bn = c$ . Each such point corresponds to a solution. The unreachable points fall below a certain diagonal boundary and become sparse as $c$ increases.

8. References

AoPS Wiki: Chicken McNugget Theorem
Nathanson, M. B. – Elementary Methods in Number Theory
Beck and Robins – Computing the Continuous Discretely
Wikipedia: Coin Problem

Chicken McNugget Theorem

Diophantine Equations

by aoum, Apr 20, 2025, 10:18 PM

Diophantine Equations: Integer Solutions to Polynomial Equations

Diophantine equations are polynomial equations whose solutions are sought only in integers. Named after the ancient Greek mathematician Diophantus of Alexandria, these equations are a central topic in number theory, ranging from elementary problems to deep unsolved conjectures.

1. What Is a Diophantine Equation?

A Diophantine equation is an equation of the form:

$P(x_1, x_2, \dots, x_n) = 0$
where $P$ is a polynomial with integer coefficients, and the goal is to find integer solutions $(x_1, x_2, \dots, x_n) \in \mathbb{Z}^n$ .

2. Linear Diophantine Equations

The most basic type is the linear Diophantine equation in two variables:

$ax + by = c$
This equation has integer solutions if and only if $\gcd(a, b) \mid c$ .

Theorem: Let $a, b, c \in \mathbb{Z}$ with $\gcd(a, b) = d$ . Then $ax + by = c$ has integer solutions if and only if $d \mid c$ . If so, the general solution is:

$x = x_0 + \frac{b}{d}t, \quad y = y_0 - \frac{a}{d}t, \quad t \in \mathbb{Z},$
where $(x_0, y_0)$ is a particular solution.

Example:

Solve $12x + 18y = 6$ .

Here, $\gcd(12, 18) = 6$ , and since $6 \mid 6$ , there are solutions.

Using the extended Euclidean algorithm, one solution is $(x_0, y_0) = (-1, 1)$ . The general solution is:

$x = -1 + 3t, \quad y = 1 - 2t.$
3. The Pythagorean Equation

One of the oldest Diophantine equations is:

$x^2 + y^2 = z^2,$
whose integer solutions $(x, y, z)$ are called Pythagorean triples.

Theorem: All primitive Pythagorean triples can be generated by:

$x = m^2 - n^2, \quad y = 2mn, \quad z = m^2 + n^2,$
where $m > n$ , $\gcd(m, n) = 1$ , and $m \not\equiv n \pmod{2}$ .

Example:

Take $m = 2$ , $n = 1$ :

$x = 3, \quad y = 4, \quad z = 5.$
4. Fermat’s Last Theorem

One of the most famous Diophantine equations is:

$x^n + y^n = z^n,$
with $n \ge 3$ . Fermat claimed this equation has no positive integer solutions for $n \ge 3$ . It was eventually proven by Andrew Wiles in 1994.

5. Thue Equations and Higher-Degree Examples

More generally, Diophantine equations may involve higher-degree polynomials. The equation:

$x^3 - 2y^3 = 1$
is an example of a cubic Diophantine equation. These can be quite difficult to solve.

6. The Equation $x^2 - Dy^2 = 1$ (Pell’s Equation)

This is a classical quadratic Diophantine equation. The general solution can be found using continued fractions.

Example: Solve $x^2 - 2y^2 = 1$ .

The minimal solution is $(x_1, y_1) = (3, 2)$ . Then all solutions are given by:

$x_n + y_n\sqrt{2} = (3 + 2\sqrt{2})^n.$
7. Diophantine Sets and Hilbert’s Tenth Problem

Hilbert’s Tenth Problem asked for an algorithm to determine whether a Diophantine equation has integer solutions.

Theorem (Matiyasevich, Davis, Putnam, Robinson): There is no algorithm that can decide whether an arbitrary Diophantine equation has integer solutions. Diophantine equations are undecidable in general.

8. Integer Points on Curves

Let $f(x, y) = 0$ define a curve. The number of integer solutions may depend on the genus of the curve.

Mordell’s Theorem: If $C$ is a smooth projective curve of genus $g \ge 2$ defined over $\mathbb{Q}$ , then $C(\mathbb{Q})$ is a finite set.

9. Diophantine Approximation

This area studies how closely real numbers can be approximated by rationals. Dirichlet's approximation theorem and Roth’s theorem are fundamental here.

10. Applications

Diophantine equations appear in:

Cryptography (e.g., RSA uses Euler’s theorem)
Algebraic geometry (integral points on varieties)
Combinatorics (e.g., integer partitions)
Computational number theory

References

AoPS Wiki: Diophantine Equation
Mordell, L. J. – Diophantine Equations
Niven, Zuckerman, & Montgomery – An Introduction to the Theory of Numbers
T. Andreescu & D. Andrica – Number Theory: Structures, Examples, and Problems
Wikipedia: Diophantine Equation

Diophantine Equations

Recursion

by aoum, Apr 17, 2025, 12:11 AM

Recursion: A Foundational Principle in Mathematics and Computer Science

Recursion is a method of defining functions, sequences, and structures in terms of themselves. It is both a powerful conceptual framework and a computational technique that appears throughout mathematics, computer science, and logic.

1. Recursive Definitions

A definition is recursive if it defines an object in terms of smaller or simpler instances of itself. To ensure that recursion is well-defined, it must contain:

A base case: the simplest instance of the definition that does not involve recursion.
A recursive step: which reduces a general case to one or more simpler cases.

2. Example: Factorial Function

A classic example is the factorial function $n!$ , defined recursively by:

$n! = \begin{cases} 1 & \text{if } n = 0, \\ n \cdot (n-1)! & \text{if } n > 0. \end{cases}$
This definition satisfies:

Base case: $0! = 1$
Recursive case: $n! = n \cdot (n - 1)!$

We compute $5!$ as:
$5! = 5 \cdot 4! = 5 \cdot 4 \cdot 3! = 5 \cdot 4 \cdot 3 \cdot 2! = \dots = 120.$
3. Recursive Sequences: The Fibonacci Numbers

Defined by:

$F_0 = 0, \quad F_1 = 1,$ $F_n = F_{n-1} + F_{n-2} \quad \text{for } n \geq 2,$
this sequence grows rapidly and is deeply connected with the golden ratio $\varphi = \frac{1 + \sqrt{5}}{2}$ . The closed-form expression (Binet’s formula) is:

$F_n = \frac{\varphi^n - (1 - \varphi)^n}{\sqrt{5}}.$
4. Recursion in Proof: Mathematical Induction

Mathematical induction is the natural tool for proving properties of recursively defined objects. For example, to prove:

$F_n < 2^n \quad \text{for all } n \geq 1,$
we use induction:

Base case: $F_1 = 1 < 2$
Inductive step: Assume $F_k < 2^k$ and $F_{k-1} < 2^{k-1}$
Then:

$F_{k+1} = F_k + F_{k-1} < 2^k + 2^{k-1} = 2^{k-1}(2 + 1) = 3 \cdot 2^{k-1} < 2^{k+1}.$

5. Recursive Algorithms

Recursive functions in programming directly reflect mathematical recursion. For example, a recursive algorithm for factorial:

def factorial(n):
    if n == 0:
        return 1
    return n * factorial(n - 1)
 
# Example usage:
print(factorial(5))  # This will print the factorial of 5

def factorial(n):
    if n == 0:
        return 1
    return n * factorial(n - 1)

# Example usage:
print(factorial(5))  # This will print the factorial of 5

Recursive algorithms are concise, but may be inefficient if not optimized (e.g. naive recursive Fibonacci has exponential time).

6. Recurrence Relations

A recurrence relation expresses a term $a_n$ in terms of earlier terms. For instance:

$a_n = 3a_{n-1} + 4a_{n-2}, \quad a_0 = 2, \ a_1 = 5.$
This can be solved using characteristic equations. Let $a_n = r^n$ , then:

$r^n = 3r^{n-1} + 4r^{n-2} \Rightarrow r^2 = 3r + 4 \Rightarrow r^2 - 3r - 4 = 0.$
Solving yields roots $r = 4$ and $r = -1$ , so:

$a_n = \alpha \cdot 4^n + \beta \cdot (-1)^n.$
Constants $\alpha$ and $\beta$ are found using initial conditions.

7. Recursive Structures: Fractals

Recursion underlies self-similar geometries like the Sierpiński triangle and Koch snowflake. Each stage is constructed by recursively applying transformation rules.

Example of a Sierpinski triangle using Asymptote:

$[asy] void sierpinski(pair A, pair B, pair C, int depth) { if (depth == 0) { draw(A--B--C--cycle); } else { pair AB = midpoint(A--B); pair AC = midpoint(A--C); pair BC = midpoint(B--C); sierpinski(A, AB, AC, depth - 1); sierpinski(AB, B, BC, depth - 1); sierpinski(AC, BC, C, depth - 1); } } sierpinski((0,0), (2,0), (1,sqrt(3)), 4); [/asy]$

8. Mutual and Structural Recursion

Mutual recursion involves two or more functions defined in terms of each other.

Structural recursion refers to definitions that follow the structure of data types. For example, recursively summing a list:

def sum(L):
    if not L:  # Check if the list is empty
        return 0
    return L[0] + sum(L[1:])  # Recursively sum the list
 
# Example usage:
result = sum([1, 2, 3, 4, 5])
print(result)  # This will print the sum of the list

def sum(L):
    if not L:  # Check if the list is empty
        return 0
    return L[0] + sum(L[1:])  # Recursively sum the list

# Example usage:
result = sum([1, 2, 3, 4, 5])
print(result)  # This will print the sum of the list

9. Theoretical Insights

Recursion is essential in:

Set theory: Defining ordinals and cardinals recursively
Formal languages: Recursive grammars generate infinite languages
Logic: Gödel numbering and recursive functions in computability theory
Category theory: Fixed points and recursive objects

10. Recursive vs Iterative

While recursion and iteration can often achieve the same results, recursion emphasizes definition by self-reference, whereas iteration emphasizes repetition through control structures. Some recursive problems can be transformed into iterative solutions and vice versa.

References

AoPS Wiki: Recursion
Graham, Knuth, Patashnik – Concrete Mathematics
Grimaldi – Discrete and Combinatorial Mathematics
Sipser – Introduction to the Theory of Computation
Wikipedia: Recursion (Mathematics)

recursion

Ptolemy’s Theorem

by aoum, Apr 16, 2025, 1:06 AM

Ptolemy’s Theorem: A Classic Result in Euclidean Geometry

Ptolemy’s Theorem is a foundational result in cyclic geometry that describes a precise relationship between the sides and diagonals of a cyclic quadrilateral (a quadrilateral inscribed in a circle). Named after the ancient Greek mathematician Claudius Ptolemy, it lies at the heart of trigonometry and classical geometry.

$[asy] size(200); pair A = dir(110); pair B = dir(40); pair C = dir(-20); pair D = dir(210); draw(circle((0,0),1)); draw(A--B--C--D--cycle); draw(A--C, dashed+blue); draw(B--D, dashed+blue); label("$A$", A, NW); label("$B$", B, NE); label("$C$", C, SE); label("$D$", D, SW); label("$AC$", midpoint(A--C), NE); label("$BD$", midpoint(B--D), SW); label("$AB$", midpoint(A--B), N); label("$BC$", midpoint(B--C), E); label("$CD$", midpoint(C--D), S); label("$DA$", midpoint(D--A), W); [/asy]$

Ptolemy's theorem is a relation among these lengths in a cyclic quadrilateral.

1. Statement of Ptolemy’s Theorem

Let $ABCD$ be a cyclic quadrilateral. Then the product of the two diagonals equals the sum of the products of the two pairs of opposite sides:

$AC \cdot BD = AB \cdot CD + AD \cdot BC.$
This relation is exact if and only if the quadrilateral is inscribed in a circle.

2. Applications of Ptolemy’s Theorem

Deriving trigonometric identities
Proving special cases of triangle relationships
Solving geometry olympiad problems
Constructing chord lengths in circle geometry

3. Special Cases

If $ABCD$ is a rectangle (so $AB = CD$ and $AD = BC$ ), then the theorem reduces to the Pythagorean Theorem:

$AC^2 = AB^2 + AD^2.$
This is because in a rectangle inscribed in a circle, the diagonals are equal and intersect at right angles.

4. Proof Using Similar Triangles

Let’s outline a synthetic geometric proof:

Construct point $E$ on $AC$ such that $\angle EBD = \angle ABC$ . Then triangles $EBD$ and $ABC$ are similar (angle-angle). Therefore:

$\frac{EB}{AB} = \frac{BD}{BC} \Rightarrow EB = \frac{AB \cdot BD}{BC}.$
Similarly, one shows:

$EC = \frac{AD \cdot BC}{AB}.$
Now since $E$ lies on $AC$ , and $AC = EB + EC$ , adding gives:

$AC = \frac{AB \cdot BD}{BC} + \frac{AD \cdot BC}{AB}.$
Multiplying both sides by $BD$ and simplifying yields the result:

$AC \cdot BD = AB \cdot CD + AD \cdot BC.$
5. Ptolemy's Inequality

If the quadrilateral $ABCD$ is not cyclic, the relation becomes an inequality:

$AC \cdot BD \le AB \cdot CD + AD \cdot BC,$
with equality if and only if the quadrilateral is cyclic.

6. Coordinate Proof (Analytic Geometry)

Place the cyclic quadrilateral on the unit circle using complex numbers:

Let $A = e^{i\alpha}$ , $B = e^{i\beta}$ , $C = e^{i\gamma}$ , and $D = e^{i\delta}$ with $0 < \alpha < \beta < \gamma < \delta < 2\pi$ . Then the chord lengths correspond to:

$|AC| = |e^{i\alpha} - e^{i\gamma}|, \quad |BD| = |e^{i\beta} - e^{i\delta}|.$
Ptolemy’s Theorem follows from identities involving complex absolute values and angles.

7. Trigonometric Form of Ptolemy’s Theorem

If $ABCD$ is inscribed in a circle, and the arcs subtended by sides are known, then the theorem can also be written using the law of sines:

$\sin(\angle A) \cdot \sin(\angle C) = \sin(\angle B) \cdot \sin(\angle D).$
8. Connections and Historical Note

Ptolemy used this theorem extensively in his work Almagest to create a table of chords — the precursor to modern trigonometric functions. In that setting, he used it to find exact values for chords of angles such as $36^\circ$ and $72^\circ$ .

9. References

Wikipedia: Ptolemy’s Theorem
AoPS Wiki: Ptolemy’s Theorem
Euclid's Elements, Book XIII
Courant and Robbins, What is Mathematics?

Ptolemys Theorem

euclidean geometry

The Bell Curve

by aoum, Apr 14, 2025, 11:37 PM

The Bell Curve: Mathematics of the Normal Distribution

The Bell Curve is the common name for the graph of the normal distribution, one of the most fundamental and widely used probability distributions in mathematics, statistics, and the sciences. Its characteristic shape — symmetric, centered, and tapering off — resembles a bell.

Probability density function

https://upload.wikimedia.org/wikipedia/commons/thumb/7/74/Normal_Distribution_PDF.svg/500px-Normal_Distribution_PDF.svg.png

The red curve is the standard normal distribution.

Cumulative distribution function

https://upload.wikimedia.org/wikipedia/commons/thumb/c/ca/Normal_Distribution_CDF.svg/400px-Normal_Distribution_CDF.svg.png

1. Definition

The normal distribution with mean $\mu$ and standard deviation $\sigma > 0$ has the probability density function (PDF):

$f(x) = \frac{1}{\sigma \sqrt{2\pi}} \exp\left( -\frac{(x - \mu)^2}{2\sigma^2} \right)$
This function satisfies:

It is symmetric about $x = \mu$
It is maximized at $x = \mu$
The area under the curve is 1: $\int_{-\infty}^\infty f(x) \, dx = 1$

The standard normal distribution is the special case when $\mu = 0$ and $\sigma = 1$ :

$\phi(x) = \frac{1}{\sqrt{2\pi}} e^{-x^2/2}$
2. Properties

Mean: $\mu$
Variance: $\sigma^2$
Standard deviation: $\sigma$
Mode and median: both equal to $\mu$
The curve is bell-shaped and asymptotic to the $x$ -axis.

3. Empirical Rule (68-95-99.7 Rule)

In a normal distribution:

About 68.27% of the data falls within one standard deviation of the mean: $[\mu - \sigma, \mu + \sigma]$
About 95.45% lies within two standard deviations
About 99.73% lies within three standard deviations

This makes the bell curve a natural model for random variation in measurements.

4. Cumulative Distribution Function (CDF)

The cumulative distribution function is:

$\Phi(x) = \int_{-\infty}^x \phi(t)\,dt$
There is no closed-form expression in terms of elementary functions, but it is closely related to the error function:

$\Phi(x) = \frac{1}{2} \left[ 1 + \operatorname{erf} \left( \frac{x}{\sqrt{2}} \right) \right]$
5. Central Limit Theorem (CLT)

The Central Limit Theorem states that the sum (or average) of many independent random variables, regardless of their individual distributions, tends to a normal distribution as the number of variables grows.

This explains why the bell curve appears so frequently in nature, science, and statistics.

6. Standardization

Any normal variable $X \sim N(\mu, \sigma^2)$ can be converted to a standard normal variable $Z$ using:

$Z = \frac{X - \mu}{\sigma}$
This transformation allows use of standard normal tables.

7. Applications

The bell curve is used to model:

Measurement errors
Heights and weights
IQ scores
Test scores
Brownian motion
Many statistical inference procedures (confidence intervals, hypothesis testing)

8. Moments and Moment Generating Function

The moment generating function (MGF) of $X \sim N(\mu, \sigma^2)$ is:

$M_X(t) = \mathbb{E}[e^{tX}] = \exp\left( \mu t + \frac{1}{2} \sigma^2 t^2 \right)$
The $n$ -th moment is:

$\mathbb{E}[X^n] = M_X^{(n)}(0)$
9. Derivation from First Principles (Sketch)

One way to derive the normal distribution is from the requirement that it maximizes entropy among all continuous distributions with a given mean and variance. Another is via the De Moivre–Laplace limit theorem (a special case of the CLT).

Alternatively, it arises as the limit of binomial distributions:

$\binom{n}{k} p^k (1-p)^{n-k} \approx \phi\left( \frac{k - np}{\sqrt{np(1-p)}} \right)$
10. Reference Integrals

The key integral (used in normalization) is:

$\int_{-\infty}^\infty e^{-x^2} dx = \sqrt{\pi}$
and

$\int_{-\infty}^\infty e^{-(x - \mu)^2 / (2\sigma^2)} dx = \sigma \sqrt{2\pi}$
11. References

Wikipedia: Normal Distribution
Feller, W. An Introduction to Probability Theory and Its Applications
AoPS Wiki: Normal Distribution
Papoulis, A. Probability, Random Variables, and Stochastic Processes

Bell Curve

normal distribution

statistics

The Sierpiński Carpet

by aoum, Apr 13, 2025, 11:01 PM

The Sierpiński Carpet: A Classic Fractal of Infinite Complexity

The Sierpiński carpet is one of the most famous examples of a self-similar fractal, first described by Wacław Sierpiński in 1916. It is a two-dimensional generalization of the Sierpiński triangle, constructed by recursively removing central squares from a grid. Despite being infinitely complex, it has elegant mathematical properties involving dimension, measure, and topology.

https://upload.wikimedia.org/wikipedia/commons/thumb/2/28/Animated_Sierpinski_carpet.gif/250px-Animated_Sierpinski_carpet.gif

6 steps of a Sierpiński carpet.

1. Construction of the Sierpiński Carpet

The Sierpiński carpet is built using the following recursive algorithm:

Start with a unit square (generation 0).
Divide it into 9 equal smaller squares (like a tic-tac-toe grid).
Remove the open middle square.
Apply the same process recursively to each of the 8 remaining squares.
Repeat this process infinitely.

Let $C_n$ denote the $n$ th iteration of the Sierpiński carpet.

2. Area and Perimeter

Let’s calculate the total area after $n$ iterations:

At each iteration:

The total number of squares increases by a factor of 8.
Each square is scaled by a factor of $\frac{1}{3}$ in both dimensions.

So:

Number of squares at iteration $n$ : $8^n$
Area of each square: $\left(\frac{1}{3}\right)^{2n} = \frac{1}{9^n}$
Total area: $A_n = 8^n \cdot \frac{1}{9^n} = \left(\frac{8}{9}\right)^n$

Hence:
$\lim_{n \to \infty} A_n = \lim_{n \to \infty} \left( \frac{8}{9} \right)^n = 0$
Thus, the area of the Sierpiński carpet is zero, even though it occupies a full square in the limit.

Perimeter becomes infinite as the number of boundaries grows without bound.

3. Hausdorff Dimension

To find the Hausdorff dimension, we use the formula for self-similar fractals:

If the carpet is made of $N$ self-similar copies of scale $r$ , then:

$d = \frac{\log N}{\log \frac{1}{r}} = \frac{\log 8}{\log 3} \approx 1.8928$
So, the dimension lies between 1 and 2 — it is more than a line, but less than a surface.

4. Topological and Geometric Properties

The Sierpiński carpet is nowhere dense and totally disconnected in measure.
It is self-similar — it looks the same at any magnification.
It is universal for 1-dimensional planar curves: any such curve can be embedded in it.
It has zero Lebesgue measure but is uncountable.

5. Generalizations

The Menger sponge is the 3D analog of the Sierpiński carpet.
The Sierpiński–Menger cube is another hybrid.
Higher-dimensional analogs can be defined using similar removal patterns.

6. Applications

The Sierpiński carpet appears in:

Modeling porous materials.
Antenna design (e.g. fractal antennas).
Image compression and recursive rendering.
Topological counterexamples in mathematical logic.

7. References

Wikipedia: Sierpiński Carpet
Falconer, K. Fractal Geometry: Mathematical Foundations and Applications
Mandelbrot, B. The Fractal Geometry of Nature
AoPS Wiki: Sierpiński Carpet

Sierpiski Carpet

Fractals

The Sierpiński Triangle

by aoum, Apr 13, 2025, 10:55 PM

The Sierpiński Triangle: A Fractal of Recursive Simplicity

The Sierpiński triangle, also known as the Sierpiński gasket or Sierpiński sieve, is one of the most iconic and fundamental fractals in mathematics. It is named after the Polish mathematician Wacław Sierpiński, who described it in 1915, though it appeared earlier in the art of the Italian mathematician Giulio Ucelli in the 13th century.
$[asy] size(150); void sierpinski(pair A, pair B, pair C, int n) { if (n == 0) { fill(A--B--C--cycle, gray(0.7)); return; } pair AB = (A + B)/2; pair BC = (B + C)/2; pair CA = (C + A)/2; sierpinski(A, AB, CA, n - 1); sierpinski(AB, B, BC, n - 1); sierpinski(CA, BC, C, n - 1); } pair A = (0,0), B = (4,0), C = (2,3.464); sierpinski(A, B, C, 5); [/asy]$

The Sierpiński triangle

1. Construction

The Sierpiński triangle is formed using a recursive process:

Start with an equilateral triangle.
Subdivide it into four smaller congruent equilateral triangles.
Remove the central triangle.
Repeat the process for each of the remaining smaller triangles.

This process is repeated infinitely to produce the full fractal.

2. Number of Triangles and Area

At iteration $n$ :

The number of black (filled) triangles is $3^n$ .
The side length of each triangle is scaled by a factor of $\left(\frac{1}{2}\right)^n$ .
The total area removed after $n$ steps is:
$A_{\text{removed}} = A_0 \left(1 - \left(\frac{3}{4}\right)^n\right)$ where $A_0$ is the area of the original triangle.
Thus, the remaining area after $n$ iterations is:
$A_n = A_0 \cdot \left(\frac{3}{4}\right)^n$
As $n \to \infty$ , $A_n \to 0$

So the total area of the limiting Sierpiński triangle is 0, despite having an infinite number of points.

3. Hausdorff Dimension

Using the formula for self-similar fractals:

If there are $N$ self-similar pieces scaled by a factor of $r$ , then:

$d = \frac{\log N}{\log(1/r)} = \frac{\log 3}{\log 2} \approx 1.58496$
This is between 1 and 2, so the Sierpiński triangle is "more than a line" but "less than a surface".

4. Binary Representation and Pascal’s Triangle

An amazing fact: the Sierpiński triangle appears in Pascal's Triangle modulo 2.

Construct Pascal’s triangle and color in the odd numbers (1 mod 2), leaving the even numbers blank. The resulting pattern forms the Sierpiński triangle!

This comes from the identity:

$\binom{n}{k} \equiv 1 \pmod{2} \iff \text{no carry when adding } k \text{ and } n-k \text{ in binary}$
5. Topological Properties

It is a closed set.
It is nowhere dense in the plane.
It is uncountable, yet has measure zero.
It is totally disconnected in measure but path-connected in the topological sense.

6. Relation to Other Fractals

The Sierpiński carpet is the 2D square analog.
The Menger sponge is a 3D analog.
The Vicsek fractal and Cantor dust share similar recursive properties.

7. Recursive Coordinates and Geometry

Let the initial triangle have vertices at:

$A = (0,0), \quad B = (1,0), \quad C = \left(\frac{1}{2}, \frac{\sqrt{3}}{2}\right)$
Then each recursive iteration subdivides each triangle using midpoints:

$D = \text{midpoint}(AB)$
$E = \text{midpoint}(BC)$
$F = \text{midpoint}(CA)$

This recursive generation makes the Sierpiński triangle well-suited to algorithms and coding.

8. Applications

Sierpiński triangles appear in:

Fractal antennas (compact and efficient multiband antennas)
Computer graphics (recursive modeling, procedural generation)
Chaos theory and cellular automata (Rule 90 produces the triangle)
Teaching recursion and binary numbers
Compression algorithms and self-similarity studies

9. References

Wikipedia: Sierpiński Triangle
Mandelbrot, B. The Fractal Geometry of Nature
AoPS Wiki: Sierpiński Triangle
Falconer, K. Fractal Geometry: Mathematical Foundations and Applications

Would you like to go deeper into the connection with Pascal's triangle, or see the chaos game method for generating it randomly?

This post has been edited 1 time. Last edited by aoum, Apr 13, 2025, 10:56 PM
Reason: Added image caption

Sierpiski Triangle

Fractals

The Graph Minor Theorem

by aoum, Apr 12, 2025, 12:41 AM

The Graph Minor Theorem: A Landmark in Graph Theory

The Robertson–Seymour Graph Minor Theorem, also known as the Graph Minor Theorem, is one of the most celebrated and far-reaching results in modern graph theory. It is the culmination of a massive 23-part series by Neil Robertson and Paul Seymour, published between 1983 and 2004. The theorem has deep implications for structural graph theory, algorithms, and even mathematical logic.

https://upload.wikimedia.org/wikipedia/commons/thumb/0/04/Petersen_family.svg/250px-Petersen_family.svg.png

The Petersen family, the obstruction set for link-less embedding

1. Terminology and Definitions

Let us begin by introducing some essential concepts.

Graph Minor: A graph is called a minor of a graph if can be obtained from by a sequence of:
- edge deletions,
- vertex deletions,
- edge contractions.
Minor-Closed Family: A class $\mathcal{C}$ of graphs is minor-closed if for every graph $G \in \mathcal{C}$ , all minors of $G$ also belong to $\mathcal{C}$ .
Forbidden Minors: A minor-closed class can be described by a (possibly infinite) set of graphs $\{H_1, H_2, \dots\}$ such that no $H_i$ is a minor of any graph in the class.

2. Statement of the Theorem

Quote:

Graph Minor Theorem (Robertson–Seymour, 2004):
Let $\mathcal{G}$ be any minor-closed class of finite undirected graphs. Then $\mathcal{G}$ can be characterized by a finite set of forbidden minors.

That is:

$\text{If a class of graphs is closed under taking minors, then there exists a finite set of forbidden minors.}$
This result is also known as the finite obstruction set theorem.

3. Examples

Planar Graphs: The class of planar graphs is minor-closed. By Kuratowski’s Theorem, a graph is planar iff it does not contain $K_5$ or $K_{3,3}$ as a minor. So the forbidden minor set is $\{K_5, K_{3,3}\}$ .
Graphs of Treewidth ≤ $k$ : Also minor-closed. The Graph Minor Theorem implies that there is a finite set of graphs such that a graph has treewidth greater than $k$ iff it contains one of them as a minor.

4. Consequences

The implications of this theorem are vast:

Structural Graph Theory: It allows the classification of graph families by finite obstructions.
Algorithmic Meta-Theorems: For many problems, if the input graph is in a minor-closed family, then the problem becomes tractable.
Graph Minors Series: The proof spans over 500 pages and includes foundational results such as:
- Graph structure theorem,
- Well-quasi-ordering of graphs under minors (see Kruskal’s Tree Theorem),
- Treewidth and pathwidth theories.

5. Well-Quasi-Ordering of Graphs

The Graph Minor Theorem builds upon the deep fact that finite graphs are well-quasi-ordered under the minor relation.

That is, in any infinite sequence of finite graphs:

$G_1, G_2, G_3, \dots$
there exist $i < j$ such that $G_i$ is a minor of $G_j$ . This generalizes Kruskal's Tree Theorem (which handles trees) to arbitrary finite graphs.

6. Implications in Logic and Proof Theory

The Graph Minor Theorem is so complex that it cannot be proved in certain formal logical systems:

It is unprovable in Peano Arithmetic.
Its full strength lies beyond many standard axiomatic systems like ATR $_0$ (arithmetical transfinite recursion).
It’s one of the most natural examples of a mathematical theorem with high proof-theoretic complexity.

7. Algorithmic Consequences

The theorem implies the following:

For any minor-closed property $P$ , there exists a polynomial-time algorithm (with very high constants) to test whether a graph satisfies $P$ .
This is because the forbidden minors can, in theory, be computed, and minor-checking can be done in polynomial time (Robertson & Seymour, 1995).
For example, recognizing graphs with genus $\leq g$ is decidable in polynomial time.

8. Proof Strategy (High-Level Sketch)

The proof is extremely technical and proceeds in stages:

Define the concept of a tangle to understand high-connectivity regions of graphs.
Decompose graphs using tree-decompositions to reduce complexity.
Show that any class of graphs closed under minors is well-quasi-ordered.
From WQO, deduce the existence of a finite obstruction set.
Develop a massive machinery of structural graph theory to manage large and complex graphs.

9. Further Developments

Since the original theorem:

It has been extended to graphs with labels, embeddings, directed graphs, etc.
Inspired algorithmic metatheorems such as Courcelle’s Theorem, which states that properties expressible in monadic second-order logic are decidable on graphs of bounded treewidth.
Led to fixed-parameter tractability for many problems previously considered intractable.

10. References

Robertson, N., Seymour, P. D. Graph Minors I–XXIII, J. Comb. Theory Series B (1983–2004).
Wikipedia: Graph Minor Theorem
Diestel, R. Graph Theory, Springer.
AoPS Wiki: Graph Minor
Thomas, R. A survey of the Graph Minor Theorem
Downey and Fellows, Parameterized Complexity

Graph Minor Theorem

graph theory

Submit

um this does seem slightly similar to ai
by electric_pi, Yesterday at 11:24 PM
100 posts!
by aoum, Yesterday at 9:11 PM
Very very very very very very very very very very very very very very very very very very very very very very very very very very very very very very very very very very very very very very very very cool (The maximum of the factorial machine is 7228！
by Coin1, Yesterday at 4:44 AM
cool blog and good content but it looks eerily similar to chatgpt
by SirAppel, Apr 17, 2025, 1:28 AM
1,000 views!
by aoum, Apr 17, 2025, 12:25 AM
Excellent blog. Contribute?
by zhenghua, Apr 10, 2025, 1:27 AM
Are you asking to contribute or to be notified whenever a post is published?
by aoum, Apr 10, 2025, 12:20 AM
nice blog! love the dedication c:
can i have contrib to be notified whenever you post?
by akliu, Apr 10, 2025, 12:08 AM
WOAH I JUST CAME HERE, CSS IS CRAZY
by HacheB2031, Apr 8, 2025, 5:05 AM
Thanks! I'm happy to hear that! How is the new CSS? If you don't like it, I can go back.
by aoum, Apr 8, 2025, 12:42 AM
This is such a cool blog! Just a suggestion, but I feel like it would look a bit better if the entries were wider. They're really skinny right now, which makes the posts seem a lot longer.
by Catcumber, Apr 4, 2025, 11:16 PM
The first few posts for April are out!
by aoum, Apr 1, 2025, 11:51 PM
Sure! I understand that it would be quite a bit to take in.
by aoum, Apr 1, 2025, 11:08 PM
No, but it is a lot to take in. Also, could you do the Gamma Function next?
by HacheB2031, Apr 1, 2025, 3:04 AM
Am I going too fast? Would you like me to slow down?
by aoum, Mar 31, 2025, 11:34 PM
That's nice to know. I'm also learning new, interesting things on here myself, too.
by aoum, Mar 7, 2025, 11:35 PM
Reading the fun facts and all from this blog's material makes me feel so at ease when using formulas. like, I finally understand the backstory of it and all that even teachers don't teach
by expiredcraker, Mar 7, 2025, 4:50 AM
Thanks! There are many interesting things about math out there, and I hope to share them with you all. I'll be posting more of these!
by aoum, Mar 7, 2025, 12:56 AM
Wow. This is a very interesting blog! I could really use this advice!
by rayliu985, Mar 7, 2025, 12:43 AM
Thanks! Nice to hear that!
by aoum, Mar 6, 2025, 10:56 PM
blog is great
by HacheB2031, Mar 6, 2025, 5:45 AM
Yes, I'll be doing problems of the day every day.
by aoum, Mar 5, 2025, 1:15 AM
I think it would also be cool if you did a problem of the day every day, as I see from today's problem.
by jocaleby1, Mar 5, 2025, 1:13 AM
Do you guys like my "lectures" or would you like something else?
by aoum, Mar 4, 2025, 10:37 PM
Yeah, keep on making these "lectures"
by jocaleby1, Mar 4, 2025, 2:41 AM
Thanks! Glad to hear that!
by aoum, Mar 3, 2025, 10:28 PM
ME ME ME OMG I need a math mentor like this your explanation is so easy to understand! also 3rd shout!
by expiredcraker, Mar 3, 2025, 3:32 AM
Anyone wants to contribute to my blog? Shout or give me a friend request!
by aoum, Mar 2, 2025, 3:22 PM
Nice blog! Contrib?
by jocaleby1, Mar 1, 2025, 6:43 PM

59 shouts

Pi in the Sky