2
$\begingroup$

Consider two countable families of objects, given as unions of finite subfamilies:

$F^k = \bigcup_{n \in \mathbb{N}} F^k_n$, k = 1,2.

Let there be a bijection $f: F^1 \rightarrow F^2$ such that $x \in F^1_n \Leftrightarrow f(x) \in F^2_n$ for all n $\in \mathbb{N}$.

This means: The two families have the same counting functions $f^1(n) = f^2(n)$ for all n $\in \mathbb{N}$ with $f^k(n) = |F^k_n|$.

This may be by sheer accident, or it may be because the two families are in some sense essentially the same.

Can the notions of "by accident" and "essentially the same" be distinguished in this context, and how?

"Essentially the same" might mean: "there is a computable bijection" and "by accident" might mean: "there is no computable bijection". Or might category theoretical notions lead further?

Are there known examples of two families as above that have the same counting functions by accident (in the meaning just mentioned or another one)?

PS: More sensible tags are welcome!

Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ "essentially the same family" is nicely (well, this is of course subjective) captured by the categorical notion of species and their isomorphisms. It is a much stronger than a computable bijection. $\endgroup$
    – Philippe Nadeau
    Commented Sep 13, 2010 at 10:19
  • $\begingroup$ Thank you! This answers question 1. What about question 2? $\endgroup$
    – Hans-Peter Stricker
    Commented Sep 13, 2010 at 10:23
  • 1
    $\begingroup$ This can be also answered philosophically. Surely we can define 'by accident' formally, and then arbitrarily construct sets of objects that have the same counting function but with is no -meaningful- isomorphism. But then such a construction is most likely not between anything interesting combinatorially. That is, we -act- like every pair of sets with a bijection has a meaningful bijection, just that we may not have found one yet. On the other hand, this may just be motivation to look at those numerical identities that don't yet have a satisfying combinatorial interpretation. $\endgroup$
    – Mitch
    Commented Sep 13, 2010 at 15:31

2 Answers 2

Reset to default
7
$\begingroup$

If you adopt Philippe Nadeau's proposal to define "essentially the same" in terms of isomorphism of species, then a standard example of "accidental" is the following. For any finite set $S$, there are just as many linear orderings of S as there are permutations of $S$ (i.e., bijections from $S$ to itself), namely $|S|!$. But the two species are not isomorphic. There is a distinguished permutation, namely the identity, but there is no distinguished linear ordering (provided $|S|>1$).

Some people feel that these two are, nevertheless, in some sense the same. (In fact, some people indiscriminately use the word "permutation" for both.) That feeling can be formalized in the observation that, if you choose one linear ordering of $S$, then it determines a natural bijection between the linear orderings and the permutations: Given a permutation, apply it to the chosen linear ordering. So people who want to think of these two species as essentially the same would want a weakening of "isomorphism of species" that would allow this sort of "isomorphism modulo an arbitrary choice." Unfortunately, it's not clear how big an object could reasonably be arbitrarily chosen --- presumably not a whole isomorphism. So I don't see a good way to make this intuition precise; as a result, I'm inclined to stick with "isomorphism of species" and to accept that linear orderings and permutations are not essentially the same.

Improve this answer
$\endgroup$
3
  • $\begingroup$ That's the kind of example of "accidental" I was looking for. Thank you, Andreas! $\endgroup$
    – Hans-Peter Stricker
    Commented Sep 13, 2010 at 17:56
  • $\begingroup$ That touches upon a question I return from time to time: for "linear" species (i.e., functors from finite ordered sets into finite sets), any two that have the same cardinality are isomorphic. So, is there any natural notion of isomorphism "inbetween" species and linear species? $\endgroup$
    – Martin Rubey
    Commented Sep 13, 2010 at 20:21
  • $\begingroup$ @Martin Rubey: Take the objects of the domain category to be finite sets with distinguished elements. Then you have a natural bijection between the even-sized subsets of S and the odd-sized ones, namely, remove the distinguished element from those subsets that contain it and add it to those that don't. Without a distinguished element (or at least a distinguished odd-sized subset), there would be no natural bijection witnessing the fact that finite nonempty sets have equally many even- and odd-sized subsets. $\endgroup$
    – Andreas Blass
    Commented Sep 14, 2010 at 16:16
5
$\begingroup$

Partitions of $n$ with parts congruent to $1$ or $4$ modulo $5$ are known to be equinumerous with those having difference between successive parts at least equal to $2$ (cf. Rogers-Ramanujan identities); no "direct" bijection is known (although there are computable ones, cf. Garsia and Milne's involution principle).

Some work I think of Igor Pak showed that such a bijection is forbidden to be constructed in a certain way (sorry for the vague formulation), and therefore this might be one of the (rare) case of accidents.

Improve this answer
$\endgroup$
3
  • $\begingroup$ That's funny: Igor Pak just commented my other question mathoverflow.net/questions/38541/… $\endgroup$
    – Hans-Peter Stricker
    Commented Sep 13, 2010 at 13:51
  • $\begingroup$ Do you think, "rare" can eventually be quantified, maybe like "almost none"? $\endgroup$
    – Hans-Peter Stricker
    Commented Sep 13, 2010 at 13:53
  • 2
    $\begingroup$ Igor's definition of a geometric bijective proof can be found in his preprint math.ucla.edu/~pak/papers/stab5.pdf . He shows that almost all classical bijective proofs are geometric, and that any geometric bijection has a property called asymptotic stability. He claims that there is no asymptotically stable bijection proving the Roger-Ramanujan identity, but cites the details to a "forthcoming paper" with the title "Rogers-Ramanujan bijections are not geometric". As far as I know, that preprint has not appeared yet. $\endgroup$
    – David E Speyer
    Commented Sep 13, 2010 at 15:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.