17

Let $\mathrm{FinSet}$ be the category of finite sets.

A finite set structure is a faithful functor $F\colon C\to \mathrm{FinSet}$ such that, for any $n\geq 1$, there are only finitely many isomorphism classes of objects $F$ maps to $\{1, \dots, n\}$.

Question. Is there a natural finite set structure realizing the Ackermann function (or some other computable function growing faster than any primitive recursive function)?

Francesco Polizzi
  • 65,122
catlyn
  • 171
  • 1
    The Ackermann function $A(m,n)$ takes two inputs; apart from this, if I understand well, you're asking about the existence of a species of structure whose associated exponential series (in the variables X,Y) is $\sum \frac{A(m,n)}{n!m!}X^nY^m$. First of all, is this series convergent? – fosco May 10 '21 at 14:34
  • 1
    @fosco I had in mind $f(n)=A(n, n)$ – catlyn May 10 '21 at 14:35
  • oh, fair enough; well, is the series $\sum \frac{f(n)}{n!}X^n$ convergent in at least a disk $B(0,\epsilon[$? – fosco May 10 '21 at 14:36
  • 9
    @fosco : why is the convergence of the series relevant to the question ? – Simon Henry May 10 '21 at 14:37
  • 3
    @fosco, surely not; $f(n) \ge (n!)^2$ eventually. – LSpice May 10 '21 at 14:37
  • hi @SimonHenry ! To a combinatorial species you can associate various formal power series, and especially from the exponential series you can understand a lot about the species itself --although not everything. Ad yes, that series it's not convergent, so there is no associated function you can study. This makes the problem elusive, even provided you find a meaning for what kind of structure $A(n,n)$ is counting. – fosco May 10 '21 at 14:40
  • 7
    I'm not sure how to understand this question. For any function $f:\mathbb{N} \to \mathbb{N}$ I can chose a sequence of sets $P_n$ such that $# P_n = f(n)$ and take $C$ to be a naively defined category with an object for each $i \in P_n$ mapping to a set with $n$ elements... so any functions can be obtained this way. – Simon Henry May 10 '21 at 14:42
  • 2
    @SimonHenry yes you can associate some category but I wondered if there was a natural (in the vague sense of the word) choice. Maybe a structure arising independently elsewhere in mathematics. – catlyn May 10 '21 at 14:44
  • 2
    @fosco : yes but,I am not aware of anything that forces the exponential generating function of combinatorial species to converge, so why would the convergence brings anything to the question ? But maybe you have in mind some result proving the convergence for some class of "nice" species ? – Simon Henry May 10 '21 at 14:45
  • 1
    @SimonHenry even though the question isn't phrased in this way, I suspect it is asking about a species of structure with the Ackermann function as generating species. I have no idea what the sequence $a_n=A(n,n)$ could be counting, though, and throwing the very few terms of the sequence that can be computed at OEIS doesn't seem a viable choice: is there a combinatorial interpretation for those numbers? – fosco May 10 '21 at 14:46
  • 2
    Not sure why this (good) question has a category theory tag, but there is a kind of "categorical number theory / combinatorics" that was studied by Steve Schanuel. I don't know any more than that. – Paul Taylor May 10 '21 at 14:57
  • There is a whole "school" of enumerative combinatorics done using Joyal's species! Relevant names are Joyal himself, Labelle, Leroux, Viennot, Mendez, Rajan... – fosco May 10 '21 at 15:07
  • 4
    Interesting question. Maybe some nested set-partition-like structures? A stupid answer would be to take a deterministic rewrite system that takes $A\left(n,m\right)$ steps to terminate (I think there should be one), and just say "the intermediate states of this rewrite system". – darij grinberg May 10 '21 at 15:47
  • 7
    The inverse Ackermann function appears in some algorithms, e.g. using a "soft heap" you can find the minimum spanning tree in time $O(m\alpha(m, n))$. A decade ago I probably knew why and whether something was being counted. – Ville Salo May 10 '21 at 17:55
  • 1
    So, I do not know what the Ackermann function counts, but the TREE function does count something explicit and combinatorial, and the Ackermann function is tiny in comparison with TREE. https://mathoverflow.net/questions/93828/how-large-is-tree3 – Per Alexandersson May 16 '21 at 06:38

0 Answers0