Skip to content

feat: define updateFinset which updates a finite number components of a vector#7341

Merged
sgouezel merged 34 commits intomasterfrom
marginal_updateSet
Nov 7, 2023
Merged

feat: define updateFinset which updates a finite number components of a vector#7341
sgouezel merged 34 commits intomasterfrom
marginal_updateSet

Conversation

@fpvandoorn
Copy link
Copy Markdown
Member

@fpvandoorn fpvandoorn commented Sep 23, 2023

  • from the Sobolev project (formerly: marginal project)

@fpvandoorn fpvandoorn added awaiting-review awaiting-CI This PR does not pass CI yet. This label is automatically removed once it does. labels Sep 23, 2023
@ghost ghost added the blocked-by-other-PR This PR depends on another PR (this label is automatically managed by a bot) label Sep 23, 2023
We should generalize `updateFinset` to `SetLike` instead of restricting to `Finset`.
However, at the moment `Finset` is not `SetLike`, so we cannot do this yet.
-/
def updateFinset (x : ∀ i, π i) (s : Finset ι) [DecidablePred (· ∈ s)]
Copy link
Copy Markdown
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I assume there's a reason you didn't just use [DecidableEq _] here? If so, can you add it to the docstring?

Copy link
Copy Markdown
Member Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

DecidablePred generalizes better to other SetLike things. But I was inconsistently using DecidableEq in the rest of the file, so I just use that everywhere.

Copy link
Copy Markdown
Member

@eric-wieser eric-wieser left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I'm out of time for now

Comment on lines +18 to +24
/-- `updateFinset x s y` is the vector `x` with the coordinates in `s` changed to the values of `y`.

We should generalize `updateFinset` to `SetLike` instead of restricting to `Finset`.
However, at the moment `Finset` is not `SetLike`, so we cannot do this yet.
-/
def updateFinset (x : ∀ i, π i) (s : Finset ι) (y : ∀ i : ↥s, π i) (i : ι) : π i :=
if hi : i ∈ s then y ⟨i, hi⟩ else x i
Copy link
Copy Markdown
Member

@eric-wieser eric-wieser Sep 25, 2023

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

It's not clear to me what the benefit of defining this on Finset is:

Suggested change
/-- `updateFinset x s y` is the vector `x` with the coordinates in `s` changed to the values of `y`.
We should generalize `updateFinset` to `SetLike` instead of restricting to `Finset`.
However, at the moment `Finset` is not `SetLike`, so we cannot do this yet.
-/
def updateFinset (x : ∀ i, π i) (s : Finset ι) (y : ∀ i : ↥s, π i) (i : ι) : π i :=
if hi : i ∈ s then y ⟨i, hi⟩ else x i
/-- `updateSet x s y` is the vector `x` with the coordinates in `s` changed to the values of `y`.
This is `Set.piecewise` where the left argument `x` is dependently-typed
-/
def updateSet (x : ∀ i, π i) (s : Set ι) [DecidablePred (· ∈ s)] (y : ∀ i : ↥s, π i) (i : ι) : π i :=
if hi : i ∈ s then y ⟨i, hi⟩ else x i

Copy link
Copy Markdown
Member Author

@fpvandoorn fpvandoorn Sep 25, 2023

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I definitely want to apply this to Finset. I need to integrate over a Pi-type over this Finset at some point.

Your suggestion means that I need to coerce the Finset to Set. It also means that all lemmas I want are inconveniently stated in terms of Set-operations instead of Finset-operations. So I need to add a bunch of rewrites commuting coerions with operations. This makes it less convenient to work with.

The proper way to do this is to define this for all SetLike objects, but this is impossible at the moment, as the docstring describes.

Copy link
Copy Markdown
Member

@eric-wieser eric-wieser Sep 25, 2023

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

So I need to add a bunch of rewrites commuting coercions with operations.

Shouldn't norm_cast handle this?

The proper way to do this is to define this for all SetLike objects

I'd argue this is much worse, because now you need separate lemmas about updateSet _ (s ∩ t) for Set and Finset, and another seven or so for updateSet _ (s ⊓ t) for Submonoid, Submodule, .... Then you have to repeat this for bot and iInf and sInf.

If you do it for Set you only need to write these once, because simp turns everything into the set operations for you.

Copy link
Copy Markdown
Member Author

@fpvandoorn fpvandoorn Sep 26, 2023

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I gave this an honest try to use updateSet in our work. It is in d0aa7ef but it a lot less nice.

In the theorem marginal_union I do the following calculation (s and t are Finsets):

(∫⋯∫_s ∪ t, f ∂μ) x = 
∫⁻ (y : (i : ↥(s ∪ t)) → π i), f (updateFinset x (s ∪ t) y) ∂.pi fun i' : ↥(s ∪ t) ↦ μ i'

This is true by definition when using updateFinset.

When using updateSet, I have to be very careful to use Finset-unions. If I use Set-unions, then there are multiple places where the expression becomes type-incorrect (or it becomes nontrivial to prove that it is equal to the Finset-union case).

The rest of the calculation mostly goes through the same, if I'm very careful by explicitly stating where the coercions should be added. Some lemmas I still need to formulate for Finset specifically, and sometimes I can use Set analogues.

I strongly prefer to keep updateFinset. If you don't like this operation, I'd be happy to call it marginalAux or something and move it to the Marginal file, to be PR'd later. (marginalAux was actually the original name, until I thought that this operation might be more generally useful.)

EDIT: "just use norm_cast" isn't very helpful, since updateSet is a dependently typed function: the type of argument y depends on the set s, so rewriting the set s to an equal set s' is already quite painful.

@fpvandoorn fpvandoorn requested a review from eric-wieser October 4, 2023 06:51
bors bot pushed a commit that referenced this pull request Oct 19, 2023
* Also fix the statement of some lemmas of an earlier PR.
* From the Sobolev project
* There are more that depend on #7341 

Co-authored-by: Heather Macbeth 25316162+hrmacbeth@users.noreply.github.com
@digama0
Copy link
Copy Markdown
Member

digama0 commented Oct 21, 2023

Note: I have pushed an update to the lean toolchain because this PR was on a buggy version of the toolchain. WARNING: checking out old commits of this PR using v4.2.0-rc2 or v4.2.0-rc3 can cause lake clean to delete your mathlib folder! If you need to do so, make sure to delete lakefile.olean manually before running any lake commands.

@ghost ghost added the merge-conflict The PR has a merge conflict with master, and needs manual merging. (this label is managed by a bot) label Oct 31, 2023
@ghost ghost removed the merge-conflict The PR has a merge conflict with master, and needs manual merging. (this label is managed by a bot) label Nov 6, 2023
Copy link
Copy Markdown
Member

@jcommelin jcommelin left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

LGTM

maintainer merge

@github-actions
Copy link
Copy Markdown

github-actions bot commented Nov 6, 2023

🚀 Pull request has been placed on the maintainer queue by jcommelin.

@sgouezel sgouezel added this pull request to the merge queue Nov 7, 2023
@github-merge-queue github-merge-queue bot removed this pull request from the merge queue due to no response for status checks Nov 7, 2023
@sgouezel sgouezel added this pull request to the merge queue Nov 7, 2023
Merged via the queue into master with commit 0eb6b93 Nov 7, 2023
@sgouezel sgouezel deleted the marginal_updateSet branch November 7, 2023 15:29
grunweg pushed a commit that referenced this pull request Dec 15, 2023
…of a vector (#7341)

* from the Sobolev project (formerly: marginal project)

---------

Co-authored-by: Mario Carneiro <di.gama@gmail.com>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

None yet

Projects

None yet

Development

Successfully merging this pull request may close these issues.

6 participants