7
$\begingroup$

Much literature (see, e.g., references here) has been written about the existence and “construction” of moduli spaces of algebraic spaces of a given genus — coarse or fine, smooth or stable, possibly with marked points or other rigidifying structures. I put “construction” in quotes here, because it is unclear to me how effective these descriptions are. How obvious is the answer to the following question supposed to be? (To me it certainly isn't.)

Question: Is there a Church-Turing computable function which takes as input $g$ (and possibly also $n$) and returns an effective description of the moduli space of stable curves of genus $g$ (or at least the smooth curves; and possibly with $n$ marked points)?

Any sort of moduli space interests me, really: for the fine ones, the problem is that it's not even clear to me what an algorithmic description of a Deligne-Mumford stack should look like. (Nor is it clear to me how one would compute a coarse space from a fine one!)

Has anything been written about this kind of questions? Failing that, what is the most promising kind of construction of moduli spaces of curves with an eye toward algorithmic effectivity?

Improve this question
$\endgroup$
6
  • $\begingroup$ How hard is it to express the relevant constructions and definitions in higher-order logic? If the definitions are sufficiently predicative (do not rely on powersets in essential ways), then we could interpret them in a realizability model to get an answer. $\endgroup$ Commented Feb 18 at 11:59
  • $\begingroup$ @AndrejBauer I'm not familiar with the notions in your comment but I suspect that this kind of direct-from-the-definitions approach will not work. The issue is that definitions in algebraic geometry often involve some a priori large objects, i.e. a stack is defined as a category fibered over the category of all rings so it is not even clear what a computable version of this would mean. $\endgroup$ Commented Feb 18 at 15:34
  • $\begingroup$ My guess is that a realizability model would involve either restricting attention to rings where the set of elements and addition and multiplication are all computable, or treating a ring as a black box where certain operations are accessible to computation as oracles. But it is not clear that such definitions are equivalent to the original algebraic geometry definition in any sense, and this requires some separate finiteness theorem to check. $\endgroup$ Commented Feb 18 at 15:36
  • $\begingroup$ Alternately one can try to show that a concrete description of the moduli space as an object of a particular type is computable, as in my answer where I try to describe it as a quotient of a quasiprojective variety as a group action. Then the fact that the moduli space has this form is a theorem, and presumably one would have to express the proof of this theorem in some sufficiently constructive logic to get an algorithm "for free". $\endgroup$ Commented Feb 18 at 15:38
  • $\begingroup$ (but of course you should see all of this as an invitation to explain in more detail how the realizability model approach to effectivity would work and whether the difficulties I mention are obstructions to it.) $\endgroup$ Commented Feb 18 at 15:39

1 Answer 1

Reset to default
7
$\begingroup$

I think the standard constructions give algorithmic effectivity if you think them through step-by-step and combine them with more-or-less standard arguments, though I have not actually worked out all the details of this. I would even stake the claim that this is true to the extent that the interesting question is not so much which constructions are effective as which constructions give efficient algorithms, e.g. what computational complexity bounds can we prove.

A good way of presenting a stack effectively is as a global quotient stack $X /G$. For example, one can give polynomial equations and inequalities defining a quasiprojective variety $X$, together with polynomial equations defining an affine group scheme $G$, including the group law and the action on $X$.

Of course, not all stacks are representable as the quotient of a quasiprojective algebraic variety, but the moduli stack of smooth curves of genus $g$ with $n$ marked points certainly is, and I think the stable one is as well. The usual argument here is to observe that for $C$ a curve of genus $g>1$ the line bundle $3 K_C$ is always very ample and defines an embedding of $C$ into projective space of dimension $5g-6$ with degree $6g-6$. One can thus consider the moduli space of smooth curves of degree $6g-6$ and genus $g$ in $\mathbb P^{5g-6}$, which is a quasiprojective variety, take the closed subscheme of curves that are tricanonically embedded, and then take the quotient by $PGL_{5g-5}$. For $n$ marked points, take the moduli space of such curves together with $n$ points on them.

So it remains to computably find equations for the moduli space of curves of a given genus and degree in projective space that are tricanonically embedded, possibly with some marked points. I can think of two approaches to this, one via the Hilbert scheme and one via the Chow variety. To prove this space is quasiprojective I would just observe that it is an locally closed subscheme of the Hilbert scheme, which is projective. The proof that the Hilbert scheme is projective involves finding a $d$ such that the closed subschemes under consideration are determined by the space of degree $d$ equations they satisfy, and all satisfy spaces of degree $d$ equations of the same dimension, so that the Hilbert scheme can be embedded into a Grassmanian parameterizing linear subspaces of the space of homogeneous polynomials of degree $d$. I think $d=2$ probably works in this case, so we can embed the moduli space into an explicit Grassmanian. For Chow varieties, the space which they are embedded into is always an explicit projective space due to the Chow embedding. For $n$ marked points, the space we embed the moduli space into would be the product of that Grassmanian or projective space with some copies of $\mathbb P^{5g-6}$.

Once we have a space containing our desired moduli space, we just need to find explicit equations and inequalities picking it out. Some of the conditions that our curves have to satisfy, like smoothness, are easily expressed as first-order statements in the theory of an algebraically closed field so there is an algorithm giving the relevant equations. For others, like the existence of an isomorphism between $\mathcal O(1)$ and the tricanonical line bundle, it's not immediately obvious how to express it as a first-order statement, but I think you can work out how to do it by hand: You're looking for a section of the third power of the tangent bundle tensor $\mathcal O(-1)$. On each affine chart such a section can be expressed as a tuple of polynomials and one just needs some computable bound on the degree of such polynomials.

Improve this answer
$\endgroup$
6
  • $\begingroup$ It really would be interesting to see whether anywhere above there is any reliance on excluded middle or the general axiom of choice. Definitions never rely on any axioms, but proofs of theorems do. It might be the case that some of the concepts you mentioned only make sense because certain theorems are known to hold. Unfortunately, I am so far removed from this topic that I don't even know where to look. $\endgroup$ Commented Feb 18 at 19:49
  • $\begingroup$ As a rule of thumb, any algebraic structure that is finitely presented will have a direct transcription to realizability (and much more). $\endgroup$ Commented Feb 18 at 19:51
  • $\begingroup$ The descriptions of the Deligne-Mumford compactification as finite quotient stacks (away from “bad” characteristics) is done by Pikaart, Looijenga, et al., using “non-Abelian level structures.” Of course since these are quasi-compact, smooth Deligne-Mumford stacks, they are global quotients of quasi-projective schemes by actions of general linear groups. $\endgroup$ Commented Feb 19 at 12:50
  • $\begingroup$ @AndrejBauer I think this is one of the situations where whether an argument relies on the law of the excluded middle doesn't have a well-defined answer because there are definitions used which have multiple ways you can state them that are classically equivalent but not constructively equivalent, and it depends on how you state the definition. My guess is that there is a way to state things that makes everything constructive. (In part, this is because, as I sketched, I believe there is an algorithm, so presumably that algorithm corresponds to a constructive proof of something.) $\endgroup$ Commented Feb 20 at 12:05
  • $\begingroup$ @AndrejBauer I am now more optimistic that the usual definition of stack makes sense constructively with a black-box model of computation, i.e. a ring is treated as a black box which inputs two elements and outputs their sum and product and does a couple other things like that, and then a stack is supposed to be a program which inputs a ring and outputs a type in the sense of a program that can tell whether something is a well-formed member of the type and can tell if a proof that two members of the type are equal is a proof and can tell if two proofs are equal. $\endgroup$ Commented Feb 20 at 12:14

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.