Because the launch of my preprint with Tim, Ben, and Freddie proving the Polynomial Freiman-Ruzsa (PFR) conjecture over , I (along with Yael Dilles and Bhavik Mehta) have began a collaborative mission to formalize this argument within the proof assistant language Lean4. It has been lower than every week because the mission was launched, however it’s continuing fairly nicely, with a big fraction of the paper already both totally or partially formalized. The mission has been drastically assisted by the Blueprint device, which permits one to put in writing a human-readable “blueprint” of the proof that’s linked to the Lean formalization; related blueprints have been used for different initiatives, similar to Scholze’s liquid tensor experiment. For the PFR mission, the blueprint could be discovered right here. One characteristic of the blueprint that I discover notably interesting is the dependency graph that’s routinely generated from the blueprint, and might present a tough snapshot of how far alongside the formalization has superior. For PFR, the newest state of the dependency graph could be discovered right here. On the present time of writing, the graph seems to be like this:

The colour coding of the varied bubbles (for lemmas) and rectangles (for definitions) is defined within the legend to the dependency graph, however roughly talking the inexperienced bubbles/rectangles symbolize lemmas or definitions which were totally formalized, and the blue ones symbolize 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 put up I wish to give a fast “tour” of the mission, 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 mission:

Nonetheless, this a part of the proof has not but been formalized in Lean. Observe that the “pfr” bubble is white, however has a inexperienced border. Which means the assertion of PFR has been formalized in Lean, however not the proof; and the proof itself will not be able to be formalized, as a result of a number of the conditions (particularly, “entropy-pfr” (Theorem 6.16)) don’t even have their statements formalized but. If we click on on the “Lean” hyperlink beneath 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 seems to be like (after a process often called “fairly printing”). There are a selection of hypotheses said earlier than the colon, as an example that is a finite elementary abelian group of order (that is how now we have chosen to formalize the finite area vector areas ), that is a non-empty subset of (the speculation that is non-empty was not said within the LaTeX model of the conjecture, however we realized it was vital within the formalization, and can replace the LaTeX blueprint shortly to replicate this) with the cardinality of lower than instances the cardinality of , and the assertion after the colon is the conclusion: that could be contained within the sum of a subgroup of and a set of cardinality at most .

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

Right here we see that is required to have the “sort” of an additive subgroup of . (Lean’s language revolves very strongly round varieties, however for this tour we is not going to go into element into what a sort is strictly.) The distinguished “sorry” on the backside of this theorem asserts {that a} proof will not be but supplied for this theorem, however the intention in fact is to exchange this “sorry” with an precise proof finally.

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

The expression refers to one thing referred to as the entropic Ruzsa distance between and , which is one thing that’s outlined elsewhere within the mission, 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 could 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 , by the best way, refers back to the Shannon entropy of , outlined elsewhere within the mission, however for this dialogue we don’t must know its definition, apart from to know that it’s a actual quantity.

Lemma 3.11 and Lemma 3.13 it’s clear how the previous will indicate the latter: the amount is clearly non-negative! (There’s a issue of current in Lemma 3.11, however it may be simply canceled out.) So it ought to be a simple process to fill within the proof of Lemma 3.13 assuming Lemma 3.11, even when we nonetheless don’t know the way to 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 now we have 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 somewhat from the LaTeX model for technical causes that we are going to not go into right here. (Additionally, the variables 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 presently 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 related lean file in my editor (Visible Studio Code, with the lean4 extension) and navigate to the “sorry” of “rdist_nonneg”. The accompanying “Lean infoview” then exhibits the present state of the Lean proof:

Right here we see numerous ambient hypotheses (e.g., that is an additive commutative group, that is a map from to , and so forth; many of those hypotheses aren’t really 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 completed 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 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 implies , and the opposite to point out that . (The yellow squiggly underline signifies that this lemma has not been totally 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 may 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 schooling, I wrote a “Lean phrasebook” of additional correspondences between traces of Lean code and sentences or phrases in Mathematical English, which could be discovered right here.

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

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

This works, and now the tactic state reviews no targets left to show on this department, so we transfer on to the remaining sorry, wherein the purpose is now to show :

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 now have 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 (which I’ll name “h”), after which to infer the earlier purpose from . For the primary, I do know I ought to invoke the lemma “diff_ent_le_rdist” that’s encoding Lemma 3.11. A method to do that is to strive the tactic “precise?”, which can routinely search to see if the purpose can already be deduced instantly from an current lemma. It reviews:

So I do that (by clicking on the prompt code, which routinely pastes it into the fitting location), and it really works, leaving me with the ultimate “sorry”:

The lean tactic “precise” 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 recommend potential traces of code as one varieties. On this case, it provided a suggestion which was virtually appropriate (the second line is what we want, whereas the primary will not be vital, and actually doesn’t even compile in Lean):

In any occasion, “precise?” 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 “precise?” tactic a second time and observe its suggestion to determine the matching sure :

(One can discover documention for the “abs_nonneg” methodology right here. Copilot, by the best way, was additionally capable of resolve this step, albeit with a barely completely different syntax; there are additionally a number of different search engines like google and yahoo out there to find this methodology as nicely, similar to Moogle. One of many fundamental functions of the Lean naming conventions for lemmas, by the best way, is to facilitate the situation of strategies similar to “abs_nonneg”, which is less complicated determine the way to seek for than a way named (say) “Lemma 1.2.1”.) To fill within the closing “sorry”, I strive “precise?” one final time, to determine the way to mix and to present the specified purpose, and it really works!

(Observe that every 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 right here. The reader might observe that this methodology makes use of the relation somewhat than the relation, however in Lean the assertions and are “definitionally equal“, permitting techniques similar to “precise” to make use of them interchangeably. “precise le_trans h’ h” would even have labored on this occasion.)

It’s potential to compactify this proof fairly a bit by chopping out a number of intermediate steps (a process typically often called “code golf“):

And now the proof is finished! In the long run, it was actually a “one-line proof”, which is sensible given how shut Lemma 3.11 and Lemma 3.13 had been to one another.

The present model of Blueprint doesn’t routinely confirm the proof (although it does compile in Lean), so now we have to manually replace the blueprint as nicely. The LaTeX for Lemma 3.13 presently seems to be 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 finally it does, and the dependency graph (which Blueprint has for some motive determined to rearrange a bit) now exhibits “ruzsa-nonneg” in inexperienced:

And so the formalization of PFR strikes somewhat bit nearer to completion. (In fact, this was a very simple 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.) Observe that whereas “ruzsa-nonneg” is now coloured in inexperienced, we don’t but have a full proof of this end result, as a result of the lemma “ruzsa-diff” that it depends on will not be inexperienced. Nonetheless, the proof is domestically full at this level; hopefully sooner or later sooner or later, the predecessor outcomes may also be domestically confirmed, at which level this end result shall be utterly confirmed. Observe 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 totally formalized to begin engaged on later phases, though I anticipate a small quantity of interplay between completely different parts as we iron out any bugs or slight inaccuracies within the blueprint. (As an example, I’m suspecting that we may have so as to add some measurability hypotheses on the random variables within the above two lemmas to make them utterly true, however that is one thing that ought to emerge organically because the formalization course of continues.)

That concludes the temporary tour! If you’re occupied with studying extra concerning the mission, you may observe the Zulip chat stream; you may also obtain Lean and work on the PFR mission your self, utilizing a neighborhood copy of the Github repository and sending pull requests to the grasp copy you probably have managed to fill in a number of of the “sorry”s within the present model. (One key benefit of working with a mission based mostly round a proof assistant language similar to Lean is that it makes large-scale mathematical collaboration potential with out essentially having a pre-established degree of belief amongst the collaborators; my fellow repository maintainers and I’ve already accepted a number of pull requests from contributors that had not beforehand met, because the code was verified to be appropriate and we might see that it superior the mission. Conversely, because the above instance ought to hopefully reveal, it’s potential for a contributor to work on one small nook of the mission with out essentially needing to know all of the arithmetic that goes into the mission as an entire.)

If one simply desires to experiment with Lean with out going to the hassle of downloading it, you may taking part in strive the “Pure Quantity Recreation” for a mild introduction to the language, or the Lean4 playground for a web-based Lean server. Additional assets to study Lean4 could also be discovered right here.