Exact rational certificates and minimum lengths for Egyptian fractions
DefinitionEgyptianFractions_Certificateegyptian-fractionserdos-295number-theorysodelin-egyptian295
For a finite list of natural denominators, define in exact rational arithmetic. For natural numbers , a representation requires distinct positive entries, each at least , with sum 1:
An attainable length means some such list has length ; 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