Exact multiplicity by a bounded search.
ProvedSingmaster.mult_eq_two_add_interioraether-catalogcombinatorics
Exact multiplicity by a bounded search. For t ≥ 3 and any cut-off N ≥ 2
whose triangular number already exceeds t, the multiplicity of t is exactly
2 (the two boundary occurrences C(t,1) = C(t,t-1) = t) plus the number of interior
occurrences in the box [0,N)².
The hypothesis t < C(N,2) is what makes the box exhaustive: an interior entry of row
n is at least C(n,2), and n ↦ C(n,2) is strictly increasing.
theorem Singmaster.mult_eq_two_add_interior{t N : ℕ} (ht : 3 ≤ t) (hN2 : 2 ≤ N)
(hN : t < N.choose 2) : mult t = 2 + (interiorOcc t N).card := by sorry
Formalization Note Transplanted verbatim from the Aether Catalog source Combinatorics/SingmasterExactCounts.lean; the statement is byte-identical to the source declaration, elaborated with autoImplicit disabled in the platform environment.
Preamble
-- Thm stub generated from Combinatorics/SingmasterExactCounts.lean
import Mathlib
import Definitions.Def_Combinatorics_SingmasterExactCounts
import Definitions.Def_Combinatorics_SingmasterOccurrences
/-
# Exact multiplicities: a certified finite algorithm, and `N(3003) = 8`
Fifth research cycle. The earlier files bound or reduce the multiplicity function
`N(t) = Singmaster.mult t`; this file turns the structure theory into a *certified
decision procedure* for a single value of `t`, and runs it.
## The algorithm
Every occurrence of `t ≥ 3` is either one of the two boundary occurrences `(t,1)`,
`(t,t-1)`, or an **interior** one, i.e. `C(n,k) = t` with `2 ≤ k ≤ n - 2`. An interior
occurrence satisfies `C(n,2) ≤ C(n,k) = t` (`Singmaster.choose_two_le_choose`), so its
row is capped by any `N` with `t < C(N,2)`; that is, by roughly `√(2t)`. Hence
`N(t) = 2 + #{(n,k) : n,k < N, 2 ≤ k ≤ n-2, C(n,k) = t}`,
a search over an explicitly bounded box (`Singmaster.mult_eq_two_add_interior`). As in
`Combinatorics.SingmasterCentralBinomial` the test `C(n,k) = t` is carried out through
`Nat.descFactorial` (`Singmaster.choose_eq_iff_descFactorial`), which costs `k`
multiplications instead of `C(n,k)` additions and is what makes kernel evaluation
possible.
## Results
* `Singmaster.mult_eq_two_add_interior` — the certified algorithm;
* `Singmaster.mult_eq_two_of_no_interior` — the "only the two trivial occurrences" case;
* `Singmaster.mult_3003` — **`3003` occurs exactly eight times**, upgrading
`Singmaster.eight_le_mult_3003` from a lower bound to an equality. This is the
specimen singled out in Singmaster's problem;
* `Singmaster.mult_120`, `mult_210`, `mult_1540`, `mult_7140`, `mult_11628` — the other
small numbers of multiplicity six: each occurs **exactly** six times.
Together with `Combinatorics.SingmasterCentralBinomial` this makes every multiplicity
claim in the classical folklore list machine-checked, except for the asymptotic ones.
-/
open Finset
open Singmaster
/-! ## Binomial coefficients through descending factorials -/
/-! ## The interior occurrences -/
/-! ## The certified algorithm -/Formal statement
theorem Singmaster.mult_eq_two_add_interior{t N : ℕ} (ht : 3 ≤ t) (hN2 : 2 ≤ N)
(hN : t < N.choose 2) : mult t = 2 + (interiorOcc t N).card := by sorrySource