37
$\begingroup$

I'm interested in proofs of claims of the form "Finite objects $A$ and $B$ are isomorphic" which are nonconstructive, in the sense that the proof doesn't exhibit the actual isomorphism at hand.

A stronger (and more precisely specified) requirement would be a case in which it's computationally easy to write a proof, but computationally hard to extract the isomorphism given the proof, e.g. a class of graphs for which one can easily generate triples $(G,H,P)$ with $P$ a proof that $G$ and $H$ are isomorphic but for which there's no (known) efficient algorithm to take in $(G,H,P)$ and return a permutation of the vertices exhibiting the isomorphism.

Some examples of things that would fit the bill, were they to exist:

  • (give a nonconstructive proof that) all objects of type $X$ are uniquely specified by their values on five specific measurements; observe that $A$ and $B$ align on all such measurements.

  • The easy-to-compute function of graphs $f(G,H)$ turns out to be equal to the product, over all relabelings of $G$, of the number of edges in the symmetric differences between the edge sets of $H$ and the relabeled copy of $G$. (This occurs because of some cute algebraic cancellation or something, like how one can compute determinants in time $O(n^3)$.) Now we observe that $f(G,H) = 0$ via direct computation, and conclude that a relabeling with no difference at all to $H$ must exist.

  • Groups $G$ and $H$ of order $n$, specified by their multiplication tables, can be easily shown to embed as subgroups of a larger group $K$, which we can classify and more easily prove things about. But the existence of two non-isomorphic subgroups of order $n$ in $K$ would imply something about its Sylow subgroups that we know to be false.

Are there good examples of this phenomenon? Reasons to think it doesn't happen? I would also be interested in any pointers to literature on related topics here.

$\endgroup$
9
  • 1
    $\begingroup$ Do the objects have to be finite? I missed that part when I was writing my answer. $\endgroup$
    – David
    Aug 24, 2022 at 16:43
  • 1
    $\begingroup$ I feel like there should be some good examples using the probabilistic method, or maybe some of its classic results can be rephrased as giving the existence of an isomorphism. $\endgroup$ Aug 25, 2022 at 14:11
  • 2
    $\begingroup$ Or what about knot invariants? For instance, the Jones polynomial is a complete invariant on prime knots up to 9 crossings. So if you take two such knots, compute their Jones polynomials, and find they are the same, then there must be an isomorphism between them, i.e. a sequence of Reidemeister moves, but no obvious way to find those moves. However, the proof is presumably by taking a pre-existing list of knots up to isomorphism, computing all their Jones polynomials, and seeing they are all distinct. So maybe that's cheating. $\endgroup$ Aug 25, 2022 at 14:23
  • 1
    $\begingroup$ (And knots are fundamentally finite objects; there are well-known ways to represent an arbitrary knot diagram by a finite sequence of integers or the like.) $\endgroup$ Aug 25, 2022 at 14:27
  • 2
    $\begingroup$ Too boring to put as a "real" answer: The Classification of Finite Simple Groups says that every finite simple group is isomorphic to [blah blah blah], but does not provide an explicit construction for this isomorphism. So if you can construct a simple finite group of order n, and then prove that it isn't isomorphic to (say) $C_n$ or any of the other families except for one specific family, then you can narrow that down to a single group, but you still would not have an explicit construction. $\endgroup$
    – Kevin
    Aug 26, 2022 at 6:00

8 Answers 8

47
$\begingroup$

The simplest example I know: the existence of primitive roots tells us that if $p$ is a prime then the group $(\mathbb{Z}/p\mathbb{Z})^{\times}$ of units $\bmod p$ is cyclic, hence isomorphic to $C_{p-1}$. However, exhibiting such an isomorphism amounts to finding such a primitive root, and the proof does not do this, nor does it really supply an efficient algorithm to do it.

I don't know what the time complexity of finding a primitive root is. The "obvious" probabilistic algorithm is to factor $p - 1$, then pick a random $a \in (\mathbb{Z}/p\mathbb{Z})^{\times}$ and test whether it's a primitive root by computing $a^{\frac{p-1}{q}} \bmod p$ for all prime divisors $q$ of $p-1$. This should be pretty fast in practice although it will take at least as long as factoring $p - 1$ and I don't know what the deterministic time complexity is.

$\endgroup$
5
  • $\begingroup$ You can find a prime $p$ and a primitive root modulo $p$ in probabilistic polynomial time. For example, pick a prime $p$ such that $(p-1)/2$ is prime (you can generate a random such prime by generating random primes and applying a primality test to $(p-1)/2$), then use the randomized algorithm in your answer. $\endgroup$
    – D.W.
    Aug 24, 2022 at 6:02
  • $\begingroup$ This would have been my example also. Depending on exactly when the OP accepts an isomorphism to have been exhibited, we may end up having to solve the related discrete logarithm problem. $\endgroup$ Aug 26, 2022 at 11:49
  • $\begingroup$ @D.W. one thing that is missing from your comment is that the theorem Qiaochu is discussing applies to all primes, and finding an explicit primitive root mod $p$ for arbitrary primes $p$ (not just prime $p$ where $(p-1)/2$ is prime) is a hard task at present. Victor Shoup wrote on p. 340 of his book on computational number theory and algebra that "there is no known way to efficiently recognize a primitive root modulo $p$ without knowing the prime factorization of $p − 1$." $\endgroup$
    – KCd
    Aug 26, 2022 at 18:40
  • 2
    $\begingroup$ @KCd, No, I didn't miss that. The question asked for (efficiently constructible) examples of groups that are non-constructively isomorphic, and I'm saying that you can obtain such examples by looking at the class of groups $(\mathbb{Z}/p\mathbb{Z})^\times,C_{p-1}$ where $p$ is prime and $(p-1)/2$ is prime. That provides a perfectly valid answer to the original question, and one that meets all of the conditions in the question. There is no requirement in the question that we have to include all $p$. You might just as well complain that this only works when $p$ is prime. $\endgroup$
    – D.W.
    Aug 26, 2022 at 19:11
  • $\begingroup$ @D.W. okay, I see what you mean. (There are nonprime m where $(\mathbf Z/m\mathbf Z)^\times$ is cyclic, such as odd prime powers.) $\endgroup$
    – KCd
    Aug 26, 2022 at 20:07
26
$\begingroup$

Here's a charmingly ugly example. Suppose $X$,$Y$, and $Z$ are simply-connected CW-complexes. Suppose each has the same homology groups as the others:

$H_0(X; \mathbb{Z}) \cong H_0(Y; \mathbb{Z}) \cong H_0(Z; \mathbb{Z}) \cong \mathbb{Z}$

$H_3(X; \mathbb{Z}) \cong H_3(Y; \mathbb{Z}) \cong H_3(Z; \mathbb{Z}) \cong \mathbb{Z}$

$H_5(X; \mathbb{Z}) \cong H_5(Y; \mathbb{Z}) \cong H_5(Z; \mathbb{Z}) \cong \mathbb{Z}$

$H_n(X; \mathbb{Z}) \cong H_n(Y; \mathbb{Z}) \cong H_n(Z; \mathbb{Z}) \cong 0$ for all $n\neq 0,3,5$.

Then at least two of the spaces $X$, $Y$, and $Z$ are homotopy-equivalent to one another. How do you know that? It's because the assumptions imply that the homotopy types of each of $X$, $Y$, and $Z$ have minimal CW-decompositions with:

a single basepoint 0-cell,

a single 3-cell, so each of $X$, $Y$, and $Z$ have 3-skeleton $S^3$,

and a single 5-cell, so the homotopy type is determined by the homotopy class of the attaching map of the 5-cell to the 3-skeleton.

But the boundary of a 5-cell is $S^4$. So the possible homotopy types of $X$, $Y$, and $Z$ are the homotopy classes of maps $S^4 \rightarrow S^3$, i.e., the fourth homotopy group of the three-sphere, $\pi_4(S^3)$.

A quick calculation yields that $\pi_4(S^3) \cong \mathbb{Z}/2\mathbb{Z}$. So there's only two homotopy-types of spaces of the kind that $X,Y$, and $Z$ are assumed to be. So at least two of the three have to be homotopy-equivalent to one another. But it's non-constructive: the information given isn't enough to pin down which two are homotopy-equivalent. So you get non-constructive isomorphism in the homotopy category of topological spaces.

It's more non-constructive than that, though. Even if you use an argument like this to figure out that $X$ and $Y$ have to be homotopy-equivalent to one another, that's a long way from having continuous maps between them, an explicit homotopy equivalence.

$\endgroup$
23
$\begingroup$

We know that any two finite fields with the same cardinality are isomorphic. On the other hand, suppose you have two different polynomials $f, g \in \mathbb{F}_q[x]$ which are irreducible and have the same degree. I'm not aware of any easy computation which would give an explicit isomorphism of fields $\mathbb{F}_q[x] / \langle f \rangle \simeq \mathbb{F}_q[x] / \langle g \rangle$, which would amount to finding a root of $g$ in the first field.

$\endgroup$
18
$\begingroup$

If a purely set theoretic example is acceptable:

The Cantor-Schröder-Bernstein theorem says that a bijection between two sets $A$ and $B$ exists when there are injections $i : A \rightarrow B$ and $j : B \rightarrow A$.

This theorem is not constructively valid. There is information on why this is the case in the answers at that link to a MathOverflow question. Cantor's original proof, for example, used the well-ordering theorem (which is equivalent to the axiom of choice).

Here is a recent paper which shows that Cantor-Schröder-Bernstein implies excluded middle.

$\endgroup$
14
  • 2
    $\begingroup$ If I remember correctly, we can explicitly write down this bijection! I’m confused in what sense this is not constructive $\endgroup$
    – FShrike
    Aug 24, 2022 at 19:36
  • 1
    $\begingroup$ Oh I see, because the law of excluded middle must be used. However, I feel that such tenets of classical logic are implicit in the original question - most contexts in which isomorphisms arise are contexts in which “normal” logic applies, such as the law of the excluded middle. Otherwise, (a proof of) CSB is explicit - so, in common language, constructive - in providing such a bijection $\endgroup$
    – FShrike
    Aug 24, 2022 at 19:39
  • 6
    $\begingroup$ The 'explicit' bijection in the CSB proof does not (in general) yield an algorithm. The description involves cases on propositions that may not be algorithmically decidable. For instance, the mathoverflow answer by Todd Trimble about injections between ℕ and a subset of ℕ involving non-halting Turing machines. In that case, the described function would involve cases on whether or not machines halt, which is a well known undecidable problem. This is why excluded middle is a problem for logic internal to computation. It corresponds to the assertion that every proposition is decidable. $\endgroup$
    – Dan Doel
    Aug 24, 2022 at 23:09
  • 4
    $\begingroup$ @FShrike The way I understand it is that $x\in X$ or $x\not\in X$ is constructively invalid. $\endgroup$ Aug 25, 2022 at 11:02
  • 2
    $\begingroup$ @FShrike Deciding membership in an arbitrary set is not computable (I think you run into issues here). I sort of see what you're saying, but if you consider such things "constructive," the definition of that word seems like it depends on arbitrary "syntactic" choices (compared to defining it in terms of computability etc). For example, consider a nonconstructive statement "… then z is the smallest natural satisfying P" can be rewritten as "then z = $\mu x(P(x))$" with the unbounded $\mu$ operator. Is this now constructive because we are "constructing" it with $\mu$? Note P could be undecidable $\endgroup$
    – David
    Aug 25, 2022 at 14:31
13
$\begingroup$

Lovasz ["A note on the Line Reconstruction Problem", J Combinatorial Theory B, 13, 1972] proved that two finite simple graphs $G,H$ on $n$ vertices with the same collection of unlabeled proper subgraphs must be isomorphic if each has $m > \frac{1}{2}\binom{n}{2}$ edges. It is an attack on the well known edge-reconstruction conjecture. The proof uses inclusion-exclusion to count the set of monomorphisms $G\to H$, and shows that $|G\to H| = |H\to H|$, but $|H\to H|$ is of course greater than zero.

By inclusion-exclusion $|G\to H| = \sum_{X\subseteq G} (-1)^{|E(X)|}|X\to \overline{H}|$ where $X$ runs over all graphs with $V(X)=V(G)$ and $E(X)\subseteq E(G)$, and $\overline{H}$ is the complement of $H$. Similarly, $|H\to H| = \sum_{X\subseteq H} (-1)^{|E(X)|}|X\to \overline{H}|$. Since $G$ and $H$ have the same unlabeled proper subgraphs, the terms on the right hand side with $|E(X)| < m$ must be identical in both equations, and since $m > \frac{1}{2}\binom{n}{2}$, the terms with $|E(X)| = m$ must be zero. Hence, $|G\to H| = |H\to H|$ and so there is at least one isomorphism from $G$ to $H$.

I have never seen a way the proof can be modified to find an explicit isomorphism from $G$ to $H$ using known isomorphisms from $G-e$ to $H-\phi(e)$, where $e\in E(G)$ and $\phi :E(G)\to E(H)$ is some bijection.

$\endgroup$
12
$\begingroup$

A contrived example to link this to the law of excluded middle is to start with some proposition $p$ and then consider the set $\{0 \mid p\} \cup \{1 \mid \neg p\}$. It's immediate that classically, this set is isomorphic to $\{2\}$. However, actually having the isomorphism entails knowing whether $p$ is true or false.

$\endgroup$
6
$\begingroup$

A particular example:

$\mathbb{P}$ : Set of all primes

$\mathbb{N}$ : Set of all positive interger.

$\mathbb{P}\subset \mathbb{N}$ and $\mathbb{P}$ is an infinite set $[$ a list of proofs$]$

Any infinite subset of $\mathbb{N}$ has the cardinality $|\mathbb{N}|=\aleph_0$.

Hence there is a bijection between $\mathbb{P}$ and $\mathbb{N}$.

But it's difficult to construct such bijection.

$\endgroup$
6
  • 2
    $\begingroup$ Why is it difficult to construct such a bijection? Map each prime to the number of primes below it. $\endgroup$ Aug 26, 2022 at 16:46
  • 3
    $\begingroup$ Sure but what’s non constructive about it? $\endgroup$ Aug 26, 2022 at 17:29
  • 3
    $\begingroup$ I think the point is not what theorems are needed, but that computing the bijection appears to be computationally hard. I'm not aware of any efficient (polynomial-time) algorithm to compute this function in either direction. $\endgroup$
    – D.W.
    Aug 26, 2022 at 19:15
  • 1
    $\begingroup$ @D.W. Computationally hard and non-constructive are not synonymous. $\endgroup$ Aug 28, 2022 at 9:45
  • 4
    $\begingroup$ @Shinrin-Yoku, I am well aware of that. In this specific question, the original poster writes that they are looking for "a case in which it's computationally easy to write a proof, but computationally hard to extract the isomorphism given the proof". That is why it is relevant that it appears to be computationally hard to compute this bijection. $\endgroup$
    – D.W.
    Aug 28, 2022 at 22:55
2
$\begingroup$

There are non-constructive techniques for Graph Isomorphism, such as Weisfeiler--Leman (WL). While it is known that WL cannot place Graph Isomorphism into $\textsf{P}$, it serves as a complete invariant for a number of graph families including planar graphs, graphs of bounded tree width, graphs of bounded rank width, and graphs of bounded genus.

To use WL as an isomorphism test, we run WL on the disjoint union of our two input graphs $G, H$. If the multiset of colors for $G$ differ from that of $H$, then we know that $G$ and $H$ are non-isomorphic. For the above families of graphs, this is enough to decide isomorphism.

While the multiset of colors on its own does not in general yield an isomorphism, it is possible to use WL to compute a canonical labeling. Grohe & Neuen have a write-up of this in the appendix here (https://arxiv.org/abs/1901.10330).

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .