# Computational complexity of sizes and number of orbits of a group acting on a set

I'm interested in the relation between the computational complexity of counting orbits and counting elements in orbits for groups acting on sets. More formally:

Assume that $$X_n$$ is a infinite sequence of finite sets index by $$n\in\mathbb{N}$$. Assume that $$G$$ is a group with a finite set of generators. Furthermore assume that a group action of $$G$$ is defined on each set $$X_n$$ and that this action can be efficiently computed given an element of $$G$$ and an element of $$X$$.

Consider the following two problems:

Problem 1 (counting orbits): Input: $$n$$

Given $$n$$, decide the number of orbits of $$G$$ acting on $$X_n$$, i.e. compute the size $$|X_n/G|=|\{\{g\cdot x:g\in G\}:x\in X_n\}|$$.

Problem 2 (size of orbit): Input: $$x\in X_n$$

Given $$x\in X_n$$, decide the number of elements in the orbit of $$G$$ acting on $$X_n$$ containing x, i.e. compute the size $$|\{g\cdot x:g\in G\}|$$.

Does $$\#P$$-Completeness of Problem 2 imply $$\#P$$-Completeness/Hardness of Problem 1?

Note that $$\#P$$-Completeness of Problem 2 implies that the size of $$X_n$$ must scale super-polynomially with $$n$$.

Note: I've asked a similar question on StackExchange/Mathematics, however after two weeks and only an unrelated answer I thought I'd also ask the same question here.

• First you need to specify what you mean by “given a group action”. Oct 26, 2018 at 12:58
• @ChrisGodsil If I would write "for a fixed group action.." would that be clearer or do you mean to specify in what form the group action is represented? What exactly are you looking for? For example I assume that the action of a group element on an element of the set can be efficiently computed. Oct 26, 2018 at 13:59
• If you goiNg to discuss complexity, we need to know the size of the input. Oct 26, 2018 at 15:51
• @ChrisGodsil I've re-written the question, I hope it's more clear now. Oct 26, 2018 at 16:26
• The question assumes nothing about the cardinality of $X_n$. Without some such assumption Problem~1 can't be solved algorithmically even when $G$ is the trivial group. A comment on Keith Kearnes's answer suggests that maybe $X_n$ was intended to have cardinality $n$, but the actual question mentions super-polynomial size. So I'm voting to close as unclear. Oct 26, 2018 at 20:49

Since group actions on set can be quite wild (little restrictions on compatibility) I am not too aware of any relation or even chance of finding such a reltaion, however, if you have something like a free action or something similar, this should considerably help to actually make your problems equivalent (since for example for a free action all orbits are in bijection). I hope that helps!

[Too long for a comment. Not a definitive answer, but maybe as close as we're likely to get.]

I'm assuming here, since you talk about $$X_n$$ being potentially exponentially large, that we may think of $$X_n$$ as being a subset of binary strings whose length is at most polynomial in $$n$$, and that the action of each generator of $$G$$ is efficiently computable in $$n$$, given such a binary string. (Probably the use of binary strings isn't key, but it seems to be consistent with your intention, and to clear up some of the questions in the comments.)

First, an example: Graph Isomorphism. $$X_n$$ is the set of $$n$$-vertex graphs. It's more natural in this setting to allow the group $$G_n$$ to vary with $$n$$, and to be $$S_n$$, but the way you've set it up I suppose I'd say $$G=F_2$$ is the free group on 2 generators, and the action of $$G$$ on $$X_n$$ is by permuting the $$n$$ vertices. (This is an action of $$F_2$$ since $$S_n$$ is generated by 2 elements.) Then computing orbit size is equivalent to computing $$|Aut(x)|$$, which - by a standard result - is poly-time equivalent to computing Graph Isomorphism. By Babai's result, this can be done in $$n^{O(\log n)^2}$$ time. On the other hand, exactly counting the number of isomorphism classes seems to be exponentially harder, though this is an interesting open question. Now, in this case, computing the orbit size seems to not be #P-hard, and it's unclear whether counting the number of graphs is (but that also seems a bit unlikely), so this example doesn't get at your question about #P.

This situation - computing orbit size seems easier than counting orbits - seems typical for most natural isomorphism problems I'm aware of (graph, group, finite ring, tensors over finite fields, algebras, etc.). This might suggest a positive answer to your question about #P-completeness, except that also for most natural isomorphism problems I'm aware of, neither orbit size nor counting orbits seems to be #P-complete.

More generally, I'm don't think I know of even a single #P-complete problem whose input is just one number $$n$$. This is related to some of the difficulty in answering Kalai's question about computing the number of isomorphism classes of graphs (see the comments there). You can start to see the difficulty if you think about trying to reduce #3SAT to a problem whose sole input is an integer $$n$$.

• Hi @Joshua! Thanks for your comments! One of the problems I was considering was also a graph problem, however in this case equivalence is under the action of "local complementation". In arxiv.org/abs/1907.08024 we showed that computing the size of such orbits is #P-Complete, however it is unclear how hard it is to count the number of orbits. I agree with you that since the problem only has an integer as input, it might be unlikely that this would also be #P-Complete. Jan 22, 2020 at 10:40

I assume that you are given a finite set $$X=\{x_1,\ldots,x_m\}$$ and a finite set of generators for $$G$$, say $$g_1, \ldots, g_n$$, which are permutations of $$X$$.

Then, for every $$i$$ and $$j$$, imagine a directed edge from $$x_i$$ to $$g_j\cdot x_i$$. This constructs a directed graph from the data. The orbits are the connected components. The size of this graph is quadratic in terms of the input. Either breadth-first search or depth-first search provides a linear time algorithm for finding these connected components. Not sure what assumptions you need to begin with to get close to $$\# P$$-complete. Do you have in mind some formulation of this problem where $$X$$ is infinite?

• The size of the orbits can be exponentially large in the input of the problem. So even if finding the orbits can exponentially long time, deciding their size can still be in $P$. No $X$ is finite but exponentially large in the input of the problem. $X$ can for example be all graphs on a fixed number of vertices or all words of a certain length with entries from a finite alphabet. Oct 26, 2018 at 14:04
• What is the input? Oct 26, 2018 at 14:06
• Sorry for being unclear. In the case of graphs, the input is the number of vertices. Oct 26, 2018 at 14:20
• I mean: what is the input to your original problem about groups acting on sets? Is $X$ part of the input? If so, then $X$ cannot be exponentially large in terms of the input (it is part of the input). So what is the input? Oct 26, 2018 at 15:00
• $X$ is not part of the input. For the problem counting the number of orbits the input is simply the number of vertices $n$ and $X$ is then the graphs on $n$ vertices. For deciding the size of an orbit the input is a graph (element of $X$). I can rewrite the question for the case where $X$ are graphs if that's clearer. Oct 26, 2018 at 15:52