feat(combinatorics/additive/small_roth): Small Roth numbers #10645
Conversation
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
github-actions
bot
added
the
blocked-by-other-PR
2 tasks
b-mehta
reviewed
Dec 6, 2021
github-actions
bot
added
merge-conflict
github-actions
bot
removed
the
merge-conflict
leanprover-community-bot-assistant
added
the
blocked-by-other-PR
leanprover-community-bot-assistant
removed
the
blocked-by-other-PR
|
This PR/issue depends on: |
leanprover-community-bot-assistant
added
the
merge-conflict
leanprover-community-bot-assistant
removed
the
merge-conflict
sgouezel
reviewed
May 2, 2022
sgouezel
added
awaiting-author
github-actions
bot
added
the
modifies-synchronized-file
YaelDillies
added
awaiting-review
sgouezel
reviewed
Jun 11, 2023
|
|
||
| namespace roth | ||
|
|
||
| /-- `roth.presalem_spencer a l` returns whether there doesn't exist `b, c ∈ l` such that |
There was a problem hiding this comment.
Suggested change
| /-- `roth.presalem_spencer a l` returns whether there doesn't exist `b, c ∈ l` such that | |
| /-- `roth.presalem_spencer a l` returns true iff there doesn't exist `b, c ∈ l` such that |
| namespace roth | ||
|
|
||
| /-- `roth.presalem_spencer a l` returns whether there doesn't exist `b, c ∈ l` such that | ||
| `a + c = 2 * b`. `l` is a Salem-Spencer iff `presalem_spencer a l'` holds for all `a ∈ l` with `l'` |
There was a problem hiding this comment.
Suggested change
| `a + c = 2 * b`. `l` is a Salem-Spencer iff `presalem_spencer a l'` holds for all `a ∈ l` with `l'` | |
| `a + c = 2 * b`. The list `l` is a Salem-Spencer iff `presalem_spencer a l'` holds for all `a ∈ l` with `l'` |
something is missing before the iff.
| (H.2.1 hb hc e).not_gt $ hl.rel hb) } | ||
| end | ||
|
|
||
| /-- The Roth number algorithm invariant. -/ |
There was a problem hiding this comment.
Can you expand the docstring, and give a better name?
sgouezel
added
awaiting-author
|
Bhavik and I decided that we need to know more about the complexity of Lean 4's operations to decide whether this algorithm is worth pursuing, the tradeoff being that this algorithm does a lot of search (it's a barely optimised DFS), while Lean 4 might let us do a lot of reasoning for little cost. |
YaelDillies
added
maybe-later
and removed
awaiting-author
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Add this suggestion to a batch that can be applied as a single commit.
This suggestion is invalid because no changes were made to the code.
Suggestions cannot be applied while the pull request is closed.
Suggestions cannot be applied while viewing a subset of changes.
Only one suggestion per line can be applied in a batch.
Add this suggestion to a batch that can be applied as a single commit.
Applying suggestions on deleted lines is not supported.
You must change the existing code in this line in order to create a valid suggestion.
Outdated suggestions cannot be applied.
This suggestion has been applied or marked resolved.
Suggestions cannot be applied from pending reviews.
Suggestions cannot be applied on multi-line comments.
Suggestions cannot be applied while the pull request is queued to merge.
Suggestion cannot be applied right now. Please check back later.
This implements the BASIC2 algorithm from that paper.
Co-authored-by: Mario Carneiro
Co-authored-by: Bhavik Mehta bhavikmehta8@gmail.com
An example search is available on branch
roth_demo. We will add tactics to perform and cache the search automatically later.