An Interesting but Little-Known Function

A boolean matrix is a matrix whose entries are truth values, usually represented as 1 (true) and 0 (false). We multiply boolean matrices in the same way that we multiply ordinary matrices, except that instead of sum we use the boolean "or" and instead of product we use the boolean "and".

Boolean matrices have a natural interpretation in terms of directed graphs: given a graph G on n vertices, we put a 1 in row i and column j of M if there is a directed edge in G from vertex i to vertex j, and 0 otherwise. Then the boolean matrix power M^e has a 1 in row i and column j if and only if there is a directed path from vertex i to vertex j of length e.

Given an n × n boolean matrix M, a natural question is, what is the largest size s(n) of the semigroup generated by M under boolean matrix multiplication? In other words, how many distinct powers can M have, in the worst case? Believe it or not, this natural quantity has received very little attention in the literature. There is a paper by Markowsky in 1977, and another by Denes, Roush, and Kim in 1983, but that's about it. For small n, it is known that s(n) = n² - 2n + 2, while for larger n, it is known that s(n) is approximately g(n), Landau's function, which counts the maximal order of an element in the symmetric group of order n. It is known that Landau's function is approximately e^{sqrt(n log n)}, so this tells us how s(n) behaves for large n. But to my knowledge nobody knows the exact value, or even small values past n = 20. This might be a nice computational challenge for an undergraduate.