Recent MathOverflow Questions

Any important consequences with presupposition of $P \neq NP$?

Math Overflow Recent Questions - Wed, 08/16/2017 - 17:00

As we know, there are lots of consequences with the presupposition of the Riemann Hypothesis.

Similarly, are there any important consequences with the presupposition of $\mathbf{P} \neq \mathbf{NP}$ ?

Parallelitope fundamental domains of the n-torus

Math Overflow Recent Questions - Wed, 08/16/2017 - 16:31

The group $\mathbb Z^n$ acts on the topological space $\mathbb R^n$ by translation: if $z = (z_1, \cdots, z_n) \in \mathbb Z^n$ and $x = (x_1, \cdots, x_n) \in \mathbb R^n$, then $z\cdot x := z+x$. The quotient space of this action is the $n$-dimensional torus $\mathbb R^n/\mathbb Z^n$. In this setting, a fundamental domain is a convex set $Z \subset \mathbb R^n$ such that $Z$ surjects onto $ \mathbb R^n / \mathbb Z^n$ via the usual quotient map, and such that this map is injective on the interior of $Z$.

My question is: when is a parallelitope in $\mathbb R^n$ a fundamental domain of the $n$-dimensional torus?. By a parallelitope, I mean the $n$-dimensional analogue of a parallelogram. More precisely, a parallelitope is set of the form $\left\{ \sum_{i = 1}^n a_i v_i \mid 0 \leq a_i \leq 1 \right\}$ for some linearly independent set $\left\{ v_1, \cdots, v_n \right\}\subset \mathbb R^n$.

I'm fine with assuming that our parallelitopes are rational, meaning $v_i \in \mathbb Q^n$ for all $i$. I'm also inerested more generally in which parallelitopes in $\mathbb R^n$ surject onto $\mathbb R^n / \mathbb Z^n$ via the usual quotient map.

My initial guess was that any parallelitope with sufficiently large volume would at least surject onto the $n$-torus, but this dream was quickly crushed by the following example: if $Z$ is the rectangle $[0, 0.9999]\times [0,10000000]$ in $\mathbb R^2$, then $Z$ doesn't surject onto $\mathbb R^2 / \mathbb Z^2$, but a small rotation of $Z$ does surject.

On the other hand, it's easy to see that this property is preserved by the action of $SL_n(\mathbb Z)$ on $\mathbb R^n$. Thus we may assume that the matrix $[v_1 v_2 \cdots v_n]$ is in hermite normal form (and in particular, upper-triangular). Using this trick, I found it's not to hard (though quite messy) to figure out the $n=2$ case by hand, but I'm not sure what to do in higher dimensions.

First Return to Zero for Asymptotically Stable Random Walks

Math Overflow Recent Questions - Wed, 08/16/2017 - 16:13

Let $X_1,X_2,\ldots$ be a sequence of i.i.d. random variables taking values in $\mathbb Z$ with common characteristic function $\phi$, and let $S_n=X_1+\cdots+X_N$, with $S_0=0$. Let $$\tau=\min\{n\geq1:S_n=0\}$$ be the first return time to $0$. I'm interested in asymptotic estimates of $$P(\tau=n)\qquad P(\tau>n)$$ as $n\to\infty$.

For example if $S_n$ is aperiodic and the $X_i$ are in the normal domain of attraction of a stable law of parameter $1<\alpha\leq2$, i.e., $$\lim_{t\to0}|t|^{-\alpha}(1-\phi(t))\in(0,\infty),$$ then $$n^{2-\alpha}P(\tau=n)\sim C_\alpha\tag{1}$$ for some constant $C_\alpha$ (Theorem 8 of Ratio theorems for random walks II by Kesten), from which $P(\tau>n)$ is easily recovered.

Question. Are there known generalizations of eq. (1) for random walks that are in the non-normal domain of attraction of a stable law, or is it known that no such result exist? (The standard references (such as Spitzer) do not seem to discuss such results.)

I'm looking for results of a similar generality as Theorems 7 and 10 of Local Probabilities for Random Walks Conditioned to Stay Positive by Vatutin and Wachtel, which concern the slightly different stopping times $$\tau^-=\min\{n\geq1:S_n\leq0\}\qquad \tau^+=\min\{n\geq1:S_n>0\}.$$

Entire function that grows along one axis and decays along the other

Math Overflow Recent Questions - Wed, 08/16/2017 - 15:34

I would like to find an entire function on the complex plane that grows with $|\mathrm{Re}(z)|$ no faster than $e^{\alpha |\mathrm{Re}(z)|}$ (for some fixed positive $\alpha$), and decays as fast as possible in both directions along the $\mathrm{Im}(z)$ axis.

As an example, we could consider $\cosh(\alpha z)$. This grows like $e^{\alpha |\mathrm{Re}(z)|}$ along the real axis and oscillates along the imaginary axis. By averaging over different $\alpha$'s, we can make it decay like $1/\mathrm{Im}(z)$ in the imaginary direction,

$\int_0^\alpha d\alpha' \cosh(\alpha' z) = \frac{\sinh(\alpha z)}{z}.$

And by averaging again over $\alpha$, we can make it decay like $1/\mathrm{Im}(z)^2$,

$\int_0^\alpha d\alpha' \frac{\sinh(\alpha' z)}{z} = \frac{\cosh(\alpha z) - 1}{z^2}.$

However, beyond this point the averaging trick doesn't make it decay any faster in the imaginary direction.

Is there an entire function that grows at most like $|\mathrm{Re}(z)|$ in the real directions and decays faster than $1/z^2$ in the imaginary directions?

CTRW: solve a renewal equation

Math Overflow Recent Questions - Wed, 08/16/2017 - 15:30

Let X(t) be a continuous time random walk, with exponentially distributed waiting times of pdf $f_T(t)= k e^{-k t}\; t\geq 0$ and a jump sizes pdf $f_J(x)$. Suppose the initial distribution $\rho_{X(0)}(x)$. I would like to prove (or correct) the following intuitive expression for the survival probability above a certain threshold $a$: \begin{align} \Pr (X(t')\geq a \; \forall t'\leq t \; | \; \rho_{X(0)}) &\equiv S_a(t \; | \; \rho_{X(0)}) \\ &= \int_a^\infty \Big(\sum_{n=0}^\infty \frac{(e^{-kt}kt)^n \mathcal{O}^n}{n!}\Big) \rho_{X(0)} (x) dx\\ &= \sum_{n=0}^\infty \frac{(e^{-kt}kt)^n }{n!}\int_a^\infty\mathcal{O}^n\rho_{X(0)} (x) dx \end{align} where $\mathcal{O}$ is an operator that I believe to be $H_a \circ \circledast_{f_J}$ the convolution by the jump size pdf followed by the multiplication by a Heaviside function with a cut off at $a$.

The first step would be to write a renewal equation for $S_a$, here is my attempt, first for $a<x_0$ and $\rho_{X(0)}=\delta_{x_0}$: \begin{align} S_{a}(t|\delta_{x_0})&=\int_t^{\infty} f_T(t')dt'+\int_0^t \int_{a}^{\infty}S_{a}(t-t'|\delta_{x})f_J(x-x_0)f_T(t')dxdt' \end{align} The probability to stay above $a$ up to time $t$ starting from $x_0$ is the probability to stay at $x_0$ (no jump) plus the probability to make any jump to $x\geq a$ at time $t'<t$ and to survive above $a$ up to time $t$. We could then define $S_a(t \; | \; \rho_{X(0)})=\int_a^\infty S_a(t \; | \; \delta_{x})\rho_{X(0)}(x)dx$ \begin{align} \int_a^\infty S_{a}(t|\delta_{x_0})\rho_{X(0)}(x_0)dx_0 &= \int_a^\infty \rho_{X(0)}(x_0)dx_0\int_t^\infty f_T(t')dt'\\ &+ \int_a^\infty \rho_{X(0)}(x_0)\int_0^t \int_a^\infty S_a(t-t'|\delta_{x})f_J(x-x_0)f_T(t')dxdt'dx_0 \end{align}

We can easily simplify the time part of this integral equation by taking its Laplace transform with respect to $t$. And I see how to get the Poisson distribution. However, the space part is more complicated. We can write explicitly the Heaviside's functions and take the Fourier transform, but this does not lead me to the expected result. The renewal equation is probably not correctly set.

Do you see anything wrong here? A resolution using a Green function may be another way.

Functorial description of irreducibility of topological space?

Math Overflow Recent Questions - Wed, 08/16/2017 - 15:13

This is a crosspost of this MSE question.

A topological space is connected if it's not the coproduct of two non-trivial spaces. Equivalently, it is connected if the copresheaf it represents preserves coproducts.

A topological space is irreducible if it's not the union of proper closed subsets, or alternatively if every pair of non-trivial opens has inhabited intersection. Does irreducibility admit a functorial description?

Functions defined on S^2

Math Overflow Recent Questions - Wed, 08/16/2017 - 14:29

Let $u$ be a differentiable function defined on $S^2$, and for every vector $N \in S^2$ let $L_N$ be the plane which passes through the origin and is normal to $N$. Does there exist a plane $L_{N^*}$ such that $L_{N^*}\cap S^2$ contains three points $p_1,p_2,p_3$ such that $\nabla u(p_i) \cdot N^* =0$ for i=1,2,3?

Existence of two points with such properties is trivial. Indeed one can take $L_{N^*}$ to be the plane passing through the two critical (maximum an minimum) points of $u$.

Matrix norms: operator norm vs vectorized $L_1$-norm? [on hold]

Math Overflow Recent Questions - Wed, 08/16/2017 - 13:58

Let for a square matrix $A$ the operator norm $\|A\|$, and vectorized $L_1$-norm $$ \|vec(A)\|_1 = \sum_{i,j} |A_{ij}| $$ Do we have the following? $$ \|A\| \le \|vec(A)\|_1 $$

Spectrum of an operator

Math Overflow Recent Questions - Wed, 08/16/2017 - 13:47

Let $L$ an operator self-adjoint acting on $L^2(\Bbb{R}^{2})$ such that :

  1. $L(\phi_{\alpha,\beta})=(|\alpha|-|\beta|)(\phi_{\alpha,\beta})$ where $(\phi_{\alpha,\beta})$ is an orthonormal basis for $L^2(\Bbb{R}^{2})$ with $ \alpha=(\alpha_1,\alpha_2)\in\Bbb{N}^{2}$ and $|\alpha|$ its length $\alpha_1+\alpha_2$.
  2. There is a sequence $(u_n)\in L^2(\Bbb{R}^{2})$ such that :

for $p\in \Bbb{N}$ we have $(L-p)u_n\overset{L^2(\Bbb{R}^{2})}{\longrightarrow} 0$ and $ u_n\overset{weakly}{\longrightarrow} 0$.

From 1, the spectrum of the operator $L$ is the set $\sigma(L)=\{m;m\in\Bbb{Z}\}$. Now, for the above $p$ there are $\alpha, \beta$ such $p=(|\alpha|-|\beta|)$ and $L(\phi_{\alpha,\beta})=p(\phi_{\alpha,\beta})$

My question is the following: Is there a contradiction between $L(\phi_{\alpha,\beta})=p(\phi_{\alpha,\beta})$ and the fact 2.

Thanks in advance for any help.

subisomorphic modules

Math Overflow Recent Questions - Wed, 08/16/2017 - 13:38

An $R$-module $M$ is called Baer if for every $N\leq M_R$, ann$_{S}(N)$ is a direct summand of $S$ where $S=$ End$_{R}(M)$.

Question: Let $N$ and $K$ be Baer $R$-modules such that $N$ is isomorphic to a direct summand of $K$ and $K$ is isomorphic to a direct summand of $N$. Does $N\simeq K$? I am searching for a counterexample in this field.

Thank you for your comments.

Slope semi-stability on stacks

Math Overflow Recent Questions - Wed, 08/16/2017 - 13:33

Can anyone tell me a good reference for usual slope semi-stability on stacks (may be of coherent sheaves)??

Maximal subgraphs with dense connections

Math Overflow Recent Questions - Wed, 08/16/2017 - 12:46

Let G=(V,E) be a given network. Denote by $S_k \subset V$ be the maximal subset of nodes such that in the induced subgraph $G_k=(S_k, E_k)$ (where $E_k=E\cap S_k \times S_k$), all agents have at least $k$ connections, i.e., $i\in S_k \Rightarrow \sum_{j\in S_k} g_{ij}\geq k$, where $G$ denotes the unweighted adjacency matrix.

My question is whether for a given $k$ the set $S_k$ corresponds to a known quantity in the graph theory literature. I am interested in understanding how the cardinality of set $S_k$ changes as a function of $k$ for different families of graphs (or certain random graph models).

Working on which problems of differential geometry or differential topology leads to the Fields medal? [on hold]

Math Overflow Recent Questions - Wed, 08/16/2017 - 12:40

Sorry because of this question.

Most of my colleagues ask me that working on which problems of differential geometry or differential topology leads to the Fields medal? They believe that field of most of Fields medalists are algebraic geometry. I want to ask this question here for good answer.


An exponential sum estimate on small intervals

Math Overflow Recent Questions - Wed, 08/16/2017 - 12:07

Let $1<r<2$ be a real number. Let $4<p\le 6$. Consider the exponential sum estimate $$\int_0^{2\pi}\int_0^{N^{r-2}} \left|\sum_{n=1}^N e^{inx+in^2 y}\right|^pdydx$$ Notice that the $y$ variable takes values in an interval of length much smaller than one. My question is, as $N\to \infty$, what is the sharp bound on the above exponential sum?

A manifold is a homotopy type and _what_ extra structure?

Math Overflow Recent Questions - Wed, 08/16/2017 - 11:15
Motivation: Surfaces

Closed oriented 2-manifolds (surfaces) are "classified by their homotopy type". By this we mean that two closed oriented surfaces are diffeomorphic iff they're homotopy equivalent. This means that somehow the homotopy type of the surface contains essentially all information about the manifold.

Let's turn the question around. Let's choose a homotopy type $M$, and ask whether it specifies a manifold. I have to be more precise by what I mean here. First of all, let's fix a dimension, say 2 for now, although we can increase it later. Of course not every homotopy type will correspond to a surface. There a some restrictions on $M$, such as:

  1. It has to have cohomological dimension 2, i.e. isomorphisms $H^k(M) \cong 0 \quad \forall k > 2$.
  2. We have to specify an isomorphism $\phi\colon \mathbb{Z} \xrightarrow{\cong} H^2(M)$ which will in particular define the fundamental class $[M] := \phi(1)$, corresponding to orientation.
  3. Cohomology and homology have to exhibit Poincaré duality, which is to say that the cap product with the fundamental class is an isomorphism: $[M] \cap - \colon H_k(M) \xrightarrow{\cong} H^{2-k}(M)$

Now we're in better shape. Although I don't know a proof and haven't seen this statement anywhere, I'd venture the following conjecture, which should be easy to prove or disprove by anyone who knows more homotopy theory than me:

Conjecture Each homotopy type with the extra structure outlined in 1. - 3. corresponds to a closed, oriented surface. In particular, there is an equivalence between the category of homotopy types with extra structure and the category of closed, oriented surfaces.

Note also that the cap product is functorial, so a map of surfaces should be a map of the homotopy types preserving all of the structure.

The takeaway is this: I've come to believe that surfaces are essentially homotopy types with extra structure on cohomology and homology that comes from the manifold structure. Possibly I haven't captured all structure that is needed. But I guess one could amend the list in that case.

Question 1: Am I right so far?

Higher dimensions: Topological, PL and smooth structures

It gets hairier when we go up dimensions. There are closed 3-manifolds that are homotopy equivalent, but not homeomorphic. On the other hand, simply connected topological 4-manifolds are classified by their intersection form, so they can be completely recovered by the information in 1. - 3. ! For smooth structures, there is of course less luck, although the Kirby-Siebenmann class in 4th cohomology tells you whether there is a PL structure or not, so that sounds like a promising candidate for more extra structure along the lines of what we had so far.

Question 2: How far can we carry on the idea and classify higher dimensional (topological, PL, or smooth manifolds) by extra structure on the homotopy type, or its homology and cohomology?

Boundaries, noncompact manifolds

We could wonder whether it's possible to generalise the story to manifolds with boundaries, or noncompact manifolds. Then the homotopy type will certainly not be sufficient.

Already surfaces with boundary are not classified by their homotopy type. (Typical counterexample: The direct sum of two annuli, and the minimal 1-handlebody of a torus.) What is really relevant here is the homotopy type of the boundary inclusion $\partial M \hookrightarrow M$, and the corresponding relative cohomology.

(Similarly, for noncompact manifolds what seems to be relevant is compactly supported cohomology, which is related to the compactification of the manifold.)

How far can the idea be generalised here?

The number of permutations of a given cycle type that fix a string with a given histogram

Math Overflow Recent Questions - Wed, 08/16/2017 - 09:59

Let $\lambda$ and $\mu$ be partitions of some integer $n \geq 1$. Let $d$ be the number of parts in $\mu$ and let $\bar{\mu} \in \{1,\dotsc,d\}^n$ denote the string $1^{\mu_1} 2^{\mu_2} \dotsb d^{\mu_d}$ (i.e., $\mu_1$ ones, $\mu_2$ twos, etc.). Let $N_{\lambda\mu}$ denote the number of permutations of cycle type $\lambda$ that leave the string $\bar{\mu}$ invariant.

Does this quantity have a name or is it perhaps related to some other known combinatorial quantity? Is there any simple formula or algorithm for computing it?


One can check that $N_{(2,1,1,1),(3,2)} = 4$ because in the string 11122 there are three ways of swapping ones and one way of swapping twos.

Computing $N_{\lambda\mu}$

More generally one can go about computing $N_{\lambda\mu}$ by packing the cycles $\lambda$ into the histogram $\mu$. We call $\{S_1, \dotsc, S_d\}$ a packing of $\lambda$ into $\mu$ if $S_i$ are disjoint sets such that their union is $\{1, \dotsc, k\}$, where $k$ is the number of parts in $\lambda$, and $\mu_i = \sum_{j \in S_i} \lambda_j$ for all $i \in \{1, \dotsc, d\}$. Then it seems that $$ \begin{align} N_{\lambda\mu} &= \sum_{\{S_1,\dots,S_d\}} \prod_{i=1}^d \binom{\mu_i}{\lambda_{S_i}} \prod_{j \in S_i} (\lambda_j-1)! \\ &= \sum_{\{S_1,\dots,S_d\}} \prod_{i=1}^d \frac{\mu_i!}{\prod_{j \in S_i} \lambda_j} \end{align} $$ where the sum is over all packings of $\lambda$ into $\mu$ and $\binom{\mu_i}{\lambda_{S_i}}$ denotes the multinomial coefficient with the parts of $\lambda$ indexed by $S_i$ at the bottom. Is there any simpler way of doing this?

Properties of $\zeta(s)\zeta(2s)\zeta(3s)...$

Math Overflow Recent Questions - Wed, 08/16/2017 - 03:24

Let's consider the Dirichlet series $f(s)=\sum_{n=1}^\infty a_n n^{-s}$, where $a_n$ is the number of non-isomorphic abelian groups of order $n$. Now $a_n$ is weakly multiplicative and $a_{p^k}=P(k)=$ partition number of $k$, so we get $f(s)=\prod_{p} \sum_{k=0}^\infty P(k) p^{-ks}=\prod_{p} \prod_{k=1}^\infty \frac{1}{1-p^{-ks}}$ because of the generating function of the partition number. So we get $f(s)=\prod_{k=1}^\infty \zeta(k s)$ (where everything converges absolutely).
So my question is: what is known about this function? Is there a functional equation or an analytic continuation?
Thank you very much.

Model structure on wheeled topological properads

Math Overflow Recent Questions - Tue, 08/15/2017 - 18:59

A wheeled properad is roughly, if I understand correctly, a properad (or PROP) with contraction maps $O_i^j\to O_{i-1}^{j-1}$ which contract an input with an output. There is a book, Infinity Properads and Infinity Wheeled Properads by Hackney, Robertson and Yau, which defines a category of wheeled infinity-properads, from the point of view of a Joyal/Lurie-like combinatorial picture (as simplicial sets with some extra structure).

Now the combinatorially defined infinity-category of operads is equivalent to the category of topological operads when the two sides are viewed as model categories or $\infty$-categories obtained from localization. If I understand correctly, a similar statement holds for PROPs.

My question is whether one can define a category of topological wheeled properads and a model structure on this category which is equivalent to the definition of Hackney, Robertson and Yau. In fact, I haven't even been able to find a notion of topological wheeled properad defined anywhere - is there a reason why this is nontrivial?

Implausible inequality

Math Overflow Recent Questions - Tue, 08/15/2017 - 18:53

Let $t,d,a \ge 1$, of which $d$ can be unbounded, $a$ can be constrained to be larger than some threshold (which can depend on $d$ in some mild way, say logarithmically). How to find out whether the following true?

$\exists C,\epsilon>0$ constants independent of $d$ s.t. $\forall t>d\cdot C$, it holds that:

$\left(\frac{t}{d}\right)^{d/2}\left(\frac{d+a}{t+a}\right)^{(d+a)/2} \le C\cdot t^{-1-\epsilon}$

What I was thinking to try is to look at the limit of the fraction of the LHS/RHS when $t\rightarrow \infty$, see if it is finite. Well, it is (zero for $1+\epsilon \le a/2$). But that doesn't give a constant $C$ independent of $d$. Ideas would be appreciated.

EDIT: Replaced the condition as suggested by Yaakov Baruch's comment.

Center of a split unipotent group

Math Overflow Recent Questions - Tue, 08/15/2017 - 15:49

Let $N$ be a unipotent algebraic group over a field $k$ of characteristic $p>0$. Assume that $N$ is split (i.e. it admits a filtration whose quotients are isomorphic to the additive group). In particular, it is smooth and connected (since the additive group is smooth and connected and these two properties are stable under passing to extensions).

Then which of the following subgroups of $N$ are split?

  • the (scheme-theoretic) center of $N$ (or its identity component)
  • the maximal smooth central $k$-subgroup of $N$ (or its identity component)
  • the cc$kp$-kernel of $N$ (i.e. the maximal smooth connected central $p$-torsion $k$-subgroup of $N$)


Subscribe to curious little things aggregator