nt.number theory - Unique representation of constructible numbers

I am interested in programmatically working with constructible numbers (the closure of the rational numbers under square roots). In order to perform comparisons between numbers I believe I would need a unique (symbolic) representation for them. Does such a thing exist, or what are relevant references for this kind of thing?

co.combinatorics - Monotonic maximal chains in a Coxeter group

Let $(W, S)$ be a Coxeter system, and let $T = bigcup_{w in W, s in S} wsw^{-1}$. Associated to every element $t in T$ is a unique positive root $alpha_t in Phi^{+}$ considered as a vector in the standard geometric representation $V$ of $W$. A total order on $T$ is a reflection order if, whenever $alpha_{t_1} < alpha_{t_2}$, it follows that $alpha_{t_1} < x alpha_{t_1} + y alpha_{t_2} < alpha_{t_2}$ whenever the middle term is a positive root with $x > 0, y > 0$. (See, for example, Bjorner and Brenti's book.)

Fix a reflection order and let $[u, v]$ be a Bruhat interval. A maximal chain $u = w_0 to w_1 to ... to w_m = v$ in the Bruhat order is what I'll call monotonic if $w_i w_{i-1}^{-1} > w_{i+1} w_i^{-1}$ in the reflection order.

There is a nonrecursive formula for the Kazhdan-Lusztig polynomials $P_{u,v}(q)$ which implies that $P_{u,v}(0)$ is equal to the number of monotonic maximal chains in $[u, v]$. This number is known by other means to be equal to $1$, so I know that there is a unique monotonic maximal chain; however, I can't prove this directly. So far all I've been able to do is use the greedy algorithm to prove that at least one monotonic maximal chain exists.

Does anyone have a direct proof of this fact?

Edit: No progress, but now I have a more general conjecture which I no longer know by other means is true. Fix a sequence $a_1, ... a_m$ of odd positive integers such that $sum_i a_i = ell(v) - ell(u)$. Then there exists at most one monotonic chain (not necessarily maximal) such that $w_i w_{i-1}^{-1} in T$ and such that $ell(w_{i-1}) - ell(w_i) = a_i$.

integer programming - linear program with zeros

Hi, I want to be able to solve a linear program that has constraints that are either zero or a range. An example below in LP_Solve-like syntax shows what I want to do. This doesnt work. In general all the decision variables Qx can be 0 or a <= Qx <= b where a > 0 and b > a. All decision variables must be integers.


max: 0.2 Q1 + 0.4 Q2 + 0.6 Q3 + 0.8 Q4 + 0.4 Q5 + 0.6 Q6 + 0.6 Q7 + 0.7 Q8;


Q1 = 0 or Q1 >= 5;
Q2 = 0 or Q2 >= 1;
Q3 = 0 or Q3 >= 1;
Q4 = 0 or Q4 >= 1;
Q5 = 0 or Q5 >= 1;
Q6 = 0 or Q6 >= 1;
Q7 = 0 or Q7 >= 9;
Q8 = 0 or Q8 >= 1;
Q4 <= 30;
Q1 + Q2 + Q3 + Q4 + Q5 + Q6 + Q7 + Q8 <= 50;

How would I rewrite this to work? Is there a particular solver that should be used for this kind of task?

rt.representation theory - If associated-graded of a filtered bialgebra is Hopf, does it follow that the original bialgebra was Hopf?

Warning: older texts use the word "Hopf algebra" for what's now commonly called "bialgebra", whereas now "Hopf" is an extra condition. So as to avoid any confusion, I'll give my definitions before concluding with my question.

Definitions

Let $C$ be a category with symmetric monoidal structure $otimes$ and unit $1$ (and either strictify, or decorate all the following equations with associators and unitators and so on). An (associative, unital) algebra in $(C,otimes)$ is an object $V$ along with maps $e: 1to V$ and $m: Votimes V to V$ satisfying associativity and unit axioms: $mcirc(motimes text{id}) = mcirc (text{id}otimes m)$ and $mcirc (text{id}otimes e) = text{id} = mcirc (eotimes text{id})$. A (coassociative, counital) coalgebra is an object $V$ along with maps $epsilon: Vto 1$ and $Delta: V to Votimes V$ satisfying coassociativity and counit axioms. A bialgebra is any of the following equivalent things:

• A coalgebra in the category of algebras and algebra-homomorphisms ($1$ has its canonical algebra structure coming from the $otimes$ axioms that $1otimes 1 = 1$; in the tensor product of algebras, elements in the different multiplicands commute)


• An algebra in the category of coalgebras and coalgebra-homomorphisms


• An object $V$ with maps $e,m,epsilon,Delta$ satisfying the axioms above and a compatibility axiom:
  $$ Delta circ m = (motimes m) circ (text{id} otimes text{flip} otimes text{id}) circ (Delta otimes Delta) $$

A bialgebra can have the property of being Hopf (it is a property, not extra data): a bialgebra $V$ is Hopf if there exists an antipode map $s: Vto V$ satisfying
$$ m circ (sotimes text{id}) circ Delta = ecirc epsilon = m circ (text{id} otimes s) circ Delta $$
Naturally, it's better to see these definitions than read them; check e.g. the Wikipedia article. If an antipode exists for a bialgebra, it is unique (justifying considering Hopfness a property rather than a structure) and it is an antihomomorphism for both the algebra and coalgebra structures.

Let VECT be the category of vector spaces (over your favorite field), with $otimes$ the usual tensor product and $1$ the ground field. A ($mathbb N$-)filtered vector space is a sequence $V = {V_0 hookrightarrow V_1 hookrightarrow V_2 hookrightarrow dots}$ in VECT. A morphism of filtered vector spaces $V to W$ is a sequence of morphisms $V_n to W_n$ so that every square commutes: ${V_n hookrightarrow V_{n+1} to W_{n+1}} = {V_n to W_n hookrightarrow W_{n+1}}$. Equivalently, a filtered vector space is a space $V in $VECT along with an increasing sequence of subspaces $V_0 subseteq V_1 subseteq dots subseteq V$ such that $V = bigcup V_n$, and a linear map of filtered vector spaces $V to W$ is filtered if the image of $V_n$ lies in $W_n$ for each $n$.

Because $otimes$ is exact in VECT (because every monomorphism splits), to a pair $V,W$ of filtered vector spaces we can define an $mathbb N^2$-filtered space with $(p,q)$-part $V_potimes W_q$, and then we can define the $mathbb N$-filtered space $Votimes W$ by setting $(Votimes W)_n$ to be the colimit of the diagram given by all $V_potimes W_q$ with $p+q leq n$. Equivalently, we can take the tensor product in VECT of the unions $V = bigcup V_n$ and $W = bigcup W_n$, and then filter it by declaring that the $n$th part is the union of the $(potimes q)$th parts for $p+q = n$.

A ($mathbb N$-)graded vector space is a sequence ${V_0,V_1,V_2,dots}$ in VECT, or equivalently a space $V$ along with a direct sum decomposition $V = bigoplus V_n$. A morphism of graded vector spaces preserves the grading.

Let $V$ be a filtered vector space. Its associated graded space $text{gr}V$ is given by $(text{gr}V)_n = V_n / V_{n-1}$, where $V_{-1} = 0$, of course. Then $text{gr}$ is a symmetric monoidal functor, and so takes filtered bialgebras to graded bialgebras.

Question

Let $V$ be a filtered bialgebra, i.e. a bialgebra in the category of filtered vector spaces. Then $text{gr}V$ is a graded bialgebra. Suppose that $text{gr}V$ is Hopf. Does it follow that $V$ is Hopf? I.e. suppose that $text{gr}V$ has an antipode map. Must $V$ have an antipode map?

(Or perhaps it requires additional hypotheses, e.g. that we be in characteristic 0, or that $V$ is locally finite in the sense that each $V_n$ is finite-dimensional?)

dg.differential geometry - Do free higher homotopy classes of compact Riemannian manifolds have preferred representatives?

A well known theorem of Cartan states that every free homotopy class of closed paths in a compact Riemannian manifold is represented by a closed geodesic (theorem 2.2 of Do Carmo, chapter 12, for example). This means that every closed path is homotopic to a closed geodesic (through a homotopy that need not fix base points).

I am wondering if there is a higher dimensional generalization of this result. Let us define a free n-homotopy class of $M$ to be a set $L_n$ of continuous maps $S^n to M$ such that if $f in L_n$ and $g: S^n to M$ is any continuous map which is homotopic to $f$ (no base points required) then $g in L_n$.

Question 1: Can one use the geometry of $M$ to intelligently single out a preferred class in any free n-homotopy class?

The naive guess is that every free n-homotopy class has an area minimizing representative, but my intuition tells me that this is either not true or really hard to prove. This is because the proof in the 1-dimensional case develops the argument from certain continuity properties of arclength that tend to either fail or require tremendous care when generalized to area. But perhaps this idea abstracts the wrong property of geodesics; maybe one should instead look for representatives which extremize some intelligently chosen functional instead. I'm hoping someone has already thought about this and come up with a good answer.

Question 2: Can anything more be said in the presence of negative curvature?

In the 1-dimensional case, I believe that the closed geodesic guaranteed by Cartan is in fact unique if $M$ is compact with strictly negative curvature. If there is an affirmative answer to question 1, I would be curious to know if there is a corresponding uniqueness statement in negative curvature. And if question 1 doesn't seem to have a nice answer in general, maybe negative curvature helps.

Thanks in advance!

soft question - Indexed tensor manipulation CAS

hello.

I am looking for tensor manipulation software that would allow me:

• declare indices


• declare results of contraction (or simplification rules)


• allow algebraic simplifications and expansion


• index renaming

So far I have found Maxima to satisfy my requirement more or less, http://maxima.sourceforge.net/docs/manual/en/maxima_27.html

one last thing I also want, (but not necessarily require), is interface with python.
In principle I could use sage to interface with maxima.

Is there some other Cas that has package with similar tensor
manipulation properties?

from links given below, I also found this, http://cadabra.phi-sci.com/, which looks geared specifically for tensor manipulations.

fa.functional analysis - Do all graphs of C1 functions have Hausdorff dimension 1?

Let $f colon I to mathbb{R}$. Since $f$ is $C^1$, the graph $Gamma_f$ is locally bilipschitz to $I$, via the projection. It follows that Hausdorff dimension is the same as that of $I$ (being defined in terms of the metric space structure only), so it is $1$.

Disclaimer: I haven't seen these topics for quite a while, so I may have said something stupid.

nt.number theory - Why is the largest signed 32 bit integer prime?

This may be subjective, but does anyone have any insight into why this is the case? This struck me while considering that it's also the eigth Mersenne prime (2^31-1=2147483647).

I'm now wondering why this might be the case.

UPDATE:
It's been pointed out that the relationship doesn't necessarily hold for larger storage classes, e.g., 2^63 - 1 is not prime.

abstract algebra - Canonical examples of algebraic structures

I often think of "universal examples". This is useful because then you can actually prove something in the general case - at least theoretically - just by looking at these examples.

Semigroup: $mathbb{N}$ with $+$ or $*$

Group: Automorphism groups of sets ($Sym(n)$) or of polyhedra (e.g. $D(n)$).

Virtual cyclic group: Semidirect products $mathbb{Z} rtimes mathbb{Z}/n$.

Abelian group: $mathbb{Z}^n$

Non-finitely generated group: $mathbb{Q}$

Divisible group: $mathbb{Q}/mathbb{Z}$

Ring: $mathbb{Z}[x_1,...,x_n]$

Graded ring: Singular cohomology of a space.

Ring without unit: $2mathbb{Z}$, $C_0(mathbb{N})$

Non-commutative ring: Endomorphisms of abelian groups, such as $M_n(mathbb{Z})$.

Non-noetherian ring: $mathbb{Z}[x_1,x_2,...]$.

Ring with zero divisors: $mathbb{Z}[x]/x^2$

Principal ideal domain which is not euclidean: $mathbb{Z}[(1+sqrt{-19})/2]$

Finite ring: $mathbb{F}_2^n$.

Local ring: Fields, and the $p$-adics $mathbb{Z}_p$

Non-smooth $k$-algebra: $k[x,y]/(x^2-y^3)$

Field: $mathbb{Q}, mathbb{F}_p$

Field extension: $mathbb{Q}(i) / mathbb{Q}, k(t)/k$

Module: sections of a vector bundle. Free <=> trivial. Point <=> vector space.

Flat / non-flat module: $mathbb{Q}$ and $mathbb{Z}/2$ over $mathbb{Z}$

Locally free, but not free module: $(2,1+sqrt{-5})$ over $mathbb{Z}[sqrt{-5}]$

... perhaps I should stop here, this is an infinite list.

big list - What are the worst notations, in your opinion ?

A cute idea but for which I have yet to find supporters is D. G. Northcott's notation (used at least in [Northcott, D. G. A first course of homological algebra. Cambridge University Press, London, 1973. xi+206 pp. MR0323867) for maps in a commutative diagram, which consists in enumerating the names of the objects placed vertices along the way of the composition. Thus, if there only one map in sight from $M$ to $N$, he writes it simply $MN$, so we has formulas looking like $$A'A(ABB'') = A'ABB'' = A'B'BB'' = 0.$$ He also writes maps on the right, so his $$xMN=0$$ means that the image of $x$ under the map from $M$ to $N$ is zero.

I would not say this is among the worst notations ever, though.

lo.logic - A Decision Problem Concerning Diophantine Inequalities

It is undecidable. If you could solve this, you could also solve Hilbert's 10th problem.

Suppose we have an algorithm solving your problem for all $n$. Given a polynomial $pinmathbb[x_1,dots,x_n]$, let's decide whether it has integer solutions. If $p$ is constant, this is trivial. Otherwise we can find $z_0inmathbb Z^n$ such that $|p(x)|>1$ for all $xin z_0+[0,1]^n$. Let's work with a polynomial $f(x)=p(x+z_0)$ rather than $p$. It satisfies $|f(x)|>1$ for all $xin[0,1]^n$.

Let $g(x)=x_1(x_1-1)x_2(x_2-1)dots x_n(x_n-1)$. Apply our algorithm to the inequality
$$
r(x):=(f(x)^2-1)cdot g(x)<0 .
$$
If it says that $S+mathbb Z^n=mathbb R^n$, then we know that $S$ contains a point from $mathbb Z^n$, and this point must a root of $f$. If it says that $S+mathbb Z^nnemathbb R^n$, then we know that there is $cinmathbb R^n$ such that $r(c+z)ge 0$ for all $zinmathbb Z^n$.

This $c$ must belong to $mathbb Z^n$. Indeed, suppose that e.g. $c_1notinmathbb Z$. We may assume that all coordinates of $c$ are positive and $0<c_1<1$. Substitute $z=(0,z_2,dots,z_n)$ where $z_2,dots,z_n$ are arbitrary positive integers and conclude that $|f(c+z)|le1$ for all such $z$. It follows that $f$ is constant on the hyperplane ${x_1=c_1}$, and the modulus of this constant no greater than 1. This contradicts
the fact that $|f|>1$ on $[0,1]^n$.

Thus we know that $cinmathbb Z^n$, or, equivalently, that $r(z)ge 0$ for all $zinmathbb Z^n$. This means that $f$ does not have integer roots except possibly at points where one of the coordinates is 0 or 1. Thus we reduced the problem to the case of $n-1$ variables and can solve it by induction.

gr.group theory - Hausdorff dimension of products of normal subgroups

In the first conference I ever went to Slava Grigorchuk asked me a similar question and I didn’t have an answer. But when I have got back to Jerusalem I have talked with Elon Lindenstrauss about it and he suggested the following easy counterexample. Take $G=mathbb{F}_p[[t]]$. Pick $S$ to be a subset of the integers with density one and with infinite complement $T$. Say $S=left{ n_i right}$ and $T=left{ m_i right}$. Take $A=overline{< t^{n_i}>}$ and take $B=overline{left< t^{n_i} +t^{m_i} right>}$. Cleary, $AB=G$, $h(A)=h(B)=1$, but $A cap B=emptyset$.

Now, $G$ is not finitely generated, if you would like to have a counterexample which is finitely generated, then you can take $G=SL_d(F_p[[t]])$ and construct in a similar way to the above $A$ which is made from upper triangular matrices and $B$ which is made from lower triangular matrices. However, $A$ and $B$ will not be normal any more.

I am not familiar with a counterexample in which $A$ and $B$ are normal and $G$ is finitely generated. I am also not familiar with a counterexample in which $A$ and $B$ are finitely generated. But as you can deduce from my story above this does not mean much.

na.numerical analysis - Adaptive controllers for stiff ODE and DAE integrators

I'm looking for adaptive controllers (adaptive in both step size and order) for stiff integrators. I have asymptotically correct error estimates for the current method and all candidate methods of order 1 higher and lower than the current method. My naive controllers have occasional problems with either oscillating between different methods despite smooth long-term behavior, or getting stuck (e.g. with a high order method and unreasonably short time steps).

For the curious, these are IRKS general linear methods, see Butcher, Jackiewicz, and Wright 2007.

gn.general topology - SU(2) representations of alternating knot groups

This looks like a good place to start from (if you haven't already read it)

MR2488756 (2009m:57024) Nagasato, Fumikazu . Finiteness of a section of the ${rm SL}(2,Bbb C)$-character variety
of the knot group.
Kobe J. Math. 24 (2007), no. 2, 125--136.

This paper shows that for any knot, there are only finitely many irreducible metabelian characters in the ${rm SL}(2,{bf C})$ character variety. It is also shown that the number of conjugacy classes is given by a simple formula involving the Alexander polynomial. In the context of two bridge knots, there are inequalities involving the $A$-polynomial of the knot. Results of this nature were previously obtained by X. S. Lin [Acta Math. Sin. (Engl. Ser.) 17 (2001), no. 3, 361--380; MR1852950 (2003f:57018)] for ${rm SU}(2)$ representations.

This paper can be found at www.math.titech.ac.jp/~fukky/metabelian.pdf

nt.number theory - k-pseudorandom measures

In reading the paper of Green and Tao on arithmetic progressions within the primes, I became very interested in the notion of a k-pseudorandom measure discussed in that paper.

A measure here is a function $nu:mathbf{Z}_Ntomathbf{R}$ such that $mathbf{E}nu=1+o(1)$, and it is k-pseudorandom if it obeys the ($k2^{k-1}$,$3k-1$,$k$) (I think) linear forms condition, which basically asserts that it behaves independently with respect to at most $k2^{k-1}$ independent linear forms in $3k-1$ variables, and if it also obeys the correlation condition, which is a weaker form controlling the linear forms $x+h_i$.

They show that a relative Szemeredi's theorem applies to functions bounded by a k-pseudorandom measure, and then construct one that (effectively) bounds the primes.

My question is where else these type of functions have been studied, whether their theory has been expanded, and whether other explicit examples have been found and applied in other situations.

polynomials - Tschirnhaus Transformation

Recently in my Intro to Proofs class, we've been talking about the fundamental theorem of algebra, which states that all polynomials of degree n always have n, not necessarily distinct, not necessarily real, solutions. Every high school student is taught the formula $x = frac{-bpmsqrt{b^2-4ac}}{2a}$ for solving quadratic equations, and there exist solutions to the general cubic (Cardano's formula) and general quartic (Ferrari's solution). But what about higher functions?
The Abel-Ruffini theorem states that general functions of degree 5 or higher cannot be solved using a finite number of additions, subtractions, multiplications, divisions, and root extractions. Now, that isn't to say that no function of 5 or higher can be solved -- quite the contrary, actually: x⁵ = 1 has solutions $x = sqrt[5]{1}in{1,-frac{1pm_1sqrt{5}}{4}pm_2 isqrt{frac{5pm_1sqrt{5}}{8}}}$ where ±₁ and ±₂ are independent of the other but related to itself (thus both ±₁ are the same sign always), producing five solutions, four of which are complex.
But there also exist equations with no exact solutions, such as x⁵ - x - 1 = 0. Sure, it has a real solution at x≈1.1673, but that's only an approximation, good to 4 decimal places. However, this is not really what my question is about.

While they cannot be solved generally, quintic functions can be reduced significantly. Take, for example, the function x⁵ + a₄x⁴ + a₃x³ a₂x² + a₁x + a₀ = 0. Making the substitution x = v - a₄/4 produces the new equation v⁵ + b₃v³ + b₂v² + b₁v + b₀ = 0, where the b coefficients are in terms of the a coefficients. Realize that this is just a linear shift to the side of the previous equation, but it becomes simpler to manage, as it's missing the 4^th power term.
Tschirnhaus took it a step further, though. He used a method, which is now called the Tschirnhaus Transformation (the subject of my question) to solve the general cubic in a manner separate to Cardano's solution, and proposed that it could be used to solve any polynomial (and was mistaken). My question lies in what exactly it was that he did. Here is a paper which explains his transformation. I've followed it up to (7), and I understand that we're then solving for alpha in order to reduce the equation to a simple y³ + g, but then I am completely lost as to where the resulting equation came from. (7) is $res_{x}(P_{3},T) = y^3 + (palpha^{2}-frac{1}{3}p^2 +3alpha q)y + frac{2}{3}alpha^{2}p^{2}-alpha^{3}q+q^{2}+alpha pq+frac{2}{27}p^3$, and the result is $y^{3} = 9q^{3}alpha /p^{2}+frac{4}{3}alpha pq-frac{8}{27}p^{3}-2q^{2}$
.
Additionally, I followed the separate method for reducing (but not solving) the quintic through to (12), but I don't understand how (13) and (14) are derived.
If anybody here would be kind enough to explain where they came from, then thank you very much. I realize that there may be typos here, but I can't for the life of me understand what's going on anymore.

Thank you in advance.

Gabriel Benamy

PS. If any syntax is off, it's because the preview, auto preview, and tag look-ahead prompt are all down and I had to write everything on Wikipedia (which has somewhat different syntax, anyway).
PPS. Apparently, my notify email address is invalid, but I didn't have the option of changing it, so I had to uncheck "notify me" in order to post. Am I doing something wrong?

EDIT: Because apparently, I am unable to comment (as Mathoverflow functionality has completely died for me), I have to add this as an edit. Qiaochu Yuan said that I've misquoted both theorems. From my understanding, having "n complex roots" is the same as n, not necessarily real, roots. After all, 1 + i is "not necessarily real" but is a root of x³ - 3x² + 4x - 2 = 0. 1 is also a real root of this (and is also complex, because all real values are complex).
Additionally, he says that the Abel-Ruffini theorem says that "polynomials of degree 5 or higher cannot be solved using the arithmetic operations and root extractions." This is not true, as demonstrated with x^5 - 1 = 0, which is a polynomial of degree 5 and clearly can be solved. The AR theorem states that not all can be solved in such a way, not that none can be solved in such a way.

ct.category theory - Between abstract and concrete: What's the right way to think of specific categories?

Regarding the vivid discussion in the comments after the question (and hopefully, also of some interest for the question itself): I think that a "metacategory" is a definition by axioms, using only first order language, while "interpretation" means: an interpretation as in logic (say, as in p. 29 of Ebbinghaus-Flum-Thomas).

So such an interpretation (a category) is a set, or for convenience, several sets: A set of "objects," a set of "arrows" two function (that is, two more sets) "dom, cod" from the set of arrows to the set of objects, a function "1" from the objects to the arrows, a function "$circ$" on the pairs of composable arrows, etc., that satisfy the first order axioms of a metacategory.

In summary, I agree with the comment of Qiaochu Yuan: set theory is involved, but not because the objects should somehow be "sets with structure."

puzzle - Generalization of Finch Cheney's 5 Card Trick

Kleber's paper will certainly point you in the right direction if you can find it. (I have a printed out copy, and I don't remember where on the web I got it. Sorry.)

In it, he suggests thinking about a strategy as a pairing up of the $(n!+n-1)_{n-1}$ messages with the ${{n!+n-1}choose n} = (n!+n-1)_{n-1}$ hands the audience can give you. Of course, you can only pair a message with one of the n! hands that contain its cards, and you can only pair a hand with one of the n! messages you can make with it. So this is just like finding a perfect matching on an n!-regular bipartite graph, and by Hall's Marriage Theorem this is possible.

The bipartite graph you draw here is quite symmetric: aside from being n!-regular, it's also vertex transitive, so any of the n! edges you could choose from a particular vertex v are part of some perfect matching (since one of them is). This is where Kleber's claim that there are "at least n!" strategies come from.

We can get a much better lower bound if this paper is to be believed. Here it says there are at least $left(frac{(n!-1)^{n!-1}}{n!^{n!-2}}right)^{{n!+n-1}choose n}$ strategies, which for n=2 isn't very enlightening (it says there's at least one, when we know there are really two), but for n>2 puts our previous estimate to shame: with a three-card hand (and thus an eight-card deck), we get at least 2.54x10^21 strategies, a number so fantastically larger than our previous estimate of 6 that I'm still a little bit in shock. (It is, at least, many orders of magnitude lower than the naive upper bound of 6^56, where for each of the 3-subsets of 8 we choose one of the possible messages it could send without worrying about overlap with other hands.)

Anyway, I haven't read the linked paper, but the abstract suggests we might not get a much better lower bound than this. To improve, one might look for results on vertex transitive k-regular bipartite graphs, but I haven't found any.

st.statistics - How does the Dirichlet process work?

Hi, i'm looking to get into nonparametric bayesian techniques but I'm having problem understanding what's going on in the definition of the Dirichlet process or how it works. So what does P ~ DP(α*P₀) mean?

What does a distribution P looks like? Is the samples being used, X_i ~ P?

soft question - Which math paper maximizes the ratio (importance)/(length)?

I read all 30 previous answers, and then did "search" on this page with my browser, and
to my surprise I did not find Picard's name.

Picard's proof of the Picard Little Theorem certainly qualifies for this list.
See, for example Littlewood's Miscellany, where he discusses the question, "Can a
PhD thesis consist of one line?"

Picard's one-line proof started an enormous body of literature in XX century, beginning with
Nevanlinna theory and including Hyperbolic groups.

To be sure, Picard's original paper (CR 88(1879)1024-7) is slightly longer than one line,
but the proof itself (assuming the background that was well-known in 1879) is really
one line, as reproduced in Littlewood:-)

A slight generalization of this is called Picard's Great Theorem, the only theorem that I know, which
has the word "Great" in its standard name:-)

co.combinatorics - General form of amount of triangles that can be formed in an MxN point lattice

I've been searching for the answer for many years, both by researching by myself and reading about the subject. Now I'm wondering if this has a solution.

The problem can be stated as follows.

Given a M x N grid of points, how many triangles with vertices in the grid can be formed?
Note that you can't select two points that coincide or three collinear points because that wouldn't conform a triangle (area would be 0)

OK, I know a bit of programming and could manage to code a program that solves this, but would REALLY like to know if there is a general form depending on M and N.
I suspect it has to do with prime numbers... (Perhaps I totally missed heheh)

Thanks for your time!
Manuel

ct.category theory - Why is Top_4 a reflective subcategory of Top_3?

Hi,

I’m studying some category theory by reading Mac Lane linearly and solving exercises.

In question 5.9.4 of the second edition, the reader is asked to construct left adjoints for each of the inclusion functors Top_{n+1} in Top_n, for n=0, 1, 2, 3, where Top_n is the full subcategory of all T_n-spaces in Top, with T_4=Normal, T_3=Regular, etc.

For n=0, 1, 2, it seems to me that I can use the AFT, with the solution set constructed similarly to the one constructed for proving that Haus (=Top_2) is a reflective subcategory of Top (Proposition 5.9.2, p. 135 of Mac Lane).

But I can’t figure out what should I do with the case of n=3, that is, with the inclusion functor Top_4 in Top_3: Top_4 doesn’t even have products, so it seems that I cannot use the AFT.

Is there some direct construction of this left adjoint (by universal arrows, perhaps)? Answers including a reference would be especially helpful.

gn.general topology - What Is This Quotient Space?

Suppose Y is obtained by attaching a zero-cell, so $Y = X cup {ast}$. Then $Y^2$ is $$(X times X) cup (X times {ast}) cup ({ast} times X) cup ({ast} times {ast})$$
and so $Y^2/X^2$ is homeomorphic to
$$
{ast} cup X cup X cup {ast}.
$$
This can be arbitrarily complicated depending on X.

ADDENDUM: By request, a connected example is the inclusion $mathbb{CP}^1 subset mathbb{CP}^2$. The quotient $Y^2/X^2$, in this case, has a nonzero cohomology operation $Sq^2$ from H⁶ to H⁸ with ℤ/2-coefficients, and there is no wedge of products of spheres that can have this cohomology. (You should work out the details.)

ag.algebraic geometry - Component of Hilbert Scheme

The short (and unfriendly!) answer is that it is an irreducible component of the Hilbert scheme. Here is a slightly more detailed answer.

Given a subvariety $Xsubset mathbb P^N$, you can attach to it a polynomial, the Hilbert polynomial $P_X(t) in mathbb Q[t]$. It is a rough invariant, which nevertheless contains much qualitative information about $X$. Its degree gives the dimension $d$ of the variety: $ degree P_X(t)=dim(X)$. The leading coefficient of $P_X(t)$ calculates the degree of the variety $lead(P(t))=(1/d!): deg(X)$, the arithmetic genus of the variety is $; p_a(X)=(-1)^d(P_X(o)-1) $, etc.

Now, the Hilbert scheme (introduced by Grothendieck, as the name does not say...) parametrizes all subschemes of $mathbb P^N$ and Hartshorne has proved the wonderful theorem that if you fix the Hilbert polynomial $P(t)$, the corresponding Hilbert scheme will be connected.

Since then people have investigated these connected schemes and, in particular, their irreducible components which your question is about. The best introduction to these questions might still be Mumford's 1966 notes notes:

References
Mumford, D. Lectures on Curves on Algebraic Surfaces (with George Bergman), Princeton University Press, 1964.

Hartshorne R. Connectedness of the Hilbert scheme. Publications Mathématiques de l'IHÉS, 29 (1966), p. 5-48

Comment for functor aficionados Here are two sentences from Hartshorne's
article that will warm your heart

"It also appears that the Hilbert scheme is never actually needed in the proof. ... we define the notion of a connected functor, and prove that the functor $Hilb^p$ is connected" [From the introduction]

"This section is a variation on the theme " anything you can do with preschemes, you can do with the functors they represent " " [page 12]

Finally, you can't even define Hilbert schemes rigorously if you don't first define the functor it represents...

soft question - Math Vs Social Science

I will suppose you have an algebraic taste, and that you want to develop theory rather than analyze data.

A starting point is the observation that relationships in a social group can be modeled by a semigroup. Among the leaders of this area, developed around the 70's, you can find Harrison White. He completed a PhD in theoretical physics at MIT, then a PhD in sociology at Princeton. Currently, he is at Columbia. A serious trouble of this approach (from my point of view) is that relationships change over time, so we do not have a stable algebraic structure. There are ways around it... If you want to follow this lead, then I recommend you the book Algebraic Models for Social Networks by Philippa Pattison.

Another observation is that social sciences are full of relationships we don't measure with numbers. So, a categorical-functorial approach has been developed. In that sense Lorrain and White wrote an enjoyable article:
http://www.tandfonline.com/doi/pdf/10.1080/0022250X.1971.9989788
I would like to know how to use some category theory in this context...

I must say many sociologists dislike this approach a lot, because they consider it reductionist. I am afraid research in this area may fall in no man's land i.e neither mathematicians nor sociologists read it. However, there are some groups trying to develop this field. In particular, UC Irvine has the Institute for Mathematical Behavioral Sciences: http://www.imbs.uci.edu/. I also recomend to look up for Santa fe institute.

On other hand, a big problem for social sciences is measurement. Suppose, you develop a social theory (for example [1]). To validate the model you need to test it with reality. This is a big issue in social sciences, because you cannot take people inside a box, isolated other variables, and measure a specific behavior. Plus, real life events have many variables to account for. However, these days Google, Facebook, NSA, etc, are collecting a lot of social generated data; and there is not good theory for this sort of data. The void is being filled by computer scientists; for example Carnegie Mellon has a PhD program at its Center for Computational Analysis of Social and Organizational Systems. I attended their main conference some time ago...It impressed me their focus on extract, analyze, and represent relational data rather than understand it (in the sense of constructing theory). That perspective can be very useful, but I dislike it. Hopefully, social generated data can be used one day for constructing theories. (Noam Chomsky argued for developing theory here:
http://www.theatlantic.com/technology/archive/2012/11/noam-chomsky-on-where-artificial-intelligence-went-wrong/261637/).

[1] "A New Model of Wage Determination and Wage Inequality." Rationality and Society, 2009 by Guillermina Jasso

ra.rings and algebras - is there a notion of weakly noetherian?

A left module M over a ring is finitely presented iff the functor Hom(M,_) preserves filtered inductive limit. Meanwhile, if M is finitely generated, then for every filtered system { N_i } of left modules the morphism lim Hom(M,N_i) --> Hom(M,lim N_i) is injective.

Is there a theory of modules satisfying that necessary condition? If every ideal of a commutative ring satisfies the necessary condition, how much of the theory of noetherian rings survives?

Introduction to deformation theory (of algebras)?

My answer is more concerned with your second question ``Why this should "obviously" be a construction worth looking at, and why it should be useful and meaningful."

I would quote Arnold who, by saying that Mathematics and physics are the two opposite sides of a same medal, conveys the platonistic idea that the coherence and unity of mathematics comes in fact from the coherence and unity of nature, since it is the natural language to describe it.

If one believes in this, one realizes that most of our mathematics is classical, in the sense that most of mathematical objects come from the study of concepts originated in classical mechanics (geometry, Lie groups, ...). But it is known since the early 20th century that classical mechanics is the shadow of quantum mechanics.

Therefore, there should exist a whole brave new world of quantum mathematics, of which classical mathematics should be the ``semiclassical limit".

The paper of Bayern, Flato, Lichnerowicz and Sternheimer gives a paradigm to explore it : they show that quantum mechanics can be interpreted in terms of deformations of associative algebras of classical commutative algebras of observables on Poisson manifolds.

Therefore, an approach to quantize a mathematical concept is to encode its structure in terms of properties of an algebra of functions, and deform this algebra to a non commutative algebra with similar properties. If you apply it to the algebra of functions on a Lie group, you arrive to the concept of quantum group.

nt.number theory - Sum of reciprocals of primes modulo which a polynomial has a root

Charles is completely right that this follows from Frobenius' theorem. Since you don't like Galois theory, here is a proof which does not explicitly mention Galois theory. (But it is hiding just out of sight.)

We may assume that $f$ is irreducible as, if $g$ divides $f$, then the set of primes for which $f$ has a root contains the set for which $g$ does.

Let $K$ be the field $mathbb{Q}[x]/f(x)$. Let $R$ be the ring of integers of $K$, and let $S=mathbb{Z}[x]/f(x)$. Note that $S$ is a finite index sublattice of $R$ and, if $p$ is a prime which does not divide $|R/S|$, then $R/p cong S/p$. Also, for any prime $p$ which does not divide the discriminant of $f$, the polynomial $f$ factors into distinct factors in $mathbb{F}_p[x]$.

Thus, if $p$ is large enough to not divide either $|R/S|$ or the discriminant of $f$, then $R/p cong S/p cong mathbb{F}_p[x]/f(x) cong bigoplus mathbb{F}_p[x]/(f_i(x))$ where $f_i$ are the irreducible factors of $f$ mod $p$. So, for such a prime $p$, prime ideals of $R$ which contain $(p)$ are in bijection with irreducible factors of $f$ mod $p$, and the norm of such a prime is $p^{deg f_i}$.

So, if $f$ has a root modulo $p$, then
$$frac{1}{p} leq sum_{pi supseteq (p), pi mbox{prime}} frac{1}{N(pi)} leq frac{deg f}{p}$$
and, if $f$ does not have a root modulo $p$, then
$$sum_{pi supseteq (p), pi mbox{prime}} frac{1}{N(pi)} leq frac{(deg f)/2}{p^2}$$

We want to show that
$$sum_{p: exists pi mbox{a prime of} R mbox{with} N(pi)=p} frac{1}{p}$$
diverges. By the above inequalities, it is equivalent to show that
$$sum_{pi subset R, pi mbox{prime}} frac{1}{N(pi)}$$
diverges. (Note that the finitely many primes which divide $|R/S|$ or the discriminant of $f$ cannot change whether or not the sum converges.)

Now, we have unique factorization into prime ideals for $R$, so
$$sum_{I subseteq R} frac{1}{N(I)^s} = prod_{pi subset R, pi mbox{prime}} left( 1 - frac{1}{N(pi)^s} right)^{-1}.$$

The left hand side is the $zeta$ function of $K$. By the class number formula (see most books on algebraic number theory), $zeta_K(s) = C/(s-1) + O(1)$ for some positive constant $C$, as $s to 1^{+}$. So
$$log zeta_K(s) = log frac{1}{s-1} + O(1) = sum log left( frac{1}{1-N(pi)^{-s}} right) = sum frac{1}{N(pi)^s} + O(1/N(pi)^{2s}).$$
We deduce that
$$sum frac{1}{N(pi)^s} = log frac{1}{s-1} + O(1)$$
so
$$sum frac{1}{N(pi)}$$
diverges.

co.combinatorics - Maximum differences in sorted vectors of naturals

This question is related to one I asked previously. This is probably a little harder. I had a crack at it today, but have become stuck. I suspect the result is buried in the order statistics literature somewhere, and perhaps somebody is familiar with it. That, or Peter might insta-solve again :).

Given a vector $s$ of integers let $d(s)$ be the maximum difference between any two integers in $s$ when sorted in ascending order. That is, if we sort $s$ in ascending order to obtain $v$, then
$$d(s) = max_{i} (v_{i+1} - v_i).$$

For $s$ a vector of length $m$ from $lbrace 1,2,dots,nrbrace^m$ we must have $0 leq d(s) < n$.

Given $0 leq k < n$, how may such vectors have $d(s) = k$ ?

Again, I'm more interested in the case where $n$ is much larger than $m$ and if reasonable bounds can be found for $d(s)$, then this would be useful too.

Note: If $N_k$ is the answer for $k$. Then you should have $n^m = sum_{k=0}^{n-1}N_k$

ct.category theory - Internal hom of sheaves

Well, here is a partial answer. The category of abelian group-valued sheaves is not a topos, the category of set-valued sheaves is. And I think you should look at set-valued presheaves, at least $hom(-,U)$ is one:

When the site comes from a topological space, you can see as follows that your two definitions coincide: When you insert into the $hom$ in your second expression an open set $V$, you either get $hom(V,U)=$the one-element-set containing only the inclusion, if $V subseteq U$, or $hom(V,U)=$empty set, if not, so taking a product with the set-valued presheaf $hom(-,U)$ either leaves X as it is or "deletes" it (i.e. transforms it into the (presheaf with value the) empty set).

So a natural transformation in $hom_{PreShv}(X times hom(-,U), Y)$ is given just by its components for all $V subseteq U$ and for other $V$ it extends to the unique map from the initial object into Y. This is the same as a natural transformation of restricted presheaves.

Edit: It now occurred to me that you were probably actually speaking of the sheaves of group homomorphisms, not just any natural transformations. You get that, when you apply the "free group"-functor to the set-valued sheaf "hom(-,U)" and take tensor product instead of product. The free group over the empty set ist the trivial group, thus the initial object in groups and tensoring with it trivializes $X$. Tensoring with the free group over one element doesn't change anything, so the same things happen as in the set case...

For more general sites, the expression $X| _U$ probably means that you look at $X$ as a functor defined on the slice category given by maps on your site into its object $U$. But you can also see $X$ as a sheaf not just on the site, but on all of its ambient sheaf category (as a hom-functor, and where you give to topos an appropriate topology - you sometimes do this in topos theory). Then looking at restricted sheaves is the same as passing to the slice category $Shv / hom(-,U)$, and $X times hom(-,U)$ is the image of $X$ under the canonical functor $Shv rightarrow Shv/hom(-,U)$ (which is given by taking product with $hom(-,U)$), so it actually $is$ $X| _U$. This still doesn't make it clear to me why the two functors in question coincide, but I guess it may be a way to look at it to find it out...

integration - Inverse of a function defined by an integral

You can always get a (non-linear) ordinary differential equation for $f^{-1}$. It is easy to see that $f$ satisfies a 2nd order linear ODE with polynomial coefficients with no order 0 term [the first order ODE has non-polynomial coefficients, so harder to work with]. From there, it is also mechanical to get an ODE for $f^{-1}$ by interchanging the roles of $f$ and $w$.

But since your original function is (in general, depending on the path of integration) a MeijerG function, very few of these have closed-form inverses. As Piero mentions in the comments, the trigonometric and Elliptic functions are some of the few cases where this 'works'.

It also depends on what you are trying to do 'next' with these functions. If you are looking at numerical evaluation, then there are closed-forms for the Lagrange inverse, some of which translate to closed-forms for the Hermite-Pade approximants, from which efficient approximations can be derived. [J.M.'s method works in general, here it turns out that this can be pushed in closed-form further than usual].

For any given case, there are useful tools in Maple (and Mathematica) to help you carry these computations out. Probably in other CASes as well, but I don't know.

math philosophy - Does the Golden Ratio Apply to Timing as Well?

My guess this is not an appropriate question for MO, but being weekend and all...

I have heard of one approach to memorization which consists in repeating something in time intervals corresponding to the Fibonacci sequence. I did not find a reference, so take this with a grain of salt, though :)

nt.number theory - Why Weil group and not Absolute Galois group?

The Weil group appears for several reasons.

Firstly: if $K$ is a non-archimedean local field with residue field $k$,
the local reciprocity law induces an embedding
$K^{times} hookrightarrow G_K^{ab}.$ The image consists of all
elements in $G_k$ whose image is an integral power of Frobenius.
This is the abelianized Weil group; it just appears naturally.

Secondly: suppose that $K$ is a global field of positive characteristic,
i.e. the function field of a curve over a finite field $k$. Then the
global reciprocity map identifies the idele class group of $K$ with
a subgroup of $G_K^{ab}$ consisting of elements which act on $k$
by integral powers of Frobenius. So again, it is the abelianized Weil group
that appears.

Thirdly: suppose that $E$ is an elliptic curve over a quadratic imaginary
field $K$
with complex multipliction by $mathcal O$, the ring of integers in $K$. (Thus I am implicity fixing $K$ to
have class number one, but this is not so important for what I am going to say next.)
If $ell$ is a prime, then the $ell$-adic Tate module is then free of rank one over
$mathcal O_{ell}$ (the $ell$-adic completion of $mathcal O$), and the $G_K$-action
on this Tate module induces a character $psi_{ell}:G_K^{ab} rightarrow mathcal O_{ell}^{times}$.

There is a sense in which the various $psi_{ell}$ are indepenent of $ell$,
but what is that sense?

Well, suppose that $wp$ is a prime of $K$, not dividing $ell$ and at which
$E$ has good reduction. Then the value of $psi_{ell}$ on $Frob_{wp}$ is indepenent
of $ell$, in the sense that its value is an element of $mathcal O$, and this value
is independent of $ell$.
More generally, provided that $wp$ is prime to $ell$,
the restriction of $psi_{ell}$ to the local Weil group at $wp$ is independent of $ell$
(in the sense that the value at a lift of Frobenius will be an algebraic integer that
is independent of $ell$, and its restriction to inertia at $wp$ will be a finite image
representation, hence defined over algebraic integers, which again is then independent
of $ell$).

Note that independence of $ell$ doesn't make sense for $psi_{ell}$
on the full local Galois group at $wp$, since on this whole group it will
certainly take values that are not algebraic, but rather just some $ell$-adic
integers, which can't be compared with one another as $ell$ changes.

Now there is also a sense in which the $psi_ell$, as global Galois characters, are independent of $ell$. Indeed, we can glue together the
various local Weil group representations to get a representation $psi$ of the global Weil
group $W_K$. Since it is abelian, this will just be an idele class character $psi$,
or what is also called a Hecke character or Grossencharacter. It will take values
in complex numbers. (At the finite places it even takes algebraic number values, but
when we organize things properly at the infinite places, we are forced to think of it
as complex valued.)

Note that $psi$ won't factor through the connected component group, i.e. it won't be
a character of $G_K^{ab}$. It is not a Galois character, but a Weil group character.
It stores in one object the information contained in a whole collection of
$ell$-adic Galois characters, and gives a precise sense to the idea that these various $ell$-adic characters are independent of $ell$.

This is an important general role of Weil groups.

Fourthly: The Hecke character $psi$ above will be an algebraic Hecke character, i.e.
at the infinite places, it will involve raising to integral powers. But we can also
raise real numbers to an arbitrary complex power $s$, and so there are Hecke characters
that do not come from the preceding construction (or ones like it); in other words,
there are non-algebraic, or non-motivic, Hecke characters. But they are abelian characters
of the global Weil group, and they have a meaning; the variable $s$ to which we can raise
real numbers is the same variable $s$ as appears in $zeta$- or $L$-functions.

In summary: Because Weil groups are "less completed", or "less profinite", than Galois
groups, they play an important role in describing how a system of $ell$-adic representations can be independent of $ell$. Also, they allow one to describe
phenomena which are automorphic, but not motivic (i.e. which correspond to non-integral
values of the $L$-function variable $s$). (They don't describe all automorphic phenomena,
though --- one would need the entire Langlands group for that.)

arithmetic geometry - Decomposition of Tate-Shafarevich groups in field extensions

Fix a prime p which doesn't divide the degree of K over ${mathbb Q}$, and let ${mathcal O}$ denote the ring of integers of ${mathbb Q}_p(chi)$ i.e. an extension of ${mathbb Q}_p$ containing the values of $chi$. Then the group algebra ${mathcal O}[G]$ decomposes into a direct sum of 1-dimensional pieces over ${mathcal O}$, one for each power of $chi$.

Then $Sha(E/K)[p^infty] otimes {mathcal O}$ being an ${mathcal O}[G]$-module inherits such a decomposition. Concretely, the $chi^i$-component of $Sha(E/K)[p^infty] otimes {mathcal O}$ is the subset where $G$ acts by $chi^i$.

This $chi^i$-component is then a reasonable candidate to compare to the $p$-adic valuation of the algebraic part of $L(E,chi^i,1)$.

Some further comments:

-Note that extending scalars to ${mathcal O}$ increases the size of the modules so this has to be taken into account.

-The component corresponding to the trivial character is the invariants under $G$, and when $G$ has size prime-to-p this is simply $Sha(E/{mathbb Q})[p^infty] otimes {mathcal O}$ (which is good).

-To make a precise relationship between the $L$-value and Sha, you need to take into account the other terms in BSD. Namely:

*The torsion-term should work out exactly as above (decomposing into $chi$-components).

*The periods have to be considered (which was ignored above in my vague phrase "the algebraic part of").

*The Tamagawa numbers give me pause -- possibly there is an analogous $chi$-decomposition, but I don't see it now.

*Lastly, if K is ramified over ${mathbb Q}$ then the discriminant of K appears in the BSD quotient (in the denominator which increases the size of Sha). To handle this, I imagine what should be done is that rather then considering the L-value alone, consider the L-value times the Gauss sum of the character. (By the conductor-discriminant formula this should give exactly the extra powers of p needed.)