8
$\begingroup$

From wikipedia we know the smallest permutation representation of the monster group is a permutation group acting on

$$M = 2^4 · 3^7 · 5^3 · 7^4 · 11 · 13^2 · 29 · 41 · 59 · 71 \approx 10^{20} \ \text{elements} $$

This number is less than $2^{67}$ which is the number of binary bit strings of length 67, and therefore the group of invertible $67$-bit binary circuits naturally is isomorphic to $\text{Sym}(2^{67})$ which contains a copy of $\text{Sym}(M)$.

Therefore we should expect there exists a representation of the monster group via 67 bit circuits. Moreover Robert Wilson found a representation of the monster group via exactly TWO generators.

So that means there is an explicit pair of two $67$ bit invertible circuits that generate the monster group.

This doesn't seem like a particularly big object. My macbook that I am typing this on involves FAR FAR FAR larger circuits than this.

I would like to somehow find out WHAT these two circuits are.

Improve this question
$\endgroup$
9
  • 7
    $\begingroup$ I'm not an expert in this area. But the amount of data in writing down a general permutation of 10^20 elements is on the order of 10^40. It is certainly possible to write down some 67-bit circuits which follow simple "programs", but the vast majority of possible permutations cannot be encoded in say fewer than 10^40 bits. You can hope that two permutations from the monster group are highly structured, however, and can be expressed relatively simply. $\endgroup$ Commented Jan 24 at 2:29
  • 7
    $\begingroup$ This is an inefficient way of representing elements of the Monster group. The smallest linear representation of $M$ is a $196882$-dimensional representation over $\mathbb{F}_2$, so we can instead describe $M$ by writing down a pair of $196882 \times 196882$ binary matrices; this requires a "mere" $10$ gigabytes or so. And apparently much more efficient ways of calculating in $M$ are known: sciencedirect.com/science/article/pii/S2772827724000020 $\endgroup$ Commented Jan 24 at 4:59
  • 4
    $\begingroup$ @Jack: sorry, where are you getting $10^{40}$ from? The number of bits required to write down a permutation in $S_n$ scales like $\log n! \approx n \log n$, so it should be closer to $10^{21}$ bits or so. Which is still a lot, of course. $\endgroup$ Commented Jan 24 at 5:06
  • $\begingroup$ @QiaochuYuan You are right, of course. Still too large to be feasible but not quite as bad as I had said. $\endgroup$ Commented Jan 24 at 12:14
  • 2
    $\begingroup$ In my mmgroup package I can represent an element of the Monster group as a bit string of length 255. The group operation on such bit strings has been implemented. $\endgroup$ Commented Jan 27 at 23:42

1 Answer 1

Reset to default
9
$\begingroup$

Short answer

Suitable circuits can probably be constructed within a research project; but they have no practical value for doing computations in the Monster. If you have a circuit for $a$ and a circuit for $b$, then you have to concatenate them to compute $ab$. Reducing the size of the concatenated circuit for computing $ab$ is not easier than the general word shortening problem in the Monster. An educated guess based on some run times on my computer is that such a circuit might have $10^{9 \pm 1}$ gates; but I'm not expert on that subject.

Some background

The objects on which the smallest permutation representation of the Monster acts are usually called $2A$ involutions. In mmgroup I can represent an element of the Monster with $255$ bits, and a $2A$ involution with $91$ bits. The latter representation is not yet fully functional. Downsizing these representations to the minimum possible bit length of $180$ or $67$ bits, respectively, would be a formidable research project. Here one has to enumerate the cosets of several subgroups of a group of structure $2^{1+24}.Co_1$, which is a subgroup of $M$. This could be done e.g. by using a combination of mmgroup and MAGMA. Using this information one might be able to implement C programs for computing in $M$ and for transforming a $2A$ involution with an element of $M$, where $2A$ involutions and elements of $M$ are compressed as much as possible. If such a C program is deterministic, primitive recursive, and not too weird, then conversion to a circuit is essentially a technical problem.

Speeding up computation in the Monster

If the intention of the OP is to speed up computation in the Monster, I recommend to proceed as follows.

  • Study existing implementations of the Monster group and try to improve them.

  • Port the implementation to a vector extension of a 64 bit CPU (such as AVX 512 for x86 or NEON for ARM), or to a graphics card. Here on may use tools like OpenCL or CUDA.

Disclaimer:

I'm the author of the mmgroup package.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thank you for this very comprehensive answer! I guess I wasn't expecting the circuit to be practically useful as much as it being an aesthetically pleasant exercise to see an image which contains the circuit on it. This aesthetic exercise however impractical too if the circuit has $10^9$ gates (it would be similar in size to a literal chip for a computer). I intend to spend some time and understand your mmgroup work. It seems that is the cutting edge in the field for fast calculations. $\endgroup$ Commented Jan 28 at 19:29
  • 1
    $\begingroup$ If you think about using a real-world chip like an FPGA or a gate array then you can certainly do with less gates, because you may have registers, a clock, etc. But then something like Bitcoin mining is definitely more lucrative than computing in the Monster (-; $\endgroup$ Commented Jan 28 at 20:47

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.