Recent MathOverflow Questions

Maximizing a non-convex quadratic form over a convex set

Math Overflow Recent Questions - Sun, 06/11/2017 - 07:49

Say that we have a compact set $C \subset \mathbb{C}^d$. I will assume this set to be balanced (i.e. $c \in C \Rightarrow \omega c \in C \;\forall \omega : |\omega| = 1$). Let $\operatorname{Conv}(C)$ denote the convex hull of $C$.

It is not difficult to see that for a positive semidefinite Hermitian matrix $P$, the following holds:

$$\max_{c \in \operatorname{Conv}(C)} c^* P c = \max_{c \in C} c^* P c \tag{1}$$

which follows because the quadratic form $x^* P x$ is convex in $x$ for a positive semidefinite $P$. I am now trying to relax the requirement of positive semidefiniteness of $P$, while retaining property $(1)$.

In particular, let's say that we know the following: $P$ is Hermitian and $c^* P c \geq 0 \;\forall c \in C$. What are the constraints on $C$ (or further constraints on $P$?) such that the property $(1)$ still holds, given that $P$ is no longer positive semidefinite?

Optimization ordinal regression with constraints

Math Overflow Recent Questions - Sun, 06/11/2017 - 07:18

everyone! I have a question about optimization for logistic ordinal regression ! Given the dataset $(x_i, y_i)^n$, Here $y_i\in \{1,2,\dots, k\}$, its negative log likelihood function is shown as follows:


$$s.t. \theta_1< \theta_2< \dots<\theta_k $$ where $\phi(z)$ is the logistic function defined as $\phi(t)=1/(1+exp(-t))$ The constraints make me feel bad!

I want to know which optimization method can handle this problem. And, the detailed derivation process would help me a lot!

The gradient of the loss function can be found from [link]:

Is primality essential in Varshamov's bound?

Math Overflow Recent Questions - Sun, 06/11/2017 - 06:32

Let $v_q(n,r)=\sum_{i=0}^r \binom{n}i (q-1)^i$ denote a number of points in a ball of radius $r$ in the Hamming metric on the cube $\Sigma^n$, where $|\Sigma|=q$. What is the maximal number of points in $\Sigma^n$ with mutual distances at least $d$ (later: $d$-distant point sets)? Gilbert's bound says that we may find $M$ such points if $(M-1)\cdot v_q(n,d-1)< q^n$: add points one by one, while we have less than $M$ points, the $(d-1)$-balls centered at them do not cover $\Sigma^n$ and we may add another point. If $q$ is a power of prime, Varshamov's bound improves the previous result by claiming that we may find $q^k$ $d$-distant points whenever $q^{k-1}v_q(n,d-1)<q^n$. For the proof, we identify $\Sigma$ with a finite field and consider the maximal subspace $X$ of $\Sigma^n$ into which all points are $d$-distant. If $\dim X\geqslant k$, we are done, else there exist a point $v$ not covered by $(d-1)$-balls centered at elements of $X$, and the span of $X$ and $v$ is larger $d$-distant subspace.

My question is: is Varshamov's bound true if we do not require that $q$ is a prime power (say, for $q=6$)? This often happens and always does astonish me when arithmetical properties like being prime powers are crucial for purely combinatorial or topological claims, and I wonder what is the situation in this particular case.

Concavity of the trace of a matrix power

Math Overflow Recent Questions - Sun, 06/11/2017 - 06:16

Let $B$ be an $n\times n$ matrix, and define $f$ to be the function that maps positive semidefinite (PSD) $n\times n$ matrices $A$ to real numbers by

$$ f(A) = \mathrm{trace}( (B^*A^2B)^{1/3}). $$

In other words, $f$ maps $A$ to the sum of $1/3$-powers of the eigenvalues of the PSD matrix $B^*A^2B$.

Is the function $f$ concave over the PSD cone? I.e. is it true that for any two PSD matrices $X$ and $Y$, $f((X + Y)/2) \ge f(X)/2 + f(Y)/2$?

A more general question is whether the function $f(A) = \mathrm{trace}( (B^*A^2B)^{p})$ is concave over the PSD cone for $0< p < 1/2$.

Carlen and Lieb have some closely related results, but I could not find the particular combination of matrix powers in their paper or in other related work on trace inequalities.

Two correlated bivariate functions

Math Overflow Recent Questions - Sun, 06/11/2017 - 06:09

I have two functions,


$f(x,y)=\frac{1-x}{2} log\frac{2(1-x)}{2-x-y} +\frac{x}{2} log\frac{2x}{x+y} +\frac{1-y}{2} log\frac{2(1-y)}{2-x-y} +\frac{y}{2} log\frac{2y}{x+y}$


What is the monotonic function $h(z)$ such that $h(g)=f$ ?

$h$ seems to exist since from numerical simulations $f$ and $g$ seem perfectly $correlated$ , i.e.,:

\begin{array}{l} {f(x_{1} ,y_{1} )>f(x_{2} ,y_{2} )\Rightarrow g(x_{1} ,y_{1} )>g(x_{2} ,y_{2} )} \\ {f(x_{1} ,y_{1} )<f(x_{2} ,y_{2} )\Rightarrow g(x_{1} ,y_{1} )<g(x_{2} ,y_{2} )} \end{array}

Weak Hall's marriage lemma

Math Overflow Recent Questions - Sun, 06/11/2017 - 05:40

Let $G=(S,T,E)$ be a bipartite graph, $|S|=|T|$. Then the following are equivalent:

1) there exist a perfect matching in $G$;

2) there exist non-negative weights on edges such that the sum of weights of edges incident to each vertex equals 1 (in other words, there exists a Markov process which maps a uniform measure on $S$ to a uniform measure on $T$);

3) for any subset $S_1\subset S$, $S_1$ has at least $|S_1|$ neighbours in $T$.

Obviously, 1) implies 2) and 2) implies 3). My question is: does there exist a simple proof that 3) implies 2), avoiding proving 1)? The one I have in mind (with Hahn-Banach theorem, or linear programming duality if you prefer) is not any simpler.

Find solution to PDE

Math Overflow Recent Questions - Sun, 06/11/2017 - 05:05

Let $f$ be a real function on ${{\mathbb{R}}^{n}}\times \left[ 0,\infty \right)$ with compact support, and it is a class of ${{C}^{2}}$ with respect to $x\in {{\mathbb{R}}^{n}}$ , and a class of ${{C}^{1}}$ respect to $t\in \left[ 0,\infty \right)$, Let $g\in C\left( {{\mathbb{R}}^{n}} \right)\times {{L}^{\infty }}\left( {{\mathbb{R}}^{n}} \right)$and $c\in \mathbb{R}$. Find the solution to the problem: $\left\{ \begin{align} & {{u}_{t}}-\Delta u+cu=f;\text{ in }{{\mathbb{R}}^{n}}\times \left( 0,\infty \right) \\ & \text{ }u=g;\text{ in }{{\mathbb{R}}^{n}}\times \left\{ t=0 \right\} \\ \end{align} \right.$

Im not sure how to approach to this problem and I am having difficulty in solving it, so I would appreciate any help.

Closed form for $\int_0^T e^{-x}\frac{I_n(\alpha x)}{x}dx$

Math Overflow Recent Questions - Sun, 06/11/2017 - 04:54

I try to solve $\int_0^T e^{-x}\frac{I_n(\alpha x)}{x}dx$ where $I_n(x)$ is the modified Bessel function of the first kind and $0<\alpha<1$.

My first approach was to turn this integral into an infinite sum to fit a hypergeometric series:

  • Using the infinite series representation of the Bessel function, I got incomplete gamma functions in the sum, which does not sound promising.
  • The multiplication theorem yields an infinite series of integrals where we get rid of the $\alpha$: $$\int_0^T e^{-x}\frac{I_n(\alpha x)}{x}dx=\alpha^n\sum_{m=0}^{\infty}\frac {\big(\frac {\alpha ^{2}-1}{2}\big)^m}{m!}\int_0^T e^{-x}x^{m-1}I_{n+m}(x)dx$$

According to a table of integrals, the new integrals are: \begin{align} \int_0^T e^{-x}x^{m-1}I_{n+m}(x)dx&=\Big(\frac{T}{2}\Big)^{n+m}\frac{\Gamma(2m+n)}{\Gamma(m+n+1)\Gamma(2m+n+1)}\\ &\times{}_2F_2[\{m+n+\frac{1}{2},2m+n\};\{2m+2n,2m+n+1\};-2T] \end{align}

Expanding ${}_2F_2$ (let's call $k$ the summation index), we get a double infinite series which might fit the definition of a hypergeometric function of 2 variables. However, I get several Pochhammer symbols with coupled summations indices like this: $\frac{(n)_{2m+k}}{(n+1)_{2m+k}(2n)_{2m+k}}$ which does not fit any hypergeometric function definition.

Another approach could be to get inspiration from the limit $T\rightarrow \infty$ which is the Laplace transform of $\frac{I_n(x)}{x}$ (up to a constant) and it has a closed form (according to a table): $$\int_0^\infty e^{-x}\frac{I_n(\alpha x)}{x}dx=\frac{\big(\frac{\alpha}{1+\sqrt{1-\alpha^2}}\big)^n}{n}$$

However, I don't find any reference on the way to compute this.

Do you have any suggestion about how to compute it?

Trying to prove one of C.Taubes' theorems gauge-theory-freely

Math Overflow Recent Questions - Sun, 06/11/2017 - 04:16

One of C.Taubes' theorems says that for a symplectic 4-manifold with $b_2^+>1$, $\mathrm{Gr}(e)=0$ if $C_1(K).e-e.e\neq0$. This theorem is proved using Seiberg-Witten theory. And my question is: can one prove this gauge-theory-freely?

Simple Trigonometry [on hold]

Math Overflow Recent Questions - Sun, 06/11/2017 - 04:07

In the attached image I would like to relate theta A with theta E and theta S with the knowns being X, Y(the vertical distance between the centre of the circle and X), LH, LM, and the radius of the circle. I think a simple cosine rule of a triangle can relate these. Please help.


Formula for the Frobenius-Schur indicator of a finite group?

Math Overflow Recent Questions - Sun, 06/11/2017 - 03:59

Let $G$ be a finite group and let $k$ be an algebraically closed field of characteristic $p \neq 2$.

Let $V$ be a finite-dimensional irreducible $kG$-module. If $V \cong V^*$, then $V$ admits a nonzero $G$-invariant bilinear form $(-,-)$, unique up to scalar, such that $(-,-)$ is alternating or symmetric. Is there a formula or a general method to determine whether $(-,-)$ is going to be alternating or symmetric?

If $k = \mathbb{C}$, then the answer is yes: for a $\mathbb{C}G$-module $V$ with irreducible character $\chi$ we have the Frobenius-Schur indicator $$\nu_2(\chi) = \frac{1}{|G|} \sum_{g \in G} \chi(g^2)$$

which satisfies $\nu_2(\chi) \in \{-1, 0, 1\}$ and

  • $\nu_2(\chi) \neq 0$ iff $V \cong V^*$.
  • $\nu_2(\chi) = 1$ if there is a nonzero $G$-invariant orthogonal bilinear form on $V$.
  • $\nu_2(\chi) = -1$ if there is a nonzero $G$-invariant alternating bilinear form on $V$.

I think similar things should be true when $p \not \mid |G|$. What about in general? Is this an open problem?

How to prove that doubly regular tournaments are regular?

Math Overflow Recent Questions - Sun, 06/11/2017 - 03:58

A doubly regular tournament is a tournament such that every two vertices have $j$ common out-neighbours. How can we prove such a tournament is $2j+1$-regular?

$L^2$-Euler number

Math Overflow Recent Questions - Sun, 06/11/2017 - 02:34

Suppose $M$ is a closed manifold, whose universal covering $\tilde M$ is a complete.

Q: Can we say that $\chi(M)=L^2\chi(\tilde M)$, where $L^2\chi(\tilde M)$ denotes the alternative sum of the dimension of $L^2$-harmonic forms on $\tilde M$?

If $M$ is a closed symplectic manifold, does the above formula hold?

Orbifold line bundles

Math Overflow Recent Questions - Sat, 06/10/2017 - 23:36

I was going through the paper -, and I got this question. Let $Y$ be a connected smooth projective variety of dimension $n$ over $\mathbb{C}$. Let $G$ be a finite group acting faithfully on $Y$.

An orbifold line bundle on $Y$ is a line bundle $L$ on $Y$ together with a lift of action of $G$, which means that $G$ acts on the total space of $L$, and for any g ∈ $G$, the action of $g$ on $L$ is an isomorphism between $L$ and $\rho(g^{ −1} )^∗ L$.

But he further remarks that, A line bundle $L$ with the property that for any $g\in G$, the bundle $L$ is isomorphic to $\rho(g^{-1})^∗L$, need not have an orbifold structure. I am confused by this. I am trying to think of line bundles which satisfy this isomorphism property, but are not orbifold bundles.

Is this the right example? Consider the quotient $X=Y/G$, assume that it is non-singular. Let $D\subset X$ be the ramification divisor (say it is smooth). Consider $D'\subset Y$ the reduced pull back of $D$. Note that $p:D'\rightarrow D$ is a finite flat morphism, and $G$ acts on $D'$. The line bundle $O_Y(D')|_{D'}$ on $D'$ is isomorphic to $g^*O_Y(D')|_{D'}$, for all $g$. But is it an orbifold line bundle on $D'$?

I think not. For, given an orbifold line bundle $L$ on $D'$, consider the push forward $p_*L$ to $D$. Then we can define the subsheaf of $G$-invariants $(p_*L)^G$ as the image of the averaging operator on $p_*L$. The same paper says that $(p_*L)^G$ is a sub-line bundle of $p_*L$, and that $p^*(p_*L)^G\subset L$.

If $L=O_Y(D')|_{D'}$, then I cannot think of any line bundle $M$ on $D$ such that $p^*M\subset L$. Thus, $(p_*L)^G=0$, and that is clearly not a line bundle.

Does any of this make sense? Or am I completely wrong. Forgive me if I am completely off, this is a new area for me, and I need to apply it in my work. I am trying work out some examples to understand.

Geodesics on a parameterized curve [on hold]

Math Overflow Recent Questions - Sat, 06/10/2017 - 23:12

A parameterized curve $f(t):I\rightarrow M$ is a geodesic of M iff its acceleration is everywhere perpendicular to M, i.e. \begin{equation} \ddot{f}(t)=g(t)N({f}(t)) \end{equation}

Where $g(t):I\rightarrow \mathbb{R}$ and $N({f}(t))$ is unit normal vector–fields. Taking the scalar product of both sides of this equation with $N({f}(t))$ we find ...??


How can I find the function $g(t)$ where Find the value of the $g(t)$ and the offset by the equation leads

$f(t):I\rightarrow M$ is geodesic iff it satisfies the differential equation


I found this solution in one of the books but I did not understand how the derivation and the reasons enter image description here

the book here Geometrical Dynamics of Complex Systems: A Unified Modelling Approach

Can you help by stating the reasons

Thank you very much anyway

Wolff's article: Note on counterexamples in strong unique continuation problems

Math Overflow Recent Questions - Sat, 06/10/2017 - 22:30

I am reading Wolff's Note on counterexamples in strong unique continuation problems:

On Page 3, he wrote "Since $Z_n(\frac {x}{|x|})$" is a solution to a second order ODE, $\nabla Z_n$ vanishes only at 0. I got completely lost in this sentence.

For your reference, $Z_n(n\geq 2)$ is the homogeneous term of degree $n$ in the Taylor expansion of the function $\frac {1}{|x-e|^{d-2}}$ (the fundamental solution) at $0$, where $d\geq 3$ is the dimension and $e$ is an arbitrary unit vector in $\mathbb R^d$.

Let me explain my understanding of the question. Since the fundamental solution is harmonic away from $e$, $Z_n$ is also harmonic. So I am thinking of the following proposition:

A harmonic, homogeneous polynomial of degree $\geq 2$ centred at $0$ has a unique critical point, namely, the origin.

I cannot prove or disprove this statement.

Alternatively, in this paper, it is needed that $\nabla Z_n$ does not vanish in the annulus $\frac 1 4\leq |x|\leq 4$, so one can argue as follows. We know that the zero set of the gradient of a harmonic function inside a large ball is a discrete closed set. If there were a zero of $\nabla Z_n$ inside the annulus, then we can do a scaling (independent of $n$?), so after that, this zero will be away from the annulus. I am not sure if this is a good answer for this paper.

Distance function on a curve on a manifold

Math Overflow Recent Questions - Sat, 06/10/2017 - 09:14

Suppose that we are given a non-negative even function $b\in C^\infty[-1,1]$ satisfying $b(0)=0$, $\sqrt{b(x+y)}\le \sqrt{b(x)}+\sqrt{b(y)}$ for any $x,y\in[-\frac12,\frac12]$. Can we always find a 3-dimensional smooth Riemannian manifold $(M,g)$ and a smooth curve $a:[-\frac12,\frac12]\to M$ parametrized by arc length, such that the square of the distance function $d_g(a(t),a(s))^2=b(t-s)$?

For example, if we set $(M,g)=(\mathbb{R}^3,\|\cdot\|)$, can we find a smooth curve $a:[-\frac12,\frac12]\to \mathbb{R}^3$ parametrized by arc length, such that the square of the distance function $\|a(t)-a(s)\|^2=b(t-s)$?

What is the probability that you roll a dice with s sides for n times and t sides appeared once?

Math Overflow Recent Questions - Sat, 06/10/2017 - 04:28

You roll a dice with $s$ sides for $n$ times. What is the probability that $t$ sides appeared once?

Example with $s=2$, $n=3$: you roll a dice with 2 sides for 3 times. possible outcomes: '1' and '2'.

  • $p(t=0)$ is the probability that '1' appeared 0 times and '2' appeared 3 times + the probability that '2' appeared 0 times and '1' appeared 3 times, that is 1/4.
  • $p(t=1)$ is the probability that '1' appeared once and '2' appeared twice + the probability that '2' appeared once and '1' appeared twice, that is 3/4.
  • $p(t=2)=0$, because it is impossible that both '1' and '2' appear once.

If there is a formula for $p(s,n,t)$ it will be awesome, but also an algorithm is welcome.

Klee's trick --- more applications

Math Overflow Recent Questions - Fri, 06/09/2017 - 20:23

In his "Some topological properties..." (1955), Klee gave a construction (simple and beautiful) of an isotopy $h_t\colon\mathbb{R}^{2\cdot n}\to \mathbb{R}^{2\cdot n}$ which moves any compact set $K$ in the coordinate $\mathbb{R}^n$-subspace to any other homeomorphic compact $K'$ set in this subspace.

The idea is to extend the homeomorphisms $K\to K'$ and $K'\to K$ to continuous functions $f,g\colon\mathbb{R}^n\to\mathbb{R}^n$ and construct the needed isotopy as concatenation of $(x,y)\mapsto (x,y+t\cdot f(x))$ and $(x,y)\mapsto (x-t\cdot g(y),y)$

Later in "Plane separation" (1968), Doyle used this idea to give 5 line proof of the Jordan separation theorem.

Do you know any other places where this idea shows up?

What is the time complexity of the largest singular value and its vectors?

Math Overflow Recent Questions - Thu, 06/08/2017 - 19:09

Full zero-error SVD on an $m \times n$ matrix $A$ would cost $O(\min(m^2n,mn^2))$. What is the time complexity if we need only the largest singular value and its corresponding vectors? I think it is $O(mn)$, but I'm not sure. I can't see a precise answer from the previous discussions.


Subscribe to curious little things aggregator