/- 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

Parities of partition numbers

There are several conjectures on parities of partition numbers. The most famous conjecture is the Parkin-Shanks conjecture, which states that the natural density of n where the partition number p(n) is even (resp. odd) exists and equals 1/2.

There are several related (weaker) results toward the conjecture. Kolberg showed that p(n) takes each parity infinitely often. Subbarao conjectured that every arithmetic progression r (mod t) contains infinitely many n with p(n) even and infinitely many n with p(n) odd; the even case was proved by Ono and the odd case by Radu. Quantitative lower bounds for the number of n ≤ X with p(n) even (resp. odd) have also been studied. The best known bounds are ≫ √X log log X for even values (Bellaïche–Nicolas) and ≫ √X for odd values (Zheng, in an appendix to Ono–Swaminathan). Ono–Swaminathan also proved that both parities occur infinitely often along the quadratic progressions (D m² + 1) / 24, and Ono conjectured the same for every nonconstant integer-valued polynomial that is eventually positive.

References:

@[expose] public sectionnamespace PartitionParityopen Nat Real Filter Topology Asymptotics Polynomial

p(n) is even for infinitely many n and odd for infinitely many n. (Kolberg)

@[category research solved, AMS 11] theorem kolberg : {n : ℕ | Even (partitionNumber n)}.Infinite ∧ {n : ℕ | Odd (partitionNumber n)}.Infinite := ⊢ {n | Even n.partitionNumber}.Infinite ∧ {n | Odd n.partitionNumber}.Infinite All goals completed! 🐙

The natural density of n where the partition number p(n) is even (resp. odd) exists and equals 1/2.

@[category research open, AMS 11] theorem parkin_shanks : {n : ℕ | Even (partitionNumber n)}.HasDensity (1 / 2) ∧ {n : ℕ | Odd (partitionNumber n)}.HasDensity (1 / 2) := ⊢ {n | Even n.partitionNumber}.HasDensity (1 / 2) ∧ {n | Odd n.partitionNumber}.HasDensity (1 / 2) All goals completed! 🐙

Every arithmetic progression contains infinitely many n where p(n) is even. Conjectured by Subbarao and proved by Ono.

@[category research solved, AMS 11] theorem subbarao.even : ∀ r t, 0 < t → {n : ℕ | n ≡ r [MOD t] ∧ Even (partitionNumber n)}.Infinite := ⊢ ∀ (r t : ℕ), 0 < t → {n | n ≡ r [MOD t] ∧ Even n.partitionNumber}.Infinite All goals completed! 🐙

Every arithmetic progression contains infinitely many n where p(n) is odd. Conjectured by Subbarao; Ono proved it for every progression containing at least one n with p(n) odd, and Radu showed that every progression contains such an n.

@[category research solved, AMS 11] theorem subbarao.odd : ∀ r t, 0 < t → {n : ℕ | n ≡ r [MOD t] ∧ Odd (partitionNumber n)}.Infinite := ⊢ ∀ (r t : ℕ), 0 < t → {n | n ≡ r [MOD t] ∧ Odd n.partitionNumber}.Infinite All goals completed! 🐙

For every arithmetic progression r (mod t), the number of n ≤ X with n ≡ r (mod t) and p(n) even is ≫ √X. (Ahlgren)

@[category research solved, AMS 11] theorem ahlgren.even : ∀ r t, 0 < t → (fun X : ℝ ↦ √X) =O[atTop] fun X : ℝ ↦ ({n : ℕ | n ≤ X ∧ n ≡ r [MOD t] ∧ Even (partitionNumber n)}.ncard : ℝ) := ⊢ ∀ (r t : ℕ), 0 < t → (fun X ↦ √X) =O[atTop] fun X ↦ ↑{n | ↑n ≤ X ∧ n ≡ r [MOD t] ∧ Even n.partitionNumber}.ncard All goals completed! 🐙

For every arithmetic progression r (mod t), the number of n ≤ X with n ≡ r (mod t) and p(n) odd is ≫ √X / log X. Ahlgren proved this for every progression containing at least one n with p(n) odd; by Radu's theorem every progression does.

@[category research solved, AMS 11] theorem ahlgren.odd : ∀ r t, 0 < t → (fun X : ℝ ↦ √X / X.log) =O[atTop] fun X : ℝ ↦ ({n : ℕ | n ≤ X ∧ n ≡ r [MOD t] ∧ Odd (partitionNumber n)}.ncard : ℝ) := ⊢ ∀ (r t : ℕ), 0 < t → (fun X ↦ √X / Real.log X) =O[atTop] fun X ↦ ↑{n | ↑n ≤ X ∧ n ≡ r [MOD t] ∧ Odd n.partitionNumber}.ncard All goals completed! 🐙

The number of n ≤ X with p(n) even is ≫ √X log log X. (Bellaïche–Nicolas)

@[category research solved, AMS 11] theorem bellaiche_nicolas.even : (fun X : ℝ ↦ √X * X.log.log) =O[atTop] fun X : ℝ ↦ ({n : ℕ | n ≤ X ∧ Even (partitionNumber n)}.ncard : ℝ) := ⊢ (fun X ↦ √X * Real.log (Real.log X)) =O[atTop] fun X ↦ ↑{n | ↑n ≤ X ∧ Even n.partitionNumber}.ncard All goals completed! 🐙

The number of n ≤ x with p(n) even is at least 0.069 √x log log x for every x > 1. (Bellaïche–Nicolas)

@[category research solved, AMS 11] theorem bellaiche_nicolas.even_explicit : ∀ x : ℝ, 1 < x → 0.069 * √x * x.log.log ≤ ({n : ℕ | n ≤ x ∧ Even (partitionNumber n)}.ncard : ℝ) := ⊢ ∀ (x : ℝ), 1 < x → 69e-3 * √x * Real.log (Real.log x) ≤ ↑{n | ↑n ≤ x ∧ Even n.partitionNumber}.ncard All goals completed! 🐙

The number of n ≤ x with p(n) odd is at least 0.037 √x / (log x)^(7/8) for every x ≥ 2. (Bellaïche–Nicolas)

@[category research solved, AMS 11] theorem bellaiche_nicolas.odd_explicit : ∀ x : ℝ, 2 ≤ x → 0.037 * √x / (x.log) ^ (7 / 8 : ℝ) ≤ ({n : ℕ | n ≤ x ∧ Odd (partitionNumber n)}.ncard : ℝ) := ⊢ ∀ (x : ℝ), 2 ≤ x → 37e-3 * √x / Real.log x ^ (7 / 8) ≤ ↑{n | ↑n ≤ x ∧ Odd n.partitionNumber}.ncard All goals completed! 🐙

The number of n ≤ X with p(n) odd is ≫ √X / log log X. (Bellaïche–Green–Soundararajan)

@[category research solved, AMS 11] theorem bellaiche_green_soundararajan.odd : (fun X : ℝ ↦ √X / X.log.log) =O[atTop] fun X : ℝ ↦ ({n : ℕ | n ≤ X ∧ Odd (partitionNumber n)}.ncard : ℝ) := ⊢ (fun X ↦ √X / Real.log (Real.log X)) =O[atTop] fun X ↦ ↑{n | ↑n ≤ X ∧ Odd n.partitionNumber}.ncard All goals completed! 🐙

For square-free D > 1 with D ≡ 23 (mod 24), both parities occur infinitely often among p((D m² + 1) / 24) as m ranges over the positive integers coprime to 6. Note that 24 ∣ D m² + 1 for such m. Conjectured by Ono and proved by Ono–Swaminathan.

@[category research solved, AMS 11] theorem ono_swaminathan.quadratic : ∀ D : ℕ, 1 < D → Squarefree D → D % 24 = 23 → {m : ℕ | m.Coprime 6 ∧ Even (partitionNumber ((D * m ^ 2 + 1) / 24))}.Infinite ∧ {m : ℕ | m.Coprime 6 ∧ Odd (partitionNumber ((D * m ^ 2 + 1) / 24))}.Infinite := ⊢ ∀ (D : ℕ), 1 < D → Squarefree D → D % 24 = 23 → {m | m.Coprime 6 ∧ Even ((D * m ^ 2 + 1) / 24).partitionNumber}.Infinite ∧ {m | m.Coprime 6 ∧ Odd ((D * m ^ 2 + 1) / 24).partitionNumber}.Infinite All goals completed! 🐙

The odd half of Theorem 1 of Ono–Swaminathan, with its effective bound: for square-free D > 1 with D ≡ 23 (mod 24) there is an m coprime to 6 with m ≤ 12 h(-D) + 2 such that p((D m² + 1) / 24) is odd, where h(-D) is the class number of ℚ(√-D). Here ℚ(√-D) is AdjoinRoot (X ^ 2 + D), a number field since X ^ 2 + D is irreducible over ℚ for D > 0.

@[category research solved, AMS 11] theorem ono_swaminathan.odd_bound (D : ℕ) (hD : 1 < D) (hsq : Squarefree D) (h23 : D % 24 = 23) : haveI : Fact (Irreducible (X ^ 2 + C (D : ℚ))) := ⟨irreducible_X_sq_add_C_of_pos (Nat.cast_pos.2 (D:ℕhD:1 < Dhsq:Squarefree Dh23:D % 24 = 23⊢ 0 < D All goals completed! 🐙))⟩ ∃ m : ℕ, m.Coprime 6 ∧ m ≤ 12 * NumberField.classNumber (AdjoinRoot (X ^ 2 + C (D : ℚ))) + 2 ∧ Odd (partitionNumber ((D * m ^ 2 + 1) / 24)) := D:ℕhD:1 < Dhsq:Squarefree Dh23:D % 24 = 23⊢ ∃ m, m.Coprime 6 ∧ m ≤ 12 * NumberField.classNumber (AdjoinRoot (X ^ 2 + C ↑D)) + 2 ∧ Odd ((D * m ^ 2 + 1) / 24).partitionNumber All goals completed! 🐙

[a, b, c] is a reduced primitive positive-definite binary quadratic form of discriminant -D: b² - 4ac = -D, |b| ≤ a ≤ c, gcd(a, b, c) = 1, and b ≥ 0 if |b| = a or a = c.

def IsReducedForm (D : ℕ) (a b c : ℤ) : Prop := b ^ 2 - 4 * a * c = -D ∧ |b| ≤ a ∧ a ≤ c ∧ Int.gcd (Int.gcd a b) c = 1 ∧ (|b| = a ∨ a = c → 0 ≤ b)

For square-free D ≡ 3 (mod 4), the discriminant -D is fundamental and the class number of ℚ(√-D) equals the number of reduced primitive positive-definite binary quadratic forms of discriminant -D [Cox, Theorem 2.8]. This identification is used in Zheng's appendix to Ono–Swaminathan.

@[category textbook, AMS 11] theorem classNumber_eq_ncard_reducedForms (D : ℕ) (hsq : Squarefree D) (h3 : D % 4 = 3) : haveI : Fact (Irreducible (X ^ 2 + C (D : ℚ))) := ⟨irreducible_X_sq_add_C_of_pos (Nat.cast_pos.2 (D:ℕhsq:Squarefree Dh3:D % 4 = 3⊢ 0 < D All goals completed! 🐙))⟩ NumberField.classNumber (AdjoinRoot (X ^ 2 + C (D : ℚ))) = {⟨a, b, c⟩ : ℤ × ℤ × ℤ | IsReducedForm D a b c}.ncard := D:ℕhsq:Squarefree Dh3:D % 4 = 3⊢ NumberField.classNumber (AdjoinRoot (X ^ 2 + C ↑D)) = {(a, b, c) | IsReducedForm D a b c}.ncard All goals completed! 🐙

Zheng's explicit lower bound: liminf_{X → ∞} N_odd(X) / √X ≥ 243 / (64 √6 π⁵), where N_odd(X) is the number of n ≤ X with p(n) odd [Ono-Swaminathan, Appendix A, Corollary 2].

@[category research solved, AMS 11, conditional formal_proof using lean4 at "https://github.com/AxiomMath/PartitionZheng/blob/9bfb4326c4ea1e00016a842d7cc145e5c4e0684a/Solution/Basic.lean#L17" assuming ono_swaminathan.odd_bound classNumber_eq_ncard_reducedForms] theorem zheng.liminf : ((243 / (64 * √6 * π ^ 5) : ℝ) : EReal) ≤ liminf (fun X : ℝ ↦ ((({n : ℕ | n ≤ X ∧ Odd (partitionNumber n)}.ncard : ℝ) / √X : ℝ) : EReal)) atTop := ⊢ ↑(243 / (64 * √6 * π ^ 5)) ≤ Filter.liminf (fun X ↦ ↑(↑{n | ↑n ≤ X ∧ Odd n.partitionNumber}.ncard / √X)) atTop All goals completed! 🐙

The number of n ≤ X with p(n) odd is ≫ √X.

@[category research solved, AMS 11] theorem zheng.odd : (fun X : ℝ ↦ √X) =O[atTop] fun X : ℝ ↦ ({n : ℕ | n ≤ X ∧ Odd (partitionNumber n)}.ncard : ℝ) := ⊢ (fun X ↦ √X) =O[atTop] fun X ↦ ↑{n | ↑n ≤ X ∧ Odd n.partitionNumber}.ncard All goals completed! 🐙

Ono's conjecture, as stated in Section 1 of Ono–Swaminathan: if g is a nonconstant integer-valued polynomial that is eventually positive, then p(g(n)) is even for infinitely many n and odd for infinitely many n.

@[category research open, AMS 11] theorem ono.polynomial (g : ℚ[X]) (hg : 0 < g.natDegree) (hint : ∀ n : ℕ, ∃ k : ℤ, g.eval (n : ℚ) = k) (hpos : ∀ᶠ n : ℕ in atTop, 0 < g.eval (n : ℚ)) : {n : ℕ | Even (partitionNumber ⌊g.eval (n : ℚ)⌋₊)}.Infinite ∧ {n : ℕ | Odd (partitionNumber ⌊g.eval (n : ℚ)⌋₊)}.Infinite := g:ℚ[X]hg:0 < g.natDegreehint:∀ (n : ℕ), ∃ k, eval (↑n) g = ↑khpos:∀ᶠ (n : ℕ) in atTop, 0 < eval (↑n) g⊢ {n | Even ⌊eval (↑n) g⌋₊.partitionNumber}.Infinite ∧ {n | Odd ⌊eval (↑n) g⌋₊.partitionNumber}.Infinite All goals completed! 🐙end PartitionParity