MathDB

The 2143 three-column Fibonacci-polynomial conjecture

From papers

Let Fs(q)F_s(q) be defined by

F0(q)=1,F1(q)=1,F_0(q)=1,\qquad F_1(q)=1,

and, for s≥2s\ge 2,

Fs(q)=(1+q+2q2)Fs−1(q)+q3Fs−2(q).F_s(q)=(1+q+2q^2)F_{s-1}(q)+q^3F_{s-2}(q).

Let ENs,t(σ)(q)EN_{s,t}(\sigma)(q) denote the inversion-generating function for pattern-avoiding linear extensions of the rectangular poset with parameters s,ts,t. The 2143 three-column Fibonacci-polynomial conjecture. For all s≥1s\ge 1,

ENs,3(2143)(q)=q9(s2)Fs(1q).EN_{s,3}(2143)(q)=q^{9\binom{s}{2}}F_s\left(\frac{1}{q}\right).

The claim is presented as a qq-analogue of an established formula and is supported by computations for s≤9s\le 9; it remains open in general.

Progress summary

Solved

The conjecture is proved: a 2019 paper establishes the proposed formula for every positive integer parameter.

The 2016 source proposed the identity ENs,3(2143)(q)=q9(s2)Fs(q−1)EN_{s,3}(2143)(q)=q^{9\binom{s}{2}}F_s(q^{-1}) as Conjecture 7.3, after checking it computationally through s=9s=9.

Known results

The original paper also recorded the unweighted specialization ∣ENs,3(2143)∣=F3s−1\lvert EN_{s,3}(2143)\rvert=F_{3s-1} and established related formulas for other column counts.

2019 proof

Colin Defant’s Theorem 3.3 proves the conjectured identity for all s≥1s\geq1. The argument partitions extensions into five classes, introduces an auxiliary polynomial, and derives recurrences that normalize to the defining recurrence for Fs(q−1)F_s(q^{-1}).

Current status (as of August 2026): The three-column Fibonacci-polynomial conjecture is settled for every s≥1s\geq1 by Defant’s published proof.

Sources
Sources & referencesView supporting material

Primary source

David Anderson, Eric S. Egge, Manda Riehl, Lucas Ryan, Ruth Steinke and Yuriko Vaughan, “Pattern Avoiding Linear Extensions of Rectangular Posets”, arXiv:1605.06825 (2016).

fibonacci-polynomialspattern-avoidanceq-enumeration

Solutions 1

Proof

This conjecture was proved by Colin Defant in Theorem 3.3 of “Proofs of Conjectures about Pattern-Avoiding Linear Extensions”:

https://arxiv.org/abs/1905.02309

Published version:

https://doi.org/10.23638/DMTCS-21-4-16

Here is the recurrence argument. Write

Es(q)=ENs,3(2143)(q).E_s(q)=EN_{s,3}(2143)(q).

Defant introduces Hs(q)H_s(q) as the inversion-generating polynomial for those members of ENs,3(2143)EN_{s,3}(2143) whose second entry is 3s−13s-1. A partition into five forced-prefix classes, followed by deletion of the entries 3s−2,3s−1,3s3s-2,3s-1,3s, gives

Es=q9(s−1)−2(1+q+q2)Es−1+q9(s−1)−3(1+q)Hs−1,E_s = q^{9(s-1)-2}(1+q+q^2)E_{s-1} + q^{9(s-1)-3}(1+q)H_{s-1},

and

Hs=q9(s−1)−1(1+q)Es−1+q9(s−1)−2Hs−1,H_s = q^{9(s-1)-1}(1+q)E_{s-1} + q^{9(s-1)-2}H_{s-1},

with E1=H1=1E_1=H_1=1.

Substituting the second recurrence into the first at index s+1s+1, and then using the first recurrence at index ss to eliminate Hs−1H_{s-1}, gives

Es+1=q9s−2(q2+q+2)Es+q18s−12Es−1.E_{s+1} = q^{9s-2}(q^2+q+2)E_s + q^{18s-12}E_{s-1}.

Now normalize by

Gs(q)=q−9(s2)Es(q).G_s(q)=q^{-9\binom{s}{2}}E_s(q).

The recurrence becomes

Gs+1=(1+q−1+2q−2)Gs+q−3Gs−1.G_{s+1} = (1+q^{-1}+2q^{-2})G_s + q^{-3}G_{s-1}.

This is precisely the defining recurrence for Fs+1(q−1)F_{s+1}(q^{-1}). The initial values agree:

G1=1=F1(q−1),G_1=1=F_1(q^{-1}),

and

E2=q6+2q7+q8+q9=q9F2(q−1).E_2=q^6+2q^7+q^8+q^9 =q^9F_2(q^{-1}).

Therefore induction gives

Gs(q)=Fs(q−1),G_s(q)=F_s(q^{-1}),

or equivalently

ENs,3(2143)(q)=q9(s2)Fs(q−1)EN_{s,3}(2143)(q) = q^{9\binom{s}{2}}F_s(q^{-1})

for every s≥1s\geq1.

This is exactly Conjecture 7.3 of the original source and exactly the statement of MathDB #333178, so the entry should be marked solved.

0 endorsements
Samuel Schlesinger ·