feat(Analysis/Polynomial/MahlerMeasure): Landau's inequality and Mignotte bound#37349
Open
feat(Analysis/Polynomial/MahlerMeasure): Landau's inequality and Mignotte bound#37349
Conversation
…otte bound Extract Landau's inequality as a standalone theorem: the Mahler measure of a polynomial is at most the ℓ² norm of its coefficient vector. This was previously an intermediate step inside the proof of `mahlerMeasure_le_sqrt_natDegree_add_one_mul_supNorm`. Also add: - `one_le_mahlerMeasure`: M(p) ≥ 1 when the leading coefficient has norm ≥ 1 (e.g. nonzero integer polynomials) - `le_mahlerMeasure_mul_right/left`: monotonicity of Mahler measure under multiplication by a polynomial with M ≥ 1 - `norm_coeff_le_choose_mul_mahlerMeasure_mul`: Mignotte's coefficient bound for factors — if f = g * h with M(h) ≥ 1, then ‖g.coeff n‖ ≤ C(deg g, n) · M(f) These results complete the Mahler measure toolkit needed for verified polynomial factorization (Berlekamp–Zassenhaus). Co-Authored-By: Claude Opus 4.6 (1M context) <[email protected]>
PR summary 00fca21215Import changes for modified filesNo significant changes to the import graph Import changes for all files
|
Contributor
|
This pull request is now in draft mode. No active bors state needed cleanup. While this PR remains draft, bors will ignore commands on this PR. Mark it ready for review before using commands like |
- Rename `one_le_mahlerMeasure` to `one_le_mahlerMeasure_of_one_le_norm_leadingCoeff` to follow Mathlib convention of encoding hypotheses in names (matching the existing `one_le_mahlerMeasure_of_ne_zero` in NumberTheory). - Rename `norm_coeff_le_choose_mul_mahlerMeasure_mul` to `norm_coeff_le_choose_mul_mahlerMeasure_of_one_le_mahlerMeasure` since the `_mul` suffix was misleading (reads as multiplicativity). - Replace informal `‖f‖₂` in Mignotte docstring with the explicit `√(∑ i ∈ f.support, ‖f.coeff i‖ ^ 2)`. - Differentiate docstrings for `le_mahlerMeasure_mul_left` vs `_right`. Co-Authored-By: Claude Opus 4.6 (1M context) <[email protected]>
Co-Authored-By: Claude Opus 4.6 (1M context) <[email protected]>
Contributor
|
FWIW, the new declarations list doesn't match the actual declarations added (e.g., |
This file contains hidden or 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
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 PR extracts Landau's inequality as a standalone theorem and adds the
Mignotte coefficient bound for polynomial factors.
Landau's inequality (
mahlerMeasure_le_sqrt_sum_sq_norm_coeff) states thatthe Mahler measure of a polynomial is at most
√(∑ ‖coeff i‖²). This waspreviously buried as an intermediate step inside the proof of
mahlerMeasure_le_sqrt_natDegree_add_one_mul_supNorm, which is now a shortcorollary.
The Mignotte bound (
norm_coeff_le_choose_mul_mahlerMeasure_mul) says thatif
f = g * hwithM(h) ≥ 1, then‖g.coeff n‖ ≤ C(deg g, n) · M(f).The hypothesis
M(h) ≥ 1holds in particular for nonzero integer polynomials(via
one_le_mahlerMeasure, also added here). This is the classical boundused in Berlekamp–Zassenhaus polynomial factorization.
New declarations:
one_le_mahlerMeasuremahlerMeasure_le_sqrt_sum_sq_norm_coeffle_mahlerMeasure_mul_right/le_mahlerMeasure_mul_leftnorm_coeff_le_choose_mul_mahlerMeasure_mulThe ℓ² norm is stated explicitly as
√(∑ i ∈ p.support, ‖p.coeff i‖ ^ 2)with a TODO to restate using a dedicated polynomial ℓ² norm once one is
defined (cf. the TODO in
Mathlib.Analysis.Polynomial.Norm).🤖 Prepared with Claude Code