The 2143 three-column Fibonacci-polynomial conjecture

About 10 years old · traced to 2016

Let $F_s(q)$ be defined by

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

and, for $s\ge 2$ ,

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

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

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

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

References

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).

Posted 1 month ago

Progress summary

Refreshed 1 month ago

Claimed solved

A 2019 paper proves the conjecture for every positive size, while a posted recurrence argument repeats the proof but is not independently verified.

Anderson, Egge, Riehl, Ryan, Steinke, and Vaughan proposed the formula in 2016 for $2143$ -avoiding linear extensions with three columns. They checked it computationally for $s\leq 9$ .

Known results

The 2016 paper states the identity as Conjecture 7.3 and presents it as a $q$ -analogue of the established count $\lvert EN_{s,3}(2143)\rvert=F_{3s-1}$ (Anderson et al., 2016).

2019 proof; posted recurrence attempt

Colin Defant’s Theorem 3.3 proves, for every $s\geq 1$ , $EN_{s,3}(2143)(q)=q^{9\binom{s}{2}}F_s(q^{-1})$ . The proof derives coupled recurrences for two extension classes and normalizes them to the defining recurrence for $F_s$ . A posted attempt gives the same recurrence strategy and claims a complete proof, but it has not been independently verified.

Current status (as of August 2026): The conjecture is settled for every $s\geq 1$ by Defant’s Theorem 3.3; no open case remains.

Sources

ProofThis solution needs a summarySee full solutionHide full solution

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

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

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

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

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

with $E_1=H_1=1$ .

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

E_{s+1} = q^{9s-2}(q^2+q+2)E_s + q^{18s-12}E_{s-1}.

Now normalize by

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

The recurrence becomes

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

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

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

and

E_2=q^6+2q^7+q^8+q^9 =q^9F_2(q^{-1}).

Therefore induction gives

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

or equivalently

EN_{s,3}(2143)(q) = q^{9\binom{s}{2}}F_s(q^{-1})

for every $s\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.