# 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:

$$L(w,\theta)=-\sum_{i=1}^{n}log(\phi(\theta_{y_i}-w^Tx_i)-(\phi(\theta_{y_i-1}-w^Tx_i))$$

$$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!

### 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,

$0<x,y<1$

$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}$

$g(x,y)=\left|x-y\right|$

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.

Image

### 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 - http://repository.ias.ac.in/3652/1/427.pdf, 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. $$\ddot{f}(t)=g(t)N({f}(t))$$

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 ...??

$$g(t)=...$$

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

$$\ddot{f}(t)+\dot{N}({f}(t))N({f}(t))=0$$

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

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:

http://www.ams.org/journals/proc/1992-114-02/S0002-9939-1992-1014648-2/S0002-9939-1992-1014648-2.pdf

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.