0
$\begingroup$

Consider some finite set $S$ (can be matrices over $F_p$), consider some symmetric relation $F(s1,s2)$ which values are True or False (for example - matrices (anti)commutate or not).

Question 1: can the count of n-tuples $(s1,s2,...,s_n): \forall i,j: F(s_i,s_j)=True$ be expressed somehow in terms of $F$ ?

Question 2: Is the generating function over $n$ always rational ? (Motivated by Peter Taylor's finding here for 2x2 anti-commuting matrices.) Or some other types of recurrent relations over $n$ might be true ?

Generalizations: one may ask similar question for k-plet relations $F(s_1,s_2,...,s_k)$, also to cover q-commuting case it would be desirable to relax symmetricity constraint.

Hopefully the answer may help to explain patterns observed in : MO commuting/Manin tuples, MO anti-commuting tuples, which are all particular cases of Manin matrix counting question.

Improve this question
$\endgroup$
1
  • 2
    $\begingroup$ For fixed $S$ and $F$ there's always a rational generating function over $n$. Consider a finite state machine whose states are subsets of $S$ whose elements are pairwise related, with a transition from a subset $\sigma_i$ to any superset which adds one element, and a loop from $\sigma_i$ to itself for each reflexive element it contains. Then the g.f. counts Markov chains in this FSM, so is rational. $\endgroup$
    – Peter Taylor
    Commented Apr 26 at 7:59

0

Reset to default

You must log in to answer this question.