Sagan–Swanson conjecture

What Lean checks

Written proof of all four stated asymptotic normality assertions using actual means and variances; finite model checks are supplementary.

Status: complete unrefereed proof. Independent analytic, source/model, and root mathematical audits passed. This document concerns Conjecture 7.8, not the separate log-concavity and bottom-heaviness conjectures.

1. Statement and exact probability models

Sagan and Swanson, q-Stirling numbers in type B, European Journal of Combinatorics 118 (2024), 103899, Conjecture 7.8, ask whether the coefficient distributions of all four polynomials below are asymptotically normal whenever n,k→∞n,k\to\infty and k/n→α∈(0,1)k/n\to\alpha\in(0,1):

S[n,k],c[n,k],SB[n,k],cB[n,k].S[n,k],\qquad c[n,k],\qquad S_B[n,k],\qquad c_B[n,k].

For a polynomial P(q)=∑jpjqjP(q)=\sum_j p_jq^j with nonnegative coefficients, its coefficient distribution assigns probability pj/P(1)p_j/P(1) to jj. Asymptotic normality means convergence to the standard normal distribution after centering by the distribution's own mean and dividing by its own standard deviation.

Primary source: published manuscript, printed pages 31–32; arXiv record. The symmetric-function identities used here are the classical type-A identities and Theorem 2.1 in type B:

c[n,k]=en−k([1]q,[2]q,…,[n−1]q),cB[n,k]=en−k([1]q,[3]q,…,[2n−1]q),S[n,k]=hn−k([1]q,[2]q,…,[k]q),SB[n,k]=hn−k([1]q,[3]q,…,[2k+1]q).\begin{aligned} c[n,k]&=e_{n-k}([1]_q,[2]_q,\ldots,[n-1]_q),\\ c_B[n,k]&=e_{n-k}([1]_q,[3]_q,\ldots,[2n-1]_q),\\ S[n,k]&=h_{n-k}([1]_q,[2]_q,\ldots,[k]_q),\\ S_B[n,k]&=h_{n-k}([1]_q,[3]_q,\ldots,[2k+1]_q). \end{aligned}

Here [a]q=1+q+⋯+qa−1[a]_q=1+q+\cdots+q^{a-1}, and eme_m and hmh_m are elementary and complete homogeneous symmetric polynomials. These identities can also be checked directly: the elementary identity follows by adding the last variable, while the complete homogeneous identity uses

hm(x1,…,xL)=hm(x1,…,xL−1)+xLhm−1(x1,…,xL).h_m(x_1,\ldots,x_L)=h_m(x_1,\ldots,x_{L-1})+x_Lh_{m-1}(x_1,\ldots,x_L).

They reproduce the four defining recurrences, with the same initial conditions.

We prove a common theorem that applies to all four expressions. Fix integers d≥1d\ge1 and β\beta with d+β≥1d+\beta\ge1. Let Ln,mnL_n,m_n be integer sequences with Ln≥1L_n\ge1 and mn≥0m_n\ge0, and put

aj=dj+β,1≤j≤Ln,Ln/n→κ>0,mn/n→ρ>0.a_j=dj+\beta,\qquad 1\le j\le L_n,\qquad L_n/n\longrightarrow\kappa>0,\qquad m_n/n\longrightarrow\rho>0.

In the elementary case assume also ρ<κ\rho\lt \kappa. Define

Qn(q)=emn([a1]q,…,[aLn]q)Q_n(q)=e_{m_n}([a_1]_q,\ldots,[a_{L_n}]_q)

in the elementary case, or replace emne_{m_n} by hmnh_{m_n} in the complete homogeneous case.

Theorem. In either case, QnQ_n is nonzero for all sufficiently large nn. Its coefficient distribution, standardized by its actual mean and variance, converges to the standard normal distribution.

For each nn, introduce an auxiliary parameter λn>0\lambda_n>0. In the elementary case let the independent occupation counts KjK_j be Bernoulli, with

Pr(Kj=1)=λnaj1+λnaj.\Pr(K_j=1)=\frac{\lambda_n a_j}{1+\lambda_n a_j}.

In the complete homogeneous case require λnaLn<1\lambda_n a_{L_n}<1 and let

Pr(Kj=r)=(1−λnaj)(λnaj)r,r≥0.\Pr(K_j=r)=(1-\lambda_n a_j)(\lambda_n a_j)^r,\qquad r\ge0.

Independently of the counts and of one another, let Uj,ℓU_{j,\ell} be uniform on {0,…,aj−1}\{0,\ldots,a_j-1\}. Set

Yj=∑ℓ=1KjUj,ℓ,Tn=∑jKj,Yn=∑jYj.Y_j=\sum_{\ell=1}^{K_j}U_{j,\ell},\qquad T_n=\sum_jK_j,\qquad Y_n=\sum_jY_j.

The bivariate probability generating factors are respectively

1+λnz[aj]q1+λnaj,1−λnaj1−λnz[aj]q.\frac{1+\lambda_n z[a_j]_q}{1+\lambda_n a_j}, \qquad \frac{1-\lambda_n a_j}{1-\lambda_n z[a_j]_q}.

Taking the coefficient of zmnz^{m_n} proves the exact identity

𝔼[qYn∣Tn=mn]=Qn(q)Qn(1).\mathbb E[q^{Y_n}\mid T_n=m_n]=\frac{Q_n(q)}{Q_n(1)}.

Thus the auxiliary parameter can be chosen to make conditioning convenient without changing the desired distribution.

2. Saddle parameter and covariance limits

Choose λn\lambda_n uniquely so that 𝔼Tn=mn\mathbb ET_n=m_n. For sufficiently large nn, this is possible: the Bernoulli expectation increases continuously from 0 to LnL_n, while the geometric expectation increases continuously from 0 to infinity as λn\lambda_n approaches 1/aLn1/a_{L_n}.

Write τn=nλn\tau_n=n\lambda_n. Define

ν(w)={w/(1+w)elementary,w/(1−w)complete,v(w)={w/(1+w)2elementary,w/(1−w)2complete.\nu(w)=\begin{cases}w/(1+w)&\text{elementary},\\w/(1-w)&\text{complete},\end{cases} \qquad v(w)=\begin{cases}w/(1+w)^2&\text{elementary},\\w/(1-w)^2&\text{complete}. \end{cases}

There is a unique τ>0\tau>0 satisfying

∫0κν(τdx)dx=ρ.\int_0^\kappa\nu(\tau d x)\,dx=\rho.

In the elementary case the integral increases from 0 to κ\kappa as τ\tau increases from 0 to infinity. In the complete homogeneous case it increases from 0 to infinity on 0<τ<1/(dκ)0\lt \tau<1/(d\kappa); the divergence at the upper endpoint is logarithmic.

Moreover, τn→τ\tau_n\to\tau. To see this without presupposing a saddle-point approximation, choose two fixed parameters on either side of τ\tau, within the relevant domain. Their expectation sums, divided by nn, converge by Riemann sums to integrals lying on opposite sides of ρ\rho. Monotonicity traps τn\tau_n between them for all sufficiently large nn. Arbitrarily close choices give the convergence.

Consequently, in the geometric case all λnaj\lambda_na_j are uniformly bounded above by some constant strictly below 1. On the index interval κn/3≤j≤2κn/3\kappa n/3\le j\le2\kappa n/3, which contains a positive multiple of nn indices, the Bernoulli probabilities or geometric ratios are bounded away from both 0 and 1. The constants may depend on ρ,κ,d,β\rho,\kappa,d,\beta, which are fixed.

For brevity write νx=ν(τdx)\nu_x=\nu(\tau dx) and vx=v(τdx)v_x=v(\tau dx), and define

A=∫0κvxdx,B=d2∫0κxvxdx,D=d2∫0κx2(νx12+vx4)dx.A=\int_0^\kappa v_x\,dx,\qquad B=\frac d2\int_0^\kappa x v_x\,dx,\qquad D=d^2\int_0^\kappa x^2\left(\frac{\nu_x}{12}+\frac{v_x}{4}\right)dx.

Since a uniform variable on {0,…,a−1}\{0,\ldots,a-1\} has mean (a−1)/2(a-1)/2 and variance (a2−1)/12(a^2-1)/12, conditioning on KjK_j gives

Cov(Kj,Yj)=Var(Kj)aj−12,Var(Yj)=𝔼Kjaj2−112+Var(Kj)(aj−1)24.\begin{aligned} \mathop{\mathrm{Cov}}(K_j,Y_j)&=\mathop{\mathrm{Var}}(K_j)\frac{a_j-1}{2},\\ \mathop{\mathrm{Var}}(Y_j)&=\mathbb EK_j\frac{a_j^2-1}{12} +\mathop{\mathrm{Var}}(K_j)\frac{(a_j-1)^2}{4}. \end{aligned}

Riemann sums therefore imply

VarTnn→A,Cov(Tn,Yn)n2→B,VarYnn3→D.\frac{\mathop{\mathrm{Var}}T_n}{n}\to A,\qquad \frac{\mathop{\mathrm{Cov}}(T_n,Y_n)}{n^2}\to B,\qquad \frac{\mathop{\mathrm{Var}}Y_n}{n^3}\to D.

Both AA and the conditional variance constant V=D−B2/AV=D-B^2/A are positive. Cauchy–Schwarz gives

V≥d212∫0κx2νxdx>0.V\ge\frac{d^2}{12}\int_0^\kappa x^2\nu_x\,dx>0.

3. Uniform joint expansion

The centered vectors

(Kj−𝔼Kj,Yj−𝔼Yjn)\left(K_j-\mathbb EK_j,\frac{Y_j-\mathbb EY_j}{n}\right)

have uniformly bounded exponential moments in a fixed neighborhood of the origin. Indeed, aj/na_j/n is uniformly bounded, so 0≤Yj/n≤CKj0\le Y_j/n\le C K_j. Bernoulli counts are bounded. Geometric counts have a common positive exponential-moment radius because their ratios are uniformly bounded below 1. Their means are uniformly bounded as well.

Taylor expansion of the logarithm of each centered characteristic function is consequently uniform through order three near zero. For fixed real s,ws,w, independence and the covariance limits give

𝔼exp(isn(Tn−mn)+iwn3/2(Yn−𝔼Yn))→exp[−12(As2+2Bsw+Dw2)].\begin{aligned} &\mathbb E\exp\left( i\frac{s}{\sqrt n}(T_n-m_n) +i\frac{w}{n^{3/2}}(Y_n-\mathbb EY_n)\right)\\ &\qquad\longrightarrow \exp\left[-\tfrac12(As^2+2Bsw+Dw^2)\right]. \end{aligned}

For completeness, the sum of the remainders is O(n−1/2(|s|+|w|)3)O(n^{-1/2}(|s|+|w|)^3): there are O(n)O(n) summands and each third-order remainder is O(n−3/2(|s|+|w|)3)O(n^{-3/2}(|s|+|w|)^3). No conditional central limit theorem is assumed in this step.

4. Uniform Fourier bound away from the central point

Fix real ww and put η=w/n3/2\eta=w/n^{3/2}. The characteristic function of a uniform mark has the form

𝔼eiηUj,1=Rjeiδj,δj=η(aj−1)/2,\mathbb Ee^{i\eta U_{j,1}}=R_j e^{i\delta_j},\qquad \delta_j=\eta(a_j-1)/2,

where RjR_j is real because the centered uniform distribution is symmetric. Also

1−Cw2/n≤Rj≤1,|δj|≤C|w|/n.1-Cw^2/n\le R_j\le1,\qquad |\delta_j|\le C|w|/\sqrt n.

The lower bound follows from cosx≥1−x2/2\cos x\ge1-x^2/2. In particular Rj≥1/2R_j\ge1/2 for all indices when nn is sufficiently large.

In the elementary case the uncentered joint characteristic factor is

Fj(u,w)=1−pj+pjRjei(u+δj),F_j(u,w)=1-p_j+p_jR_j e^{i(u+\delta_j)},

where pj=Pr(Kj=1)p_j=\Pr(K_j=1). On the middle index interval from Section 2,

|Fj(u,w)|2≤1−2pj(1−pj)Rj(1−cos(u+δj)).|F_j(u,w)|^2 \le1-2p_j(1-p_j)R_j(1-\cos(u+\delta_j)).

In the complete homogeneous case, writing rj=λnajr_j=\lambda_na_j, the corresponding factor is

Fj(u,w)=1−rj1−rjRjei(u+δj).F_j(u,w)=\frac{1-r_j}{1-r_jR_j e^{i(u+\delta_j)}}.

Its squared denominator is at least

(1−rj)2+2rjRj(1−cos(u+δj)).(1-r_j)^2+2r_jR_j(1-\cos(u+\delta_j)).

Thus in either case, on a positive multiple of nn indices,

|Fj(u,w)|≤exp[−cdist(u+δj,2πℤ)2]|F_j(u,w)|\le \exp\bigl[-c\,\mathop{\mathrm{dist}}(u+\delta_j,2\pi\mathbb Z)^2\bigr]

for a fixed c>0c>0. All other factors have modulus at most 1. For u∈[−π,π]u\in[-\pi,\pi], the distance function is 1-Lipschitz and dist(u,2πℤ)=|u|\mathop{\mathrm{dist}}(u,2\pi\mathbb Z)=|u|. Multiplying the bounds gives

∏j|Fj(u,w)|≤exp[−c1n(|u|−C1|w|n)+2].\prod_j|F_j(u,w)| \le \exp\left[-c_1n\left(|u|-\frac{C_1|w|}{\sqrt n}\right)_+^2\right].

Centering the variables changes no moduli. After u=s/nu=s/\sqrt n, this is the integrable bound

exp[−c1(|s|−C1|w|)+2]\exp[-c_1(|s|-C_1|w|)_+^2]

on the whole integration interval, uniformly in nn. This explicitly supplies the aperiodicity and tail estimate needed for the rare conditioning event. Merely applying an unconditional bivariate central limit theorem would not supply it.

5. Conditioning by Fourier inversion

Let μn=𝔼Yn\mu_n=\mathbb EY_n, and define

In(w)=𝔼[eiw(Yn−μn)/n3/2𝟏Tn=mn].I_n(w)=\mathbb E\left[ e^{iw(Y_n-\mu_n)/n^{3/2}}\mathbf1_{T_n=m_n}\right].

Since TnT_n is integer-valued and 𝔼Tn=mn\mathbb ET_n=m_n, Fourier inversion yields

In(w)=12π∫−ππ𝔼exp[iu(Tn−mn)+iw(Yn−μn)/n3/2]du.I_n(w)=\frac1{2\pi}\int_{-\pi}^{\pi} \mathbb E\exp\left[iu(T_n-m_n)+iw(Y_n-\mu_n)/n^{3/2}\right]du.

Substitute u=s/nu=s/\sqrt n and extend the integrand by zero outside its integration interval. Sections 3 and 4 permit dominated convergence:

nIn(w)→12π∫ℝe−(As2+2Bsw+Dw2)/2ds=12πAe−Vw2/2.\begin{aligned} \sqrt n I_n(w) &\longrightarrow\frac1{2\pi}\int_{\mathbb R} e^{-(As^2+2Bsw+Dw^2)/2}\,ds\\ &=\frac1{\sqrt{2\pi A}}e^{-Vw^2/2}. \end{aligned}

In particular,

Pr(Tn=mn)∼12πAn.\Pr(T_n=m_n)\sim\frac1{\sqrt{2\pi A n}}.

Dividing by In(0)I_n(0) and applying the characteristic-function continuity theorem proves

Yn−μnn3/2|{Tn=mn}→d𝒩(0,V).\left.\frac{Y_n-\mu_n}{n^{3/2}}\,\right|\,\{T_n=m_n\} \ \xrightarrow{d}\ \mathcal N(0,V).

The centering here is still unconditional. The next step justifies the centering and scaling required by the conjecture.

6. Actual conditional means and variances

For fixed real tt, set h=t/n3/2h=t/n^{3/2} and tilt the independent variables by ehYne^{hY_n}. Denote the tilted probability by Prh\Pr_h. Then

𝔼[eh(Yn−μn)∣Tn=mn]=e−hμn𝔼ehYnPrh(Tn=mn)Pr(Tn=mn).\mathbb E\left[e^{h(Y_n-\mu_n)}\mid T_n=m_n\right] =e^{-h\mu_n}\mathbb Ee^{hY_n} \frac{\Pr_h(T_n=m_n)}{\Pr(T_n=m_n)}.

The first factor is bounded by eCt2e^{C t^2} uniformly for all sufficiently large nn. This follows from the uniform exponential moments in Section 3: for every centered (Yj−𝔼Yj)/n(Y_j-\mathbb EY_j)/n, the logarithm of its moment generating function is at most Cu2C u^2 for uniformly small real uu. Take u=t/nu=t/\sqrt n and sum over O(n)O(n) indices.

The tilted count laws remain independent. Let

Aj(h)=𝔼ehUj,1=1+O(n−1/2)A_j(h)=\mathbb Ee^{hU_{j,1}}=1+O(n^{-1/2})

uniformly in jj. Bernoulli odds become λnajAj(h)\lambda_na_j A_j(h); geometric ratios become λnajAj(h)\lambda_na_j A_j(h). The latter remain uniformly below 1, and on the same middle interval the tilted probabilities or ratios remain uniformly bounded away from 0 and 1. The usual one-dimensional version of the factor bound from Section 4, now with no mark phase, therefore gives

Prh(Tn=mn)≤12π∫−ππe−cnu2du≤Cn−1/2.\Pr_h(T_n=m_n) \le\frac1{2\pi}\int_{-\pi}^{\pi}e^{-cnu^2}\,du \le Cn^{-1/2}.

No assumption that mnm_n is the tilted mean is needed for this upper bound. Section 5 gives a matching lower-order bound for the untilted denominator. Hence, for every fixed real tt,

supn sufficiently large𝔼[et(Yn−μn)/n3/2∣Tn=mn]<∞.\sup_{n\text{ sufficiently large}} \mathbb E\left[e^{t(Y_n-\mu_n)/n^{3/2}}\mid T_n=m_n\right]\lt \infty.

Use one positive and one negative tt to obtain a uniform exponential moment for the absolute value. All fixed moments are then uniformly integrable. The distributional convergence in Section 5 implies

𝔼[Yn∣Tn=mn]−μnn3/2→0,Var(Yn∣Tn=mn)n3→V>0.\frac{\mathbb E[Y_n\mid T_n=m_n]-\mu_n}{n^{3/2}}\to0, \qquad \frac{\mathop{\mathrm{Var}}(Y_n\mid T_n=m_n)}{n^3}\to V>0.

Centering and rescaling by these actual conditional moments now gives the standard normal limit. This proves the common theorem.

7. All four families and conclusion

Apply the theorem with mn=n−km_n=n-k and the following parameters:

Family Symmetric function LnL_n dd β\beta κ\kappa ρ\rho
c[n,k]c[n,k] elementary n−1n-1 1 0 1 1−α1-\alpha
cB[n,k]c_B[n,k] elementary nn 2 −1 1 1−α1-\alpha
S[n,k]S[n,k] complete homogeneous kk 1 0 α\alpha 1−α1-\alpha
SB[n,k]S_B[n,k] complete homogeneous k+1k+1 2 −1 α\alpha 1−α1-\alpha

Every hypothesis holds for every fixed α∈(0,1)\alpha\in(0,1), including the elementary inequality 0<ρ<κ0\lt \rho\lt \kappa. No rate of convergence of k/nk/n is assumed. The exact probability identity in Section 1 transfers the conditional limit to the coefficient distributions. This proves all four assertions of Sagan–Swanson Conjecture 7.8.

The proof establishes the full conjectured proportional regime. It makes no claim about the boundary regimes k/n→0k/n\to0 or 11, or the distinct log-concavity conjectures. No numerical verification is used as a proof step.