Recent MathOverflow Questions

Syzygy dimension and finitistic dimension

Math Overflow Recent Questions - Thu, 08/10/2017 - 12:24

Let $A$ be a finite dimensional algebra. Define the syzygy-dimension O-dim of A as $O-dim(A):= inf \{ i \geq 1 | \Omega^{i}(mod-A) = \Omega^{i+1}(mod-A) \}$, dually one can define a cosyzygy-dimension. It is easy to see that this dimension coincides with the Gorenstein dimension in case the algebra is Gorenstein. Defining for a module $M$ $O-dim(M):= \inf \{ s | M \in \Omega^s(mod-A) , M \notin \Omega^{s+1}(mod-A) \}$, one has $O-dim(A) = \sup \{ O-dim(M) | O-dim(M) < \infty \}$+1 for nonselfinjective A.

Question 1: Do we always have $findim(A) \leq O-dim(A)$, with $findim(A)$ being the finitistic dimension of the algebra? My proof attempt leads to the question wheter every module $N$ in $\Omega^{\infty}(mod-A) := \bigcap_{i \geq 0} \Omega^{i}(mod-A)$ has either projective dimension zero or infinite. Maybe it is also better to take the finitistic injective dimension instead of the finitistic projective dimension?

My computer found no counterexample, but of course he can only check representation-finite algebras. In fact always was the syzygy dimension at most 1 larger than the finitistic dimension.

Question 2: Do the syzygy and cosyzygy dimension coincide?

Are polynomials with non-($S_n$ or $A_n$) Galois groups discrete?

Math Overflow Recent Questions - Thu, 08/10/2017 - 11:21

There are various results, beginning with van der Waerden, on the asymptotic number of integral polynomials with bounded coefficients, whose Galois group is $S_n$. Some of these results also include $A_n$ in the number of polynomials. In particular, Rainer Dietmann (On the distribution of Galois groups, 2012) shows that the number of polynomials of degree $n$ and height $\leq H$ which do not have Galois group $S_n$ or $A_n$ to be $\ll H^{n-1+e(n)+\varepsilon}$ for a function $e(n)$ which rapidly tends to zero.

On the other hand, Joos Heintz (On polynomials with symmetric Galois group which are easy to compute, 1986) shows that the polynomials over a Hilbertian field $k$, considered as points in $k^{n+1}$, which have Galois group $S_n$ are dense.

Is it known or suspected that the polynomials (over $\mathbb{Z}$, $\mathbb{Q}$, or number fields) with a given Galois group $G \not= S_n,A_n$ are discrete? Is the answer different if instead one takes all polynomials with Galois group different from $S_n,A_n$ or if $A_n$ is dropped from the excluded groups?

EDIT: Certainly it is true over $\mathbb{Z}$ since $\mathbb{Z}^{n+1}$ is discrete. However, I wonder how close two polynomials with Galois group $G \not= S_n,A_n$, or even two distinct groups $\not= S_n,A_n$, can get.

Minimal size of the maximum biclique

Math Overflow Recent Questions - Thu, 08/10/2017 - 11:06

We examine a bipartite graph with two sides $R$ and $L$, and denote by $|L|$ and $|R|$ the number of nodes in each side. We know only that each node on side $R$ is connected to $k$ nodes on side $L$, that $|R| < k< |L|$, and moreover that $k$ is much larger than $|R|$.

What is the minimal size (i.e., number of edges) of the maximum biclique1?

1 Maximum biclique: The largest (in terms of number of edges) complete bipartite subgraph. Not to be confused with a maximal biclique.

Derived tensor products and Tor of commutative monoids

Math Overflow Recent Questions - Thu, 08/10/2017 - 08:21

Two commutative monoids $M,N$ have a tensor product $M\otimes N$ satisfying the universal property that there is a tensor-Hom adjunction for any other commutative monoid $L$: $$\text{Hom}(M\otimes N,L)\cong\text{Hom}(M,\text{Hom}(N,L)).$$ If $M$ and $N$ are abelian groups, then $M\otimes N$ agrees with the abelian group tensor product.

Now I would like to understand the derived tensor product and $\text{Tor}(M,N)$. Similar questions have been asked before, but I am interested in a very particular construction:

If we identify $M$, $N$, $\mathbb{N}$ as discrete commutative monoid spaces, we may take the relative smash product of $E_\infty$-spaces (see below) $M\wedge_{\mathbb{N}} N$. Each point $x\in M\otimes N$ corresponds to a connected component of $M\wedge_{\mathbb{N}} N$, and so we can take Tor groups based at x: $$\text{Tor}_n(M,N;x)=\pi_n(M\wedge_{\mathbb{N}} N;x).$$ If $M$ and $N$ are groups, the choice of basepoint is irrelevant (we can always shift to $x=0$), and we recover the usual Tor groups.

How might I go about computing this commutative monoid Tor? Here is a more specific question: if $\mathbb{N}\rightarrow R$ is a surjection of commutative semirings (such as $R=\mathbb{N}/(n=n+1)$), is there some $x\in R\otimes R\cong R$ such that $\text{Tor}(R,R;x)$ is nonzero? I suspect the answer is yes when $x=n$.

By the smash product of $E_\infty$-spaces, I mean for example $\infty$-categorical Day convolution of $\Gamma$-spaces, which satisfies the same tensor-Hom adjunction universal property. More generally, I would be interested in techniques to compute smash products of $E_\infty$-spaces, but I think this is very difficult, so I am asking about this toy example.

When is the following block matrix invertible?

Math Overflow Recent Questions - Thu, 08/10/2017 - 07:34

Let

$$A = \begin{bmatrix} x_{11} A_{11} & x_{12} A_{12} & x_{13} A_{13} & \cdots & x_{1d} A_{1d}\\ x_{21} A_{21} & x_{22} A_{22} & x_{23} A_{23} & \cdots & x_{2d} A_{2d}\\ \vdots & \vdots & \vdots & \ddots & \vdots \\ x_{d1} A_{d1} & x_{d2} A_{d2} & x_{d3} A_{d3} & \cdots & x_{dd} A_{dd}\\ \end{bmatrix}$$

where $A_{ij}$ is an $n \times n $ invertible matrix and $x_{ij} \neq 0$ is a scalar. All the entries in matrices and scalars are from a finite field $\mathbb{F}_q$. Let $X = (x_{ij})$. It can easily be shown that there exists a matrix $X$ such that the matrix $A$ is invertible if $q > 2$. But is there any nice sufficient condition I can put on matrix $X$ or an explicit construction of $X$ to make $A$ invertible other than saying the $\det(A)$ polynomial in $x_{ij}$ must be non-zero?

Number of connected components of the intersection of two maximal tori

Math Overflow Recent Questions - Thu, 08/10/2017 - 07:28

Let $G$ be a connected complex semisimple Lie group and $S$, $T$ two maximal tori in $G$. Is there a known upper bound on the number of connected components of $S\cap T$? For example, is it bounded by the cardinality of the centre $Z_G$: $$|\pi_0(S\cap T)|\leq|Z_G|?$$

Numerically inverting an integral

Math Overflow Recent Questions - Thu, 08/10/2017 - 05:04

I have an increasing function $H:[0,\infty)\to[0,\infty)$, and a function G defined as $$G(t)=\int_0^t H(s)ds.$$

I need a numerical method to find t, given that I know $G(t)=x$ for some $x\in[0,\infty)$.

I have seen a similar question asked here: Numerical Solution to Inverse Integral (Pseudo Random Number Generation) but there was no reference and I'm not sure I understand why it works.

Result attribution for eigenvalues of a matrix of Pascal-type

Math Overflow Recent Questions - Thu, 08/10/2017 - 01:26

A few years ago, I wanted to cite a result in a paper, for which I could not find a reference. I ended up not using the full strength of it, and the part that I needed could be easily proved. Still, I'd like to know where the full version appears. The result is as follows:

The eigenvalues of the matrix $$\left[\binom{i+j}{i}\binom{2n-i-j}{n-i}\right]_{0\le i,j\le n}$$ are $$\binom{2n+1}{k}, \quad 0\le k\le n.$$

If a formula for the corresponding eigenvectors also appears somewhere, that would be helpful, too. (I only needed the fact that $\binom{2n+1}{n}$ has eigenvector $[1,1,\dots,1]^T$, and that's easy to see.) Thanks.

Orthonormal basis and decay

Math Overflow Recent Questions - Wed, 08/09/2017 - 17:50

Edit: I added smoothness, hoping to simplify the problem with this additional assumption.

Let me motivate this question first: In signal analysis it is often of interest to understand when a certain function has a fast decaying representation with respect to some basis. I encountered an example where I expected such a fast decaying representation but was unable to show it myself:

The situation is that one is given a sequence of functions whose supports are only overlapping with their nearest neighbors. Intuitively, I expected that if I would write any of those function in terms of the Gram-Schmidt orthonormalized sequence of all functions, then the expansion coefficients should decay fast.

Let me now make this more precise:

Take a family of intervals $I_{2i}:=(i,i+1)$ and $I_{2i+1}=(\frac{1}{2}+i,\frac{1}{2}+i+1)$ with $i \ge 0$ Those intervals are almost disjoint in the sense that $I_i \cap I_j=\emptyset$ if and only if $\left\lvert i-j \right\rvert >1,$ so we only have a nearest neighbor overlap.

We consider a family of smooth functions $h_i:I_i \rightarrow \mathbb{R}$ that are $L^2$ normalized (but not orthogonal) where $h_{i+1}$ is just a translate of $h_i$ by $\frac{1}{2}$ to the right.

We assume that $\langle h_0,h_1 \rangle \neq 0$ and $\langle h_1,h_2 \rangle \neq 0$ to avoid trivialities. Due to the condition on the domain, all other $h_i$ however (besides $h_0$, $h_1,$ and $h_2$) have zero overlap with $h_1$.

We now consider the Gram-Schmidt orthonormalized sequence $(g_i)$ of the $h_i$, i.e. $g_0:=h_0$ and $g_1:=\frac{h_1-\langle h_1,g_0\rangle g_0}{\left\lVert h_1-\langle h_1,g_0\rangle g_0 \right\rVert}$ and so on. Note that also $g_2,g_3,...$ and so on may now have non-vanishing overlap with $h_1$, although this one should intuitively still be small.

Clearly, $h_1=\sum_{n=0}^{\infty} a_n g_n$ for some $a_n$.

I would like to know: How rapidly do the coefficients $a_n$ decay? In particular, is it true that (the following notation means up to a constant) $\left\lvert a_n \right\rvert \lesssim L^n$ for some $L\in (0,1)$?

How can I determine the monodromy of this variation of mixed hodge structures?

Math Overflow Recent Questions - Wed, 08/09/2017 - 14:26

Consider the variation of mixed hodge structures which generates at the origin: $$ f:X = \text{Proj}\left( \frac{\mathbb{C}[t][x,y,z]}{(xy(x + y + tz))} \right) \to \mathbb{A}^1_t $$ How can I compute the monodromy of the cohomology groups $\mathbf{R}f_*(\underline{\mathbb{Q}}_X^{\text{Hdg}})$?

Minimal size of the maximal biclique

Math Overflow Recent Questions - Wed, 08/09/2017 - 03:52

We examine a bipartite graph with two sides $R$ and $L$, and denote by $|L|$ and $|R|$ the number of nodes in each side. We know only that each node on side $R$ is connected to $k$ nodes on side $L$, that $|R| < k< |L|$, and that $k$ is much larger than $|R|$.

What is the minimal size (i.e., number of edges) of the maximal biclique1?

1maximal biclique: A complete bipartite subgraph, that isn't a subgraph of another complete bipartite subgraph.

Gaussian primes in small boxes

Math Overflow Recent Questions - Tue, 08/08/2017 - 18:39

The best unconditional result bounding prime gaps is due to Baker, Harman and Pintz, and states that for any sufficiently large $n$, the interval $$[n,n+Cn^{0.525}]$$ contains a prime, for some constant $C>0$. I was curious whether an analogous result holds in the Gaussian integers.

Question 1: What is the slowest growing monotonic function $F$ such that for any sufficiently large $n,m>0,$ the box $$[n,n+F(n)]\times [m,m+F(m)]$$ contains a Gaussian prime?

We'll assume that $m\asymp n$ since the possibility of $m$ being significantly smaller than $n$ may cause additional problems (notably if $m$ is fixed, this becomes a variant of Landau's problem).

For this reason, I am particularly interested in the case $m=n$, as any method that applies here likely also applies when $m\asymp n$. The case $m=n$ takes the following simple form:

Question 2: What is the slowest growing function $F$ such that there always exists $$a,b\in [n,n+F(n)]$$ with $a^2+b^2$ prime?

Remark: There are results for Gaussian primes in narrow sectors, which can viewed as an analogue of prime gaps in the Gaussian integers. That is, very small sectors in radial coordinates where the angle tends to $0$ quite quickly as the radius tends to infinity will still contain Gaussian primes. See this Mathoverflow answer, and this paper of Harman and Lewis. I am wondering if such a result holds in Cartesian coordinates.

Finding the asymptotic bound of a summation

Math Overflow Recent Questions - Tue, 08/08/2017 - 16:59

Given a sufficiently large positive integer $n$, I would like to know the asymptotic bound in $n$ of the following summation: $$ \sum_{i=0}^{n}{\frac{P(n, i)}{n^i}} = \sum_{i=0}^{n}{\frac{n!}{(n-i)! \cdot n^i}.} $$

Is it $O(n)$, $O(\log n)$, $\dots$?

Combinatorics problem related to Motzkin numbers with prize money I

Math Overflow Recent Questions - Tue, 08/08/2017 - 11:41

Here a combinatorics problem. I offer 30 euro for a proof and 100 bounty points for a counterexample: Let $n \geq 2$.

An $n$-Kupisch series is a list of $n$ numbers $c:=[c_1,c_2,...,c_n]$ with $c_n=1$, $c_i \ge 2$ for $i \neq n$ and $c_i-1 \leq c_{i+1}$ for all $i=1,...,n-1$ and setting $c_0:=c_n$. The number of such $n$-Kupisch series is equal to $C_{n-1}$ (Catalan numbers). The CoKupisch series $d$ of $c$ is defined as $d=[d_1,d_2,...,d_n]$ with $d_i:= \min \{k | k \geq c_{i-k} \} $ and $d_1=1$. One can show that the $d_i$ are a permutation of the $c_i$. A number $a \in \{1,...,n \}$ is a descent if $a=1$ or $c_a >c_{a-1}$. Define a corresponding set, indexed by descents: $X_1 := \{1,2,...,c_1-1 \}$, and $X_a := \{ c_{a-1}, c_{a-1}+1 ,..., c_a -1 \}$ for descents $a > 1$.

A $n$-Kupisch series is called $2-$Gorenstein if it satisfies the following condition:

for each descent $a$, and each $b \in X_a$: either $c_{a+b} \geq c_{a+b-1}$ or $d_{a+b-1} = d_{a+b + c_{a+b}-1} - c_{a+b}$ is satisfied.

Conjecture: The number of $n$-Kupisch series that are $2$-Gorenstein for $n \geq 2$ equals 1, 2, 4, 9, 21, 51, 127, 323, 835, 2188, 5798, 15511, 41835, ... which are the Motzin numbers. https://oeis.org/A001006

My computer says it is true for $n=2,3,...,14$. (also for n=1 if [1] is the unique 1-Kupisch series, by a representation-theoretic interpretation)

Here an example which visualises the c and d sequences in a picture of a Dyck path: https://drive.google.com/file/d/0B9hKtvQe-4-bQlpjcURfYnNzUGs/view

Background: This has a representation theoretic background (see http://www.sciencedirect.com/science/article/pii/0022404994900442 )and would give a certain classification result together with a new categorification of the Motzkin numbers. There is a very natural bijection of n-Kupisch series to Dyck paths from (0,0) to (2n-2,0) and probably the 2-Gorenstein algebras among them might give a new combinatorial interpretation of Motzkin paths as subpaths of Dyck paths.

I found in fact many such things and translated them into elementary problems, but I have no talent in complicated combinatorics :(

example for n=5:

All 5-Kupisch series (number is 14): [ [ 2, 2, 2, 2, 1 ], [ 3, 2, 2, 2, 1 ], [ 2, 3, 2, 2, 1 ], [ 3, 3, 2, 2, 1 ], [ 4, 3, 2, 2, 1 ], [ 2, 2, 3, 2, 1 ], [ 3, 2, 3, 2, 1 ], [ 2, 3, 3, 2, 1 ], [ 3, 3, 3, 2, 1 ], [ 4, 3, 3, 2, 1 ], [ 2, 4, 3, 2, 1 ], [ 3, 4, 3, 2, 1 ], [ 4, 4, 3, 2, 1 ], [ 5, 4, 3, 2, 1 ] ]

All 2-Gorenstein 5-Kupisch series (number is 9): [ [ 2, 2, 2, 2, 1 ], [ 3, 2, 2, 2, 1 ], [ 2, 3, 2, 2, 1 ], [ 4, 3, 2, 2, 1 ], [ 2, 2, 3, 2, 1 ], [ 3, 2, 3, 2, 1 ], [ 3, 3, 3, 2, 1 ], [ 2, 4, 3, 2, 1 ], [ 5, 4, 3, 2, 1 ] ]

Representation theoretic conjecture/background:

Conjecture:

The number of 2-Gorenstein algebras that are Nakayama algebras with n simple modules with a linear oriented line as a quiver is equal to the sequence of Motzkin numbers.

Background/explanations:

Here the $c_i$ are the dimension of the indecomposable projective modules which determine the algebra uniquely (assuming that the algebras are connected quiver algebras over a field). The $d_i$ are the dimension of the indecomposable injective modules at point $i$. 2-Gorenstein means that the dual of the regular module $D(A)$ has a projective presentation $P_1 \rightarrow P_0 \rightarrow D(A) \rightarrow 0$ with $P_1$ having injective dimension bound by 1. ($P_0$ is always projective-injective for Nakayama algebras)

Here a link for the program I used to test things (copy all programs, and the finaltest program does the job then. 1 means the Kupisch series is 2-Gorenstein and 0 means it is not): https://docs.google.com/document/d/1U9mriuvCEE9FeXY1TfY_yJ1mi05TCdHRfppwCSwi1S8/pub

Cartan's Structure Equations VS Cartan's Method of Equivalence

Math Overflow Recent Questions - Tue, 08/08/2017 - 07:25

There have been a number of posts on related questions, such as: Geometric interpretation of Cartan's structure equations, What is the geometric significance of Cartan's structure equations? and Maurer-Cartan structure equation derivation.

While my question is related, it is I hope a bit more specific. I am trying to learn some of Cartan's methods, and getting a little confused, because they all seem to be closely related, so that differentiating between them is difficult for me.

I would like to think of Cartan's structure equations this way. You start with an adapted co-frame and apply d, then express the results in terms of old data (the co-frame), but while respecting the Lie algebra. This gives 2 new things, the connection 1-form, and torsion. We then apply d again, and express the results in terms of "old" data (maybe while respecting an underlying Lie algebra).

I am trying to make sense of this. It seems that this is the same process than the one used in Cartan's equivalence method. Am I right? So torsion is the first "invariant", which could be used to compare 2 different geometric structures locally, while curvature would be the next "invariant".

But what is the relevant EDS perhaps? It seems that we are building something recursively, so I am a little confused. Perhaps we need to go to infinity, to see the whole structure, right? As in, using infinity-structures, like Urs Schreiber seems to be suggesting, in the second link above. Can someone please comment or answer my questions?

Edit: after some thinking, and reading a good chunk of Olver's book "Equivalence, Invariants and Symmetry", here is my current understanding of Cartan's structure equations. Let's say you have a Riemannian manifold $(M,g)$, and let $(\theta^i)$, for $1 \leq i \leq m$, with $m=\dim M$, be a smooth local orthonormal coframe. Applying $d$ to the coframe gives our first set of "invariants" (or perhaps I should write $O(m)$-invariants). That the first set of "invariants" is nothing but the Levi-Civita connection is the meaning of the first structure equations. We then apply $d$ a second time, and get a second set of "invariants". That this second set of invariants can be broken in 2 parts, the first quadratic in the Levi-Civita connection and the second one nothing but the curvature of $g$, is the content of Cartan's second structure equation.

Gap in Przytycki's computation of the skein module of links in a handlebody?

Math Overflow Recent Questions - Tue, 08/08/2017 - 02:28

I am reading the paper [1], where the author proves that the skein module of links in a handlebody $F\times I$ has a free basis given by products $D_1 \cdots D_n$ where each $D_i$ is the closure of $v_i\in \pi_1(F)$, $v_i$ is the smallest length lexicographically smallest representative of its conjugacy class and $v_1\leq v_2\leq\cdots\leq v_n$. Besides several instances where the author makes a vague argument which presumably can be fixed using diamond lemma, I am stuck in the point where he proves that such products span the skein module.

The only place devoted to this issue is the second paragraph of "Proof of Theorem 2.11", p. 333. He says that, as an algebra both the skein module $\mathcal{S}(F\times I)$ and the symmetric algebra over the span of conjugacy classes of the fundamental group $S(R\hat{\pi}^\circ)$ are generated by the representatives of conjugacy classes of $\pi_1(F)$, hence the claim. But the map between these is not an algebra homomorphism, so this argument does not apply.

I don't know how to fix this gap. Naively one would think that induction on the number of crossings would work. But here is the problem. We need to be able to do two things: 1) switch the order of components, 2) change a representative of a component (i.e. conjugate the element $v_i\in\pi_1(F)$ to make it lexicographically smaller). Now the problem with these two operations is that they behave well with respect to different invariants. 1) works up to diagrams with smaller number of crossings, 2) works up to diagrams whose components have words of smaller lengths (see Lemma 1.7). Clearly 1) messes up the maximal length, indeed, usually the left-overs will have words whose lengths are sums of lengths of what we start with. On the other hand, 2) involves performing some isotopies. Even if the number of self-crossing of the component does not go up under such isotopies, the number of crossings with other components may increase. So we are chasing our own tail here.

UPDATE: First note that the question is about modules over the polynomial ring $\mathbb{Z}[v,v^{-1},h]$, not over the field of fractions. It turns out the question is not that easy. I did some experiments and it turns out the statement is actually false in almost all cases, except as stated by the author. For instance, if the surface is not planar, i.e. for the punctured torus it is false. If it is planar, i.e. a disk with several disks removed, and if the order of generators is different, or the choice of generators is different, it is false. The order of generators plays a role in saying what's lexicographically smaller. For instance, take a disk with $2$ disks removed. Suppose the generators of the fundamental group are $x$ going around one puncture, and $y$ going around both punctures. If the order on the generators is $x<y<y^{-1}<x^{-1}$, then the statement is false. It still seems to be true if the order of generators is as the author describes, namely $x<x^{-1}<y<y^{-1}$. Why?

[1] Przytycki, J. (1992). Skein module of links in a handlebody. Topology '90 (pp. 315-342).

Minimal normal subgroups of finite groups

Math Overflow Recent Questions - Mon, 08/07/2017 - 22:11

Let $G$ be a finite group and $p$ be a prime. Suppose that every minimal normal subgroup of $G$ is isomorphic to $\mathbb{Z}_{p}$. What possible structures does $G$ have?

Maximal subgroups of finite simple groups isomorphic to $\mathbb{Z}_{p}\rtimes\mathbb{Z}_{q}$

Math Overflow Recent Questions - Mon, 08/07/2017 - 17:30

Let $G$ be finite simple group. Suppose that there exist a minimal subgroup of $G$ say $L$ isomorphic to $\mathbb{Z}_{p}$ and a maximal subgroup of $G$ say $M$ isomorphic to $\mathbb{Z}_{p}\rtimes\mathbb{Z}_{q}$ for some primes $p$ and $q$ such that $M$ is the only nontrivial proper subgroup of $G$ containing properly $L$. If $L'$ and $M'$ are some other subgroups of $G$ isomorphic to $\mathbb{Z}_{r}$ and $\mathbb{Z}_{r}\rtimes\mathbb{Z}_{s}$ for some primes $r$ and $s$ with same conditions as $L$ and $M$, then show that $L\cong L'$ and $M\cong M'$.( i.e. show that $p=r$ and $s=q$).

projection to the scheme

Math Overflow Recent Questions - Mon, 08/07/2017 - 17:03

Let $A$ be an $k$-affinoid algebra. Let $X=M(A)$ be the affinoid space associated to $A$ in the sense of Berkovich. There exists a natural morphism $\pi:X\to Y:=Spec(A)$ which sends $x$ to $ker (|\cdot|_x)$. In the book "Spectral theory and analytic geometry over non-archimedean fields" of Berkovich, he say that the functor $\mathcal{F}\mapsto\pi^*\mathcal{F}$ from the category of $\mathcal{O}_Y$-module to $\mathcal{O}_X$-module is exact and faithful. I don't know how to show that it is faithful.

On the proof of a normal form theorem for ordinal (primitive) recursion

Math Overflow Recent Questions - Mon, 08/07/2017 - 16:34

Consider the following statement (which follows easily from various results found in the literature):

(†) There exists a primitive recursive (“p.r.”) relation $T$ on the ordinals such that, if $(f_e)_{e<\omega}$ is a standard numbering of the p.r. functions of one variable on the ordinals, we have $f_e(x)=y$ iff $\exists z.T(e,x,y,z)$; moreover, there then exists such a $z$ which is less than the smallest p.r.-closed ordinal $\geq x$.

One straightforward consequence of (†) is a Kleene normal form theorem for $\alpha$-recursion: there exists a p.r. relation $T'$ on the ordinals such that, if $(\varphi_e)_{e<\omega}$ is a standard numbering of the partial recursive functions of one variable on the admissible ordinal $\alpha$, we have $\varphi_e(x)\simeq y$ iff $\exists z<\alpha.T'(e,x,y,z)$. (One straightforward consequence of that is that there exists a “universal” partial recursive $g$ on $\alpha$ with the property that $g(e,x) \simeq \varphi_e(x)$.)

Now every proof of (†) that I was able to find boils down to something like this: if $f_e(x)=y$ then for $\beta$ large enough (larger than all the intermediate computation values) we have $L_\beta \models f_e(x)=y$, and “$L_\beta \models f_e(x)=y$” is a p.r. relation of the ordinals $e,x,y,\beta$ because it is a p.r. relation of the sets $e,x,y,\beta$ and p.r. relations on ordinals and on sets that happen to be ordinals coincide.

This proof is explicit, in the sense that it actually gives $T$, but the $T$ in question seems rather insanely complicated (as a p.r. relation on ordinals) because of the process of converting a p.r. relation on sets to one on ordinals and because of the route through formulas and the $L_\beta$.

Question: Can the statement (†) above be proved entirely at the level of p.r. functions and relations on the ordinals? Variant: Can we give an explicit $T$ that is reasonably short?

In the case of ordinary recursion, it is not too difficult. What I would like to understand is whether there is some reason why the transfinite ordinal case should be harder or whether it is just an artefact of the way things are written in the literature.

Motivation: Partially from trying to get a better understanding of this question I asked recently; partially from thinking about how, if $\alpha$-recursion is viewed as a transfinite programming language, one would proceed to write an “interpreter” for the language in the language itself (=universal function).

Pages

Subscribe to curious little things aggregator