Given two vectors of size n
u = [u_1, u_2, u_3, ..., u_n ]
and
v = [v_1, v_2, v_3, ..., v_n ]
What is the name of the operation "u ? v" such that the result is a vector of size n of the form
u ? v = [v_1.u_1, v_2.u_2, v_3.u_3, ..., v_n.u_n ]
For want of a better name, I have termed it "piecewise vector multiplication".
What is this operation normally known as in the literature?
Consider the function $f$ on $S_n$ which equals $1/n$ on all adjacent transpositions $(i,i+1)$, where we let $n+1 = 1$, and $0$ otherwise, and its Fourier transform $hat{f}(rho)$ evaluated at the irreducible representations.
Recall the irreducible representations of $S_n$ are indexed by the set of partitions of $n$. Partitions here are written as a finite non-increasing sequence of positive integers that add up to $n$.
When $rho$ is the representation corresponding to the partition $(n)$, the matrix $hat{f}(rho)$ is simply the $1 times 1$ matrix $[1]$.
When $rho$ is the representation corresponding to the partition $(n-1,1)$, the resulting matrix $hat{f}(rho)$ can be explicitly diagonalized, since it can be extended into a cyclic matrix on $mathbb{R}^n$. The eigenvalues are simply $cos frac{2pi k}{n}$ where $k = 1, ldots n-1$. Therefore the spectral gap for that matrix (the smallest gap between $1$ and an eigenvalue not equal to $1$) is simply
$$1-cos frac{2 pi}{n} = 1-cos frac{2(n-1)pi}{n} = frac{2 pi^2}{n^2} + O(frac{1}{n^3})$$.
the following questions are in increasing levels of difficulty and are interesting to Markov chain theorists:
Denote by $e_{lambda,j}$, $j = 1, ldots, d_lambda$ the eigenvalues of $hat{f}(rho_lambda)$, where $rho_lambda$ is the representation associated with the partition $lambda$ and $d_lambda$ is the dimension of that representation.
For any fixed $k in mathbb{N}$, is it true that $ (1-max_j e_{lambda,j}) le (n-lambda_1) frac{2 pi^2}{n^2} + O(frac{1}{n^3})$, for $n-lambda_1 le k$? Here $lambda_1$ denotes the longest part of the partition $lambda$.
If $lambda > lambda'$ in the sense that one can move blocks in the Ferrers diagram of $lambda'$ in the up and right direction to obtain $lambda$, for instance $(n-1,1) > (n-2,1,1)$, is it true that the spectral gap of $hat{f}(rho_lambda)$ is smaller than that associated with $lambda'$?
Give an explicit formula for $e_{lambda,j}$. This is most likely not possible.
This question shows how hard it can be to diagonalize matrices and to understand the representation theory of $S_n$ at a practical level.
No for general topological spaces, yes for metrizable ones (and I believe the argument can be generalized to all normal spaces).
Bad example: $X={a,b,c}$ with open sets $emptyset$, $X$, ${a}$, ${a,b}$, ${a,c}$. Let $A={a}$, then $bar A=X$. The homotopy is given by $H_1=id$, $H_tequiv a$ for $t<1$. The dimension of $A$ is 0 but the dimension of $bar A$ is 1.
On the positive side, let me begin with a quick and dirty proof in the case when $bar A$ is a compact metric space. Let ${U_i}$ be an open covering of $bar A$. We need to find a refined covering of multiplicity at most $N+1$ where $N=dim A$. It suffices to find a continuous map $f:bar Ato A$ and an open covering ${V_j}$ of $A$ such that ${f^{-1}(V_j)}$ is a refinement of ${U_i}$. Indeed, in this case we can find a refinement of ${V_j}$ of multiplicity at most $N+1$ and its $f$-preimage is the desired refinement of ${U_i}$.
In the compact case, let ${V_j}$ be the covering by $(rho/3)$-balls where $rho$ is the Lebesgue number of the covering ${U_i}$. Then, for some $t$ sufficiently close to 1, the map $f=H_t$ satisfies the desired property: the preimage of every $V_j$ has diameter less than $rho$ and hence is contained in some of the sets $U_i$. Indeed, suppose the contrary. Then there is a sequence $t_kto 1$ and sequences $x_k,y_kin bar A$ such that $|x_ky_k|gerho$ but $|H_{t_k}(x_k)H_{t_k}(y_k)|<2rho/3$. Due to compactness we may assume that $x_k$ and $y_k$ converge to some $x,yinbar A$. Then $|xy|gerho$ but $|H_1(x)H_1(y)|le 2rho/3$, a contradiction.
In the general metric space case, let $rho(x)$ denote the local Lebesgue number of ${U_i}$ at $x$, that is the supremum of $rho$ such that the ball $B_rho(x)$ is contained in one of the set $U_i$. Note that $xmapstorho(x)$ is a positive 1-Lipschitz function on $bar A$. It is easy to construct a continuous function $u:bar Ato[0,1)$ such that the distance from $x$ to $H_t(x)$ is less that $rho(x)/10$ for all $xinbar A$ and all $t>u(x)$. Then the map $f:bar Ato A$ given by $f(x)=H_{u(x)}(x)$ and the covering of $A$ by the balls of the form $B_{rho(x)/10}(x)$, $xin A$, will do the job.
Such homotopies are given by the $smile_i$-products. Steenrod gives explicit formulas, IIRC, in [Steenrod, N. E. Products of cocycles and extensions of mappings. Ann. of Math. (2) 48, (1947). 290--320. MR0022071], but the easiest is to prove they exist using acyclic models.
(Maybe Steenrod only deals with $mathbb Z_2$ coefficients? I don't have access to the paper now :( )
Dan, I doubt that you will find a proof of this in the literature. To get (ii) from (i), note that (i) gives you a block basic sequence $x_1,....,x_m$ in the block subspace $Y$ s.t. $|sum_{i=1}^m x_i|= 1$ and for some choice $a_i$ of signs,
$|sum_{i=1}^m a_i x_i| > C$. WLOG $a_1=-1$. Now group together maximal blocks all of whose signs are
the same to rewrite
$sum_{i=1}^m a_i x_i$ as $sum_{j=1}^n (-1)^j y_j$, where $y_j$ is the sum of the $x_i$'s in the $j$-th maximal block.
I assumed real coefficients in the above, but the complex case is only a bit more involved.
If this explanation isn't sufficient, I suggest that you study further the section in [LT] on bases. I addressed the only point that I thought might be troubling to someone who had studied [LT].
It's a long time since I worked on this kind of problem, so please bear with me.
I have an approximate inverse matrix that I'm using as a preconditioner to solve the conjugate gradient method. Unfortunately the matrix is much more dense than the storage I have available and reducing it to a much sparser matrix results in a far less optimal solution.
Here is a subset of one of the matrices being produced to get an idea of the arrangement and layout of the data:
10.880 1.917 1.979 0.669 0.311 0.000 0.000 0.000
1.917 10.871 0.651 1.924 0.000 0.000 0.000 0.000
1.979 0.651 11.596 2.159 2.038 0.330 0.000 0.000
0.669 1.924 2.159 11.253 0.350 0.000 0.000 0.000
0.311 0.000 2.038 0.350 11.221 1.972 0.320 0.311
0.000 0.000 0.330 0.000 1.972 11.171 1.862 1.810
0.000 0.000 0.000 0.000 0.320 1.862 10.550 0.310
0.000 0.000 0.000 0.000 0.311 1.810 0.310 10.550
0.322 0.059 2.062 0.694 0.673 0.057 0.000 0.000
0.112 0.331 0.736 1.990 0.123 0.011 0.000 0.000
0.000 0.000 0.696 0.063 1.934 0.321 0.000 0.000
0.000 0.000 0.239 0.342 0.343 0.000 0.000 0.000
0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000
Now it looks to me that this kind of matrix could be fairly well approximated in fourier space, and by using a wavelet transform I could store a lot more of the data without resorting to a sparse matrix format where I cull the data that doesn't exceed a certain value.
Does that sound reasonable looking at the example dataset? How would I go about doing this, what existing techniques are involved and what resources should I start looking at to help me become familiar with this area?
I'm interested in using the least amount of storage space to store the best approximation to these matrices.
The answer is always "no". By classification, a bielliptic surface over $mathbb C$ has the form $(Etimes F)/G$ where $E,F$ are elliptic curves, $G=subset Aut(E,0)$ is an abelian group acting by complex multiplications on $E$ and by translations on $F$. ($G$ is not necessarily cyclic as Tuan correctly points out.)
($X$ maps to an elliptic curve $F/G$ and every fiber is isomorphic to an elliptic curve $E$, hence the name bielliptic.)
Then $F$ acts on $Etimes F$ by $(x,y)mapsto (x,y+f)$, and this action commutes with the $G$-action. Thus, $Fsubset Aut^0(X)$. As $F$ is a projective variety, $Aut^0(X)$ is not affine.
This is a sideways answer.
Let $E_{ij}(a)=I+a E_{ij}$, for $ineq j$ and $ain A$.These matrices generate the conmutator subgroup $$E(n, A)=[mathrm{GL}(n, A),mathrm{GL}(n, A)]subseteqmathrm{GL}(n, A).$$
One can easily check that the obvious relations satisfied by these elements are $$E_{ij}(a)E_{ij}(b)=E_{ij}(a+b),$$ $$[E_{ij}(a),E_{jk}(a)]=E_{ik}(a) mbox{ if $ineq k$,}$$ $$[E_{ij}(a),E_{kl}(b)]=1 mbox{ if $ineq l$ and $jneq k$.}$$
Yet the group presented by generators and this relations is not $E(n,A)$, but what we call the $*n$-th unstable Steinberg group* $mathrm{St}(n, A)$ of $A$. In general, this is larger than (precisely, an extension of) $E(n,A)$.
(NB: The following paragraph has been edited to make it match reality. Thanks to Allen for pointing the mistake in the comment bellow)
This is seen, for example, because the map $mathrm{St}(n, A)to E(n,A)$ has a non-trivial kernel. Indeed, after passing to the direct limit as $n$ goes to infinity, the kernel of that map is precisely the second algebraic $K$-theory group of $A$, $K_2(A)$. Milnor shows in his book that $K_2(mathbb{R})$ is uncountable, and describes $K_2(mathbb Q)$ (he also shows that $K_2(mathbb Z)$ is cyclic of order two, so this can be done for rings that are not fields too...)
A nice reference for all this is Jonathan Rosenberger's Algebraic $K$-theory and its applications, and there is John Milnor's Introduction to algebraic $K$-theory, which is also extremely nice.
A short intuitive description for $K_2(A)$ is: it measures how much more information is there in the elementary matrices of a ring which does not follow formally from the Steinberg relations.
I don't think this is true even when $X$ and $V$ are schemes if you only require that the
map $Vto X$ is an embedding of functors (rather than a locally closed embedding). Example:
Take $X=Spec(k[x])$, $V=Spec(k[x,x^{-1}]times k)$, $U=Spec(k)$.
That is, $X$ is an affine line, $V$ is the disjoint union of a punctured line and origin,
and $U$ is a point, which we view as the connected component of $V$. The natural map
$Vto X$ (corresponding to stratification of $X$) is a categorical monomorphism: it induces an embedding of functors.
EDIT:
Now we add the assumption that $Vhookrightarrow X$ is locally closed. I think the statement still fails,
here's a counterexample:
$X$ will be an ind-scheme: so there is a sequence of schemes $X_n$ related by closed embeddings
$X_nhookrightarrow X_{n+1}$ and
$$X(A)=lim_{to} X_n(A).$$
In other words, every point of $X(A)$ factors through one of $X_n$'s.
For ind-schemes, a locally closed subfunctor $Vsubset X$ is given by a compatible
family of locally closed $V_nsubset X_n$ (so that it is a locally closed sub-ind-scheme). Problem
is, the statement fails for ind-schemes.
Let's take
$X_n={mathbb A}^n$, with the embedding $X_nhookrightarrow X_{n+1}$ being the coordinate embedding.
Now let $V_n$ be the union of the origin $0$ and $n-1$ punctured lines
$$l_k:=lbrace(k,0,dots,0,x,0,dots,0)|xne 0rbrace,$$
where $x$ is in the $k$-th position, and $k$ varies from $2$ to $n$. (Let's say I work over
a field of characteristic $0$, so all integers are distinct.)
Finally, $U_nsubset V_n$ is the origin, which is a component of each $V_n$, so it is both open
and closed.
It is easy to see that it is impossible to find a compatible family of open subsets $W_nsubset X_n$
such that $U_n=V_ncap W_n$. Indeed, $W_1$ contains $0$, so it is non-empty, and thus contain
$nin{mathbb A}^1=X_1$ for some $n$. But then $W_n$ must contain $(n,0,dots,0)$ without meeting
$l_n$.
Background: given a finite-dimensional real vector space V of dimension d, I can define a pointed cone in two ways: either as a set of the form ${r_1v_1 + cdots + r_nv_n mid r_1, dots, r_n in R_{ge 0}}$ (here R is the real numbers, I can't seem to use mathbf?) where $v_1, dots, v_n$ are some choice of generators, or as the intersection of finitely many half-spaces which doesn't contain any lines.
In particular, if I start with the generator description, one can define supporting hyperplanes as those with defining equation $a_1x_1 + cdots + a_dx_d = b$ such that the cone lives in one of the two spaces $a_1x_1 + cdots + a_dx_d le b$ or $a_1x_1 + cdots + a_dx_d ge b$. A facet can be defined as the positive real span of a collection of d-1 vectors for which there exists a supporting hyperplane that vanishes on it. The relevant theorem here is that if I take the collection of supporting hyperplanes of facets, then the cone is the intersection of the appropriate half-spaces. All proofs of this that I have seen use the fact somewhere that R is an ordered field.
My question is whether one can generalize this situation to partially-ordered fields.
In particular, I am only interested in the following field. Take the ring of symmetric functions in n variables, and let K be its fraction field. Say that an element is "Schur positive" if it can be written in the form f/g where both f and g are Schur positive symmetric functions. (Note: it could be the case that f/g = f'/g' where both f and g are Schur positive and neither f' nor g' are Schur positive nor Schur negative, but whatever). And then I'll say that $x ge y$ if $x-y$ is "Schur positive." This gives me a partial ordering on K compatible with addition and multiplication.
I'll now define a cone defined by generators in the same way, but instead of using coefficients from nonnegative reals, I'll use "Schur positive" coefficients. Now, is there any way of getting a dual "hyperplane" description for these kinds of cones, or any sensible definition of "facets"? There is a map from K to the rationals which sends a rational Schur polynomial to the evaluation at all 1's which sends "Schur positive" elements to positive numbers.
This all seems crazy, so let me explain my motivation. In the paper http://arxiv.org/abs/0712.1843 , Eisenbud and Schreyer show that the Betti tables of Cohen-Macaulay modules of a fixed codimension are positive rational combinations of pure Betti tables, and they use the generators / hyperplane duality mentioned in the beginning. In my paper http://arxiv.org/abs/0907.4505 with Weyman, we study equivariant resolutions, and wonder if their result generalizes in an equivariant way (see Section 4 specifically). It seems that the definition of K I give above is one sensible way to go to generalizing this. Going through Eisenbud and Schreyer's proof, everything can be done in an equivariant way, EXCEPT for knowing things about "Schur positive convex geometry."
I've thought about it for a while and looked for references, but have no idea where to begin to see if this kind of thing has been studied before. Hopefully someone else knows something about it.
Just by coincidence, I was catching up on my arxiv reading and noticed that Losev's paper appears to answer your question. See part (3) of Theorem 4.3.1 there. He says it was "known previously".
To be kinder to the reader: the Cherednik algebra is really a family of algebras depending on a parameter $c$; it looks like Losev's result is that at $c=k/m$ for relatively prime integers $k$ and $m$ the varieties we want correspond to partitions of $n$ which are of the form $(m,m,dots,m,1,1,dots,1)$ for some number of $m$'s and some number of $1$'s.
Having looked more carefully at Losev's paper, it seems the idea of the proof is this: in the spirit of Bezrukavnikov-Etingof, having fixed a partition $lambda$ Losev gives (his Theorem 1.3.1) an inductive description of primitive ideals with associated variety corresponding to $lambda$. The partition $lambda$ corresponds to a "parabolic" subgroup $W$ of $S_n$ consisting of those permutations fixing a generic point of the corresponding variety, and the set of primitive ideals corresponding to $lambda$ is in bijection with the set of primitive ideals of finite codimension in the Cherednik algebra attached to $W$ at the same parameter $c=k/m$. But $W$ is a product of symmetric groups, so the classification due to Berest-Etingof-Ginzburg of finite dimensional modules for the type $S_n$ Cherednik algebra (they exist exactly when $c$ has denominator $n$) implies the result.
It appears that ideas from Losev's work on finite $W$-algebras also work for symplectic reflection algebras. It would therefore be nice to understand the finite dimensional modules outside of the symmetric group case a little better. (And now I'm more motivated to learn about $W$-algebras!)
There is a classic result of Ramanujan known as his Master Formula which Wolfram has here:
http://mathworld.wolfram.com/RamanujansInterpolationFormula.html
To summarize briefly (and coarsely): if the values you want to interpolate do not grow faster than the gamma function, things will be ok. If they do grow faster than that, his formula doesn't converge, so you'll have to find another technique.
Without loss of generality you can think that $Y=ell^1$ (just pick an infinite sequence of linearly independent unit vectors in $Y$ and multiply them by the coefficients decaying so fast that no non-trivial $ell^1$ combination will have any chance to be $0$). Now, construct a locally finite cover of $X$ with opposite points identified that has small diameters of the covering sets (every metric space is paracompact). Construct the corresponding continuous partition of unity and lift it back to $X$ to get symmetric continuous locally finite partition of unity. Decouple symmetric open sets consisting of 2 symmetric components. Now, for each open set in the new cover, choose a number so that the opposite open sets intersecting the sphere correspond to opposite numbers and all numbers are non-zero, but otherwise arbitrarily. Multiply the numbers by the partition of unity. Fix also any linear ordering of the symmetric pairs of neighborhoods. All we need now is a continuous mapping $F$ from the metric space of ordered finite sets of numbers with the metric that allows both finitely many small insertions and small perturbations (to find the distance between two sets, you can place their elements in the sequence in the given order adding any number of zeroes anywhere and take the minimum of the $ell^1$ norm of the difference that can be attained in this way) to $ell^1$ that is symmetric ($F(-x)=-F(x)$) and never $0$ on for $xne 0$. This is a great relief because the space $X$ we want to map is not huge anymore, it is just a fancy metric space of finite sets of numbers. The downside is that we need much more symmetry than before but still not too much ($x$ and $-x$ are still clearly distinguishable though can come arbitrarily close). Now we can raise the level of abstraction again and consider any separable metric space $X$ with an isometric involution $U$ without fixed points and try to map it to $ell^1$ so that $F(Ux)=-F(x)$. This is trivial. Just create a countable symmetric (with respect to $U$) dense set, for each pair of symmetric points $x,Ux$ take the balls around $x$ and $Ux$ of radius $1/3$ times the distance between them, and construct an antisymmetric function that vanishes outside these 2 balls but not inside them (the plus-minus distance to the boundary, say). Multiply these functions by small numbers and put them in a sequence. You are done.
Of course, the main part of this proof is the paracompactness result. So, if you strongly dislike AC, then the question remains open (but how can you do abstract Banach spaces and dislike AC?)
OK, if you so strongly prefer formal language, here is a sequence of claims. For each claim, tell me if you agree with it, have a counterexample, would like to see the proof/reference, or just do not understand what I mean. I'll respond to your reaction.
Claim 1. We can take $Y=ell^1$
Claim 2. If $Z$ is a separable metric space with an isometric involution $I$ without fixed points, then we can find a continuous maping $F$ from $Z$ to $ell^1$ such that $F(Iz)=-F(z)$ for all $zin Z$ and $F(z)ne 0$ for all $zin Z$.
Claim 3. Define the equivalence relation on the set of finite or infinite sequences of reals with finitely many non-zero terms as follows. Two sequences are equivalent if two finite sequences obtained by deleting all zero elements in the original sequences (so 0,1,0,0,2,0,3,0,0,0,...) becomes just (1,2,3)) coincide. The space $Z$ of equivalence classes of non-zero sequences with the distance defined as the infimum (actually, minimum) of the $ell^1$ distances between class representatives is a separable metric space.
Claim 4. The mapping $I$ that maps the class of a sequence $z$ to the class of the sequence $-z$ is well defined and is an isometric involution on $Z$ without fixed points.
Claim 5. Every set can be linearly ordered.
Claim 6. There is a symmetric locally finite covering $mathcal U$ of the unit ball in $X$ by open sets $U$ of diameter less than $1/10$ each (symmetric means that if $U$ is in the cover, then so is $-U$).
Claim 7. There exists a mapping $G:mathcal Uto{pm 1}$ such that $G(-U)=-G(U)$ when $U$ intersects the unit sphere.
Define the functions $f_U(x)=dist(x,Xsetminus U)$.
Claim 8. For each point x at least one $f_U(x)ne 0$ and one can find a neighborhood $V$ of $x$ and a finite subset $mathcal V_xsubsetmathcal U$ such that $f_U$ is identically zero on $V$ for all $Unotinmathcal V_x$.
Claim 9. There exists a linear order $L$ on $mathcal U$ such that $U_1<U_2$ implies $(-U_1)<(-U_2)$ when both $U_1,U_2in mathcal U$ intersect the unit sphere in $X$ and have non-empty intersection.
Claim 10: The mapping $H$ from the unit ball in $X$ to $Z$ that maps every point $x$ to the equivalence class of the sequence ${G(U)f_U(x)}_{Uin V_x}$ arranged according to $L$ is well-defined, continuous, and satisfies $H(-x)=I(H(x))$ on the unit sphere.
Claim 11: The composition mapping $Fcirc H$ is a continuous mapping from $X$ to $ell_1$ that is antisymmetric on the unit sphere and the pre-image of zero under this mapping is empty.
Response round 1.
Proof of claim 2. Consider a countable dense set $S$ in $Z$. For each $yin S$, define $r=r_y$ to be one third of the distance between $y$ and $Iy$.
Claim 2.1: The open ball $B(Iy,r)$ equals $IB(y,r)$ and these 2 balls are disjoint.
Claim 2.2: The function $f_y(z)$ defined as $r-d(z,y)$ on $B(y,r)$, as $d(z,Iy)-r)$ on $B(Iy,r)$ and 0 everywhere else is continuous and satisfies $f_y(Iz)=-f_y(z)$.
Claim 2.3: For each $zin Z$ there exists $yin S$ such that $f_y(s)ne 0$.
Claim 2.4. There exists a bijection $psi:mathbb Nto S$ and a mapping $eta:mathbb Nto(0,+infty)$ such that the sequence $eta(n)r_{psi(n)}$ belongs to $ell^1$.
Claim 2.4. The mapping $F$ that maps $z$ to the sequence $eta(n)f_{psi(n)}(z)$ has the properties proclaimed in Claim 2.
Metric space of equivalence classes of sequences:
Definition 3.1. A sequence is a mapping from any linearly ordered set S to reals.
Definition 3.2. A sequence $psi$ is non-zero and has finitely many non-zero elements if the set of $sin S$ such that $psi(s)ne 0$ is finite and non-empty.
Definition 3.3. Non-zero sequences $psi_1:S_1tomathbb R$ and $psi_2:S_2tomathbb R$ with finitely many non-zero elements are equivalent if there is an order preserving bijection $varphi$ between the sets $S'_j={sin S_j:psi_j(s)ne 0}$ such that $psi_2circ varphi=psi_1$.
Claim 3.4. Thus introduced equivalence relation is reflexive, symmetric, and transitive.
Definition 3.4. The distance between equivalence classes $Psi_1$ and $Psi_2$ is defined as the infimum over all pairs $psi_1in Psi_1$ and $psi_2in Psi_2$ such that $psi_1$ and $psi_2$ are defined on the same finite set $S$ of the (finite) sums $sum_S|psi_1(s)-psi_2(s)|$
Claim 3.5. This distance is well-defined and satisfies three standard distance axioms.
Claim 3.6. The metric space thus constructed is separable.
Among the standard examples of abelian categories without enough projectives, there are
No abelian category where the functors of infinite product are not exact can have enough projectives. In Grothendieck categories (i.e. abelian categories with exact functors of small filtered colimits and a set of generators) there are always enough injectives, but may be not enough projectives.
Among the standard examples of abelian categories with enough projectives, there are
I think the answer is 'yes.' I don't have a suitably general reason why this is the case, although surely one exists and is in the literature somewhere.
At any rate, for the problem at hand, we have for $s > 0$
$$sum frac{a_n}{n^s} = frac{1}{Gamma(s)}int_0^infty sum a_n e^{-nt} t^{s-1} dt.$$
Edit: the interchange of limit and sum used here requires justification, and this is done below. Supposing that $sum a_n x^n rightarrow sigma$, we may write $sum a_n e^{-nt} = (sigma + epsilon(t))cdot e^{-t}$ where $epsilon(t) rightarrow 0$ as $t rightarrow 0$, and $epsilon(t)$ is bounded for all t. In this case
$$sum frac{a_n}{n^s} = sigma + Oleft(sint_0^infty epsilon(t) e^{-t} t^{s-1} dtright)$$
Showing that error term tends to $0$ is just a matter of epsilontics; for any $epsilon > 0$, there is $Delta$ so that $|epsilon(t)| < epsilon$ for $t < Delta$. Hence
$$left|sint_0^infty epsilon(t) e^{-t} t^{s-1} dt right| < sepsilon int_0^Delta t^{s-1} dt + sint_Delta^infty e^{-t}t^{s-1}dt < epsilon Delta^s + sint_Delta^infty e^{-t} t^{-1} dt.$$
Letting $s rightarrow 0$, our error term is bounded by $epsilon$, but $epsilon$ of course is arbitrary.
Edit: Justifying the interchange of limit and sum above is surprisingly difficult. We will require
Lemma: If for fixed $epsilon > 0$, the partial sums $D_{epsilon}(N) = sum_{n=1}^N a_n/n^epsilon = O(1),$ then
(a) $A(N) = sum_{n leq N} a_n = O(n^epsilon)$, and
(b) $sum_{n leq N} a_n e^{-nt} = O(t^{-epsilon})$,
where the O-constants depend on $epsilon.$
This, with the hypothesis that $sum a_n/n^s$ converges for all $s > 0$, imply the conclusions a) and b) for all positive $epsilon$.
To prove part a), note that
$$sum_{n leq N} a_n = sum_{n leq N} a_n n^{-epsilon}n^epsilon = sum_{n leq N-1} D_{epsilon}(n) (n^epsilon - (n+1)^epsilon) + D_epsilon(N)N^epsilon,$$
which is seen to be $O(N^epsilon)$ upon taking absolute values inside the sum.
To prove part b), note that
$$t^epsilon sum_{n leq N} a_n e^{-nt} = t^epsilon sum_{n=1}^{N-1} A(n)(e^{-nt} - e^{-(n+1)t}) + t^epsilon A(N) e^{-Nt} = O left( sum_{nleq N} (tn)^epsilon e^{-nt}(1-e^{-t}) + (tN)^epsilon e^{-Nt}right).$$
Now, $(tN)^epsilon e^{-Nt} = O(1)$, and
$$sum_{nleq N} (tn)^epsilon e^{-nt}(1-e^{-t}) = 2^epsilon(1-e^{-t}) sum_{nleq N} (tn/2)^epsilon e^{-nt/2} e^{-nt/2} = Oleft(frac{1-e^{-t}}{1-e^{-t/2}}right) = Oleft(frac{1}{1+e^{t/2}}right) = O(1),$$
and this proves b).
We use this to justify interchanging sum and integral as follows: note that
$$sum_{n=1}^N frac{a_n}{n^s} = frac{1}{Gamma(s)}int_0^infty sum_{n=1}^N a_n e^{-nt} t^{s-1} dt,$$
and therefore
$$frac{1}{Gamma(s)}int_0^infty lim_{Nrightarrowinfty}sum_{n=1}^N a_n e^{-nt} t^{s-1} dt = frac{1}{Gamma(s)}int_0^1 lim_{Nrightarrowinfty}sum_{n=1}^N a_n e^{-nt} t^{s-1} dt + frac{1}{Gamma(s)}int_1^infty lim_{Nrightarrowinfty}sum_{n=1}^N a_n e^{-nt} t^{s-1} dt.$$
In the first integral, note that for $epsilon < s$, $sum_{n leq N} a_n e^{-nt} t^{s-1} = O(t^{s-epsilon -1})$ for all $N$. So by dominated convergence in the first integral, and uniform convergence of $e^t sum_{n=1}^N a_n e^{-nt}$ for $t geq 1$ in the second, this is limit is
$$lim_{Nrightarrowinfty}frac{1}{Gamma(s)}int_0^1 sum_{n=1}^N a_n e^{-nt} t^{s-1} dt + lim_{Nrightarrowinfty}frac{1}{Gamma(s)}int_1^infty sum_{n=1}^N a_n e^{-nt} t^{s-1} dt = lim_{Nrightarrowinfty} sum_{n=1}^N a_n frac{1}{Gamma(s)}int_0^infty e^{-nt}t^{s-1} dt.$$
This is just $sum_{n=1}^infty frac{a_n}{n^s}$.
Note then that we do not need to assume from the start that the infinite Dirichlet sum tends to anything as $s rightarrow 0$; once it converges for each fixed $s$, that is implied by the behavior of the power series.
In the following article : "H. Matsumura, P. Monsky, On the automorphisms of hypersurfaces, J. Math. Kyoto Univ. 3 (1964) 347-361", it is shown that in finite characteristic, automorphism groups of smooth hypersurfaces of $mathbb{P}^N$ are finite (with known exceptions such as quadrics, elliptic curves, K3 surfaces). However, the question of their reducedness is left open. Does anyone know something about it ?
In fact, we need to show that $H^0(X,T_X)=0$. In characteristic $0$, you can use Bott's theorem to do that. What can you do in finite characteristic ?
The vast majority of disconnected graphs have a single isolated vertex.
Let $A$ be a nonempty proper subset of ${1,...,n}$ of size $a$. Let $s(a)$ be the number of graphs with
$e=lfloor frac12 {n choose 2}rfloor$ edges which have no edges from $A$ to $A^c$.
We want to count the union of all of these. Inclusion-exclusion works, with the dominant terms coming from when $a=1$.
An upper bound is the sum of $s(a)$ over all $A$ of size at most $n/2$, which is at most
$n ~s(1)$ + ${nchoose 2}s(1)$ + $2^ns(3)$.
To get a lower bound, subtract the number of graphs with no edges connecting $A$ to $A^c$ or edges connecting $B$ to $B^c$ for all disjoint ${A,B}$. Denote this by $s(#A,#B)$. So, subtract
${nchoose2}s(1,1) + 3^ns(1,2)$ from $n~s(1)$.
The rest should be routine estimates on $s(1)$, $s(2)$, $s(3)$, $s(1,1)$, and $s(1,2)$.
$s(a,b) le s(a+b)$.
$s(a) = ({nchoose 2} -a(n-a))$ choose $e$.
Let the total number of graphs with $e$ edges be $#G = s(0)$.
$$s(a)/#G = prod_{i=0}^{a(n-a)-1} frac{lceil{nchoose2}/2rceil-i}{{nchoose2}-i}.$$
$s(2)/s(1) le 2^{-n+3}$.
$s(3)/s(1) le 2^{-2n+8}$.
The dominant term in both the upper bound and the lower bound is $n~s(1)$.
If I calculated correctly, that's asymptotic to $frac 2 e n 2^{-n} ~#G$.
Here's another counter-example, taken from Loop Groups (p 128).
Consider the space of continuous functions on the circle and define
$$
f(theta) = sum_{k gt 1} frac{sin k theta}{k log k}
$$
The positive part of this function is
$$
f_+(theta) = frac{1}{2 i} sum_{k gt 1} frac{e^{i k theta}}{k log k}
$$
which is unbounded near $theta = 0$.
Let's move on to the other part of your question: when can we ensure that the splitting exists? What you are asking for is that $V$ be the direct sum of two subspaces, $V_-$ and $V_+$. Of course, if you start with two abstract vector spaces, $V_-$ and $V_+$, both of which admit symmetric, positive definite bilinear forms, say $b_-$ and $b_+$ respectively, then you can construct an example by taking $V = V_- oplus V_+$ and taking $-b_- + b_+$. This shows that you can get this situation to work with quite awful spaces, but the point is that all the awfulness of $V$ divides nicely into awfulness of $V_-$ plus awfulness of $V_+$.
Presumably, though, you are more interested in the case where you start with $V$ and the quadratic form. Maybe this quadratic form can be fairly arbitrary (perhaps varies in some space of quadratic forms). In this situation, you would want conditions on $V$ that guarantee that the splitting occurs without too much fuss.
Let's examine the question from the other end: suppose that $V = V_- oplus V_+$. Then by changing the sign of the form on $V_-$, we obtain a positive-definite symmetric bilinear form on $V$. This usually goes by the name of an inner product as we're over $mathbb{R}$. So the problem reduces to finding complements of subspaces in inner product spaces. To guarantee this, you want completeness. Then your bilinear form is related to the original inner product by the operator $2P_+ - I$ where $P_+$ is the orthogonal projection on to $V_+$.
So what you want is to be working with a Hilbert space and the space of self-adjoint square-roots of the identity.
As I said, this isn't an "if and only if". But it is a simple condition that quite often holds. It can be further relaxed since it's enough that the inner product induced by the bilinear form and the original inner product be merely equivalent rather than equal, but I'll leave those details as an exercise.
Edit: From your other question related to this it seems as though you are particularly interested in the case where one of the factors is finite dimensional. In that case, the splitting always holds.
I would like to know to what extent it is possible to compare fibers over $mathbb{F}_p$ of coarse moduli spaces over $mathbb{Z}$, and coarse moduli spaces over $mathbb{F}_p$. I ask a more precise question below.
Let $mathcal{M}_g^{mathbb{Z}}$ be the moduli stack of smooth genus $g$ curves over $mathbb{Z}$. Let $M_g^{mathbb{Z}}$ be its coarse moduli space, and $(M_g^{mathbb{Z}})_p$ the fiber of this coarse moduli space over $mathbb{F}_p$.
Let $mathcal{M}_g^{mathbb{F}_p}$ be the moduli stack of smooth genus $g$ curves over $mathbb{F}_p$ and $M_g^{mathbb{F}_p}$ its coarse moduli space.
The universal property gives a map $phi:M_g^{mathbb{F}_p}rightarrow(M_g^{mathbb{Z}})_p$. My question is : is $phi$ an isomorphism ?
In fact, since $phi$ is a bijection between geometric points, and $M_g^{mathbb{F}_p}$ is normal, the question can be reformulated as : is $(M_g^{mathbb{Z}})_p$ normal ? This shows that when $g$ is fixed, the answer is "yes" except for a finite number of primes $p$.
N.B. this answer was in response to an earlier version of the question, which only had the first two paragraphs -- hence it doesn't address what appears to have been the original poster's actual question. For that, see the answers of Leonid or Harald.
I'm not sure if this answers your question, but it might be worth noting that a measurable function $f$ on the real line is in $L^2({mathbb R})$ if and only if its Fourier transform $widehat{f}$ is (Plancherel theorem), while it is in $C^infty({mathbb R})$ if and only if we have
$$ int_{-infty}^infty | widehat{f}(x) |^2 (1+ |x|^2)^{k} < infty quad{rm for } k=1,2,dots $$
(this is a form of Sobolev embedding, albeit in a very special case). In particular, if I've correctly understood the notation from the wikipedia page for Sobolev spaces, the space you're after seems to be the intersection $bigcap_{k=0}^infty H^k({mathbb R})$. I don't know if this goes by a particular name.
I would like to find the chromatic polynomial χ for the n by m rook's graph Gn,m for as many values of n and m possible. The rooks graph is also (a) the line graph of the complete bipartite graph Kn,m and (b) the Cartesian product of Kn and Km.
This is going to be very difficult in general since, for example, χ(Gn,n;x) evaluated at x=n is the number of Latin squares of order n (which is known only for n≤11). In general, χ(Gn,m;x) counts a generalisation of Latin squares. Moreover, Gn,m typically has lots of edges, making the standard deletion/contraction computation infeasible.
However, if we find enough values of χ(Gn,m;x) for small x we can simply fit a polynomial to these points to find χ(Gn,m;x) itself. For rook's graphs, it may be possible to find values of χ(Gn,m;x) efficiently by generalising techniques used in counting Latin squares.
I would like to know if it is ever feasible to find a chromatic polynomial via polynomial fitting in some cases, that cannot be found using deletion/contraction?
Question: Are there examples in the literature in which a chromatic polynomial was found by polynomial fitting small data points (which could not be found faster using deletion/contraction)?
Select $K$ random binary vectors $Y_i$ of length $m$ uniformly at random.
Let the following collection of random variables be defined: $X_{i,j}=w(Y_i oplus Y_j)$ where $w(cdot)$ denotes the Hamming weight of a binary vector, i.e., the number of the nonzero coordinates in its argument. Define $D_{min}(Y_1,ldots,Y_K)$ as the smallest of the $X_{i,j}$ for $i neq j.$
Thus we have $n=C(K,2)=K(K-1)/2$ non-independent random variables $X_{i,j}$ with support {$0,1,ldots,m$} and individual distribution $Bin(m,1/2)$. It seems to me that the random variables $X_{i,j}$ will be $s$-wise negatively correlated (for $s$ large enough) if distances between pairs chosen from a subcollection of $Y_{i_1},Y_{i_2},ldots,Y_{i_v}$ where ($v < K$) tincreases then the distances between $Y_{i_j}$ and the remaining vectors will tend to decrease. Take $s=v+1.$
It is possible to get a bound on the following quantity. Fix $w$ an integer less than $m/2.$ The Hamming sphere of radius w has "volume", i.e., contains $V_w(m)=sum_{s=0}^w C(m,s)$ vectors and we approximately have to first order in the exponent
$$
V_w(m) =2^{m H((w+1)/2)}
$$
where $H(cdot)$ is the binary entropy function. Then, for a random uniform choice of the $Y_i$ for $i=1,2,ldots,K$ it is clear that if the Hamming spheres centred at these vectors are disjoint then the minimum distance is at least $2w+1$ thus
$Pr[D_{min} geq 2 w+1] leq frac{(2^m-V)}{2^m}frac{ (2^m-2 V) }{2^m} cdotsfrac{ (2^m - (K-1)V)}{ 2^{m}}$
where $V=V_w(m).$ This means that, by replacing each fraction of the form $(1-x)$ by $exp(-x)$ where $x >0$ but small, we get the approximate upper bound
$Pr[ D_{min} geq 2w+1] leq expleft[-K(K-1)V^2/(2^{m+1} right]$ which then expresses this upper bound in terms of the entropy function, which is nice. Unfortunately this upper bound is quite loose.
I will be happy with any pointers to literature or any other suggestions.
There's an old problem in 4-manifold theory that, as far as I know, doesn't have a name associated with it and really deserves a name.
Let $M$ be a smooth 4-manifold with boundary. Let $S$ be a smoothly embedded 2-dimensional sphere in $partial M$. Assume $S$ does not bound a ball in $partial M$, but $S$ is null-homotopic in $M$. Does $S$ bound a smooth 3-ball in $M$? Perhaps you need to replace $S$ by another non-trivial $S'$ in $partial M$ before you can find a 3-ball in $M$ bounding it?
You could think of this as the co-dimension one analogue to Dehn's lemma for 4-manifolds. Usually when people talk about a Dehn lemma for 4-manifolds they're interested in the co-dimension 2 analogue.
Does this problem / conjecture have a name? If not, do you have a good name for it? Do you know of anywhere in the literature where this issue is investigated?
Off the top of my head the only vaguely related things I know about in the literature is a 1975 paper of Swarup's.
Let $L$ be a Galois number field over $mathbb{Q}$. Based on classical algebraic number theory (specifically, the Chebotarev density theorem), I can answer lots of numerical questions about how primes $pinmathbb{Z}$ split in $mathfrak{O}_L$. For example the probability that $p$ splits completely is $1/[L:mathbb{Q}]$, and the average number of factors is the sum over the Galois group of the reciprocals of the orders (so, for a quadratic extension, we get $1+1/2=3/2$ since half the primes split, and half don't.
My question: Another question one can ask is if the factors of $p$ are principal (since $L$ is Galois, they are all conjugate, and thus all principal or all not). Are there any quantitative results about this?
One might optimistically hope that the probability of this is the reciprocal of the class number, but I have no idea if this is true.
The other book suggestions are all so far excellent; the only caveat with them is that they all get into the number theoretic aspects very soon. I am taking the guess that you are more geometrically minded since you are starting with algebraic geometry rather than with number theory.
Also I am taking the guess that you are reading algebraic geometry from the standard book of Hartshrone. I assume you are reading the first chapter.
My advise to you would be to first understand affine and projective varieties as given in Chap I. of Hartshorne, and then move straight ahead to chapter IV on algebraic curves. You would have to take a few things like the Riemann-Roch theorem(rather, Serre duality theorem) for granted and you would have to replace any occurrence of "scheme" with variety, and there may be a few gaps. I suggest that you ignore these and read it. This will give you a very solid and rather modern introduction into the subject algebraic curves, and to elliptic curves in particular.
Afterwards you can go back to chaps. II and III and read the theory of schemes and the machinery of sheaf cohomology, if you wish to further pursue algebraic geometry.
I am not sure if the 3-dimensional problem formulated in the question is the proper analogue of the 2-dimensional one for triangles - essentially because of the appearance of Dehn invariants and such.
At least the following modification of the question can be answered using the results of Dupont and Sah:
Given a combination of side lengths and dihedral angles $sum l_iotimes frac{theta_i}{2pi}inmathbb{R}otimes(mathbb{R}/mathbb{Z})$, is there a euclidean polytope having this element as Dehn invariant?
The answer is given by an exact sequence which you can find in Section 4 of J.L. Dupont and C.-H. Sah: Homology of euclidean groups of motions made discrete and euclidean scissors congruences. Acta Math. 164 (1990), 1--27:
$$
0to mathcal{P}(mathbb{R}^3)/mathcal{Z}_2(mathbb{R}^3)stackrel{D}{longrightarrow} mathbb{R}otimes(mathbb{R}/mathbb{Z}) stackrel{J}{longrightarrow} H_1(SO(3),mathbb{R}^3)to 0
$$
In this sequence, $mathcal{P}(mathbb{R}^3)$ are scissors congruence classes of polytopes in $mathbb{R}^3$, $mathcal{Z}_2(mathbb{R}^3)$ are the scissors congruence classes of prisms, $D$ is the Dehn invariant and $J(lotimes frac{theta}{2pi})= frac{1}{2}lfrac{dcostheta}{sintheta}$ using the identification $H_1(SO(3),mathbb{R}^3)congOmega^1_{mathbb{R}}$ with absolute Kähler differentials.
So, if you are given the six dihedral angles for the tetrahedron, it is at least in principle possible to figure out if there are six side lengths which give a realizable Dehn invariant. Unfortunately the theorem does not tell you if the Dehn invariant will be realizable by a tetrahedron - the theorem generally does not tell you how to construct the polytope realizing the Dehn invariant...
Anyway, there are analoguous exact sequences for hyperbolic and spherical scissors congruence classes. For hyperbolic scissors congruences you get in particular
$$
mathcal{P}(mathbb{H}^3)stackrel{D}{longrightarrow}mathbb{R}otimes(mathbb{R}/mathbb{Z})to H_2(SL_2mathbb{C},mathbb{Z})^-to 0
$$
where $mathcal{P}(mathbb{H}^3)$ is the group of scissors congruence classes in hyperbolic 3-space, and $H_2(SL_2mathbb{C},mathbb{Z})^-$ is the $-1$-eigenspace of complex conjugation on $H_2(SL_2mathbb{C},mathbb{Z})$. For spherical scissors congruence the $+1$-eigenspace appears. This can be found in papers of Dupont, Sah, or the book "Scissors congruences, group homology and characteristic classes" by J.L. Dupont. The map $mathbb{R}otimes(mathbb{R}/mathbb{Z})to H_2(SL_2mathbb{C},mathbb{Z})^-$ can be identified with the reduction $S^2mathbb{C}^timesto K_2(mathbb{C})$ from a symmetric square of the units of $mathbb{C}$ to $K_2$, though that may not necessarily be considered explicit. At least, this tells you that there is a precise obstruction to realizing a linear combination of side lengths and dihedral angles as the Dehn invariant of some hyperbolic or spherical polytope. It is probably further significant work to produce precise conditions for realizability by tetrahedra.
A priori, it does not make sense to talk about complete boundedness, since there are no specified operator space structure on $A_1$ and $A_2$.
In general, an infinite-dimensional Banach space can carry many incomparable operator space structure. Most prominently, there is the minimal and the maximal operator space structure (see Chapter 3 in the book of Gilles Pisier (see here). These two almost never the same.
There are criteria (also due to Pisier) which ensure that certain bounded maps between $C^*$-algebras are automatically completely bounded. This is related to the notion of length of a $C^*$-algebra. This is also explained in his book.
Using the duality between locally compact Hausdorff spaces and commutative $C^*$-algebras one can write down a vocabulary list translating topological notions regarding a locally compact Hausdorff space $X$ into algebraic notions regarding its ring of functions $C_0(X)$ (see Wegge-Olsen's book, for instance). For example, we have the following correspondences:
$$
;;;text{open subset of $X$}quad longleftrightarrowquadtext{ideal in $C_0(X)$}
$$
$$
;;;;;quadtext{dense open subset of $X$}quad longleftrightarrowquadtext{essential ideal in $C_0(X)$}
$$
$$
;;;quadtext{closed subset of $X$}quad longleftrightarrowquadtext{quotient of $C_0(X)$}
$$
$$
text{locally closed subset of $X$}quad longleftrightarrowquadtext{subquotient of $C_0(X)$}
$$
$$
;;;quadqquadqquadqquadqquadtext{???}qquadqquad longleftrightarrowquadtext{$C^*$-subalgebra in $C_0(X)$}
$$
By ideal I always mean a two-sided closed (and hence self-adjoint) ideal.
Well, I can't quite see how to reconvert a $C^*$-subalgebra in $C_0(X)$ into something topological involving only the space $X$ (and some data describing the subalgebra in topological terms). Can you come up with something handy?
Example: A simple example of a subalgebra of a commutative $C^*$-algebra not being an ideal is
$$
mathbb Ccdot(1,1)subset mathbb Coplusmathbb C.
$$
First attempts: Instead of talking about a subalgebra, we should probably talk about the injective $^* $-homomorphism given by the inclusion of this subalgebra. But is this inclusion proper (i.e., does it preserve approximate units) in general? Well, at least when we restrict to compact spaces. Then an injective $^* $-homomorphism $C(Y)to C(X)$ will induce a surjective continuous map $Xto Y$. How to proceed?
Remark: Alternatively, we could think about this question within the duality of affine algebraic varieties and finitely generated commutative reduced algebras or even within the duality between affine schemes and commutative rings.
Disclaimer: I posted this question yesterday on MSE. I also got an interesting answer. However, I'm not yet fully satisfied. If I violate any policy by reposting the question here, please tell me about it.
There are lots of terrific graph theory books now, most of which have been mentioned by the other posters so far. I would particularly agree with the recommendation of West; one of the most complete and well-written texts there are.
But to me, the most comprehensive and advanced text on graph theory is Graph Theory And Applications by Johnathan Gross and Jay Yellen. Crystal clear, great problems and contains probably the best chapter on topological graph theory there is in any source by 2 experts in the field. It's pricey, but well worth it.
And of course, anything by Bollobas is beautiful. The problem with Bollobas, though, is that it treats graph theory as pure mathematics while the books by Gross/Yellen and West have numerous applications. Like linear algebra, the applications of graph theory are nearly as important as its underlying theory.
I don't know a name, but I'll give you a different characterization. Biconnectivity is sufficient but too strong, while "having minimum degree at least 2" is necessary but too weak. I'm almost certain this is a necessary and sufficient condition:
$G$ has minimum degree at least 2, and if v is a cutvertex of $G$, then there is some new connected component of $G - v$ with at least two vertices adjacent to v.
Here's a proof of sufficiency: If v is not a cutvertex of $G$, then pick any two vertices adjacent to v. There's a path between them not going through v (since $G - v$ is connected), so v is contained in a cycle.
If v is a cutvertex of $G$, then pick the two vertices adjacent to v that are in the same connected component of $G - v$. There's a path between them that extends to a cycle containing v.
Now, a proof of necessity. Suppose that $G$ has a cutvertex $v$ whose removal does create deg(v)-1 new connected components. Then $v$ can't lie in a cycle. (This is easy to check.)
This characterization is equivalent to: Removing any vertex of degree d increases the total number of connected components by at most $d-2$. Some generalization of this property may have a name.
Several people have given excellent answers to your second question, so let me address the first.
2) As far as I remember, PA do not have a "built-in" scheme for inductive definitions. So I assume that it is not immediately clear how to define things like $x_n$ or the $n$-th Fibonacci number. How do they do things like that? One can define some specific coding of finite sequences of numbers and use that, but this is so ugly and so specific to aritmetics, it there a better way?
Permitting definitions by primitive recursion moves you from Peano arithmetic to Godel's System T. This is a conservative extension of Peano arithmetic, which also allows defining functions by recursion over the natural numbers.
In the modern presentation (due to Tait, IIRC), the idea is that we move from a first-order logic with a domain of natural numbers, to a multi-sorted first-order logic, where quantification is permitted over functions of higher type in addition. So the sorts of the logic are types like $mathbb{N}$, $mathbb{N} to mathbb{N}$, $(mathbb{N} to mathbb{N}) to mathbb{N}$, and so on. The terms of higher type are given by a simple typed lambda calculus (i.e., a simple functional programming language).
One of the nice things about System T is that even though it is conservative over Peano arithmetic, it also makes the step from arithmetic to analysis much easier to see. Since a real number can be represented by a term of type $mathbb{N} to mathbb{N} times mathbb{N}$ (e.g, as a Cauchy sequence of rationals), in this setting it's easy to understand exactly how much extra axiomatic strength various theorems of analysis need beyond basic Peano arithmetic. As F.G. Dorais has already mentioned, Simpson's Subsystems of Second-Order Arithmetic is the standard reference here.
Throughout, by finite triangulation I mean a triangulation consisting of a finite number of triangles.
Suppose $T$ and $T'$ are finite triangulations of a 3-manifold $M$. We will say that $T'$ is simpler than $T$ iff $T'$ consists of the same number or fewer triangles than $T$ and that $T'$ is a simplest triangulation of $M$ iff $forall$ triangulation $T$ of $M$, $T'$ is simpler than $T$.
Note: If a 3-manifold $M$ has a finite triangulation, then clearly it has a simplest triangulation.
By a theorem of Pachner (Theorem A.1.1. in 'The geometry of dynamical triangulations') any two triangulations of a manifold can be transformed from one to another by a finite number of stellar subdivisions. As we are only dealing with 3-manifolds, there are only 4 stellar subdivisions; known as the $1 to 4$, $2 to 3$, $3 to 2$ and $4 to 1$ moves as described in http://at.yorku.ca/t/a/i/c/45.pdf and hereafter called the Pachner moves. So clearly, there exists a finite sequence of Pachner moves from any finite triangulaiton $T$ of $M$ to $T'$, a simplest triangulation of $M$.
If $T$ is a finite triangulation of $M$, does the greedy algorithm of just applying as many $4 to 1$ and $3 to 2$ Pachner moves to $T$ as possible always result in a simplest triangulation of $M$?
Or alternatively,
Is there a finite triangulation $T$ of a 3-manifold $M$ such that repeatedly applying only the $4 to 1$ and $3 to 2$ Pachner moves does not eventually result in a simplest triangulation of $M$?
It is enough to show that the complement of $U$ has empty interior. Also, that complement is contained in the zero set $Z$ of a non-constant polynomial $f$, so it is enough to show that $Z$ does not contain open sets.
If $zin Z$ is a point in the interior of $Z$, then the Taylor series of $f$ at $z$ is of course zero. Since $f$ is an entire function, this is absurd.
The answer to your very last question is yes. As for the rest:
Computing the parity up to N is, in theory, quasi linear by using Pentagonal Number Theorem: compute the inverse of the pentagonal number power series mod $x^N$. This is of course faster than the quadratic-complexity "en masse" method of using simply the recurrence relation. I am not sure how inverse_mod is actually computed in sage, but it ran fine for the following code:
def get_parity(n):
x = GF(2)['x'].0
f = 1
for k in xrange(1,sqrt(2*n/3)+10):
f += x^((k*(3*k-1))/2) + x^((-k*(-3*k-1))/2)
return f.inverse_mod(x^n).coeffs()
def get_best(l):
n = len(l)
highest, lowest = [0,0,0], [0,0,1]
for a in [1..sqrt(n)]:
for b in [0..a-1]:
score = (l[b::a].count(1) + 0.0)*a/(n-b)
if score > highest[2]:
highest = [a, b, score]
elif score < lowest[2]:
lowest = [a, b, score]
return highest, lowest
l = get_parity(2^22)
best = get_best(l[:2^21])
for x in best:
print x[2], (l[x[1]::x[0]].count(1)+0.0)*x[0]/(len(l)-x[1])
What this does is calculate for every a.p. $an+b$ the density of odd values, and finds the two a.p.'s with most and least odd values.
get_parity took more than 20 minutes (not sure exactly since I was watching TV), and get_best took almost an hour (again, I think). I'm running a macbook pro with 4gb ram.
The results were:
(1442, 766) 0.557846694263366 0.531611381990907
(1389, 357) 0.440522320970815 0.468967411597574
This is to say that the most special a.p.'s up to $2^{21}$ become a bit less special when going up to $2^{22}$, and quite close to equidistribution. Hence, I would say that yes, the computer does suggest that the analogous result holds when we restrict n to lie in a fixed arithmetic progression.
Edit 1: If we change the "score" of an a.p. to:
$$frac{\#{odd\ in\ a.p.} - \#{even\ in\ a.p.}}{sqrt{length}}$$
Then up to $2^{21}$ the largest values are:
(712, 254) 4.84633129231862
(1389, 357) -4.60795692951670
In general it could happen that the Albanese variety does not admit a principal polarization at all. For instance the Albanese variety of an abelian variety is the Abelian variety itself. So choose $X$ to be some abelian variety that has no principal polarization and you will get an example.
On the other hand it can happen that the Albanese variety is principally polarized. For instance you can take the Albanese of the $n$-th symmetric product of a curve. It is equal to the Jacobian of the curve and so admits a principal polarization. Or if you want to be fancier you can take a hyperplane section in the symmetric product of a curve. It will also have the Jacobian of the curve as its Albanese variety.
Another useful comment is that the Albanese of $X$ is the dual of $Pic^{0}(X)$ and so $Alb(X)$ admits a principal polarization if and only if $Pic^{0}(X)$ does. If you fix an ample line bundle $L$ on an $n$-dimensional complex projective variety $X$, then $L$ induces a natural polarization on $Pic^{0}(X)$: the universal cover of $Pic^{0}(X)$ is naturally identified with $H^{1}(X,O_{X}) = H^{1,0}(X)$, the integral $(1,1)$ form $c_{1}(L)$ then induces a Hermitian pairing on $H^{1,0}(X)$ by the formula
$$
h(alpha,beta) := -2i int_{X} alphawedge bar{beta} wedge c_{1}(L)^{wedge (n-1)}.
$$
This $h$ defines a polarization on $Pic^{0}(X)$. The construction of $h$ is purely cohomological and so it is straightforward to check if it defines a principal polarization by computing the divisors of this polarization.
As I mentioned in my comment, you can prove the statement and its converse by looking at the moment generating function. Supposing that f ≥ 0 and λ > 0 is a real number, the following is true for a Poisson point measure ξ with Eξ = μ,
$$mathbb{E}left[e^{-lambdaxi f}right]=expleft(-muleft(1-e^{-lambda f}right)right).$$
You can calculate the probability that ξf is finite from this using monotone convergence,
$$mathbb{P}left(xi f lt inftyright)=lim_{lambdadownarrow 0}expleft(-muleft(1-e^{-lambda f}right)right).$$
If μ(f∧1) <∞ then (1-e-λf) ≤ f∧1 for all λ ≤ 1, so dominated convergence gives μ(1-e-λf) → 0 as λ →0. So, E[e-λξf] → 1. This gives ξf < ∞ almost surely.
Now, for the converse statement: If μ(f∧1) = ∞ then, using (1-e-λf) ≥ ½ λ(f∧1) for λ ≤ 1 shows that μ(1-e-λf) = ∞. So, E[e-λξf]=0, giving ξf = ∞ almost surely.
And, yes, the Kolmogorov-zero one law does indeed imply that ξf < ∞ with probability 0 or 1. Splitting the space up into a countable sequence of measurable sets Sn on which both μ and f are bounded, then we want to know if the sum ∑nξ(1Snf) of independent random variables is finite, which is a tail event.
Looking at my copy of Kallenberg I see that the statement you give, and I have just proven above, is Lemma 12.13. Precisely quoting his proof:
If ξ|f| < ∞ a.s. then μ(|f|∧1) < ∞ by Lemma 12.2. The converse implication was established in the proof of the same lemma.
Looking at his Lemma 12.2, it is the statement of the moment generating function which I just used. Like you say, it doesn't seem like he does establish the converse implication at all. However, it is a relatively simple step using my argument above.
I would like to add a further analogy and an application for the case of the complex complete flag manifold $G/B$. In this case $ X = G = SU(N)$ is isomorphic (as a homogeneous space) to its principal homogeneous space: the Stiefel manifold $V_{n-1}(mathbb{R}^n)$, as given in the following wikipedia page.
In both cases of the sphere and the Stiefel manifold, they can be given as (intersection of) quadrics. in $mathbb{C}^n$ (the stiefel manifold can be identified with the space of full rank $ntimes (n-1)$ matrices satisfying $bar{M}^t M = 1$). Of course, the case of the standard Hopf fibration (X = S^3, M = S^2) is mutual to both cases.
This construction can be applied to perform integrations over the $SU(n)$ invariant measures
of the complex projective spaces and complete flag manifolds: Integration over spheres and Stiefel manifolds is relatively straightforward because they can be performed on quadric constraint surfaces in $mathbb{C}^n$. The integrals can be converted to (a series of) Gaussian integrals by means of Fourier transforms.
Functions on the complex projective spaces and complete flag manifolds can be extended to functions on the total manifolds, the sphere and the Stiefel manifold by defining them to be constants along the torus fibers.
In the case of the complex projective spaces, the sphere is identified with the space of
unit vectors in $mathbb{C}^n$ and the complex projective space with the projectors onto these vectors. Thus any function on the sphere which depends solely on the projectors of the unit vector is an extension of a function on the complex projective space and its integral on the sphere is proportional to the integral of the original function on the complex projective space.
In the case of the complete flag manifold, the Stiefel manifold may be considered as the space of orthonormal frames in $C^n$, (the column vectors of $M$) and the flag manifold as the space of projectors onto these vectors. Again, functions on the Stiefel manifold depending solely on the projectors of the frame vectors are extensions of functions on the flag manifolds.
You should learn about the hyperfinite II_1 factor, which is the limit of the inclusions
M_1 --> M_2 --> M_4 --> M_8 --> ....
(here M_k is the k by k matrices over $mathbb{C}$) where each inclusion is given by tensoring with the identity matrix in M_2. Every 'finite' element is "self-similar" in a sense.
Consider a simple 3-polytope P, (so every vertex has 3 neighbors). If $p_k$ is the number of faces of P which are k-gonal, Euler's theorem implies that
$$(*) ~~sum_{k ge 3} (6-k)p_k=12.$$
Note that 6-gonal faces do not contribute to the LHS.
One way to think about it is that polygonal faces with 7 and more sides contribute "negative curvature", small faces namely triangles quadrangles and pentagons, contribute positive "curvature" and hexagons are "flat".
Eberhard's theorem asserts that if you have a sequence of numbers $p_k, k ne 6$ such that $sum_{k ge 3} (6-k)p_k=12$ then you can find a simple 3-polytope with $p_k$ k-gonal faces. (But you have no control on $p_6$).
There are various results extending Eberhard's theorem in various directions. Chapter 13 in Grunbaum's book "Convex Polytopes" and especially the supplemantary material at the end of the chapter in the new 2nd edition is a good source. Another general source is my chapter from the "Handbook of Discrete and Computational geometry" on garphs and skeleta of polytops.
A relatively recent paper on the subject is by Stanislav Jendrol "On the face vectors of trivalent convex polyhedra". Another paper by Jendrol which deals with general 3-polytopes from the same year is "On face vectors and vertex vectors of convex polyhedra" Discrete Math 118 (1993)119-144. There are analogs of Eberhard theorem for 4-regular planar graphs, for toroidal graphs and in other directions.
A far as I know, there is no good answer known for the question posed by Shephard of characterizing all sequences $(p_3,p_4,dots)$, and no such characterization is known even for the simple case.
In higher dimensions and even in four dimensions there are various different ways to extend these problems, these problems become very difficult and very little is known.
You can ask again about the numbers of k-gonal 2-dimensional faces. While the formula above implies that in dimension 3 and more $p_3+p_4+p_5>0$ it is known that in dimensions 5 and more $p_3+p_4>0$.
Perhaps an even more natural extension is to consider the type of facets a given d-simensional polytope have. You can ask for a simple 4 polytope (a 4-polytope whose graph is 4-regular) what are the number of facets $p_Q$ isomorphic to a given 3-polytope Q. This gives you a vector indexed by combinatorial types of simple 3-polytopes, but I am not aware of any Eberhard type theorem and I do not know even which 3-polytopes should be considered as the analogs of the hexagons in the above formula. Dually stated and extented to triangulations of 3-spheres the question is to associate to a triangulated 3-simensional sphere (or just simplicial 3-polytope) the list of links of vertices (with multiplicities) it has. A related MO question is this one.
Rather than classifying the facets according to their full combinatorial type we can classify them according to their own number of facets. Here, for dimension greater than 4 there is no analog for (*). It is possible that under wide circumstences the numbers of facets with k facets can be prescribed, but I am not aware of results in this direction.
Precscribing the entire vector of face numbers of the individual facets, may well be the most interesting extension from 3 to higher dimensions.
There are some reasons to jump from dimension 3 directly to dimension 5. The nature of the problem is different in even and odd dimensions. Let me try to elaborate on that.
Suppose you have a simple 5-polytope P and denote by $p_{a,b}$ the number of facets F so that $f_3(F)=a$ and $f_2(F)=b$. (For a polytope or some other cell complex X, $f_i(X)$ denotes the number of $i$-dimensional faces of $X$.) Dually, we can consider a triangulation $K$ of the 4-simensional sphere $S^4$ and let $p_{a,b}$ be the number of vertices whose link has $a$ vertices and $b$ edges.
Now the Dehn-Sommervill relations imply that
$$(**) sum p_{a,b} (b-6a+30) = 60 .$$
So now we can consider 4 dimensional facets as "small" if b-6a+30 is negative, as "large" if $b-6a+30$ is positive, and as neutral if $b=6a-30$. An analog of Eberhard theorem will say that you can prescribe the types of small and large facets and realize the polytope (or the triangulated sphere) by allowing to add many "neutral" facets.
A related question that was studied in several papers is: for which d-polytopes P there is a (d+1) polytopes Q such that all faces of Q are isomorphic to P. Such polytopes P are called "facets". An intriguing open problem is if the icosahedron is a facet.
Simple polytopes are dual to simplicial polytopes, and there is some special interest in these problems for cubical complexes (or their duals). Indeed there is an analog of Eberhard's theorem for 3-polytopes with all vertex degrees 4. There should be an analog for (**) and this may be related to interesting questions about curvature of cubical complexes.
A stack polytope is a polytope obtained by gluing simplices along facets. (They are related to Appolonian circle packing.) Stacked polytopes are simplicial. I do not know if there is an analog of Eberhard's theorem when we consider only simple 3-polytope which are dual to stacked 3-polytopes. This is also interesting for other dimensions. All facets of stacked 5 polytopes are stacked and their number of edges is four times the number of vertices minus 10. Therefore, for a dual-to-stacked 5 polytope formula (**) reduces to $$sum p_{a,b}(10-a)=30.$$ (Here, $b=4a-10$ so we can omit the subscript $b$.) So in this case, the distinction is between facets with $a<10$, those with $a>10$ and those with $a=10$. Again we can look for some analogs for Eberhard's theorem, which in this case, might be easier.
I will work over $mathbb C$. Although I have not checked, the example below should work for characteristic different from $3$.
To exhibit a degree $d$ projective surface $S subset mathbb P^3$ not containing any line you can consider surfaces of the form $t^d = f(x,y,z)$ where $f$ is homogeneous polynomial of degree $d$.
Let $C subset mathbb P^2$ be the curve determined by the polynomial $f$ and $pi: S to mathbb P^2$ be the linear projection from the point $p=[0:0:0:1]. $ If $ell$ is a line contained in $S$ then $pi(ell)$ is a line tangent to $C$ at a total inflection point $q$, i.e. the contact between $C$ and the line $pi(ell)$ at $q$ is of order $d$. For details see Section 6 of Counting lines on surfaces by Boissière and Sarti.
This reduces the problem of finding a surface without lines to the one of finding an
algebraic curve without total inflection points. For quartic curves we have not to look much, as Klein determined all the inflections of his famous quartic
$$
x^3y + y^3 z+ z^3 x = 0.
$$
All its $24$ inflection points are simple, see for instance Jeremy Gray's paper in
The Eightfold Way: The Beauty of Klein's Quartic Curve. Thus the surface
$$
t^4 - x^3 y - y^3 z - z^3 x =0
$$
has no invariant lines.
It should be possible to pursue this argument further to determine the sought examples.
Edit: The quartic surface above ( as any quartic of the form ${ t^4- f(x,y,z)=0 }$ ) has many conics, as the pre-image of a bitangent line (there are $28$) is the union of two conics. On the other hand, the surface
$$
t^5 - x^4y - y^4 z - z^4 x =0
$$
seems to be a good candidate for a quintic without lines nor conics.