Here is a sequence of polynoms – (presumably) counting N-tuples of ANTI-commuting 2×2 matrices over $F_p, p>2$. (That is just the case of 2×2 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 2×2 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.
Best Answer
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.