Top 100 Mathematical Theorems
Pure Mathematics Theorem ProvingBesides program verification, ImandraX works as an interactive theorem prover for mathematics. In an ongoing project, Grant Passmore has formalized 33 theorems from Freek Wiedijk's "Formalizing 100 Theorems" list in ImandraX, the same benchmark used to compare Lean, Coq and Isabelle.
Overview
Freek Wiedijk's list tracks which proof assistants have formalized 100 important mathematical theorems. This ongoing formalization effort covers a growing collection of results, spanning number theory, real analysis, combinatorics, probability, geometry, and algebra.
All proofs are written in IML and verified using ImandraX's automated reasoning, combining the inductive waterfall, nonlinear arithmetic, and lightweight tactic guidance.
| # | Theorem | Key Technique |
|---|---|---|
| 1 | Irrationality of √2 | Modular arithmetic, GCD |
| 3 | Denumerability of the Rationals | Cantor pairing, bijection |
| 4 | Pythagorean Theorem | Polynomial identity, auto |
| 10 | Euler's Generalization of Fermat's Little Theorem | Permuting coprime residues, cancellation |
| 11 | Infinitude of Primes | Euclid's construction, idempotent smallest-divisor |
| 19 | Lagrange's Four-Square Theorem | Euler's four-square identity, descent |
| 20 | Fermat's Two-Square Theorem | Wilson's theorem, descent |
| 23 | Formula for Pythagorean Triples | Euclid's formula, lowest-terms uniqueness |
| 27 | Sum of Interior Angles = 180° | Algebraic geometry, parallel construction |
| 30 | Ballot Problem | Induction over permutations, factorial algebra |
| 34 | Divergence of Harmonic Series | Dyadic blocks, monotonicity |
| 38 | Arithmetic Mean/Geometric Mean | Young's inequality, list induction |
| 42 | Sum of Reciprocals of Triangular Numbers | Telescoping, nonlinear arithmetic |
| 44 | Binomial Theorem | Pascal's identity, induction |
| 51 | Wilson's Theorem | Pairing with modular inverses |
| 52 | Number of Subsets | Powerset induction, auto |
| 54 | Königsberg Bridges | Exhaustive + parity argument |
| 57 | Cube Dissection Impossibility | Pigeonhole, geometric axioms |
| 58 | Number of Combinations | Factorial algebra, Pascal |
| 60 | Bézout's Theorem | Extended GCD, subtraction recursion |
| 65 | Isosceles Triangle Theorem | Polynomial angle equality |
| 66 | Sum of a Geometric Series | Induction on the sequence recognizer |
| 68 | Sum of an Arithmetic Series | Induction, polynomial identity |
| 69 | GCD Algorithm | Euclidean GCD, divisibility |
| 73 | Ascending or Descending Sequences | Length labels, pigeonhole |
| 74 | Principle of Mathematical Induction | Minimal counterexample |
| 77 | Sum of Kth Powers | Bernoulli polynomials, telescoping |
| 78 | Cauchy-Schwarz Inequality | Projection formula, sqrt monotonicity |
| 80 | Fundamental Theorem of Arithmetic | Euclid's lemma, multiset permutation |
| 85 | Divisibility by 3 Rule | Digit-sum congruence, modular arithmetic |
| 88 | Derangements Formula | Recurrence-based generator, counting |
| 89 | Factor and Remainder Theorem | Synthetic division, list induction |
| 91 | Triangle Inequality | Cauchy-Schwarz, unsquaring |
| 93 | Birthday Problem | Exact integer bounds, evaluation |
| 96 | Inclusion/Exclusion | Per-element counting, binomial sums |
Theorem 1: Irrationality of √2
The proof that no rational number, when squared, equals 2. The argument proceeds via modular arithmetic: if p² = 2q² with gcd(p,q) = 1, then both p and q must be even, contradicting coprimality.
The proof builds through a chain of lemmas on squares modulo 2 and modulo 4:
theorem square_even_iff_even x =
((x * x) mod 2 = 0) = (x mod 2 = 0)
theorem square_mod4_even x =
x mod 2 = 0 ==> (x*x) mod 4 = 0
theorem square_mod4_odd x =
x mod 2 = 1 ==> (x*x) mod 4 = 1These combine to show both p and q must be even:
theorem no_coprime_solution_p2_eq_2q2 p q =
(gcd p q = 1 && p*p = 2*(q*q)) ==> false
[@@by [%use p_even_from_eq p q]
@> [%use q_even_from_eq p q]
@> [%use gcd_absorbs_common_divisor 2 p q]
@> auto]The final theorem lifts this to normalized rationals:
theorem sqrt2_is_irrational (r:Rational.t) =
Rational.is_reduced r
==> Rational.square r <> Rational.of_int 2Theorem 3: Denumerability of the Rationals
A constructive proof that the rationals are countable, using Cantor's pairing function as the foundation. The encoding maps each rational p/q to a natural number by encoding sign bits and absolute values via nested Cantor pairs:
let encode (q:Rational.t) : int =
let n1,n2,n3,n4 = encode_terms q in
let f = Cantor.cantor_pair in
f (n1, f (n2, f (n3, n4)))The key results about the Cantor pairing function itself:
theorem cantor_pair_onto n =
let (a, b) = cantor_pair_inverse n in
n >= 0 ==> a >= 0 && b >= 0 && cantor_pair (a, b) = n
theorem cantor_pair_one_one a b a' b' =
a >= 0 && b >= 0 && a' >= 0 && b' >= 0
&& cantor_pair (a,b) = cantor_pair (a',b')
==> a = a' && b = b'The main theorem establishes the surjection from ℕ to ℚ:
theorem rationals_denumerable_surj (q : Rational.t) =
Bijection.surj decode encode
(fun n -> n >= 0) (fun (_:Rational.t) -> true) qTheorem 4: Pythagorean Theorem
Two formulations. The coordinate-level statement is purely polynomial in 6 reals:
theorem pythagoras_coords (ax:real) (ay:real) (bx:real) (by:real) (cx:real) (cy:real) =
(* Right angle at C *)
(((ax - cx) * (bx - cx) + (ay - cy) * (by - cy)) = 0.0)
==> (* |AB|² = |AC|² + |BC|² *)
(((ax - bx) * (ax - bx) + (ay - by) * (ay - by))
= ((ax - cx) * (ax - cx) + (ay - cy) * (ay - cy)
+ (bx - cx) * (bx - cx) + (by - cy) * (by - cy)))
[@@by auto]The geometric version uses vector predicates over ℝ²:
theorem pythagoras (a : point) (b : point) (c : point) =
right_at c a b ==> dist2 a b = Real.(dist2 a c + dist2 b c)
[@@by auto]Both are fully automatic: auto handles the polynomial identity directly.
Theorem 10: Euler's Generalization of Fermat's Little Theorem
If a is coprime to n, then a^φ(n) ≡ 1 (mod n), where φ(n) counts the integers in [1, n-1] coprime to n:
theorem euler a n =
n >= 2 && 1 <= a && a < n && gcd a n = 1
==> pow a (phi n) mod n = 1Multiplying each coprime residue by a permutes the residues mod n, so both lists have the same product P mod n. That gives a^φ(n) · P ≡ P:
lemma euler_step2 a n =
n >= 2 && 1 <= a && a < n && gcd a n = 1
==> (pow a (phi n) * list_prod_mod (coprime_list n (n - 1)) n) mod n
= list_prod_mod (coprime_list n (n - 1)) n
[@@by
[%use euler_step1 a n]
@> [%use scale_mod_product a n (coprime_list n (n - 1))]
@> unroll 10]P is itself coprime to n, so it cancels. The file builds on the GCD and Wilson's theorem developments.
Theorem 11: Infinitude of Primes
Euclid's classic argument: for any n, the smallest divisor of n! + 1 is a prime greater than n. The proof requires several deep lemmas:
prod_upto_mod_zero: everyk <= ndividesn!no_small_divisor_for_euclid_sum: nok ∈ [2..n]dividesn! + 1sd_idempotent: the smallest-divisor function is idempotent (its output is prime)euclid_gt_n: the constructed prime exceedsn
theorem infinitude_of_primes n =
let bigger_prime = euclid (abs n) in
is_prime bigger_prime && bigger_prime > n
[@@by [%use euclid_is_prime (abs n)]
@> [%use euclid_gt_n (abs n)] @> auto]The idempotency theorem sd_idempotent is one of the deepest lemmas: it establishes that the smallest divisor of m is itself prime by showing that sd(sd(m)) = sd(m). This uses transitivity of divisibility and the strict minimality property.
Theorem 19: Lagrange's Four-Square Theorem
Every non-negative integer is a sum of four squares. The function witness_for computes the four numbers:
theorem four_squares_theorem n =
n >= 0 ==>
let w = witness_for n in
n = (w.a * w.a) + (w.b * w.b) + (w.c * w.c) + (w.d * w.d)Euler's four-square identity makes sums of four squares closed under multiplication:
theorem sum4_prod4 q r =
sum4 q * sum4 r = sum4 (prod4 q r)
[@@by simplify () @> nonlin ()]For each odd prime p, a pigeonhole argument finds some m·p with 1 <= m < p that is a sum of four squares, and a recursive descent reduces m to 1. The theorem then follows for all n by multiplying the prime witnesses along the prime factorization from Theorem 80.
Theorem 20: Fermat's Two-Square Theorem
Every prime p ≡ 1 (mod 4) is a sum of two squares:
theorem two_squares_theorem p =
Inf_primes.is_prime p && p mod 4 = 1
==>
let w = prime_witness p in
p = (w.a * w.a) + (w.b * w.b)The starting point comes from Wilson's theorem (Theorem 51): ((p-1)/2)!² ≡ -1 (mod p), so ((p-1)/2)!² + 1 is a multiple m·p with 1 <= m < p. As in the four-square proof, a recursive descent using the Brahmagupta–Fibonacci identity reduces m to 1.
Theorem 23: Formula for Pythagorean Triples
Euclid's formula (m² - n², 2mn, m² + n²) generates exactly the primitive Pythagorean triples. Both directions are proved. The forward direction:
theorem pythagorean_triples_forward m n =
m > n && n > 0 && Gcd.gcd m n = 1 && (m + n) mod 2 = 1
==>
let a = euclid_a m n in
let b = euclid_b m n in
let c = euclid_c m n in
a * a + b * b = c * c
&& a > 0 && b > 0 && c > 0
&& Gcd.gcd a c = 1The equation itself is a polynomial identity:
theorem pythagorean_equation m n =
let a = euclid_a m n in
let b = euclid_b m n in
let c = euclid_c m n in
a * a + b * b = c * c
[@@by [%simp_only euclid_a, euclid_b, euclid_c] @> nonlin ()]For the converse, pythagorean_triples_necessity computes the generators from the triple, m = (a + c) / gcd(a + c, b) and n = b / gcd(a + c, b). It then shows they reproduce the triple, using a lemma that two fractions in lowest terms with the same value have the same numerator and denominator. When a is even, the proof swaps a and b.
Theorem 27: Triangle Interior Angles
An algebraic proof that the interior angles of any nondegenerate triangle sum to 180°. Without trigonometry, angles are represented as ordered pairs of nonzero vectors, with equality defined via the polynomial condition cos² θ₁ = cos² θ₂.
The construction draws a line through vertex A parallel to BC:
let d_point (a:point) (b:point) (c:point) : point = add a (sub c b) (* AD = BC *)
let e_point (a:point) (b:point) (c:point) : point = add a (sub b c) (* AE = -BC *)The theorem witnesses three consecutive angles along this straight line that match the triangle's interior angles:
theorem triangle_interior_angles_sum_to_180 (a:point) (b:point) (c:point) =
neqp a b && neqp b c && neqp c a && noncollinear a b c
==> angles_sum_to_straight
(angB_u b a) (angB_v b c)
(angA_u a b) (angA_v a c)
(angC_u c a) (angC_v c b)
[@@by intros
@> ... exists r1 r2 r3
@> [%simp_only ...] @> nonlin ()]The final step reduces to a polynomial identity discharged by nonlin().
Theorem 30: The Ballot Problem
If candidate A gets a votes and B gets b < a, the probability that A stays strictly ahead throughout the count is (a - b) / (a + b). The theorem states this in integer form by counting favorable orderings among all permutations of the voters:
theorem ballot_theorem (p : int list) e =
Sets.dlistp p
==> num_favs (perms p) e * List.length p
= (if a_count p e > b_count p e
then a_count p e - b_count p e
else 0)
* Combinations.fact (List.length p)The core lemma ballot_gen counts favorable orderings by induction following the permutation generator, using a custom induction scheme. A factorial identity then reduces the count to the closed form:
lemma ballot_arith n a =
n >= 2
==> (Combinations.fact (n - 2) * (n * (1 - n + 2*a) - 2*a)) * n
= (2*a - n) * Combinations.fact n
[@@by
[%use fact_split n]
@> [%use ballot_arith_core n a (Combinations.fact (n - 2))]
@> nonlin ()]Theorem 34: Divergence of the Harmonic Series
The proof that H(n) = 1 + 1/2 + ... + 1/n grows without bound. The key insight: each dyadic block [2^{k-1}+1 .. 2^k] contributes at least 1/2 to the sum.
theorem harmonic_extend_lower_bound_corollary k =
k >= 1 ==> harmonic_extend (exp2 (k-1)) (exp2 k) >=. (1.0 /. 2.0)This gives the lower bound H(2^k) ≥ 1 + k/2:
theorem harmonic_sum_lower_bound k =
k >= 1 ==> harmonic_sum (exp2 k) >=. (1.0 +. (_R k /. 2.0))Combined with monotonicity of H, this yields:
theorem harmonic_series_diverges m n =
m >= 0 && n >= exp2 (2*m)
==> harmonic_sum n >. Real.of_int mTheorem 38: Arithmetic Mean/Geometric Mean
For non-negative reals, the arithmetic mean is at least the geometric mean. The geometric mean is given relationally as a g >= 0 with gⁿ = prod xs:
theorem am_gm xs g =
xs <> []
&& all_nonneg xs
&& g >=. 0.0
&& real_pow g (List.length xs) = prod xs
==> Real.of_int (List.length xs) *. g <=. sum xsThe proof starts from the inequality xⁿ⁺¹ - (n+1)x + n >= 0 for x >= 0, proved by induction:
lemma hirschhorn_nonneg (x : real) (n : int) =
x >=. 0.0 && n >= 0 ==> hirschhorn x n >=. 0.0A scaled version of it gives Young's inequality, which drives a list induction proving the power form (sum xs)ⁿ >= nⁿ · prod xs (am_gm_power). The mean form follows by taking nth roots, via strict monotonicity of real_pow.
Theorem 42: Sum of Reciprocals of Triangular Numbers
A proof that ∑(1/T_k) = 2, where T_k = k(k+1)/2 is the k-th triangular number. The key is the telescoping identity:
lemma tri_term_telescopes k =
(k > 0) ==> tri_term k = (_R 2) *. ((_R 1) /. (_R k) -. (_R 1) /. (_R (k + 1)))
[@@by intros @> simplify () @> nonlin ()]The main theorem establishes the closed form S(n) = 2 - 2/(n+1):
theorem sum_of_reciprocals_of_triangular_numbers n =
sum_recip_tri n = sum_recip_tri_closed n
[@@by induction () @>| [auto; intros @> ... @> nonlin ()]]Theorem 44: Binomial Theorem
The binomial theorem (x+y)ⁿ = Σ C(n,k) xⁿ⁻ᵏ yᵏ proved by induction using Pascal's identity. The key combiner lemma distributes x and y over partial sums:
lemma binom_sum_step n k x y =
k >= 0 && n >= 0
==> x * binom_sum n k x y + y * binom_sum n (k - 1) x y
= binom_sum (n + 1) k x yThis itself requires induction, with interior cases using Pascal's identity and boundary cases using choose_out_of_range.
theorem binomial_theorem n x y =
n >= 0 && x >= 0 && y >= 0
==> pow (x + y) n = binom_eval n x yTheorem 51: Wilson's Theorem
If p is prime, then (p-1)! ≡ -1 (mod p):
theorem wilson p =
is_prime p ==> Combinations.fact (p - 1) mod p = p - 1Modular inverses come from the Bézout coefficients of Theorem 60. Only 1 and p-1 are their own inverses mod p, so the numbers 2, ..., p-2 pair off with their inverses and their product is 1:
lemma interior_product_is_one p =
is_prime p ==> pref_prod_mod p (p - 2) = 1Multiplying by p - 1 gives the result. Theorems 10 and 20 both build on this file.
Theorem 52: Number of Subsets
A finite set with n elements has 2ⁿ subsets:
let rec powerset (xs:'a list) : 'a list list =
match xs with
| [] -> [[]]
| x::xt -> let ps = powerset xt in ps @ (prepend x ps)
theorem powerset_len xs =
List.length (powerset xs) = pow 2 (List.length xs)
[@@by auto]Proved fully automatically: ImandraX discovers the induction and discharges all goals.
Theorem 54: Königsberg Bridges
Euler's theorem that no Eulerian path exists through the seven bridges of Königsberg. Two independent proofs are given.
Proof 1: exhaustive symbolic enumeration:
theorem konigsberg_concrete start b1 b2 b3 b4 b5 b6 b7 =
not (eulerian start b1 b2 b3 b4 b5 b6 b7)
[@@by unroll 50]Proof 2: a general parity argument via permutation-preserving occurrence counts:
theorem konigsberg r p =
List.mem r regions && valid_path p r
==> not (permutation p bridges)
[@@by intros
@> ... [%use parity_occurrences p r s]
@> [%use permp_occurrences p bridges s]
@> [%use parity_bridges s]
@> esimp @> simplify ()]Theorem 57: Cube Dissection Impossibility
A proof that a cube cannot be dissected into finitely many smaller cubes all of different sizes. The proof constructs an infinite descending sequence of cubes, each smaller than the last, using the "smallest cube touching the top face" operation, then applies the pigeonhole principle:
theorem no_dissection_exists cs t h0 =
is_dissection cs && has_coverage cs t && List.mem h0 cs
&& cube_max Ax_Z h0 <. 1.0
==> false
[@@by [%use sequence_length cs h0 (List.length cs + 1)]
@> [%use sequence_all_in_cs cs t h0 (List.length cs + 1)]
@> [%use sequence_distinct_widths cs t h0 (List.length cs + 1)]
@> [%use pigeonhole cs (build_sequence cs h0 (List.length cs + 1))]
@> auto]This is one of the most complex proofs in the collection, featuring 4 geometric axioms, a custom pigeonhole principle (itself proved from scratch), and extensive lemma chains about descending width sequences.
Theorem 58: Formula for Number of Combinations
The closed-form formula C(n,k) = n! / (k! · (n-k)!) proved in a division-free form:
theorem choose_times_factorials n k =
(0 <= k && k <= n)
==> Binomial.choose n k * fact k * fact (n - k) = fact nThen, using exact division:
theorem choose_closed_form n k =
0 <= k && k <= n
==> Binomial.choose n k = fact n / (fact k * fact (n - k))The proof uses Pascal's identity, factorial shift lemmas, and exact-division cancellation.
Theorems 60 & 69: Bézout's Theorem & GCD Algorithm
The Euclidean GCD algorithm and Bézout's theorem proved together. GCD is defined by subtraction:
let rec gcd (a:int) (b:int) : int =
if a < 0 || b < 0 then 0
else if a = 0 then b
else if b = 0 then a
else if a >= b then gcd (a - b) b
else gcd a (b - a)Bézout coefficients are computed by a parallel recursion:
let rec bezout_sub (a:int) (b:int) : int * int =
...
else if a >= b then
let (u',v') = bezout_sub (a - b) b in (u', v' - u')
else
let (u',v') = bezout_sub a (b - a) in (u' - v', v')
theorem bezout a b =
let (u,v) = bezout_sub a b in u*a + v*b = gcd a b
[@@by auto]Key derived properties include gcd_dvd_both_pos, gcd_absorbs_common_divisor, and the coprimality-of-squares lemma gcd_square_square_from_coprime.
Theorem 65: Isosceles Triangle Theorem
If two sides of a triangle are equal, the opposite angles are equal. Angles are represented as polynomial relations (cos² equality):
theorem isosceles_triangle (a:point) (b:point) (c:point) =
neqp a b && neqp a c && dist2 a c = dist2 b c
==> angle_eq (sub c a) (sub b a) (sub a b) (sub c b)
[@@by [%simp_only neqp,sub,angle_eq,norm2,dot,dist2]
@>>| ... @> nonlin ()]The proof normalizes all geometric definitions to polynomial form and finishes with nonlin().
Theorem 66: Sum of a Geometric Series
For a geometric sequence with ratio r ≠ 1, the sum is (first - r · last) / (1 - r):
theorem sum_geometric_series seq ratio =
geometric_sequence seq ratio && ratio <> 1.0 ==>
sum seq = Real.((first seq - ratio * last seq) / (1.0 - ratio))The division-free form is proved by induction following the recursion of the geometric_sequence recognizer:
theorem sum_geometric_series_multiplicative seq ratio =
geometric_sequence seq ratio ==>
Real.(sum seq * (1.0 - ratio)) = Real.(first seq - ratio * last seq)Dividing by 1 - r gives the main theorem.
Theorem 68: Sum of an Arithmetic Series
The sum of n + 1 terms a, a + d, ..., a + nd is (n + 1)(2a + nd) / 2:
theorem sum_arithmetic_series a d n =
n >= 0 ==>
arithmetic_sum a d n
= Real.((of_int n + 1.0) * (2.0 * a + (of_int n * d)) / 2.0)As with the geometric series, the division-free form is proved first, by induction on arithmetic_sum. The step case is a polynomial identity:
lemma arith_algebra_key (a : real) (d : real) (n : real) =
Real.(n * (2.0 * a + (n - 1.0) * d) + 2.0 * a + 2.0 * n * d) =
Real.((n + 1.0) * (2.0 * a + n * d))
[@@by nonlin ()]The file also derives Gauss's formula and the sum of the first n odd numbers as corollaries.
Theorem 73: Ascending or Descending Sequences
The Erdős–Szekeres theorem: a list of more than r · s distinct reals has an ascending subsequence longer than r or a descending subsequence longer than s:
theorem erdos_szekeres l r s =
dlistp l
&& List.length l > r * s
&& r >= 0 && s >= 0
==> List.length (longest_ascending_subseq l) > r
|| List.length (longest_descending_subseq l) > sEach element x gets a label: the lengths of the longest ascending and longest descending subsequences ending at x. For any two elements, the later one can extend one of those subsequences, so no two elements share a label. The labels then fit in a grid of size A · D, where A and D are the two longest lengths, and a pigeonhole lemma proved by induction finishes the argument:
lemma pigeonhole_h xs ys =
dlistp_pair xs && all_in xs ys
&& ph_ind xs ys = ph_ind xs ys
==> List.length xs <= List.length ysTheorem 74: Principle of Mathematical Induction
A meta-theorem: given axioms for base and inductive step, prove prop n for all n ≥ 0. The proof uses a minimal-counterexample argument:
axiom base prop = prop 0
axiom inductive prop n = n >= 0 && prop n ==> prop (n+1)
theorem induction prop n =
n >= 0 ==> prop n
[@@by intros
@> ... [%use counterexample_outcome prop 0 n]
@> [%cases c = -1, c >= 1]
@>| [... [%use counterexample_neg1_means_k_holds prop 0 n] @> auto;
... [%use inductive prop (c-1)] @> simplify ();
arith]]Theorem 77: Sum of Kth Powers
Faulhaber's formula expresses 1ᵐ + 2ᵐ + ... + nᵐ with Bernoulli polynomials B_j:
theorem faulhaber n m =
n >= 0 && m >= 0
==> Real.of_int (m + 1) *. sum_pow_r n m
= bernpoly (m + 1) (Real.of_int (n + 1))
-. bernpoly (m + 1) 1.0
[@@by
induction ()
@>| [auto;
intros
@> [%use bernpoly_telescope m (Real.of_int n)]
@> auto]]The main step is the telescoping identity B_{m+1}(x+1) - B_{m+1}(x) = (m+1)xᵐ, after which induction on n closes the theorem:
lemma bernpoly_telescope m x =
m >= 0
==>
bernpoly (m + 1) (x +. 1.0) -. bernpoly (m + 1) x
= Real.of_int (m + 1) *. real_pow x mProving the identity means expanding the difference into a double sum over binomial coefficients and swapping the order of summation. The file proves a real-valued binomial theorem and the Bernoulli recurrence along the way.
Theorem 78: Cauchy-Schwarz Inequality
Proved in two forms over arbitrary-dimension real vectors:
Form 1: ⟨u,v⟩² ≤ ⟨u,u⟩⟨v,v⟩
theorem cauchy_schwarz_1 u v =
same_length u v ==>
Real.(dot u v * dot u v) <=. Real.(dot u u * dot v v)Form 2: |⟨u,v⟩| ≤ ‖u‖ ‖v‖ (using a relational sqrt)
theorem cauchy_schwarz_2 u v eu ev =
same_length u v && is_sqrt eu (norm_sq u) && is_sqrt ev (norm_sq v)
==> abs_real (dot u v) <=. Real.(eu * ev)The proof proceeds via the optimal projection formula: ‖u - tv‖² ≥ 0 with t = ⟨u,v⟩/⟨v,v⟩ gives the inequality directly. Key lemmas include sqrt monotonicity, norm-squared non-negativity, and the algebraic simplification of the projection residual.
The equality condition (linear dependence) is also established:
lemma linear_dependence_implies_equality a v =
Real.(dot (scalar_mult a v) v * dot (scalar_mult a v) v)
= Real.(norm_sq (scalar_mult a v) * norm_sq v)Theorem 80: Fundamental Theorem of Arithmetic
Every integer ≥ 2 has a unique prime factorization. The proof has two parts.
Existence: by strong induction, factoring via the smallest divisor:
let rec prime_factors (n:int) : int list =
if n < 2 then []
else let d = small_divisor_from 2 n in
if d = n then [n] else (prime_factors d) @ (prime_factors (n / d))
theorem prime_factorization_exists n =
n >= 2 ==> all_prime (prime_factors n) && prod_list (prime_factors n) = nUniqueness: using Euclid's lemma (if p | ab then p | a or p | b, proved via Bézout) and multiset permutation:
theorem prime_factorization_unique xs ys =
all_prime xs && all_prime ys && prod_list xs = prod_list ys
==> permutation xs ysThis is one of the largest proofs in the collection, building on Bézout's theorem, the GCD development, and a bespoke prime_mem_if_divides_prod lemma chain.
Theorem 85: Divisibility by 3 Rule
An integer is divisible by 3 if and only if the sum of its digits is divisible by 3:
theorem divisibility_by_3_rule n =
(n >= 0) ==> ((n mod 3 = 0) = (sum_digits n mod 3 = 0))
[@@by [%use sum_digits_preserves_mod3 n] @> auto]The core congruence sum_digits_preserves_mod3 is proved by induction, using the distribution of mod over addition and the fact that 10 ≡ 1 (mod 3).
Theorem 88: Derangements Formula
The number of permutations of {0, ..., n-1} with no fixed points is D(n) = n! Σ (-1)ᵏ/k!, computed here by the recurrence D(n) = (n-1)(D(n-1) + D(n-2)) (subfact):
theorem derangements_formula n =
n >= 0 ==> List.length (derangements n) = subfact n
[@@by
intros
@> [%use forward_bound n]
@> [%use backward_bound n]
@> [%use derangements_rec_dlist n]
@> [%use derangements_in_rec n]
@> auto]derangements n filters all permutations. The proof builds a second generator, derangements_rec, that follows the recurrence directly, and shows that it has subfact n elements, contains only derangements, has no duplicates, and contains every derangement. The two lists therefore have the same length.
Theorem 89: Factor and Remainder Theorem
Polynomials are lists of real coefficients, evaluated by Horner's method, and synth_div computes the quotient by synthetic division. The remainder theorem says p(x) = (x - a) · q(x) + p(a):
theorem remainder_theorem p a x =
poly_eval p x = Real.((x - a) * poly_eval (synth_div p a) x + poly_eval p a)
theorem factor_remainder p a x =
poly_eval p a = 0.0
= (poly_eval p x = Real.((x - a) * poly_eval (synth_div p a) x))The remainder theorem is proved by induction on the coefficient list. The step case is a polynomial identity proved by nonlin, and the factor theorem follows from the remainder theorem with auto.
Theorem 91: Triangle Inequality
‖u + v‖ ≤ ‖u‖ + ‖v‖ over ℝ², building on Cauchy-Schwarz:
theorem triangle_inequality (x:R2.vec) (y:R2.vec) (nx:real) (ny:real) (nxy:real) =
nx >= 0.0 && ny >= 0.0 && nxy >= 0.0
&& nx * nx = norm x && ny * ny = norm y && nxy * nxy = norm (add x y)
==> nxy <= nx + nyThe proof chains together Cauchy-Schwarz, sum-of-squares expansion, and an "unsquaring" lemma that extracts the inequality from its squared form.
Theorem 93: The Birthday Problem
23 is the smallest group size for which a shared birthday is more likely than not:
theorem birthday_problem k =
(0 <= k && k <= 22 ==> collision_prob k <=. 0.5)
&& (k = 23 ==> collision_prob k >. 0.5)The proof works with exact integers first: 2 · 365!/(365-23)! < 365²³ and the reverse inequality for 22 are checked by evaluation. A lemma proved by nonlin moves these into real-valued probabilities:
lemma int_ineq_to_real (a : int) (b : int) =
b > 0 && 2 * a < b
==> Real.(of_int a / of_int b) <. 0.5
[@@by nonlin ()]The cases k = 0, ..., 22 are covered with a bounded-range predicate.
Theorem 96: Principle of Inclusion/Exclusion
The size of a union of finite sets is the alternating sum of the sizes of all intersections:
theorem inclusion_exclusion_principle u l =
Sets.(dlistp u && dlistp l && l <> [] && sublistp l (subsets u)
==> inc_exc l = List.length (union_list l))The proof counts per element. An element that lies in j of the sets appears in C(j, k) of the k-fold intersections, and the alternating sum of these binomial coefficients is 1 when j >= 1. So each element of the union contributes exactly 1, and every other element contributes 0:
lemma sum_contribs_count u l =
Sets.(dlistp l && l <> []
==> sum_contribs u l 1 = num_members u (union_list l))Summary
33 Theorems Formalized
From Freek's Top 100 list, spanning number theory, analysis, algebra, geometry, combinatorics, and probability.
Alongside Lean/Coq/Isabelle
ImandraX joins the leading proof assistants in formalizing classical mathematics.
Automation + Guidance
Many proofs use just auto or nonlin(). The hardest require custom
induction schemes and lemma chains.
Growing Collection
New results are continually being added to the formalization effort.