3
$\begingroup$

The Monster M is the largest of the finite sporadic groups that arises in the classification of finite, simple groups in mathematics.

M can be realized as a (very large!) set of 196882 X 196882 matrices with nothing more than entries of 1's and 0's, so long as we compute arithmetic as follows:

1+1=0 1+0=1+0=1 1*1=1 0*0=0 1*0=0*1=0

I have two simple questions for the reader. What is the minimum amount of bytes needed to store a single matrix? What is the computational cost (i.e., in FLOPS) of a single matrix multiplication in the most efficient implementation (i.e., taking into account that the entries are binary, not taking into account mathematical properties about the Monster)?

This is a question purely at the computational side of the problem. In other words, treat the matrices as general 196882 x 196882 matrices with binary entries. This is not a question about the Monster. That was just added as motivation.

$\endgroup$
  • $\begingroup$ dont quite understand intention of this question (seems like non sequitur as written) but it could be tcs.se level rephrased in a slightly different way ie if it is actually asking about the complexity of computing the Monster. $\endgroup$ – vzn Oct 29 '13 at 0:54
  • $\begingroup$ ok. the problem is much different to compute the solution without floating point operations ie integers (which is apparently the case). there is also a question of whether the final product matrix is nec 0/1 which also substantially chgs the question. $\endgroup$ – vzn Oct 29 '13 at 2:56
  • $\begingroup$ there is a much more general question here of computing the Monster. mathoverflow might be the place to ask this or possibly cstheory.se.... $\endgroup$ – vzn Oct 29 '13 at 3:09
  • $\begingroup$ Question migrated from Stack Overflow and merged. $\endgroup$ – Shog9 Nov 4 '13 at 5:52
6
$\begingroup$

If you are storing a matrix of 0's and 1's, you could consider using a bitvector for storage. This can pack some fixed number of bits (say, 32 bits or 64 bits) into a single integer, which decreases the required storage by a very large factor. In your case, your matrices need a total of 38,762,521,924 entries, so you'll need at least 4,845,315,241 bytes, or about 4GB, of storage per matrix. Since the Monster group has size about 8 × 1053, though, I seriously doubt you can fit everything into memory.

Another note: the arithmetic you're describing happens to have the plus operator defined as binary XOR and the multiplication operator defined as bitwise AND. Therefore, you could, in a language like C or C++, use the ^ operator to denote addition and the & operator to denote multiplication.

Finally, the complexity of multiplication depends on the matrix multiplication implementation. The naive method takes time O(n3), where n is the dimension of the matrix, but since the matrices are large you could probably use either the Strassen algorithm (time complexity about O(n2.8)) or Coppersmith-Winograd, the latter of which requires about O(n2.37) multiplications. You'd probably have to empirically profile these algorithms to see which is best, since the constant factors hidden here are pretty huge.

Hope this helps!

$\endgroup$
  • $\begingroup$ +1 - it's an awesome answer. My math background isn't bad, but all this is new to me. Well done to both questioner and answer-giver. $\endgroup$ – duffymo Oct 28 '13 at 23:01
  • $\begingroup$ Must've looked over this response at the time. The big-oh specifications were more what I was looking for. $\endgroup$ – Andrew Odesky Jan 4 '14 at 1:03
3
$\begingroup$

The problem amounts to compute the product of two matrices over the finite field $F_2$. This question is discussed in details in the paper Computational linear algebra over fi nite fi elds which also contains an extensive bibliography.

$\endgroup$
  • $\begingroup$ @vzn I apologize for not having read your answer carefully, since you already gave this reference in your answer. $\endgroup$ – J.-E. Pin Oct 29 '13 at 14:17
2
$\begingroup$

This question doesn't seem to have much to do with the structure of the Monster group, but just asks what is the complexity of matrix multiplication. There's a lot written on the complexity of matrix multiplication -- I suggest you do a search. The naive algorithm is $O(n^3)$ (here $n=196882$), but there are other algorithms. Also, if the matrix is sparse, it is possible to do much better.

P.S. The number of bytes to store the matrix in the straightforward way is obvious: $196882^2/8$.

$\endgroup$
  • $\begingroup$ agreed the question is not clearly written as far as tying in the question to the monster group, but it makes more sense if he's spec. asking about the complexity of computing the Monster, which would be quite interesting because of its similarity to binary operations... $\endgroup$ – vzn Oct 29 '13 at 0:53
  • $\begingroup$ @D.W.: Thanks for your reply. Yes, this is not about the Monster. And yes, the straightforward way is obvious. I was wondering if there were other less obvious ways or less obvious data structures that took into account the binary entries and the knowledge that we were only interested in matrix multiplication. The "hard" part about this question to me, or rather the part I don't know, is finding an efficient number of floating point operations to compute products and sums of binary or boolean values. The straightforward answer as regards matrix multiplication is certainly very redundant. $\endgroup$ – Andrew Odesky Oct 29 '13 at 1:18
  • 1
    $\begingroup$ @aentropy Multiplying zero-one matrices doesn't use any floating-point operations at all because there are no floating-point numbers involved. $\endgroup$ – David Richerby Oct 29 '13 at 9:34
  • $\begingroup$ @DavidRicherby Thanks for the clarification $\endgroup$ – Andrew Odesky Oct 29 '13 at 19:26
2
$\begingroup$

as DW answers, algorithms for fast matrix multiplication are highly relevant. however, after edits on the question, it appears that floating point arithmetic is not required to solve the problem, the solution must be integer valued. although possibly "bigNums" (arbitrary precision integers) are required.

here is a survey on Computational linear algebra over finite fields by Dumas/Pernet that is apparently relevant/closely related. there are also papers/research on eg matrix multiplcation over finite fields.

see also Computing in the monster by Norton.

We discuss the feasibility of a general technique for computing in the Fischer–Griess Monster, and provide information on some of its subgroups which illustrates the use of computational techniques in solving a particular problem in this group.

$\endgroup$
  • 2
    $\begingroup$ BigNums are clearly not required to multiply matrices over the finite field of $\{0,1\}$ with operations XOR and AND. $\endgroup$ – David Richerby Oct 29 '13 at 9:55
  • 1
    $\begingroup$ Thanks for the reply and the references. I knew there would be a lot of computational overhead that could be removed by taking into account the finite field we were working in, but wasn't sure what data structures were best to use, though it seems obvious to me now that boolean is the way to go for $F_2$. Norton's paper will especially be interesting to look at. $\endgroup$ – Andrew Odesky Oct 29 '13 at 19:24
  • $\begingroup$ agreed apparently all matrices including resultant matrix are $\{0,1\}$ although havent seen this clearly outlined in a ref. bignums can show up when the addition operation is not the same as "xor" as in this case (didnt notice that thx for clarification). wikipedia $F_2$ $\endgroup$ – vzn Oct 29 '13 at 20:42
  • $\begingroup$ @vzn You don't need a reference: the matrices are zero-one because matrix multiplication is defined wrt XOR and AND, which cannot give answers other than 0 and 1! Also, the matrices form a group under this operation and groups are, by definition, closed. $\endgroup$ – David Richerby Oct 31 '13 at 10:25
2
$\begingroup$

Here is an article, also titled "Computing in the Monster" (pdf) by R. A. Wilson (different than the one by Norton cited in vzn's answer). There is also a follow-up article, "New Computations in the Monster" (pdf). In these papers, the author demonstrates algebraic constructions that allow for explicit computations in the Monster group.

Here's a neat snippet from the first paper (emphasis mine):

The smallest matrix representations of the Monster have dimension 196882 in characteristics 2 and 3, and dimension 196883 in all other characteristics. Thus the smallest matrices which we could conceivably use to generate the Monster would require around 5GB of storage each, and on modern workstations with the best available algorithms it would take several weeks of processor time to multiply two such matrices.

Despite these obvious difficulties, I decided some years ago to attempt an explicit construction of these matrices, with no hope of ever being able to use them for any serious calculation. With the collaboration of Richard Parker, Peter Walsh and Steve Linton, this project was eventually successful. The generating matrices were stored in a compact way, so that all the information and special programs needed would fit onto a single 1.44MB floppy disk.

Clever math, FTW.

$\endgroup$
1
$\begingroup$

To represent most $n\times n$ 0-1 matrices requires $n^2$ bits: this is a simple fact of Kolmogorov complexity. So, without using special properties of the monster group's elements, you're not going to get a more efficient representation than the naive one.

$\endgroup$
  • $\begingroup$ thats for random matrices, but what about the Monster? is there anything that suggests its entries are close to random? or could it be the opposite? that would be a very interesting research question. $\endgroup$ – vzn Oct 31 '13 at 15:22

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.