Recent Questions - MathOverflowmost recent 30 from mathoverflow.net2014-09-17T11:44:03Zhttp://mathoverflow.net/feedshttp://www.creativecommons.org/licenses/by-sa/3.0/rdfhttp://mathoverflow.net/q/1811030Independent SetsPavan Sanghahttp://mathoverflow.net/users/542392014-09-17T11:32:41Z2014-09-17T11:32:41Z
<p>I was wondering if a lot is known about independent sets in Random Geometric graphs? Most google searches don't bring up much. In addition i'm interested in any algorithms used for finding independent sets in Random Geometric Graphs. </p>
http://mathoverflow.net/q/1811020Functions $f$ on $\mathbb{Z}/N\mathbb{Z}$ with $|f|$ and $|\widehat{f}|$ constantFreddie Mannershttp://mathoverflow.net/users/222532014-09-17T11:22:51Z2014-09-17T11:22:51Z
<p>Let $N$ be a positive integer; for simplicity I'm happy to assume it's an odd prime but I'm interested in the general case too.</p>
<p>Let $f \colon \mathbb{Z}/N\mathbb{Z} \to \mathbb{C}$ and let $\widehat{f}$ denote its Fourier transform, $\widehat{f}(\xi) = \frac{1}{N} \sum_x f(x) e^{-2 \pi i \xi x / N}$.</p>
<p>I'm interested in functions $f$ with $|f|$ constant and $|\widehat{f}|$ constant; with the above conventions, WLOG taking $|f| = 1$ we have $|\widehat{f}| = 1/\sqrt{N}$.</p>
<p>My question is: is anything known about such functions? Do they have a name? Is there perhaps even a precise classification of them? Any pointers or references would be appreciated.</p>
<hr>
<p>It's maybe worth saying that, although apparently a question about analysis, it is actually surely strongly algebraic in nature. Indeed, the conditions can be phrased as an algebraic set over $\mathbb{R}$ which I believe has dimension $0$ when $N$ is prime (if we add the condition $f(0) = 1$ to remove the degeneracy), which would mean the collection of such $f$ is finite and the coefficients are algebraic numbers. Furthermore all the examples I've computed are exceedingly structured, e.g.</p>
<p>$$ f(x) = e^{2 \pi i (\alpha x^2 + \beta x + \gamma) / N} $$</p>
<p>where $\alpha \in (\mathbb{Z}/N\mathbb{Z})^\times$, $\beta \in \mathbb{Z}/N\mathbb{Z}$, $\gamma \in \mathbb{R}$, as well as more complicated variants.</p>
http://mathoverflow.net/q/1811010How to extend Dirichlet distribution to Dirichlet processhenrysupercoolhttp://mathoverflow.net/users/583062014-09-17T11:19:46Z2014-09-17T11:19:46Z
<p>For a Dirichlet process, there are two parameter $\alpha$ and $H$, and the Dirichlet process $X$ is defined as
$$(X(B_1),\cdots,X(B_n))\sim Dir(\alpha H(B_1),\cdots,\alpha H(B_n))$$
where$\{B_i\}_{i=1}^n$is a partition of the measurable space.</p>
<p>While the Dirichlet distribution is like that
$$f(x_1,x_2, \cdots ,x_{K - 1};\alpha _1,\alpha _2, \cdots ,\alpha _{K - 1},\alpha _K) = \frac{1}{B(\vec \alpha )}\prod\limits_{i = 1}^K x_i^{\alpha_i - 1} $$</p>
<p>My question is:</p>
<p>If I want to view the Dirichlet distribution as a special case of the Dirichlet process, then how should I set the parameters $\alpha$ and $H$ in the definition of Dirichlet process?</p>
http://mathoverflow.net/q/1811000The distribution of maximum of fraction Brownian motion over finite time intervalrandallxuhttp://mathoverflow.net/users/387292014-09-17T11:11:25Z2014-09-17T11:11:25Z
<p>Suppose that $\{B_t^H,\ t\geq 0\}$ is a fractional Brownian motion with Hurst exponent $H$, I wonder if there are explicit expressions for the joint distribution of
$(\sup_{0\leq t\leq T}B_t^H,B_T^H)$, where $T$ is a fixed constant. I search this problem by google scholar, but only find some asymptotic results. No explicit results provided. Thanks for your attention.</p>
http://mathoverflow.net/q/1810990path integral and index theoremuser44895http://mathoverflow.net/users/583052014-09-17T11:11:16Z2014-09-17T11:29:04Z
<p>I actually have an integral which is used to prove Atiyah-Singer index theorem for spin complex in a path integral fashion. The integral I need to evaluate is following (in simplified form)</p>
<p>$\int \prod_{n=1}^\infty da_n^\mu exp{\frac{1}{4}}\sum_{n=1}^\infty[(2n \pi)^2 (a_n^\mu)^2 + a_n^{\mu} a_n^{\nu} R_{\mu\alpha} R_{\nu}^{\alpha}/M^4]$ where $a_n^\mu$ are fourier coefficients and $R_{\mu\nu}$ is the famous curvature tensor with it's two indices contracted (Ricci tensor), </p>
<p>the result to which should be </p>
<p>$\int \prod_{n=1}^\infty det |1-\frac{R_{\mu}^{\alpha} R_{\nu}^{\alpha}}{M^4 (2n\pi)^2}|^{-1/2}$.</p>
<p>Now I am having difficulty to verify this result. I have tried to diagonalize the Ricci tensor in terms of the eigenvalues $x_i$ and $-x_i$ and hence the product of two tensor in
$R_{\mu\alpha} R_{\nu}^{\alpha}$ will give only diagonal terms which can be combined with the first term to give something similar to $[1-\frac{R_{\nu}^{\alpha} R_{\nu}^{\alpha}}{M^4 (2n\pi)^2}](2n \pi)^2 (a_n^\mu)^2$ and then I can perform Gaussian integration (did not work) to get similar but not same result. </p>
<p>Can anyone help me out?</p>
http://mathoverflow.net/q/1810980Connection between Strebel differentials, ribbon graphs, and Belyi mapsJimereehttp://mathoverflow.net/users/255652014-09-17T10:33:34Z2014-09-17T10:33:34Z
<p>In <a href="http://arxiv.org/pdf/math-ph/9811024v2.pdf" rel="nofollow">this paper</a>, a nice story is woven regarding the connection between quadratic differentials on Riemann surfaces, so-called 'ribbon graphs' drawn on those surfaces, and Belyi maps. However, I am running into trouble when I try to apply the results of that paper in a concrete example, and I am wondering whether anyone can help to identify the source of my confusion. Although there are a lot of words below, I hope the question will be reasonably easy to answer!</p>
<p>First, to briefly recap: Consider a meromorphic quadratic differential $q=\phi\left(x\right)\mathrm{d}x^2$ with only second order poles, drawn on a Riemann surface $\mathcal{C}$ of genus $g$ and with $n$ punctures. For special values of the parameters in $\phi\left(x\right)$, $q$ will satisfy the definition of a so-called <strong>Strebel differential</strong>, as given in Theorem 4.2. When the quadratic differential is Strebel, so-called 'horizontal trajectories' drawn on $\mathcal{C}$ using $q$ can can be used to construct a unique <strong>ribbon graph</strong> on $\mathcal{C}$ corresponding to that Strebel differential; the ribbon graph has vertices for the zeroes of $q$ and one face for every second-order pole of $q$.</p>
<p>Each ribbon graph can be interpreted as a <strong>dessin d'enfant</strong> in the sense of Grothendieck, i.e. as a bipartite graph on $\mathcal{C}$. To do this, we colour every vertex of the ribbon graph white, and insert a black node into every edge. In the paper, this is referred to as the "edge refinement of the ribbon graph". To each dessin there corresponds a unique <strong>Belyi map</strong>, i.e. a holomorphic map to $\mathbb{P}^1$ ramified at only $\left \{ 0,1,\infty \right \}$ (the dessin is the inverse image of the line segment $\left[0,1\right]$ by the Belyi map).</p>
<p>One of the main results of the paper in question is Theorem 6.5. Take a Strebel differential $q$ on $\mathcal{C}$. To $q$ there corresponds a ribbon graph, which we can interpret as a dessin, and to that dessin there corresponds a unique Belyi map $\beta$. It turns out that $q$ is the pullback by $\beta$ of a meromorphic quadratic differential on $\mathbb{P}^1$ with three punctures, so that:</p>
<p>$$q = \beta^* \left(\frac{\left(\mathrm{d}\zeta\right)^2}{4\pi^2\zeta\left(1-\zeta\right)}\right)$$</p>
<p>It then seems to follow (but isn't explicitly stated in the paper) that:</p>
<p>$$q = \left( \frac{\left(\mathrm{d}\beta\right)^2}{4\pi^2\beta\left(1-\beta\right)} \right) $$</p>
<p>My trouble comes when I attempt to apply this theorem in a concrete example. For instance, take $\mathcal{C}$ to be the four-punctured sphere, so that $g=0$ and $n=4$. As drawn in figure 5 <a href="http://arxiv.org/pdf/hep-th/0610080v1.pdf" rel="nofollow">here</a>, there are five topologically distinct possible ribbon graphs. Let's just pick one of these, and draw it in dessin form:</p>
<p> <img src="http://i.stack.imgur.com/5Yc93s.png" alt="One possible ribbon graph that can be drawn on the four-punctured sphere."></p>
<p>Since the ribbon graph has four vertices and four faces, we expect the Strebel differential to have four zeroes (for the vertices) and four second order poles (for the faces). The Belyi map associated to the above dessin is known to be:</p>
<p>$$\beta\left(t\right) = \frac{t^3\left(t+6\right)^3\left(t^2-6t+36\right)^3}{\left(t-3\right)^3\left(t^2+3t+9\right)^3}$$</p>
<p>(The details are given in <a href="http://journals.cambridge.org/download.php?file=%2FJCM%2FJCM16%2FS1461157013000119a.pdf&code=0ed8ad7b442c1f1381bc6fe8a66d382c" rel="nofollow">this paper</a>. In short, the above dessin can be associated to the modular subgroup $\Gamma\left(3\right)$, and the associated Belyi map is given <a href="http://mysite.science.uottawa.ca/asebbar/publi/mcse.pdf" rel="nofollow">here</a>.)</p>
<p>When we substitute our expression for $\beta\left(t\right)$ into our expression for $q$ in terms of $\beta$ above, we would expect to recover an expression with four zeroes and four second order poles, but we don't! So it looks like something isn't consistent. So, in summary, my question is: <strong>why don't I recover the right form of the Strebel differential, for a certain given ribbon graph, when I substitute the associated Belyi map into the expression above for $q$ in terms of $\beta$?</strong></p>
http://mathoverflow.net/q/181097-4How to compute the derivative and integral of a curve with fractional dimension? [on hold]Nature and Taohttp://mathoverflow.net/users/583042014-09-17T10:12:54Z2014-09-17T10:12:54Z
<p>It is interesting to find differential and integral calculus theory in the manifold with any dimension, where the value of dimension can take any real number or complex number. Then the Newton-Leibniz’s calculus theory will be a special case of this theory whenever the dimension of manifold equals a positive integer.
Recently, I see such a calculus theory. It can be used to establish the quantum field theory on fractal spacetime so that the divergence dilemma in quantum theory can be removed, e.g., G ’t Hooft and K G Wilson’s Dimensional Regularization Method.
About this calculus theory, you can find it in: </p>
<p>Yong Tao, “The Validity of Dimensional Regularization Method on Fractal Spacetime,” Journal of Applied Mathematics, vol. 2013, Article ID 308691, 9 pages, 2013. doi:10.1155/2013/308691</p>
<p>The website is at:
<a href="http://www.hindawi.com/journals/jam/2013/308691/" rel="nofollow">http://www.hindawi.com/journals/jam/2013/308691/</a></p>
<p>I don't know if the calculus theory above is correct. I hope to obtain the answer.
Thanks !</p>
http://mathoverflow.net/q/1810951Bases of surface groupsPablohttp://mathoverflow.net/users/388892014-09-17T09:49:42Z2014-09-17T11:18:04Z
<p>Let $\Gamma_g$ be a surface group of genus $g \geq 2$. A $2g$-tuple $(x_1,y_1, \dots,x_g,y_g) \in \Gamma_g^{2g}$ will be called a <strong><em>Surface Basis</em></strong> if we have the presentation $$\Gamma_g = \langle x_1, y_1, \dots, x_g, y_g \vert \prod_{i = 1}^{g}[x_i,y_i] = 1\rangle$$ Take some $1 \leq k \leq g$ and $H \leq \Gamma_g$ of finite index such that $x_1, \dots, x_k \in H$. One can show that $H$ is a surface group of genus $(g-1)[\Gamma_g : H] + 1$, and that it has a surface basis. My question is:</p>
<blockquote>
<p>Is there a surface basis for $H$ containing $x_1, \dots, x_k$?</p>
</blockquote>
<p>The analogous question for free groups has a positive answer as shown in <a href="http://mathoverflow.net/questions/172599/bases-of-free-groups">Bases of free groups</a>.</p>
http://mathoverflow.net/q/181094-1An isogeny from a split algebraic torusTonyhttp://mathoverflow.net/users/49482014-09-17T09:34:55Z2014-09-17T09:34:55Z
<p>Suppose that there is an isogeny (in the category of commutative algebraic groups) from a split algebraic torus to a semi-abelian variety. Does it follows that this semi-abelian variety is also an algebraic torus?</p>
http://mathoverflow.net/q/1810900Merging regions of function with similar mean and deviation using statistical testwatskeburthttp://mathoverflow.net/users/583022014-09-17T08:14:57Z2014-09-17T08:14:57Z
<p>I have got a question related to statistical tests that I would like to use in a new algorithm I am developing. Given an action space $x$, the algorithm would identify the regions in the function landscape $f(x)$ that have similar characteristics, i.e., roughly the same mean and standard deviation. Once I have identified these similar regions, I can determine the optimal combinations of mean and standard deviation. For instance, in a control application, I could highlight that region 1 has a slightly higher mean than region 2, BUT the standard deviation of region1 is much higher than region 2. So, the system engineer would most likely prefer to exploit region 2 as it is much more stable. This in contrast to standard approaches that would only focus on the mean and thus, would favour region 1.</p>
<p>To accomplish this, I have a binary tree-like structure based on the work of (Bubeck, 2011) related to $X$-armed bandits. The tree stores nodes over the action space $x$ [0,1] where a node stores the position in the action space, e.g. position 0.2 in the action space, and the sampled reward on $f(x)$, e.g., 0.78. Based on these values, the tree grows, i.e., more nodes are added. Thus, nodes at deeper levels represent finer action space positions, while nodes at higher levels are at a much larger distance. Note that we do not sample an action more than once, we only can add 2 child nodes to that specific node and proceed. These 2 nodes then represent a finer action (little bit more to the left and right, resp., in action space).</p>
<p>What I would like to do is the following. Imagine an off-line setting for now, where the tree is built up to a very fine level in the action space. Let's say 0.001 is the distance between the leaf nodes. Now, I would like to identify these regions. My approach would be the following: every leaf first is a (small) region on its own. In a breadth-first method, look at the sampled values of every two leaf nodes and use a (statistical) test to determine whether they represent the same region. If this test would then take into account the size of the samples (in this case only two) and their level in the tree (very very deep, so these leafs are negligible in the action space), it would conclude that there is not enough evidence to say they represent different regions. Hence, these 2 small regions are merged in a bigger region. This process is then repeated one level up and bigger regions with similar characteristics can be identified. Of course, the statistical test would have to take into account that, when I go up in the tree, the distance in the action space is bigger and I have already acquired more samples, so it can differentiate with a higher probability.</p>
<p>A long story short, how can I identify regions of the tree with similar characteristics (mean and deviation), taken into account that I have a (1) certain amount of samples in a subtree/subregion (2) from particular positions in action space. (1) and (2) are definitely important aspects the test should to take into account. Eventually, the test should also work when trying to merge subtrees, they are not necessary equally large (different depth) in an on-line setting.</p>
<p>A visual overview of the problem can be found here: <a href="http://i.stack.imgur.com/Zk8AA.png" rel="nofollow">http://i.stack.imgur.com/Zk8AA.png</a></p>
<p>Can anybody point me in the right direction?</p>
<p>Thanks a lot!</p>
http://mathoverflow.net/q/1810891Does this simple inequality have a name?Felix Goldberghttp://mathoverflow.net/users/220512014-09-17T07:53:04Z2014-09-17T08:37:06Z
<p>Let $x_{1},\ldots,x_{n}$ be nonnegative numbers such that $m \leq x_{i} \leq M$. Let
$$
S=\sum_{i=1}^{n}{x_{i}}
$$
and
$$
Q=\sum_{i=1}^{n}{x_{i}^{2}}.
$$</p>
<p>Then
$$
Q \leq S(M+m)-nMm.
$$</p>
<p>This has been recently discovered by at least two different people (including myself) but I am sure that it has come up many times before. Does it have a standard name or reference?</p>
http://mathoverflow.net/q/181088-4Prove that a mixed strategy in two player, zero sum, matrix game must exist (alternative proof) [on hold]user3784030http://mathoverflow.net/users/583002014-09-17T06:50:35Z2014-09-17T06:50:35Z
<p><strong>So I am having a trouble with this game theory proof. I feel pretty good with my answer for part 1, but I am not really sure how to get started on the rest of it. Any help would be appreciated.</strong></p>
<p>Let $A$ be an $m \times n$ matrix game, and consider the two player, zero sum, matrix game. For each pair of mixed strategies $(X,Y)$ define</p>
<p>$B_I(X,Y)=max_{1\leq i \leq m}(e_iAY^t)-XAY^t$ (that is the most P1 can improve if P2 plays strategy Y)</p>
<p>$B_{II}(X,Y)=max_{1\leq j\leq n}(XAe_j^t)-XAY^t$</p>
<p>$B=B_I+B_{II}$</p>
<p>Since $S_m \times S_n$ is compact, one can find $(X^*,Y^*)$ such that $B(X^*,Y^*)$ is minimal.</p>
<p>1) Explain why if $B(X^*,Y^*)=0$ then $(X^*,Y^*)$ is a saddle point in mixed strategies.</p>
<p>I am thinking that since $B_I$ is the most P1 can improve if P2 plays strategy Y, and $B_{II}$ is the most P2 can improve if P1 plays strategy X,
that if $B(X^*,Y^*)=0$ this implies that:</p>
<p>$$B(X^*,Y^*)=B_I+B_{II}=max_{1\leq i \leq m}(e_iAY^t)-XAY^t+max_{1\leq j\leq n}(XAe_j^t)-XAY^t=max_{1\leq i \leq m}(e_iAY^t)+max_{1\leq j\leq n}(XAe_j^t)-2(XAY^t)=0$$</p>
<p>$$max_{1\leq i \leq m}(e_iAY^t)+max_{1\leq j\leq n}(XAe_j^t)=2(XAY^t)$$</p>
<p>Which implies that P1's strategy and P2's strategy cannot be improved, and therefore $(X^*,Y^*)$ is an optimal strategy, so it is a saddle point in mixed strategies.</p>
<p>2) Assume $B(X^*,Y^*)\neq 0$. Assume there are unique $i,j$ such that $e_iAY^t-XAY^t=B_X, XAe_j^t-XAY^t=B_Y$. Show that for small enough $\epsilon$ either $B((1-\epsilon)X^*+\epsilon e_i,Y^*)<B(X^*,Y^*)$ or $B(X^*,(1-\epsilon)Y^*+\epsilon e_j)<B(X^*,Y^*)$. This is a contradiction.</p>
<p>3) Use induction on the size of the matrix to show that, even if $i,j$ are not unique in part 2, you still reach a contradiction. Conclude that saddle points in mixed strategies always exist.</p>
http://mathoverflow.net/q/1810874higher-order reflectionMonroe Eskewhttp://mathoverflow.net/users/111452014-09-17T06:25:32Z2014-09-17T06:25:32Z
<p>In the first-order context, "reflection" of a formula $\varphi(x)$ below $\kappa$ refers to the the following situation: </p>
<blockquote>
<p>There are many ordinals $\alpha<\kappa$ such that for all $a \in V_\alpha$, $V_\alpha \models \varphi(a)$ iff $V_\kappa \models \varphi(a)$.</p>
</blockquote>
<p>If $\kappa$ is inaccessible, then this holds for any expansion of $V_\kappa$ in a countable language. "Many" can be taken to mean on a club set.</p>
<p>When we move to higher-order logic, talk of reflection usually shifts to talk of indescribability. A cardinal is $\Pi^m_n$ indescribable if for any $A \subseteq V_\kappa$ and any $\Pi_n$ sentence $\sigma$ in $(m+1)$-order logic with a predicate for $A$, if $(V_\kappa, \in, A) \models \sigma$, then there is $\alpha<\kappa$ such that $(V_\alpha,\in,A\cap V_\alpha) \models \sigma$. It is a standard fact that if $\kappa$ is measurable, then there is a measure-one set of $\alpha< \kappa$ that are $\Pi^m_n$-indescribable for every $m,n$. One can also show something stronger: If $\kappa$ is measurable, there is a measure-one set of $\alpha < \kappa$ such that if $A \subseteq V_\alpha$, then there is $\beta < \alpha$ such that $(V_\alpha,\in,A)$ and $(V_\beta,\in,A\cap V_\beta)$ have the same $\omega$-order theory.</p>
<p>Now this is not completely analogous to reflection because we're no longer talking about elementary substructures, but just elementarily equivalent structures, albeit with a common interpretation of a particular predicate. So my question is, what kind of large cardinal $\kappa$ is needed to get the following statement?</p>
<blockquote>
<p>For any $A \subseteq V_\kappa$ and any $n \in \omega$, there are many ordinals $\alpha < \kappa$ such that $(V_\alpha,\in,A \cap V_\alpha) \prec^n (V_\kappa,\in,A)$, where $\prec^n$ means elementary in $(n+1)$-order logic.</p>
</blockquote>
<p>It happens at an $\omega$-strong cardinal, but this is clearly not optimal.</p>
http://mathoverflow.net/q/181085-4additive identity uniquenes [on hold]user2899211http://mathoverflow.net/users/582972014-09-17T06:12:44Z2014-09-17T06:12:44Z
<p>I am taking discrete math online and I work graveyards. My teacher has a 2 day wait to respond to questions. I am normally OK with math but now I'm frustrated. Over something that should be simple.</p>
<p>In the example below (labelled <strong>example</strong>) for proving uniqueness of the additive identity why are the n's negative? </p>
<p>−n = 0 + (−n) by Axiom A.3</p>
<p>How did we get to prove if z + n = n , then z = 0 and start with negative n's?
Why are they negative?
Why is it not n = 0 + n by Axiom A.3
= (-n + u) + (n) by assumption</p>
<p><strong>EXAMPLE:</strong></p>
<p>Proposition 1.1. Uniqueness of the Additive Identity</p>
<p>If z is an integer with the property that
z + n = n for any n ∈ Z,
then z = 0.</p>
<p>Axiom A.4 is also about the existence of an integer. We naturally want to know if
the additive inverse is unique. For an integer n, is there an integer u, other than −n,
such that n + u = 0?</p>
<p>Let us say that we have n + u = 0 for some integer u. Then, we can argue as
follows:
−n = 0 + (−n) by Axiom A.3
= (n + u) + (−n) by assumption
= (u + n) + (−n) by Axiom A.2
= u + (n + (−n)) by Axiom A.1
= u + 0 by Axiom A.4
= u by Axiom A.3.
We have found that the additive inverse is unique, so we express this fact in a
proposition.</p>
http://mathoverflow.net/q/1810843Symmetric power of an algebragrffnsnhttp://mathoverflow.net/users/582272014-09-17T06:04:18Z2014-09-17T06:17:49Z
<p>Given an algebra $A$ over $k$ with characteristic zero and a positive integer $n$, the subspace of $A^{\otimes n}$ consisting of all tensors invariant under the action of all permutations $\sigma\in\mathfrak{S}_n$ permuting its factors forms a subalgebra of $A^{\otimes n}$ often denoted by $S^n(A)$, the $n$-th symmetric power of $A$. Is there a simple relationship between the irreducible representations of $A$ and the irreducible representations of $S^n(A)$? The only reference I have found to the symmetric power of an algebra (as opposed to a vector space) is in Etingof's <a href="http://math.mit.edu/~etingof/replect.pdf" rel="nofollow">lecture notes</a> on page 65.</p>
http://mathoverflow.net/q/1810780Does a irreducible set of states necessarily need to be closed in a Markov chain?Vedarunhttp://mathoverflow.net/users/375372014-09-17T04:25:14Z2014-09-17T06:18:46Z
<p>I have come across two different definitions for a 'irreducible set of states' of a Markov chain. </p>
<p>Definition 1: A subset of states $A$ of a Markov chain is irreducible if it is possible to access (in possibly more than one step) each state from the other.</p>
<p>Definition 2: A nonempty set of states $A$ is closed if $x \in A$ and $x \rightarrow y ~ \implies y \in A$. A closed set $A$ is irreducible if $A$ has no proper closed subset.</p>
<p>My question is the following:</p>
<p>(Q): If $A$ is a set of transient states that are accessible from each other, does it also mean $A$ is an irreducible set of states? </p>
<h2>Why do i care?</h2>
<p>The following is perturbation bounds paper for finite Markov chains.
<a href="http://www.jstor.org/stable/3212261" rel="nofollow">http://www.jstor.org/stable/3212261</a></p>
<p>The paper claims the perturbation bounds apply to two Markov chains if both of them have a 'single irreducible set of states which don't necessarily overlap'. Referring to (Q), if a Markov chain has a transient set of states that communicate with each other and another closed set of states that communicate with each other, does the Markov chain have a 'single' irreducible set of states or 'two' irreducible set of states?</p>
<h2>Example:</h2>
<p>$P =
\begin{bmatrix} 0 & 1/2 & 0 & 1/6 & 1/6 & 1/6 \\
0 & 0 & 1/2 & 1/6 & 1/6 &1/6 \\
1/2 & 0 & 0 & 1/6 & 1/6 & 1/6 \\
0 & 0 & 0 & 0 & 1 & 0 \\
0 & 0 & 0 & 0 & 0 & 1 \\
0 & 0 & 0 & 1 & 0 & 0 \\
\end{bmatrix}$</p>
<p>Does this Markov chain have a single irreducible set of states $\{4,5,6\}$ or two irreducible sets $\{1,2,3\}$ and $\{4,5,6\}$ ?</p>
http://mathoverflow.net/q/1810725Local solvability of nonlinear elliptic boundary value problemsG.S.http://mathoverflow.net/users/434452014-09-17T02:13:15Z2014-09-17T07:46:01Z
<p>Malgrange proves the following statement regarding local solvability of (determined or underdetermined) nonlinear elliptic systems:</p>
<p><em>Let $F_i(x,D^\alpha u)=0$ be a nonlinear elliptic system of order $k$ for the function $u_0$ at the point $x_0\in\mathbb{R}^n$. Then there exists $u\in C^k$ that solves the system locally at $x_0$.</em></p>
<p>The system is <em>elliptic</em> for $u_0$ at $x_0$ if its linearisation for $u_0$ at $x_0$ is elliptic.</p>
<p><strong>Question</strong>: Is there an analogous result in the literature for nonlinear (or quasilinear) elliptic boundary value problems?</p>
<p>For instance, let $U$ be an open, bounded set in $\mathbb{R}^n$ and consider a nonlinear (or quasilinear) boundary value problem (with nonlinear or quasilinear boundary data):
\begin{align*}
F_i(x,D^\alpha u)&=0&&\text{on $U$}\\
B_j(x,D^\beta u)&=0&&\text{on $\partial U$},
\end{align*}
where the linearisation of this system is an elliptic linear boundary value problem for some function $u_0$ at some point $x_0\in\partial U$ (satisfies the Lopatinskii-Shapiro condition at $x_0$).</p>
<p><em>Then do we get local solvability at $x_0$ analogously to the theorem of Malgrange</em>? <em>Alternatively, is there a similar or related statement that has been proved in the literature or counter examples</em>?</p>
http://mathoverflow.net/q/1810636Examples of intuition from fields other than Physics to solve math problemsMichaelhttp://mathoverflow.net/users/384482014-09-17T00:02:53Z2014-09-17T04:59:47Z
<p>This is a chaser for the <a href="http://mathoverflow.net/questions/46883/examples-of-using-physical-intuition-to-solve-math-problems">examples of using physical intuition to solve math problems</a> question. </p>
<p>Physical intuition seems to be used relatively frequently for solving math problems as well as stating new interesting ones. What would be examples of interesting Math questions or frameworks or problem solutions derived from field other than Physics?</p>
http://mathoverflow.net/q/1810542Nilradical of a Lie algebra associated to a associative algebraSven Wirsinghttp://mathoverflow.net/users/578042014-09-16T22:05:05Z2014-09-17T09:56:17Z
<p>Let $A$ be a finite dimensional (unital) $K$-Algebra. By $A^{\circ}$ we denote the associated $K$-Lie-algebra of $A$ with respect to the product $a\circ b:=ab-ba$. In addition, we denote by $rad(A^{\circ})$ the largest nilpotent ideal of $A^{\circ}$ and by $J(A)$ the largest nilpotent ideal of $A$ (the Jacobson-radical).</p>
<p>If $A/J(A)$ is separable and commutative there exist a complement $H$ of $J(A)$ in $A$ by the Wedderburn-Malcev-Theorem. I could proove that in this case $J(A)+Z(A)=rad(A^{\circ})$ holds ($Z(A)$ is the center of $A$.).</p>
<p>What is the nilradical of $A^{\circ}$ for an arbitrary finite dimensional (unital) associative algebras $A$?</p>
http://mathoverflow.net/q/1810263Strictly positive solutions of a random linear systemAlihttp://mathoverflow.net/users/447222014-09-16T16:02:48Z2014-09-17T06:53:28Z
<p>Suppose $B\in\mathbb{R}^{m\times n}$ is a random binary matrix with i.i.d entries and $c\in \mathbb{R}^m$ is a strictly positive vector, that is $c_i>0$ for $i=1,2,\cdots m$. Also assume $m<n$, basically meaning that $B$ is a fat matrix. Is there any result (or any suggestion on how to approach the problem) that states for sufficiently large $n$, the linear system </p>
<p>$Bx=c$</p>
<p>has a strictly positive solution almost surely (obviously among the many possible ones, there is one would this property). Basically I am looking for a tail bound like</p>
<p>$\mathbb{P}(\nexists x>0: Bx=c)\leq f(n,m)$</p>
<p>where $f(n,m)\to 0$ as $n \to \infty$ and $m$ stays fixed. Any suggestions on finding a tail bound like above?</p>
http://mathoverflow.net/q/1810001Non-DS circulant graphsMojtaba Jazaerihttp://mathoverflow.net/users/311792014-09-16T08:37:24Z2014-09-17T11:40:51Z
<p>Let $p$ be a prime number greater than or equal to 11. Are there any cospectral non-isomorphic graphs with circulant graphs on $p$ vertices.
Which circulant graphs over prime number of vertices greater than or equal to 11 are determined by the spectrum?</p>
http://mathoverflow.net/q/1808847Representing a number close to 1 with a sum of reciprocals of natural numbersJeremy Kahnhttp://mathoverflow.net/users/82522014-09-15T02:53:49Z2014-09-17T04:59:30Z
<p>For positive integers $n_1, \ldots, n_k$, let $H(n_1, \ldots, n_k)$ denote $1/n_1 + \ldots + 1/n_k$. Let $V(N)$ be the largest possible value of $H(n_1, \ldots, n_k)$ that is less than 1, subject to the condition that $n_1 + \ldots +n_k \le N$. So $V(5) = 5/6$, realized as $1/2 + 1/3$. My question is, how does $1/(1-V(N))$ grow as a function of $N$? In particular, is there a $C$ and a $k$ such that
$$
\frac 1{1-V(N)} \le C N^k\
$$
for all $N$?</p>
http://mathoverflow.net/q/1808194Continuity of the stationary distribution of $M/G/1$ queue w.r.t. the input rateIndigohttp://mathoverflow.net/users/563842014-09-14T09:38:54Z2014-09-17T08:44:51Z
<p>Let $(\lambda_n)_{n\geq0}$ be a sequence of positive numbers such that $\lambda_n\rightarrow \lambda$ as $n\rightarrow +\infty$. These $\lambda_n$ are the parameters of a sequence of Poisson Processes $N(\lambda_n)$. Let $(S_i)_{i\geq0}$ be a sequence of reasonably smooth, positive i.i.d. random variables (say they have finite first and second moment). </p>
<p>To these objects we can associate a sequence of $M/G/1$ queues $(Q_n(t))_{n\geq0}$ by defining the arrival process as $N(\lambda_n)$ and the service times as $(S_i)_{i\geq0}$. If $\rho_n := \lambda_n/\mathbb E [ S_1] < 1$, their stationary distributions exists and are defined as $(Q_n)_{n\geq0}$. Assume also that $\rho := \lambda /\mathbb E[S_1] <1$.</p>
<p>My question is: is it true that $Q_n \stackrel{\text{d}}{\rightarrow} Q$, where $Q$ is the stationary distribution of the $M/G/1$ queue with input rate $\lambda$ and service times $(S_i)_{i\geq0}$?</p>
http://mathoverflow.net/q/18051112Stromquist's 3 knives procedureErel Segal Halevihttp://mathoverflow.net/users/344612014-09-10T08:15:53Z2014-09-17T08:37:18Z
<p>(copied from <a href="http://math.stackexchange.com/questions/916884/stromquists-3-knives-procedure">math.SE</a>)</p>
<p>BACKGROUND: A cake has to be divided among 3 people with possibly different tastes, such that each person receives a single connected piece, and no person prefers another person's piece. In other words, no participant should end up being <em>envious</em> of any other participant. Symbolically, let $\ v_{jk}\ $ be the value of the $k$-th piece to participant $\ j\ $ (the values for each player are based on a continuous measure). We would like:</p>
<p>$$\forall_{j=1\ 2\ 3}\ \ \ v_{jj}\ \ =\ \ \max(v_{j1},\ v_{j2},\ v_{j3})$$</p>
<p>This problem was unsolved for several tens of years, until <a href="http://dx.doi.org/10.2307/2320951" rel="nofollow">Stromquist (1980)</a> suggested the following division protocol:</p>
<blockquote>
<p>A referee moves a sword from left to right over the cake, hypothetically
dividing it into a small left piece and a large right piece.
Each player holds a knife over what he considers to be the midpoint of
the right piece. As the referee moves his sword, the players continually
adjust their knives, always keeping them parallel to the sword.
When any player shouts "cut", the cake is cut by the sword and by
whichever of the players' knives happens to be the middle one of the three.</p>
<p>The player who shouted "cut" receives the left piece. He must be satisfied,
because he knew what all three pieces would be when he said the word.
Then the player whose knife ended nearest to the sword, if he didn't
shout "cut", takes the centerpiece; and the player whose knife was farthest
from the sword, if he didn't shout "cut", takes the right piece. The
player whose knife was used to cut the cake, if he hasn't
already taken the left piece, will be satisfied with whatever piece is left over.
If ties must be broken - either because two or three players shout
simultaneously or because two or three knives coincide - they may be
broken arbitrarily.</p>
</blockquote>
<p>Note that all knives are visible to all players.</p>
<p>It is clear that, if all players play truthfully (according to their own value function), the resulting division is indeed envy-free. My question is: what happens if two players play untruthfully, against their own interest - can they make the third player envious?</p>
<p>In most protocols for cake-cutting among $\ n\ $ participants, the answer is "no", i.e., every player that plays truthfully is guaranteed to receive an envy-free share, regardless of what the other players do. For example, consider the classic protocol for 2 players: "I cut, you choose". I (the cutter) have to cut the cake to two pieces that I consider to be of equal value, but, even if I cut the cake in a very strange manner to two very unequal pieces (even against my own interest), <em>you</em> still have a safe strategy - you just pick the piece that you consider to be more valuable, and you are guaranteed to feel no envy. In other words, the cut-and-choose protocol (and most other cake-cutting protocols) is <em>safe</em> for truthful players.</p>
<p>So, my question is: is Stromquist's procedure indeed safe for truthful players? I.e. does it guarantee that every single player playing by the rules feels no envy, regardless of what the other players do?</p>
<p>EDIT: Here is the problematic scenario I had in mind when asking.</p>
<p>Suppose there are two evil players - Kunning (K) and Liar (L), who want to hurt the good player Marge (M). Initially K and L put their knives close to the sword (S), like this:</p>
<pre><code>|----------SKL------M--------|
</code></pre>
<p>Now Marge knows that if she remains quiet, she will get the piece between L and the right border, which is larger than the piece to the left of S, so she remains quiet. But then L moves his knives <em>discontinuously</em> to the right, like this:</p>
<pre><code>|----------SK------LM--------|
</code></pre>
<p>And at the same moment, K shouts "cut". Now the piece to the right of L is smaller than the piece to the left of S, so Marge should shout "cut" now, but there is 50% chance that the protocol will give the piece to the left of S to K, who shouted at the same time, and Marge will envy him.</p>
<p>This scenario is possible only if L is not truthful. Why? Because a cake is assumed (as usual) to be non-atomic - the value of every subset of zero length is zero. Hence the value to the left of the sword is a continuous function of time, and the middle point of the part to the right of the sword is also a continuous function of time. But, if a player is not truthful, he may decide to make the position of his knife a discontinuous function.</p>
<p>So my more specific question is: is my description of the above scenario correct? If it is, how can the procedure be corrected? Maybe by requiring that the location of each knife is a continuous function of time?</p>
<p>EDIT 2: In second reading, I see that Stromquist indeed mentioned that "the players <strong>continually</strong> adjust their knives".</p>
http://mathoverflow.net/q/1785962Asymptotic property of a quadratic formMichael Fan Zhanghttp://mathoverflow.net/users/425112014-08-15T08:56:03Z2014-09-17T08:18:59Z
<p>suppose $x=\Delta$, $y=M \Phi \Delta$, where $\Delta\in N\times 1$, $M^T=M \in N \times N$ and $\Phi^T=\Phi \in N \times N$. Define $Z=xy^T+yx^T$. It is known from my previous question that $Z$ has two eigenvalues, one is positive and the other is negative and they are given by</p>
<p>$y^Tx+\sqrt{x^Txy^Ty}$ and $y^Tx-\sqrt{x^Txy^Ty}$.</p>
<p>My question is if we have the following result:</p>
<p>$y^Tx+\sqrt{x^Txy^Ty}=\mathcal{O}(\|\Delta\|^2)$, as $\|\Delta\|\rightarrow \infty$.</p>
<p>Based on my simulations, if increases the magnitude of the elements of $\Delta$, $y^Tx+\sqrt{x^Txy^Ty}$ grows linearly w.r.t. the increases of $\|\Delta\|^2$.</p>
http://mathoverflow.net/q/1609830Preserving Predimension Functions under Functional Convergencesuser47697http://mathoverflow.net/users/02014-03-21T01:58:23Z2014-09-17T05:28:42Z
<p><strong>Definition 1.</strong> If $\mathcal{L}$ is a countable relational language, a <strong>predimension class</strong> $C$ is a class of $\mathcal{L}$-structures with the following properties:</p>
<p><strong>C1:</strong> $\forall M\in C~~~|M|<\aleph_{0}$</p>
<p><strong>C2:</strong> $|\frac{C}{\cong}|\leq \aleph_{0}$</p>
<p><strong>C3:</strong> $C$ is closed under substructure.</p>
<p><strong>C4:</strong> $C$ is closed under isomorphism.</p>
<p><strong>Definition 2.</strong>
A <strong>predimension function</strong> $\delta:C\longrightarrow \mathbb{R}^{\geq 0}$ on the predimension class $C$ is a function with the following properties:</p>
<p><strong>P1:</strong> $\delta (\emptyset)=0$
</p>
<p><strong>P2:</strong> $\forall M,N\in C~~M\cong N\Longrightarrow \delta (M)=\delta (N)$
</p>
<p><strong>P3:</strong> $\forall M,N,P,Q\in C$</p>
<p>$Dom(M)=Dom(P)\cup Dom(Q)~,~Dom(N)=Dom(P)\cap Dom(Q)$</p>
<p>$\Longrightarrow\delta (M)+\delta (N)\leq \delta (P)+\delta (Q)$</p>
<p><strong>P4:</strong> $\neg \exists \{ M_{i}\}_{i\in \omega}\subseteq C~~~;~~~\forall i\in \omega~~~(M_{i}\subseteq M_{i+1}\Longrightarrow \delta (M_i)>\delta (M_{i+1}))$</p>
<p><strong>Remark 1.</strong>
Finding predimension preserving transformations is important for producing various (non-linear) predimension functions and geometries with special properties. An example of such a special geometry is Hrushovski's amalgamation construction for refuting Zilber's Trichotomy Conjecture. The following lemma is about a predimension preserving transformation.</p>
<p><strong>Lemma.</strong>
Convex functions preserve predimensions. Precisely if $\delta:C\longrightarrow \mathbb{R}^{\geq 0}$ is a predimension function and $f:\mathbb{R}^{\geq 0}\longrightarrow \mathbb{R}^{\geq 0}$ is a function with the following properties:</p>
<p><strong>F1:</strong> $f(0)=0$</p>
<p><strong>F2:</strong> $\forall x~~~f'(x)\geq 0$</p>
<p><strong>F3:</strong> $\forall x~~~f''(x)\leq 0$</p>
<p>Then $fo\delta:C\longrightarrow \mathbb{R}^{\geq 0}$ is a predimension function.</p>
<p><strong>Proof.</strong>
Easy.</p>
<p><strong>Remark 2.</strong>
The above lemma provides a simple tool for producing a wide range of non-linear predimension functions from a given predimension. For example one can produce a complicated predimension function $M\mapsto Ln(|M|+1)$ using the trivial predimension $M\mapsto |M|$ and the convex transformation $x\mapsto Ln(x+1)$ on each predimension class $C$.</p>
<p><strong>Main Question.</strong> Which type of functional convergences can preserve predimension functions? (i.e. The limit of the predimension functions is a predimension itself.) </p>
<p>By a simple observation stated in my answer, the pointwise convergence cannot preserve the p4 property of predimensions. </p>
<p>It seems the same "weakness" exists in uniform convergence too. In the below diagram one can see an imaginary situation that each function $\delta_n$ is a predimension on $C$ (note that each $\delta_n$ is descending just on finite steps which doesn't violate p4) but $\delta$ which is the unform limit of the sequence $\{\delta_n\}_{n\geq 1}$ is not a predimension on $C$ because it is strictly descending on an infinite increasing chain of structures in $C$.</p>
<p><img src="http://i.stack.imgur.com/p0bF1.png" alt="enter image description here"></p>
<p><strong>Question 1.</strong>
Does the uniform convergence preserve predimensions?
</p>
<p>The positive side of the main question is much more important than finding counterexamples for "weak" convergences. Thus if the answer of the question 1 is negative, it is interesting to ask:
</p>
<p><strong>Question 2.</strong>
Is there a "strong" version of functional convergences which can preserve predimensions?</p>
<p><strong>Remark 3.</strong> For the answer of the question 2 I am looking for those convergences which work for an arbitrary predimension class and an arbitrary sequence of predimensions on it.</p>
http://mathoverflow.net/q/1607919Number of standard Young tableaux with fixed corner entryAlex R.http://mathoverflow.net/users/9342014-03-19T01:29:47Z2014-09-17T06:28:50Z
<p>For a partition $\lambda=(\lambda_1\geq \lambda_2\geq\ldots\geq \lambda_k)$ of $n$, let the set of standard Young tableau of shape $\lambda$ be denoted by $SYT(\lambda)$ with boxes at $(i,j)$ denoted by $B_{ij}$ taking in distinct values in $\{1,2,\ldots,n\}$. Also let $f_\lambda:=|SYT(\lambda)|$. Finally, let $N_{ij}(k)$ be the set of young tableau of shape $\lambda$ with $B_{ij}=k$. We will exclusively be talking about boxes on the right edge of the Young tableaux (boxes that have no boxes directly south or east of them). We will call these corner boxes. In the diagram below, 8,9 and 10 are corner boxes. On the other hand, 5 and 6 are not corners. </p>
<p><img src="http://i.stack.imgur.com/XBUfB.png" alt="enter image description here"></p>
<p>The usual branching rule says that </p>
<p>$$f_\lambda=\sum_{\mu\rightarrow\lambda}f_\mu,$$</p>
<p>where the sum is taken over all partitions $\mu$ of $n-1$ that are contained ($\rightarrow$) in $\lambda$. It is easy to see that when $(i,j)$ is a corner box, $N_{ij}(n)=f_{\lambda- (i,j)}$, the number of SYT of shape $\lambda$ minus the corner box in question. This kind of reasoning can be extended to $N_{ij}(n-1),N(n-2)$. Unfortunately, $N_{ij}(n-k)$ becomes exceeding difficult to compute for $k>2$. </p>
<p>I would like to ask what is known about $N_{ij}(k)$, when $(i,j)$ is a corner box. Specifically, are there any recurrences that these satisfy? Are they at all related to coefficients of certain weighted hook-walk algorithms? Have they been considered in any enumeration problems? Does this question have an answer for certain fixed nontrivial shapes $\lambda$?</p>
http://mathoverflow.net/q/870095Internal equivalence implies weak equivalence for Frechet Lie groupoids?David Robertshttp://mathoverflow.net/users/41772012-01-30T06:21:59Z2014-09-17T10:38:50Z
<p>It is a <a href="http://books.google.com.au/books?id=87vtu4HbdawC&lpg=PA114&ots=VtyWCoKPHj&dq=local%20bisections%20lie%20groupoid&pg=PA129#v=onepage&q&f=false" rel="nofollow">known theorem</a> that an internal equivalence of Lie groupoids (finite dimensional manifolds!) - that is an equivalence in the 2-category of Lie groupoids, smooth functors and transformations - is a weak equivalence: a fully faithful essentially surjective functor. Here we say a functor is essentially surjective is the map expressing this fact is not only surjective but a surjective <em>submersion</em>.</p>
<p>I'm interesting an analogues of this fact for <em>Frechet</em> Lie groupoids - groupoids internal to the category of Frechet manifolds, where the source and target are submersions of Frechet manifolds (this is stronger than surjective on tangent spaces - need local charts where the map looks like projection out of a direct sum).</p>
<p>The proof for Lie groupoids relies on the fact that Lie groupoids admit local bisections through every arrow $g$. These are maps $X_0 \supset U \stackrel{f}{\to} X_1$ where $s(g) \in U$, an open subset of $X_0$ such that $f(s(g)) = g$, and $t\circ f:U \to X_0$ is an open embedding. So far so good, the existence of local bisections depends on the characterisation of a submersion as locally a projection out of a direct sum, but with a small twist, which I haven't thought about, but don't expect to cause trouble.</p>
<p>The problem is showing that the 'surjective implies submersion' part of the proof, which <a href="http://books.google.com.au/books?id=87vtu4HbdawC&lpg=PA114&ots=VtyWCoKPHj&dq=local%20bisections%20lie%20groupoid&pg=PA129#v=onepage&q&f=false" rel="nofollow">uses</a> a different characterisation of submersions of finite-dimensional manifolds, namely that admit local sections through every point in their codomain. This is false in the general Frechet case, but it doesn't mean the proof couldn't be rewritten to use the other characterisation of submersions (locally a projection).</p>
<p>My question is: has this been done?</p>
http://mathoverflow.net/q/527265Automorphisms of non-abelian groups of order p^3RDKhttp://mathoverflow.net/users/67612011-01-21T05:01:11Z2014-09-17T08:23:01Z
<p>There are two non-abelian groups of order p^3, namely, semi-direct product of Z/pZ x Z/pZ by Z/pZ and semi-direct product of Z/(p^2)Z by Z/pZ. What are the automorphism groups of these groups?</p>
http://mathoverflow.net/q/3110920Is there an explicit construction of a free coalgebra?Bruce Westburyhttp://mathoverflow.net/users/39922010-07-08T20:09:15Z2014-09-17T08:23:20Z
<p>I am interested in the differences between algebras and coalgebras. Naively, it does not seem as though there is much difference: after all, all you have done is to reverse the arrows in the definitions. There are some simple differences: </p>
<p>The dual of a coalgebra is naturally an algebra but the dual of an algebra need not be naturally a coalgebra. </p>
<p>There is the Artin-Wedderburn classification of semisimple algebras. I am not aware of a classification even of simple, semisimple coalgebras. </p>
<p>More surprising is: a finitely generated comodule is finite dimensional.</p>
<p>This question is about a more striking difference. The free algebra on a vector space $V$ is $T(V)$, the tensor algebra on $V$. I have been told that there is no explicit construction of the free coalgebra on a vector space. However these discussions took place following the consumption of alcohol. What is known about free coalgebras?</p>