/-
Copyright 2026 The Formal Conjectures Authors.
Licensed under the Apache License, Version 2.0 (the "License");
you may not use this file except in compliance with the License.
You may obtain a copy of the License at
https://www.apache.org/licenses/LICENSE-2.0
Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
limitations under the License.
-/
module
public import FormalConjecturesUtil
public import FormalConjectures.Wikipedia.ArtinPrimitiveRootsConjectureBen Green's Open Problem 93
References:
[Gr24] Green, Ben. "100 open problems." (2024).
[BrVa19] Breuillard, E. and Varjú, P. P., Irreducibility of random polynomials of large degree. Acta Math. 223 (2019), 195--249. arXiv:1810.13360
[BSKK23] Bary-Soroker, L., Koukoulopoulos, D. and Kozma, G., Irreducibility of random polynomials: general measures. Invent. Math. 233 (2023), 1041--1120. arXiv:2007.14567
[Ko99] Konyagin, S. V., On the number of irreducible polynomials with 0,1 coefficients. Acta Arith. 88 (1999), 333--350.
@[expose] public sectionopen Polynomial Filteropen scoped Topologynamespace Green93
monicPoly a is the monic polynomial $X^n + a_{n-1} X^{n-1} + \cdots + a_1 X + a_0 \in
\mathbb{Z}[X]$ with lower coefficients a j, $0 \le j < n$.
noncomputable def monicPoly {n : ℕ} (a : Fin n → ℕ) : ℤ[X] :=
X ^ n + ∑ j : Fin n, C (a j : ℤ) * X ^ (j : ℕ)open scoped Classical in
irreducibleProb M n is the probability that the random monic polynomial
$$X^n + a_{n-1} X^{n-1} + \cdots + a_1 X + a_0$$
of degree $n$ is irreducible, where $a_0, \dots, a_{n-1}$ are chosen uniformly from
${0, 1, \dots, M}$, conditioned on the constant term $a_0$ being nonzero. It is a quotient of
two finite counts over the coefficient vectors a : Fin n → Fin (M + 1).
The polynomial is monic, so by Gauss's lemma it is irreducible in $\mathbb{Z}[X]$ if and only if it
is irreducible over $\mathbb{Q}$ (for $n \ge 1$). For $M = 1$ the constant term is $1$ and
irreducibleProb 1 n is the probability $p_n$ of [Gr24, Problem 93] that
$1 + a_1 x + \cdots + a_{n-1} x^{n-1} + x^n$ is irreducible for i.i.d. uniform
$a_i \in {0, 1}$.
noncomputable def irreducibleProb (M n : ℕ) : ℝ :=
((Finset.univ.filter fun a : Fin n → Fin (M + 1) ↦
(monicPoly fun j ↦ (a j : ℕ)).coeff 0 ≠ 0 ∧
Irreducible (monicPoly fun j ↦ (a j : ℕ))).card : ℝ) /
(Finset.univ.filter fun a : Fin n → Fin (M + 1) ↦
(monicPoly fun j ↦ (a j : ℕ)).coeff 0 ≠ 0).card
irreducibleProb M n is nonnegative.
@[category API, AMS 11 12 60]
theorem irreducibleProb_nonneg (M n : ℕ) : 0 ≤ irreducibleProb M n := M:ℕn:ℕ⊢ 0 ≤ irreducibleProb M n
M:ℕn:ℕ⊢ 0 ≤
↑{a | (monicPoly fun j ↦ ↑(a j)).coeff 0 ≠ 0 ∧ Irreducible (monicPoly fun j ↦ ↑(a j))}.card /
↑{a | (monicPoly fun j ↦ ↑(a j)).coeff 0 ≠ 0}.card
All goals completed! 🐙
irreducibleProb M n is at most $1$, since it is a quotient of a count by a larger count.
@[category API, AMS 11 12 60]
theorem irreducibleProb_le_one (M n : ℕ) : irreducibleProb M n ≤ 1 := M:ℕn:ℕ⊢ irreducibleProb M n ≤ 1
M:ℕn:ℕ⊢ ↑{a | (monicPoly fun j ↦ ↑(a j)).coeff 0 ≠ 0 ∧ Irreducible (monicPoly fun j ↦ ↑(a j))}.card /
↑{a | (monicPoly fun j ↦ ↑(a j)).coeff 0 ≠ 0}.card ≤
1
M:ℕn:ℕ⊢ ↑{a | (monicPoly fun j ↦ ↑(a j)).coeff 0 ≠ 0 ∧ Irreducible (monicPoly fun j ↦ ↑(a j))}.card ≤
↑{a | (monicPoly fun j ↦ ↑(a j)).coeff 0 ≠ 0}.cardM:ℕn:ℕ⊢ 0 ≤ ↑{a | (monicPoly fun j ↦ ↑(a j)).coeff 0 ≠ 0}.card
M:ℕn:ℕ⊢ ↑{a | (monicPoly fun j ↦ ↑(a j)).coeff 0 ≠ 0 ∧ Irreducible (monicPoly fun j ↦ ↑(a j))}.card ≤
↑{a | (monicPoly fun j ↦ ↑(a j)).coeff 0 ≠ 0}.card M:ℕn:ℕ⊢ {a | (monicPoly fun j ↦ ↑(a j)).coeff 0 ≠ 0 ∧ Irreducible (monicPoly fun j ↦ ↑(a j))} ⊆
{a | (monicPoly fun j ↦ ↑(a j)).coeff 0 ≠ 0}
M:ℕn:ℕa:Fin n → Fin (M + 1)ha:a ∈ {a | (monicPoly fun j ↦ ↑(a j)).coeff 0 ≠ 0 ∧ Irreducible (monicPoly fun j ↦ ↑(a j))}⊢ a ∈ {a | (monicPoly fun j ↦ ↑(a j)).coeff 0 ≠ 0}
M:ℕn:ℕa:Fin n → Fin (M + 1)ha:(monicPoly fun j ↦ ↑(a j)).coeff 0 ≠ 0 ∧ Irreducible (monicPoly fun j ↦ ↑(a j))⊢ (monicPoly fun j ↦ ↑(a j)).coeff 0 ≠ 0
All goals completed! 🐙
M:ℕn:ℕ⊢ 0 ≤ ↑{a | (monicPoly fun j ↦ ↑(a j)).coeff 0 ≠ 0}.card All goals completed! 🐙Is a random polynomial with coefficients in ${0,1}$ and nonzero constant term almost surely irreducible?
More precisely, writing $p_n$ for the probability that $1 + a_1 x + \cdots + a_{n-1} x^{n-1} + x^n$ is irreducible, where the $a_i$ are independent and take the values $0$ and $1$ with equal probability, does $p_n \to 1$?
The probability $p_n$ is irreducibleProb 1 n. The conjecture is due to Odlyzko and Poonen
[BrVa19, Section 1].
@[category research open, question, AMS 11 12 60]
theorem green_93 : Tendsto (fun n : ℕ ↦ irreducibleProb 1 n) atTop (𝓝 1) := ⊢ Tendsto (fun n ↦ irreducibleProb 1 n) atTop (𝓝 1)
All goals completed! 🐙
Konyagin [Ko99] proved that $p_n \ge c / \log n$ for an absolute constant $c > 0$, as stated in
[BrVa19, Section 1]. We state it for all large $n$. It is superseded by
green_93.variants.bskk_small.
@[category research solved, AMS 11 12 60]
theorem green_93.variants.konyagin :
∃ c : ℝ, 0 < c ∧ ∀ᶠ n : ℕ in atTop, c / Real.log (n : ℝ) ≤ irreducibleProb 1 n := ⊢ ∃ c, 0 < c ∧ ∀ᶠ (n : ℕ) in atTop, c / Real.log ↑n ≤ irreducibleProb 1 n
All goals completed! 🐙
Bary-Soroker, Koukoulopoulos and Kozma [BSKK23, Theorem 1(b)] proved that a random monic
polynomial of degree $n$ whose coefficients are uniform on $N$ consecutive integers in $[-H, H]$
with $2 \le N \le 34$, and with nonzero constant term, is irreducible with probability at least
$\delta$. Here $\delta > 0$ is an absolute constant, and $n$ must be at least an absolute constant
and at least $(\log H)^3$. We state it for the integers ${0, 1, \dots, M}$ with
$1 \le M \le 33$, so $N = M + 1$ and $H = M$. The condition on $(\log H)^3$ is absorbed into
$n_0$, because $M$ is bounded. The case $M = 1$ gives $p_n \ge \delta$ for large $n$ for the
polynomial of green_93.
@[category research solved, AMS 11 12 60]
theorem green_93.variants.bskk_small :
∃ δ : ℝ, 0 < δ ∧ ∃ n₀ : ℕ, ∀ M n : ℕ, 1 ≤ M → M ≤ 33 → n₀ ≤ n →
δ ≤ irreducibleProb M n := ⊢ ∃ δ, 0 < δ ∧ ∃ n₀, ∀ (M n : ℕ), 1 ≤ M → M ≤ 33 → n₀ ≤ n → δ ≤ irreducibleProb M n
All goals completed! 🐙
Bary-Soroker, Koukoulopoulos and Kozma [BSKK23, Theorem 1(a)] proved that a random monic
polynomial of degree $n$ whose coefficients are uniform on $N \ge 35$ consecutive integers in
$[-H, H]$, with nonzero constant term, is irreducible with probability at least $1 - n^{-c}$.
Here $c > 0$ is an absolute constant, and $n$ must be at least an absolute constant and at least
$(\log H)^3$. We state it for the integers
${0, 1, \dots, M}$ with $M \ge 34$, so $N = M + 1 \ge 35$ and $H = M$. In particular
irreducibleProb M n $\to 1$ for each such $M$, which is the analogue of green_93 for
coefficients in ${0, \dots, M}$.
@[category research solved, AMS 11 12 60]
theorem green_93.variants.bskk_large :
∃ c : ℝ, 0 < c ∧ ∃ n₀ : ℕ, ∀ M n : ℕ, 34 ≤ M → n₀ ≤ n → (Real.log (M : ℝ)) ^ 3 ≤ n →
1 - (n : ℝ) ^ (-c) ≤ irreducibleProb M n := ⊢ ∃ c, 0 < c ∧ ∃ n₀, ∀ (M n : ℕ), 34 ≤ M → n₀ ≤ n → Real.log ↑M ^ 3 ≤ ↑n → 1 - ↑n ^ (-c) ≤ irreducibleProb M n
All goals completed! 🐙The Riemann hypothesis holds for the Dedekind zeta function of every number field $\mathbb{Q}(a)$ generated by a root $a$ of a nonzero polynomial with all coefficients in ${0, 1}$.
Here a number field K is generated by a if IntermediateField.adjoin ℚ {a} = ⊤. The Riemann
hypothesis for K is ArtinPrimitiveRootsConjecture.DedekindZetaRH K, which uses the analytic
continuation of the Dedekind zeta function and not Mathlib's NumberField.dedekindZeta.
def ZeroOneRootFieldsRH : Prop :=
∀ (K : Type) [Field K] [NumberField K] (f : ℤ[X]) (a : K),
f ≠ 0 → (∀ i, f.coeff i = 0 ∨ f.coeff i = 1) → aeval a f = 0 →
IntermediateField.adjoin ℚ {a} = ⊤ → ArtinPrimitiveRootsConjecture.DedekindZetaRH K
Breuillard and Varjú. Assume the Riemann hypothesis for the Dedekind zeta functions of all
number fields $\mathbb{Q}(a)$ with $a$ a root of a polynomial with coefficients in ${0, 1}$
(ZeroOneRootFieldsRH). Then $p_n \to 1$ [BrVa19, Theorem 1].
@[category research solved, AMS 11 12 60]
theorem green_93.variants.breuillard_varju :
ZeroOneRootFieldsRH → Tendsto (fun n : ℕ ↦ irreducibleProb 1 n) atTop (𝓝 1) := ⊢ ZeroOneRootFieldsRH → Tendsto (fun n ↦ irreducibleProb 1 n) atTop (𝓝 1)
All goals completed! 🐙end Green93