Guess the next polynoms in the sequence (MO vs. AI :), count anticommuting $F_p$-matrices, P. Hrubeš conjecture

Question

Here is a sequence of polynoms - (presumably) counting N-tuples of ANTI-commuting 2x2 matrices over $F_p, p>2$. (That is just the case of 2x2 matrices, and (surprisingly) it is not so easy to see a pattern ! Compare to commuting matrices where pattern is simple - see MO).

Question: Is there any pattern in the polynom sequence below? What can be the next polynoms ? (Any guess/compute/suggest is highly welcome.)

• $p^{5}+3p^{4}-2p^{3}-2p^{2}+p$ : 2-tuples
• $p^{6}+3p^{5}+3p^{4}-6p^{3}-3p^{2}+3p$ : 3-tuples
• $8p^{6}-5p^{5}+3p^{4}-2p^{3}-10p^{2}+7p$ : 4-tuples
• $5p^{7}+11p^{6}-24p^{5}+15p^{4}+5p^{3}-25p^{2}+14p$ : 5-tuples
• $6p^{8}+p^{7}+15p^{6}-45p^{5}+31p^{4}+19p^{3}-51p^{2}+25p$ : 6-tuples
• $7p^{9}+p^{8}-5p^{7}+20p^{6}-14p^{5}-34p^{4}-29p^{3}+14p^{2}+41p$ : 7-tuples
• $8p^{10}+p^{9}-8p^{8}+16p^{7}-30p^{6}+35p^{5}+3p^{4}-10p^{3}+28p^{2}-42p$ : 8-tuples
• Unclear, except $f(1)=f(-1)=1, f(3)=1517649, f(5)=434329585$ : 9-tuples
• Unclear, except $f(1)=f(-1)=1, f(3)=4990113, f(5)=2403378145$ : 10-tuples
• Unclear, except $f(1)=f(-1)=1, f(3)=21327762$ : 11-tuples

(All polynoms satisfy $f(1)=f(-1)=1$, condition $f(1)=1$ is easy to explain, while reason for $f(-1)=1$ - unclear.) Roots are plotted here.

Fun: Mathoverflow vs AI (0:0). Here I tried to get the answer with the top performing AI language model DeepSeekMath https://www.kaggle.com/code/alexandervc/spin-off-real-math-problem hopefully MO can be better :)

---

Context 1: Surprisingly anticommuting matrices appear e.g. in Noga Alon, Kai Zheng paper on Cayley graphs $(Z/2)^d$ which is devoted to the generalization of the breakthrough result by Hao Huang resolving the Sensitivity Conjecture in graph theory. (As Scott Aaronson writes Huang's proof "comes from the book".) They utilize a result of P.Hrubeš that the maximum possible number of complex invertible anticommuting N by N matrices is $2log_2(N) +1$. So in some sense it is not so easy to find big sets of anticommuting matrices, more precisely you cannot do that when they are invertible, and even more strongly we can expect that big set of anti-commuting matrices should be "quite far" from invertibility. There is the following conjecture by P. Hrubeš which is quantifying that "quite far":

Conjecture (P.Hrubeš): $\sum rank(M_i^2) ≤ O(nlog(n))$ for any set of $n\times n$ anticommuting complex matrices.

Possible approach: One might try to think of the following strategy towards such kind of result. The main problem having big set of anti-commuting matrices - that at certain stage you will need to require it is anti-commuting with itself (or near itself). But $AA+AA=0$ implies $A^2=0$ (p>2). Thus we arrive to the Grassman algebra: anticommuting AND $M_i^2=0$ - but that should not be difficult to count such matrices over $F_p$ - it should follow similar pattern as for commuting matrice (see MO) - at least at 2x2 case the answer seems to be $p^{n+1}+p^{n}-p$ which is only one degree less than the pattern seen from the polynoms above $np^{n+2}+...$. The conjecture is trivially true for Grassman algebra - just all ranks are zeros. If we would be able to find deformation from the Grassman matrix variety to the anticommuting variety - such that we would be able to control the ranks - we can hope to the prove the conjecture.

Context 2: Counting anti-commuting matrices is a particular case of counting q-commuting matrices (q=-1) and which is particular case counting q-Manin matrix variety (just take a rectangular Manin matrices of shape (n,1) i.e. only one column). Optimistic hope is that for all q (and qp/super/other analogs) counting will be given by polynomials and there will be nice generating functions over matrix sizes $n$ - see results by Yifeng Huang and Anton Mellit MO post for pairs of matrices.

Thanks to MO: The polynomials above were computed with the help of Peter Taylor code appeared in the mathoverflow answer on related question. (My intention was to ask that question right after the question above (2.5 years ago), but looking on these strange polynoms it made me thought that actually counting is not given by polynomials, but now after some more computations I have more optimism).

PS

One may see that the polynoms for 2,3,4 tuples are different from the the subsequent. It might be related to the following there are invertible anti-commuting 2,3 tuples, but there are no such 4-tuples.

Answer 1

It's not entirely clear to me how much data your guesses are based on, so I present a table with calculated data and guessed polynomials based on that data and the assumption that $f(1) = f(-1) = 1$.

$$\begin{array}{c|rrrrr|l} \textrm{Dim. tuple} & f(3) & f(5) & f(7) & f(11) & f(13) & \textrm{Guesses for poly} \\ \hline 2 & 417 & 4705 & 23233 & 202081 & 452257 & p^5+3p^4-2p^3-2p^2+p \\ 3 & 1521 & 26065 & 173089 & 2290321 & 6012721 & p^6+3p^5+3p^4-6p^3-3p^2+3p \\ 4 & 4737 & 110785 & 863233 & 13407361 & 36837697 & 8p^6-5p^5+3p^4-2p^3-10p^2+7p \\ 5 & 14289 & 496945 & 5045089 & 113281201 & 358361809 & 5p^7+11p^6-24p^5+15p^4+5p^3-25p^2+14p \\ 6 & 44193 & 2536225 & 36499393 & 1325439841 & 5013745633 & 6p^8+p^7+15p^6-45p^5+31p^4+19p^3-51p^2+25p \\ 7 & 141297 & 13916305 & 286149409 & 16652411281 & 74810161777 & 7p^9+p^8-6p^7+35p^6-84p^5+56p^4+42p^3-91p^2+41p \\ 8 & 461313 & 77844865 & 2264277505 & 208434923521 & 1107983409793 & 8p^{10}+p^9-7p^8+56p^6-140p^5+92p^4+76p^3-148p^2+63p \\ 9 & 1517649 & 434329585 & 17762209633 & 2574995104561 & 16182795556369 & 9p^{11}+p^{10}-8p^9+84p^6-216p^5+141p^4+123p^3-225p^2+92p \\ 10 & 4990113 & 2403378145 & 137857285825 & 31436323682401 & 233532753660193 & 10p^{12}+p^{11}-9p^{10}+120p^6-315p^5+205p^4+185p^3-325p^2+129p \\ 11 & 16337649 & 13184998225 & 1059859907617 & 380035371185041 & 3337003295425969 & 11p^{13}+p^{12}-10p^{11}+165p^6-440p^5+286p^4+264p^3-451p^2+175p \\ 12 & 53196417 & 71779197505 & 8083328647681 & 4556998303140481 & 47295113651706817 & 12p^{14}+p^{13}-11p^{12}+220p^6-594p^5+386p^4+362p^3-606p^2+231p \\ 13 & 172253649 & 388185983665 & 61233876460897 & 54269703879276721 & 665719485396037969 & 13p^{15}+p^{14}-12p^{13}+286p^6-780p^5+507p^4+481p^3-793p^2+298p \\ 14 & 554908065 & 2087405364385 & 461191717267393 & 642536718916721761 & 9315832529969607265 & 14p^{16}+p^{15}-13p^{14}+364p^6-1001p^5+651p^4+623p^3-1015p^2+377p \\ 15 & 1779367665 & 11169437347345 & 3456224813772577 & 7569173683597203601 & 129705052899459293425 & 15p^{17}+p^{16}-14p^{15}+455p^6-1260p^5+820p^4+790p^3-1275p^2+469p \\ 16 & 5682292737 & 59509281940225 & 25788754164378625 & 88774878097178250241 & 1797955678015106647297 & 16p^{18}+p^{17}-15p^{16}+560p^6-1560p^5+1016p^4+984p^3-1576p^2+575p \\ 17 & 18079773777 & 315856939150705 & 191687543576763745 & 1037177302481468389681 & 24826693688627052936337 & 17p^{19}+p^{18}-16p^{17}+680p^6-1904p^5+1241p^4+1207p^3-1921p^2+696p \\ 18 & 57338411937 & 1670837408986465 & 1419976657439328961 & 12076140404906226349921 & 341639526320049692470177 & 18p^{20}+p^{19}-17p^{18}+816p^6-2295p^5+1497p^4+1461p^3-2313p^2+833p \\ 19 & 181313000433 & 8811950691455185 & 10486983570616069153 & 140176635307767444258961 & 4686916450943683946548273 & 19p^{21}+p^{20}-18p^{19}+969p^6-2736p^5+1786p^4+1748p^3-2755p^2+987p \\ 20 & 571832888961 & 46348571786564545 & 77238913776173875201 & 1622672987777336274844801 & 64122747776447821674077761 & 20p^{22}+p^{21}-19p^{20}+1140p^6-3230p^5+2110p^4+2070p^3-3250p^2+1159p \\ 21 & 1799181037521 & 243186950694322225 & 567482597908716083041 & 18737432858861663162635441 & 875102561978161296050485201 & 21p^{23}+p^{22}-20p^{21}+1330p^6-3780p^5+2471p^4+2429p^3-3801p^2+1350p \\ \end{array}$$

Note that we disagree on data for 11-tuples, and guessed polys from 7-tuples.

We appear to have the recurrence $$f_n(p) = (2p+4)f_{n-1}(p) - (p^2 +8p + 6)f_{n-2}(p) + (4p^2 + 12p + 4)f_{n-3}(p) - (6p^2 + 8p + 1)f_{n-4}(p) + (4p^2 + 2p)f_{n-5}(p) -p^2 f_{n-6}(p)$$

Source code used to generate the data.

Answer 2

It is possible to calculate the general formula for the polynomials $f_n$.

Note that:

1. If $AB+BA=0$ and $B\neq 0$ then either $0$ is an eigenvalue of $A$ or $\operatorname{tr} A=0$.
2. If $A\neq 0$ has nonzero trace and an eigenvalue equals to $0$, then it is conjugate to $\begin{pmatrix}a&0\\0&0\end{pmatrix}$. If $B\neq 0$ anticommutes with such $A$ then under the same conjugation $B$ would be of the form $\begin{pmatrix}0&0\\0&b\end{pmatrix}$. The only matrix anticommuting with both $A$ and $B$ is the zero matrix
3. If $\operatorname{tr}A = \operatorname{tr}B=0$, then $A,B$ anticommutes if and only if $\operatorname{tr}(AB)=0$. On the subspace of 2x2 matrices with zero trace, the bilinear form $A,B\mapsto\operatorname{tr}(AB)$ can be diagonalized to $(2, 2, -2)$. It has $p+1$ isotropic lines and no totally isotropic planes.

Therefore, each n-tuple of anticommuting 2x2 matrices, after removing occurances of the zero matrix, is exactly one of the following types:

1. No nonzero matrices. Number of n-tuples: $1$.
2. Exactly one nonzero matrix. Number of n-tuples: $n(p^4-1)$.
3. Two anticommuting nonzero matrices, each with nonzero traces. Number of n-tuples: $\binom n2 (p+1)p(p-1)^2$.
4. $k$ nonzero matrices with trace $0$, which anticommutes and nonisotropic according to the bilinear form above, for $k=2,3$. Number of n-tuples:
   • for $k=2$: $\binom n2 p(p-1)^2(p^2-1)$
   • for $k=3$: $\binom n3 p(p-1)^3(p^2-1)$
5. $k$ nonzero scalar multiples of the same isotropic matrix with trace $0$, for $k\geq 2$. Number of n-tuples: $\binom nk (p+1)(p-1)^k$
6. $k-1$ nonzero scalar multiples of the same isotropic matrix with trace $0$, and another nonisotropic trace-$0$ matrix anticommuting with the previous one, for $k\geq 2$. Number of n-tuples: $\binom nk k (p+1)(p-1)^{k-1}(p^2-p)$

Summing it all, we get \begin{multline} f_n(p) = 1 + n(p^4-1) + \binom n2 (p+1)p(p-1)^2 + \binom n2 p(p-1)^2(p^2-1) + \binom n3 p(p-1)^3(p^2-1) + \sum_{k=2}^n \binom nk (p+1)(p-1)^k + \sum_{k=2}^n \binom nk k (p+1)(p-1)^{k-1}(p^2-p) =\\= 1 + n(p^4-1) + \binom n2 (p+1)p(p-1)^2 + \binom n2 p(p-1)^2(p^2-1) + \binom n3 p(p-1)^3(p^2-1) +(p+1)\left(p^n - 1 - n(p-1)\right) +(p+1)(p^2-p)\left( np^{n-1} - n \right) \end{multline}