at.algebraic topology - a naive question about homogeneous polynomials

Assume that $p$ is non-zero. If the form $dp/p$ were exact, then locally a primitive would be $log(p)+const$; this is easily seen not to work as soon as you can "loop around" $S$ (e.g. restrict everything to a line intersecting $S$ and see what happens there). Thus the form $dp/p$ is exact if and only if $S$ is empty, and hence if and only if $p$ is constant.

abelian varieties - Distribution of dimensions of factors of the Jacobian of X_0(p)

Let me begin with what was formerly a comment above: the feeling among most experts is probably* that for each fixed $d$, the number of isogeny factors of $J_0(p)$ of dimension $d$ should be small compared to the dimension of $J_0(p)$, i.e. $o_d(p)$.

In what follows, I will cite some results which point in this direction. My overall response is not as logically coherent as I might have liked: perhaps a true expert will do better.

When $p$ is prime, it follows from a 1975 theorem of Ribet (reference below) that the $mathbb{Q}$-rational endomorphism algebra of $J_0(p)$ is the same as the geometric (i.e., $mathbb{C}$-rational) endomorphism algebra, and that this algebra is a product of formally real fields, each being the subfield of $mathbb{Q}$ obtained by adjoining the Fourier coefficients of the various weight $2$ cuspforms of level $p$.

Thus the problem can be viewed as a special case of a popular one in pure algebraic geometry: for which genera $g$ do there exist complex algebraic curves of genus $g$ with, e.g., Jacobians isogenous to a product of elliptic curves? (Or, more generally, with endomorphism algebra containing at least $N$ semisimple factors?) If you count codimensions in the Siegel moduli space corresponding to (say) principally polarized abelian varieties with certain nontrivial endomorphism algebras and the Torelli locus (i.e., of Jacobians), then you find that (at least in many special cases) the sum of these codimensions adds up to more than $frac{g(g+1)}{2}$, the dimension of the Siegel moduli space. Thus unless there is excess intersection between these two loci, for sufficiently large $g$ one expects Jacobians not to be highly decomposed. [This is a cue for Prof. JSE to weigh in on the matter.]

For instance, I think it is at least conjectured that for sufficiently large $g$, no $g$-dimensional Jacobian splits completely into a product of elliptic curves. This is known to be true over finite fields, but maybe not over $mathbb{C}$.

Serre has worked on both the general geometric question and on this special case. In his 1997 JAMS paper, Serre showed that the maximal dimension of a simple isogeny factor of $J_0(N)$ approaches infinity with $N$. I think the result is quantitative, so if you look there you may get the most information currently known on the question you asked.

---

Ribet, Kenneth A. Endomorphisms of semi-stable abelian varieties over number fields. Ann. Math. (2) 101 (1975), 555--562.

---

Serre, Jean-Pierre
Répartition asymptotique des valeurs propres de l'opérateur de Hecke $T_p$. (French) [Asymptotic distribution of the eigenvalues of the Hecke operator $T_p$]
J. Amer. Math. Soc. 10 (1997), no. 1, 75--102.

---

*: I think it's true, and the small number of people I've spoken to about this explicitly (several years ago) thought it was true. We'll see what others have to say.

ct.category theory - What should the definition of "Yoneda property" be?

Well, I'll take a stab at it. I think you're going to want properties $P$ of functors $F$ of the form

$F$ has property $P$ if and only if $forall X$, $F(X)$ has property $P'$

as you'd suggested above. I think we can avoid $P'$ being a natural isomorphism with $h_X$ by making sure it's a property of all of these sets, rather than something we say about it as a functor (on the other hand, if we want to define Yoneda and CoYoneda properties of morphisms, this becomes a problem, and so this is really bothering me philosophically...)

But this definition handles "is a group", "is initial", "is terminal" by "every $F(X)$ is a group", and statements that for a contravariant or covariant (as appropriate) we have a single element. We're going to want to allow products as well to be Yoneda, presumably. Now, $Xtimes Y$ is a product if for any $Zto X, Zto Y$ we get $Zto Xtimes Y$ commuting with projection. So I guess here we might want to have the property "There exist functors $G,H$ such that for all $X$, we have $F(X)=G(X)times H(X)$" perhaps? It avoids quantifying over the category in question, but instead does so over the category of functors, which I haven't thought through terribly well.

Mostly I'm just thinking aloud here, but no one else had much, so I thought I'd throw my two cents in.

graph theory - Proof of Bondy and Chvátal Theorem

Let me restate the theorem for variables.

Notation Read $pbowtie q$ as "$p$ is adjacent to $q$", and $pnotbowtie q$ as "$p$ is not adjacent to $q$".

Theorem Let $G$ be a graph whose order is greater than $2$. Let $v_1$ and $v_2$ be vertices such that $v_1neq v_2 land v_1notbowtie v_2$ and $deg v_1 + deg v_2 ge ninmathbb{N}$. Then $G$ is Hamiltonian iff $G' = G + v_1 v_2$ is Hamiltonian.

Proof Assume $G'$ is Hamiltonian but not $G$. Therefore, by definition, there exists a cycle $(p_1,ldots,p_n)$ in $G$ connecting $v_1$ (at $p_1$) to $v_2$ (at $p_n$) visiting all of $G$'s vertices. If $p_kbowtie p_1$ then $p_{k-1} notbowtie p_n$, since $(p_1,p_k,p_{k+1},ldots,p_n,p_{k-1},p_{k-2},ldots,p_1)$ is a Hamiltonian cycle of $G$. As such, $deg p_n le n - (1 + deg p_1)$, a contradiction.

dg.differential geometry - Existence of Fermi coordinates on a Riemannian manifold

I would answer this question this way:

First, without any further assumptions about the Riemannian metric on $M$, you don't even have a lower bound on the time $t_f$ for which the geodesic exists and does not intersect itself. The geodesic may fail to exist either simply because the metric is incomplete.

Second, if for some reason you know that the geodesic exists for time $t_f$ and does not hit any boundary or singular set of $M$, then you can definitely find Fermi co-ordinates on a neighborhood of the geodesic, but you have no control over the "thickness" of the neighborhood along the geodesic, so it may approach zero.

Third, the answers above hold regardless of whether you know anything about the metric at a single point $p$. That is far too little information, and you can make the metric do anything you want at a point arbitrarily close to the point $p$. As others have indicated, you must assume some information on an neighborhood of $p$, and the conclusion holds only for that neighborhood.

ADDED: Your question is analogous to the following one: Suppose I have a real-valued function $f$ on an interval, and for some (large) value of $k$, I know the $k$-th order Taylor polynomial of $f$ at a point $p$ in the interval. Is there a bound on the first derivative of $f$ on an open interval containing $p$, where the bound and the size of the interval depend only on the coefficients of the Taylor polynomial?

It is easy to show that the answer is no, and essentially the same proof can be used to show that the answer to your question is also no.

RESPONSE TO REVISED VERSION:
1) Yes, if your manifold is open, and you start with a geodesic segment, then there exist Fermi co-ordinates in a neighborhood of the geodesic. But you have no control over the thickness of the neighborhood around the geodesic on which the Fermi co-ordinates exist. It will vary and may approach zero as you approach one of the endpoints of the geodesic segment.

2) I'm a little baffled by why you would want to do everything relative to a background flat metric. Is this metric a natural part of what you need this for? This makes the question a bit contrived for me.

linear algebra - "Transient" of the discrete-time Riccati equation

It is a well-known result that, if the pair $(A,Q^{1/2})$ is stabilizable and the pair $(A, C)$ is detectable, the solution to the discrete-time Riccati recursion

$P(t+1) = A P(t) A^T - A P(t) C^T (CP(t)C^T + R)^{-1} CP(t) A^T + Q$

converges to the unique stabilizing solution of the Algebraic Riccati Equation

$P = A P A^T - A P C^T(CPC^T + R)^{-1}CP A^T + Q$

from any initial positive semidefinite matrix $P(0)=P_0$.

Do you know any result on the behavior of $P(t)$ during the transient, or more generally
for all $t geq 0$? More precisely, I need some result that ensures that $P(t)$ is
stabilizing for all $t geq 0$, under fair conditions on $A$, $C$, $Q$, $R$, and for arbitrary $P_0$.

Thank you very much in advance,

f.

EDIT. Some background: We consider a discrete-time, linear, time invariant system of the form

$x(t+1) = Ax(t) + v(t)$

$y(t) = Cx(t) + w(t)$

where $x(t) in R^n$, $Ain R^{ntimes n}$, $y(t)in R^p$, $Cin R^{ptimes n}$, and $v$ and $w$ are zero-mean, uncorrelated white noises (say, Gaussian) with appropriate dimensions, with variances $Q$ and $R$ respectively. The predictor $hat{x}(t+1|t)$, that is, the best linear estimator of $x(t+1)$ given $y(0), cdots, y(t)$, is given by the Kalman filter. It can be expressed recursively substituting the equations of the Kalman filter into each other. The variance $P(t+1)$ of the corresponding prediction error $tilde{x}(t+1|t) = hat{x}(t+1|t)-x(t+1)$ is then given (recursively) by the Riccati equation.

The "dual" of the linear estimation problem above is the "linear quadratic regulator" problem of optimal control, and the Riccati equation is fundamental also in this context.

Given matrices $Ain R^{ntimes n}$ and $B in R^{ntimes m}$ with $mleq n$, to say that the pair $(A, B)$ is reachable means that the matrix $[B AB cdots A^{n-1}B]$ has full rank ($=n$). The pair $(A, B)$ is stabilizable if with a suitable "change of base" $(A,B)mapsto(T^{-1} A T, T^{-1}B)$ it can be put in the form

$left(left[begin{matrix} A_{11} & A_{12} \\ 0 & A_{22} \\ end{matrix}right], left[begin{matrix} B_1 \\ 0 \\ end{matrix}right]right)$

where $(A_{11}, B_1)$ is reachable and $A_{22}$ is Hurwitz (all eigenvalues in the interior of the unit disk).

Dually, given matrices $Ain R^{ntimes n}$ and $C in R^{ptimes n}$ with $pleq n$, to say that the pair $(A, C)$ is observable means that the matrix

$left[begin{matrix} C \\ CA \\ vdots \\ CA^{n-1} end{matrix}right]$

has full rank. The pair $(A, C)$ is detectable if with a suitable "change of base" $(A,C)mapsto(T^{-1} A T, CT)$ it can be put in the form

$left(left[begin{matrix} A_{11} & 0 \\ A_{21} & A_{22} \\ end{matrix}right], left[begin{matrix} C_1 & 0 end{matrix}right]right)$

where $(A_{11}, C_1)$ is observable and $A_{22}$ is Hurwitz.

Finally, the matrix $P=P^Tgeq 0$ is stabilizing if the "closed loop" matrix $A - KC$ is Hurwitz, where $K = A P C^T(CPC^T + R)^{-1}$.

For more details, see for example the Wikipedia pages on Kalman filter, controllability, observability, and Kalman decomposition. For a full reference, see e.g. A. H. Jazwinski, Stochastic Processes and Filtering Theory.

reference request - Is every real vector bundle over the circle necessarily trivial?

In the spirit of Theo's comment, I'll say something about sufficient conditions.

A real vector bundle over the circle is trivial if and only if it is orientable. I discussed this a bit here.

The main point is that up to isomorphism, every real vector bundle over the circle is either trivial, or the Whitney sum of a trivial bundle with the Mobius bundle. The latter is not orientable.

The other answers at the question I linked to above may also be helpful to you.

rt.representation theory - Representations of the three string braid group

Bruce,
I can give you representants for an open piece of the moduli space (3,3) resp. (3,2,1). I'll add them in Mathematica-form so that you can plug them into any braid you like to work on. The variables a,b,d,x,y,z are the coordinates of the moduli space and l stands for a third root of unity (i dont know how to tell Mathematica to work with roots of unity, so if you know replace l by that thing).
I obtained these representants from the hexagon of 1-dml simples of the modular group and taking the dimension vector (1,1,1,2,1,0) as required. The corresponding moduli problem is then rational (in x,y,z) over that of pairs of 2x2 matrices of rank one. these are rational (in a,b,d). Hope this helps (and sorry for the lengthy formulas below).

sigma1={{-(1 - a - b - d + a d + x - a x - b x - d x + a d x + l x - a l x - b l x - d l x + a d l x - y + a y) z, -(-1 + l) (b + d - a d - l + a l + b l + d l - a d l) z, -(-1 + l) z, -(-1 + l) (1 - a - b - d + a d + l - a l - b l - d l + a d l - y + a y) z, (-1 + l) z, (b + d - a d) (-1 + l) z}, {-(-1 + a) (-1 + l) (1 + l) x y z, -(-b - d + a d + l - a l + b x + d x - a d x - l x + a l x + y - a y + l y - a l y) z, (-1 + l) (-1 + x) z, (-1 + a) (-1 + l) (l + x) y z, -(-1 + l) (-1 + x) z, -(b + d - a d) (-1 + l) (-1 + x) z}, {b (-1 + l) (1 + l) x y z, b (-1 + l) (-1 + x + y + l y) z, (a + b - a d - l + d l - a x - b x + a d x + l x - d l x - a y + l y) z, -b (-1 + l) (l + x) y z, (-1 + l) (a + b - a d - a x - b x + a d x - a y) z, -b (-1 + l) (-1 + x + y) z}, {-(1 - a - b - d + a d) (-1 + l) (1 + l) x z, (-1 + l) (b + d - a d - l + a l + b l + d l - a d l) z, (-1 + l) z, -(1 - a - b - d + a d + l - a l - b l - d l + a d l + x - a x - b x - d x + a d x + l y - a l y) z, -(-1 + l) z, -(b + d - a d) (-1 + l) z}, {-b (-1 + l) (1 + l) x y z, - b (-1 + l) (-1 + x + y + l y) z, (-1 + l) (1 - d - x + d x - y) z, b (-1 + l) (l + x) y z, -(-1 + d + a l + b l - a d l + x - d x - a l x - b l x + a d l x + y - a l y) z, b (-1 + l) (-1 + x + y) z}, {(-1 + a) (-1 + l) (1 + l) x y z, (-1 + a) (-1 + l) (-1 + x + y + l y) z, -(-1 + l) (-1 + x) z, -(-1 + a) (-1 + l) (l + x) y z, (-1 + l) (-1 + x) z, -(-1 + a + b l + d l - a d l + x - a x - b l x - d l x + a d l x + y - a y) z}}

sigma2={{-(1 - a - b - d + a d + x - a x - b x - d x + a d x + l x - a l x - b l x - d l x + a d l x - y + a y) z, -(-1 + l) (b + d - a d - l + a l + b l + d l - a d l) z, -(-1 + l) z, (-1 + l) (1 - a - b - d + a d + l - a l - b l - d l + a d l - y + a y) z, -(-1 + l) z, -(b + d - a d) (-1 + l) z}, {-(-1 + a) (-1 + l) (1 + l) x y z, -(-b - d + a d + l - a l + b x + d x - a d x - l x + a l x + y - a y + l y - a l y) z, (-1 + l) (-1 + x) z, -(-1 + a) (-1 + l) (l + x) y z, (-1 + l) (-1 + x) z, (b + d - a d) (-1 + l) (-1 + x) z}, {b (-1 + l) (1 + l) x y z, b (-1 + l) (-1 + x + y + l y) z, ( a + b - a d - l + d l - a x - b x + a d x + l x - d l x - a y + l y) z, b (-1 + l) (l + x) y z, -(-1 + l) (a + b - a d - a x - b x + a d x - a y) z, b (-1 + l) (-1 + x + y) z}, {(1 - a - b - d + a d) (-1 + l) (1 + l) x z, -(-1 + l) (b + d - a d - l + a l + b l + d l - a d l) z, -(-1 + l) z, -(1 - a - b - d + a d + l - a l - b l - d l + a d l + x - a x - b x - d x + a d x + l y - a l y) z, -(-1 + l) z, -(b + d - a d) (-1 + l) z}, {b (-1 + l) (1 + l) x y z, b (-1 + l) (-1 + x + y + l y) z, -(-1 + l) (1 - d - x + d x - y) z, b (-1 + l) (l + x) y z, -(-1 + d + a l + b l - a d l + x - d x - a l x - b l x + a d l x + y - a l y) z, b (-1 + l) (-1 + x + y) z}, {-(-1 + a) (-1 + l) (1 + l) x y z, -(-1 + a) (-1 + l) (-1 + x + y + l y) z, (-1 + l) (-1 + x) z, -(-1 + a) (-1 + l) ( l + x) y z, (-1 + l) (-1 + x) z, -(-1 + a + b l + d l - a d l + x - a x - b l x - d l x + a d l x + y - a y) z}}

EDIT March 9th : The component (3,3;3,2,1) is not able to detect braid-reversion. On the other hand, the component of 6-dimensional representations (3,3;2,2,2) can. A minimal braid that can be separated by this family from its reversed braid is s1^-1s2^2s1^-1s2. One can show that every irreducible component of simple B(3)-representations has a Zariski dense family parametrized by a minimal rational variety. For representations of dimension <= 11 explicit such families are given in this note.

Each of these families can then be turned into a family of 3-string braid invariants over Q(rho) for rho a primitive 3-rd root of unity by specializing the parameters to random integers. For the family (3,3;2,2,2) mentioned above this can be done in SAGE as follows :

K.=NumberField(x^2+x+1)
a=randint(1,1000)
b=randint(1,1000)
c=randint(1,1000)
d=randint(1,1000)
e=randint(1,1000)
f=randint(1,1000)
g=randint(1,1000)
h=randint(1,1000)

B=matrix(K,[[1,0,0,a,0,f],[0,1,1,0,1,0],[1,1,0,1,0,0],[0,0,1,0,d,e],[0,1,0,b,c,0],[g,0,1,0,0,1]])
Binv=B.inverse()

mat2=matrix(K,[[1,0,0,0,0,0],[0,1,0,0,0,0],[0,0,1,0,0,0],[0,0,0,-1,0,0],[0,0,0,0,-1,0],[0,0,0,0,0,-1]])
mat3=matrix(K,[[1,0,0,0,0,0],[0,1,0,0,0,0],[0,0,l^2,0,0,0],[0,0,0,l^2,0,0],[0,0,0,0,l,0],[0,0,0,0,0,l]])
s1=h*Binv*mat3*B*mat2
s2=h*mat2*Binv*mat3*B

s1inv=s1.inverse()
s2inv=s2.inverse()

One can then check braid-reversion for all knots with at most 8 crossings that are closures of 3-string braids. Here are the tests to perform

test41=(s1inv*s2*s1inv*s2-s2*s1inv*s2*s1inv).trace()
test52=(s1inv**3*s2inv*s1*s2inv-s2inv*s1*s2inv*s1inv**3).trace()
test62=(s1inv**3*s2*s1inv*s2-s2*s1inv*s2*s1inv**3).trace()
test63=(s1inv**2*s2*s1inv*s2**2-s2**2*s1inv*s2*s1inv**2).trace()
test73=(s1**5*s2*s1inv*s2-s2*s1inv*s2*s1**5).trace()
test75=(s1inv**4*s2inv*s1*s2inv**2-s2inv**2*s1*s2inv*s1inv**4).trace()
test82=(s1inv**5*s2*s1inv*s2-s2*s1inv*s2*s1inv**5).trace()
test85=(s1**3*s2inv*s1**3*s2inv-s2inv*s1**3*s2inv*s1**3).trace()
test87=(s1**4*s2inv*s1*s2inv**2-s2inv**2*s1*s2inv*s1**4).trace()
test89=(s1inv**3*s2*s1inv*s2**3-s2**3*s1inv*s2*s1inv**3).trace()
test810=(s1**3*s2inv*s1**2*s2inv**2-s2inv**2*s1**2*s2inv*s1**3).trace()
test816=(s1inv**2*s2*s1inv**2*s2*s1inv*s2-s2*s1inv*s2*s1inv**2*s2*s1inv**2).trace()
test817=(s1inv**2*s2*s1inv*s2*s1inv*s2**2-s2**2*s1inv*s2*s1inv*s2*s1inv**2).trace()
test818=(s1inv*s2*s1inv*s2*s1inv*s2*s1inv*s2-s2*s1inv*s2*s1inv*s2*s1inv*s2*s1inv).trace()
test819=(s1**3*s2*s1**3*s2-s2*s1**3*s2*s1**3).trace()
test820=(s1**3*s2inv*s1inv**3*s2inv-s2inv*s1inv**3*s2inv*s1**3).trace()
test821=(s1inv**3*s2inv*s1**2*s2inv**2-s2inv**2*s1**2*s2inv*s1inv**3).trace()

The following tests should give non-zero invariants : 6.3,7.5,8.7,8.9,8.10 (which are known as 'flypes' in the theory) and 8.17 (the non-invertible knot with minimal number of crossings). I tried to include all details in the note Rationality and dense families of B(3) representations. All comments to this text are welcome. I like to thank Bruce Westbury for providing me with feedback.

soft question - Co-Objects are better

Dear Martin,

As Harry points out in his comments, in certain settings (e.g. moduli spaces) an object is characterized by maps in. In others (e.g. the free abelian group on one generator), the characterization is by maps out.

Certainly in algebra, injective objects (characterized by maps in) are typically regarded
as more mysterious and black-box like than projectives (where one can typically think of
free modules, which are quite concrete). I know several situations in which someone made real progress by judicious use of injective objects, and I'm sure part of the obstruction to previous researchers was just that injectives are not as familiar; in short, there
is probably arbitrage to be gained for some (myself, at least) by learning more about injectives in various contexts,
and trying to use them as fluently as one uses free objects.

In topology and geometry, perhaps there is more fluidity between the two characterizations.
E.g. maps into the circle make it the Eilenberg-Maclane space $K({mathbb Z},1)$, while
maps out define the fundamental group.

You are correct that quotienting by an equivalence relation (gluing) is related to
maps out. Perhaps this is one reason why the construction of moduli spaces (e.g. Picard
schemes) can be quite involved; they are characterized by maps in, but are often
constructed by a gluing procedure, which creates conflict; thus one finds oneself working locally, and is led into sheaf/stack-theoretic issues.

Certainly, the tension between the two characterizations has been a fertile source for
good mathematics.

analytic number theory - Evaluating Shintani cone zeta functions

Hi everyone

I am trying the evaluate sums of the form
$$ sum_{n_1>0,n_2>0,ldots,n_m>0} frac{1}{big((a_{1,1}n_1 +ldots +a_{1,m}n_m)^k ldots (a_{m,1}n_1+ ldots +a_{m,m}n_m)^kbig)}$$
for general $a_{1,1},ldots,a_{m,m} in mathbb{C}$ (I probably also need to assume real part greater than $0$ to ensure convergence. If you want feel free to assume that $a_{i,j}in bar{mathbb{Q}}$ and the ${a_{i,j}}$ for fixed $j$ constitutes an orbit under $G_{mathbb{Q}}$, although it probably won't make any difference). Sums of this type was considered by Shintani in the seventies. He used geometric series and the integral formula for the gamma function to turn it into a multiple integral of the form
$$ int_{0}^{infty}ldots int_0^{infty}frac{ e^{-(a_{1,1}t_1+ldots+ a_{m,1}t_m)} }{1-e^{-(a_{1,1}t_1+ldots+ a_{m,1}t_m)}}ldots frac{ e^{-(a_{m,1}t_1+ldots+ a_{m,m}t_m)} }{1-e^{-(a_{m,1}t_1+ldots+ a_{m,m}t_m)}}t_1^{k-1} ldots t_m^{k-1} dt_1ldots dt_m$$
however this doesn't seem - to me at least - to be much easier to evaluate explicitly if $m >4$. Hence I would be very interested if anyone out there knows of a trick ( perhaps a functional equation that I don't know of...) which would help me evaluate them. Any thoughts would be welcome.

co.combinatorics - The problem of finding the first digit in Graham's number

Motivation

In this BBC video about infinity they mention Graham's number. In the second part, Graham mentions that "maybe no one will ever know what [the first] digit is". This made me think: Could it be possible to show that (under some assumptions about the speed of our computers) we can never determine the first digit?

In logic you have independence results like "We cannot decide if AC is true in ZF". But we cannot hope for this kind of result in this case, since we can easily program a computer to give us the answer. The problem is, that we don't have enough time to wait for the answer!

In complexity theory you prove things like "no program can solve all problems in this infinite set of problems, fast". But in this case you only have one problem, and it is easy to write a program, that gives you the answer. Just write a program that prints "1" another that prints "2" ... and a program that prints "9". Now you have a program that gives you the answer! The problem is, that you don't know which of the 9 programs that are correct.

Questions

Edit: I have now stated the questions differently. Before I asked about computer programs instead proofs.

1. Could it be possible to show that any proof of what the first digit in Grahams numbers is, would have length at least $10^{100}$?


2. Do there exist similar results? That is, do we know a decidable statement P and a proof that any proof or disproof of P must have length $10^{100}$.


3. Or can we prove, that any proof that a proof or disproof of P must have length at least $n$, must itself have length at least $n$?

I think the answer to 3) is no, at least if all proofs are in the same system. Such a proof would prove that it should have length all least n for any n.

(Old Questions:

1. Could it be possible to show that it would take a computer at least say $10^{100}$ steps to determine the first digit in Grahams number?


2. Do there exist similar results? That is, do we know a decidable statement P and a proof that P cannot be decided in less that say $10^{100}$ steps.


3. Or can we prove that we need at least $n$ steps to show that a decidable statement cannot be decided in less than $n$ steps?)

(I'm not sure I tagged correctly. Fell free to retag, or suggest better tags.)

lo.logic - How many of the true sentences are provable?

Update: in response to comment below, I'm not sure anymore the probability in question was 0.

Let's try the measure that gives an equal weight for any true statement of fixed length $N$ (written in mathematical English).

Then we have statements of the form "S or 1+2=3" which form more then $1/10^{20}$th of all true statements of a given length. On the other hand, the statements "S and Z" (where Z is an undecidable problem) form some positive (bounded below) measure subset in the statements of given length as well.

So, yes, for the measure described above the measure of provable statements is within some positive bounds $[a, b]$ for any $N$ greater than some $N_0$.

But that measure is proportional, for a fixed $N$, to the characteristic function of the set of all true statements, so, no, my answer doesn't give a "natural" measure.

---

I think the probability of "a random true statement is provable" is 0 in any good formalization of your problem.

Here's the reasoning: consider a true undecidable statement S. Now I would say that in any reasonable definition of probability the long statement will contain S with probabilitiy that goes to 1 as its length increases. One can't prove it until there's no definition of this probability, but the related fact for strings is straightforward:

Consider any string S. Then the probability $P(n) := {$the random string of length $n$ contains `S$}$ goes to 1 as $nto infty$.

The proof can be done by considering the random strings of the form (chunk 1)(chunk 2)...(chunk N) where all chunks are of the same length as S.

nt.number theory - Totally real number fields with bounded regulators

I believe the question is: "Does there exist a constant $A$ such that there exists infinitely many totally real number fields with regulator less then $A$?" Ignore this response if that's incorrect.

I think the answer is no. The place to go for questions like this are the work of Zimmert and the survey paper of Odlyzko (which, as it turns out, would've pointed you to Zimmert anyway). You'll have to dig into the references to make sure I haven't misinterpreted a convention or notation, but I believe a proof goes as follows:

In Odlyzko's "Bounds for disciminants...", he cites Zimmert as giving a lower bound (equation 5.5) for the regulator of a number field which grows exponentially in the degree of the number field. So if the answer to your question were yes, your infinitely many number fields would have to be of bounded degree. But for number fields of a fixed degree, Theorem C in Friedman's "Analytic Formula for the Regulator of a Number Field" (attributed to Silverman, from an interesting-looking paper that I'd never heard of before) gives a lower bound for the regulator in terms of the discriminant D. This lower bound goes to infinity with D under the condition that all proper subfields of your number field have a strictly smaller unit rank, which is true for totally real number fields. The nail in the coffin is then that there are only finitely many number fields with discriminant under any given bound, and so only finitely many totally real number fields with regulator under any given bound.

Note that you can't cite the Silverman result right off the bat since the lower bound appears to me to go to 0 as $D$ and $n$ (discriminant and degree) simultaneously go to infinity.

Hope that helps.

gt.geometric topology - A Pachner complex for triangulated manifolds

A theorem of Pachner's states that if two triangulated PL-manifolds are PL-homeomorphic, the two triangulations are related via a finite sequence of moves, nowadays called "Pachner moves".

A Pachner move has a very simple picture. If $N$ is a triangulated $n$-manifold and $C subset N$ is a co-dimension zero subcomplex of $N$ which is equivalent to a subcomplex $D'$ of $partial Delta_{n+1}$ where $Delta_{n+1}$ is an $(n+1)$-simplex equipped with its standard triangulation, then you can replace $N'$ in $N$ by $(partial Delta_{n+1}) setminus D'$ from $partial Delta_{n+1}$, the gluing maps being the only ones available to you.

One way to say Pachner's theorem is that there is a ''graph'' of triangulations of $N$, and it is connected. Specifically, the vertices of this graph consist of triangulations of $N$ taken up to the equivalence that two triangulations are equivalent if there is an automorphism of $N$ sending one triangulation to the other. The edges of this graph are the Pachner moves.

This formulation hints at an idea. Is there a useful notion of "Pachner complex"?

Of course this would lead to many further questions such as what geometric / topological properties does such a complex have, is it contractible for instance, are there "short" paths connecting any two points in the complex, and so on.

I'm curious if people have a sense for what such a Pachner complex should be. For example, some Pachner moves commute in the sense that the subcomplexes $C_1, C_2 subset N$ are disjoint, so you can apply the Pachner moves independantly of each other. Presumably this should give rise to a "square" in any reasonable Pachner complex.

This feels related to the kind of complexes that Waldhausen and Hatcher used to use in the 70's but it's also a little different.

• Udo Pachner, P.L. homeomorphic manifolds are equivalent by elementary shellings, European J. Combin. 12 (1991), 129–145.

mp.mathematical physics - Mathematical explanation of the failure to quantize gravity naively

Let me add a few comments that might fill in some gaps not covered by other answers.

• When would it be safe to say that gravity has been successfully quantized?

A quantum theory consists of an algebra of "observables" (taken often to be a C*-algebra), a "state"---positive linear functional on the algebra, and a way of assigning a Hermitian element of the algebra to each conceivable single-number-outcome experiment. The theoretical prediction for an experiment is given by evaluating the state on the corresponding observable---taking its "expectation value". Higher moments of the same observable give information on the statistical distribution of experimental outcomes under identical conditions. Of course, since physicists don't have perfect information about the state of the entire universe, we are forced to work with a class of states and test hypotheses about which are closest to fitting all available observations.

If the above construction can be carried out such that all experiments sensitive to gravitational effects have representative observables and all their expectation values with respect to states that are approximately classical reproduce the results of classical general relativity, then the result is a successful quantization of gravity.

• Has the above construction succeeded or failed for gravity any more or less than for any other field theory?

This construction has been mathematically rigorously successful for free fields on Minkowski spacetime (and one some classes of curved Lorentzian manifolds, aka spacetimes). Other examples of rigorous constructions exist, but they are not of direct physical relevance. The golden standard of physically relevant field theories is quantum electrodynamics (QED). It has not yet been rigorously constructed. However, assuming that QED exists as a quantum theory and that all expectation values of observables in it can be expanded as power series in the strength of the interaction (electron charge), then each coefficient can be constructed order by order. Existence of a family of quantum theories corresponding to such a series expansion has not been resolved at the mathematical level.

The above construction is referred to as "perturbation theory". Essentially, it's a procedure that starts from a rigorously constructed free theory and constructs an interacting theory, in the above sense, as a power series in a finite number of parameters (coupling constants, which measure the strength of the interaction). This transition from free to interacting (for a given set of coupling constants) is not necessarily unique. Theories for which this non-uniqueness is parametrized by a finite number of parameters are called renormalizable, the rest are called non-renormalizable.

QED and the rest of the standard model have been found to be renormalizable, but perturbative gravity, obtained by expanding around Minkowski spacetime, has been found to be non-renormalizable. In principle, the non-uniqueness in the perturbative construction of interacting field theories needs to be fixed from experimental input. The unbounded number of experimental inputs needed to construct a particular realization of a non-renormalizable field theory is what makes such theories unattractive.

An even bigger failure on the part of gravity is that the classical structure of general relativity (a Lorenzian manifold) enters in an essential way into the construction of free quantum field theories. If it is omitted, we have no way of guaranteeing the correct classical limit of the resulting quantum theory. On the other hand, a Lorentzian manifold should be the result of a classical limit of quantized gravity, not an input to it. This problem has not yet been resolved at the level of theoretical physics.

• What role do Euclidean functional/path integrals play?

The answer to this question is that it is unclear. Euclidean path integrals are equivalent to other constructions of quantum field theories if the space-time manifold has translational symmetry along the time direction. In such cases, given a Euclidean path integral formulation of a field theory (as mentioned in A.J. Tolland's reply), the corresponding quantum theory can be constructed and vice versa.

However, in the case of the gravitational path integral, if it is used as a starting point for a non-perturbative definition, it may not correspond to a quantum theory at all. Since the functional integration is performed over all possible Lorentzian metrics, there is no background time-translation symmetry to speak of. Therefore, even the construction of the Euclidean path integral succeeds, the equivalence to a quantum theory may fail. Again, this question has not yet been resolved even at the level of theoretical physics.

• Are discretization or other non-trivial modifications of the underlying manifold structure of spacetime necessary?

Unknown. However, there is no direct evidence that gravity cannot be formulated as just another field theory on a smooth manifold. In fact, there are counter examples: the infinitely many possibilities for perturbative quantization of gravity on Minkowski spacetime. Recall that non-renormalizability does not mean non-existence, just non-uniqueness. The many proposals that try to do away with a smooth manifold are heuristic at best.

If anyone is interested, I can elaborate on any of the points I've brought up above.

dg.differential geometry - Riemannian surfaces with an explicit distance function?

NB: For some time, I have been meaning to revise this answer to make it more complete (and, to be frank, more accurate), but I never found the time to do it. The main point is that my original answer did not take into account the difference between the cut locus and the conjugate locus, and, of course, this affects the formula for the distance between points.

I'm aware of a few metrics with non-constant curvature for which one can write the distance function explicitly in terms of the coordinates. The simplest such metric I know is the (incomplete) metric $ds^2 = y (dx^2+dy^2)$ on the upper half plane $y>0$. The Gauss curvature of this metric is $K = 1/(2y^3)>0$, so it's not constant.

Every geodesic of this metric in the upper half plane can be parametrized in the form
$$
x = a + b tqquadqquad y = b^2 + frac{t^2}{4}
$$
for some constants $a$ and $b$, and, for such a geodesic, the arclength function along the curve is
$$
s = c + b^2 t + frac{t^3}{12} .
$$
for some constant $c$.

Using these formulae, one finds that two points $(x_1,y_1)$ and $(x_2,y_2)$ are joinable by a geodesic segment if and only if $4y_1y_2 ge (x_1{-}x_2)^2$. In the case of strict inequality, there are two geodesic segments joining the two points, and the length of the shorter segment is
$$
L_1bigl((x_1,y_1),(x_2,y_2)bigr)
= {1over3}sqrt{3(x_1{-}x_2)^2(y_1{+}y_2)+4(y_1^3{+}y_2^3)
- (4y_1y_2-(x_1{-}x_2)^2)^{3/2}} .
$$
Note that, in a sense, this is better than the constant curvature case. Here, the distance function is algebraic in suitable coordinates, whereas, in the constant nonzero curvature cases, the distance function is not.

However, the function $L_1$ does not necessarily give the actual distance between the two points (i.e., the infinimum of the lengths of curves joining the two points), and it's not only because not every pair of points can be joined by a geodesic. To see this, one should complete the upper half plane by adding a point that represents the 'boundary' $y=0$. The Riemannian metric does not extend smoothly across this 'point', of course (after all, the Gauss curvature blows up at you approach this point), but it does extend as a metric space. The vertical lines, which are geodesics, can then be used to join $(x_1,y_1)$ to $(x_2,y_2)$ by going through the singular point, and the total length of this geodesic is
$$
L_2bigl((x_1,y_1),(x_2,y_2)bigr)
= frac{2}{3}bigl({y_1}^{3/2}+{y_2}^{3/2}bigr).
$$
(Also, note that $L_2$ is defined for any pair of points in the upper half-plane.)
If one doesn't like this path that goes through the singular point, one can easily perturb it slightly to avoid the singular point and not increase the length by much, so it's clear that the infimum of lengths of curves lying strictly in the upper half plane and joining the two points is no more than $L_2$.

This suggests that the true distance function $L$ should be the minimum of $L_1$ and $L_2$ where they are both defined, i.e., where $4y_1y_2 ge (x_1{-}x_2)^2$, and $L_2$ on the set where $4y_1y_2 < (x_1{-}x_2)^2$.

To get a sense of how these two formulae interact, one can use the fact that $x$-translation preserves the metric while the scalings $(x,y)mapsto (ax,ay)$ for $a>0$ preserve the metric up to a homothety (and hence preserve the geodesics and scale the distances). These two actions generate a transitive group on the upper half plane, so, it suffices to see how these two functions interact when $(x_1,y_1) = (0,1)$, i.e., to see the conjugate locus and cut locus of this point.

The conjugate locus is easy: It's just $y-x^2/4=0$, which is the boundary of the region $y-x^2/4ge0$ consisting of the points that can be joined to $(0,1)$ by a geodesic segment. Meanwhile, the cut locus is given by points $(x,y)$ that satisfy $y-x^2/4ge0$ and for which $L_1bigl((0,1),(x,y)bigr) = L_2bigl((0,1),(x,y)bigr)$. In fact, one has $L_1bigl((0,1),(x,y)bigr) < L_2bigl((0,1),(x,y)bigr)$ only when $y > f(x)$, where $f$ is a certain even algebraic function of $x$ that satisfies $f(x) ge x^2/4$ (with equality only when $x=0$). Moreover, for $|x|$ small, one has
$$
f(x) = left({frac{{sqrt{3}}}{4}}xright)^{4/3} + O(x^2)
$$
while, for $|x|$ large, one has
$$
f(x) = left({frac{sqrt{3}}{4}}xright)^{4} + o(x^4).
$$

Thus, all of the geodesics leaving $(x,y)=(0,1)$, other than the vertical ones, meet the cut locus before they reach the conjugate locus (and they all do meet the conjugate locus).

Thus, the actual distance function for this metric is explicit (it's essentially the minimum of $L_1$ and $L_2$), but it is only semi-algebraic.

Remark: The thing that makes this work is that, while the metric has only a 1-parameter family of symmetries, it has a 2-parameter family of homotheties (as described above), and this extra symmetry of the geodesics is critical for making this work. Of course, there are other such metrics, all the ones of the form $ds^2 = y^{a} (dx^2+dy^2)$ ($a$ is a constant) have this property and don't have constant curvature unless $a = 0$ or $a = -2$. You don't get algebraic answers for all values of $a$, of course, but there is a way to get $D$ implicitly defined in terms of a special function (depending on the value of $a$).

More generally, the metrics whose geodesics admit more symmetries than the metric itself does tend to have such formulae. I'm not aware of any other cases in which one can get $D$ so explicitly.

rt.representation theory - Resolution of singularities for nilpotent cone of the symplectic group

Ben gave the general answer above. If you care specifically about the symplectic group and are interested in a "flag-like" description of its flag variety, then one exists. It is given by all half-flags of isotropic subspaces (this is just like for $SL_n$, the symplectic group acts transitively and the stabilizer of the standard half-flag will be the standard Borel). With this description, it's just as straightforward computing Springer fibers and the like as it is for the $SL_n$ case, which you're presumably familiar with.

A reference for these flag-like descriptions can be found in the section of Fulton and Harris on "Homogeneous Spaces" (there's a similar description for the special orthogonal groups).

computer science - does the "convolution theorem" apply to weaker algebraic structures?

In general, it is a major open question in discrete algorithms as to which algebraic structures admit fast convolution algorithms and which do not. (To be concrete, I define the $(oplus,otimes)$ convolution of two $n$-vectors $[x_0,ldots,x_{n-1}]$ and $[y_0,ldots,y_{n-1}]$, to be the vector $[z_0,ldots,z_{n-1}]$ with $$z_k = (x_0 otimes y_k) oplus (x_1 otimes y_{k-1}) oplus cdots oplus (x_k otimes y_0).$$ Here, $otimes$ and $oplus$ are the multiplication and addition operations of some underlying semiring.)

For any $otimes$ and $oplus$, the convolution can be computed trivially in $O(n^2)$ operations. As you note, when $otimes = times$, $oplus = +$, and we work over the integers, this convolution can be done efficiently, in $O(n log n)$ operations.

But for more complex operations, we do not know efficient algorithms, and we do not know good lower bounds. The best algorithm for $(min,+)$ convolution is $n^2/2^{Omega (sqrt{log n})}$ operations, due to combining my recent APSP paper

Ryan Williams: Faster all-pairs shortest paths via circuit complexity. STOC 2014: 664-673

and

David Bremner, Timothy M. Chan, Erik D. Demaine, Jeff Erickson, Ferran Hurtado, John Iacono, Stefan Langerman, Perouz Taslakian: Necklaces, Convolutions, and X + Y. ESA 2006: 160-171

A substantially subquadratic algorithm for $(min,+)$ convolution would (to my knowledge) imply a subcubic algorithm all-pairs shortest paths in general graphs, a longstanding open problem. The above ESA06 reference also gives a $O(n^2 (log log n)^2/log n)$ algorithm for a "(median,+) convolution".

The situation is subtle. It's not clear when convolution over a semiring is easy and when it's hard. For instance, the $(min,max)$ convolution can be computed in subquadratic time: I believe that $O(n^{3/2} log n)$ operations suffice. This can be obtained from adapting the $(min,max)$ matrix multiplication algorithm in my work with Vassilevska and Yuster on all-pairs bottleneck paths. Basically you reduce the problem to computing $sqrt{n}$ instances of a $(+,times)$ ring convolution.

ag.algebraic geometry - How to find examples of non-trival kernel of maps between Brauer groups Br(R) -> Br(K)

Background/Motivation: The facts about the Brauer groups I will be using are mainly in Chapter IV of Milne's book on Etale cohomology (unfortunately it was not in his online note).

Let $R$ be a Noetherian normal domain and $K$ its quotient field. Then there is a natural map $f: Br(R) to Br(K)$. In case $R$ is regular, a well known result by Auslander-Goldman says that $f$ is injective. The natural question is when can we drop the regularity condition? But anything in the $Cl(R)/Pic(R)$ will be in the kernel of $f$, so we need that quotient to be $0$ to make it interesting.

Also, it is known that even assuming said quotient to be $0$, one has example like $R=mathbb R[x,y,z]_{(x,y,z)}/(x^2+y^2+z^2)$ which is UFD, but the kernel contains (I think) the quaternion algebra over $R$. The trouble in this case is that $mathbb R$ is not algebraically closed. In fact, if $R$ is local, then $ker(f)$ injects into $Cl(R^{sh})/Cl(R)$, here $R^{sh}$ is the strict henselization. Most of the examples with non-trivial kernel I know seem a little ad-hoc, so:

Question: Are there more general methods to generate examples of $R$ such that $f$ is not injective?

I would love to see answers with more geometric/arithmetic flavors. I am also very interested in the positive and mixed charateristics case. Thanks in advance.

pr.probability - Estimate rate of real correct/wrong from 4 answers quiz.

I recently read that one in ten students think the first man on the moon was Buzz Lightyear, a Toy story cartoon. I'm not here to discuss the data in itself, rather, this reading got me into a problem I like just out of my interest for probability and statistics.

Suppose you have a quiz asking who was the first man on the moon, together with four answers:

1. Benjamin Franklin


2. Neil Armstrong


3. George Harrison


4. Buzz Lightyear

Now, if you give this test to a random number generator and you say they are students, the answers will be 25 % each. Clearly, you cannot declare 1 in 4 students believes Buzz Lightyear was the first man on the moon, and you also cannot declare 1 in 4 students knew the correct answer. It was just probability.

When you take such a test, you have these different cases:

1. people who know the correct answer and mark it


2. people who assume an incorrect answer as correct and mark it and


3. people who have no clue, and mark at random.

The results of the tests contain therefore a bias resulting from the "guessers", but hardly we can say that all people answering "Buzz Lightyear" really believed he was the first man on the moon. Most likely, some of them confused it with Buzz Aldrin and belong to case 2. Some others had no clue and threw a random choice. Same for the correct case: not all those who answered Armstrong really knew it. Some just guessed correctly.

Do you have any reference (or proposed solution) on this specific case to estimate the rate of really correct answers vs. random chance ?

sequences and series - Uniquely generate all permutations of three digits that sum to a particular value?

Visualizing this problem, as unique ways to hand out ninja stars to ninjas. This also shows how each larger solution is made up of its neighboring, more simple solutions.

Here is how to implement it in php: (might help you understand it too)

function multichoose($k,$n)
{
 if ($k < 0 || $n < 0) return false;
 if ($k==0) return array(array_fill(0,$n,0));
 if ($n==0) return array();
     if ($n==1) return array(array($k));
     foreach(multichoose($k,$n-1) as $in){ //Gets from a smaller solution -above as (blue)
  array_unshift($in,0);  //This prepends the array with a 0 -above as (grey)
      $out[]=$in;
     }
     foreach(multichoose($k-1,$n) as $in){ //Gets the next part from a smaller solution too. -above as (red and orange)
  $in[0]++; //Increments the first row by one -above as (orange)
      $out[]=$in;
     }
     return $out;
}

print_r(multichoose(3,4)); //How many ways to give three ninja stars to four ninjas?

Not optimal code: Its more understandable that way.

Our output:

(0,0,0,3)
(0,0,1,2)
(0,0,2,1)
(0,0,3,0)
(0,1,0,2)
(0,1,1,1)
(0,1,2,0)
(0,2,0,1)
(0,2,1,0)
(0,3,0,0)
(1,0,0,2)
(1,0,1,1)
(1,0,2,0)
(1,1,0,1)
(1,1,1,0)
(1,2,0,0)
(2,0,0,1)
(2,0,1,0)
(2,1,0,0)
(3,0,0,0)

Fun use to note: Upc relies upon this exact problem in barcodes. The sum of the whitespace and blackspace for each number is always 7, but is distributed in different ways.

//Digit   L Pattern  R Pattern  LR Pattern (Number of times a bit is repeated)
    0   0001101    1110010    2100
    1   0011001    1100110    1110
    2   0010011    1101100    1011
    3   0111101    1000010    0300
    4   0100011    1011100    0021
    5   0110001    1001110    0120
    6   0101111    1010000    0003
    7   0111011    1000100    0201
    8   0110111    1001000    0102
    9   0001011    1110100    2001

Note only 10 of the 20 combinations are used, which means the code can be read upside-down just fine. All 20 can be used however, and are in EAN13, with a bit more complexity.

http://en.wikipedia.org/wiki/EAN-13

http://en.wikipedia.org/wiki/Universal_Product_Code

http://www.freeimagehosting.net/uploads/58531735d3.png

gr.group theory - Counting the Groups of Order n Weighted by 1/|Aut(G)|

Computational evidence suggests $g(n)$ varies wildly with $n$. When $n$ is a power of a prime, or has lots of small factors, $g(n)$ can be very large (I would guess $g(2^k)$ is superexponential in $k$), and $a(n)$ contributes negligibly. In particular, for the prime power case, three-step nilpotent groups seem to dominate, and a good theoretical reason for this is that they asymptotically dominate in number of isomorphism types by a huge factor.

If $n$ has only a few factors, then $g(n)$ is a little bigger than $1/n$. In this case, $a(n)$ contributes nontrivially.

For those of you who are interested in groups of order $2^n$ (and who isn't?), I've computed a decomposition of $g(2^k), k leq 7$ by nilpotence class, so the class one columns on the left indicate $a(2^k)$, the abelian contribution.

g(2) = a(2) = 1.

nilpotence class |   1  
isom. types      |   1
weighted count   |   1

$g(4) = a(4) = 2/3 sim 0.67$.

nilpotence class |   1  
isom. types      |   2
weighted count   |  2/3

$g(8) = 23/42 sim 0.55$

nilpotence class |     1      |     2    
isom. types      |  3 (60%)   |  2 (40%) 
weighted count   | 8/21 (70%) |  1/6 (30%) 

$g(16) = 1247/2520 sim 0.49$

nilpotence class |       1      |     2     |   3
isom. types      |    5 (36%)   |  6 (43%)  |   3 (21%)
weighted count   | 64/315 (41%) | 1/6 (34%) | 1/8 (25%) 

$g(32) = 149297/312480 sim 0.48$

nilpotence class |        1        |       2      |      3     |   4
isom. types      |     7 (14%)     |   26 (51%)   |  15 (29%)  |  3 (6%)
weighted count   | 1024/9765 (22%) | 37/240 (32%) | 3/16 (39%) | 1/32 (7%) 

$g(64) = 48611383/78744960 sim 0.62$

$begin{array}{rccccc} text{nilpotence class} & 1 & 2 & 3 & 4 & 5 \
text{isomorphism types} & 11, (4%) & 117, (44%) & 114 , (43%) & 22, (8%) & 3, (1%) \
text{weighted count} & frac{32768}{615195} , (9%) & frac{3}{20} , (24%) & frac{5}{16} , (51%) & frac{3}{32} , (15%)& frac{1}{128} , (1%) end{array}$

$g(128) = 8999449693/8000487936 sim 1.12$

$begin{array}{rccccc} text{nilpotence class} & 1 & 2 & 3 & 4 & 5 & 6 \
text{isomorphism types} & 15 , (1%) & 947 , (41%) & 1137 , (49%) & 197 , (8%) & 29 , (1%) & 3 , (0%) \
text{weighted count} & frac{2097152}{78129765} , (2%) & frac{275929}{1451520} , (17%) & frac{2295}{3584} , (57%) & frac{7}{32} , (19%) & frac{3}{64} , (4%) & frac{1}{512}, (0%) end{array}$

The groups of order 64 took about 15 minutes on my ancient computer running GAP, and the groups of order 128 took about 40 hours. I'll leave the question of groups of order 256 to someone else, since a modern desktop computer should be able to work it out in a little under a year.

You might be curious about the three isomorphism types of nilpotence class $k-1$ for $k geq 4$. They are the dihedral, quasidihedral, and quaternion groups.

big list - What category without initial object do you care about?

Any programming languages based on lambda calculus (Haskell, (OCa)ML, Clean, Coq, Agda) forms a category -- in many different ways, in fact. One way is to have an object for each type of the language and a morphism for each well-typed expression with exactly one free variable. If the programming language has linear types then this category will not have a terminal object, since such an object would imply the ability to "discard" a value of any type.

Linear types are extremely useful in giving pure functional programming languages the ability to express side-effecting operations. Loosely, you have a linear type called "world"; every impure function both takes and returns a value of that type (and perhaps other values too). Since you can't duplicate or discard a "world", its handling imposes a deterministic evaluation order on all of the impure functions, and program transformations will not alter this order. The aggregate result of the side effects can then be reasoned about (formally, even).

ag.algebraic geometry - morphisms from abelian varieties to rational curves.

Let E be an elliptic curve and let x,y be points on it. Then the divisor

[x] + [-x] + [y] - 2[2y] - [-3y]

is principal, so is div(f) for some function f:E -> P^1; this function sends x and y to the same point of P^1 (namely, 0) but sends -x and -y to different points (unless you were very unlucky in your choices) so [-1] can't descend along f.

set theory - confusion about forcing

The syntactic method is simply to work inside the forcing relation, by looking at what is forced by which conditions. That is, rather than actually building the forcing extension $V[G]$, you reason as though you were inside it, by means of the forcing relation. For example, if you have condition $p$ forcing various statements $varphi_1$, ... $varphi_n$, and from those statements you can deduce $psi$, then you can conclude that $p$ also forces $psi$. In particular, note that any condition $p$ forces that $dot Gsubsetcheck P$ is $check V$-generic and contains $check p$, so syntactically, you have the filter you want in the sense I described. The point is that you don't actually need to build an actual model using an actually generic filter to gain insight into what is true there, because you have the forcing relation telling you what is forced to be true there.

If you want to build an actual model by forcing over $V$, then the thing to do is to use Boolean-valued models $V^B$, where there is Boolean-valued truth. You can quotient this $B$-valued structrue by an ultrafilter $U$ (no need for any genericity) to arrive at an actual first order 2-valued structure $V^B/U$, which satisfies a version of Los' theorem: $V^B/Umodelsphi$ if and only if $[phi]in U$.

For question 2, if you make your choice of $b(a)$ $p(a)$ inside $M$, then of course $f$ is a function in $M$. But there is little reason to expect that this function $f$ has much relation to the function in $M[G]$ named by $r$, since the conditions $p(a)$ might be incompatible. If you can choose a single $p=p(a)$, then it follows that $p$ forces $r=check f$.

fa.functional analysis - Algebraic Dual / Continuous Dual

Ok Ady, since you like CH I will work with CH, and to make your life
easier, I will work with GCH.

Since I do not expect that everybody in MO is aware of various
Banach space constructions, let me give some information on James
tree spaces which are relevant to the question.

A tree is a partially order set $(T,<)$ such that for every $t$ in $T$ the
initial segment ${sin T: s < t}$ is well-ordered under $ < $.
A segment of $T$ is a subset $S$ of $T$ which is:

1. linearly ordered under $ < $ and


2. for all $s, t, win T$ if $s < t < w$ and $s, w in S$ then $tin S$.

The completion of $T$, usually denoted by $c(T)$, is the collection of all initial
segments of $T$ ordered by inclusion. Notice that $c(T)$ contains $T$ and
is much larger than $T$. For instance, if $T$ is the tree of all finite sequences
of natural numbers (usually called the Baire tree, which is clearly countable),
then its completion is the Baire-tree together with its branches (i.e. the
Baire space) and so it has the cardinality of the continuum.

For every tree $T$ the corresponding James tree space $JT$ is defined to
be the completion of $c_{00}(T)$ with the norm:
$$|v| = sup{ (sum_{i=1}^d (sum_{tin S_i} v(t) )^2 )^{1/2} }$$
where the above supremum is taken over all finite families $(S_i)_{i=1}^d$ of
pairwise disjoint segments of $T$. Basic facts (I can provide appropriate
references to anyone who is interested):

• For every tree $T$ the space $JT$ is hereditarily $ell_2$; that is,
  every infinite-dimensional subspace of $JT$ contains a copy of $ell_2$.


• For every tree $T$ the second dual of $JT$ is linearly isometric to
  the James tree space of the completion $c(T)$ of $T$. In particular,
  neither $JT^* $ nor $JT^{**}$ contain a copy of $ell_1$.

Now we come to the specifics of the construction. Remember that we work
with GCH. This implies, in particular, the following: if $X$ is a Banach
space of cardinality $kappa$, then the algebraic dual of $X$ has cardinality
$kappa^+$.

Let $T$ be the tree of all countable subsets of $omega_1$ equipped
with the partial order of end-extension. We have GCH, hence, the tree
is just all sequences of real numbers, and so, it has cardinality
$aleph_1$. The cardinality of the corresponding James tree space is
also $aleph_1$.

The completion $c(T)$ of our tree $T$ is the set of all subsets of
$omega_1$. Hence it has cardinality $2^{aleph_1}$ which is,
under GCH, $aleph_2$. It follows that the cardinality of $JT^{**}$
is $aleph_2$.

Now consider cases.

Case 1: the topological dual $JT^* $ of $JT$ has cardinality strictly
bigger than $aleph_1$. Then we are done: our counterexample is $JT$.

Case 2: the topological dual $JT^* $ of $JT$ has cardinality $aleph_1$.
We are also done: our counterexample is $JT^* $.

fields - An unfamiliar (to me) form of Hensel's Lemma

A far more general result is the "non-archimedean inverse function theorem". I haven't looked at Roquette's reference, so maybe he is mentioning it. But it is something which I didn't really find in the standard number theory textbooks - probably you can find it in texts on $p$-adic analysis - and I learned it from my number theory professor last semester (Jean-Benoît Bost). This theorem is powerful - and I find it fascinating and surprising - and all versions of Hensel's lemma which one usually encounters while learning number theory are immediate consequences.

Let $K$ be a field, $left| cdot right|$ a non-archimedean absolute value on $K$ for which $K$ is complete, $mathcal{O}$ the associated valuation ring, $mathcal{M}$ the maximal ideal, $pi$ a uniformizer. Let $Phi_i in mathcal{O}[X_1,,cdots,X_n]$ for $1 leq i leq n$ and consider the map $Phi = (Phi_1,,cdots,Phi_n) : mathcal{O}^n to mathcal{O}^n$. Let $J$ be the Jacobian $det(partial Phi_i / partial X_j) in mathcal{O}[X_1,,cdots,X_n]$.

Theorem. If $x_0 in mathcal{O}^n$, $y_0 = Phi(x_0)$ and $J(x_0) neq 0$, then for any $R in (0, left|J(x_0)right|)$, $Phi$ induces a bijection $$overline{B}(x_0,R) to y_0 + (DPhi)(x_0) overline{B}(0,R)$$ (where $DPhi$ is the derivative we all know!) and furthermore we have a bijection $$B^circ(x_0,left|J(x_0)right| to y_0 + (DPhi)(x_0) B^circ(0,left|J(x_0)right|).$$

(I use the standard notations $overline{B}$ and $B^circ$ for closed and open balls respectively.)

The proof uses in an essential way the Picard fixed point theorem.

Corollary 1. Take $n = 1$, $Phi_1 = P$, $x_0 = alpha$, $varepsilon in (0,1)$. Suppose that $left|P(alpha)right| leq varepsilon left|P'(alpha)right|^2$. Then there exists a unique $beta in mathcal{O}$ such that $P(beta) = 0$ and $left|beta - alpharight| leq varepsilon left|P'(alpha)right|$. (We take $R = varepsilon left|P'(alpha)right|$ in the first bijection.)

Hence, as a special case, if $left|P(alpha)right| < left|P'(alpha)right|^2$, we find $left|beta - alpharight| < left|P'(alpha)right|$.

As an even more special case, if $P'(alpha) in mathcal{O}^times$ and $left|P'(alpha)right| <1$, there exists $beta in mathcal{O}$ such that $P(beta) = 0$ and $left|beta - alpharight| < 1$. Restating this in terms of the residue field: a simple zero in the residue field can be lifted to a real zero in $mathcal{O}$. This is the really known version of Hensel's lemma, I guess.

[Definition: the Gauss norm of a polynomial with coefficients in $K$ is defined as the maximum of the absolute values of its coefficients. It is very easy to check that the Gauss norm is multiplicative.]

Corollary 2. Take $f,g,h in mathcal{O}[X]$ such that $deg g = n$, $deg h = m$ and $deg f = deg g + deg h = n + m$. Assume that there exists $varepsilon in (0,1)$ such that $left|f - ghright| leq varepsilonleft|text{Res}(g,h)right|^2$ and $deg(f - gh) leq m + n - 1$. Then there exist $G, H in mathcal{O}[X]$ such that $f = GH$, $deg(G - g) leq n - 1$, $deg(H - h) leq m - 1$, and also $left|G - gright| leq varepsilon left|text{Res}(g,h)right|$ and $left|H - hright| leq varepsilon left|text{Res}(g,h)right|$. (Obviously $text{Res}$ denotes the resultant here, and $left|cdotright|$ the Gauss norm.)

To prove this: write $G = g + xi$ and $H = h + eta$ where $xi$ and $eta$ are polynomials with coefficients in $mathcal{O}$ and have degrees $leq n - 1$ and $leq m - 1$ respectively. Then $f = GH$ if and only if $f = (g + xi)(h + eta)$. It can be seen as a map from $mathcal{O}^n times mathcal{O}^m to mathcal{O}^{n + m}$ given by polynomials. So consider the map $Phi: (xi, eta) mapsto (g + xi)(h + eta) - f$. We have also $text{Res}(g,h) = det((xi, eta) mapsto g xi + h eta))$. It is easy to see that the theorem above then gives the result.

As a corollary: if $f$, $g$ and $h$ satisfy $overline{f} = overline{g} overline{h}$ - where $overline{f}$ is $f$ reduced modulo $mathcal{M}$ et cetera - and if $overline{g}$ and $overline{h}$ are coprime (this is a condition on the resultant!) then there exist $G,H in O[X]$ satisfying the following conditions: $f = GH$, $deg(G - g) leq n - 1$, $deg(H - h)leq m - 1$, $overline{G} = g$ and $overline{H} = h$. Hence "a factorization over the residue field lifts to a factorization over $mathcal{O}$" (under the right conditions).

Corollary 3. Finally, let us come to the motivation for the question: the more general result is that if $P in K[X]$ is irreducible, then $left|Pright|$ (Gauss) is the maximum of the absolute values of the leading coefficient and the constant coefficient. (As a special case, we find the result which Pete L. Clark cites as the Hensel-Kurschak lemma.)

Indeed, let $P(X) = sum_{i = 0}^n a_i X^{n - i} in K[X]$. Suppose WLOG that $left|Pright| = 1$. Let $mathbb{F}$ be the residue field and let $overline{P}$ be the image of $P$ modulo $mathcal{M}$. Set $r = min {n : overline{a_{n - r}} neq 0}$. Then we have in the residue field the factorization $overline{P}(X) = X^r left(overline{a_{n - r}} + overline{a_{n - r - 1}}X + cdots + overline{a_0} X^{n - r}right)$ and we can lift the factorization by Corollary 2, contradicting irreducibility.

I know this is quite some digression; but I find the whole discussion about the various forms of Hensel's lemma very interesting, and I thought this could add something to the discussion.

graph theory - Bound on the number of unlabeled cographs on n vertices

See e.g. the Wikipedia article on cographs, which explains that isomorphism classes of cographs are in one-to-one correspondence with isomorphism classes of n-leaf rooted trees in which the internal nodes are labeled with 0's and 1's and in which, moreover, the labels are in strict alternation from root to leaf.

Because of the alternation, the labeling part only adds a factor of two to the overall count, so really all you need to do is to count n-leaf rooted trees. So the number of cographs appear to be the numbers in OEIS sequence A000084 (the number of trees is half that, A000669). They are asymptotic to around 3.561^n, matching Zaimi's answer.

gt.geometric topology - Complete knot invariant?

As Ryan says, this follows from Waldhausen's paper, when appropriately interpreted. Sufficiently large 3-manifolds are usually called "Haken" in the literature, and as Ryan says, they are irreducible and contain an incompressible surface (which means that the surface is incompressible and boundary incompressible). An irreducible manifold with non-empty boundary and not a ball (ie no 2-sphere boundary components) is always sufficiently large, by a homology and surgery argument. By Alexander's Lemma, knot complements are irreducible, and therefore sufficiently large (the sphere theorem implies that they
are aspherical).

Waldhausen's theorem implies that if one has two sufficiently large 3-manifolds $M_1, M_2$ with connected boundary components, and an isomorphism $pi_1(M_1) to pi_1(M_2)$ inducing an isomorphism $pi_1(partial M_1) to pi_1(partial M_2)$, then $M_1$ is homeomorphic to $M_2$. This is proven by first showing that there is a homotopy equivalence $M_1simeq M_2$ which restricts to a homotopy equivalence $partial M_1simeq partial M_2$. Then Waldhausen shows that this relative homotopy equivalence is homotopic to a homeomorphism by induction on a hierarchy. The peripheral data is necessary if the manifold has essential annuli, for example the square and granny knots have homotopy equivalent complements.

If $K_1, K_2subset S^3$ are (tame) knots, and $M_1=S^3-mathcal{N}(K_1), M_2=S^3-mathcal{N}(K_2)$ are two knot complements, then Waldhausen's theorem applies. However, one must also cite the knot complement problem solved by Gordon and Luecke, in order to conclude that $K_1$ and $K_2$ are isotopic knots. Otherwise, one must also hypothesize that the isomorphism $partial M_1 to partial M_2$ takes the meridian to the meridian (the longitudes are determined homologically). This extra data is necessary to solve the isotopy problem for knots in a general 3-manifold $M$, to guarantee that the homeomorphism $(M_1,partial M_1)to (M_2,partial M_2)$ extends to a homeomorphism $(M,K_1)to (M,K_2)$, since for example there are knots in lens spaces which have homeomorphic complements by a result of Bleiler-Hodgson-Weeks.

ca.analysis and odes - Sum and interpolation of hurwitz zeta functions

Well, if $p$ is an integer, you should realize that $frac{1}{(tau+a)^{p+1}}$ can be obtained by integrating $Q(x)e^{-2pi iax}$ against $e^{-2pi itau x}$ where $Q(x)$ is the (unique) polynomial of degree $p$ satisfying $Q^{(m)}(0)=e^{-2pi ia}Q^{(m)}(1)$ for $m<p$ and $Q^{(p)}=frac{(2pi i)^{p+1}}{e^{-2pi ia}-1}$.

So, your function is just $Q(x)e^{-2pi iax}$ on $(0,1)$ extended by periodicity to the entire line. The polynomial $Q$ can be easily found for each particular $p$, so if you need some small range of $p$, you have an exact closed form formula. If you want to consider large $p$, then it is not so useful but the origianal series gives you a high precision approximation if you keep just the first few terms. Either way, you have an "expression one can work with", don't you?

The thing that totally puzzles me is why you think that your series has any relation to the Hurwitz zeta function.

sg.symplectic geometry - To what extent can I think of a Lagrangian fibration in a symplectic manifold as T*N?

Dear Theo Johnson-Freyd, I hope to have at least partially understood the content of your question, and that my answer could be useful.

0.Setting and specification of the terminology.
In a symplectic $2n$-dimensional manifold $(M,omega)$, let be given a lagrangian foliation $mathcal{F}$, i.e. a foliation of $M$ whose leaves are lagrangian w.r.t. $omega$.
(Instead, I mean a lagrangian fibration of $(M,omega)$ as a surjective summersion $f:Mto B$ whose fibers are lagrangian w.r.t. $omega$. Any fibration determines a foliation but the converse is not true. The difference will be immaterial in my point(1), but not so in my point(2).)

1.Local Existence of lagrangian submanifolds transversal to $mathcal{F}$.
For any $pin M$, there exists a lagrangian submanifold of $(M,omega)$ which passes through $p$ and is transversal to $mathcal{F}$.

Infact, for any $pin M$, there exists a chart $(U,phi)$ for $M$ centered at $p$, such that:
$omega= sum_{i=1}^{n}{dphi_i wedge dphi_{n+i}}$,
the restriction of $mathcal{F}$ on $U$ is generated by $frac{partial}{partialphi_{n+1}},ldots,frac{partial}{partialphi_{2n}}$,
and consequently $phi_{n+1}=ldots=phi_{2n}=0$ is a local lagrangian submanifold of $(M,omega)$ passing through $p$ and transverval to $mathcal{F}$.

This is just the Caratheodory-Jacobi-Lie theorem, applied starting with a system $dphi_1,ldots,dphi_n$ of $1$-forms which locally generates the distribution corresponding to the lagrangian foliation $mathcal{F}$.

2. A relative globalization.
If $L$, a lagrangian submanifold of $(M,omega)$, is transversal to $mathcal{F}$, then there exists a diffeomorphism $f$ from an open neigborhood of $L$ in $M$ onto an open set in $T^*L$ such that:
$f|_L$ is the zero section of $tau_L^{ast}:T^{ast}Lto L$,
$f_{ast}omega$ is the canonical symplectic on $T^{ast}L$,
and $f$ takes the leaves of $mathcal{F}$ in the fibers of $tau^{ast}_L$.

This is just Theorem 7.1 in "Symplectic Manifolds and their Lagrangian submanifolds" of A.Weinstein.

ag.algebraic geometry - coarse moduli space of DM stacks

No, not every DM-stack has a coarse moduli space. The following is a counter-example (see my paper on geometric quotients):

Let X be two copies of the affine plane glued outside the y-axis (a non-separated scheme). Let G=Z₂ act on X by y → –y and by switching the two copies. Then G acts non-freely on the locally closed subset {y=0, x ≠ 0}. The quotient [X/G] is a DM-stack with non-finite inertia and it can be shown that there is no coarse moduli space (neither categorical nor topological) in the category of algebraic spaces.

at.algebraic topology - HNN extensions which are free products

This might help.

Lemma If $A$ does not split freely and $C$ is a non-trivial subgroup of $A$ then the HNN extension $G=A*_C$ does not split freely.

The proof uses Bass--Serre theory---see Serre's book Trees from 1980.

Proof. Let $T$ be the Bass--Serre tree of a free splitting of $G$. Because $A$ does not split freely, $A$ stabilizes some unique vertex $v$. But $C$ is non-trivial, so $C$ also stabilizes a unique vertex, which must be $v$. Therefore, $G$ stabilizes $v$, which means the free splitting was trivial. QED

A similar argument shows the following.

Lemma If $ A*_C $ splits non-trivially as an amalgamated free product $ A' *_{C'} B'$ then either $A$ splits over $C'$ or $C$ is conjugate into $C'$.

pr.probability - Name for probabilistic version of Pascal's identity and differentiation formula for binomial distribution

I'm trying to find a standard name or standard reference for two simple-to-prove relations involving binomial distributions.

Define:

$b(n,r,p) := binom{n}{r}p^r(1 - p)^{n-r}$

i.e., it is the probability that, out of n coin tosses, exactly r turn up heads if the probability of a heads in each coin toss is p.

Then, the first identity is:

$b(n,r,p) = pb(n-1,r-1,p) + (1 - p)b(n-1,r,p)$

This can be proved directly using probabilistic arguments, or through algebraic simplication combined with the use of Pascal's identity. I thought it should be called the "probabilistic Pascal's identity", but Google doesn't agree with me.

The second identity for which I'm looking for a name is:

$frac{partial}{partial p} b(n,r,p) = n(b(n-1,r-1,p) - b(n-1,r,p))$

This is easy to prove algebraically, using another recurrence relation for the binomial coefficients along the way; it probably also has a probabilistic proof.

These identities came up in the proofs of some theorems in an economics paper (models of utility functions of discrete variables) and the person writing the paper asked me if there are standard names/references for the identities, so that they can be referred to using those names without having to do the algebra in the paper.

Also, if anybody knows a place where one can enter an identity and determine whether it has a standard name or reference, that would be great.

What are fixed points of the Fourier Transform

$bf{1.}$ A more complete list of particular self-reciprocal Fourier functions of the first kind, i.e. eigenfunctions of the cosine Fourier transform $sqrt{frac{2}{pi}}int_0^infty f(x)cos ax dx=f(a)$:

$1.$ $displaystyle e^{-x^2/2}$ (more generally $e^{-x^2/2}H_{2n}(x)$, $H_n$ is Hermite polynomial)

$2.$ $displaystyle frac{1}{sqrt{x}}$ $qquad$ $3.$ $displaystylefrac{1}{coshsqrt{frac{pi}{2}}x}$ $qquad$ $4.$ $displaystyle frac{cosh frac{sqrt{pi}x}{2}}{cosh sqrt{pi}x}$ $qquad$$5.$ $displaystylefrac{1}{1+2cosh left(sqrt{frac{2pi}{3}}xright)}$

$6.$ $displaystyle frac{coshfrac{sqrt{3pi}x}{2}}{2cosh left( 2sqrt{frac{pi}{3}} xright)-1}$ $qquad$ $7.$ $displaystyle frac{coshleft(sqrt{frac{3pi}{2}}xright)}{cosh (sqrt{2pi}x)-cos(sqrt{3}pi)}$ $qquad$ $8.$ $displaystyle cosleft(frac{x^2}{2}-frac{pi}{8}right) $

$9.$ $displaystylefrac{cos frac{x^2}{2}+sin frac{x^2}{2}}{coshsqrt{frac{pi}{2}}x}$ $qquad$ $10.$ $displaystyle sqrt{x}J_{-frac{1}{4}}left(frac{x^2}{2}right)$ $qquad$ $11.$ $displaystyle frac{sqrt[4]{a} K_{frac{1}{4}}left(asqrt{x^2+a^2}right)}{(x^2+a^2)^{frac{1}{8}}}$

$12.$ $displaystyle frac{x e^{-betasqrt{x^2+beta^2}}}{sqrt{x^2+beta^2}sqrt{sqrt{x^2+beta^2}-beta}}$$qquad$ $13.$ $displaystyle psileft(1+frac{x}{sqrt{2pi}}right)-lnfrac{x}{sqrt{2pi}}$, $ psi$ is digamma function.

Examples $1-5,8-10$ are from the chapter about self-reciprocal functions in Titschmarsh's book "Introduction to the theory of Fourier transform". Examples $11$ and $12$ can be found in Gradsteyn and Ryzhik. Examples $6$ and $7$ are from this question What are all functions of the form $frac{cosh(alpha x)}{cosh x+c}$ self-reciprocal under Fourier transform?. Some other self-reciprocal functions composed of hyperbolic functions are given in Bryden Cais's paper On the transformation of infinite series. Discussion of $13$ can be found in Berndt's article.

$bf{2.}$ Self-reciprocal Fourier functions of the second kind, i.e. eigenfunctions of the sine Fourier transform $sqrt{frac{2}{pi}}int_0^infty f(x)sin ax dx=f(a)$:

$1.$ $displaystyle frac{1}{sqrt{x}}$ $qquad$ $2.$ $displaystyle xe^{-x^2/2}$ (and more generally $e^{-x^2/2}H_{2n+1}(x)$)

$3.$ $displaystyle frac{1}{e^{sqrt{2pi}x}-1}-frac{1}{sqrt{2pi}x}$ $qquad$ $4.$ $displaystyle frac{sinh frac{sqrt{pi}x}{2}}{cosh sqrt{pi}x}$ $qquad$ $5.$ $displaystyle frac{sinhsqrt{frac{pi}{6}}x}{2cosh left(sqrt{frac{2pi}{3}}xright)-1}$

$6.$ $displaystyle frac{sinh(sqrt{pi}x)}{cosh sqrt{2pi} x-cos(sqrt{2}pi)}$ $qquad$ $7.$ $displaystyle frac{sin frac{x^2}{2}}{sinhsqrt{frac{pi}{2}}x}$ $qquad$ $8.$ $displaystyle frac{xK_{frac{3}{4}}left(asqrt{x^2+a^2}right)}{(x^2+a^2)^{frac{3}{8}}}$

$9.$ $displaystyle frac{x e^{-betasqrt{x^2+beta^2}}}{sqrt{x^2+beta^2}sqrt{sqrt{x^2+beta^2}+beta}}$$qquad$ $10.$ $displaystyle sqrt{x}J_{frac{1}{4}}left(frac{x^2}{2}right)$$qquad$ $11.$ $displaystyle e^{-frac{x^2}{4}}I_{0}left(frac{x^2}{4}right)$

$12.$ $displaystyle sinleft(frac{3pi}{8}+frac{x^2}{4}right)J_{0}left(frac{x^2}{4}right) $$qquad$ $13.$ $displaystyle frac{sinh sqrt{frac{2pi}{3}}x}{cosh sqrt{frac{3pi}{2}}x}$

Examples $1-5,7$ can be found in Titschmarsh's book cited above. $8-12$ can be found in Gradsteyn and Ryzhik. $13$ is from Bryden Cais, On the transformation of infinite series, where more functions of this kind are given.

reference request - Collecting various theories on toy examples: Projective space

I am looking for text books/notes/papers/documents playing with toy examples: projective space, in particular, $P^{1}$. Because I think this is really a cute example. Although algebraic geometry on $P^{1}$ is comparatively simple, it gave inspirations to treat more general situtation. Precisely, I am looking for something including following topics:(but you can add whatever you want)

1. algebraic geometry of $P^{n}$, say, $Coh(P^{n})$, $D^{b}(Coh(P^{n}))$, say, exceptional collection,semi-orthogonal decomposition,stability conditions




2. Relation to representation theory, say, Hall algebra of $Coh(P^{n})$ and $D^{b}(Coh(P^{n}))$ and its relation to affine quantum group: $U_{q}(hat{sl_{n+1}})$, representation theory of Kronecker quiver. Tilting theory. Weighted projective line and so on.




3. $D-module$ on flag variety of $U(sl_{2})$(or $P^{1}$) and so on..................




4. Add whatever you like.




5. Add whatever you like.

..................................................

linear algebra - How to compute the rank of a matrix?

Okay, that's a misleading title. This is a somewhat subtler problem than undergraduate linear algebra, although I suspect there's still an easy answer. But I couldn't resist :D.

Here's the actual problem: We're given a black-box linear transformation from $V rightarrow W$, where $V, W$ are vector spaces of dimensions m, n respectively (say m < n), and we want to know if it has full rank. (Numerical considerations aren't an issue; if you want, say it's over a finite field.) This is easy to do in time $O(m^2n)$ and with m calls to the black-box function, just by computing the image of a basis in m and using Gaussian elimination. It's also immediately obvious that we can't do better than m calls to the function in a deterministic algorithm, and I'm pretty sure but haven't quite managed to prove that you can't beat Gaussian elimination asymptotically either.

But can we do better if we just want a probabilistic algorithm? If we're allowed to make as many function calls as we want? What's the best lower bound we can get, probabilistically? These are probably pretty trivial questions (since everything's linear-algebraic and nice), but I just don't know how to approach them.