Project ideas

Project Ideas

The following is a miscellanaous collection of project ideas, both mine and generated by AI.

My ideas

Desargues theorem: Characterization of affine and projective spaces in incidence geometry.
RSA Encryption
Quadratic equations and their solutions: make these computable by constructing fields.
Graph algorithms: Implement algorithms for shortest path, minimum spanning tree, etc.; a collection.
Linear Equations
Dynamics on the circle: Poincaré rotation number, periodic points, Denjoy counterexamples.
Euclidean Geometry
Classical Mechanics: For example, the harmonic oscillator, Kepler’s laws, etc.
Huffman code: Implement the Huffman coding algorithm for data compression and prove optimality (at least correctness).

Suggestions from Mistral

Certainly! Here are some modern, important, or elegant mathematical results that are not typically found in basic textbooks and have relatively short, self-contained proofs:

The Erdős–Ko–Rado Theorem:
- Statement: If ( n \geq 2k ), then the maximum size of a family of ( k )-element subsets of an ( n )-element set, in which any two subsets have at least one element in common, is ( \binom{n-1}{k-1} ).
- Proof: The proof is combinatorial and uses the method of shifting or compression. It is elegant and can be presented in a few pages.
The Friendship Theorem:
- Statement: If in a finite graph every two vertices have exactly one common neighbor, then there is a vertex adjacent to all others.
- Proof: This result is a classic in graph theory and can be proven using combinatorial arguments. The proof is short and elegant.
The Ham Sandwich Theorem:
- Statement: Given ( n ) measurable “objects” in ( n )-dimensional space, it is possible to divide all of them simultaneously with a single hyperplane.
- Proof: The proof uses the Borsuk-Ulam theorem and is a beautiful application of topological methods to a geometric problem. It can be presented in a few pages.
The Sperner’s Theorem:
- Statement: The largest antichain of subsets of an ( n )-element set has size ( \binom{n}{\lfloor n/2 \rfloor} ).
- Proof: The proof involves combinatorial arguments and the use of the LYM inequality. It is elegant and can be presented in a few pages.
The Pigeonhole Principle and its Generalizations:
- Statement: If ( n ) items are put into ( m ) containers, with ( n > m ), then at least one container must contain more than one item.
- Proof: While the basic principle is straightforward, its generalizations and applications can be quite elegant and powerful. The proofs are short and self-contained.
The Cauchy-Davenport Theorem:
- Statement: If ( A ) and ( B ) are non-empty subsets of ( \mathbb{Z}/p\mathbb{Z} ) (where ( p ) is a prime), then ( |A + B| \geq \min(p, |A| + |B| - 1) ).
- Proof: The proof uses the polynomial method and is a beautiful example of the interplay between algebra and combinatorics. It can be presented in a few pages.
The Probabilistic Method:
- Statement: Various results in combinatorics and graph theory can be proven using probabilistic arguments.
- Proof: Examples include the existence of graphs with certain properties or the Erdős–Rényi model for random graphs. The proofs are often short and elegant.
The Van der Waerden’s Theorem:
- Statement: For any given positive integers ( k ) and ( r ), there is a number ( W(k,r) ) such that if the integers ( {1, 2, \ldots, W(k,r)} ) are colored with ( r ) colors, there is always a monochromatic arithmetic progression of length ( k ).
- Proof: The proof uses the Hales-Jewett theorem and is a classic example of Ramsey theory. It can be presented in a few pages.

These results are not only important in their respective fields but also demonstrate the beauty and elegance of mathematical proofs.

Additional Suggestions

Certainly! “Period 3 implies chaos” is a famous result in dynamical systems theory, known as the Li-Yorke Theorem. Here are some more theorems that are modern, important, or elegant, and have relatively short, self-contained proofs:

Li-Yorke Theorem (Period 3 Implies Chaos):
- Statement: If a continuous function ( f ) on an interval has a point of period 3, then it has points of all periods.
- Proof: The proof is elegant and uses the concept of “scrambled sets” to show the existence of chaotic behavior. It can be presented in a few pages.
The Banach Fixed-Point Theorem:
- Statement: If ( (X, d) ) is a non-empty complete metric space and ( T: X \to X ) is a contraction mapping, then ( T ) has a unique fixed point.
- Proof: The proof is constructive and uses the method of successive approximations. It is short and elegant.
The Brouwer Fixed-Point Theorem:
- Statement: Every continuous function from a convex compact subset of a Euclidean space to itself has at least one fixed point.
- Proof: The proof can be done using combinatorial topology (Sperner’s lemma) or algebraic topology (degree theory). It is elegant and can be presented in a few pages.
The Arrow Impossibility Theorem:
- Statement: No voting system can simultaneously satisfy certain desirable properties (non-dictatorship, Pareto efficiency, independence of irrelevant alternatives, and unrestricted domain).
- Proof: The proof is combinatorial and elegant, showing the inherent limitations of voting systems. It can be presented in a few pages.
The PCP Theorem (Probabilistically Checkable Proofs):
- Statement: Every decision problem in NP has probabilistically checkable proofs with constant query complexity and logarithmic randomness.
- Proof: The proof is a major result in computational complexity theory and can be presented in a few pages, though it requires some background in complexity theory.
The Robertson-Seymour Theorem (Graph Minors):
- Statement: Any minor-closed property of finite graphs can be characterized by a finite set of minimal excluded minors.
- Proof: The proof is a deep result in graph theory and involves the concept of tree-width and graph decompositions. It can be presented in a few pages, though it requires some background in graph theory.
The Nash Embedding Theorem:
- Statement: Every Riemannian manifold can be isometrically embedded in some Euclidean space.
- Proof: The proof is a major result in differential geometry and involves the use of the implicit function theorem. It can be presented in a few pages, though it requires some background in differential geometry.
The Szemerédi Regularity Lemma:
- Statement: Every graph can be approximated by a bounded number of pseudo-random bipartite graphs.
- Proof: The proof is a fundamental result in extremal graph theory and involves the concept of ε-regular pairs. It can be presented in a few pages, though it requires some background in graph theory.
The Erdős–Szekeres Theorem:
- Statement: For any integers ( r, s \geq 2 ), any sequence of more than ( (r-1)(s-1) ) distinct real numbers contains a monotone subsequence of length ( r ) or ( s ).
- Proof: The proof is combinatorial and elegant, using the pigeonhole principle. It can be presented in a few pages.
The Lovász Local Lemma:
- Statement: A collection of “bad” events in a probability space can be avoided with positive probability if each event is independent of all but a small number of other events.
- Proof: The proof is a powerful tool in probabilistic combinatorics and can be presented in a few pages.

These theorems are not only important in their respective fields but also demonstrate the beauty and elegance of mathematical proofs. They provide deep insights into various areas of mathematics and can be appreciated with relatively short, self-contained proofs.

Suggestions for Algorithms (from Mistral)

Certainly! Here are some algorithms that can be implemented and proved in a relatively self-contained way. These algorithms are fundamental and have elegant proofs of correctness and efficiency:

Euclidean Algorithm for Greatest Common Divisor (GCD):
- Description: Computes the greatest common divisor of two integers using repeated division.
- Proof: The proof of correctness is straightforward and involves showing that the GCD of two numbers is preserved through the steps of the algorithm. The time complexity is ( O(\log(\min(a, b))) ).
Binary Search:
- Description: Finds the position of a target value within a sorted array.
- Proof: The proof of correctness involves showing that the algorithm maintains the invariant that the target, if present, is within the current search interval. The time complexity is ( O(\log n) ).
Merge Sort:
- Description: Sorts an array by dividing it into halves, sorting each half, and then merging the sorted halves.
- Proof: The proof of correctness involves showing that the merge step correctly combines two sorted arrays into one sorted array. The time complexity is ( O(n \log n) ).
Quick Sort:
- Description: Sorts an array by selecting a pivot element and partitioning the array around the pivot.
- Proof: The proof of correctness involves showing that the partition step correctly places elements relative to the pivot. The average-case time complexity is ( O(n \log n) ), but the worst-case time complexity is ( O(n^2) ).
Dijkstra’s Algorithm:
- Description: Finds the shortest paths from a source vertex to all other vertices in a weighted graph with non-negative weights.
- Proof: The proof of correctness involves showing that the algorithm maintains the shortest path tree property. The time complexity is ( O((V + E) \log V) ) using a priority queue.
Prim’s Algorithm:
- Description: Finds a minimum spanning tree for a weighted undirected graph.
- Proof: The proof of correctness involves showing that the algorithm maintains the cut property and the cycle property. The time complexity is ( O((V + E) \log V) ) using a priority queue.
Kruskal’s Algorithm:
- Description: Finds a minimum spanning tree for a weighted undirected graph using a greedy approach.
- Proof: The proof of correctness involves showing that the algorithm maintains the cut property and the cycle property. The time complexity is ( O(E \log E) ) using a disjoint-set data structure.
Floyd-Warshall Algorithm:
- Description: Finds shortest paths between all pairs of vertices in a weighted graph.
- Proof: The proof of correctness involves showing that the algorithm correctly updates the shortest path estimates. The time complexity is ( O(V^3) ).
Bellman-Ford Algorithm:
- Description: Finds shortest paths from a single source vertex to all other vertices in a weighted graph, allowing negative weights.
- Proof: The proof of correctness involves showing that the algorithm correctly relaxes edges and detects negative weight cycles. The time complexity is ( O(V \cdot E) ).
Knuth-Morris-Pratt (KMP) Algorithm:
- Description: Searches for occurrences of a pattern within a main text string.
- Proof: The proof of correctness involves showing that the prefix function is correctly computed and used to skip unnecessary comparisons. The time complexity is ( O(n + m) ), where ( n ) is the length of the text and ( m ) is the length of the pattern.
Boyer-Moore Algorithm:
- Description: Searches for occurrences of a pattern within a main text string using a more efficient skipping mechanism.
- Proof: The proof of correctness involves showing that the bad character and good suffix heuristics correctly skip unnecessary comparisons. The time complexity is ( O(n/m) ) in the best case.
Ford-Fulkerson Algorithm:
- Description: Computes the maximum flow in a flow network.
- Proof: The proof of correctness involves showing that the algorithm correctly augments flows along paths and terminates when no more augmenting paths exist. The time complexity is ( O(E \cdot f) ), where ( f ) is the maximum flow.

These algorithms are fundamental in computer science and have elegant proofs of correctness and efficiency. They can be implemented and understood with relatively short, self-contained explanations.

Certainly! Here are some algorithms that are not primarily about graphs and can be implemented and proved in a relatively self-contained way:

Gaussian Elimination:
- Description: Solves systems of linear equations by transforming the coefficient matrix into row echelon form.
- Proof: The proof of correctness involves showing that the row operations preserve the solution set and that the algorithm correctly reduces the matrix. The time complexity is ( O(n^3) ) for an ( n \times n ) matrix.
Fast Fourier Transform (FFT):
- Description: Computes the discrete Fourier transform of a sequence and its inverse.
- Proof: The proof of correctness involves showing that the algorithm correctly decomposes the problem into smaller subproblems and combines their solutions. The time complexity is ( O(n \log n) ).
Dynamic Programming Algorithms:
- Knapsack Problem:
  - Description: Solves the problem of maximizing the value of items that can be carried in a knapsack with a given capacity.
  - Proof: The proof of correctness involves showing that the recursive relation correctly computes the maximum value. The time complexity is ( O(nW) ), where ( n ) is the number of items and ( W ) is the capacity.
- Longest Common Subsequence (LCS):
  - Description: Finds the longest subsequence common to two sequences.
  - Proof: The proof of correctness involves showing that the recursive relation correctly computes the length of the LCS. The time complexity is ( O(nm) ), where ( n ) and ( m ) are the lengths of the sequences.
Karatsuba Algorithm:
- Description: Multiplies two large integers more efficiently than the standard quadratic algorithm.
- Proof: The proof of correctness involves showing that the algorithm correctly splits the numbers and combines the results. The time complexity is ( O(n^{\log_2 3}) \approx O(n^{1.58}) ).
Strassen’s Algorithm:
- Description: Multiplies two matrices more efficiently than the standard cubic algorithm.
- Proof: The proof of correctness involves showing that the algorithm correctly decomposes the problem into smaller subproblems and combines their solutions. The time complexity is ( O(n^{\log_2 7}) \approx O(n^{2.81}) ).
Convex Hull Algorithms:
- Graham’s Scan:
  - Description: Finds the convex hull of a set of points in the plane.
  - Proof: The proof of correctness involves showing that the algorithm correctly sorts the points and maintains the convex hull property. The time complexity is ( O(n \log n) ).
- Jarvis March (Gift Wrapping):
  - Description: Finds the convex hull of a set of points in the plane.
  - Proof: The proof of correctness involves showing that the algorithm correctly finds the leftmost point and wraps around the hull. The time complexity is ( O(nh) ), where ( h ) is the number of points on the hull.
Quickselect Algorithm:
- Description: Finds the k-th smallest element in an unordered list.
- Proof: The proof of correctness involves showing that the partition step correctly places elements relative to the pivot. The average-case time complexity is ( O(n) ), but the worst-case time complexity is ( O(n^2) ).
Binary Exponentiation:
- Description: Computes the power of a number efficiently using repeated squaring.
- Proof: The proof of correctness involves showing that the algorithm correctly decomposes the exponent and combines the results. The time complexity is ( O(\log n) ).
Fast Exponential Algorithms:
- Description: Computes the exponential function efficiently using techniques like scaling and squaring.
- Proof: The proof of correctness involves showing that the algorithm correctly approximates the exponential function. The time complexity is ( O(\log n) ).
Newton’s Method:
- Description: Finds successively better approximations to the roots (or zeroes) of a real-valued function.
- Proof: The proof of correctness involves showing that the algorithm converges to a root under certain conditions. The time complexity depends on the initial guess and the function’s properties.
Simplex Algorithm:
- Description: Solves linear programming problems by iteratively improving the objective function.
- Proof: The proof of correctness involves showing that the algorithm correctly pivots and improves the objective function. The time complexity is exponential in the worst case but efficient in practice.
FFT-based Polynomial Multiplication:
- Description: Multiplies two polynomials efficiently using the Fast Fourier Transform.
- Proof: The proof of correctness involves showing that the algorithm correctly transforms the polynomials, multiplies them in the frequency domain, and transforms them back. The time complexity is ( O(n \log n) ).

These algorithms cover a wide range of applications and can be implemented and understood with relatively short, self-contained explanations. They demonstrate the beauty and elegance of algorithmic solutions in various domains.

From Gemini

You’re looking for results that are surprising, have elementary proofs, and don’t require a lot of background. “Period three implies chaos” is a great example. Here are a few more in a similar vein:

The existence of transcendental numbers
- Concept: A transcendental number is a real number that is not a root of any non-zero polynomial equation with integer coefficients. In simpler terms, you can’t find any equation like axⁿ + bxⁿ⁻¹ + … + cx + d = 0 (where a, b, c, d are integers) that a transcendental number can solve. It’s surprising that such numbers exist at all!
- Striking: It shows that there are “more” numbers than those that arise from simple algebraic operations.
- Proof: Cantor’s diagonalization argument provides a relatively straightforward proof. It shows that the set of algebraic numbers (numbers that are roots of polynomial equations) is countable, while the set of real numbers is uncountable. Therefore, there must be real numbers that are not algebraic, hence transcendental.
- Background: Basic set theory (countable vs. uncountable sets).
Fermat’s Theorem on sums of two squares
- Concept: An odd prime number p can be expressed as the sum of two squares (p = x² + y² for integers x and y) if and only if p is congruent to 1 modulo 4 (i.e., p leaves a remainder of 1 when divided by 4).
- Striking: It connects number theory (prime numbers and divisibility) with algebra (sums of squares) in a neat way.
- Proof: There are several relatively elementary proofs, some using the concept of Gaussian integers (complex numbers with integer real and imaginary parts). A proof using Fermat’s method of infinite descent is also quite elegant and doesn’t require much background.
- Background: Basic number theory (divisibility, prime numbers, modular arithmetic).
Pick’s Theorem
- Concept: Given a polygon whose vertices lie on lattice points (points with integer coordinates) in the plane, the area of the polygon can be calculated using only the number of lattice points on its boundary (b) and the number of lattice points in its interior (i): Area = i + b/2 - 1.
- Striking: It’s a simple formula that relates a geometric property (area) to discrete quantities (lattice points).
- Proof: Can be done by decomposing the polygon into triangles and showing that the formula holds for triangles. Then, it can be extended to arbitrary polygons.
- Background: Basic geometry.
The infinitude of primes
- Concept: There are infinitely many prime numbers.
- Striking: It’s a fundamental result in number theory that has fascinated mathematicians for centuries.
- Proof: Euclid’s proof is a classic example of a short and elegant proof by contradiction. It assumes there are finitely many primes, multiplies them all together, adds 1, and shows that this new number must either be prime itself or divisible by a prime not in the original list, leading to a contradiction.
- Background: Basic number theory (prime numbers, divisibility).

These results have a few things in common:

They are surprising or counterintuitive.
They have relatively short and self-contained proofs.
They don’t require a lot of advanced mathematical background.

I hope these examples are closer to what you were looking for! Let me know if you have any other questions.

Algorithms from Gemini

You’re looking for algorithms with relatively simple implementations and proofs of correctness that don’t require deep theoretical background. Here are a few suggestions:

Euclid’s Algorithm for Greatest Common Divisor (GCD)
- Algorithm: Repeatedly apply the division algorithm: gcd(a, b) = gcd(b, a mod b) until b is 0. Then a is the GCD.
- Implementation (Python):
```
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a
```
- Proof: The proof relies on the fact that if d divides both a and b, it also divides a mod b, and vice-versa. This shows that the set of common divisors of (a, b) is the same as the set of common divisors of (b, a mod b). The algorithm terminates because b decreases in each step.
- Self-contained: The proof uses basic number theory (divisibility).
Binary Search
- Algorithm: Given a sorted array, repeatedly compare the target value with the middle element. If they are equal, the search is complete. If the target is smaller, search the left half; otherwise, search the right half.
- Implementation (Python):
```
def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1  # Target not found
```
- Proof: The proof is by induction on the size of the search space. In each step, the search space is halved. The algorithm terminates when the search space is empty (left > right).
- Self-contained: The proof uses basic induction.
Selection Sort
- Algorithm: Repeatedly find the minimum element from the unsorted part and put it at the beginning.
- Implementation (Python):
```
def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        min_index = i
        for j in range(i + 1, n):
            if arr[j] < arr[min_index]:
                min_index = j
        arr[i], arr[min_index] = arr[min_index], arr[i]
    return arr
```
- Proof: The proof is by loop invariant. At the beginning of each iteration of the outer loop, the subarray arr[0..i-1] is sorted and contains the i smallest elements of the original array.
- Self-contained: The proof uses basic loop invariants.

Depth-First Search (DFS) on a Tree

Algorithm: Explore as far as possible along each branch before backtracking.
Implementation (Python - recursive):

def dfs(graph, node, visited):
    visited.add(node)
    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)

# Example graph representation: adjacency list
graph = {'A': ['B', 'C'], 'B': ['D', 'E'], 'C': ['F'], 'D': [], 'E': ['F'], 'F': []}
visited = set()
dfs('A', graph, visited)
print(visited)

Proof: The proof that DFS visits all reachable nodes in a tree can be done by induction on the height of the tree.
Self-contained: The proof uses basic graph theory (trees, reachability) and induction.

Key aspects for self-contained proofs:

Induction: Often used for recursive algorithms or algorithms with loops.
Loop invariants: Useful for iterative algorithms.
Basic number theory: For algorithms dealing with integers.
Basic set theory and logic: For general algorithm analysis.

These algorithms are relatively simple to implement and understand, and their correctness can be proven using elementary mathematical techniques. This makes them good examples for learning about algorithm design and analysis.

You’re right, those are fairly standard examples. Let’s delve into some slightly less common but still accessible algorithms with relatively self-contained proofs:

Stable Matching (Gale-Shapley Algorithm)
- Problem: Given n men and n women, each with a preference list of the opposite sex, find a stable matching (a matching where no two people who are not matched both prefer each other to their current partners).
- Algorithm: The Gale-Shapley algorithm is an iterative algorithm where men propose to their most preferred woman who hasn’t rejected them yet. Women tentatively accept the best proposal they’ve received so far but can reject a current partner if a better proposal comes along.
- Proof: The proof of termination relies on the fact that once a woman is engaged, she remains engaged (though possibly to a better partner). Since there are a finite number of men, the algorithm must terminate. The proof of stability is by contradiction: if there were an unstable pair (M, W), it would mean M preferred W to his current partner, and W preferred M to her current partner. This would imply M must have proposed to W before, and W must have rejected him, which is a contradiction since she would have accepted him if she preferred him to her current partner at that time.
- Self-contained: The proof uses basic logic and set theory.
- Implementation (Python - simplified):
```
def stable_matching(men_prefs, women_prefs):
    n = len(men_prefs)
    matches = {}  # women -> men
    free_men = list(range(n))

    while free_men:
        man = free_men[0]
        woman = men_prefs[man][0] # man's most preferred woman

        if woman not in matches:
            matches[woman] = man
            free_men.pop(0)
        else:
            current_match = matches[woman]
            if women_prefs[woman].index(man) < women_prefs[woman].index(current_match):
                matches[woman] = man
                free_men.pop(0)
                free_men.append(current_match)
            else:
                men_prefs[man].pop(0) # woman rejects man, remove her from his preferences
    return matches
```
Dijkstra’s Shortest Path Algorithm (for unweighted graphs or unit weights)
- Problem: Find the shortest paths from a single source vertex to all other vertices in a graph with non-negative edge weights (we’ll focus on the simpler case of unweighted graphs here).
- Algorithm: Use Breadth-First Search (BFS). Keep track of the distance from the source to each vertex.
- Proof: The proof is by induction on the distance from the source. It can be shown that BFS visits vertices in increasing order of their distance from the source.
- Self-contained: The proof uses basic graph theory (paths, distances) and induction.
- Implementation (Python):
```
from collections import deque

def bfs_shortest_paths(graph, start):
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    queue = deque([start])

    while queue:
        node = queue.popleft()
        for neighbor in graph[node]:
            if distances[neighbor] == float('inf'):
                distances[neighbor] = distances[node] + 1
                queue.append(neighbor)
    return distances
```
Topological Sorting (for Directed Acyclic Graphs - DAGs)
- Problem: Given a DAG, find a linear ordering of its vertices such that for every directed edge uv, vertex u comes before vertex v in the ordering.
- Algorithm: Perform a Depth-First Search (DFS). When a vertex is finished being explored (i.e., all its descendants have been visited), add it to the beginning of a list.
- Proof: The proof relies on the fact that in a DAG, there are no cycles. Therefore, when a vertex is finished being explored, all its descendants must have already been visited. This ensures that the topological order is correct.
- Self-contained: The proof uses basic graph theory (DAGs, DFS).

These algorithms are a bit more involved than the previous examples, but their proofs are still accessible with a basic understanding of discrete mathematics. They also demonstrate more interesting algorithmic techniques.