Skip to content

feat(Analysis/Polynomial/MahlerMeasure): Landau's inequality and Mignotte bound#37349

Open
kim-em wants to merge 3 commits intomasterfrom
mahler-measure-mignotte
Open

feat(Analysis/Polynomial/MahlerMeasure): Landau's inequality and Mignotte bound#37349
kim-em wants to merge 3 commits intomasterfrom
mahler-measure-mignotte

Conversation

@kim-em
Copy link
Copy Markdown
Contributor

@kim-em kim-em commented Mar 30, 2026

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 that
the Mahler measure of a polynomial is at most √(∑ ‖coeff i‖²). This was
previously buried as an intermediate step inside the proof of
mahlerMeasure_le_sqrt_natDegree_add_one_mul_supNorm, which is now a short
corollary.

The Mignotte bound (norm_coeff_le_choose_mul_mahlerMeasure_mul) says that
if f = g * h with M(h) ≥ 1, then ‖g.coeff n‖ ≤ C(deg g, n) · M(f).
The hypothesis M(h) ≥ 1 holds in particular for nonzero integer polynomials
(via one_le_mahlerMeasure, also added here). This is the classical bound
used in Berlekamp–Zassenhaus polynomial factorization.

New declarations:

  • one_le_mahlerMeasure
  • mahlerMeasure_le_sqrt_sum_sq_norm_coeff
  • le_mahlerMeasure_mul_right / le_mahlerMeasure_mul_left
  • norm_coeff_le_choose_mul_mahlerMeasure_mul

The ℓ² 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

…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]>
@github-actions
Copy link
Copy Markdown

github-actions bot commented Mar 30, 2026

PR summary 00fca21215

Import changes for modified files

No significant changes to the import graph

Import changes for all files
Files Import difference

Declarations diff

+ mahlerMeasure_le_sqrt_sum_sq_norm_coeff
+ norm_coeff_le_choose_mul_mahlerMeasure_of_one_le_mahlerMeasure
+ one_le_mahlerMeasure_of_one_le_norm_leadingCoeff

You can run this locally as follows
## summary with just the declaration names:
./scripts/pr_summary/declarations_diff.sh <optional_commit>

## more verbose report:
./scripts/pr_summary/declarations_diff.sh long <optional_commit>

The doc-module for scripts/pr_summary/declarations_diff.sh contains some details about this script.


No changes to technical debt.

You can run this locally as

./scripts/reporting/technical-debt-metrics.sh pr_summary
  • The relative value is the weighted sum of the differences with weight given by the inverse of the current value of the statistic.
  • The absolute value is the relative value divided by the total sum of the inverses of the current values (i.e. the weighted average of the differences).

@github-actions github-actions bot added the t-analysis Analysis (normed *, calculus) label Mar 30, 2026
@kim-em kim-em marked this pull request as draft March 30, 2026 01:07
@mathlib-bors
Copy link
Copy Markdown
Contributor

mathlib-bors bot commented Mar 30, 2026

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 bors r+ or bors try.

kim-em and others added 2 commits March 30, 2026 01:12
- 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]>
@kim-em kim-em marked this pull request as ready for review March 30, 2026 01:15
@mcdoll mcdoll removed their assignment Mar 31, 2026
@khwilson
Copy link
Copy Markdown
Contributor

FWIW, the new declarations list doesn't match the actual declarations added (e.g., one_le_mahlerMeasure is not actually an added declaration)

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

t-analysis Analysis (normed *, calculus)

Projects

None yet

Development

Successfully merging this pull request may close these issues.

4 participants