Now Reading
A barely longer Lean 4 proof tour

A barely longer Lean 4 proof tour

2023-12-06 21:49:56

In my previous post, I walked by way of the duty of formally deducing one lemma from one other in Lean 4. The deduction was intentionally chosen to be quick and solely showcased a small variety of Lean ways. Right here I want to stroll by way of the method I used for a barely longer proof I labored out lately, after seeing the next challenge from Damek Davis: to formalize (in a civilized style) the proof of the next lemma:

Lemma. Let {a_k} and {D_k} be sequences of actual numbers listed by pure numbers k=0,1,dots, with a_k non-increasing and D_k non-negative. Suppose additionally that a_k leq D_k - D_{k+1} for all k geq 0. Then a_k leq frac{D_0}{k+1} for all k.

Right here I attempted to attract upon the teachings I had discovered from the PFR formalization challenge, and to first arrange a human readable proof of the lemma earlier than beginning the Lean formalization – a lower-case “blueprint” fairly than the fancier Blueprint used within the PFR challenge. The primary concept of the proof right here is to make use of the telescoping sequence identification

displaystyle sum_{i=0}^k D_i - D_{i+1} = D_0 - D_{k+1}.

Since D_{k+1} is non-negative, and a_i leq D_i - D_{i+1} by speculation, we now have

displaystyle sum_{i=0}^k a_i leq D_0

however by the monotone speculation on a_i the left-hand aspect is at the very least (k+1) a_k, giving the declare.

That is already a human-readable proof, however so as to formalize it extra simply in Lean, I made a decision to rewrite it as a sequence of inequalities, beginning at a_k and ending at D_0 / (k+1). With a bit little bit of pen and paper effort, I obtained

a_k = (k+1) a_k / (k+1)

(by subject identities)

= (sum_{i=0}^k a_k) / (k+1)

(by the formulation for summing a continuing)

leq (sum_{i=0}^k a_i) / (k+1)

(by the monotone speculation)

leq (sum_{i=0}^k D_i - D_{i+1}) / (k+1)

(by the speculation a_i leq D_i - D_{i+1}

= (D_0 - D_{k+1}) / (k+1)

(by telescoping sequence)

leq D_0 / (k+1)

(by the non-negativity of D_{k+1}).

I made a decision that this was a ok blueprint for me to work with. The following step is to formalize the assertion of the lemma in Lean. For this fast challenge, it was handy to make use of the online Lean playground, fairly than my native IDE, so the screenshots will look a bit totally different from these within the earlier publish. (If you happen to like, you may comply with this tour in that playground, by typing in some model of the code displayed under.) I begin by importing Lean’s math library, and beginning an instance of a press release to state and show:

Now we now have to declare the hypotheses and variables. The primary variables listed here are the sequences a_k and D_k, which in Lean are finest modeled by features a, D from the pure numbers ℕ to the reals ℝ. (One can select to “hardwire” the non-negativity speculation into the D_k by making D take values within the nonnegative reals {bf R}^+ (denoted NNReal in Lean), however this seems to be inconvenient, as a result of the legal guidelines of algebra and summation that we’ll want are clunkier on the non-negative reals (which aren’t even a bunch) than on the reals (that are a subject). So we add within the variables:

Now we add within the hypotheses, which in Lean conference are normally given names beginning with h. That is pretty simple; the one factor is that the property of being monotone reducing already has a reputation in Lean’s Mathlib, particularly Antitone, and it’s usually a good suggestion to make use of the Mathlib supplied terminology (as a result of that library comprises a whole lot of helpful lemmas about such phrases).

One factor to notice right here is that Lean is kind of good at filling in implied ranges of variables. As a result of a and D have the pure numbers ℕ as their area, the dummy variable ok in these hypotheses is routinely being quantified over ℕ. We may have made this quantification specific if we so selected, for example utilizing ∀ ok : ℕ, 0 ≤ D ok as an alternative of ∀ ok, 0 ≤ D ok, however it’s not mandatory to take action. Additionally word that Lean doesn’t require parentheses when making use of features: we write D ok right here fairly than D(ok) (which in actual fact doesn’t compile in Lean until one places an area between the D and the parentheses). That is barely totally different from normal mathematical notation, however will not be too troublesome to get used to.

This seems like the top of the hypotheses, so we may now add a colon to maneuver to the conclusion, after which add that conclusion:

It is a completely effective Lean assertion. Nevertheless it seems that when proving a universally quantified assertion similar to ∀ ok, a ok ≤ D 0 / (ok + 1), step one is nearly at all times to open up the quantifier to introduce the variable ok (utilizing the Lean command intro ok). Due to this, it’s barely extra environment friendly to cover the common quantifier by inserting the variable ok within the hypotheses, fairly than within the quantifier (during which case we now have to now specify that it’s a pure quantity, as Lean can now not deduce this from context):

At this level Lean is complaining of an surprising finish of enter: the instance has been acknowledged, however not proved. We are going to quickly mollify Lean by including a sorry because the purported proof:

Now Lean is content material, aside from giving a warning (as indicated by the yellow squiggle beneath the instance) that the proof comprises a sorry.

It’s now time to comply with the blueprint. The Lean tactic for proving an inequality through chains of different inequalities is named calc. We use the blueprint to fill within the calc that we wish, leaving the justifications of every step as “sorry”s for now:

Right here, we “open“ed the Finset namespace so as to simply entry Finset‘s range operate, with vary ok principally being the finite set of pure numbers {0,dots,k-1}, and in addition “open“ed the BigOperators namespace to entry the acquainted ∑ notation for (finite) summation, so as to make the steps within the Lean code resemble the blueprint as a lot as attainable. One may keep away from opening these namespaces, however then expressions similar to ∑ i in vary (ok+1), a i would as an alternative should be written as one thing like Finset.sum (Finset.vary (ok+1)) (enjoyable i ↦ a i), which seems rather a lot much less like like normal mathematical writing. The proof construction right here might remind some readers of the “two column proofs” which are considerably widespread in American highschool geometry courses.

Now we now have six sorries to fill. Navigating to the primary sorry, Lean tells us the ambient hypotheses, and the purpose that we have to show to fill that sorry:

The ⊢ image right here is Lean’s marker for the purpose. The uparrows ↑ are coercion symbols, indicating that the pure quantity ok must be transformed to an actual quantity so as to work together through arithmetic operations with different actual numbers similar to a ok, however we will ignore these coercions for this tour (for this proof, it seems Lean will principally handle them routinely with out want for any specific intervention by a human).

The purpose here’s a self-evident algebraic identification; it entails division, so one has to verify that the denominator is non-zero, however that is self-evident. In Lean, a handy approach to set up algebraic identities is to make use of the tactic field_simp to clear denominators, after which ring to confirm any identification that’s legitimate for commutative rings. This works, and clears the primary sorry:

field_simp, by the best way, is wise sufficient to infer by itself that the denominator ok+1 right here is manifestly non-zero (and actually constructive); no human intervention is required to level this out. Equally for different “clearing denominator” steps that we’ll encounter within the different components of the proof.

Now we navigate to the subsequent `sorry`. Lean tells us the hypotheses and targets:

We are able to scale back the purpose by canceling out the frequent denominator ↑ok+1. Right here we will use the helpful Lean tactic congr, which tries to match two sides of an equality purpose as a lot as attainable, and go away any remaining discrepancies between the 2 sides as additional targets to be confirmed. Making use of congr, the purpose reduces to

Right here one may think that that is one thing that one can show by induction. However this specific form of identification – summing a continuing over a finite set – is already lined by Mathlib. Certainly, looking for Finset, sum, and const quickly leads us to the Finset.sum_const lemma right here. However there’s an much more handy path to take right here, which is to use the highly effective tactic simp, which tries to simplify the purpose as a lot as attainable utilizing all of the “simp lemmas” Mathlib has to supply (of which Finset.sum_const is an instance, however there are millions of others). Because it seems, simp utterly kills off this identification, with none additional human intervention:

See Also

Now we transfer on to the subsequent sorry, and take a look at our purpose:

congr doesn’t work right here as a result of we now have an inequality as an alternative of an equality, however there’s a highly effective relative gcongr of congr that’s completely fitted to inequalities. It will probably additionally open up sums, merchandise, and integrals, decreasing world inequalities between such portions into pointwise inequalities. If we invoke gcongr with i hello (the place we inform gcongr to make use of i for the variable opened up, and hello for the constraint this variable will fulfill), we arrive at a tremendously simplified purpose (and a brand new ambient variable and speculation):

Now we have to use the monotonicity speculation on a, which we now have named ha right here. Wanting on the documentation for Antitone, one finds a lemma that appears relevant right here:

One can apply this lemma on this case by writing apply Antitone.imp ha, however as a result of ha is already of kind Antitone, we will abbreviate this to apply ha.imp. (Truly, as indicated within the documentation, as a result of manner Antitone is outlined, we will even simply use apply ha right here.) This reduces the purpose properly:

The purpose is now very near the speculation hello. One may now lookup the documentation for Finset.vary to see easy methods to unpack hello, however as earlier than simp can do that for us. Invoking simp at hello, we acquire

Now the purpose and speculation are very shut certainly. Right here we will simply shut the purpose utilizing the linarith tactic used within the previous tour:

The following sorry could be resolved by related strategies, utilizing the speculation hD utilized on the variable i:

Now for the penultimate sorry. As in a earlier step, we will use congr to take away the denominator, leaving us on this state:

It is a telescoping sequence identification. One may attempt to show it by induction, or one may attempt to see if this identification is already in Mathlib. Looking for Finset, sum, and sub will locate the right tool (because the fifth hit), however a less complicated approach to proceed right here is to make use of the precise? tactic we noticed within the previous tour:

A short verify of the documentation for sum_range_sub' confirms that that is what we wish. Truly we will simply use apply sum_range_sub' right here, because the apply tactic is wise sufficient to fill within the lacking arguments:

One final sorry to go. As earlier than, we use gcongr to cancel denominators, leaving us with

This seems simple, as a result of the speculation hpos will inform us that D (ok+1) is nonnegative; particularly, the occasion hpos (ok+1) of that speculation will state precisely this. The linarith tactic will then resolve this purpose as soon as it’s informed about this specific occasion:

We now have an entire proof – no extra yellow squiggly line within the instance. There are two warnings although – there are two variables i and hello launched within the proof that Lean’s “linter” has seen usually are not truly used within the proof. So we will rename them with underscores to inform Lean that we’re okay with them not getting used:

It is a completely effective proof, however upon noticing that lots of the steps are related to one another, one can do a little bit of “code golf” as within the previous tour to compactify the proof a bit:

With sufficient familiarity with the Lean language, this proof truly tracks fairly intently with (an optimized model of) the human blueprint.

This concludes the tour of a lengthier Lean proving train. I’m discovering the pre-planning step of the proof (utilizing a casual “blueprint” to interrupt the proof down into extraordinarily granular items) to make the formalization course of considerably simpler than prior to now (once I typically adopted a sequential strategy of writing one line of code at a time with out first sketching out a skeleton of the argument). (The proof right here took solely about quarter-hour to create initially, though for this weblog publish I needed to recreate it with screenshots and supporting hyperlinks, which took considerably extra time.) I consider {that a} real looking near-term purpose for AI is to have the ability to fill in routinely a major fraction of the types of atomic “sorry“s of the scale one noticed on this proof, permitting one to transform a blueprint to a proper Lean proof much more quickly.

One last comment: on this tour I stuffed within the “sorry“s within the order during which they appeared, however there’s truly no requirement that one does this, and as soon as one has used a blueprint to atomize a proof into self-contained smaller items, one can fill them in in any order. Importantly for a bunch challenge, these micro-tasks could be parallelized, with totally different contributors claiming whichever “sorry” they really feel they’re certified to resolve, and dealing independently of one another. (And, as a result of Lean can routinely confirm if their proof is appropriate, there is no such thing as a have to have a pre-existing bond of belief with these contributors so as to settle for their contributions.) Moreover, as a result of the specification of a “sorry” somebody could make a significant contribution to the proof by engaged on a particularly localized element of it with no need the mathematical experience to know the worldwide argument. This isn’t notably necessary on this easy case, the place the complete lemma will not be too laborious to know to a skilled mathematician, however can develop into fairly related for advanced formalization tasks.

Source Link

What's Your Reaction?
In Love
Not Sure
View Comments (0)

Leave a Reply

Your email address will not be published.

2022 Blinking Robots.
WordPress by Doejo

Scroll To Top