computer science - Are there any pairing functions computable in constant time (AC⁰)

The pairing function f(a,b) = (a + b)(a + b + 1)/2 + a is the one that arises by drawing diagonals on the natural number lattice, and marching down them from upper left to lower right. See the picture here.

To compute f(a,b), one needs to perform some additions and a multiplication, which seems to be quadratic time in the length of a and b, that is, in log(a)+log(b), which would seem to be constant time in max(a,b), but I'm not sure if this would be what you meant.

In that book, it is noted that Polya has proved that any surjective polynomial pairing function is equal to this function or to its dual form f(b,a). (And someone gave a talk here at CUNY a few weeks ago on precisely this fact.) So if this function is not acceptable to you, then you will find no polynomial surjective function.

But here is another function, which seems to be a little faster to compute. Suppose that a and b are given to me in their binary representation. Now, I just interleave their binary digits, using 0's if the digits of one of them runs out. This is surely a pairing function, and I can compute it linear time of the lengths of the input.

ct.category theory - "synthetic" reasoning applied to algebraic geometry

A hyperlinked and more detailed version of this question is at

nLab:synthetic differential geometry applied to algebraic geometry.

Repliers are kindly encouraged to copy-and-paste relevant bits of their reply here into that wiki page.

The axioms of synthetic differential geometry are intended to pin down the minimum abstract nonsense necessary for talking about the differential aspect of differential geometry using concrete objects that model infinitesimal spaces.

But the typical models for the axioms – the typical smooth toposes – are constructed in close analogy to the general mechanism of algebraic geometry: well-adapted models for smooth toposes use sheaves on C ∞Ring op (the opposite category of smooth algebras) where spaces in algebraic geometry (such as schemes) uses sheaves on CRing op.

In fact, for instance also the topos of presheaves on k−Alg op, which one may think of as being a context in which much of algebraic geometry over a field k takes place, happens to satisfy the axioms of a smooth topos (see the examples there).

This raises some questions.

Quesions:

To which degree do results in algebraic geometry depend on the choice of site CRing op or similar?

To which degree are these results valid in a much wider context of any smooth topos, or smooth topos with certain extra assumptions?

In the general context of structured (∞,1)-toposes and generalized schemes: how much of the usual lore depends on the choice of the (simplicial)ring-theoretic Zariski or etale (pre)geometry (for structured (∞,1)-toposes), how much works more generally?

More concretely:

To which degree can the notion of quasicoherent sheaf generalize from a context modeled on the site CRing to a more general context. What is, for instance, a quasicoherent sheaf on a derived smooth manifold? If at all? What on a general generalized scheme, if at all?

Closely related to that: David Ben-Zvi et al have developed a beautiful theory of integral transforms on derived ∞-stacks.

But in their construction it is always assumed that the underlying site is the (derived) algebraic one, something like simplicial rings.

How much of their construction actually depends on that assumption? How much of this work carries over to other choices of geometries?

For instance, when replacing the category of rings /affine schemes in this setup with that of smooth algebra / smooth loci, how much of the theory can be carried over?

It seems that the crucial and maybe only point where they use the concrete form of their underlying site is the definition of quasicoherent sheaf on a derived stack there, which uses essentially verbatim the usual definition QC(−):Spec(A)↦AMod.

What is that more generally? What is AMod for A a smooth algebra? (In fact I have an idea for that which I will describe on the wiki page in a moment. But would still be interested in hearing opinions.)

Maybe there is a more intrinsic way to say what quasicoherent sheaves on an ∞-stack are, such that it makes sense on more general generalized schemes.

cosmology - Why is the E-mode polarization spectrum out of phase with the Temperature spectrum?

The E-mode polarization power spectrum of the Cosmic Microwave Background displays the same acoustic peaks that can be seen in the (more famed) temperature power spectrum. However, they are out of phase with respect to each other. A number of sources give answers that all come down to the following:

The main EE' power spectrum has peaks that are out of phase with those in theTT' spectrum, because the polarization anisotropies are sourced by the fluid velocity.

But I fail to understand this. Can someone elaborate on this?

light - how to assess a periodical signal?

You have it the wrong way around. You have to establish a periodicity before doing the folding.

There are various ways to do this, but the most frequently (pun intended) used is the Lomb-Scargle periodogram.

Start with a datset consisting of a set of points $(t_i, m_ipm sigma_i )$, where $t_i$ are times of observation and $m_i$ and $sigma_i$ are the fluxes and their uncertainties at those times.

You then calculate an array of chi-squared statistics, by fitting a mean level $bar{m}$ and sinusoidal functions over a range of discrete frequencies $omega$. The aim is to maximise the statistic
$$p(omega) = frac{chi^2_{0} - chi^2(omega)}{chi^2_{0}},$$
where
$$chi^{2}_{0} = sum (m_i - bar{m})^2/sigma_i^{2}$$ and
$$chi^{2}(omega) = sum (y_i - bar{m})^2/sigma_i^{2},$$ with $y_i = Asin(omega t_i + phi) + A_0$, where $A$, $A_0$ and $phi$ are free parameters that are optimised for each frequency (i.e. you find the minimum possible $chi^2(omega)$ at each frequency).

Once a period is obtained from a peak in the power spectrum, $p_{best}$, then it must be established whether this peak is "real" or significant.

Theoretically, the probability that $p>p_{best}$ is $(1-p_{best})^{(N-3)/2}$ for $N$ independent measurements (see Cumming, Marcy & Butler 1999). This is the "false alarm probability" - the chance that you would get $p>p_{best}$ from random, aperiodic data with those uncertainties.

However, real data has correlated noise and the points are not independent. So what you do instead (see Collier Cameron et al. 2009) is shuffle all the times of the data points (i.e. randomly reallocate the times of each observation) and go through the process again. Do this a squillion times with different random reallocations and see how many times you end up with $p>p_{best}$. This gives you some idea about how confident you can be that your detected periodic signal is real. This is called a "bootstrap Monte-Carlo method".

There are other ways to do this; my answer is not complete; but it's the one I'm familiar with.

star - Is metallicity low at the central region or nucleus of the Milky Way?

The stars in the Galactic bulge are predominantly metal-rich (by that I mean have a metallicity similar to the Sun or even a little higher).

Even though these stars are predominantly old, the bulge is thought to have formed extremely quickly and the interstellar medium from which the stars were formed would have been enriched with metals very quickly.

Here is a plot from Zoccali et al. (2009) (which I recommend reading). It shows the metallicity distribution of many stars in the Galactic bulge, measured using high-resolution spectroscopy. It shows that the highest metallicity stars are towards the middle (it is very hard to get samples right in the middle because of extinction) and the averge metallicity falls as you mover further from the centre (the samples with more negative Galactic latitude $b$.). The percentages in the plots are the estimated contamination from the disk population in each sample.

The dependence of metallicity on height and radial coordinate in the Galactic disk is still keenly debated. There is general consensus that the metallicity falls with radial distance from the Galactic centre and with height above the Galactic plane. The gradient is of order a few hundredths of a dex per kpc between a few kpc and 10-12 kpc from the Galactic centre. It may flatten beyond this. You could have a look at the discussion in Cheng et al. (2012), but there are many other attempts at parameterising the gradient and it is a technically difficult thing to do.

co.combinatorics - Gamma function versions of combinatorial identites?

Chapter 5.5 of Concrete Mathematics discusses generalizing binomial coefficient identities to the Gamma function. It doesn't discuss the two integrals you mention, though.

Doing a bit of thinking on my own, if $n$ is a positive integer then
$$int_{z=0}^n binom{n}{z} dz = int_{z=0}^n frac{n! dz}{Gamma(1+z) Gamma(n+1-z)}$$
$$int_{z=0}^{n} frac{n! dz}{(n-z)(n-1-z) cdots (1-z) Gamma(1-z) Gamma(1+z)}.$$

We have $Gamma(1+z) Gamma(1-z) = pi z/sin (pi z)$, if I haven't made any dumb errors, so this is
$$int_{0}^n frac{ n! sin (pi z) dz}{pi z (n-z)(n-1-z) cdots (1-z)}.$$

I suspect this integrand does not have an elementary anti-derivative, because it reminds me of $int sin t dt/t$. But there might be some special trick which would let you compute the integral between these specific bounds.

ag.algebraic geometry - Is every flat unramified cover of quasi-projective curves profinite?

(More editing for cleanliness)

The statement is false. I learned of this example from "James" at this blog post. If you take a nodal cubic curve (notably quasiprojective), there is a flat, unramified cover by an infinite connected chain of copies of P^1, each glued transversely to its successor at a point. This is not profinite. If I'm not mistaken, the etale fundamental group of the nodal cubic over a separably closed field (with a chosen basepoint) is $mathbb{Z}$, not its profinite completion.

Edit: Regarding the correct definition of etale fundamental group: In SGA1 Exp 5, Grothendieck (and Mme. Raynaud?) build up axiomatics for the theory of the fundamental group using only profinite sets, and the group is defined following one peculiar claim. In the beginning of Exp 5 Section 7, there is the assertion that for any connected locally noetherian scheme $S$, and any geometric point $a: ast to S$, the functor that takes an etale cover $X to S$ to the set of geometric points over $a$ (with the usual morphisms) lands in the category of finite sets. The example I gave above seems to contradict this, but if you look in Exp 1, you find that all of SGA1 is written under a definition of etale morphisms that assumes that they are finite type (which this example is not). Anyway, one reason why Pete Clark only sees profinite definitions for the etale fundamental group, is that people like to use finite type morphisms, while etale morphisms only have to be locally of finite presentation (according to EGA4, and Wikipedia I guess).

As for the question of infinite degree etale covering maps between locally finite type geometrically integral schemes, I don't think one exists, since (if I'm not mistaken) you automatically get an infinite degree algebraic extension of function fields, which is therefore infinitely generated. I'm having trouble thinking through the details of this, though.