Recent MathOverflow Questions

Compute the edge-skeleton of a polytope given by its vertices

Math Overflow Recent Questions - Tue, 12/04/2018 - 00:22

Let $P$ be a polytope given by a vertex description, i.e., $P=conv(\{x_1,\ldots,x_m\})\subset\mathbb{R}^n$.

Is there an efficient (i.e., not relying on Linear Programming) algorithm to compute the edge skeleton of $P$ ?

More generally, given a polytope $P=conv(\{x_1,\ldots,x_m\})$ AND its edge skeleton $ES=\{(i,j): (x_i,x_j) \text{ is an edge of } P\}$, is there an efficient algorithm to update the skeleton after insertion of a new vertex $x_{m+1}$, i.e., to identify the subset of vertices $I\subseteq\{1,\ldots,m\}$ such that $x_i,x_{m+1}$ is an edge of $conv(P,x_{m+1})$ ?

This problem can easily be solved by LP: Given two vertices $x_i,x_j$ , one can test if the mid-point $(x_i+x_j)/2$ can be expressed as a convex combination involving the point $x_k$ (with a positive weight), for each $k\notin\{i,j\}$. However, this naive approach seems to be highly nonefficient, as it involves solving $(m-2)$ LPs to test for the membership $(i,j)\in ES$...

I found a recent related paper https://arxiv.org/abs/1412.3987 that does the job when $P$ is given by an optimization oracle and a superset of vertex directions, but this seems to be a more complicated setup than a vertex description, and it also relies on linear programming.

On $n$th class-preserving automorphism of finite $p$-group

Math Overflow Recent Questions - Mon, 12/03/2018 - 22:15

Let $G$ be a finite non-abelian $p$-group, where $p$ is a prime. An automorphism $\alpha$ of $G$ is called an $n$th class-preserving if for each $x\in G$, there exists an element $g_x\in \gamma_n(G)$ such that $\alpha(x)=g_x^{-1}xg_x$, where $\gamma_n(G)$ denotes the $n$th term of the lower central series of $G$. An automorphism $\alpha$ of $G$ is called a central automorphism if $x^{-1}\alpha(x)\in Z(G)$ for all $x\in G$. Let $Aut_{c}^n(G)$ and $Autcent(G)$ respectively denote the group of all $n$th class-preserving and central automorphisms of $G$.

My question is the following: Give some examples of finite non-abelian $p$-group $G$ of nilpotency class 3 such that $Aut_{c}^2(G)=Autcent(G)$.

Area Of sector Problem [on hold]

Math Overflow Recent Questions - Mon, 12/03/2018 - 22:14

Please help me with this problem, I don't know how to solve this; thanks in advance.

A wild embedding of $\mathbb{S}^1$ into $\mathbb{R}^3$

Math Overflow Recent Questions - Mon, 12/03/2018 - 21:34

Can one construct an embedding of $\mathbb{S}^1$ into $\mathbb{R}^3$ so that every orthogonal projection onto a two dimensional plane is a unit disc?

It is easy to construct an embedding of $\mathbb{S}^1$ into $\mathbb{R}^3$ so that one orthogonal projection is a unit disc: take a Peano-type curve $\gamma=(\gamma_1,\gamma_2):[0,1]\to\mathbb{R}^2$ that fills the unit disc and define $\Gamma(t)=(\gamma_1(t),\gamma_2(t),t):[0,1]\to\mathbb{R}^3$. Clearly $\Gamma$ is one-to-one so it is an embedding and its projection onto the first two coordinates fills the disc. It remains now to "glue" the ends to make it an embedding of $\mathbb{S}^1$.

A question regarding de Franchis theorem

Math Overflow Recent Questions - Mon, 12/03/2018 - 19:55

One form of de Franchis theorem for algebraic curves is the following: let $X$ be an algebraic curve (defined over $\mathbb{C}$ say) with genus $g > 1$. Then there are only finitely many (isomorphism classes of) curves $Y$ with genus $g' > 1$ such that there is a non-constant map $f : X \rightarrow Y$.

My question is the following: suppose that $X, X^\prime$ are two curves of the same genus $g > 1$ admitting a dominant map to the same curve $Y$ of genus $h > 1$. What can be concluded about $X,X^\prime$? Can there be infinitely many isomorphism classes of such $X$, say?

On the permanent $\text{per}[i^{j-1}]_{1\le i,j\le p-1}$ modulo $p^2$

Math Overflow Recent Questions - Mon, 12/03/2018 - 19:23

Let $p$ be an odd prime. It is well-known that $$\det[i^{j-1}]_{1\le i,j\le p-1}=\prod_{1\le i<j\le p-1}(j-i)\not\equiv0\pmod p.$$ I'm curious about the behavior of the permanent $\text{per}[i^{j-1}]_{1\le i,j\le p-1}$ modulo powers of $p$. This leads me to formulate the following conjecture.

Conjecture. Let $p>3$ be a prime. Then $$\text{per}[i^{j-1}]_{1\le i,j\le p-1}\equiv\begin{cases}\frac{p-1}2!\ p\pmod{p^2}&\text{if}\ p\equiv1\pmod4,\\0\pmod{p^2}&\text{if}\ p\equiv 3\pmod4.\end{cases}$$

I have verified this conjecture for $p=5,7,11,13,17,19,23$. Note also that $\text{per}[i^{j-1}]_{1\le i,j\le 3-1}=3$.

QUESTION: Is the above conjecture true?

Now I show that $\text{per}[i^{j-1}]_{1\le i,j\le p-1}\equiv0\pmod p$ for any odd prime $p$. Let $g$ be a primitive root modulo $p$. Then $$\text{per}[i^{j-1}]_{1\le i,j\le p-1}\equiv\sum_{\sigma\in S_{p-1}}\prod_{i=1}^{p-1}g^{i(\sigma(i)-1)}=\prod_{i=1}^{p-1}g^{-i}\times\text{per}[g^{ij}]_{1\le i,j\le p-1}\pmod p.$$ Thus we may appy the argument in the related question 316836 to get that $\text{per}[i^{j-1}]_{1\le i,j\le p-1}]\equiv0\pmod p$ since the order of $g$ is the even number $p-1$.

Your comments are welcome!

Value of $c$ such that $\lim_{n\rightarrow\infty}\sum_{k=1}^{n-1}\frac{1}{(n-k)c+\log(n!)-\log(k!)}=1$

Math Overflow Recent Questions - Mon, 12/03/2018 - 19:12

What is the value of $c$ such that $$\lim_{n\rightarrow\infty}\sum_{k=1}^{n-1}\frac{1}{(n-k)c+\log(n!)-\log(k!)}=1?$$ Numerically, it seems that the answer is $c=\log 2$. But I'd like to see a reason why.

On the sum $\sum_{\pi\in S_{n}}e^{2\pi i\sum_{k=1}^{n}k\pi(k)/n}$

Math Overflow Recent Questions - Mon, 12/03/2018 - 18:50

Motivated by Question 316142 of mine, I consider the new sum $$S(n):=\sum_{\pi\in S_{n}}e^{2\pi i\sum_{k=1}^{n}k\pi(k)/n}$$ for any positive integer $n$, where $S_n$ is the symmetric group of all the permutations of $\{1,\ldots,n\}$. Note that $S(n)$ is the permanent of the matrix $[e^{2\pi ijk/n}]_{1\le j,k\le n}$. As $S(n)\equiv\det[e^{2\pi ijk/n}]_{1\le j,k\le n}\pmod2$, it is easy to see that $S(n)\equiv n\pmod2$ in the ring of all algebraic integers.

Suppose that $S(n)\not=0$. Then the coefficient of $x_1^{n-1}\ldots x_n^{n-1}$ in the polynomial $$P(x_1,\ldots,x_n):=\prod_{1\le j<k\le n}(x_k-x_j)\left(e^{2\pi ik/n}x_k-e^{2\pi ij/n}x_j\right)$$ is $\text{per}[(e^{2\pi ij/n})^{k-1}]\not=0$. Applying Alon's Combinatorial Nullstellensatz to the subset $A=\{z\in\mathbb C:\ z^n=1\}$ of the complex field $\mathbb C$, we see that there is a permutation $\sigma\in S_n$ such that $j+\sigma(j)\not\equiv k+\sigma(k)\pmod n$ for all $1\le j<k\le n$. Thus $$\sum_{k=1}^n(k+\sigma(k))\equiv\sum_{j=1}^n j\pmod n$$ and hence $\sum_{k=1}^nk=n(n+1)/2\equiv0\pmod n$. This shows that $n$ must be odd.

Via a computer I find that \begin{gather}S(1)=1,\ S(3)=-3,\ S(5)=-5,\ S(7)=-105,\ S(9)=81,、 \\S(11)=6765=3\cdot5\cdot11\cdot41,\ S(13)=175747=11\cdot13\cdot1229, \\ S(15)=30375=3^5\cdot 5^3,\ S(17)=25219857=3\cdot13\cdot17\cdot38039.\end{gather} Thus it is natural for me to formulate the following conjecture.

Conjecture. (i) For each $n=1,3,5,\ldots$, the sum $S(n)$ is an integer divisible by $n$.

(ii) For any odd prime $p$, we have $S(p)\equiv-p\pmod{p^2}$.

Any ideas towards the solution?

What definitions were crucial to further understanding?

Math Overflow Recent Questions - Mon, 12/03/2018 - 04:51

Often the most difficult part of venturing into a field as a researcher is to come up with an appropriate definition. Sometimes definitions suggest themselves very naturally, as when you solve a problem and then ask, ‘What if I generalize this a bit?’

Other times they arise only after struggling with a subject and realizing you were looking at it from the wrong angle. An appropriate definition can then make all the difference, by reorganizing the thought and sheding light into the problems, somehow making them sharper and more focused.

I would like to collect evidences and instances of this idea. An answer should be a story of how someone came up with a good definition and how this was crucial to their understanding of a topic. If you talk about someone else, then ideally provide a reference.

(My interest in this is mainly psychological, namely, how the action of naming something somehow brings it into existence and organizes the world around it.)

edit

It was suggested that this question is a duplicate of (Examples of advance via good definitions), which asks about good definitions. It was pointed out there, and also here, that basicaly all notions that stood the test of time qualify as good definitions.

I was not asking, although it seems many people construed it this way, for a collection of good definitions, but for a collection of stories that showed how a proper definition actually changed the perception about a field.

A typical such story would have someone saying "Wait a moment! I should not be dealing with [concept A] at all! That's the wrong way to approach this. Instead I should define this other guy, [concept B], and then everything will make a lot more sense!"

I realize this is hard to make precise, so I understand if the question gets closed.

Can we have a theory $T$ that is complete for simple sentences in the language of $T$ that are weaker than $ Con(T)$?

Math Overflow Recent Questions - Sun, 12/02/2018 - 15:48

Let's denote a sentence $P$ as "weak Godel sentence of theory $T$", if and only if $$[\neg (T \vdash P) \wedge \neg (T\vdash \neg P)] \wedge [Con(T)=Con(T+P) \wedge Con(T)=Con(T+ \neg P)] $$

In English this is: $P$ is independent of $T$ and the addtion of $P$ or $\neg P$ to $T$ doesn't prove the consistency of $T$.

Let's denote a sentence as complex if it has a proper subformula of it that is a sentence, or when de-prenexed it results in a sentence that has a proper subformula of it that is a sentence. A sentence is simple if and only if it is not complex.

Let's fix the language of $T$ to a classical first order logic language that doesn't contain any constants in its signature. By sentence it is meant the usual meaning of a fully quantified formula (i.e. has no free variables).

Definition: $$T \text{ is complete for simple sentences below } Con(T) \iff \forall P (P \text { is a weak Godel sentence of }T \to P \text { is complex})$$

In other words: all sentences if the addition of them or their negation to $T$ doesn't result in a theory that can prove the consistency of $T$, that are simple, then those sentences are decidable by $T$.

Question: is it possible to have a theory that meets Godel's incompleteness criteria and yet is complete for simple sentences below its consistency level?

Simple application of Bochner--Weitzenböck type formulas

Math Overflow Recent Questions - Sat, 12/01/2018 - 19:39

I am looking for a cool and simple (but not worn-out) application of Bochner--Weitzenböck type formulas which could be used as a motivation.

What is your favourite example?

P.S. Here is one which I like, but want more: Assume two discs $\Delta_1$ and $\Delta_2$ with common boundary $\gamma$ bound a convex set in a positively curved three-dimensional manifold $M$. Then $\int_{\Delta_1}k_1\cdot k_2$ is small if the maximal angle between the discs on $\gamma$ is small; here $k_i$ denote the principle curvatures of $\Delta_1$.

Constant of the regularity of Laplacian operator

Math Overflow Recent Questions - Sat, 12/01/2018 - 03:17

Let $(Y,g_y)$ be a closed Riemannian manifold, $Z^T=[-T,T]\times Y$ with the standard product metric.

When we consider the Neunmann boundary condition, i.e. $$\begin{cases} \Delta u=f\\ \frac{\partial u}{\partial\nu}=0,~\partial Z^T, \end{cases}$$ if we let $\int_{Z^T}f=0$, we know that we have the estimate $$\|u\|_{L^p_{k+2}}\leq C (\|f||_{L^p_k}+\|u\|_{L^p_k}).$$

Q How to show that the constant $C$ does not depend on $T$.

Extension of Dirichlet's Arithmetic Progression Theorem

Math Overflow Recent Questions - Sat, 12/01/2018 - 02:54

Dirichlet's Arithmetic Progression Theorem states that:

Given $a, b\in\mathbb{Z^+}$ with $(a,b)=1$, then $a+kb$ is prime for an infinite number of $k\in\mathbb{Z^+}.$

For any given $a$ and $b$ let $K_{a,b}=\{k\mid a+kb \text{ is prime}\}$.

Also consider another Dirichlet-Valid AP $c+jd$. Restrict $j$ to $j_k\in K_{a,b}$.

Is $c+j_k d$ prime an infinite number of times?

Best software to do big number calculations quickly

Math Overflow Recent Questions - Sat, 12/01/2018 - 02:53

I am trying to do some work on some math conjecture. I am testing the conjecture numbers using very large math numbers (1000+ digits ). I am currently using python to test these numbers.

In the conjecture's calculation, I quickly need to multiply and divide a large number several times. Python can do this quickly(~3000 calculations per minute). Is there any other faster software to achieve this.

Equivalences of categories of sheaves vs categories of $\infty$-Stack

Math Overflow Recent Questions - Sat, 12/01/2018 - 02:32

Let say I have two different sites $(\mathcal{C},I)$ and $(\mathcal{D},J)$ for an ordinary topos $\mathcal{T}$. I.e.

$$Sh(\mathcal{C},I) \simeq \mathcal{T} \simeq Sh(\mathcal{D},J)$$

And we want to know if one also have an equivalence of the $\infty$-topos of sheaves of spaces on these sites:

$$ Sh_{\infty}(\mathcal{C},I) \overset{?}{\simeq} Sh_{\infty}(\mathcal{D},J)$$

This question is about finding an explicit counter example where this is not the case. But I'll give a bit more context.

If my understanding is correct, there are two cases where one can say something:

1) If $ Sh_{\infty}(\mathcal{C},I)$ and $Sh_{\infty}(\mathcal{D},J)$ are hypercomplete, or more generally if one only care about their hypercompletion. Indeed, one always has:

$$ Sh_{\infty}(\mathcal{C},I)^{\wedge} \simeq \ Sh_{\infty}(\mathcal{D},J)^{\wedge}$$

(the $^{\wedge}$ denotes hypercompletion) this is because one can show that they are both equivalent to the $\infty$-category attached to category of simplicial objects of $\mathcal{T}$ with the Jardine-Joyal model structure on simplicial sheaves. And the equivalences of this model structure only depends on the underlying ordinary topos.

2) If $\mathcal{C}$ and $\mathcal{D}$ have finite limits, then one gets the equivalence:

$$ Sh_{\infty}(\mathcal{C},I) \simeq Sh_{\infty}(\mathcal{D},J)$$

This follows from J.Lurie Lemma 6.4.5.6 in Higher topos theory. This lemma assert that under these assumptions, there is a natural equivalence between

$$ Geom( \mathcal{Y}, Sh_{\infty}(\mathcal{C},I)) \simeq Geom( \tau_0 \mathcal{Y} , Sh(\mathcal{C},I) ) $$

Where $\mathcal{Y}$ is any $\infty$-topos, $Geom$ denotes the spaces of geometric morphsisms, either of $\infty$-topos or ordinary toposes, and $\tau_0 \mathcal{Y}$ is the ordinary topos of homotopy sets of $\mathcal{Y}$. THis in particular gives a universal property to $Sh_{\infty}(\mathcal{C},I)$ which only depends on the $Sh(\mathcal{C},I)$ and so this implies the isomorphisms above.

So what about the general case ? I have quite often heard that this was not true in general, and I'm willing to believe it. But I would really like to see a counter-example !

In some of the places where I have seen asserted that this is not true in general, people were pointing out to the examples where $Sh_{\infty}(C,J)$ is not hypercomplete, and often these examples fall under the assumption of the second case.

In a comment on this old closely related question of mine, David Carchedi mention a counter-example due to Jacob Lurie which indeed avoids both situation... But I havn't been able to understand how it works, and it does not seem to appears in print. If someone can figure it out I'll be very interested to see the details.

Also a counter example to this lemma 6.4.5.6 mentioned above (without the assumption that the site has finite limit) would probably produce an answer immediately. Moreover (assuming such a counterexample exists) there must exists one where the topology is trivial, so I guess there has to be some relatively simple counter examples.

How to formally connect the log-Euclidean and Riemannian metrics for Symmetric Positive Definite matrices?

Math Overflow Recent Questions - Fri, 11/30/2018 - 23:31

I'm a statistician working on a research project dealing with metrics on SPD matrices, specifically the log-Euclidean $d_{LE}(X, Y) = \|\log(X) - \log(Y)\|$ and the Riemannian metric $d_{R}(X, Y) = \|\log(Y^{-1/2}XY^{-1/2})\|$, where the norm is the Frobenius norm.

I understand that the two metrics are closely related, and that the LE metric is something like a linearization of the Riemannian metric, but I haven't been able to find a reference that makes this precise. Any comments or suggestions are appreciated.

For some references, [1] is a good intro to different metrics for SPD matrices, and [2] gives some more details on the context I'm working in.

What is the lower bound for the number of facets that a general convex $d$-polytope with $n$ vertices can have?

Math Overflow Recent Questions - Fri, 11/30/2018 - 23:20

I am familiar with Barnette's Lower Bound Theorem on the number of facets a $d$-dimensional simplicial convex polytope with $n$ vertices can have. Is there a similar result for a general (i.e. not necessarily simplicial) $d$-polytope with $n$ vertices?

Fundamental Group of small Zariski open set

Math Overflow Recent Questions - Fri, 11/30/2018 - 19:21

Let $Y$ be an integral affine variety over $\mathbb{C}$ and $K$ be its function field. How to find a sufficiently small Zariski open set of $Y$ such that it is isomorphic to $K(\pi,1)$? Here $\pi$ is the absolute Galois group of $K$.

This statement is from the Galois Cohomology of SGA 4.5.

On sait qu’il existe des ouverts de Zariski arbitrairement petits qui pour la topologie classique sont des $K(\pi, 1)$. On ne sera donc pas surpris si l’on considère Spec(K) lui-même comme un $K(\pi, 1)$, étant le groupe fondamental (au sens algébrique) de X, autrement dit le groupe de Galois de $\overline{K} /K$, où $\overline{K}$ est clôture séparable de $K$.

What is the image of $-1$ by the local reciprocity map?

Math Overflow Recent Questions - Fri, 11/30/2018 - 19:18

Consider the Weil group $W$ of $\mathbb{Q}_p$, that is, the subgroup of those elements of $\mathrm{Gal}(\overline{\mathbb{Q}}_p/\mathbb{Q}_p)$ mapping to an integer power of Frobenius. Class field theory tells us that there is an isomorphism $$ \mathbb{Q}_p^\times \stackrel{\sim}{\longrightarrow} W^{\text{ab}}. $$

There are several ways to normalise it, say I pick the one that sends the uniformiser $p$ to a lifting of geometric Frobenius.

Question: what is then the image of $-1 \in \mathbb{Q}_p^\times$ under this map?

Reference Request: Cohomology and limits of coherent topoi. (Non-abelian case)

Math Overflow Recent Questions - Fri, 11/30/2018 - 19:08

SGA 4 VI Discusses finiteness conditions one can impose on topoi to make limits behave correctly. I am not that familiar with SGA but it is my impression that this expose only discusses abelian sheaves.

Ideally I would like to find written in the literature an analogue of the statement 8.7.7 but in a "non-abelian context" that proves the same thing for $H^1$. Something like the formula: $H^1(\lim F_i, G_i)=\lim H^1(F_i, G_i)$ as pointed sets.

I suppose one could do a careful read of this expose and verify that this holds true, this statement is probably both true and known. I am just wondering if it is written somewhere I can reference.

Pages

Subscribe to curious little things aggregator