OctoInform Beta

OpenAI preprint, September 2026 · §6. Completion of the induction · §6

Lemma 6.1 [Horizontal-strip reduction]: For m≥2m \ge 2 and λ⊢Nm=|ρm|\lambda \vdash N_m = |\rho_m|, one strip leads down to size Nm−1N_{m-1}, or at most four nonempty strips to Nm−2N_{m-2}

Horizontal strips reduce partitions not dominated by the staircase.

Hover over a blue or green term in the text, or a node in the graph, to find it in the other. Select it to read its declaration both in Lean and in words.

The Setting

For a natural number mm, the staircase ρm\rho_m is the partition (m,m−1,…,1)(m, m-1, \dots, 1) of Nm=m(m+1)/2N_m = m(m+1)/2.✦ Adding a horizontal strip to a partition is the step of the Pieri rule. The question is, for m≥2m \ge 2, how a partition λ\lambda of NmN_m that ρm\rho_m does not dominate is reached by such steps from a partition of a smaller staircase size, Nm−1N_{m-1} or Nm−2N_{m-2}, and in how many steps.

Dominance and Horizontal Strips

A partition λ\lambda is identified with its Young diagram: λ1≥λ2≥…\lambda_1 \ge \lambda_2 \ge \dots are the lengths of its rows, with λi=0\lambda_i = 0 beyond the last row, and |λ||\lambda| is its number of cells. The row prefix sum rk(λ)r_k(\lambda) of a Young diagram λ\lambda, for k≥0k \ge 0, is the number of cells in its first kk rows: rk(λ)=λ1+λ2+…+λk.r_k(\lambda) = \lambda_1 + \lambda_2 + \dots + \lambda_k .(1)✦

A Young diagram μ\mu dominates a Young diagram ν\nu, written μ⊵ν\mu \trianglerighteq \nu, if rk(ν)≤rk(μ)r_k(\nu) \le r_k(\mu) for every k≥0k \ge 0.✦

For Young diagrams ν\nu and λ\lambda, the skew diagram λ/ν\lambda/\nu is a horizontal strip if ν⊆λ\nu \subseteq \lambda and no two cells of λ\lambda outside ν\nu lie in the same column.✦ A strip chain of length q≥0q \ge 0 from a Young diagram ν\nu to a Young diagram λ\lambda is a sequence of Young diagrams ν=λ(0)⊊λ(1)⊊…⊊λ(q)=λ\nu = \lambda^{(0)} \subsetneq \lambda^{(1)} \subsetneq \dots \subsetneq \lambda^{(q)} = \lambda(2)✦ in which every λ(i)/λ(i−1)\lambda^{(i)}/\lambda^{(i-1)} is a horizontal strip.

The Claim

Theorem 1. Let m≥2m \ge 2, and let λ\lambda be a Young diagram with |λ|=Nm|\lambda| = N_m that is not dominated by ρm\rho_m. Then there is a Young diagram ν\nu for which one of the following holds: (i)|ν|=Nm−1 and λ/ν is a horizontal strip;(ii)m≥5,|ν|=Nm−2, and there is a strip chain of length at most 4 from ν to λ.\begin{aligned} &\text{(i)}\quad |\nu| = N_{m-1} \text{ and } \lambda/\nu \text{ is a horizontal strip;}\\ &\text{(ii)}\quad m \ge 5,\ |\nu| = N_{m-2}, \text{ and there is a strip chain of length at most } 4 \text{ from } \nu \text{ to } \lambda. \end{aligned}(3)✦

In the paper, the result reads: for m≥2m \ge 2 and λ⊢Nm\lambda \vdash N_m not dominated by ρm\rho_m, either there is ν⊢Nm−1\nu \vdash N_{m-1} with λ/ν\lambda/\nu a horizontal strip of size mm, or m≥5m \ge 5 and there are ν=λ(0)⊂λ(1)⊂…⊂λ(q)=λ\nu = \lambda^{(0)} \subset \lambda^{(1)} \subset \dots \subset \lambda^{(q)} = \lambda with q≤4q \le 4 and ν⊢Nm−2\nu \vdash N_{m-2}, every λ(i)/λ(i−1)\lambda^{(i)}/\lambda^{(i-1)} a nonempty horizontal strip, of total size 2m−12m - 1.

What Is Checked

The theorem is stated over Young diagrams and their sizes, the staircase ρm\rho_m with the staircase sizes Nm−1N_{m-1} and Nm−2N_{m-2}, the dominance order given by row prefix sums, horizontal strips, and strip chains.

The library proves that the row prefix sums of a staircase are, for k≤mk \le m, 2rk(ρm)=k(2m+1−k),2\, r_k(\rho_m) = k(2m + 1 - k),(4)✦ and that those of any Young diagram λ\lambda satisfy, for q≤kq \le k, qrk(λ)≤krq(λ).q\, r_k(\lambda) \le k\, r_q(\lambda).(5)✦

For a Young diagram λ\lambda and t≥0t \ge 0, the strip removal RtλR_t\lambda is the Young diagram contained in λ\lambda whose row ii has length (Rtλ)i=max⁡(λi−t,0)+min⁡(t,λi+1).(R_t\lambda)_i = \max(\lambda_i - t, 0) + \min(t, \lambda_{i+1}).(6)✦

When tt is the length λ1\lambda_1 of the first row, the strip removal satisfies (Rλ1λ)i=λi+1for every i≥1.(R_{\lambda_1}\lambda)_i = \lambda_{i+1} \quad \text{for every } i \ge 1.(7)✦

Given a Young diagram λ\lambda, a number q≥0q \ge 0 and t≤rq(λ)t \le r_q(\lambda), there are k≤qk \le q and a Young diagram ν\nu such that |ν|+t=|λ|and there is a strip chain of length k from ν to λ.|\nu| + t = |\lambda| \quad \text{and there is a strip chain of length } k \text{ from } \nu \text{ to } \lambda.(8)✦

Under the hypotheses of the theorem, if moreover λ1<m\lambda_1 < m, then m≥5andr4(λ)≥2m−1.m \ge 5 \quad \text{and} \quad r_4(\lambda) \ge 2m - 1.(9)✦