Recent MathOverflow Questions

Find conditions over $U$ such that optimization over a convex cone generated by $U$ is equal to optimization over $U$

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

Reading several pappers to prepare my thesis I found the following problem:

We considerer the following optimization problem $$ \left\{\begin{array}{cl} \max\limits_{x\in\mathcal{C}} & f(x) \\[2pt] \text{s.t.} & \mathcal{A}x-b \in K \end{array} \right. \tag{1} $$

where $f:\mathbb{R}^{n}\rightarrow \mathbb{R}$ and $\mathcal{A}:\mathbb{R}^{n}\rightarrow \mathbb{R}^{m}$ are linear functions non-zero, $b\in\mathbb{R}^{m}$, $\mathcal{C}$ is a convex cone in $\mathbb{R}^{n}$ and $K$ is a closed convex cone in $\mathbb{R}^{m}$.

Question: I need to find conditions over a set $U\subset\mathbb{R}^{n}$ such that if $\mathcal{C}$ is the convex cone generated by $U$, then problem $(1)$ is equivalent to the following problem $$ \left\{\begin{array}{cl} \max\limits_{x\in U} & f(x) \\[2pt] \text{s.t.} & \mathcal{A}x-b \in K \end{array} \right. \tag{2} ?$$

Martingale Approach for upper bound on time until n deaths

Math Overflow Recent Questions - Tue, 08/22/2017 - 19:47

suppose we have $n$ Geometric$(p)$ random variables $X_1,\dots,X_n$, and let $Y_t$ be the number of these random variable still alive at time $t$, i.e.

$Y_t = \sum_{i=1}^n \mathbb{1}\{X_i \geq t\}$

I'm interested in upper bounding the expected first time that $Y_t = 0$ using a martingale approach. Here's an example argument that doesn't quite work: we can easily show that

$M_t = \log(Y_t) - \log(n(1-p)^t)$

is a supermartingale. Now we can apply the optional stopping theorem for any stopping time $\tau$ that occurs almost surely to get a bound

$\mathbb{E}[\tau] \leq \frac{1}{\log(\frac{1}{1-p})}(\log(n) - \mathbb{E}[\log(Y_{\tau})])$

However, if we let $\tau$ be the first time that all our geo random variable die, i.e. the first time that $Y_t = 0$, then we can't get anything useful from this bound, since $\mathbb{E}[\log(Y_{\tau})] = -\infty$. I'm wondering if there's a modification of this argument that works? Or if anyone knows alternate approaches? Note that this time is the same as the expected maximum of $n$ geometric random variables. But I'm specifically wondering about a martingale approach (just out of curiosity).

Hessian of a multiple variables function

Math Overflow Recent Questions - Tue, 08/22/2017 - 19:44

I have a function $f(X,Y)$ w.r.t. to two sets of variables $X$ and $Y$. $X = \{x_1,x_2,\dots,x_n\}$ and $Y = \{y_1,y_2,\dots,y_m\}$ where $n$ and $m$ are finite. What is the Hessian matrix of this function?

Here is my thought: \begin{bmatrix} \frac{\partial^2 f}{\partial x_1 \partial x_1}& \frac{\partial^2 f}{\partial x_1 \partial x_2}&\dots&\frac{\partial^2 f}{\partial x_1 \partial x_n} &\dots & \frac{\partial^2 f}{\partial x_1 \partial y_1} &\dots& \frac{\partial^2 f}{\partial x_1 \partial y_m} \\ \frac{\partial^2 f}{\partial x_2 \partial x_1}& \frac{\partial^2 f}{\partial x_2 \partial x_2}&\dots&\frac{\partial^2 f}{\partial x_2 \partial x_n} &\dots & \frac{\partial^2 f}{\partial x_2 \partial y_1} &\dots& \frac{\partial^2 f}{\partial x_2 \partial y_m}\\ \dots&\dots&\dots&\dots&\dots&\dots&\dots&\dots\\ \frac{\partial^2 f}{\partial y_1 \partial x_1}& \frac{\partial^2 f}{\partial y_1 \partial x_2}&\dots&\frac{\partial^2 f}{\partial y_1 \partial x_n} &\dots & \frac{\partial^2 f}{\partial y_1 \partial y_1} &\dots& \frac{\partial^2 f}{\partial y_1 \partial y_m}\\ \dots&\dots&\dots&\dots&\dots&\dots&\dots&\dots\\ \frac{\partial^2 f}{\partial y_m \partial x_1}& \frac{\partial^2 f}{\partial y_m \partial x_2}&\dots&\frac{\partial^2 f}{\partial y_m \partial x_n} &\dots & \frac{\partial^2 f}{\partial y_m \partial y_1} &\dots& \frac{\partial^2 f}{\partial y_m \partial y_m} \end{bmatrix}

Please correct me if I am wrong.

Does a quotient group $G/N$ have a natural action on the regular representation of $G$?

Math Overflow Recent Questions - Tue, 08/22/2017 - 18:29

Let $G$ be a group. I am happy to assume niceties such as finite and abelian, but perhaps it is not necessary to answer my question.

Consider the $|G|$-dimensional vector space $V$ (over some nice field $K$, possibly even $\mathbb C$ if need be) whose basis $\{v_g\}_{g \in G}$ is labeled by the group elements of $G$. We know any subgroup $H \subset G$ has a natural action on this vector space: any $h \in H$ defines a linear map $h \cdot v_g = v_{hg}$.

I was now wondering: take a normal subgroup $N \trianglelefteq G$. Is there a natural action of $G/N$ on $V$? I would imagine something in the line of $[g'] \cdot v_g = k \; v_g$ where $k\in K$, but not sure what $k$ should be. Possibly something like ``$k = -1$ if $[g'] = [g]$ and $k=1$ otherwise''?

(For those interested in the more general context I am wondering about: given a (central) extension $1 \to A \to E \to B \to 1$, do $A$ and $B$ have a natural action on the regular representation of $E$?)

Quadratic character base

Math Overflow Recent Questions - Tue, 08/22/2017 - 16:57

What is the use of Quadratic Character Base in Sieving specifically Lattice Sieving?

I know it is used to make sure that the final combination is constructed in such a way that its is a square in Z[alpha] (on the algebraic side) but can someone illustrate in detail?

separable variable method came from ? [on hold]

Math Overflow Recent Questions - Tue, 08/22/2017 - 16:43

can anybody know why in separable variable we need assumption that our function is made from product of our variable , not added results or qoutient.

Y(a,b,c)=A(a).B(b).C(c).

why we can assume that ? where is came from ? (philosophy)

who was found this technique ?

Partial Differential Equations, Schwartz and Hilbert space [on hold]

Math Overflow Recent Questions - Tue, 08/22/2017 - 16:20

Define a Hilbert space $H_j$ by

$$H_j = (u \in L^2(R^d): \int (1+ x_j^2)|u|^2 dx + \int (1+ \xi_j^2)| \widehat {u} |^2 < \infty).$$

The square of the norm in $H_j$ is the sum of the integrals in brackets.

I need help how to prove that:

The Schwartz space $S$ is dense in $H_j$.

$S(R^d)= (u \in C^{\infty}: \alpha, \beta \in N^d, sup_{x \in R^d} |x^{\alpha} \partial^{\beta} u(x)|< \infty ) $

What does homomorphism between languages mean to the correspoding Turing Machines?

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

According to the article: every c.e.language over $\Sigma^*$can be formed by homomorphism from a Dyck language over $\Sigma^{'}$ intersection with a minimal linear language over $\Sigma^{'}$ to the Kleene closure $\Sigma^*$ over a alphabet.

Now we know, intersection between languages is parallel to series connection of the corresponding Turing Machines. Then what does homomorphism between languages mean to the correspoding Turing Machines?

Partially it seemingly means merge of computational paths,

Divisibility property of integers congruent to quadratic residues

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

If $a^2 \equiv b \bmod p$ then can we expect divisibility properties of $a$ and $b$ to be different than what a 'normal' behavior would indicate?

Pick a perfect square $a^2$ and a non-square $b$ in interval $[2^{m-1},2^m]$. Pick $t=O((\log m)^c)$ different primes $p_1,\dots,p_t\in[m,2m]$ where $c\in\Bbb R_+$ is fixed.

The number of pairs of $(a^2,b)\in[2^{m-1},2^m]\times[2^{m-1},2^m]$ such that $a^2\equiv b\bmod p_i$ and $a^2\equiv b\bmod (p_i+\Delta_j)$ where $j\in\{1,\dots,t'\}$ and $\Delta_1,\Delta_2$ are distinct fixed integers from $\{1,\dots,t\}$ is heuristically at most $\frac{2^{2m}}{(\min(a,b)^{(t'+1)(\log m)^c}}$.

Is it possible there could be at most only $\frac{2^{2m}}{(\min(a,b)^{2^{(t'+1)}(\log m)^c}}$ such pairs?

What is the fastest growing function $f(t', m)$ of $t',m$ that provides correct estimate in form of $\frac{2^{2m}}{(\min(a,b)^{f(t', m)}}$ such pairs?

An explicit representation for polynomials generated by a power of $x/\sin(x)$

Math Overflow Recent Questions - Tue, 08/22/2017 - 14:22

The coefficients $d_{k}(n)$ given by the power series $$\left(\frac{x}{\sin x}\right)^{n}=\sum_{k=0}^{\infty}d_{k}(n)\frac{x^{2k}}{(2k)!}$$ are polynomials in $n$ of degree $k$. First few examples: $$d_{0}(n)=1,\quad d_{1}(n)=\frac{n}{3}, \quad d_{2}(n)=\frac{2 n}{15}+\frac{n^2}{3}, \quad d_{3}(n)=\frac{16n}{63}+\frac{2 n^{2}}{3}+\frac{5n^3}{9}.$$ Question: Is there an explicit formula for the coefficients of polynomials $d_{k}(n)$?

Remark: I am aware of their connection with the Bernoulli polynomials of higher order $B_{n}^{(a)}(x)$. Namely, one has $d_{k}(n)=(-4)^{k}B_{2k}^{(n)}(n/2)$. This formula and several other alternative expressions can be found in the book of N. E. Norlund (Springer, 1924) but none of them seems to be very helpful.

Does Matrix Gaussian Maximize Entropy?

Math Overflow Recent Questions - Tue, 08/22/2017 - 13:39

What is a generalization of the maximum entropy principle to random matrices?

We know that over all random vectors $X \in \mathbb{R}^n$ with covariance $K$ the Gaussian maximizes entropy that is \begin{align} \max_{X\in \mathbb{R}^n: E[(X-\mu)(X-\mu)^T]=K } h(X) = h(X_G) \end{align} where $X_G \sim \mathcal{N}(\mu, K)$.

What would be a generalization of this statement to random matrices?

Specifically, under what constraints a matrix normal with the pdf given by \begin{align} f_X(x)= \frac{1}{(2\pi)^{mn} |V|^\frac{n}{2} |U|^\frac{n}{2}} e^{-\frac{{\rm Tr}\left[V^{-1}(x-M)^TU^{-1}(x-\mu)\right]}{2}} \end{align} where $x \in \mathbb{R}^{n\times m}$ would maximize the entropy.

For me, the issue here is that there are two covariances here $V$ and $U$.

The geometry of the solution set of a symmetric equation in four symmetric matrices

Math Overflow Recent Questions - Tue, 08/22/2017 - 12:40

Let $n$ be a natural number. We can view the space of invertible symmetric matrices over a field as an open subset of$\mathbb A^{(n^2+n)/2}$. Inside the fourth power of this space, we have the closed subscheme consisting of tuples satisfying $A_1 + A_2 = A_3 + A_4$ and $A_1^{-1} + A_2^{-1} = A_3^{-1}+ A_4^{-1}$.

  1. Is this subscheme a complete intersection of dimension $n^2+n$?

  2. How many irreducible components does this subscheme have?

The motivation is that this would evaluate the fourth moment of symplectic Kloosterman sums, in the same way that Kloosterman's classical argument evaluates the fourth moment of the usual Kloosterman sums. However, I don't expect techniques from number theory to be helpful here.

The $n=1$ case has three irreducible components of dimension $2$, given by equations as follows $(x_3=x_1,x_4=x_2),(x_3=x_2,x_4=x_1),(x_2=-x_1,x_4=-x_3)$. Using these, we can make $3^n$ $2n$-dimensional families of diagonal examples. All of these are contained in an irreducible component of dimension at least $n^2+n$, as the scheme is defined by only $n^2+n$ equations in $2n^2 +2n$-space. However, only for a few obvious ones can I locate an $n^2+n$-dimensional family containing them.

How to put Running head: xxxx and page number from title page, and header on abstract and body using Latex [on hold]

Math Overflow Recent Questions - Tue, 08/22/2017 - 11:55

Do you know how to deal with other APA formating requirements in LaTeX? For example, how to make APA style heading in LaTeX? I am new to LaTeX and I can't find out how to make it work with the 6th edition of APA Manual. ajit

Tight upper bound on the number of high degree vertices

Math Overflow Recent Questions - Tue, 08/22/2017 - 11:21

Let $G$ be a undirected graph with $n$ many vertices and $m$ many edges. Let us define $q = \Theta \big(\frac{n} {\log n}\big)$, now let us call a vertex $v$ big if degree$(v_i) \ge \frac{m}{q}$.

Question : How many big vertices will be there in a graph ?

I know the loose upper bound is $q$, Is it tight ? Is there a known tight upper bound?

Thank you

Rigorous integration by parts for weighted Sobolev spaces

Math Overflow Recent Questions - Tue, 08/22/2017 - 10:24

In appearance the following question seems to be a technical detail but I did not manage to prove the claim rigorously and I start to doubt that the result does not hold.

The setting is $Q_T=(0,T)\times \mathbb{T}^d$ where $\mathbb{T}^d$ is the torus.

For any function $\Phi\in L^2(0,T;H^2(\mathbb{T}^d))\cap W^{1,2}(0,T;L^2(\mathbb{T}^d))\cap L^\infty(0,T;H^1(\mathbb{T}^d))$ such that $\Phi(T)=0$, the following inequality \begin{align*} \frac{1}{2}\|\nabla \Phi\|_{L^\infty(0,T;L^2(\mathbb{T}^d))}^2\leq \|\partial_t \Phi\|_{L^2(Q_T)}\|\Delta_x \Phi\|_{L^2(Q_T)} \end{align*} can be proven easily by approaching $\Phi$ by smooth functions $\Phi_k$ for which the following integration by parts holds rigorously for all $t\in(0,T)$ \begin{align*} \frac{1}{2}\|\nabla \Phi_k(t)\|^2_{L^2(\mathbb{T}^2)}-\frac{1}{2}\|\nabla \Phi_k(T)\|^2_{L^2(\mathbb{T}^2)} = \int_t^T\int_{\mathbb{T}^d} \partial_t \Phi_k\,\Delta_x \Phi_k. \end{align*} Now, consider a function $\mu\in L^1(Q_T)$, lower-bounded by some positive constant $\alpha>0$ and instead of the space above for $\Phi$, assume that it belongs to $L^\infty(0,T;H^1(\mathbb{T}^d))$ and that it satisfies $\mu^{1/2}\Delta \Phi \in L^2(Q_T)$ and $\mu^{-1/2}\partial_t \Phi \in L^2(Q_T)$. If allowed, the previous integration by parts would lead to the following inequality \begin{align*} \frac{1}{2}\|\nabla \Phi\|_{L^\infty(0,T;L^2(\mathbb{T}^d))}^2\leq \|\mu^{-1/2}\partial_t \Phi\|_{L^2(Q_T)}\|\mu^{1/2}\Delta_x \Phi\|_{L^2(Q_T)}. \end{align*} But I am not able to exhibit an approximation process which continuously approach $\partial_t \Phi$ and $\Delta_x \Phi$ in the corresponding weighted spaces and at the same time remains compatible with the integration by parts.

Is this a real difficulty ? This inequality could be false ? Or there is a simple reason which justifies the computation above ?

Thanks for any help or reference !

Edit : I just discovered (after a more careful research on MO) the existence of several papers dealing with the question "H=W" aiming at giving a condition on a weight so that smooth functions are dense in the Sobolev space that it defines. With this type of results, I think the formula is true if furthermore $\mu$ is assumed bounded from above for instance (it satisfies then the $A_2$ Muckenhoupt condition), but still I am not able to understand if I need all this machinery.

Existence of regular cardinals larger than an arbitrary cardinal in von Neumann universes without axiom of choice

Math Overflow Recent Questions - Tue, 08/22/2017 - 00:57

It is well known that the von Neumann universes $V_{\alpha}$ is a model of ZF(C) when $\alpha$ is an inaccessible cardinal. In the following let $V$ be such a model of ZF(C). It is also well known (see corollary 5.3 of Set Theory, The Third Edition, by Thomas Jech) that assuming axiom of choice every successor aleph cardinal, $\aleph_{\beta+1}$, is a regular cardinal for any ordinal number $\beta$. This means that in ZFC (together with the necessary assumption on existence of the inaccessible cardinal necessary to construct $V$) we have:

For any cardinal number $\alpha \in V$ in the universe there is a regular cardinal $\beta \in V$ in the same universe, such that $\alpha < \beta$.

Does this statement hold in ZF? In other words, is it provable without the axiom of choice that for any given cardinal number in a universe there a strictly larger and regular cardinal in that universe?

Inverting the cumulative probability function to find roots of stochastic function

Math Overflow Recent Questions - Mon, 08/21/2017 - 23:56

Given a function:

$$f[x]=a\, \Phi \left[-x+\sigma \sqrt{\tau}\right]-\left(b+c\, e^{-d \tau}\right)\Phi \left[-x\right]$$

where $\Phi$ is the cumulative density function of the standard normal distribution: $$\Phi\left[z\right] = \frac{1}{\sqrt{2 \pi}}\int^{z}_{-\infty}e^{\frac{-u^2}{2}} \, \mathbb{d}u $$

...how can I find $x$ which which satisifies the conditon $f[x]=0$? Suppose that a, b, c, $\sigma$, t are known quantities.

I am stuck trying to use inverse identities since approximations to inverse functions seem to not hold when inverting a probability function multiplied by a constant.

Also, although there is an algorithm to find $x$ through recursion:

$$x \to-\Phi^{-1}[\frac{a}{b+c\, e^{-d \tau}}\, {\Phi\left[-x+\sigma \sqrt{\tau}\right]}] \,\,\, \forall \,\,\, \tau \in \, [t,T]$$

where $\Phi^{-1}$ is the probit function.

...this does not satisfy a closed form requirement.

Acceptable answers may include closed form solutions as well as numerical approximations provided that approximations converge for $\left|{x}\right|\to Large$. I also appreciate any direction or references.

Associativity for Gaussian Homomorphisms [on hold]

Math Overflow Recent Questions - Mon, 08/21/2017 - 23:03
  1. Let Cθ,Ω < ¯d be arbitrary. We say a Taylor, contra-contravariant, one-to-one vector P0 is irreducible if it is onto, differentiable, contra-trivially nonnegative and discretely injective.
  2. Let O be a connected monoid. We say an unconditionally negative curve Kˆ is invertible if it is almost everywhere universal and finitely right-linear.
  3. An isometric category Xρ,i is canonical if τ > 0.

Suppose we are given an orthogonal, holomorphic, anti-pairwise Lagrange homeomorphism E. Then µ =√2.

Let us assume every Cartan morphism is almost surely sub-Jordan and sub-complex. Let us suppose we are given an ultra-surjective morphism r0. Does O = 1?

double inequality for integral of convex functions

Math Overflow Recent Questions - Mon, 08/21/2017 - 15:41

I am able to give a proof to the following inequality for convex functions. Most likely this is well known, but I am unable to find a reference. I would appreciate if someone more knowledgeable in the literature of convex analysis could help.

Suppose $P$ is a convex subset of $\Bbb R^n$ and $f: P \to \Bbb R$ is a convex function such that $\int_P f =0$. Then there exists positive constants $\alpha,\beta>0$ (not dependent on $f$) such that $$-\alpha\inf_P f \leq \int_P |f(x)|dx^n \leq -\beta \inf_P f .$$

Pages

Subscribe to curious little things aggregator