Math Overflow Recent Questions

Subscribe to Math Overflow Recent Questions feed
most recent 30 from 2019-02-21T17:01:12Z

What optimization problems have solutions with few nonzeros?

Sat, 02/02/2019 - 15:24

Consider the following optimization problem, with $n$ variables and $m$ linear constraints: \begin{align} \text{maximize} && c_1 x_1 + \cdots + c_n x_n & \\ \text{subject to} && a_{11} x_1 + \cdots + a_{1n} x_n &= b_1 \\ && a_{21} x_1 + \cdots + a_{2n} x_n &= b_2 \\ &&... \\ && a_{m1} x_1 + \cdots + a_{mn} x_n &= b_m \\ && x_1 \ldots,x_n &\geq 0 \end{align} It is known that, if the problem has an optimal solution, then it has an optimal solution in which at most $m$ variables are non-zero; it is called an optimal basic feasible solution.

This can be easily visualized in two dimensions ($n=2$). For example here:

the solid black segment represents the single constraint ($m=1$), and the two dotted lines represent two different objectives; it is clearly visible that each objective is both maximized and minimized at one of the endpoints of the segments, which has at most one nonzero.

This nice property holds, in some cases, even if the constraints are not linear. For example, in the above case, if we raise the variables in the constraint to a power smaller than 1, then the linear objectives are still maximized (but not minimized) at the endpoints:

MY QUESTION IS: is this true in general? I.e., is it true that, if we replace each term $a_{ij}x_i$ in the above program with a term $f_{ij}(x_i)$, where $f_{ij}$ is a concave function (such as $f_{ij}(x_i) = (x_i)^{0.7}$), then there is still an optimal solution with at most $m$ nonzeros?

Note: posted previously on math.SE with no replies.

Modulo arithmetic in $\mathbb{Z}$

Sat, 02/02/2019 - 15:18

Suppose $a\ b\ c \in \mathbb{Z}$ and $0 < c * b < a$.

Show that $((a / c)\ mod\ b) * c + (a / c + b * (a\ mod\ c)) / b = a$

I have tried the following:
$(a / c + b * (a\ mod\ c)) / b = (a / c / b + (a\ mod\ c))$

So with a bit more arithmetic:
$a\ mod\ c + c * ((a / c)\ mod\ b) + a / c / b = a$

Which is the same as:
$a\ mod\ c + c * ((a / c)\ mod\ (c * b)) + a / c / b = a$

Here is where I thought I could be clever; using the definition of mod:
$a\ mod\ c + c * (a / c) - c * b * (c * (a / c) / (c * b)) + a / c / b = a$

To replace the left summand with $a$, which I thought was going to do the trick:
$a - c * b * (c * (a / c) / (c * b)) + a / c / b = a$

And of course:
$- c * b * (c * (a / c) / (c * b)) + a / c / b = 0$

Now, I am not sure if this is even true... But I can't reduce $c * (a / c)$ to $a$ because I don't know if $c | a$. Same for the other division (by $c * b$). If I could, it would be naturally unprovable because I would be left with $a / c / b = a$, which I can't show from what I have.

Am I trying to prove an unprovable theorem here or am I missing something?

Piltz Divisor Problem

Sat, 02/02/2019 - 14:36

Let $\tau_k(n)$ count the number of ways of representing $n$ as the product of $k$ natural numbers. It is known that:

$$D_k(x) = \sum_{n \leq x} \tau_k(n) = xP_k(\log x) + O(x ^{1 - \frac{1}{k-1}}(\log x)^{k-2}), \; \forall k \geq 2$$

Where $P_k$ is a polynomial of degree $k-1$ with leading coefficient $\frac{1}{(k-1)!}$

I am asked to prove this. We may assume the base case as it is a well known result.

The assuming the result for all $l \leq k$:

$$D_k(x) = \sum_{mn \leq x} \tau_{k-1}(n) = \sum_{n\leq x}\lfloor{\frac{x}{n}}\rfloor\tau_{k-1}(n)$$

$$= \sum_{n \leq x}(\frac{x}{n} + O(1))\tau_{k-1}(n) = x\sum_{n \leq x} \frac{\tau_{k-1}(n)}{n} + O(\sum_{n\leq x}\tau_{k-1}(n))$$

Using Abel's Summation formula, we may see that:

$$\sum_{n \leq x} \frac{\tau_{k-1}(n)}{n} = P_k(\log x) + O(x^{\frac{-1}{k-1}}(\log x)^{k-3})$$


$$D_k(x) = xP_k(\log x) + O(x^{1 - \frac{1}{k-1}}(\log x)^{k-3}) + O(\sum_{n \leq x}\tau_{k-1}(n))$$

Using the induction hypothesis:

$$O(\sum_{n \leq x}\tau_{k-1}(n)) = O(xP_{k-1}(\log x) + O(x^{1 - \frac{1}{k-1}}(\log x)^{k-3}))$$

$$= O(x(\log x)^{k-2}) + O(x^{1 - \frac{1}{k-1}}(\log x)^{k-3})) = O(x(\log x)^{k-2})$$

Thus we get:

$$D_k(x) = xP_k(\log x) + O(x^{1- \frac{1}{k-1}}(\log x)^{k-3}) + O(x(\log x)^{k-2})$$

$$= xP_k(\log x)+O(x(\log x)^{k-2})$$

Howwever, this error term is too large. How can I go about reducing it?

An inequality between perimeters

Sat, 02/02/2019 - 14:30

Let $E,F \subset \mathbb R^n$ be two sets of finite perimeter. Assume that the intersection of $E$ and $F$ is Lebesgue negligible, $|E \cap F| = 0$.

Is it true that

$$ P(E) + P(F) - P(E \cup F) \stackrel{?}{=} 2 \mathcal H^{n-1} (\partial^* E \cap \partial^*F). $$

The $\partial^*$ denotes the reduced boundary operator. I have the strong suspect that equality holds but I fail to have a formal proof. Btw, in the case the equality is true, does it have a name? Was it observed before, so that I can quote some reference?

Finding the coefficients of a quadratic equation giving one point and open interval

Sat, 02/02/2019 - 14:03

Here is my question

The quadratic function f is negative only on the open interval (−2, 1/4 ) and its graph passes through the point (−1, −5). Determine the coefficients of f and sketch its graph.

please explain how you got your answer and thank you.

Dichotomy of Riemannian holonomy groups

Sat, 02/02/2019 - 13:34

Berger's list of irreducible Riemannian holonomies contains two sorts of holonomy groups. The first ($SO(n)$, $U(m)$ and $Sp(k)\cdot Sp(1)$) consists of holonomy groups of rank one symmetric spaces (only $\mathrm{Spin}(9)$ is missing). These symmetric spaces are witnesses of the fact that these holonomy groups have examples that are not Ricci-flat.

The other holonomies ($SU(m)$, $Sp(k)$, $\mathrm{Spin}(7)$ and $G_2$) all admit parallel spinors (either locally or assuming that the underlying manifolds are simply connected) and are therefore Ricci flat by a theorem of Hitchin and Friedrich.

Is there a conceptual explanation for this dichotomy (better than: "just look at Berger's list")? For example, can one prove directly that an irreducible Riemannian manifold that does not admit (local) parallel spinors must have the holonomy group of a symmetric space?

Singular integral operators and PDEs

Sat, 02/02/2019 - 13:28

What is the relation between the notion of singular integral operators and partial differential equations? I know, for example, that there is a relation between the Cauchy transform (Riesz transforms in higher dimension) and the laplacian, but it seems that this connection is much deeper. I want to know much more about that (I have a bite experince in harmonic analysis but not in PDE). Any suggested refrences (survey papers, etc) are welcome.

Inducing linear connections via functors

Sat, 02/02/2019 - 13:24

Let $M$ be a smooth manifold and let $\pi:E\rightarrow M$ be a real vector bundle over it. Let $\nabla$ be a linear (Koszul) connection on $E$ (here in this question I am using covariant derivatives, but if it is more convenient, answers may treat linear connections as horizontal distributions on $E$).

It is a well known fact that then there are naturally induced linear connections on "related" vector bundles, such as $E^\ast,\ \bigotimes^kE$, etc.

There is of course a systematic way of describing these induced connections from the point of view of principal fiber bundles, however that approach is only of marginal interest for the purposes of this question.

If $\mathbb A$ is an indexing set, $(U_\alpha)_{\alpha\in\mathbb A}$ is an open cover of $M$, and $(\varphi_{\alpha\beta})$ is a cocycle of transition functions (with $\varphi_{\alpha\beta}:U_{\alpha\beta}=U_\alpha\cap U_\beta\rightarrow\text{GL}(V)$, $V$ is a finite dim. real vector space), then a unique vector bundle may be constructed from these data, which is denoted as $\text{Vb}(\varphi_{\alpha\beta})$. This construction is nicely outlined in for example Natural Operations in Differential Geometry by Michor, Kolár, Slovák.

The general way of constructing "related" vector bundles is also stated here. Let $\text{Vec}_\mathbb R$ denote the category of finite dimensional real vector spaces, and let $\mathcal F:\text{Vec}_\mathbb R\rightarrow\text{Vec}_\mathbb R$ be a functor from this category to itself. If for any $A\in\text{Hom}(V,W)$, the assignment $A\mapsto\mathcal F(A)\in\text{Hom}(\mathcal F(V),\mathcal F(W))$ (or $\text{Hom}(\mathcal F(W),\mathcal F(V))$ in case of a contravariant functor) is a smooth map, then we call $\mathcal F$ a smooth functor.

Now, if $\mathcal F$ is a smooth covariant functor, then we define a new vector bundle $\mathcal F(E)$ by $\text{Vb}(\mathcal F(\varphi_{\alpha\beta}))$ and if it is a contravariant functor then by $\text{Vb}(\mathcal F(\varphi_{\alpha\beta}^{-1}))$. This is extended in an obvious way to multiple vector bundles and multifunctors.

However from this it seems natural to me that given

  • a vector bundle $E\rightarrow M$;

  • a linear connection $\nabla\equiv\nabla(E)$;

  • a smooth functor (covariant or contravariant) $\mathcal F$

there should be an induced linear connection $\nabla(\mathcal F(E))$ on $\mathcal F(E)$ by this functor.

Question 1: Assuming this is true, how does this functor exactly induce this connection on the vector bundle $\mathcal F(E)$?

Question 2: How is this process related to the usual way of inducing connections on vector bundles associated to principal bundles? Considering the fact that for functorial vector space operations like taking duals, direct sums, tensor products etc. there are corresponding operations on representations, I assume if we are given a principal bundle $P\rightarrow M$ with structure group $G$, and a representation $\rho:G\rightarrow\text{GL}(V)$, then there is a corresponding representation $\mathcal F(\rho)=\mathcal F\circ \rho$ ($\mathcal F$ is covariant) or $\mathcal F(\rho)=\mathcal F\circ\rho^{-1}$ ($\mathcal F$ is contravariant), and the induced connections for associated vector bundles induced by these representations are the connections I am looking for, but I would be happy if I could get some links to some papers or textbooks that discuss this approach in greater detail.

Complex manifolds whose Hodge numbers are rigid under small deformations

Sat, 02/02/2019 - 13:20

Let $M$ be a closed complex manifold. Assume that for any family of closed complex manifolds over the unit disk containg $M$ as the central fiber, there exists a sufficiently small neighbourhood of 0 such that $h^{p, q}(M_t)=h^{p, q}(M)$ for all $t$ in the neighbourhood. What restrictions does this give on the geometry of $M$?

We know for a fact that this does impose some non-trivial restrictions (as there exist closed complex manifolds for which arbitrarily small deformations have different Hodge numbers). The class of the manifolds under consideration should be different from the class of locally rigid complex manifolds as well (since complex curves are not locally rigid but Hodge numbers are determined by the underlying topological space). It would also be nice if someone could point out a name for this class of complex manifolds (if they have been studied before).

Local behaviour of the moduli space of almost complex structures (up to conjugation)

Sat, 02/02/2019 - 12:58

Assume $M$ is a closed smooth manifold of real dimension $\geq 4$. What is known about the geometry of the "space" of almost complex structures up to conjugation by diffeomorphisms? There are quotes because I am not sure what is the natural topology to consider on that set. Is it locally finite-dimensional? Is there a cohomological interpretation of the tangent space at a point $[J]$ (corresponding to an a.c.s. $J$)?

Noteworthy, but not so famous conjectures proved recent years

Sat, 02/02/2019 - 12:43

Conjectures play important role in development of mathematics. Mathoverflow gives an interaction platform for mathematicians from various fields, while in general it is not always easy to get in touch with what happens in the other fields.

Question What are the conjectures in your field proved recent years, which are noteworthy, but not so famous outside your field ?

Answering the question you are welcome to give some comment for outsideres of your field which would help to appreciate the result.

Asking the question I keep in mind by "recent years" something like dozen years before now, by "conjecture" something which was known as an open problem for something like at least dozen years before it was proved and I would say the result for which Fields medal was awarded like proof of fundamental lemma would not fit "not so famous", but on the other hand these might not be considered as strict criterias, and let us "assume a good will" of the answerer.

simultaneous hitting time

Sat, 02/02/2019 - 11:18

Given probability space $(\Omega, P)$, state space $S$, subset $B \subset S$, two independent stochastic processes $(X_n)_{n \ge 1}, (X'_n)_{n \ge 1}$ with $ X\overset{d}{=}X'$.

Let $\tau= \inf \{n, X_n \in B \}$, assume $P(\tau>n) \le \frac{1}{n^2}$.

Let $\tau'=\inf\{n, (X_n, X_n')\in B\times B\}$,


can $P\times P(\tau'>n)$ be controlled by $P(\tau>n)$ ?

Representing simplicial homotopy classes cubically?

Sat, 02/02/2019 - 10:08

Let $(X,x_0)$ be a pointed simplicial set. Assume if you like that $X$ is the nerve of a category but do not assume that $X$ is a Kan complex.

Because $Ex^\infty X$ is a Kan complex, every homotopy class $\alpha \in \pi_n(X,x_0)$ may be represented by a map $sd^k \Delta[n] \to X$ such that the restriction $sd^k \partial \Delta[n] \to X$ is constant at $x_0$. I'm wondering about different "normal forms" for homotopy classes.

For instance, consider subidivided cubes. In dimension 2, I think they should look like this:

$\require{AMScd} D^2_0 = \begin{CD} \bullet \end{CD} \\ D^2_1 = \begin{CD} \bullet @>>> \bullet @<<< \bullet \\ @VVV @VVV @VVV \\ \bullet @>>> \bullet @<<< \bullet \\ @AAA @AAA @AAA \\ \bullet @>>> \bullet @<<< \bullet \\ \end{CD} \\ D^2_2 = \begin{CD} \bullet @>>> \bullet @<<< \bullet @>>> \bullet @<<< \bullet\\ @VVV @VVV @VVV @VVV @VVV \\ \bullet @>>> \bullet @<<< \bullet @>>> \bullet @<<< \bullet\\ @AAA @AAA @AAA @AAA @AAA \\ \bullet @>>> \bullet @<<< \bullet @>>> \bullet @<<< \bullet\\ @VVV @VVV @VVV @VVV @VVV \\ \bullet @>>> \bullet @<<< \bullet @>>> \bullet @<<< \bullet\\ @AAA @AAA @AAA @AAA @AAA \\ \bullet @>>> \bullet @<<< \bullet @>>> \bullet @<<< \bullet \end{CD} \\ D^2_3 = \dots $


  1. Can every $\alpha \in \pi_n(X, x_0)$ be represented by a map $D^n_k \to X$ sending the boundary to the constant at $x_0$?
  2. If not, is there a better definition of subdivided cubes for which the answer to (1) becomes "yes"?

It's nice that with the above definition, $D^n_{k+1}$ can be obtained by gluing together a bunch of copies of $D^n_k$ in an easy way. But perhaps this is too good to be true.

A trivial observation is that for $n=1$ the above cubical subdivision is basically the same as barycentric subdivision and the answer to (1) comes out as "yes".

Upper and lower bounds on the number of certain subsets of the power set

Sat, 02/02/2019 - 09:55

Let $A$ be a set with $n$ elements. Call a subset $C$ of the power set of $A$ "good" if

  • Each element of $C$ has at least three elements.

  • If $P, Q\in C$ and $P\cap Q$ has more than one element, then $P=Q$.

I've been interested in finding good upper and lower bounds of the number of good collections, but I haven't made any headway. Does anyone know of any?

Proving two inequalities involving the gamma and digamma functions

Sat, 02/02/2019 - 09:02

I'm having trouble proving the following inequality:

$$\forall p>1 \quad \forall m\geq 0 \quad \dfrac{m^2\Gamma(\dfrac{2m}{p})\Gamma(\dfrac{2m}{q})}{\Gamma(\dfrac{2m+2}{p})\Gamma(\dfrac{2m+2}{q})}\geq\dfrac{1}{4}p^2(p-1)^{\frac{2}{p}-2},$$ where as usual $q=\dfrac{p}{p-1}$. In fact, it seems clear from Mathematica that for a fixed $p$, the LHS is a decreasing function of $m$ (strictly unless $p=2$, in which case it's constant). The RHS can be seen to be the limit as $m\to \infty$. I actually only care about integer $m\geq 0$, but I don't find that helpful.

I have tried both a direct approach (three known inequalities that are nice enough to apply here, but lead to wrong inequalities) and working with the derivative, which naturally involves instances of the digamma function. Proving that the LHS is decreasing is equivalent to the following inequality: $$\forall p>1 \quad \forall m\geq 0 \quad \dfrac{1}{m}+\dfrac{1}{p}(\psi(\dfrac{2m}{p})-\psi(\dfrac{2m+2}{p}))+\dfrac{1}{q}(\psi(\dfrac{2m}{q})-\psi(\dfrac{2m+2}{q}))\leq0,$$ which again seems to be correct (if you're wondering, the limit as $m\to 0$ is negative for $p\neq2$). Much like before, I tried using two inequalities (for the digamma function), as well as the series representation. They seemed promising at first, but the inequalities gave me positive upper bounds, while the series converges too slowly to be useful (I suspect that any partial sum is positive for large enough $m$).

Any advice would be much appreciated. I'll be glad to explain more about the inequalities I've tried if requested.

Is there a natural transformation from Lists to Domains of Lists

Sat, 02/02/2019 - 08:47

The list domain, $(L, \mu_L, \eta_L)$, on $Set$, takes a set to its set of lists, with $\mu_L : L \cdot L \rightarrow L$ being concatenation of lists. Given a set of lists, there is a natural way to define a domain (dcpo) of lists, by partial initial fragment $l_1 \le l_2 $ if $ l_2 = Concat(l_1, l^{′}_{2})$. I am wondering if this means there is a functor $D$ that takes a set of lists on a set $X$ and gives back the set of domains on that set of lists. Further, is there a natural transformation from $L$ to $D$. Further, is this a monad map, making a monad $(D, \mu_D, \eta_D)$.

I submitted this over at math stack, but got no response.

symplectic sum of two copies of $Bl_{p}(\mathbb{CP}^{2})$

Sat, 02/02/2019 - 08:35

Let $M^{4}= \mathbb{P}(\mathcal{O} \oplus \mathcal{O}(1))$ and $\omega$ the symplectic form on $M^{4}$ given by the anticanonical polarisation.

Suppose we form a symplectic (Gompf) sum of two copies of $(M^{4},\omega)$ along a fibre of the $\mathbb{P}^{1}$-bundle (where the orientation reversing identification of the normal bundles is the obvious one i.e. we just pick an orientation reversing isomorphism of $\mathbb{R}^{2}$ and let the isomorphism of normal bundles be equal to this pointwise).

Question: Does the resulting symplectic $4$-manifold have a compatible Kahler structure?

Real rank 0 implies stable rank 1 on $C^\ast$-algebras?

Sat, 02/02/2019 - 05:27

A $C^\ast$ algebra has defined stable rank ( and real rank (, which are two different non-commutative versions of Lebesgue covering dimension.

In particular an algebra $A$ has

  • Stable rank 1 if and only if every element of $A$ can be approximated by invertibles.
  • Real rank 0 if and only if every self-adjoint element of $A$ can be approximated by self-adjoint invertibles.

It's known that $rr(A)\leq 2sr(A)-1$ (see second paper). Is there any example of a $C^\ast$-algebra with real rank $0$ and stable rank $>1$? If so, is there a simple one?

$P$ is projective if and only if $P\otimes N\cong Hom(Hom(P,R),N)$

Sat, 02/02/2019 - 00:50

Let $R$ be a commutative Noetherian ring and $P$ be finitely generated $R$-module.

How to prove the following.

$P$ is projective if and only if $P\otimes N\cong Hom(Hom(P,R),N)$ for all finitely generated $R$-modules $N$.

Poset dimension and width (Dilworth's theorem)

Fri, 02/01/2019 - 22:57

For a given poset $P$, let $\mathrm{dim}(P)$ denote the least cardinal $\kappa$ such that there exists a $\kappa$-sized collection of linear extensions of $P$, say $\mathcal{L}$, such that $\leq_P = \bigcap_{L\in \mathcal{L}}\leq_L$. Let $\mathrm{width}(P)$ denote the least cardinal $\lambda$ such that every antichain $A\subset P$ has size $<\lambda$.

Note that the definition of width here is slightly different from the usual definition seen in combinatorics textbooks but we do this in the set-theoretic convention to deal with the possibility that there is no antichain with maximum cardinality.

Dilworth ( proved that if $\mathrm{width}(P)$ is finite, then $\mathrm{dim}(P)<\mathrm{width}(P)$. The proof goes through the fact that if the width of $P$ is $k$, then $P$ can be decomposed into a union of $<k$ many chains. This fact is not true for $k\geq \aleph_0$. However, the counter-example (Perles' example has dimension 2 so it satisfies $\mathrm{dim}(P)<\mathrm{width}(P)$. Are there examples violating $\mathrm{dim}(P)<\mathrm{width}(P)$?

EDIT: Suggested by bof, the width is better defined as the supremum of the sizes of antichains. So with the new definition, Dilworth's theorem states $\mathrm{dim}(P)\leq \mathrm{width}(P)$ for $P$ of finite width and my question will be modified to whether this is true in general.