Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Exact rational certificates and minimum lengths for Egyptian fractions

Definition
EgyptianFractions_Certificate

by Sodelin · Sep 8, 2026 · Mathlib 0df444a (Lean v4.33.1)

egyptian-fractionserdos-295number-theorysodelin-egyptian295

For a finite list DDD of natural denominators, define R(D)=∑d∈D1/dR(D)=\sum_{d\in D}1/dR(D)=∑d∈D​1/d in exact rational arithmetic. For natural numbers L,tL,tL,t, a representation requires distinct positive entries, each at least LLL, with sum 1:

Rep⁡(L,D)  ⟺  D has no duplicates ∧ (∀d∈D, 0<d ∧ L≤d) ∧ R(D)=1.\operatorname{Rep}(L,D)\iff D\text{ has no duplicates}\ \land\ (\forall d\in D,\ 0<d\ \land\ L\leq d)\ \land\ R(D)=1.Rep(L,D)⟺D has no duplicates ∧ (∀d∈D, 0<d ∧ L≤d) ∧ R(D)=1.

An attainable length ttt means some such list has length ttt; a minimum length means attainment together with being no larger than every attainable length.

This interface ties finite certificates directly to ordinary rational addition and division. Minimum existence is not built into the definition and must be proved from an actual representation.

Definition code
import Std
import Init.Grind.Ordered.Module
/-!
# Exact certificates for distinct Egyptian fractions

All sums use Lean's standard exact rational number type `Rat`. A certificate is
a proposition about actual rational addition and division, not an unconnected
Boolean or a floating-point computation. `decide +kernel` checks closed finite
instances by reduction in Lean's kernel; no native evaluation axiom is needed.
-/

namespace EgyptianFractions

/-- The ordinary sum of the unit fractions with the supplied denominators. -/
def reciprocalSum (denominators : List Nat) : Rat :=
  (denominators.map fun (d : Nat) => (1 : Rat) / (↑d : Rat)).sum

/-- Distinct positive denominators, each at least `lower`, summing to one. -/
def IsRepresentation (lower : Nat) (denominators : List Nat) : Prop :=
  denominators.Nodup ∧
  (∀ d ∈ denominators, 0 < d ∧ lower ≤ d) ∧
  reciprocalSum denominators = 1

instance (lower : Nat) (denominators : List Nat) :
    Decidable (IsRepresentation lower denominators) := by
  unfold IsRepresentation
  infer_instance

/-- Existence of a representation containing exactly `terms` fractions. -/
def HasRepresentation (lower terms : Nat) : Prop :=
  ∃ denominators : List Nat,
    denominators.length = terms ∧ IsRepresentation lower denominators

/-- The usual meaning of a minimum representation length, without an
unproved assumption that a minimum exists for every possible lower bound. -/
def IsMinimumLength (lower terms : Nat) : Prop :=
  HasRepresentation lower terms ∧
  ∀ other, HasRepresentation lower other → terms ≤ other







end EgyptianFractions
Source
https://github.com/Sodelin/Egyptian-Fractions-Erdos-295/blob/566f9800910aae6936d93d1a9f5c756070616f31/EgyptianFractions/Certificate.lean#L1-L77

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me