User gro-tsen - MathOverflow

Answer by Gro-Tsen for An exercise about Tor

2013-04-15T13:31:38Z

Consider the short exact sequence $0 \to I \to A \to A/I \to 0$ . Tensoring with the $A$-module $A/J$ gives the long exact sequence $\cdots \to 0 \to \mathrm{Tor}_2^A(A/I,A/J) \to \mathrm{Tor}_1^A(I,A/J) \to 0 \to \mathrm{Tor}_1^A(A/I,A/J) \to I/IJ \to A/J \to (A/I)\otimes_A (A/J)\to 0$ . Here I use the fact that $A$ is a free $A$ module, so all its Tor's are 0. The right part of the sequence gives the first equality you mention. The left part identifies $\mathrm{Tor}_2^A(A/I,A/J)$ with $\mathrm{Tor}_1^A(I,A/J)$ .

Now tensor $0 \to J \to A \to A/J \to 0$ with the $A$-module $I$. This gives $\cdots \to 0 \to \mathrm{Tor}_1^A(A/J,I) \to J\otimes_A I \to I \to I/IJ \to 0$ , so $0 \to \mathrm{Tor}_1^A(A/J,I) \to J\otimes_A I \to IJ \to 0$ , and since Tor and $\otimes$ are symmetric, $\mathrm{Tor}_2^A(A/I,A/J)$ is the kernel of $I\otimes_A J \to IJ$ .

Looking for a copy of Leo Harrington's unpublished notes on the first nonprojectible ordinal

2013-02-25T14:29:08Z

Sometime around 1975, Leo Harrington wrote a set of notes, apparently 13 pages long, entitled Kolmogorov's $R$-operator and the first nonprojectible ordinal. I do not know how widely they were circulated (or if they were ever available from the UCB library or anywhere).

From what I understand, these notes relate recursion on the first stable ordinal in the first nonprojectible to recursion in a certain explicitly defined type-3 functional. A more precise statement is given in Thomas John's paper “Recursion in Kolmogorov's $R$-operator and the ordinal $\sigma_3$” (J. Symbol. Logic 51 (1986) 1–11), but the proof is not reproduced there. A related but slightly different result of Harrington's, with a different type-3 operator, is quoted (as example 4.10) by Stephen Simpson's “Short course on Admissible Recursion Theory” (355–390 in: Fenstad &al. eds., Generalized Recursion Theory II (Oslo 1977), North-Holland 1978).

I'd very much like to see a copy of these notes, or a proof of any closely related result (e.g., the one quoted by Simpson's paper mentioned above).

The author has been kind enough to see if he can find them, but he isn't too optimistic. I've also written to a number of people who worked in the subject around that time (Sacks, Shore, Simpson and Soare), but without success. So I now turn to MO in the hope that someone has heard of these notes or knows where a copy might be found.

[Xref: link to meta thread]

PS: While I'm aware that offering prizes other than reputation points is frowned upon on MO, if someone should go through the (real-world!) trouble of copying, scanning or mailing these notes for me, I think it would be appropriate that I should respond with a small (real-world!) token of thanks, like an Amazon gift card or something. :-)

Explicit equation of Dickson invariant / quasideterminant / special orthogonal group over the integers

2012-11-23T15:47:29Z

Consider $2n$ coordinates $x_1,\ldots,x_n,y_1,\ldots,y_n$ and the quadratic form $q = \sum_{i=1}^n x_i y_i$. Now call $O(q,A)$ (orthogonal group of $q$) the group of $(2n)\times(2n)$ matrices, with coefficients in a commutative ring $A$, which preserve $q$. (This is an algebraic group over $\mathop{\mathrm{Spec}}\mathbb{Z}$.) When $A$ is a field of characteristic $\neq 2$, the determinant restricted to $O(q,A)$ takes its values in ${\pm 1}$, its kernel $O(q,A) \cap SL(2n,A)$ defines a subgroup $SO(q,A)$ of index $2$. When $A$ is a field of characteristic $2$, the determinant is identically $1$ on $O(q,A)$ but there is still a subgroup of index $2$, which one might still denote $SO(q,A)$, defined by the so-called "Dickson invariant", also known as quasideterminant or pseudodeterminant, and it is relatively straightforward to give an explicit polynomial in the coefficients of $A$ which defines an equation of $SO(q,A)$ inside $O(q,A)$ (see, Dickson's book, Linear Groups, theorem 205 on page 206).

Now for an arbitrary ring $A$, there is still a subgroup $SO(q,A)$ of $O(q,A)$, which is the kernel of a morphism $\deg$ of $O(q,A)$ to the group $(\mathbb{Z}/2\mathbb{Z})(A)$ of idempotents of $A$ (so, when $A$ is connected, $SO(q,A)$ is a subgroup of order $2$) natural in $A$ and which coincides with $\frac{1}{2}(1-\det)$ when $2$ is invertible in $A$ and with Dickson's invariant when $2$ is zero in $A$. This is due to H. Bass ("Commutative Algebras and Spinor Norms over a Commutative Rings", Amer. J. Math. 96 (1974), 156–206).

Concretely, this means that there exists a polynomial $\deg$ in $4n^2$ variables over $\mathbb{Z}$ such that, modulo the ideal $I$ of relations defining $O(q,A)$, we have $\deg^2 = \deg$ and $\det = 1-2\deg$. And $I_0 := I+(\deg)$ is the ideal defining $SO(q,A)$.

My question is: can one give an explicit expression of $\deg$ (as a polynomial in $4n^2$ variables), or perhaps an explicit set of equations of $SO(q,A)$ (e.g., Gröbner basis of $I_0$ for some term order)? (At least for the particular quadratic form $q = \sum_{i=1}^n x_i y_i$ if not in general.)

Answer by Gro-Tsen for cryptographic primitive process

2013-01-24T09:35:44Z

The Threefish block cipher, for example, is well equipped to do all the things you mention (it's a symmetric cipher which was built for the purpose of creating the Skein hash function, a SHA-3 finalist; the Skein paper explains how it can easily be used as a MAC and RNG).

That being said, I don't think MathOverfow was the right place to ask this particular question.

Answer by Gro-Tsen for Is equality of terms for "real" numbers with roots, logarithm, exponential, sin, cos, and other trigonometric operations decidable with a Turing-machine?

2013-01-15T18:50:33Z

Assuming Schanuel's conjecture, the answer seems to be yes, according to Daniel Richardson, "How to recognize zero" J. Symbolic Comput 24 (1997), 627–645 (doi:10.1006/jsco.1997.0157, available here online), in which the author defines a set of numbers he calls "elementary", which is algebraically closed and closed under exponential, logarithm and trigonometric functions, and for which equality is decidable (again, assuming Schanuel's conjecture).

Answer by Gro-Tsen for Examples of interesting false proofs

2013-01-14T16:10:52Z

Here's a nice false proof of the continuum hypothesis.

Consider the rational numbers $\mathbb{Q}$ as a totally ordered field. We can add an indeterminate $T_0$ and make it positive but infinitely small (i.e., smaller than positive any element of $\mathbb{Q}$), that is, order $\mathbb{Q}(T_0)$ by lexicographic order of the Laurent series expansion at $0$. Then we can add another indeterminate $T_1$ and make it positive but infinitely small (i.e., smaller than any positive element of $\mathbb{Q}(T_0)$). This process can be iterated transfinitely and we can add $\aleph_1$ indeterminates $T_\iota$ for $\iota<\omega_1$, each infinitely smaller than all the previous ones. The resulting field $K = \mathbb{Q}(T_\iota)$ has cardinality $\aleph_1$ as is easy to show. Now any positive sequence converging to $0$ in $K$ must be eventually constant because it has to cross uncountably many $T_\iota$. So any Cauchy sequence in $K$ is eventually constant. So any Cauchy sequence in $K$ is convergent. So $K$ is complete. But since $K$ contains $\mathbb{Q}$, it contains $\mathbb{R}$. So we have a set of cardinality $\aleph_1$ containing $\mathbb{R}$, which proves the continuum hypothesis.

(The error, of course, is simply that the notion of "completeness" is wrong and its use is nonsense. But if you tell it quickly enough, many people will fall for it.)

Does Taranovsky's system of ordinal notations make sense?

2013-01-14T01:26:40Z

Dmytro Taranovsky has a Web page on which he claims to define a system of ordinal notations strong enough to provide an ordinal analysis of full second-order arithmetic. I think (perhaps unjustly) that this claim is suspicious, since from my passing acquaintance with the subject I seem to understand that the state of the art of ordinal analysis was around $\Pi^1_2$ -comprehension (e.g., Jan-Carl Stegert's doctoral dissertation building on work by Michael Rathjen), the ordinal notation systems involved are considerably more complex (reflection instances, collapsing hierarchies), and Taranovsky mentions none of this. On the other hand, a superficial look at his page does seem to make some kind of sense, and my interest in the subject is to choose the largest possible system of ordinal notations which isn't too fastidious to implement on a computer (i.e., I'm not concerned with the proof-theoretic aspect).

So before I decide to read it in great detail or not, I'd like an expert's opinion: what is to be thought of Taranovsky's ordinal notation systems? (Might they define an ordinal which is not as large as claimed? Or perhaps which could be as claimed but would be very difficult to analyse?)

Arithmetic strength of Peano + the Howard ordinal

2012-12-08T16:46:58Z

Consider the theory $\mathrm{PA}+\mathrm{BHO}$ consisting of first-order Peano arithmetic ( $\mathrm{PA}$ ) enriched by an axiom scheme which allows well-founded induction up to any ordinal less than [a standard recursive presentation of] the Bachmann-Howard ordinal. More precisely, let $\prec$ be the explicit well-ordering on $\mathbb{N}$ which results from, say, this description and which has order type of the Bachmann-Howard ordinal, and add to Peano's axioms an axiom scheme ( $\mathrm{BHO}$ ) which for every formula $\phi$ and every $n$ asserts that

$(\forall m\prec n((\forall p\prec m(\phi(p)))\Rightarrow\phi(m)))\Rightarrow\forall m\prec n(\phi(m))$

These are supposed to be theorems of Kripke-Platek set theory ( $\mathrm{KP}$ ), whose proof ordinal is the B-H ordinal, so—unless I badly messed things up—all theorems of $\mathrm{PA}+\mathrm{BHO}$ are arithmetical consequences of $\mathrm{KP}$ . My question is whether the converse holds: can every arithmetical theorem of $\mathrm{KP}$ be proved in $\mathrm{PA}+\mathrm{BHO}$ ? If not, what would a counterexample be?

The naïve idea I have is to somehow define the constructible hierarchy (up to and excluding the Bachmann-Howard ordinal), or α-recursion, in $\mathrm{PA}+\mathrm{BHO}$ but I can't imagine how it would work without some kind of second-order language. I'm not asking for details, just a general idea of how things might work (if they do).

More generally, a broader question should be something like: in what respect can "artificially" increasing the proof ordinal of some theory give it the same arithmetical strength as some stronger theory with that proof ordinal. So if there's some way to modify my question to give this, I'd like to know.

Answer by Gro-Tsen for Proof strength of Calculus of (Inductive) Constructions

2012-12-08T17:07:12Z

I just stumbled upon this old question by chance, and I thought maybe you should have a look at Alexandre Miquel's thesis if you haven't already done so (and if you can read French). Conjecture 9.7.12 on page 329 (331 of PDF) suggests that the Calculus of Constructions with universes should be equiconsistent with Zermelo set theory with universes (assuming I'm not misreading—I'm easily confused between all these theories), which at least gives some lower bound.

Various notions of Turing reduction for partial functions

2012-11-16T22:14:50Z

If $f$ and $g$ are partial functions $\mathbb{N} \to \mathbb{N}$ , define six preorder relations $f \preceq g$ as follows:

$f \mathop{\preceq_{\mathrm{S}}} g$ ("$f$ is strict/Sasso reducible to $g$") when there exists a Turing machine with oracle that, when given $g$ as oracle, computes $f$ (with the convention that whenever the computation calls $g$ on an undefined value, it does not terminate; and by "computes $f$", we mean that the computation terminates on input $n$ exactly when $f(n)$ is defined and, when this is the case, it returns $f(n)$);
$f \mathop{\preceq_{\mathrm{N}}} g$ ("$f$ is nondeterministic/enumeration reducible to $g$") when there exists a nondeterministic Turing machine with oracle that, when given $g$ as oracle, computes $f$ in the sense that there is at least one terminating branch of computation on input $n$ exactly when $f(n)$ is defined and, when this is the case, all terminating branches return $f(n)$ (again with the convention that whenever a branch of computation calls $g$ on an undefined value, it does not terminate);
$f \mathop{\preceq_{\mathrm{W}}} g$ ("$f$ is weak reducible to $g$") when there exists a nondeterministic Turing machine with oracle as above, but with the additional constraint that whatever the oracle $h$ (a partial function $\mathbb{N} \to \mathbb{N}$ ) given to it, and whatever the input $n$, all terminating branches of computation (if there are any) must return the same value, i.e., the machine defines a "recursive operator" on partial functions $h$;
$f \mathop{\preceq_{\mathrm{S}*}} g$ , $f \mathop{\preceq_{\mathrm{N}*}} g$ and $f \mathop{\preceq_{\mathrm{W}*}} g$ (perhaps call this "subreducible"?) mean that there exists a partial function $\hat f$ such that $\hat f \mathop{\preceq_{X}} g$ (for the corresponding subscript $X$ without the asterisk) and $f \subseteq \hat f$ (in other words, the Turing machine is permitted to compute more values than $f$).

(From what I understand, $\mathop{\preceq_{\mathrm{S}}}$ was defined by Leonard Sasso and $\mathop{\preceq_{\mathrm{N}}}$ is supposed to be equivalent to enumeration reducibility as defined in §9.7 of Roger's book on Recursive functions.)

Each of these six relations is reflexive and transitive, and is equivalent to ordinary Turing reduction when $f$ and $g$ are, in fact, total functions. So we get six different notions of "partial Turing degree" (S-degrees, N-degrees, etc.), all of which contain a subset isomorphic to the usual (total) Turing degrees. Also, $f \mathop{\preceq_{\mathrm{S}}} g$ implies $f \mathop{\preceq_{\mathrm{W}}} g$ which in turn implies $f \mathop{\preceq_{\mathrm{N}}} g$ and none of these implications can be reversed (Rogers §13.6, th. XIX); obviously each $f \mathop{\preceq_{X}} g$ implies $f \mathop{\preceq_{X*}} g$ , and none of the converse (consider $g=0$ and $f$ the restriction of $g$ to a non recursively enumerable set). Furthermore, there exist N-degrees (and consequently W-degrees and S-degrees) which are do not contain a total function (=which are not total Turing degrees): see Rogers, §13.6, th. XVIII.

But my question is mostly about $(X*)$ -degrees:

do they have a standard name? have they been studied?
is it even true that there exist $(X*)$ -degrees which do not contain a total function, as it is true for the $X$-degrees?
are $\mathop{\preceq_{\mathrm{S}*}}$ and $\mathop{\preceq_{\mathrm{N}*}}$ distinct?

Does the Fourier series of an $L^1$ function converge to the function weakly in $L^1$?

2012-10-29T13:29:54Z

Let $f$ be a periodic $L^1$ function, and $S_n[f]$ the $n$-th partial sum of its Fourier series. I am aware that $S_n[f]$ might not converge toward $f$ in $L^1$ (i.e., in norm). However, does it at least converge weakly? In other words, is it true that for every $L^\infty$ function $h$ (thus defining a continuous linear form on $L^1$), the integral of $S_n[f]\cdot h$ on one period converges to the integral of $f\cdot h$?

I believe the question can be rephrased as follows: if $g = f*h$ is the convolution of an $L^1$ function and an $L^\infty$ function, is it true that the Fourier series of $g$ converges pointwise to $g$? (Clearly $g$ is a continuous function, but it is well known that this does not suffice. However, I see no reason why the convolutions of $L^1$ and $L^\infty$ functions should exhaust the continuous functions.)

If the answer is negative, is there some nice subspace of $L^\infty$ such that for all $h$ in this subspace the property holds?

Comment: More generally, one could ask, "for all functions $f$ in <some space>, and all linear forms $h$ in <some subspace of the dual space>, is it true that the Fourier series of $f$ converges to $f$ when tested against $h$?" For instance, if $f$ ranges over finite signed Borel measures on the circle and $h$ over continuous functions, the answer is negative (take $f$ to be a Dirac measure at $0$ and $h$ such that the Fourier series of $h$ does not converge at $0$); whereas if $f$ ranges over Schwartz distributions and $h$ over $C^\infty$ functions then the answer is positive (because $f*h$ will be smooth). Is there something intelligent to be said along those lines?

Various definitions of recursion from ordinal machines

2012-10-05T19:19:40Z

Background: I'm trying to get an intuitive understanding of α-recursion and related concepts in higher recursion theory. Once nice book is Peter Hinman's Recursion-Theoretic Hierarchies, available here (open access), and specifically chapter VIII which is intuitively appealing because he presents recursion on ordinals by directly constructing recursive functions rather than going through the constructible hierarchy. However, this also suggests a number of questions which he does not fully answer, and I'm hoping someone can help me get a clearer picture.

Let me make the following definitions, which I state informally but should be straightforward to formalize:

A primitive $(\infty,0)$ -machine is given by a program in a programming language, all of whose variables are ordinals, which can do the following:
- Basic operations (assigning variables to other variables or to any natural number, comparing ordinals, computing the successor, predecessor, sum and product, and constructing/deconstructing finite tuples of ordinals as ordinals using the standard bijection between $\mathit{Ord}^2$ and $\mathit{Ord}$ ; part of this is probably redundant).
- Looping over an ordinal $\alpha$ which has been computed in advance (i.e., in a variable): by this I mean that a subprogram will be iterated for all ordinals $\beta<\alpha$ ; to define the value of a variable at limit times $\beta$ , we declare it to be the lim sup of variables up to this point. These loops always terminate. (Of course, it doesn't hurt to allow the program to interrupt the loop early.)
- Recursive function calls are not allowed (all subroutines must be defined prior to where they are used). Because of this, a primitive $(\infty,0)$ -machine always terminates, whatever its inputs.

Comment: Unless I got my definition horribly wrong, a primitive $(\infty,0)$ -machine, when given natural numbers as input, can only produce a natural number as output, and the functions $\omega^r \to \omega$ thus defined are exactly the primitive recursive functions as usually defined.

A general $(\infty,0)$ -machine is similar to a primitive $(\infty,0)$ -machine, except that recursive function calls are allowed: unless I am mistaken, this is equivalent to allowing a "universal" machine (i.e., a general $(\infty,0)$ -machine can compute the value returned by another general $(\infty,0)$ -machine on any specified input). Programs can now fail to terminate (and the precise (program,input)↦output partial function is defined as the smallest which satisfies the requirements).

This definition is supposed to coincide with what Hinman's aforementioned book calls a " $(\infty,0)$ -partial recursive function" (with or without parameters as are passed to the machine): see p. 377. If it does not coincide, I must have made a mistake. The difference between "general" and "primitive" is supposed to be clause (2) in definition 1.1 on p. 376 of Hinman's book.

Comment: Again, when given natural numbers as input, a general $(\infty,0)$ -machine can only produce natural numbers as output (or fail to terminate), and the partial functions $\omega^r \to \omega$ thus defined are exactly the usually defined general recursive (partial) functions.

Lastly, if $\lambda$ is any ordinal (fixed in advance), a primitive $(\infty,\lambda)$ -machine and a general $(\infty,\lambda)$ -machine are the same as a primitive $(\infty,0)$ -machine and a general $(\infty,0)$ -machine respectively, but with an additional construct:
- We can also loop over all ordinals $\beta<\lambda$ ; the difference with the previously defined type of loop (apart from the fact that here $\lambda$ is fixed in advanced rather than computed from the input) is that if the program does not interrupt the loop early (i.e., issue a break at some time $\beta<\lambda$ ), it does not terminate.

Again, general $(\infty,\lambda)$ -machines are supposed to define the same thing as Hinman's " $(\infty,\lambda)$ -partial recursive function".

Note: If $\kappa$ is recursively regular (=admissible), then the total functions computed by general $(\infty,\kappa)$ -machines on inputs $<\kappa$ , and possibly using extra parameters (=constants) $<\kappa$ , are exactly the $\kappa$ -recursive total functions $\kappa^r \to \kappa$ (viz., those which are $\Delta^1_1$ -definable over $L_\kappa$ ). I believe that primitive $(\infty,\kappa)$ -machines also compute the same functions in this context (because recursivity can be simulated by a loop over ordinals $<\kappa$ ), but that's not really important.

Now basically what I'd like to understand is what can be computed by a general $(\infty,0)$ -machine (=general 0-machine), or even a primitive $(\infty,0)$ -machine, if it is allowed a given ordinal $\alpha$ as input. So here is my

MAIN QUESTION: Let $\alpha$ be an ordinal, and let $\kappa$ be the smallest recursively regular (=admissible) ordinal $>\alpha$ . Is it true that any total function $\kappa^r \to \kappa$ which can be computed using a general $(\infty,\kappa)$ -machine without extra parameters (=constants) can, in fact, be computed using a general $(\infty,0)$ -machine from the only parameter $\alpha$ ?

This question is motivated by the fact that if given the parameter $\omega$ , a general $(\infty,0)$ -machine can clearly compute all hyperarithmetic functions $\omega^r \to \omega$ , it can compute any ordinal $<\omega_1^{CK}$ , and it seems as though it can compute the same things as a general $(\infty,\omega_1^{CK})$ -machine.

A positive answer to this question would imply, among other things, that the ordinals stable under general $(\infty,0)$ -recursive functions are exactly the recursively regular ordinals and limits thereof.

BONUS QUESTION: With the same notations, is it true for $\gamma<\kappa$ that any total function $\gamma^r \to \gamma$ which can be computed using a general $(\infty,\kappa)$ -machine without extra parameters (=constants) can, in fact, be computed using a primitive $(\infty,0)$ -machine from the only parameter $\alpha$ ?

More generally, I'm interested in any statements along the same lines that can help clear the relation between these various notions of ordinal machines.

Constructing the surreal numbers as iterated Hahn series

2011-10-30T18:49:49Z

A theorem due to N. Alling (Foundations of Analysis over Surreal Number Fields, §6.55) states that the surreal numbers are isomorphic, as an ordered and valued field, to the field of Hahn series with real coefficients and value group the surreal numbers themselves. There is also a restricted version, which I'll refer to in order to avoid the (IMHO uninteresting) foundational difficulties in dealing with classes: if $\kappa$ is a regular uncountable cardinal, the set $\mathrm{No}_\kappa$ of surreal numbers with birth date $<\kappa$ is isomorphic to the field of Hahn series of length $<\kappa$ with real coefficients and exponents in $\mathrm{No}_\kappa$ itself (in the indeterminate $\frac{1}{\omega}$ ).

Upon reading this, I thought to myself, “well, this is nice, this means the surreal numbers can be given a construction as iterated Hahn series, something along the lines of: start with the reals, take the Hahn series over that, then take the Hahn series over that (as value group), repeat transfinitely, and voilà, surreal numbers”. Unfortunately, it seems I was being a bit naïve there.

Let us define $F_0 = \mathbb{R}$ and inductively $F_{\alpha+1}$ to be the field of Hahn series of length $<\kappa$ with real coefficients and exponents in $F_\alpha$ (the indeterminate being written $\frac{1}{\omega}$ ); and for $\delta$ a limit let $F_\delta = \bigcup_{\alpha<\delta} F_\alpha$ with the obvious embeddings. Then if I am not mistaken, $F_\kappa$ is indeed isomorphic to Hahn series of length $<\kappa$ over itself, it is indeed an $\eta_\xi$ field for $\kappa=\omega_\xi$ , of cardinality $2^{<\kappa}$ , just like $\mathrm{No}_\kappa$ , and it is quite conceivable (I didn't check) that the two are isomorphic (as ordered—and valued—fields over $F_0 = \mathbb{R}$ ). But this can't possibly respect the map $x \mapsto \omega^x$ because in $\mathrm{No}_\kappa$ the latter has plenty of fixed points whereas in $F_\kappa$ it has none. So this construction is “wrong” in that it doesn't explain surreal numbers properly.

Thus, my question is: is there some variant of this construction that will succeed in constructing $\mathrm{No}_\kappa$ , including its map $x \mapsto \omega^x$ ? Perhaps the answer depends on what is done at limit ordinal steps, but I'm rather confused so I wish someone could clear up the confusion.

Every real function has a dense set on which its restriction is continuous

2011-08-12T23:28:54Z

The title says it all: if $f\colon \mathbb{R} \to \mathbb{R}$ is any real function, there exists a dense subset $D$ of $\mathbb{R}$ such that $f|_D$ is continuous.

Or so I'm told, but this leaves me stumped. Apart from the rather trivial fact that one can find a dense $D$ such that the graph of $f|_D$ has no isolated points (by a variant of Cantor-Bendixson), I don't know how to start. Is this a well-known fact?

Maximal domain of holomorphy of a series

2011-08-10T15:02:11Z

Let $(a_n)$ be an enumeration of all complex numbers with rational real and imaginary parts which are not contained in the closed unit disk (i.e., $\{z\in\mathbb{Q}[i] \colon |z|>1\}$ ).

Let $(c_n)$ be a decreasing sequence of real numbers converging “rapidly” toward zero. (I'll say more on “rapidly” in a moment.)

Define $F(z) = \sum_{n=0}^{+\infty} \frac{c_n}{z-a_n}$ for all $z$ such that this series converges. Since by “rapidly” I mean at the very least that $\sum_{n=0}^{+\infty} c_n$ converges, $F$ is defined at least on the open unit disk $U := \{z \colon |z|<1\}$ . Let $f(z) = F(z)$ on $U$. Because the series converges uniformly on every compact domain in $U$, the function $f$ is holomorphic on $U$.

‣The question: possibly discussing on the meaning of “rapidly”, is it possible that $f$ should have a holomorphic extension on some larger (connected) open set than $U$? (And, if it is possible, is there any relation between the values of that extension with those of $F$ for points outside the unit disk where it is defined?)

Possible assumptions for “rapidly” might be: •the series for $F$ (or possibly even all its derivatives) converges uniformly on the closed unit disk; •or perhaps: $c_n = o(n^{-\alpha})$ for $\alpha > \frac{3}{2}$ say (if my quick computation is correct, this implies that the series for $F$ converges outside a set of Lebesgue measure zero).

[The reason this question came up is that a student asked me for an example of a holomorphic function on the open unit disk which extends continuously to the closed unit disk but not to a larger domain of holomorphy, and my rather stupid reaction was to try to construct it in this way. (Instead, I should really have invoked the Ostrowski–Hadamard gap theorem.)

I asked this question years ago on sci.math.research and I suggested this problem to a number of people, none of whom was able to provide a satisfactory answer.]

Comment by Gro-Tsen

2013-04-02T21:55:56Z

Just saw this. Thanks a lot to you and others who helped in finding these notes!

Comment by Gro-Tsen

2013-01-21T10:41:52Z

There are two different questions one could ask: one is whether Serre's proof of GAGA uses the axiom of Choice, another is whether one can find a metamathematical argument that GAGA must be provable without Choice (an argument similar to the well-known fact that "any arithmetical statement that is provable in ZFC is provable in ZF alone"). I'm pretty convinced the answer of the second question is "yes" (perhaps something like "encode the analytic sheaf as a real number $x$ and argue in $L[x]$ where Choice holds"). But then, that's not what you asked.

Comment by Gro-Tsen

2013-01-20T15:05:12Z

I'm not sure I understand what the question is, but $0^\#$, if it exists, is a hereditarily ordinal-definable set of ordinals (indeed, a $\Pi_1$-definable set of integers) that isn't constructible (hence not ordinal machine computable).

Comment by Gro-Tsen

2013-01-15T22:34:57Z

@Ben Crowell: The cited article by Richardon does give an explicit algorithm, and claims that it was implemented and is actually usable.

Comment by Gro-Tsen

2013-01-15T18:55:45Z

Note: I added the "lo.logic" and "algorithms" tags to the question.

Comment by Gro-Tsen

2012-11-25T16:21:33Z

@Matthieu Romagny: The equations of $O_{2n}$ are "explicit enough" in the sense that I can easily write down equations for all $n$, whereas for $SO_{2n}$ I don't know how to do this. I agree that there's no "canonical" choice for deg (it's only well-defined modulo the equations of $O_{2n}$), but I'm not asking for something canonical, I'm asking for something explicit, e.g., I choose $n=10$, can you write down a polynomial in $400$ variables which represents deg? The best I was able to do with Sage was $n=2$ (which doesn't inspire an obvious generalization).

Comment by Gro-Tsen

2012-11-22T00:05:56Z

@Joel David Hamkins: I do, but I don't see which sentence could be ambiguous. @François G. Dorais: I didn't realize that making a question CW implied that all answers also automatically became CW: I thought it just meant anybody could edit the question. My bad. Apologies to Dan Turetsky for not getting points for his nice answer.

Comment by Gro-Tsen

2011-11-06T12:28:07Z

Thanks for pointing out this nice result, which answers a few questions I had in mind. However, I don't think it answers my original question, because the serious problem is for surreals whose length is precisely an epsilon number (e.g., $x\in\mathbf{No}(\varepsilon_0^\omega)$ such that $x=\omega^-x$), and which cannot be "explained" in terms of Hahn series using simpler surreals (Conway calls such surreals "irreducible"). But maybe there is no satisfactory answer to my question.

Comment by Gro-Tsen

2011-10-21T21:53:49Z

I believe the question is equivalent to this: consider the simplicial complexes whose vertices are the (irreducible) curves in $\mathbb{C}^2$ (resp. $\mathbb{C}^2\setminus\{(0,0)\}$ ) with a face connecting certain curves when they have a nonempty intersection — are these two structures isomorphic? It may not be simpler that way, but it puts the emphasis on curves, and also suggests looking at it from the model-theoretic point of view: the back-and-forth argument can be phrased by saying in terms of an Ehrenfeucht-Fraïssé game between these structures. (And I'm running out of space.)

Comment by Gro-Tsen

2011-08-17T15:20:15Z

@Cole → I don't think that's what you meant (maybe I misunderstood): $f$ itself might be continuous nowhere: Blumberg's theorem only promises continuity of the restriction $f|_D$. And even concerning continuity of $f|_D$, it's not true that one can strengthen the conclusion to $D$ being comeager (=residual): I believe there exists a real function which takes every real value on any $G_\delta$ which is dense in a non-trivial interval (along the lines of [Sierpiński](matwbn.icm.edu.pl/ksiazki/fm/fm1/fm1113.pdf), replacing closed sets of positive measure by dense $G_\delta$ on interval).

Comment by Gro-Tsen

2011-08-13T23:09:55Z

Thanks for the reference! For completeness, there's a self-contained and rather nice proof (or at least nicer than Blumberg's original one) of the statement, plus an extensive discussion, in the more general setting, in chapter 8 of Goffman, Nishiura, and Waterman's book Homeomorphisms in Analysis, available online at ams.org/publications/online-books/surv54-index

Comment by Gro-Tsen

2011-08-10T22:32:24Z

@fedja → Right, I should have been more careful about the possibility of converging to $0$ (I thought a mild condition like $c_n = o(n^-\alpha)$ for $\alpha>3/2$ would automatically preclude this, but it seems my reasoning was faulty, so I don't know); I'd love to see an example. If I don't get an answer here, I'll try bothering Nikolai as you suggest. @Igor Rivin → I guess I wasn't too clear on quantifiers. I would be asking: (given some meaning of “rapidly”) does there exist $(c_n)$ decreasing rapidly and does there exist some enumeration $(a_n)$ such that $f$ can be exended?

User gro-tsen - MathOverflow

Answer by Gro-Tsen for An exercise about Tor

Looking for a copy of Leo Harrington's unpublished notes on the first nonprojectible ordinal

Explicit equation of Dickson invariant / quasideterminant / special orthogonal group over the integers

Answer by Gro-Tsen for cryptographic primitive process

Answer by Gro-Tsen for Is equality of terms for "real" numbers with roots, logarithm, exponential, sin, cos, and other trigonometric operations decidable with a Turing-machine?

Answer by Gro-Tsen for Examples of interesting false proofs

Does Taranovsky's system of ordinal notations make sense?

Arithmetic strength of Peano + the Howard ordinal

Answer by Gro-Tsen for Proof strength of Calculus of (Inductive) Constructions

Various notions of Turing reduction for partial functions

Does the Fourier series of an $L^1$ function converge to the function *weakly* in $L^1$?

Various definitions of recursion from ordinal machines

Constructing the surreal numbers as iterated Hahn series

Every real function has a dense set on which its restriction is continuous

Maximal domain of holomorphy of a series

Comment by Gro-Tsen

Comment by Gro-Tsen

Comment by Gro-Tsen

Comment by Gro-Tsen

Comment by Gro-Tsen

Comment by Gro-Tsen

Comment by Gro-Tsen

Comment by Gro-Tsen

Comment by Gro-Tsen

Comment by Gro-Tsen

Comment by Gro-Tsen

Comment by Gro-Tsen

Does the Fourier series of an $L^1$ function converge to the function weakly in $L^1$?