User chris beck - MathOverflow

Does subgroup structure of a finite group characterize isomorphism type?

2010-08-13T09:12:07Z

Question

Suppose there is a bijection between the underlying sets of two finite groups $G, H$, such that every subgroup of $G$ corresponds to a subgroup of $H$, and that every subgroup of $H$ corresponds to a subgroup of $G$. Does this imply that $G, H$ are isomorphic? Note that we do not require the bijection to actually be the isomorphism.

Motivation

The question is interesting to me because I am considering maps of groups which aren't homomorphisms but preserve the subgroup structure in some sense - given a group, we can forget the multiplication operation and look only at the closure operator that maps a subset of $G$ to the subgroup generated by it. If the question is resolved in the affirmative, then the forgetful functor from the usual category $Grp$ to this category won't create any new isomorphisms. (Note that I didn't precisely specify the morphisms this new category -- you could just use the usual definition of a homomorphism, and say that if the mapping commutes with the closure operator, then its a morphism. The definition I actually care about is, a morphism of this category is a mapping such that every closed set in the source object is the preimage of a closed set of the target object. It doesn't make much difference as far as this question is concerned, the isomorphisms of both categories are the same.)

I asked a friend at Mathcamp about this a few weeks ago, he said a bunch of people started thinking about it but got stumped after a while. The consensus seems to have been that it is probably false, but the only counter examples may be very large. I don't really have any good ideas / tools for how to prove it might be true, I mostly wanted to just ask if anyone knew offhand / had good intuition for how to find a finite counterexample.

Thanks,

Chris

Answer by Chris Beck for A polynomial-time algorithm for deciding whether a language has a polynomial time algorithm

2010-08-14T10:00:18Z

For any NP-complete problem, search and decision are polynomially related to each other.

If we can find solutions in polynomial time then surely we can decide if a solution exists in polynomial time.

On the other hand, using self reducibility of SAT, we can show that the search problem can be solved in polynomial time using an oracle to the decision version of SAT. Here's the technique:

Suppose I am given formula F, a SAT instance on n variables, and an oracle to decide satisfiability. To solve the search problem, we show how to extend any particular partial solution by fixing a value for one more variable. Then we just start with the empty assignment and repeat this process n times.

Given F, first use Oracle to decide if F has a solution, and if it doesn't, then report Fail. Assuming that it does, we will now find a solution. Take the first variable of F, call it X_1 (any arbitrary variable will do), and plug in True for it, simplifying F accordingly. Then take this resulting formula and give it to the SAT oracle. If by hypothesizing that X_1 = True, we have now made it so that there is no solution to F, then we know that any solution will have X_1 = False. If the oracle said that there are still solutions when X_1 = True, then we retain this partial assignment and proceed. Whatever value we decided on for X_1, we plug that into F and simplify, then repeat for X_2 ... X_n. At the end we must have found a full solution.

This property is called self-reducibility of SAT -- the point is that SAT on instances of length n can be solved in polynomial time with oracle access to SAT on instances of length n-1. Clearly any other NP-complete problem has a similar self-reduction - for instance with HAM CYCLE, I could take a vertex with more than 2 edges, and then make smaller graphs by deleting one of its edges. Polynomially many graphs result this way, and each is smaller then the initial graph. If one of them has a HAM CYCLE, I can just focus on that smaller graph and start deleting edges from it... eventually, I will be left with one massive Hamiltonian cycle. If none of them has a HAM CYCLE, then I know the original graph didn't have one either.

Additionally, many NP problems that are not NP-complete will have search to decision reductions. For instance, Graph Isomorphism. Along slightly different lines, problems like Discrete Logarithm have what is called Ransom Self Reducibility -- if you have an oracle that solves a large fraction of smaller instances of a problem successfully, then you can solve the problem on a larger input size. This kind of property allows you to reduce worst case to average case, and so a way to try to establish Average Case hardness of a problem, which is important for Cryptography.

Not all NP problems are known to be self-reducible though. Although many common ones are, the result in this paper rules out any simple proof for every single problem in NP.

http://www.google.com/url?sa=t&source=web&cd=5&ved=0CDEQFjAE&url=http%3A%2F%2Fciteseerx.ist.psu.edu%2Fviewdoc%2Fdownload%3Fdoi%3D10.1.1.157.3658%26rep%3Drep1%26type%3Dpdf&ei=02VmTMjIC4K8sQPW0OSXDQ&usg=AFQjCNEvu2rttkpbEQ7X0C9MIlrU-FIgJA&sig2=k7eTQI6BgHMTaIMv312UXA

Your question is also tangentially related to the Dichotomy Conjecture for CSPs. The problem can be posed as follows. Given any particular CSP language, determining if a particular CSP in that language is satisfiable is an NP problem. For some CSP languages, the corresponding problem is NP-complete, for instance 3SAT, while for others such as XORSAT, the problem is known to be in P. Is it true that, for every CSP language, the corresponding problem will be solvable in polynomial time OR NP-complete? Given a description of a particular CSP language, can we determine in polynomial time whether the corresponding problem is solvable in Polynomial Time or NP-complete? There has been much work and a resurgence of interest in this problem in recent years, and it seems that top researchers are getting close to resolving it in the affirmative.

Comment by Chris Beck

2010-08-18T08:54:24Z

Wow, I can't believe that ordering works! It is completely arbitrary dependent on how GAP chooses to order the elements, right? Out of curiosity, do you have reason to believe that a random bijection that respects the orders of elements should work, for most large enough groups, if not all groups, or something along these lines? I intend to accept the answer, I'd just like to work out the pencil and paper proof myself first :)