Now Reading
Formalizing the proof of PFR in Lean4 utilizing Blueprint: a brief tour

Formalizing the proof of PFR in Lean4 utilizing Blueprint: a brief tour

2023-12-05 03:19:48

Because the launch of my preprint with Tim, Ben, and Freddie proving the Polynomial Freiman-Ruzsa (PFR) conjecture over {mathbb F}_2, I (along with Yael Dillies and Bhavik Mehta) have began a collaborative project to formalize this argument within the proof assistant language Lean4. It has been lower than every week for the reason that challenge was launched, however it’s continuing fairly properly, with a big fraction of the paper already both absolutely or partially formalized. The challenge has been significantly assisted by the Blueprint tool of Patrick Massot, which permits one to write down a human-readable “blueprint” of the proof that’s linked to the Lean formalization; related blueprints have been used for other projects, corresponding to Scholze’s liquid tensor experiment. For the PFR challenge, the blueprint may be discovered here. One characteristic of the blueprint that I discover notably interesting is the dependency graph that’s robotically generated from the blueprint, and might present a tough snapshot of how far alongside the formalization has superior. For PFR, the most recent state of the dependency graph may be discovered here. On the present time of writing, the graph appears like this:

The colour coding of the assorted bubbles (for lemmas) and rectangles (for definitions) is defined within the legend to the dependency graph, however roughly talking the inexperienced bubbles/rectangles characterize lemmas or definitions which have been absolutely formalized, and the blue ones characterize lemmas or definitions that are able to be formalized (their statements, however not proofs, have already been formalized, in addition to these of all prerequisite lemmas and proofs). The purpose is to get all of the bubbles main as much as the “pfr” bubble on the backside coloured in inexperienced.

On this submit I wish to give a fast “tour” of the challenge, to present a way of the way it operates. If one clicks on the “pfr” bubble on the backside of the dependency graph, we get the next:

Right here, Blueprint is displaying a human-readable type of the PFR assertion. That is coming from the corresponding portion of the blueprint, which additionally comes with a human-readable proof of this assertion that depends on different statements within the challenge:

(I’ve cropped out the second half of the proof right here, as it’s not related to the dialogue.)

Observe that the “pfr” bubble is white, however has a inexperienced border. Which means that the assertion of PFR has been formalized in Lean, however not the proof; and the proof itself isn’t able to be formalized, as a result of a number of the conditions (specifically, “entropy-pfr” (Theorem 6.16)) don’t even have their statements formalized but. If we click on on the “Lean” hyperlink under the outline of PFR within the dependency graph, we’re result in the (auto-generated) Lean documentation for this assertion:

That is what a typical theorem in Lean appears like (after a process often known as “fairly printing”). There are a variety of hypotheses acknowledged earlier than the colon, as an example that G is a finite elementary abelian group of order 2 (that is how we’ve got chosen to formalize the finite area vector areas {bf F}_2^n), that A is a non-empty subset of G (the speculation that A is non-empty was not acknowledged within the LaTeX model of the conjecture, however we realized it was vital within the formalization, and can replace the LaTeX blueprint shortly to mirror this) with the cardinality of A+A lower than K occasions the cardinality of A, and the assertion after the colon is the conclusion: that A may be contained within the sum c+H of a subgroup H of G and a set c of cardinality at most 2K^{12}.

The astute reader could discover that the above theorem appears to be lacking one or two particulars, as an example it doesn’t explicitly assert that H is a subgroup. It’s because the “fairly printing” suppresses a number of the info within the precise assertion of the theory, which may be seen by clicking on the “Source” hyperlink:

Right here we see that H is required to have the “sort” of an additive subgroup of G. (Lean’s language revolves very strongly round types, however for this tour we won’t go into element into what a kind is precisely.) The distinguished “sorry” on the backside of this theorem asserts {that a} proof isn’t but supplied for this theorem, however the intention after all is to exchange this “sorry” with an precise proof ultimately.

Filling on this “sorry” is just too arduous to do proper now, so let’s search for a less complicated process to perform as a substitute. Right here is an easy intermediate lemma “ruzsa-nonneg” that reveals up within the proof:

The expression d[X; Y] refers to one thing referred to as the entropic Ruzsa distance between X and Y, which is one thing that’s outlined elsewhere in the project, however for the present dialogue it’s not necessary to know its exact definition, apart from that it’s a actual quantity. The bubble is blue with a inexperienced border, which signifies that the assertion has been formalized, and the proof is able to be formalized additionally. The blueprint dependency graph signifies that this lemma may be deduced from only one previous lemma, referred to as “ruzsa-diff“:

ruzsa-diff” can be blue and bordered in inexperienced, so it has the identical present standing as “ruzsa-nonneg“: the assertion is formalized, and the proof is able to be formalized additionally, however the proof has not been written in Lean but. The amount H[X], by the best way, refers back to the Shannon entropy of X, outlined elsewhere in the project, however for this dialogue we don’t must know its definition, apart from to know that it’s a actual quantity.

Taking a look at Lemma 3.11 and Lemma 3.13 it’s clear how the previous will suggest the latter: the amount |H[X] - H[Y]| is clearly non-negative! (There’s a issue of 2 current in Lemma 3.11, however it may be simply canceled out.) So it needs to be a straightforward process to fill within the proof of Lemma 3.13 assuming Lemma 3.11, even when we nonetheless don’t know how one can show Lemma 3.11 but. Let’s first take a look at the Lean code for every lemma. Lemma 3.11 is formalized as follows:

Once more we’ve got a “sorry” to point that this lemma doesn’t presently have a proof. The Lean notation (in addition to the title of the lemma) differs slightly from the LaTeX model for technical causes that we are going to not go into right here. (Additionally, the variables X, mu, Y, mu' are launched at an earlier stage within the Lean file; once more, we’ll ignore this level for the following dialogue.) In the meantime, Lemma 3.13 is currently formalized as

OK, I’m now going to attempt to fill within the latter “sorry”. In my native copy of the PFR github repository, I open up the relevant Lean file in my editor (Visual Studio Code, with the lean4 extension) and navigate to the “sorry” of “rdist_nonneg”. The accompanying “Lean infoview” then reveals the present state of the Lean proof:

Right here we see plenty of ambient hypotheses (e.g., that G is an additive commutative group, that X is a map from Omega to G, and so forth; many of those hypotheses usually are not truly related for this specific lemma), and on the backside we see the purpose we want to show.

OK, so now I’ll attempt to show the declare. That is achieved by making use of a sequence of “techniques” to remodel the purpose and/or hypotheses. Step one I’ll do is to place within the issue of 2 that’s wanted to use Lemma 3.11. This I’ll do with the “suffices” tactic, writing within the proof

I now have two targets (and two “sorries”): one to point out that 0 leq 2 d[X;Y] implies 0 leq d[X,Y], and the opposite to point out that 0 leq 2 d[X;Y]. (The yellow squiggly underline signifies that this lemma has not been absolutely confirmed but as a result of presence of “sorry”s. The dot “.” is a syntactic marker that’s helpful to separate the 2 targets from one another, however you possibly can ignore it for this tour.) The Lean tactic “suffices” corresponds, roughly talking, to the phrase “It suffices to point out that …” (or extra exactly, “It suffices to point out that … . To see this, … . It stays to confirm the declare …”) in Mathematical English. For my very own training, I wrote a “Lean phrasebook” of additional correspondences between traces of Lean code and sentences or phrases in Mathematical English, which may be discovered here.

Let’s fill within the first “sorry”. The tactic state now appears like this (cropping out some irrelevant hypotheses):

Right here I can use a helpful tactic “linarith“, which solves any purpose that may be derived by linear arithmetic from present hypotheses:

This works, and now the tactic state studies no targets left to show on this department, so we transfer on to the remaining sorry, through which the purpose is now to show 0 leq 2 d[X;Y]:

Right here we’ll attempt to invoke Lemma 3.11. I add the next traces of code:

The Lean tactic “have” roughly corresponds to the Mathematical English phrase “We’ve the assertion…” or “We declare the assertion…”; like “suffices”, it splits a purpose into two subgoals, although within the reversed order to “suffices”.

I once more have two subgoals, one to show the sure |H[X]-H[Y]| leq 2 d[X;Y] (which I’ll name “h”), after which to infer the earlier purpose 0 leq 2 d[X;Y] from h. For the primary, I do know I ought to invoke the lemma “diff_ent_le_rdist” that’s encoding Lemma 3.11. A technique to do that is to strive the tactic “actual?”, which is able to robotically search to see if the purpose can already be deduced instantly from an present lemma. It studies:

So I do this (by clicking on the instructed code, which robotically pastes it into the proper location), and it really works, leaving me with the ultimate “sorry”:

The lean tactic “exact” corresponds, roughly talking, to the Mathematical English phrase “However that is precisely …”.

At this level I ought to point out that I even have the Github Copilot extension to Visible Studio Code put in. That is an AI which acts as a complicated autocomplete that may counsel doable traces of code as one varieties. On this case, it provided a suggestion which was nearly right (the second line is what we want, whereas the primary isn’t vital, and in reality doesn’t even compile in Lean):

See Also

In any occasion, “actual?” labored on this case, so I can ignore the suggestion of Copilot this time (it has been very helpful in different circumstances although). I apply the “actual?” tactic a second time and observe its suggestion to determine the matching sure 0 leq |H[X] - H[Y]|:

(One can discover documention for the “abs_nonneg” methodology here. Copilot, by the best way, was additionally in a position to resolve this step, albeit with a barely completely different syntax; there are additionally a number of different search engines like google accessible to find this methodology as properly, corresponding to Moogle. One of many foremost functions of the Lean naming conventions for lemmas, by the best way, is to facilitate the situation of strategies corresponding to “abs_nonneg”, which is simpler work out how one can seek for than a technique named (say) “Lemma 1.2.1”.) To fill within the remaining “sorry”, I strive “actual?” one final time, to determine how one can mix h and h' to present the specified purpose, and it really works!

Be aware that each one the squiggly underlines have disappeared, indicating that Lean has accepted this as a sound proof. The documentation for “ge_trans” could also be discovered here. The reader could observe that this methodology makes use of the geq relation fairly than the leq relation, however in Lean the assertions X geq Y and Y leq X are “definitionally equal“, permitting techniques corresponding to “actual” to make use of them interchangeably. “actual le_trans h’ h” would even have labored on this occasion.

It’s doable to compactify this proof fairly a bit by reducing out a number of intermediate steps (a process typically often known as “code golf“):

And now the proof is completed! Ultimately, it was actually a “one-line proof”, which is smart given how shut Lemma 3.11 and Lemma 3.13 had been to one another.

The present model of Blueprint doesn’t robotically confirm the proof (although it does compile in Lean), so we’ve got to manually replace the blueprint as properly. The LaTeX for Lemma 3.13 currently looks like this:

I add the “leanok” macro to the proof, to flag that the proof has now been formalized:

I then push every thing again as much as the grasp Github repository. The blueprint will take fairly a while (about half an hour) to rebuild, however ultimately it does, and the dependency graph (which Blueprint has for some motive determined to rearrange a bit) now reveals “ruzsa-nonneg” in inexperienced:

And so the formalization of PFR strikes slightly bit nearer to completion. (After all, this was a very straightforward lemma to formalize, that I selected for example the method; one can think about that almost all different lemmas will take a bit extra work.) Be aware that whereas “ruzsa-nonneg” is now coloured in inexperienced, we don’t but have a full proof of this outcome, as a result of the lemma “ruzsa-diff” that it depends on isn’t inexperienced. Nonetheless, the proof is domestically full at this level; hopefully in some unspecified time in the future sooner or later, the predecessor outcomes may also be domestically confirmed, at which level this outcome might be fully confirmed. Be aware how this blueprint construction permits one to work on completely different elements of the proof asynchronously; it’s not vital to attend for earlier phases of the argument to be absolutely formalized to begin engaged on later phases, though I anticipate a small quantity of interplay between completely different elements as we iron out any bugs or slight inaccuracies within the blueprint. (For example, I’m suspecting that we might have so as to add some measurability hypotheses on the random variables X, Y within the above two lemmas to make them fully true, however that is one thing that ought to emerge organically because the formalization course of continues.)

That concludes the transient tour! In case you are fascinated by studying extra in regards to the challenge, you possibly can observe the Zulip chat stream; it’s also possible to download Lean and work on the PFR project yourself, utilizing an area copy of the Github repository and sending pull requests to the grasp copy when you have managed to fill in a number of of the “sorry”s within the present model (however in the event you plan to work on something extra giant scale than filling in a small lemma, it’s good to announce your intention on the Zulip chat to keep away from duplication of effort) . (One key benefit of working with a challenge based mostly round a proof assistant language corresponding to Lean is that it makes large-scale mathematical collaboration doable with out essentially having a pre-established degree of belief amongst the collaborators; my fellow repository maintainers and I’ve already permitted a number of pull requests from contributors that had not beforehand met, because the code was verified to be right and we might see that it superior the challenge. Conversely, because the above instance ought to hopefully exhibit, it’s doable for a contributor to work on one small nook of the challenge with out essentially needing to grasp all of the arithmetic that goes into the challenge as an entire.)

If one simply needs to experiment with Lean with out going to the trouble of downloading it, you possibly can enjoying strive the “Natural Number Game” for a delicate introduction to the language, or the Lean4 playground for a web-based Lean server. Additional assets to study Lean4 could also be discovered here.

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