Recent MathOverflow Questions

Factorization of Gabriel-Zisman localization construction?

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

My question concerns whether the Gabriel-Zisman localization construction $S^{-1}$ for categories admits a known factorization into a pair of commuting constructions $S^l$ and $S^r$.

The localization of a category $\mathcal{C}$ by a collection of maps $S$ is understood to mean a new category $S^{-1}\mathcal{C}$ and a functor $Q : \mathcal{C} \to S^{-1}\mathcal{C}$ with the property that

  • For any functor $f : \mathcal{C} \to \mathcal{D}$ such that $f(s)$ is an isomorphism for all $s\in S$, there is a functor $\bar{f} : S^{-1}\mathcal{C}\to \mathcal{D}$ which satisfies $f = \bar{f} \circ Q$.

Ignoring set theoretic issues, this category always exists but is difficult to control for sets of maps $S$ which aren't particularly well-behaved. When $S$ satisfies a number of reasonable properties there is a Gabriel-Zisman model for $S^{-1}\mathcal{C}$. The objects of $S^{-1}\mathcal{C}$ are the same as those of $\mathcal{C}$ but the morphisms are now roofs: $$X \xleftarrow{s} Y \xrightarrow{f} Z \quad\quad{ where } \quad\quad s\in S,\, f\in \mathcal{C}$$

This construction is desirable because it gives us some control over $S^{-1}\mathcal{C}$.

Now the condition that any given map $f(s)\in \mathcal{D}$ is an isomorphism can be split into two parts:

  • there is a map $a$ such that $a f(s) = 1$
  • there is a map $b$ such that $f(s) b = 1$

For any $S\subset \mathcal{C}$, again ignoring set theoretic concerns, there are categories $S^l \mathcal{C}$ and $S^r \mathcal{C}$ each corresponding to the conditions above in the sense that there are functors $Q^l : \mathcal{C} \to S^l \mathcal{C}$ and $Q^r : \mathcal{C} \to S^r\mathcal{C}$. Each of which satisfy the analogue of the universal property for $Q$ in the second paragraph above. Since this construction is just obtained by factoring the quotient defining $S^{-1}\mathcal{C}$ into parts I'd expect $$S^r S^l\mathcal{C} \cong S^{-1}\mathcal{C} \cong S^l S^r \mathcal{C}$$

My question is whether the Gabriel-Zisman construction can be factored to produce the $S^r$ and $S^l$ constructions above. Are there roofs with broken symmetry which give only $S^r$ or $S^l$ appearing somewhere in the literature?

"Frobenius Descent"

Math Overflow Recent Questions - Tue, 12/19/2017 - 13:29

The following proposition is there in Pink's lecture notes on finite group schemes.

Let $k$ be an algebraically closed field of characteristic $p$. The category of finite length $W(k)$-modules $N$ with a $\sigma$-linear automorphism ($\sigma$ is the Witt vector frobenius) $F: N \to N$ is equivalent to the category of finite length $\mathbb Z_p$ modules (i.e., finite abelian $p$-groups). In particular, $\text{length} _{W(k)} N = \text{log}_p |N^F|$ where $N^F$ is the subset of $N$ fixed by $F$.

In the lecture notes there is a proof by using Lang's theorem. I think there is a more straightforward proof without using Lang theorem but just by following the technique of Fontaine's Galois descent proof in the case of Witt-vectors. Edit:For whatever its worth, here is that proof.

Question: Does anyone have a reference to the theorem or any of the proofs?

Sufficient criteria for $X \subset \mathcal{H}$ to be a Lipschitz (or unif. cont.) retract of $\mathcal{H}$

Math Overflow Recent Questions - Tue, 12/19/2017 - 04:02

I am interested in sufficient criteria which ensure that a subset $X$ of a Hilbert space $\mathcal{H}$ is a Lipschitz (or at least uniformly continuous) retract of $\mathcal{H}$.

Under which conditions on $X \subset \mathcal{H}$ is there a (nonlinear) Lipschitz (or uniformly continuous) map $\pi : \mathcal{H} \to X$ with $\pi x = x$ for all $x \in X$?

Note: It is a crucial requirement here that the range of $\pi$ be (contained in) $X$! Thus, this cannot be resolved by an application of Kirszbraun's theorem, and really depends on the properties of the set $X$.

My hope is that this is a known fact to people working in the geometry of Hilbert spaces.

In fact, it would be enough for my purposes if for each $x_0 \in X$, there is a small ball $B_r (x_0)$, and a Lipschitz (or uniformly continuous) map $\pi : B_r (x_0) \to X$ with $\pi x = x$ for $x \in X \cap B_r (x_0)$. In this case, it would be very nice if size $r$ of the ball and the modulus of continuity of $\pi$ can be bounded independently of $x_0$, as long as $\| x_0 \| \leq R$.

I know that something like the above condition is true for closed convex sets, but unfortunately, the set $X$ that I am interested in is not convex.

To explain what type sets I am looking at, and what kind of conditions I am interested in, let me introduce a bit of notation: We are given a family $(\psi_x)_{x \in \mathbb{R}^{2d}}$ of functions $\psi_x \in L^2 (\mathbb{R}^d)$, such that $x \mapsto \psi_x$ is continuous, and such that the map $$ V : L^2 (\Bbb{R}^d) \to L^2 (\Bbb{R}^{2d}), f \mapsto V f \quad \text{with} \quad V f(x) = \langle f, \psi_x \rangle $$ is a well-defined isometry (but $V$ is not surjective). We then consider the set $$ X := \{ \, |V f| \,:\, f \in L^2 (\Bbb{R}^d) \, \}, $$ i.e., we take the (pointwise) absolute values of the range of the operator $V$.

From the properties stated above, one can derive the following:

  • $X$ is "star-shaped" with respect to the origin, and thus simply connected.
  • $X$ is weakly sequentially closed. In fact, $X \cap \overline{B_r} (x)$ is weakly compact for each $r > 0$, $x \in L^2 (\Bbb{R}^{2d})$.
  • More precisely, for a weakly convergent sequence $(F_n)_n$ in $X$, say $F_n \rightharpoonup F$, it follows that $F_n \to F$ pointwise, and that $F = |V f|$ for some $f \in L^2$.

The set $X$ probably enjoys quite a lot more nice properties, but since I don't know what type of property would imply the "Lipschitz retract property", it would be helpful to have some kind of list of sufficient conditions, so that we might try to check these :)

Can a planar tangle have an infinite number of input disks?

Math Overflow Recent Questions - Mon, 12/18/2017 - 17:51

Can a planar tangle have an infinite number of input disks?

Some publications talk about cases with a finite number of input disks, while others do not say if it is finite or infinite.

So, is it necessary/required that a planar tangle has a finite number of input disks?

A problem involving the inverse Collatz map

Math Overflow Recent Questions - Mon, 12/18/2017 - 17:49

Let $C$ be the Collatz transformation defined on the natural numbers by: $$C(n) := \begin{cases} n/2 & \text{if} \;n \;\text{even} \\ (3n+1)/2 & \text{if} \;n \;\text{odd} \end{cases}$$
The inverse of $C$ is: $$C^{-1}(\{n\}) = \begin{cases} \{2n\} & \text{if} \;n \not \equiv 2 \pmod 3 \\ \{2n, (2n-1)/3\} & \text{if} \;n \equiv 2 \pmod 3 \end{cases}$$ Let $n$ be a natural number with $n \equiv 2 \pmod 3$. Let $C^{-k}$ be $C^{-1} \circ \cdots \circ C^{-1}$ ($k$ times).
Consider the cardinals $c_1(n,k):= \vert C^{-k}(\{2n\}) \vert $ and $c_2(n,k):= \vert C^{-k}(\{(2n-1)/3\}) \vert$.

Question: Is there $k_n>0$ such that $c_1(n,k_n) \neq c_2(n,k_n)$?
Remark: It is checked for $n \le 2 \cdot 10^9$.

Assuming the answer is no, let $n$ be a counter-example.
Motivation-Question: Is $n$ also a counter-example of the Collatz conjecture?

Assuming the answer is yes, let $\alpha$ be the map defined by:
$$\alpha (n) := \begin{cases} 1 & \text{if} \;n \not \equiv 2 \pmod 3 \\ 1+\min\{k>0 \ \vert \ c_1(n,k) \neq c_2(n,k) \} & \text{if} \;n \equiv 2 \pmod 3 \end{cases}$$

By looking to the graph below, we get for example that $\alpha(8)=2$ and $\alpha(20)>3$.

A natural number $N$ is called a champion if $\forall n<N$ we have $\alpha(n)<\alpha(N)$.
Below is the list of the first champions (read as $[N,\alpha(N)]$):

[2, 4] [20, 6] [182, 8] [1640, 10] [14762, 12] [132860, 14] [1195742, 15] [729940487, 16] [730007555, 17] [805176788, 20] [805183349, 21] [1975495526, 22]

Note the irregular gap between the successive champions $1195742$ and $729940487$.

Bonus question 1: Is it true that $\forall k \ \exists n$ such that $\alpha(n) \ge k$ ?
Bonus question 2: Is it true that $n \ge 2^{\alpha(n)/4}$ ?
Bonus question 3: Is it true that a champion $N$ is less than $4^{\alpha(N)}$ ?

randomized min cut - probability of not contracting a particular edge Ask Question

Math Overflow Recent Questions - Mon, 12/18/2017 - 17:40

know how karger's algorithm works ( and that the probability of finding a min-cut is over 1/n^2. My question is the following.. How can i find the probability of not contracting edges of a min-cut on a graph by running this algorithm? Suppose i have the 2 graphs below:

see here

The probability of finding a min-cut on the left graph is 1/2, as the probability of not contracting the edge c-d in the 1st run is 3/4 and then (no matter which edge out of a-b,b-c,a-c i have contracted, the resulting graph is the same) and the probability of not contracting c-d is now 2/3 giving as a result 1/2.

On the next graph, though, things are different. Let's say I want to find the probability of not contracting the edge c-d. If 2 first contractions are on any of the three edges on the left, then the possibility of not contracting c-d is 1/2, On the other hand, if the first contraction is on d-e and the 2nd on a-b then the probability of not contracting c-d is now 2/3. How do i find the total probability in these cases?

A functional equation with a quadratic solution

Math Overflow Recent Questions - Mon, 12/18/2017 - 17:32

I have the following problem. I have a function $v(x, \theta)$ that can be expressed in two ways, for all $x, \theta \in \Re$:

  1. $v(x, \theta) = u(x - \theta)$, where $u$ is strictly concave and symmetric about $0$, and

  2. $v(x, \theta) = g_1 (x) f_1 (\theta) + g_2(x) f_2 (\theta) + f_3 (\theta)$

It is clear that $v(x, \theta) = - (x - \theta)^2$ is a solution, as I can set $g_1 = - x^2$, $g_2 = 2x$, $f_1 = 1$, $f_2 = \theta$, and $f_3 = - \theta^2$. Similarly, it is easy to check that $v(x, \theta) = - k_1 (x - \theta)^2 + k_2$ is a solution for all $k_1 > 0$ and $k_2 \in \Re$.

I have a heuristic argument that these are the only solutions, but I have been unable to prove it, or find a reference that would provide an answer.

So the question is to find all functions $v(x, \theta)$ that satisfy (1) and (2).

(I am happy to impose sufficient smoothness on $v(x, \theta)$ if that helps find answers, and I am also willing to assume $f_1$ and $f_2$ are monotonic).

Any guidance would be appreciated!

Surjective group homomorphism sending minimal generating system to minimal generating system

Math Overflow Recent Questions - Mon, 12/18/2017 - 17:11

Is the following statement true: Any surjective homomorphism $f:G\to H$ of groups with equal rank maps a minimal generating system $x$ of $G$ to a minimal generating system $y$ of $H$? Is it only valid for finite rank? How about infinite rank?

Lutz twist and open book decompositions

Math Overflow Recent Questions - Mon, 12/18/2017 - 15:41

Let $M^3$ be a closed oriented 3-manifold, endowed with an open book decomposition. Consider a section of the open book, that is a knot $K \subset M$ disjoint from the binding and meeting every page at one point, so that $K$ is a transversal knot for the contact structure $\xi$ compatible with the open book. Thus, the monodromy of the open book, with this section, is an element $\phi \in \mathrm{Mod}_{g,b}^1$, the mapping class group of a genus-$g$ surface with $b\geq 1$ boundary components and with one marked point. The question is how to represent, in terms of the page and monodromy, an open book representing the Lutz twist of $\xi$ along $K$.

Number of automorphisms of binary tree

Math Overflow Recent Questions - Mon, 12/18/2017 - 14:36

I've been assigned with a task of creating a tree $T$ for which $|AUT(T)|=2^n$. Is this possible? I know how to construct a tree for which $|AUT(T)|=2^{{2^n}-1}$ but I'm having troubles with the assigned one. Could you please help me?

Picard rank of Jacobian

Math Overflow Recent Questions - Mon, 12/18/2017 - 14:12

Let $C$ be a curve over field $k$, let $J$ be its Jacobian.

(1)Suppose $C$ has no nontrivial automorphism, $k$ is algebraically closed, is it true that $\mathrm{NS}(J)\cong\mathbb{Z}\cdot\theta$? Here $\theta$ is the theta divisor.

(2)Suppose $k$ is the function field of $\mathcal{M}_g$, where $\mathcal{M}_g$ is the moduli of genus $g>2$ curves over $\mathbb{C}$. Does $\mathrm{NS}(J)$ has rank $1$? (Is there a good reference for this?)

(3)Suppose $k$ is the function field of $\mathcal{M}_g$, where $\mathcal{M}_g$ is the moduli of genus $g>2$ curves over $\overline{\mathbb{F}_p}$. Does $\mathrm{NS}(J)$ has rank $1$?

Cryptographic Secret Santa

Math Overflow Recent Questions - Mon, 12/18/2017 - 13:36

Is there a protocol for conducting a Secret Santa without a central authority? Precisely, we want to sample uniformly a permutation that has no one-cycles and reveal to each member his or her successor without revealing any other part of the permutation. Alternatively, we can uniformly sample an $n$-cycle, where $n$ is the number of participants in the Secret Santa.

Pullback of Hessian

Math Overflow Recent Questions - Mon, 12/18/2017 - 13:11

Let $f:S^N(R) \rightarrow \mathbb R$ be a smooth function on the $N$-sphere of radius $R$. Then we can define $g(x):=f(Rx)$ which is a function on $S^N(1).$

Now, we can compute the Hessian of $g$ and the Hessian of $f$ defined as in here Hessian on Riemannian manifolds.

I would like to understand what is the relationship between $det(Hess(g)(x))$ and $det(Hess(f)(Rx))$?

For the trace of the Hessian, i.e. the Laplacian, it seems that the relationship is $\Delta g(x)=R^2 \Delta f({Rx}).$ Now it is tempting to assume that $$\det(Hess \ g(x))=R^{2n} \det(Hess \ f(Rx)).$$

Is this true? Here the determinant is the standard determinant of the matrix obtained by evaluating the Hessian with respect to any orthonormal basis.

$G_\delta$-diagonal and productivity of the CCC

Math Overflow Recent Questions - Mon, 12/18/2017 - 12:39

Is there a known example of a completely regular c.c.c. space with $G_\delta$-diagonal which is not productively c.c.c.?

The non-existence of such a space is consistent (for example, under $MA$ no such space should exist.) This would entail, I'm looking for a consistent example only; unless of course it's a theorem that completely regular c.c.c. spaces with $G_\delta$-diagonal are productivity c.c.c.

Related Question:

Towards the direction of the productivity of these spaces. Is it the case that if a space X has a $G_\delta$-diagonal, then the Stone space of it's regular open algebra also has a $G_\delta$-diagonal?

Reconstruction of homogeneous polynomials

Math Overflow Recent Questions - Mon, 12/18/2017 - 11:17

This question may look trivial, but I wonder of any results related to my question.

I consider the following polynomial: \begin{equation} p(\omega) = p_k(\omega) + Y_2(\omega) r_k(\omega), \, w\in \mathbb{R}^2, \, k\geq 1, \end{equation} where $p_k, \, r_k$ are real-valued homogeneous polynomials of degree $k$, $Y_2(\omega)$ is a harmonic polynomial (which is then homogeneous) of degree 2.

I know the values of $p$ for all $\omega\in \mathbb{S}^1$ (note that $|\omega|^2 = \omega_1^2 + \omega_2^2 = 1$ on $\mathbb{S}^1$); polynomials $p_k, \, r_k$ are unknown. But I would like to reconstruct info as much as I could about them. For example I know that $|r_k| << |p_k|$ on $\mathbb{S}^1$.

I know that reconstruction of $p_k, \, r_k$ cannot be done in general, if the values are given only on $\mathbb{S}^1$. But I wonder what can one say about this problem in general, for any reasonable assumptions.

Intersections of products of Sylow $p$-subgroups

Math Overflow Recent Questions - Mon, 12/18/2017 - 11:09

Motivated by the work of Cohn, Umans and collaborators on bounding the complexity of matrix multiplication, a student and I have been investigating the following problem. For subsets $X$ and $Y$ of a group $G$, let $X \cdot Y = \{ xy \mid x \in X, y \in Y \}$.

We would like to find the size of the smallest group with three distinct Sylow $p$-subgroups $P_{1}, P_{2}$ and $P_{3}$ such that \begin{equation}\label{Syl} (P_{1}\cdot P_{2}) \cap P_{3} = \{1_{G}\} \,. \end{equation}

Any group having this property has at least $p+1$ Sylow $p$-subgroups, and so has order greater than $p^{2}$, while $\mathrm{PSL}_{2}(p)$ is an explicit example of a group with the required property. So $p^{2} < |G| < p^{3}$, we are interested in whether there exists a stronger bound of the form $|G|< p^{3-\epsilon}$ for some absolute $\epsilon > 0$ (not tending to $0$ with $p$).

We tried restricting to Frobenius groups $G = C_{q} \rtimes C_{p}$ where $q = kp+ 1$ is prime. Computational evidence suggests that for $p > 5$ such groups exist with $q < p^{2}$. Realising $G$ as a group of linear polynomials with coefficients in $\mathbb{F}_{q}$ we can reformulate the problem of estimating the intersection of point stabilisers $(G_{0} \cdot G_{1}) \cap G_{t}$ as counting the number of solutions of the polynomial $x^{k} + (t-1)y^{k} - t = 0$, for some $t \in \mathbb{F}_{q}$. The Hasse-Weil bound gives a lower bound for $q$ in terms of $p$, but these are weaker than we would like. If we assume that the fixed points of elements in $G_{0} \cdot G_{1}$ are distributed close to uniformly at random in $G$, then we have a heuristic argument that a Frobenius group satisfies the displayed equation only when $q = \Omega(p^{2}/\log(p))$.


1)What is the size of smallest Frobenius group $C_{q} \rtimes C_{p}$ satisfying the displayed equation?

2) What is the size of the smallest group satisfying the displayed equation?

A special kind of multiplicative function $f: \mathbb N \to \mathbb N$ such that $f(p)=p+k$ for all odd prime $p$, where $k>1$ is a fixed odd integer

Math Overflow Recent Questions - Mon, 12/18/2017 - 07:00

For which odd positive integer $k$, can we find a multiplicative function $f: \mathbb N \to \mathbb N$ satisfying the following conditions :

$f(p)=p+k$ for all odd prime $p$ and $f(n)$ is not a perfect square if $n$ is not square free


Does there exist even at least one odd positive integer $k$ for which we can find a function of the above type ?

Union of pairwise almost disjoint sets

Math Overflow Recent Questions - Mon, 12/18/2017 - 05:17

I asked this question on stackexchange :

but I got no answer after 24 hours, so I ask it here.

Let $r$ and $n$ be two natural numbers, with $n \geq 2$. What is known about the least possible cardinality of the union of $r$ sets with cardinality $n$, such that any two of these sets have at most one element in common ?

Let $f(r, n)$ denote this least possible cardinality.

If $n = 2$, the condition that two of the sets have at most one common element amounts to say that these sets are distinct, thus $f(r, 2)$ is the least natural number such that ${k \choose 2} \geq r$.

In the general case, each of the $r$ sets contains $n \choose 2$ pairs and two sets never contain a same pair, thus the union of the $r$ sets contains at least $r {n \choose 2} $ pairs, thus

(1) $f(r, n) \geq k(r, n)$, where $k(r, n)$ denotes the least $k$ such that ${k \choose 2} \geq r {n \choose 2}$.

This is not optimal, in the sense that $f(r, n) > k(r, n)$ happens. For example, $f(2, 3) = 5$ and $k(2, 3) = 4$.

I have two questions :

1° do you know a better minoration of $f(r, n)$ than (1) ?

2° (1) gives $f(30, 4) \geq 20$; can it be proved that $f(30, 4) \geq 21$ ?

Thanks in advance.

Minimum degree of a number theoretic polynomial?

Math Overflow Recent Questions - Mon, 12/18/2017 - 04:56

Given integer $n\in\Bbb N_{n>1}$ define $c(n)=\sum_{p^k\|n}k$.

Suppose I want a polynomial $f(x)\in\Bbb Z_r[x]$ such that $f(n)\equiv c(n)\bmod q$ at a prime $q<\log_2 n$ ($f(n)\in\Bbb Z_r$ is reduced $\bmod q$) at every $n\in\{2,3,\dots,2^m\}$ such that the degree of $f(x)$ is bound by $m^\alpha$ for some $\alpha>0$ then what is the minimal $r$ such that I can achieve this?

Can $r=2^{O(m^b)}$ hold at some $b>0$ for $q=2$?

Injective dimensions of radical powers

Math Overflow Recent Questions - Mon, 12/18/2017 - 04:17

Given a finite dimensional algebra $A$ with Jacobson radical $J$ (defined as the intersection of all maximal right ideals of the algebra) and let $J^i$ be the powers of this ideal. Let $injdim(M)$ denote the injective dimension of a module $M$.


  1. Do we have $injdim(J) \geq injdim(J^2)-1$?

  2. Is the sequence $injdim(J^i)$ weakly decreasing for $i \geq 1$?

I tested this for some algebras but found no counterexample. I even do not have a proof for Nakayama algebras at the moment (of 2.), but tested it for such algebras with at most 7 simple modules, so there is some evidence that this might be true. The analogue question replacing injective dimension by projective dimension would also be interesting, but I did not much tests for this yet.

Note that $J^i$ is injective iff $J^i=0$ (we can assume algebras to be nonsemisimple) so the sequence is decreasing for a large class of algebras including selfinjective and hereditary algebras.

(This question was split of from Injective dimension of the Jacobson radical and global dimension . Proving that $injdim(J) \geq injdim(J^2)-1$ would give a proof for the question in the link)


Subscribe to curious little things aggregator