Polynomiality conjecture for low-degree coefficients of colored-triangle polynomials

Proof of both the all-order polynomiality statement and all four exact formulas. Put

$$P_n(q)=2^{1-n}T_2(n;q)=\sum_{r\ge0}a_r(n)q^r.$$

The source's free, energy-preserving interface involutions identify $P_n(q)$ with the generating polynomial of canonical quotient triangles. Their unique ordered direct-sum decomposition gives

$$F(z,q):=\sum_{n\ge0}P_n(q)z^n =\frac1{1-C(z,q)}, \tag{1}$$

where $C$ counts nonempty irreducible canonical triangles.

Let $b_j$ be the $j$-th bottom color and $A_j$ its active set. Then

$$|A_j|=j,\qquad e_j=\#\{c\in A_j:c>b_j\}, \qquad E=\sum_je_j.$$

Set

$$D=\sum_j(j-b_j)_+ =\sum_j(b_j-j)_+ =\sum_i h_i, \quad h_i=\#\{j\le i:b_j>i\}, \quad r_j=\#(A_j\setminus[j]).$$

Then

$$D\le E,\qquad r_j\le e_j+(b_j-j)_+,\qquad \sum_jr_j\le2E.$$

If $h_i=r_i=r_{i+1}=0$, the canonical interface is an ordered direct-sum cut. Therefore every noncut is counted by a positive $h_i$ or is adjacent to a positive $r_j$, giving

$$\#\{\text{noncuts}\} \le D+2\sum_jr_j \le5E.$$

An irreducible size-$s$ configuration has $s-1$ noncuts. Thus

$$C(z,q)=z+\sum_{r\ge1}c_r(z)q^r, \qquad c_r(z)\in\mathbb Z[z], \qquad \deg c_r\le5r+1. \tag{2}$$

This proves a genuine finite cutoff, rather than an extrapolation from observed data.

For completeness, all irreducibles through energy five can now be enumerated by an exact finite-state transfer. A state before bottom position $j$ consists of $(U,A,e,d)$, where $U$ is the used bottom-color set, $A$ the active set, $e$ accumulated energy, and $d$ accumulated positive displacement. Choose $b\in A\setminus U$ and set

$$U'=U\cup\{b\}, \qquad e'=e+\#\{c\in A:c>b\}, \qquad d'=d+(j-b)_+.$$

For $j<n$, choose an increasing interface pair $u<v$ outside $A^-=A\setminus\{b\}$ and set

$$A'=A^-\cup\{u,v\}.$$

Reject precisely those interfaces satisfying

$$U'=[j], \qquad A^-\cup\{u\}=[j],$$

since these and only these are direct-sum cuts. Discard $e'>5$ or $d'>5$, which is rigorously safe because $D\le E$. By (2), only sizes $n\le26$ can contribute.

The complete resulting coefficient table, with columns $[q]C,[q^2]C,[q^3]C,[q^4]C,[q^5]C$, is

$$\begin{array}{c|rrrrr} n&1&2&3&4&5\\hline 2&1&0&0&0&0\\ 3&3&5&1&0&0\\ 4&1&36&50&47&10\\ 5&0&36&414&923&1152\\ 6&0&10&710&5171&17096\\ 7&0&1&433&11436&74462\\ 8&0&0&120&11115&174057\\ 9&0&0&17&5414&224681\\ 10&0&0&1&1516&161330\\ 11&0&0&0&253&69927\\ 12&0&0&0&24&19596\\ 13&0&0&0&1&3628\\ 14&0&0&0&0&435\\ 15&0&0&0&0&31\\ 16&0&0&0&0&1\\ 17\le n\le26&0&0&0&0&0. \end{array} \tag{3}$$

Vanishing for all larger sizes follows from the proved bound (2).

Write

$$[q^k]F(z,q)=\frac{N_k(z)}{(1-z)^{k+1}}, \qquad N_0(z)=1.$$

Equation (1) yields the exact integer-polynomial recurrence

$$N_k(z)= \sum_{j=1}^k c_j(z)N_{k-j}(z)(1-z)^{j-1}. \tag{4}$$

Using the complete table (3),

$$\begin{aligned} N_2&=5z^3+32z^4+6z^5-15z^6-3z^7,\\ N_3&=z^3+48z^4+325z^5+25z^6-368z^7 +4z^8+81z^9+9z^{10},\\ N_4&=47z^4+784z^5+2670z^6-110z^7-5608z^8 +757z^9+2928z^{10}-456z^{11}-360z^{12}-27z^{13},\\ N_5&=10z^4+1112z^5+12652z^6+15341z^7-9578z^8 -56080z^9+6607z^{10}+64728z^{11}\\ &\quad-21569z^{12}-15849z^{13} +4239z^{14}+1431z^{15}+81z^{16}. \end{aligned}$$

Since $\deg N_k=3k+1$, coefficient extraction gives, for $n\ge2k+1$,

$$k!a_k(n) = \sum_s[z^s]N_k(z) \prod_{j=1}^k(n-s+j).$$

Expanding gives exactly

$$\boxed{ \begin{aligned} a_2(n)&=\frac{25n^2-49n-116}{2},&&n\ge5,\\ a_3(n)&=\frac{125n^3+15n^2-3104n+1980}{6},&&n\ge7,\\ a_4(n)&=\frac{625n^4+2650n^3-36877n^2-31390n+244728}{24}, &&n\ge9,\\ a_5(n)&=\frac{3125n^5+32500n^4-290925n^3-1585240n^2 +7120060n+5588400}{120}, &&n\ge11. \end{aligned} }$$

Each threshold is sharp: at $n=4,6,8,10$, respectively, the actual values are $47,1825,64622,2207081$, whereas the extended polynomials give $44,1816,64595,2207000$.

Finally, (2) and (4) prove that every fixed $a_k(n)$ is eventually polynomial of degree at most $k$. Source Proposition 3.5 gives $c_1(z)=z^2+3z^3+z^4$; the maximal pole in (1) therefore has numerator value

$$N_k(1)=c_1(1)^k=5^k\ne0.$$

Hence its degree is exactly $k$, with leading coefficient $5^k/k!$, for every $k\ge0$. This proves the complete conjecture, including all four separate formulas and their exact onset thresholds.

Source: Blitvić and Petrov, Colored interlacing triangles and Genocchi medians, Conjecture 4.2, https://arxiv.org/abs/2602.04390.