After more calculation, we can generalize the quadratic case to the next higher cubic case, as first discussed here. Code for verifying the induction hypothesis and all base cases follows:

t1 = AbsoluteTiming[
  BasisVectors[m_] := Flatten@Outer[
     Times, X[k - #] & /@ Range[2], Y[k - #] & /@ Range[m]];
  T[n_, j_] := Expand[2 ChebyshevT[n, j/2]];
  T2[n_, j_] := T[n, T[n, j]];
  cx = T[3, j];
  cy = Expand[1 + T[3, T[2, j]]];
  cz = Expand[T2[3, j]];
  rep3 = {
    Z[k] -> cz*Z[k - 1] - Z[k - 2],
    X[k] -> cx*X[k - 1] - X[k - 2],
    Y[k] -> cy*Y[k - 1] - cy*Y[k - 2] + Y[k - 3]
    };]

t2 = AbsoluteTiming[
  v012 = Outer[Coefficient, 
     NestList[Expand[# /. k -> k + 1 /. rep3] &, 
      Expand[( Z[k] - ReplaceAll[Z[k], rep3]) /. 
         Z[x_] :> X[x] Y[x] /. rep3]
      , 2], BasisVectors[3], 1];
  ]

t3 = AbsoluteTiming[Expand@Dot[{1, -cx, 1}, v012]]    (* TEST 1 *)

t4 = AbsoluteTiming[
  rec9 = Expand@
    FoldList[Plus, -1, T[#, T[3, j]] & /@ Range[0, 8]][[2 ;; -1]];
  rec6x = {1, 1, Fold[Plus, -1, T[#, j] & /@ Range[0, 2]],
    Fold[Plus, -1, T[#, j] & /@ Range[0, 3]], 1 + T[3, j],
    Fold[Plus, -1, T[#, j] & /@ Range[0, 5]]};
  rec9x  = 
   Join[rec6x, 
    Expand[Plus @@ Times[Partition[rec6x, 3], {-1, T[3, j]}]]];
  rec9y = Expand[Factor@Expand[rec9/rec9x]];
  ]

t5 = AbsoluteTiming[
  Expand@Outer[Expand@
      Dot[
       BasisVectors[3] /. {X[x_] :> rec9x[[3 (x /. k -> 4) - #1]], 
         Y[x_] :> rec9y[[3 (x /. k -> 4) - #1]]}, #2 ] &, {0, 1, 2}, 
    v012, 1]
  ]    (* TEST 2 *)

In time $t < .1s$, the algorithm verifies all requisite zero sums. At "TEST 1", the return is $6$ zeros, while $9$ zeros are returned at "TEST 2". These zero sums depend mainly on the following cubic invariants:

v012
rec9
rec9x
rec9y

Discussion of base case will follow on seqfans soon.