Math Overflow Recent Questions

Primary tabs

most recent 30 from mathoverflow.net 2018-10-17T02:59:20Z

Latent Dirichlet allocation - math words digest ?

Thu, 07/05/2018 - 13:41

Latent Dirichlet allocation - is quite a popular topic in data-mining. Wikepedia mentions thousands citations in few years.

Question 0 Can one give some digest for a math minded person of the key ideas ?

Question 1 Is there non-trivial mathematical result behind ?

Question 2 What practical problem does it help to solve ?

Question 3 How the two questions above are related ?

Ideally I would be happy to see some theorem which would be important for some practical problem.

Estimate for the binomial coefficients and bounds from below for the Beta function

Thu, 07/05/2018 - 08:24

Let $n\ge p\in \mathbb N$ and let $\binom{n}{p}$ be the binomial coefficient. I believe that $$\binom{n}{p}\le 2^n\sqrt\frac{2}{π n}.$$ Question: is that true? Of course I would like it as a non-asymptotic result, valid for all integers $n,p$. A related estimate would be a bound from below for the Beta function with $$B(x,y)\ge \frac{\sqrt{(y-1)(x-1)}}{2^{x+y-1}}\sqrt\frac{π(x+y-1)}{2},\quad x,y\ge 1.$$

Non-orientable 3-manifolds

Thu, 07/05/2018 - 08:12

I am reading "Non-orientable 3-manifolds of small complexity" by Amendola, Martinelli. In this work $\mathbb P^2$-irreducible complexity 6 manifolds are listed. There are 5 of them. I wonder about the following non-orientable manifolds.

1. Take $S^2\times I$ and glue its top sphere to its bottom sphere with the antipodal homeomorphism or with a reflection in plane homeomorphism. Let's denote it by $S^2\widetilde\times S^1$.
2. $\mathbb P^2\times S^1$

I assume that those two manifolds are not $\mathbb P^2$-irreducible. I don't know how to embed $\mathbb P^2$ into the first one. The preposition 1.3 on page 5 of the abovementioned work says that a Stiefel-Whitney surface cannot be a sphere. It seems to me that it is sphere for the first manifold.

Both of them have double cover $S^2\times S^1$, and the fundamental groups are $\mathbb Z$ and $\mathbb Z + \mathbb Z_2$. What are the fundamental groups of the 5 manifolds of complexity 6 in the above work?

At the same time I have the following additional questions about non-orientable 3-manifolds.

A. In case of surfaces we obtain a non-orientable one by the connected sum of an orientable one with $\mathbb RP^2$. Is there an analog in 3-manifolds? We could use the first manifold above $S^2\widetilde\times S^1$ since $\mathbb RP^3$ is unfortunately orientable.

B. A non-orientable surface with a removed disk is embeddable in $\mathbb R^3$. Can we embed a non-orientable $M^3$ with removed ball into $\mathbb R^4$ ?

C. Is the regular neighborhood of a loop changing orientation in a 3-manifold homeomorphic to a full Klein bottle ?

EDIT 2018-07-08 I add following new question.

D. Each non-orientable surface is double covered by orientable one. We can ask whether every 3-manifold with infinite fundamental group is double cover of some non-orientable one.

The answer to my question A is negative but still it seems that we can somehow convert orientable manifold into non-orientable by attaching handle which change orientation. When Stiefel-Whitney surface is sphere then it is the case.

Parity with feasibility Mixed LP

Wed, 07/04/2018 - 22:29

If $b\in\mathbb Z$ is an integer constant with $0\leq b\leq 2^t-1$ then is it possible to test for parity of $b$ in a feasibility Mixed Integer Linear Program with $2^{2^{O(t)}}$ real variables and constraints and $1$ integer variable $b$ where the variables and constraints depend only on $t$ and the same program works at all $b$ in $[0,2^t-1]$?

Surely convexity is not issue since we can do this with both feasibility Integer Linear Program in $O(1)$ integer variables and constraints and with optimization Linear Program with $2^{O(t)}$ real variables and constraints but where $b$ is a constant which with strong duality gets different LP for each $b$.

Cohen/Random reals over intermediate models in countable support iterations

Wed, 07/04/2018 - 15:23

Assume that the continuum is $\aleph_2$ in our ground model $V$. Suppose that $(P_n \, : \, n \in \omega)$ is a fully supported iteration of length $\omega$. Suppose further that the factors of the iteration are proper and add for every step $\omega_1$-many Cohen reals over the previous model.

If we let $P_{\omega}$ be the inverse limit, then there will be new reals which were not added by one of the $P_n$'s. Will there be a real $r$ in $V^{P_{\omega}}$, such that $r$ is Cohen over every $V^{P_n}$?

I am also highly interested in the dual situation, where we replace Cohen forcing with Random forcing in the above. Can we guarantee that there is a real $r$ which is Random over all $V^{P_n}$'s? If not, is it possible to feed in countably many proper factors to the iteration, such that we can exclude reals which are Random/Cohen over the $V^{P_n}$'s

Generalized Smith Theorem for the torsion of cokernels

Wed, 07/04/2018 - 11:06

Let $R$ be a (commutative) domain and let $Q$ be its fraction field. Consider a morphism $f\colon R^n \to R^m$, i.e. a matrix $A \in M(m,n;R)$, and let $K= \operatorname{coker} f$.

Let $I_k=(\det \operatorname{min}_k(A))$ be the ideal of $R$ generated by all determinants of minors of $A$ of size $k$. I wonder if $$\operatorname{Tor}_1^R(K,Q/R) \simeq \prod_{k=1}^{\operatorname{rk} A} \frac{I_{k-1}}{I_{k}}.$$ If $R$ is a PID, the above isomorphism holds by Smith Normal Form.

Does it hold for other classes of rings?

I'm particularily interested in the case of $R$ is an order in a quadratic imaginary extension of $\mathbb{Q}$.

Map of stacks $\underline{M}\rightarrow B\mathcal{H}$ is given by principal $\mathcal{H}$ bundle

Wed, 07/04/2018 - 08:28

I am reading Orbifolds as stacks.

In page $22$ it says :

Lemma : Let $M$ be a manifold, $\mathcal{H}$ be a Lie groupoid. Then any map of stacks $F:\underline{M}\rightarrow BH$ is naturally isomorphic to the functor $BP$ induced by a principal $\mathcal{H}$ bundle $P$ over $M$.

Here $\underline{M}=B(M\rightrightarrows M)$, category of principal bundles and equivariant maps associated to groupoid $\{M\rightrightarrows M\}$.

I am not really looking for proof with full details. Some rough sketch would also be sufficient for now.

See that $(\underline{M})_0$ is the collection of principal $\{M\rightrightarrows M\}$ bundle.

What we want is a principal $\mathcal{H}$ bundle $P$ over $M$.

So, it is only natural to look for an element of $\underline{M}$ i.e., a principal $\{M\rightrightarrows M\}$ bundle say $Q$ and take its image under (object map of $F$) to get a principal $\mathcal{H}$ bundle $F(Q)$. We want principal bundle to be over $M$.

As $F$ is such that $\pi_{\mathcal{H}}\circ F=\pi_M$ where $\pi_{\mathcal{H}}:B\mathcal{H}\rightarrow Man$ and $\pi_M:\{M\rightrightarrows M\}\rightarrow Man$ where both functors on object level sends a principal bundle to its base. Thus, to get a principal $\mathcal{H}$ bundle over $M$, it is only natural to look for a principal $\{M\rightrightarrows M\}$ bundle $Q$ over $M$. Then $F(Q)$ is a principal $\mathcal{H}$ bundle over $M$ which we might want to call as $P$ in the lemma.

Now the question is what choice of $Q$ should one make?

In that paper, proof starts with saying As we have seen in Remark $4.1$, the objects of $\underline{M}$ are maps $Y\rightarrow M$.

I could not understand how $4.1$ assures what is said above. I tried to follow my nose and ended up some where close to the objects of $\underline{M}$ are maps $Y\rightarrow M$.

Can some one suggest an outline of the proof of above lemma which is not along the lines of seeing objects of $\underline{M}$ as maps $Y\rightarrow M$.

There are two notions of categories which has same notation :

1. Let $M$ be a manifold. We can associate it with Lie groupoid $\mathcal{G}:=\{M\rightrightarrows M\}$. Given a Lie groupoid $\mathcal{H}$, there is a stack associated with it namely $B\mathcal{H}$ whose objects are principal $\mathcal{H}$ bundles and morphisms are $\mathcal{H}$ equivariant maps. For $\mathcal{G}=\{M\rightrightarrows M\}$ we have associated category $B\mathcal{G}$ and we denote it by $\underline{M}$.
2. Let $C$ be an object in a category $\mathcal{C}$. We have $$\underline{C}_0=\{f:C'\rightarrow C\text{ for } C'\in \mathcal{C}_0\}$$ Given $f:C'\rightarrow C$ and $g:C''\rightarrow C$, the morphism set $Mor_{\underline{C}}(f,g)$ is defined to be $$Mor_{\underline{C}}(f,g)=\{\alpha:C'\rightarrow C''\text{ such that }g\circ \alpha=f \}$$ In particular, for a smooth manifold $M$ seen as an object in category of Manifolds, we have $\underline{M}$

I am trying to see that these two notions are exactly the same(upto isomorphism/equivalence of categories). I have rough idea which has some gaps. Is there any quick way to see these two are one and the same?

References for control-affine theory

Tue, 07/03/2018 - 12:49

In Control theory from the geometric viewpoint by Agrachev and Sachkov, the authors mention the concept of control-affine (affine in control $u_i$) systems: $$\dot{x} = (f_0 + \sum_{i=1}^{m} u_i f_i)x$$

I would like to have some sources on the topic, preferably a survey of the field, overview or a textbook. My primary questions are:

• What are main results?
• When can a CA system be linearized?
• What are specific criteria for controllability, observability, optimality of control?
• Other generalizations of results for linear systems.
• Some good examples.

A projective $\mathbb{Z}\pi_1$-module

Tue, 07/03/2018 - 10:30

Suppose that $Z$ is a finite wedge of spheres containing circles and there exist maps $f:Y\to Z$ and $g:Z\to Y$ so that $g\circ f\simeq 1_Y$. Assume that there exists a map $h:X\to Y$ which induces an isomorphism on fundamental groups, where $X$ is a finite wedge of circles.

Is $\pi_2 (M_{h},X)$ a projective $\mathbb{Z}\pi_1 (X)$-module?

Here $M_h =\frac{X\times I\sqcup Y}{(x,1)\sim h(x)}$ denotes the mapping cylinder of $h$.

The minimum of the maximum of a sequence of sinc functions

Tue, 07/03/2018 - 02:40

I apologise if this is trivial or well known to be impossible:

Can one find a finite set of integers $2\leq a_1<a_2<\ldots<a_m<\infty$ such that for the function defined as $$f_{a_1,\ldots,a_m}(x)=\max\left\{\left|\frac{\sin (a_1 x)}{\sin x}\right| ,\left|\frac{\sin (a_2 x)}{\sin x}\right| , \cdots,\left|\frac{\sin (a_m x)}{\sin x}\right| \right\}$$ the minimum satisfies $$\min\{f_{a_1,\ldots,a_m}(x):0\leq ~x~\leq 2\pi\}>1?$$

More generally can the lower bound be made larger? Say larger than a small positive integer? Or a slowly growing function of $m$?

How to prove the above proposition by means of number theory？

Tue, 07/03/2018 - 00:52

Function $\pi(x)$ is defined as the number of primes not greater than $x$.

Theorem 1: $\pi(x)\approx x/(2\log_{10}x)\qquad \{x|1\leqslant x\leqslant 1000, x\in \mathrm{positive~integer}\}$.

Theorem 2: $\pi(x)<k(x/\log_{10}x)\qquad \{x|1\leqslant x\leqslant+\infty,x\in \mathrm{positive~integer}\}$. Please prove that $k\geqslant 0.55$.

Theorem 3: $\pi(x)\approx k(x/\log_{10}x)\qquad \{x|1\leqslant x\leqslant +\infty, x\in \mathrm{positive~integer}\}$. Please prove that as $x$ gradually increases, although $k$ sometimes fluctuates, in general, $k$ is decreasing.

integration by parts for fractional laplacian formula for a larger class of functions

Tue, 07/03/2018 - 00:40

When is this formula valid $\int_{\mathbb R^N} (-\Delta)^sf g =\int_{\mathbb R^N} (-\Delta)^s g f$ with $s\in (0, 1)?$ I am aware of the integration by parts formula holds for $f, g$ in $L^2(\mathbb R^N)$. Is it valid for a larger class of functions which are not in $L^2$ but $\int_{\mathbb R^N} (-\Delta)^sf g$ and $\int_{\mathbb R^N} (-\Delta)^sg f$ are finite.

Which open manifolds admit a transitive Lie group action?

Mon, 07/02/2018 - 23:36

Let $M$ be a connected open manifold. (i.e. non-compact and without boundary). Are there any obstructions for $M$ to admit a smooth transitive Lie group action?

(I mean a finite-dimensional Lie group).

I know that there are obstructions in the compact case.

In particular, I am interested in the case where $M$ is the space of real $d \times d$ matrices of rank bigger than $k$, for some fixed $k$. Of course, in this case there is a $\text{GL}(V) \times \text{GL}(V)$-action with finite number of orbits-each orbit corresponds to a different rank.

Even if there exists a transitive action, I don't expect it to be as natural.

$U(1)$ v.s. $SU(N)$ v.s. $SO(N)$ instantons

Mon, 07/02/2018 - 20:49

I am interested in knowing the details of the comparison between $U(1)$, $SU(N)$ and $SO(N)$ instantons for their gauge theories in 4 spacetime dimensions., in terms of:

1. Chern class (1st, 2nd), and

2. Pontryagin class

3. And their normalization and mapping between the instanton numbers. For example, the unit instanton number 1 in $SO(3)$ gauge theory may map to the instanton number 1/4 in $SU(2)$ gauge theory on a non-spin manifold, while the unit instanton number 1 in $SO(3)$ gauge theory may map to the instanton number 1/2 in $SU(2)$ gauge theory on a non-spin manifold etc.

More precisely, can we compare the quantization of the charcteristic classes $$p_1(SO(N)),$$ $$c_2(SU(N)=\frac{1}{8 \pi^2}\int \text{tr}(F_{(SU(N))}\wedge F_{(SU(N))}),$$ $$c_1^2(U(1))=\int \frac{F_{U(1)}}{2 \pi} \wedge \frac{F_{U(1)}}{2 \pi} =\frac{1}{4 \pi^2} \int {F_{U(1)}} \wedge {F_{U(1)}} ,$$ on the spin manifolds and non-spin manifolds?

We can also embed the $U(1) \subset SU(N)$, $U(1) \subset SO(N)$ and $SO(N) \subset SU(N)$ to compare the instanton numbers of $G_a$ evaluated as the instanton numbers of $G_b$ whenever $G_a \subset G_b$. So how are the instanton number maps from that of $G_a$ to that of $G_b$?

Here $F=dA + A \wedge A$ is the 2-form curvature of the 1-form connection $A$.

Genus of Cayley graph of $A_5$ with two generators of order 5

Mon, 07/02/2018 - 19:36

The Cayley graph of $A_5$ with two generators of order 5 (I believe all such are isomorphic) seems rather complicated. I am wondering what is its graph genus (orientable or non-orientable). The best I could get by trial and error is an embedding without crossings on a sphere with 10 crosscaps:

Profiles of very high dimensional functions

Mon, 07/02/2018 - 19:08

This question comes from trying to understand the recent success of deep neural nets. Neural networks just (crudely speaking) create a very complicated function of very many variables, and then perform gradient descent. It would be natural to expect them to get stuck in local minima, but that does not seem to be a serious problem. The practitioners, when asked, seem to believe that this is because in very high dimensions it is very unlikely that a critical point is a local minimum (since the signs of the eigenvalues of the Hessian are, in some sense, randomly distributed, so, since the dimension is high, it is unlikely that they are all negative). Is there any notion of "random functions" that makes this reasoning, well, reasonable? Presumably, similar phenomena should occur in mathematical physics...

Create "new" Vassiliev knot invariants?

Mon, 07/02/2018 - 17:25

If I want to create ("my own") finite type knot invariant, how would I approach it? Can I just pick a degree and in some process figure out the definition of the invariant?

Prove that for any two rational numbers r and s with r ≠ 0 , 1/ (r − s) is rational [on hold]

Mon, 07/02/2018 - 17:21

Hello I have the following to problem

Prove that for any two rational numbers r and s with r ≠ 0 , 1/ (r − s) is rational.

My proof process is as follows (may be incorrect)

Suppose r and s are rational numbers.

By definition of rational, they can be expressed as a quotient of two integers with a nonzero denominator.

Then 1/r is equivalent to (1- sr)/r

Not sure where to go after this step

Coefficients $U_m(n,k)$ in the identity $n^{2m+1}=\sum\limits_{0\leq k \leq m}(-1)^{m-k}U_m(n,k)\cdot n^k$

Mon, 07/02/2018 - 17:07

Review the main result of mathoverflow.net/questions/297900, that is the identity $$\label{f1} n^{2m+1}=\sum\limits_{1\leq k \leq n}\sum\limits_{j\geq0}A_{m,j}k^j(n-k)^j,$$ where $A_{m,j}$ is from sequences A302971 and A304042. In this question we discuss the polynomial $$\label{f2} \sum\limits_{0\leq k \leq m}(-1)^{m-k}U_m(n,k)\cdot n^k, \ m\geq0 \ \mathrm{integer}$$ That is generated by the identity $$\label{f3} (1.3)\quad\sum\limits_{1\leq k \leq T}\sum\limits_{j\geq0}A_{m,j}k^j(n-k)^j=\sum\limits_{0\leq k \leq m}(-1)^{m-k}U_m(n,k)\cdot n^k,$$ where $T=1,2,3...$ and $m\geq0, \ m=\mathrm{const}$. The coefficient $A_{m,j}$ is generated by \begin{equation*}\label{gen_13} A_{m,j}:= \begin{cases} 0, & \mathrm{if } \ j<0 \ \mathrm{or } \ j>m \\ (2j+1)\binom{2j}{j} \sum_{d=2j+1}^{m} A_{m,d} \binom{d}{2j+1} \frac{(-1)^{d-1}}{d-j} B_{2d-2j}, & \mathrm{if } \ 0 \leq j < m \\ (2j+1)\binom{2j}{j}, & \mathrm{if } \ j=m \\ \end{cases} \end{equation*} Derivation of coefficients $A_{m,j}$ is discussed in mathoverflow.net/questions/297900. In particular, the right part of (1.3) returns odd power $2m+1$ of $T\in\mathbb{N}$ when $n=T$ \begin{equation*} T^{2m+1}=\sum\limits_{0\leq k \leq m}(-1)^{m-k}U_m(n,k)\cdot T^k \end{equation*} We denote the part $\sum\nolimits_{j\geq0}A_{m,j}k^j(n-k)^j$ of the left part of equation (1.3) as $$\label{f4} D_m(n,k)=\sum\limits_{j\geq0}A_{m,j}k^j(n-k)^j$$ Therefore, below we attach a tables containing the polynomials $\sum\nolimits_{0\leq k \leq m}(-1)^{m-k}U_m(n,k)\cdot n^k$ for various $t$ and $m$, that is shown in each table's caption. The main question is:

Question 1. Is there a recurrent that gives the coefficients $U_m(n,k)$ otherwise then by the identity $$\label{f3_1} \sum\limits_{1\leq k \leq T}\sum\limits_{j\geq0}A_{m,j}k^j(n-k)^j=\sum\limits_{0\leq k \leq m}(-1)^{m-k}U_m(n,k)\cdot n^k,$$ i.e is there any function $F(n,m)$ such that $F(m,n)=U_m(n,k)$? The following arrays could be generated using Mathematica code Um(n,k)_coefficients2.txt. Here we begin to show our arrays of polynomials for $m=1,2,3,4$ and $T=1,2,...,10$

Array for $m=1$ \begin{eqnarray*} % \nonumber to remove numbering (before each equation) T=1 &:& -5 + 6 n \\ T=2 &:& -28 + 18 n \\ T=3 &:& -81 + 36 n \\ T=4 &:& -176 + 60 n \\ T=5 &:& -325 + 90 n \\ T=6 &:& -540 + 126 n \\ T=7 &:& -833 + 168 n \\ T=8 &:& -1216 + 216 n \\ T=9 &:& -1701 + 270 n \\ T=10 &:& -2300 + 330 n \end{eqnarray*} Coefficients of above polynomials are terms of sequences A028896 and A275709.

Array for $m=2$ \begin{eqnarray*} % \nonumber to remove numbering (before each equation) T=1 &:& 31 - 60 n + 30 n^2 \\ T=2 &:& 512 - 540 n + 150 n^2 \\ T=3 &:& 2943 - 2160 n + 420 n^2 \\ T=4 &:& 10624 - 6000 n + 900 n^2 \\ T=5 &:& 29375 - 13500 n + 1650 n^2 \\ T=6 &:& 68256 - 26460 n + 2730 n^2 \\ T=7 &:& 140287 - 47040 n + 4200 n^2 \\ T=8 &:& 263168 - 77760 n + 6120 n^2 \\ T=9 &:& 459999 - 121500 n + 8550 n^2 \\ T=10 &:& 760000 - 181500 n + 11550 n^2 \end{eqnarray*}

Array for $m=3$ \begin{eqnarray*} % \nonumber to remove numbering (before each equation) T=1 &:& -125 + 406 n - 420 n^2 + 140 n^3\\ T=2 &:& -9028 + 13818 n - 7140 n^2 + 1260 n^3\\ T=3 &:& -110961 + 115836 n - 41160 n^2 + 5040 n^3\\ T=4 &:& -684176 + 545860 n - 148680 n^2 + 14000 n^3\\ T=5 &:& -2871325 + 1858290 n - 411180 n^2 + 31500 n^3\\ T=6 &:& -9402660 + 5124126 n - 955500 n^2 + 61740 n^3\\ T=7 &:& -25872833 + 12182968 n - 1963920 n^2 + 109760 n^3\\ T=8 &:& -62572096 + 25945416 n - 3684240 n^2 + 181440 n^3\\ T=9 &:& -136972701 + 50745870 n - 6439860 n^2 + 283500 n^3\\ T=10 &:& -276971300 + 92745730 n - 10639860 n^2 + 423500 n^3 \end{eqnarray*}

Array for $m=4$ \begin{eqnarray*} % \nonumber to remove numbering (before each equation) T=1 &:& 751 - 2640 n + 3780 n^2 - 2520 n^3 + 630 n^4\\ T=2 &:& 162512 - 325440 n + 245700 n^2 - 83160 n^3 + 10710 n^4\\ T=3 &:& 4297023 - 5837040 n + 3001320 n^2 - 695520 n^3 + 61740 n^4\\ T=4 &:& 45586624 - 47125200 n + 18484200 n^2 - 3276000 n^3 + 223020 n^4\\ T=5 &:& 291683375 - 244000800 n + 77546700 n^2 - 11151000 n^3 + 616770 n^4\\ T=6 &:& 1349845776 - 949440240 n + 253906380 n^2 - 30746520 n^3 + 1433250 n^4\\ T=7 &:& 4981676287 - 3024769440 n + 698619600 n^2 - 73100160 n^3 + 2945880 n^4\\ T=8 &:& 15551330048 - 8309593440 n + 1689523920 n^2 - 155675520 n^3 + 5526360 n^4\\ T=9 &:& 42670773999 - 20362676400 n + 3698370900 n^2 - 304479000 n^3 + 9659790 n^4\\ T=10 &:& 105670786000 - 45562677600 n + 7478370900 n^2 - 556479000 n^3 + 15959790 n^4 \end{eqnarray*} The PDF-analog of this question with extended data of $U_m(n,k)$ coefficients up to $T=40$ is available at this link.

relax a rectangular linear assignment problem

Mon, 07/02/2018 - 16:47

I wonder if there is any literature on the following problem

$\min_{X\in R^{m\times n}}\sum_{i,j} C_{i,j}X_{i,j}, s.t. \sum_{i}X_{i,j}=\sum_{j}X_{i,j}=1, X_{i,j}\geq 0$

The closest related problem might be Rectangular Linear Assignment Problem (RLAP), as RLAP further constrains $X_{i,j}$ to take only 0 or 1 (refer to http://www.optimization-online.org/DB_FILE/2008/10/2115.pdf). I understand that the proposed problem is a relax version of the RLAP. But my intuition is that the optimum for the relax problem should occur at "vertex". So, do the relaxed RLAP share the same optimum as RLAP?