Recent MathOverflow Questions

Subcategories of Grp and Mod(A)

Math Overflow Recent Questions - Mon, 06/19/2017 - 06:01

I am looking for

• a full subcategory of $\mathrm{Grp}$ or $\mathrm{Mod(A)}$ (where $\mathrm{A}$ is a commutative ring) having the amalgamation property but not general pushouts.

• a full subcategory of $\mathrm{Grp}$ or $\mathrm{Mod(A)}$ without the amalgamation property.

(A category has the amalgamation property if spans can always be completed to commutative square, equivalently if spans have a compatible cocone.)

Honestly, I am not looking for very strange constructions in which one takes away precisely the pushouts you have, I am looking for very natural or at least natural categories that one encounters in real mathematical life.

Why can't there be hyperkaehler structure in 2d? [migrated]

Math Overflow Recent Questions - Mon, 06/19/2017 - 05:52

It seems to me that there can be almost quaternionic structure on a manifold of two real dimensions, i.e., that generated by ($I,i\sigma_a$) where $I$ is the 2$\times$2 identity matrix and $\sigma_a$ are the Pauli matrices.

The three complex structures $J_a=i\sigma_a$ give rise to three Kaehler forms using $$\Omega_a={(J_a)_{\mu}}^{\nu}g_{\nu\rho}dx^{\nu}\wedge dx^{\rho}$$ Why is it then true that we cannot have hyperkahler structure in two real dimensions?

Can generalization of a generalization Pascal theorem, Pappus theorem to Higher Dimensions? [on hold]

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

Please see a chain of six circles associated with a conic. This is a generalization of Pascal theorem, Pappus theorem. I reformulate as following:

Let $1, 2, 3, 4, 5, 6$ be six arbitrary points in a hyperbola. Let $1'$ be arbitrary point in the hyperbola. The circle $(121')$ meets the hyperbola at point $2'$. The circle $(232)$ meets the hyperbola again at $3'$, define points $4', 5', 6'$ similarly. Let circle $(121')$ meets the circle $(454')$ at $A, B$, Let circle $(232')$ meets the circle $(565')$ at $C, D$. Let circle $(343')$ meets the circle $(616')$ at $E, F$. Then six points $A, B, C, D, E, F$ lie on a circle.

Special case:

1. If $1'$ at $\infty$, six circles are six lines, so the theorem is Pascal theorem.

2. If the hyperbola is two lines, and $1'$ at $\infty$ then six circles are six lines, the theorem is Pappus theorem

My question: Can generalization the result above to Higher Dimensions?

Analogies supporting heuristic: Weyl groups = algebraic groups over field with one element?

Math Overflow Recent Questions - Sun, 06/18/2017 - 14:17

There is well-known heuristic that Weyl groups are reductive algebraic groups over "field with one element".

Probably the best known analogy supporting that heuristic is the limit q->1 for number of elements in G(F_q) - for appropriate "m" it holds:

$$\lim_{q->1} \frac { |G(F_q) | } { (q-1)^m} = |Weyl~Group~of~G|$$

For example: $|GL(n,F_q)|= [n]_q! (q-1)^{n}q^{n(n-1)/2}$ so divided by $(q-1)^n$ one gets $[n]_q! q^{n(n-1)/2}$ and at the limit $q->1$, one gets $n!$ which is the size of $S_n$ (Weyl group for GL(n)).

Question What are the other analogies supporting heuristis: Weyl groups = algebraic groups over field with one element ?

Subquestion once googling papers on F_1, I have seen quite an interesting analogy from representation theory point of view - it was some fact about induction from diagonal subgroups of symmetric groups $S_{d_1}\times ... \times S_{d_k} \subset S_n$ where $\sum d_i = n$ and similar fact for $GL(n,F_q)$. But I cannot google it again and cannot remember the details :( (Tried quite a lot - I was sure it was on the first or second page of Soule's paper on F_1 - but it is not there, neither many other papers).

Knowing that total element count is okay, we may ask about counting elements with certain properties - like: m-tuples of commuting elements (MO271752), involutions, elements of order $m$, whatever ... From answer MO272059 one knows that there are certain analogies for such counting, however it seems the limits q->1 are not quite clear.

Question 2 Is there any analogy for counting elements with some reasonable conditions ? Hope to see that count for G(F_q) (properly normalized) in the limit $q->1$ gives answer for Weyl group.

Elliptic Curve, characteristic equation of Frobenius endomorphism relation to isogeny

Math Overflow Recent Questions - Sat, 06/17/2017 - 09:12

Let E be an elliptic curve over $F_p$. Suppose that its j invarient is not supersingular and that $j\neq 0$ or 1728.

Then the modular polynomial $\Phi_l(j,T)$ has a zero $\tilde{\jmath} \in \mathbb{F}_{p^r}$ if and only if the kernel $C$ of the corresponding isogeny $E \mapsto E/C$ is a one-dimensional eigenspace of $\phi^r_p$ in $E[l]$, with $\phi_p$ the Frobenius endomorphism of $E$.

In the proof: Counting points on eliptic curve over finite field page no:236. Conversly, if $\Phi_l(j,\tilde{\jmath} )=0$, then there exists a cyclic subgroup $C$ of $E[l]$ such that the $j$ invariat of $E/C$ is equal to $\tilde{\jmath}\in \mathbb{F}_{p^r}$. Let $E^1$ be an elliptic curve over $\mathbb{F}_{p^r}$ with $j$ invariant equal to $\tilde{\jmath}$. Let $E/C \mapsto E^1$ be an $\bar{\mathbb{F}}_p$ isomorphism and let $f: E \mapsto E/C \mapsto E^1$ be the composite isogeny. It has kernel $C$.

I can see $f$ is defined over $\mathbb{F}_{p^r}$, so this implies existence of an isogeny $E \mapsto E^1$ over $\mathbb{F}_{p^r}$.

How this will imple $C$ is an eigenspace of $\phi^r_p$. How the statement that,"Frobenius endomorphisms over $\mathbb{F}_{p^r}$ satisfies the same characteristic equation" will help to see that $C$ is an eigenspace of $\phi^r_p$.

Please help me to understand this.

Fix point free action and cohomology of group

Math Overflow Recent Questions - Sat, 06/17/2017 - 08:26

I learned that "If $G$ is a finite group acting on $S^n$, the sphere, freely, then $G$ has period cohomology".

My question is: Is there any other similar theorems relating the free action of a finite group and it's cohomology?

maybe this question is too vaguer.

"Canonical" form for gauge equivalence classes of matrices in $\mathfrak{gl}_n(x)$

Math Overflow Recent Questions - Sat, 06/17/2017 - 07:58

Let $\mathfrak{gl}_n(x)= \mathfrak{gl}_n \otimes_\mathbb{C}\mathbb{C}(x)$ be the algebra of matrices taking values in rational functions.

Definition: Two matrices $A, B \in \mathfrak{gl}_n(x)$ are said to be guage equivalent iff there exists an invertible matrix $P \in {GL}_n(\mathbb{C}(x))$ satisfying: $$A=PBP^{-1}+P^{-1}P'$$

The above is easily seen to be an equivaence relation on the matrices in $\mathfrak{gl}_n(x)$.

The classical Jordan decomposition for complex scalar matrices gives a canonical (modulo transposition of blocks) representative for every equivalence class of matrices for the equivalence relation of similarity. My question is basically "is there a similar thing for this case and if there is what is it?".

Question: Can one define a "canonical form" for matrices in $\mathfrak{gl}_n(x)$ modulo gauge equivalence? That is a sensible and computable assignment of a canonical representative matrix for every gauge equivalence class in $\mathfrak{gl}_n(x)$

If the above is some kind of extremely difficult untractable super-problem I'd appreciate an answer which explains why is this the case and additionally:

If the above is hopless can this be done at least for $\mathfrak{gl}_n \otimes_\mathbb{C}\mathbb{C}((x))$? With $P$ above lying in $GL_n(\mathbb{C}((x)))$ of course.

EM of a Gaussian-Gamma mixture model in matlab

Math Overflow Recent Questions - Sat, 06/17/2017 - 07:57

I have to estimate a gaussian-gamma mixture model with K components using EM algorithm, in more detaills i have an optical image (RGB) modeled by gaussian distribution and SAR image (grayscale) modeled by gamma distribution and each image contains K components. thus each component represent a class in two correspondence images. Thanks for providing me more formulas to implement it in matlab

Whitehead torsion in simplicial category

Math Overflow Recent Questions - Sat, 06/17/2017 - 04:54

I am looking for sources on Whitehead torsion in simplicial category. Specifically I am looking for a reference where the following theorem is proved (if true):

let X and Y be simplicial complexes such that there exists a sequence of collapses and expansions from X to Y in CW category (as in Cohens book) then there exists such a sequence using only simplicial collapses and expansions.

An embedding problem in Kahler geometry

Math Overflow Recent Questions - Sat, 06/17/2017 - 02:09

How from $L^2$ estimate we can get the following result

Let $X$ be a compact Kahler manifold of finite volume, bounded Riemannian sectional curvature and negative Ricci curvature and $x \in X$. There exists a positive integer $m$ such that the pluricanonical map defined by $\Gamma^0(X,K_X^m)=\cup_{\alpha>0}\Gamma^\alpha(X,K^m)$ (where $\Gamma^\alpha(X,K^m)$ is the space of $L^\alpha$ holomorphic sections of $K^m$)provides an embedding of neighbourhood of $x$ to its image.

Is there an algorithm for finding the generators for special torsion subgroup of elliptic curves?

Math Overflow Recent Questions - Sat, 06/17/2017 - 01:40

Let $E$ be an elliptic curve over finite field $\mathbb{F}_q$ and $n$ be a positive integer. I am looking for an algorithm to find the generators of $E[n]$. Is there a fast algorithm in special cases such as supersingular elliptic curves or numbers like $n=p^t$?

General theorem on Blow up

Math Overflow Recent Questions - Sat, 06/17/2017 - 00:45

Let $X$ be a singular projective variety. (We can assume $X$ to be seminormal if it helps.) Let $W$ be a codimension $>1$ subvariety of $X$ so that $W$ is in the singular locus of $X$. Let $\pi \colon Y\rightarrow X$ be a proper map which is isomorphic outside $W$ and on W its a $\mathbb{P}^n$ bundle for $n\neq 0$. Is it true that $Y$ is the blow up of $X$ along $W$? Can anyone give a reference of some general result related to this? What is the condition for a binational map to be sequence of blow ups?

How to goal set in google analytic tools? [on hold]

Math Overflow Recent Questions - Sat, 06/17/2017 - 00:21

I want to know how Google sets gaol in Google's analytic tools.

so please help,

Bounding number of $k$-nearest neighbor sets in $\mathbb{R}^d$

Math Overflow Recent Questions - Fri, 06/16/2017 - 19:19

Suppose that $\mathcal{X} \subseteq \mathbb{R}^d$ is compact.

Let there be $n$ distinct points $X = \{ x_1,...,x_n \} \subseteq \mathcal{X}$ and $k = \lfloor n^\alpha \rfloor$ where $0 < \alpha < 1$. Assume $\alpha$ and $d$ are fixed.

Define the $k$-NN radius of $x \in \mathcal{X}$ as $r_k(x) := \inf \{ r : |B(x, r) \cap X| \ge k \}$ where $B(a, r) := \{a' \in \mathcal{X} : |a - a'| \le r \}$.

Define the $k$-NN set of $x \in \mathcal{X}$ to be $N_k(x) := X \cap B(x, r_k(x))$. This can be viewed as the $k$ closest points in $X$ to $x$ (unless there are ties).

Let $M$ be the number of distinct $k$-NN sets over $\mathcal{X}$, that is, $M := |\{ N_k(x) : x \in \mathcal{X} \}|$.

Is $M$ bounded polynomially in $n$?

If not, then if we assume $X$ is sampled i.i.d. from some distribution, then do we at least have $M = O(poly(n))$ with high probability?

Reference request: Heyting algebra structure on Catalan numbers

Math Overflow Recent Questions - Fri, 06/16/2017 - 18:31

I've noticed that for every natural number $n\in\mathbb{N}$, there is a finite Heyting algebra with cardinality $C(n)$, where $C(n)$ is the $n$th Catalan number, $$1,1,2,5,14,42,132,\ldots$$ I'm looking for a reference, if this fact is known (to be known).

Below I will explain where the Heyting algebra structure comes from, in case it helps. When $n=0$ or $n=1$, we have $C(n)=1$, and there is a unique Heyting algebra structure on a set with one element, so suppose $n\geq 2$.

For any $m\in\mathbb{N}$, let $[m]:=\{0,1,\ldots,m\}$ and for any $0\leq a\leq b\leq m$, write $[a,b]$ for the subinterval $\{a,a+1,\ldots,b\}\subseteq[m]$. These subintervals form a poset, which we consider as a topological space with the Alexandrov topology: points are subintervals $[a,b]$ and open sets are down-closed subsets. Write $\Omega[m]$ for the poset of open sets in this space, so it has the structure of a Heyting algebra. It remains to show that the cardinality of $\Omega[m]$ is $C(m+2)$.

It is well-known that the Catalan number $C(n)$ counts the Dyck paths of length $2n$. These are paths in a triangle of dots (see below for $n=5$), starting at the southwest point, ending at the northeast point, where each edge in the path moves one unit either northward or eastward.

Position the elments of $[m]$ in the $(m+2)$-triangle, as shown here in the case $m=3$: $$\begin{array}{ccccccccccc} \bullet&&\bullet&&\bullet&&\bullet&&\bullet&&\bullet\\ &&&&&&&3\\ \bullet&&\bullet&&\bullet&&\bullet&&\bullet\\ &&&&&2\\ \bullet&&\bullet&&\bullet&&\bullet\\ &&&1\\ \bullet&&\bullet&&\bullet\\ &0\\ \bullet&&\bullet\\ \\ \bullet\\\\ \end{array}$$ In this setup, a Dyck path $p$ of length $m+2$ can be identified with a downclosed subset, $S(p)\in\Omega[m]$. For example, the Dyck path $p_0$ shown below $$\begin{array}{ccccccccccc} \bullet&&\bullet&&\bullet&&\bullet&-&\bullet&-&\bullet\\ &&&&&&|&3\\ \bullet&&\bullet&-&\bullet&-&\bullet&&\bullet\\ &&|&&&2\\ \bullet&&\bullet&&\bullet&&\bullet\\ &&|&1\\ \bullet&&\bullet&&\bullet\\ &0&|\\ \bullet&-&\bullet\\ |\\ \bullet\\\\ \end{array}$$ represents the set $S(p_0)=\mathord{\downarrow}[1,2]\cup\mathord{\downarrow}[3]$.

In fact, all these Heyting algebras $\Omega[m]$ fit together in a single topos, as we now explain. Consider the additive monoid of natural numbers as a category $BN$ with one object. Let $\mathbf{Int}:=\mathrm{Tw}(BN)$ be the twisted arrow category, and consider the presheaf topos $\mathrm{Psh}(\mathbf{Int})$. The subobject classifier for this topos is a functor $$\Omega'\colon\mathbf{Int}^\mathrm{op}\to\mathbf{Set}.$$ so for each object $n\in\mathbb{N}=\mathrm{Ob}(\mathbf{Int})$, we have a set $\Omega'(n)$. Moreover this set carries the structure of a Heyting algebra. Finally, $\Omega'(n)$ has a well-known description in terms of sieves, i.e. subfunctors of the representable functor $\mathbf{Int}(-,n)$. Unwrapping the definition, these are exactly the open sets of $[n]$. In other words, we have a bijection $\Omega'(n)\cong\Omega[n]$.

Can a closed rectifiable curve be "bad" in all directions?

Math Overflow Recent Questions - Fri, 06/16/2017 - 17:25

How can one tell whether a point $P$ not on a closed rectifiable curve $C$ is inside or outside $C$?

If $C$ is piecewise smooth one can throw a ray $R$ from $P$ in a random direction and count the number of intersections between $C$ and $R$. Odd - $P$ is in; even - $P$ is out. If the a line segment of $C$ lies on $R$ one can either collapse it into a single point.

Now, if $C$ is merely rectifiable then it's not clear that the number of intersections between $C$ and $R$ is going to be finite. Thus the questions:

Is it possible for a rectifiable curve $C$ and a point $P$ be in such position that for a ray $R$ the number of intersections between $C$ and $R$ will be infinite (apart of line segments of $C$ lying on $R$)?

Is it possible for the above travesty to happen for every ray $R$ from a fixed point $P$?

Random N-body problem

Math Overflow Recent Questions - Fri, 06/16/2017 - 15:28

Suppose there are $N$ unit-mass particles whose initial positions are uniformly distributed in a unit-radius disk. Each particle is assigned a randomly oriented initial velocity vector $v_i$ of length $1$ (green below). Added: Robert Israel's incisive comment suggests that I should also stipulate that $\sum_i v_i = 0$. Then the particles act upon one another via inverse-square gravity.
Dots show initial positions inside unit disk. Green vectors: initial velocity; red vectors: final velocity.

Q. What is the probability that $k \ge 1$ of the $N$ particles remain within a disk of some radius $R \ge 1$ forever?

In the illustration above, $N=8$ and $R=3$. (But I do not trust my crude simulations.)

I am wondering if the answer is: zero, independent of $k$ and $R$ and the gravitational constant? Perhaps the answer differs for points in $\mathbb{R}^2$ vs. points in $\mathbb{R}^3$ (or $\mathbb{R}^d$, $d > 3$)?

Are functions of bounded variation a.e. differentiable?

Math Overflow Recent Questions - Thu, 06/15/2017 - 10:42

In general, it is well known that, on the real line, say on $[0,1]$, if a function $f$ is of (pointwise) bounded variation, meaning that $$\sum_{i=1}^n |f(x_i)-f(x_{i-1})| <+\infty$$ for every partition ${x_i}_{0}^n$ of $[0,1]$, then $f$ can be written as the difference of two monotone functions, hence it is differentiable a.e. w.r.t. the Lebesgue measure.

I am wondering if the same is true for $BV$ functions in $\mathbb R^d$ for $d \ge 2$.

Of course, the right definition of $BV$ in $d$-dimensional domains passes through the theory of distributions: $f \colon \Omega \subset \mathbb R^d \to \mathbb R$ is in $BV(\Omega)$ if it is an $L^1$ function whose distirbutional gradient $Df$ can be represented by a finite Radon measure (see here).

Question 1. Let $f \colon \Omega \subset \mathbb R^d \to \mathbb R$ be in $BV(\Omega)$. Is it true that $f$ is differentiable a.e. with respect to the Lebesgue measure?

What I know is that they are approximately differentiable a.e. (in view of Calderon-Zygmund Theorem) so an approximate differential exists a.e. but I am not aware of any link between the approximate differentiability and the pointwise a.e. one.

Addendum.

In view of Mizar's answer, it seems that the answer to Q1 is negative, as it has been exhibited a $BV$ function which does not have even a continuous a.e. representative (in $L^1$).

While checking the details of the answer I received, I would like to ask another version of question above (do not know if still meaningful or not).

Question 2. Let $f \colon \Omega \subset \mathbb R^d \to \mathbb R$ be in $BV(\Omega)$. Assume further $f \in C^0(\Omega)$ i.e. it is continuous. Is it true that $f$ is differentiable a.e. with respect to the Lebesgue measure?

Notes.

1. See also this for related topic (in particular, I suspect that $BV^s([0,1])$ functions should be a.e. differentiable, but I have not a formal proof of this fact, nor a counterexample)

Some curious Hankel determinants

Math Overflow Recent Questions - Thu, 06/15/2017 - 09:34

Let $f(n,q)=\prod_{j=1}^na(q^j)$ for a polynomial $a(q)$ and let $d(n)=\det(f(i+j,q))_{i,j=0}^n$ be its Hankel determinant.

Computer experiments suggest that $$\lim_{q\to1}\frac{d(n)}{(q-1)^\binom{n+1}{2}}=(a(1)a'(1))^\binom{n+1}{2}\prod_{j=0}^nj!.$$ Has anyone an idea how to prove this?

Remark: For $a(q)=a+qb$ it is easy to verify that $$d(n)=((q-1)b)^\binom{n+1}{2}q^\frac{n(n+1)(2n+1)}{6}{\prod_{j=1}^n[j]_{q}!(a+q^jb)^{n+1-j}},$$ if $[n]_{q}=\frac{1-q^n}{1-q}$ and $[n]_q!=[1]_q[2]_q\dots[n]_q.$

Therefore the conjecture is true for linear polynomials and also for $a(q)=q^m.$

Lower bounds on size of unique cover?

Math Overflow Recent Questions - Thu, 06/15/2017 - 05:22

Given a universe $U = \{e_1 , . . . , e_n\}$ of elements, and given a collection $S = \{S_1 , . . . , S_m \}$ of subsets of $U$, each of size $\le k$, the subcollection $S' \subseteq S$ is a unique coverage of $V \subseteq U$ if each $e \in V$ is uniquely covered, i.e., appears in exactly one set of $S'$. For simplicity, we assume that $\cup {S_i}=U$.

Question 1: Give a lowerbound on the maximum size of $V$, as a function $f(n, k)$.

Question 2: Does it help if $S$ is a Sperner family?

Notice that here we are not interested in computational and algorithmic aspects. I think I can come up with a $n/k^4$ lowerbound (and constructive).

Background

The problem of maximizing the unique cover for $k \ge 3$ is NP-hard. The approximation algorithms are studied in 1. Approximation algorithms for Generalizations are studied in [2].

References

1 V. Guruswami and L. Trevisan, The complexity of making unique choices: Approximating 1-in-k SAT, 2005.

[2] ERIK D. DEMAINE , URIEL FEIGE , et al, Combination can be hard: Approximability of the unique coverage problem