Skip to content

[formalization] Uniform half-step lag windows and associated Bell rows #1875

Closed

Description

@PerAlexandersson

Purpose and mathematical status

Formalize the uniform half-step window theorem behind the downstream A059022 and A059023 proofs, then replace those two sequence-specific window inductions with thin recurrence bridges.

The theorem is proved on paper in uniform-half-step-lag-windows.md. It is a reachable-orbit theorem for a positive X lag, not universal preservation by the full companion matrix. Parent #601; orbit API #1872; router #1873; consolidation #1675.

Claude owns Lean source, downstream edits, integration, serialized builds, source guards, and axiom audits. The research lane edits only notes/issues and runs no Lean build.

1. Abstract half-step theorem

Add a reusable module, provisionally

RealRooted/DerivativeRecurrence/HalfStepLag.lean

Fix k>=1, H : Nat -> ℝ[X], and c : Nat -> ℝ. Use the subtraction-free recurrence shape

hodd  : forall m,
  H (2*m+1) = thetaPlusOne (H (2*m))

heven : forall q,
  H (2*(q+k)) =
    H (2*(q+k)-1) + C (c q) * X * H (2*q)

hc : forall q, 0 < c q
hnn : forall n, HasNonnegCoeffs (H n).

Define an inclusive pairwise window, or state it inline:

HalfStepWindow H k n :=
  forall i j, n <= i -> i <= j -> j <= n+2*k ->
    StrictInterl (H i) (H j).

Prove

halfStepWindow_of_positive_X_lag
  (hk : 1 <= k)
  (hbase : HalfStepWindow H k 0)
  (hodd ...) (heven ...) (hc ...) (hnn ...) :
  forall n, HalfStepWindow H k n.

The exact public names may change; keep the theorem general in c. Do not bake binomial coefficients or OEIS data into this layer.

2. Required proof route

Reuse the checked APIs already on origin/main:

  • strictInterl_chain_of_consecutive_of_endpoint;
  • StrictInterl.thetaPlusOne_of_pf;
  • StrictInterl.add_mul_X_of_common_left;
  • StrictInterl.insert_X_lag_of_nonneg;
  • thetaPlusOne_ne_zero_of_ne_zero;
  • natDegree_thetaPlusOne_of_ne_zero.

For the slide from [n,n+2k] to [n+1,n+2k+1], split on the parity of n.

Even start n=2t

The new endpoint is thetaPlusOne (H (2t+2k)), and the new start is thetaPlusOne (H (2t)). Apply thetaPlusOne_of_pf to the old endpoint edge for the new endpoint comparison. Use the Euler/Rolle self-edge for the new consecutive edge. Feed these edges and the inherited consecutive chain to strictInterl_chain_of_consecutive_of_endpoint.

Odd start n=2t+1

Set q=t+1, v=H (2q), and u=H (2t+2k+1). The new endpoint is u + C(c q)*X*v. The old window gives v<<u; insert_X_lag_of_nonneg gives u<<Xv, and applying it to the reflexive edge gives v<<Xv. Use add_mul_X_of_common_left twice to obtain the new consecutive and endpoint edges, then close the window by the same chain theorem.

Do not reprove descending-root characterizations or copy the 200-line chain lemmas from downstream.

3. Seeded row recurrence

Package the common row interface:

A m = 1                                      for m<k
A (q+k) = thetaPlusOne (A (q+k-1))
          + C(c q) * X * A q                for q>=0
c q > 0.

With

H (2*m)   = A m
H (2*m+1) = thetaPlusOne (A m),

prove:

  • HasNonnegCoeffs (A m) and the same for H;
  • the initial window H 0,...,H (2*k) is pairwise StrictInterl;
  • HalfStepWindow H k n for every n;
  • StrictInterl (A m) (A (m+r)) for r<=k;
  • coordinate PF/splitting for every row;
  • natDegree (A m)=m/k and positive leading coefficient.

Keep the exact degree proof separate from the interlacing kernel. It uses positivity to prevent cancellation between the current Euler term and the X lag.

Provide a bridge from this window to the proof-carrying reachable certificate of #1872 when that API lands. Until then, expose the seed/step/extraction theorems directly; do not add a proposition scaffold.

4. Associated Bell specialization

For the normalized k-associated Bell recurrence, use

c q = Nat.choose (q+2*k-1) (k-1).

For k>=1, prove positivity and instantiate the seeded theorem. The mathematical source is the recurrence for partitions whose every block has size at least k:

U (n+1) = X*(U n)' + C(choose n (k-1))*X*U (n-k+1),
A q = U (q+k)/X.

A recurrence-first Lean theorem is enough for this issue; do not introduce a new set-partition type in an application module. If a canonical combinatorial model is added, coordinate it with #1256 and prove the recurrence separately.

State the resulting uniform theorem: every normalized row is PF, every k+1 consecutive normalized rows form a directed interlacing clique, and the degree is q/k.

This theorem concerns the all-large associated Bell family. It does not settle #1773, where smaller blocks are allowed and only blocks of size at least k receive the variable weight.

5. Downstream migrations and regressions

At sqrt-of-2/real-rooted-oeis-proofs commit 4da79256c504843df1f8d2ddcfbe7522d9186657:

  1. In A059022, normalize the displayed coefficient to choose(q+5,2) and instantiate k=3.
  2. In A059023, normalize the displayed coefficient to choose(q+7,3) and instantiate k=4.
  3. Retain public downstream declarations such as A059022H_window and A059023H_window as short wrappers if callers use them.
  4. Replace the duplicated half-step, root-sequence, and chain machinery only after the generic theorem is available at the pinned RealRooted revision.
  5. Verify the generated _splits declarations and any retained interlacing declarations by focused and default builds plus #print axioms.

Add theorem-level regressions for:

  • a symbolic arbitrary positive weight sequence c;
  • the even and odd slide separately;
  • the constant initial window followed by 1+c_0 X;
  • extraction of an edge spanning the full row lag k;
  • k=3 and k=4 coefficient normalizations;
  • rejection of c_q<0 as unsupported by this theorem.

Acceptance

Completion requires the checked abstract window theorem, seeded recurrence corollary, exact degree/leading-sign theorem, associated-Bell specialization, A059022/A059023 bridges, downstream migrations, and axiom-clean audits of the migrated declarations.

No sorry, added axiom, assumed window proposition, finite root sampling, or universal companion-preserver claim counts as completion.

Activity

  1. added
    formalizationPlanned formalization of a specific statement
    weyl-programDifferential BKW / Weyl-matrix interlacing program (#601)
    on Oct 25, 2026
  2. PerAlexandersson commented on Nov 14, 2026

    @PerAlexandersson
    OwnerAuthor

    Completed. The library part (associated-Bell specialization associatedBell_halfStepRows / associatedBell_rows and the lag-three/four weight identities) is in #2571, on top of the existing abstract half-step window theorem. The downstream A059022/A059023 migrations to thin recurrence bridges were merged in the OEIS proofs repository (batch 7), with axiom audits unchanged.

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

Metadata

Metadata

Assignees

No one assigned

    Labels

    formalizationPlanned formalization of a specific statementweyl-programDifferential BKW / Weyl-matrix interlacing program (#601)

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions