Recent MathOverflow Questions

Length of simple closed curve in half-translation surface

Math Overflow Recent Questions - Thu, 10/12/2017 - 15:47

Let $R$ be a Riemann surface of genus $g\ge 2$ and $q$ an holomorphic quadratic differential on $R$. Together they determine a semi-translation structure: an atlas on $X$ such that its changes of charts are of the form $z\mapsto \pm z+c$ and a singular flat metric $|q|$ on $X$.

Suppose that $q$ has at least one singularity of odd order: I can't completely grasp what the $-1$ holonomy implies when considering the lengths of simple closed curves on $(X,q)$. In particular, let $c\subset X$ be a closed simple geodesic for $|q|$ which doesn't meet any singular point of $|q|$. Then, is it true that there is always a cylinder in $(X,q)$ foliated by closed geodesics parallel to $c$ (as in the case of translation surfaces with trivial holonomy)?

If no, then is it still always possible to assume the existence of a concatenation of saddle connections of $q$ parallel to $c$ and with the same length?

Example of irrational number with a pattern in digits

Math Overflow Recent Questions - Thu, 10/12/2017 - 15:03

Suppose I created the following random number generator.

A trusted person choose a irrational number. That can easily defined and computed by a computer. Like square root of a prime.

Every time the random number generator is called it calculate the first digit, then the second digit and it goes on.

On a given moment the random number generator is on digit N. An attacker saw the last M digits. (M < N)

Can you give me an example of a bad choice of irrational number that creates a pattern that is easy to guess some or all next numbers without knowing the number? (Only the last M digits is allowed to use in build the pattern)

increasing inter-class distances results in decreasing linear regression error

Math Overflow Recent Questions - Thu, 10/12/2017 - 12:35

Let $\{\mathbf{x}_i, y_i \}$ be a set of binary-labeled samples ($\mathbf{x}_i \in \mathbb{R}^d, y_i \in \{a,b\}, a,b\in\mathbb{R}$). Let $\{ \mathbf{x}'_i, y_i \}$ be also such a set. Define $\mathbf{X} = [\mathbf{x}_1 \dots \mathbf{x}_N]^T , \mathbf{y}=[y_1 \dots y_N]^T$ and similarly for $\mathbf{X}'$. Define $\beta = (\mathbf{X}^T \mathbf{X})^{-1}\mathbf{X}^T \mathbf{y}$ and $\beta' = (\mathbf{X}'^T \mathbf{X}')^{-1}\mathbf{X}'^T \mathbf{y}$. Define $\widehat{\mathbf{y}} = \mathbf{X} \beta$, $\pmb{\epsilon} = \widehat{\mathbf{y}} - \mathbf{y}$, and similarly for $\widehat{\mathbf{y}'}, \pmb{\epsilon}'$.

Then how can we prove the following conjecture?

Conjcture. (a) Assume for any $i,j,k$ with $y_i = y_j \neq y_k $, $$ ||\mathbf{x}_i - \mathbf{x}_j || = ||\mathbf{x}'_{i} - \mathbf{x}'_{j}||, \qquad || \mathbf{x}_i - \mathbf{x}_k || < || \mathbf{x}'_{i} - \mathbf{x}'_{k} || $$ Then $||\pmb{\epsilon}|| > ||\pmb{\epsilon}'||$.

Probability perspective. Now we take a probabilistic perspective. Let $N$ be a natural number. Let $x$ be a random vector such that the above $\mathbf{x}_i$ are the realizations of it. Also define similarly $x'$. Let $y$ be a random vector that models $y_i$. (I.e., $y = \text{label}(x) = \text{label}(x')$.) Define $\widehat{y} = x^T\beta$ and $\widehat{y'} = x'^T\beta'$ where $$ \beta = (\mathbf{X}_n^T\mathbf{X}_N)^{-1}\mathbf{X}_N^T\mathbf{y}_N $$ with $X_n = [\mathbf{x}_1 \cdots \mathbf{x}_N]^T$ for the realizations $\mathbf{x}_i$ of $x$ and $\mathbf{y}_N = [y_1 \dots y_N]^T$ ($y_i = \text{label}(\mathbf{x}_i)$), and $\beta'$ is defined similarly. Define $\epsilon = \widehat{y} - y$ and similarly for $\epsilon'$.

Conjecture. (b). Assume $||\mathbb{E}[x|y=0] - \mathbb{E}[x|y=1]|| < ||\mathbb{E}[x'|y=0] - \mathbb{E}[x'|y=1]|| $ while $ \text{var}(x|y=i) =\text{var}(x'|y=i)$ for $i=0,1$. Then $$ \text{var}(\epsilon) > \text{var}(\epsilon'). $$

(c) The above holds true when $N \to \infty$.

Question. How can I possibly approach this type of problem? What kind of techniques should I consider? Should I ease or changethe problem?

Basically what the conjecture says is that if we increase inter-class distances while preserving intra-class variances, the regression error decreases. Intuitively I think this is quite clear especially for simple linear regression with one feature variable.

Why is the root poset is graded by height?

Math Overflow Recent Questions - Thu, 10/12/2017 - 12:22

Let $\Phi$ be a finite crytallographic root system. Let $\Phi^+$ be the positive roots and $\alpha_1$, ..., $\alpha_n$ be the simple roots. For $\beta = \sum c_i \alpha_i$ in $\Phi^+$, we define $h(\beta) = \sum c_i$. For $\beta = \sum c_i \alpha_i$ and $\gamma = \sum d_i \alpha_i$, we define $\beta \preceq \gamma$ iff $c_i \leq d_i$ for all $i$. Many sources state that $\Phi^+$ is graded by $h$. The nontrivial part of this statement is that, if $\alpha \leq \gamma$ with $h(\gamma) - h(\alpha) \geq 2$, then there is a root $\beta$ with $\alpha \leq \beta \leq \gamma$. Could someone give me a proof or reference to a proof, other than type by type check?

To show that I haven't been completely lazy: Humphreys defines $\Phi^+$ and $h$ but doesn't state that $h$ grades $\Phi^+$, Bjorner and Brenti define a different, unrelated partial order on $\Phi^+$ which they call the root poset. Cuntz and Stump cite Armstrong Section 5.4.1 but it doesn't seem to be in there.

Eilenberg-Zilber-type theorem for good fiber products?

Math Overflow Recent Questions - Thu, 10/12/2017 - 09:46

My question is:

If $p\colon X \to B$, $q\colon Y \to B$ are proper submersions, is there a characterization of $H_*(X \times_B Y)$ in terms of $H_*(X)$, $H_*(Y)$, $H_*(B)$ that is simpler than the Eilenberg-Moore spectral sequence?

Ideally, what I would like is a chain complex $A$ built from $C_*(X)$, $C_*(Y)$, $C_*(B)$ with a map $A \to C_*(X \times_B Y)$ which descends to an isomorphism. But I'm willing to compromise -- it's OK if this map doesn't descend to an isomorphism. Also, I don't care too much about what version of homology it is, and you can change the hypotheses on $p, q$ if you want (e.g. require them to be surjective).

What upper bounds are known on the number of non-isomorphic cycle matroids?

Math Overflow Recent Questions - Thu, 10/12/2017 - 01:15

For $n\in\mathbb{N}^{+}$, let $c_{n}$ denote the number of simple non-isomorphic cycle matroids of graphs on $n$ vertices. That is, let

$$A(n)=\{M(G)\;;\;G\text{ is a graph on }n\text{ vertices}\},$$

and let $B(n)$ be a largest subset of $A(n)$ such that no two elements of $B(n)$ are isomorphic (as matroids). Then

$$c_{n}\equiv|B(n)|.$$

(Here $M(G)$ denotes the cycle matroid of graph $G$. )

A simple upper bound for $c_{n}$ would be something like $2^{2^{\binom{n}{2}}}$, since the ground set of the cycle matroid of a graph on $n$ vertices is of size at most $\binom{n}{2}$.

Are there any better upper bounds known for $c_{n}$?

Edit: It looks like I am asking for the number of non-$2$-isomorphic graphs on $n$ vertices. Whitney's 2-isomorphism theorem (version of Oxley's Matroid Theory) states: "Let $G$ and $H$ be graphs having no isolated vertices. Then $M(G)$ and $M(H)$ are isomorphic if and only if $G$ and $H$ are $2$-isomorphic."

Intuitively, this number looks like it should be significantly smaller than the number of non-isomorphic graphs on $n$ vertices, since non-isomorphic graphs can be $2$-isomorphic.

Do we know of upper bounds on the number of non-$2$-isomorphic graphs on $n$ vertices? (Should I ask this as a separate question?)

Orthogonal representations of graphs

Math Overflow Recent Questions - Tue, 10/10/2017 - 11:28

A faithful orthonormal representation of a graph $G=(V,E)$ on $n$ vertices $\{1,2,\dotsc,n\}$ is an assignment of unit vectors $v_1,v_2,...,v_n \in \mathbb{R}^d$ to the vertices of $G$ such that $\langle v_i,v_j \rangle =0 \Leftrightarrow ij \in E(G)$, and in addition $|\langle v_i , v_j \rangle| \neq 1$ if $i \neq j$, i.e., distinct vertices are assigned non-parallel vectors. Note that this definition of orthonormal representation is slightly rarer in the literature and differs (by graph complementation) from the definition in [1] where $ij \in E(\bar{G}) \Rightarrow \langle v_i , v_j \rangle = 0$.

The question is: Given a graph $G$ that has a faithful orthonormal representation in dimension $d$, form a new graph $G'$ by deleting an edge $uv$ from $G$. Does $G'$ then also have a faithful orthonormal representation in the same dimension $d$?

[1] L. Lovász, On the Shannon Capacity of a Graph, IEEE Trans. Inf. Theory, 25 (1):1-7 (1979).

Leaves with nontrivial holonomy of Linear foliations of $\mathbb{R}^n \setminus \{0\}$

Math Overflow Recent Questions - Tue, 10/10/2017 - 01:53

A linear $1$-form on $\mathbb{R}^n$ is a $1$-form $\alpha=\sum_i P_i(x_1,x_2,\ldots,x_n)dx_i$ such that each $Pi$ is in the linear form $P_i=\sum_j a_{ij}x_j$. A linear foliation of $\mathbb{R}^n \setminus \{0\}$ is a foliation tangent to the kernel of a linear $1$-form.

As I learned from this answer, there are linear $1$-forms which are Frobenius integrable but are not closed $1$-form.

Is there a complete classification of linear foliations? In particular, is there a linear foliation of $\mathbb{R}^n \setminus \{0\}$ which has a (compact) leaf with non trivial holonomy?

I think that this situation can not occurs when the corresponding $1$-form $\alpha= \sum_i \sum_j(a_{ij}x_j)dx_i $ is a closed $1$-form.(Equivalently the matrix $(a_{ij})$ is a symmetric matrix)

A Tarski group extension

Math Overflow Recent Questions - Tue, 10/10/2017 - 01:35

I was wondering if it is possible to have the following structure for a group $G$:

  • $G'$ is a Tarski monster (or some other minimal non-Abelian group, namely a non-Abelian group having all proper subgroups Abelian).

  • $G/G'$ characteristically simple and infinite (maybe an elementary Abelian $p$-group).

The first two properties may be satisfied by using a paper of Obratsov, I think, since one can construct a nice Tarski with a particular $Out(G)$.

  • There is a subgroup $H$ of $G$ which is neither normal or Abelian.

Bonus property

  • There is a subgroup of finite index, having all proper subgroups either normal or Abelian: obviously such a subgroup contains $G'$.

Determining the Mordell-Weil group of an universal elliptic curve

Math Overflow Recent Questions - Tue, 10/10/2017 - 00:59

Let $K$ be a number field and let $K(a,b)$ be the field of rational functions with two indeterminates over $K$. Consider the elliptic curve $E$ over $K(a,b)$ defined by the Weierstrass equation \begin{equation*} E : y^2=x^3+ax+b. \end{equation*} What is the torsion subgroup and the rank of the Mordell-Weil group of $E$ over $K(a,b)$?

In the case $K=\mathbf{Q}$, this Mordell-Weil group is trivial because $E$ admits specializations $a,b \in \mathbf{Q}$ such that $E_{a,b}$ has trivial Mordell-Weil group. In the general case, I would like to show similarly the existence of $a,b \in K$ such that $E_{a,b}$ has trivial Mordell-Weil group over $K$, but I don't know how to proceed.

Since $K(a,b)$ is a finitely generated field, the Lang-Néron theorem tells us that the Mordell-Weil group of $E$ is finitely generated, but I'm not familiar enough to tell whether the proof actually gives us a way to compute this Mordell-Weil group.

Dynkin diagram and Lie algebras

Math Overflow Recent Questions - Tue, 10/10/2017 - 00:25

Affine Kac Moody algebras and Hyberbolic Kac Moody algebras were classified using Dynkin diagrams like finite dimensional simple Lie algebras over $\mathbb{C}$ . Is this classification using Dynkin diagram extents further to bigger class of Lie algebras? or is there any other class of Lie algebras or Lie super algebras which were characterized interms of some Dynkin diagrams?

Average number of integer points in a polytope

Math Overflow Recent Questions - Tue, 10/10/2017 - 00:19

$n$ is a parameter.

Pick a polytope $P$ in $\Bbb R^n$ defined by polynomial in $n$ many linear inequalities with coefficient size bound by polynomial in $n$ (selected from all such inequalities uniformly).

Pick an uniformly random full rank lattice $L$ in $\Bbb Z^n$ with generator basis bound by coefficients polynomial in $n$.

What is the probability that size of $|L\cap P|$ exceeds $n^c$ for some $c>0$?

Does the answer change much if the polytope is convex?

Study of vortex type equation instead rational curves?

Math Overflow Recent Questions - Mon, 10/09/2017 - 22:56

On Hamiltonian Floer theory we apply the symplectic vortex equation instead of J-holomorphic curves

My question is in which theory can we replace the vortex type equation instead rational curves

Any reference is welcomed

formalization of coordinate-free linear algebra in a proof assistant

Math Overflow Recent Questions - Mon, 10/09/2017 - 22:31

I am aware of projects that formalize linear algebra in existing proof assistants (i.e. Coq), but it seems like most of them are based on matrices. I was wondering if it's done in a coordinate-free way, with operations like taking tensor/wedge powers and dualizing. If so, at least in the finite dimensional case, can one coordinatize and work with matrices?

Using this definition of "closeness", how close is $L$ to $V$?

Math Overflow Recent Questions - Mon, 10/09/2017 - 21:37

For a class $W$:

Let $\mathcal{T}_0(W)=W$.
Let $\mathcal{T}_{\alpha+1}(W)=\{x\in V:x\subseteq\mathcal{T}_\alpha(W)\}\cup\mathcal{T}_\alpha(W)$.
Let $\mathcal{T}_{\beta}(W)=\bigcup_{\alpha\in\beta}\mathcal{T}_\alpha(W)$ for limit ordinals $\beta$.

Let $\mathrm{K}(W)=\min\{\alpha:\mathcal{T}_\alpha(W)=V\}$ (if such a minimum exists). The smaller this value is, the "closer" $W$ is to $V$.

With this definition, $\mathrm{K}(L)$ is guaranteed to be either a limit ordinal or $0$. Quite clearly $\mathrm{K}(L)=0\Leftrightarrow V=L$.

However, assuming $V\neq L$, is it possible to prove what $\mathrm{K}(L)$ is? Are there any models of ZFC in which it does not exist? (I.E. $M\models\forall\alpha\in\mathrm{Ord}(\mathcal{T}_\alpha(L)\neq V)$)

A couple facts that may help:

  • $\mathcal{T}_\alpha(L)$ is transitive for every $\alpha$ (Proven by transfinite induction)
  • $V_{\omega+\alpha}\in\mathcal{T}_\alpha(L)$ (Proven also by transfinite induction)
  • $\mathrm{K}(L)\neq\alpha+1$ for any $\alpha$ (Transfinite induction)
  • $V\setminus L$ is either the empty set or a proper class (Deduction using the fact that $L$ is transitive and a model of the axiom of pairing)

"Quasiconformal" projections from Heisenberg group to the plane

Math Overflow Recent Questions - Mon, 10/09/2017 - 21:16

Let $G$ be the 3-dimensional Heisenberg group equipped with its Carnot-Caratheodory subriemannian metric $d_{G}$. Let $U$ be a domain in $G$ of the form $V \times I$, where $V$ is an open subset of $\mathbb{R}^{2}$ and $I$ is an open interval (so $I$ is the third coordinate in $G$ corresponding to the center of the group). I'm going to consider uniformly continuous maps $f: U \rightarrow V$. If $f$ is Lipschitz then the Pansu differentiation theorem tells us that $f$ has a Pansu derivative $m$-a.e., where $m$ is the Haar measure on $G$. I want to try to get a similar statement below.

For $x \in V$ let $I_{x} = \{x\} \times I$ Let $d_{\mathbb{R}^{2}}$ denote Euclidean distance on $\mathbb{R}^{2}$. Now I want to consider instead a "quasiconformal" map $f: U \rightarrow \mathbb{R}^{2}$ in the following sense: there is a constant $C \geq 1$ independent of $r$ such that for each $x, y \in V$, $$ \frac{\sup\{d_{\mathbb{R}^{2}}(f(I_{x}),f(I_{y})): d_{G}(I_{x},I_{y}) = r\}}{\inf\{d_{\mathbb{R}^{2}}(f(I_{x}),f(I_{y})): d_{G}(I_{x},I_{y}) = r\}} \leq C $$ (here I'm taking the Hausdorff distance between compact sets). I want to know what I can say about differentiability or absolute continuity properties of $f$.

The main thing I want to know is that if $A \subseteq V$ has measure 0 in $\mathbb{R}^{2}$ then does $f(A \times I)$ have measure 0 in $\mathbb{R}^{2}$? The analogous statement for $\mathbb{R}^{3}$ replacing $G$ is true just by standard quasiconformal mapping theory so I expect it should be true here as well but don't know if it is done somewhere in the literature.

Edit: Let me clarify my goal. The corollary that I want from the above statement is that for each $t \in I$ (or a.e. $t \in I$, that may be enough) the image $f(A \times \{t\})$ has measure 0 in $\mathbb{R}^{2}$, i.e., $f$ is absolutely continuous along horizontal planes. As part of the situation I'm considering we can assume that $f$ is injective on the horizontal planes $V \times\{t\}$. If $G$ is replaced by $\mathbb{R}^{3}$, the hypotheses imply that $f$ is quasiconformal as a map from $\mathbb{R}^{2}$ to $\mathbb{R}^{2}$ when restricted to horizontal planes and the conclusion follows. Of course this tactic does not work with the subriemannian distance $d_{G}$ on $G$.

Poincare Inequality on non compact manifold

Math Overflow Recent Questions - Mon, 10/09/2017 - 20:55

Let $(X,g)$ be a non compact Riemannian manifold, such that its closure $\bar X=X\cup Y$ is a compact manifold with boundary $Y$.

Q: For the Poincare inequality $$\|u\|_{L^2}\leq C \|\nabla u\|_{L^2},$$ for any $u\in C^1_c(X)$, how to determine the Constant $C$ ?(what will it be related to ? e.g. dimension, diameter or volume?)

This is a revised version.

Thanks for the Arun Debray's comments.

Gaussian Elimination in Computer Science [on hold]

Math Overflow Recent Questions - Mon, 10/09/2017 - 20:38

I been trying to solve a few problems that ask me to give answers with certain contrains (for example, all numbers in the answer must be positive and real) using Gaussian elimination, but I have found myself with the following issue at least twice now:

I can produce a tringualar superior matrix using Gauss-elimination.

If there are no empty-rows, then I can solve the matrix and check if certain constrains are full-filled looking at the answer.

However, if rank of the matrix is smaller than n (a.k.a some row is now empty), then I don't know how to proceed.

Generally speaking, I would be able to do this by hand. Just write down the equations and see how far can you take them.

My problem arises when I am tryng to code an algorithm to solve this kind of problems.

Is there any kind of practical solution to this?

Quotients of Grassmannians

Math Overflow Recent Questions - Mon, 10/09/2017 - 20:31

Let $G=SL_n(\mathbb C)$ and $T$ be a maximal torus. Then the Grassmannians $Gr(r,n)$ and $G(n-r,n)$ are isomorphic. Now for the left action of the torus on each of them can we say that the GIT quotients $T \backslash \backslash G(r,n) (\mathcal L_{n\omega_r})$ and $T \backslash \backslash G(n-r,n) (\mathcal L_{n\omega_{n-r}})$ are isomorphic ? Here $\omega_r$ and $\omega_{n-r}$ are the fundamental weights associated to the simple roots $\alpha_r$ and $\alpha_{n-r}$ respectively and the quotient means the smistable quotients.

Elliptic operator becomes Fredholm

Math Overflow Recent Questions - Mon, 10/09/2017 - 20:07

Let $X$ be a Riemannian $n$-manifold with tubular end $\mathbb R^+\times Y$, where $Y$ is a closed $n-1$-manifold. Suppose $L:L^{p,w}_2(X)\to L^{p,w}(X)$ is an elliptic operator, here $L^{p,w}_i$ is a weighted $L^{p}_i$ space.

Q: WHY: If $L$ acting on $L^{p,w}_2(\mathbb R\times Y)\to L^{p,w}(\mathbb R\times Y)$ is Fredholm, then $L:L^{p,w}_2(X)\to L^{p,w}(X)$ is Fredholm?

Pages

Subscribe to curious little things aggregator