Here's a variation of a question I was given during a research internship.

Some Definitions:

Definition 1: Let $S$ be a semigroup. For any $a, b\in S$, define Green's $\mathcal{L}$-relation by $a\mathcal{L}b$ if and only if $S^1a=S^1b$ and define Green's $\mathcal{R}$-relation by $a\mathcal{R}b$ if and only if $aS^1=bS^1$, where $S^1$ is $S$ with a one adjoined if necessary. Then Green's $\mathcal{D}$-relation is given by $a\mathcal{D}b$ if and only if $a(\mathcal{L}\circ\mathcal{R})b$ (which is equivalent to $a(\mathcal{R}\circ\mathcal{L})b$); that is, there exists a $c\in S$ such that $a\mathcal{L}c\mathcal{R}b$

Definition 2: The rank of a matrix is the number of linearly independent columns it has.

The Question:

Let $S=M_n(\mathbb{Z}_2)$. Let $D^{(n)}_2$ be the matrices in the rank $2$ $\mathcal{D}$-class of $S$. Find

$$N_n=\left\lvert\left\{\left.\begin{array} \, e & \mathcal{L} & f \\ \mathcal{R} & \, & \mathcal{R} \\ h & \mathcal{L} & g \end{array}\right\vert e, f, g, h\in E\left(D^{(n)}_2\right)\right\}\right\rvert;$$ that is, find $N_n$, the number of quadruples $(e, f, g,h)\in E\left(D_2^{(n)}\right)^4$ such that $e\mathcal{L}f\mathcal{R}g\mathcal{L}h\mathcal{R}e$.

Here $E(T)$ is the set of idempotents of the semigroup $T$.


I did most of the cases when $n=4$ and $n=6$ using the programming language GAP. For the $6\times 6$ case, I sorted matrices of the $D^{(6)}_2$ into certain types (that I can't produce from memory as my notes are missing) then had GAP do an iterated procedure to find $N_6$.

  • $\begingroup$ What do you call "the 𝒟-class of $S$"? The semigroup $S$ has several $\cal D$-classes. $\endgroup$
    – J.-E. Pin
    Mar 26 '17 at 10:26
  • $\begingroup$ @J.-E.Pin I'm not sure. The $\mathcal{D}$-class of matrices of rank $2$ perhaps. $\endgroup$
    – Shaun
    Mar 26 '17 at 10:49
  • 1
    $\begingroup$ I think the question could be better formulated. First of all, someone may have (hopefully wrong) an impression that you were given a question during your internship and now you're soliciting help on this site. If you have something different in mind, please make it more clear. Also, are you interested in trying larger $n$ with GAP, or this is not a question about GAP? How to read the formula for $N_n$? Why there are empty spaces there? Also, $e$ is not used there. Is there a name for $N_n$? $\endgroup$ Mar 28 '17 at 10:05
  • 1
    $\begingroup$ @AlexanderKonovalov The internship ended a couple of years ago. This is not a question about​ GAP. The formula for $N_n$ is what I'm after. What empty spaces? I have made $e$ clearer. There's no name for $N_n$ I am aware of. $\endgroup$
    – Shaun
    Mar 28 '17 at 10:16
  • 1
    $\begingroup$ I'm looking for the number of quadruples $(e, f, g,h)\in E\left(D_2^{(n)}\right)^4$ such that $e\mathcal{L}f\mathcal{R}g\mathcal{L}h\mathcal{R}e$. $\endgroup$
    – Shaun
    Mar 28 '17 at 10:26

This is not an answer to the question posed, but is also too long to fit into a comment. I believe that the following lines of GAP code compute the value of $N_4$, $N_5$, $N_6$, and $N_7$. This uses the Semigroups and Digraphs packages for GAP:

S := GLM(4, 2); # The monoid of 4x4 matrices over the field with 2 elements
S := GLM(5, 2);
S := GLM(6, 2);
# Find the first (and only) D-class with row/column rank equal to 2.
D := First(DClasses(S), x -> RowRank(Representative(x)) = 2); 

# The following function creates a bipartite graph from the principal
# factor of D, such that there is an edge from vertex i to vertex j if
# there is an idempotent in the intersection of RClasses(D)[i] and
# LClasses(D)[j], and then counts the number of e-squares using that graph. 
NrESquares := function(D)
  local gr, out, m, count, com, i, j;
  gr := RZMSDigraph(PrincipalFactor(D));
  out := OutNeighbors(gr);
  m := NrRClasses(D);
  count := 0;
  for i in [1 .. m - 1] do 
    for j in [i + 1 .. m] do 
      com := Intersection(out[i], out[j]);
      if Size(com) >= 2 then
        count := count + Binomial(Size(com), 2);
    Print("at ", i, " of ", m, ", found ", count, " so far\n");
  return count;

According to which $N_4 = 13020$, $N_5 = 4010160$, $N_6 = 1069306560$, and $N_7 = 275635858176$. On my laptop, finding $N_4$ took about 1 second, $N_5$ about 10 seconds, $N_6$ about 3 minutes, and $N_7$ about an hour.

The majority of the computation is finding the PrincipalFactor, which uses a method which works for any (finite) semigroup in GAP. A more specialist method for counting E-squares might be able to do it more quickly.

  • $\begingroup$ No OEIS sequence with $\dots, 13020,4010160, \dots$ in it. $\endgroup$ Apr 10 '17 at 9:38
  • $\begingroup$ Yup I noticed that too $\endgroup$ Apr 10 '17 at 9:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.