# Recent MathOverflow Questions

### Inverse limits of perfect groups

Math Overflow Recent Questions - Wed, 12/27/2017 - 11:42

Is every group isomorphic to an inverse limit (that is, projective limit) of perfect groups?

I guess, the answer is no. In that case: Is there a characterization of the groups that are isomorphic to inverse limits of perfect groups?

### Elementary description to count of perfect squares - I

Math Overflow Recent Questions - Wed, 12/27/2017 - 11:29

Is there an elementary description of $$N(a)=\Big|\Big\{x\in\{0,1,\dots,\Big\lfloor\frac a2\Big\rfloor-1,\Big\lfloor\frac a2\Big\rfloor\Big\}:\sqrt{x(a-x)}\in\Bbb Z\}\Big|$$ and though likely non-monotone how does it grow (heuristically $N(a)=O(\log a)$)?

### Bhargava's article on fixed divisors

Math Overflow Recent Questions - Wed, 12/27/2017 - 11:28

I'm studying some of the Bhargava's early works. In "Generalized factorials and fixed divisors" there's the lemma 2 that i cant understand. We have that $D$ is a DVR, $X$ is any subset of $D$, with $P$ that is the only maximal ideal of $D$. We take $\left\{a_i\right\}_{i\in \mathbb{N}}$ a $P$-ordering of $X$. Then he defines $A_k(X)$ as a matrix with $[A_k(X)]_{i,j}=(-1)^{i-j}\frac{V(a_0,\dots,\hat{a_j},\dots,a_i)}{V(a_0,\dots,a_{i-1})}$, where $V(x_1,\dots,x_n)$ is the determinant of the Vandermonde matrix with values $x_1,\dots,x_n$.

It says: "Then it follows from a fundamental property of P-orderings (A, Lemma 2) that these Vandermonde quotients are necessarily integral modulo P..." This lemma says this: $\forall 0\le j \le k < |X|$, $\Rightarrow$ $v_k(X,P)\subseteq \prod_{0\le i \le k, i\ne j}w_P(a_j-a_i)$.

$v_k(X,P)$ is the maximum power of $P$ that divides $<(a_k-a_0)\dots(a_k-a_{k-1})>$, the same for $w_P$. I can't understand why i can undestand that those quotients are integral mod $P$. I'm thinking that this inclusion is meaning something like: "the numerator has an higher power of the generator of $P$ than the denominator" but that doesn't seem so obvious. Someone can help me?

### Maximum of the Dirchlet eigenvalue of Monge-Ampere equation arrived at regular simplex

Math Overflow Recent Questions - Wed, 12/27/2017 - 09:19

I wish this could be the toy model of "hear the shape from the spectrum".

There is a article http://pages.iu.edu/~nqle/MA_EVP.pdf of NAM Q.LE state a conjecture of when the eigenvalue of Monge-Ampere equation will arrive the maximum.

It divide into two part:

Conjecture 1 1. Among all bounded open convex sets in $\mathbb R^n$ having a fixed positive volume, the n-dimensional regular simplex (that is the interior of the convex hull of (n + 1) equally spaced points in $\mathbb R^n$) has the smallest Monge-Ampere eigenvalue. 2. Among all open bounded centrally symmetric convex sets in $\mathbb R^n$ having a fixed positive volume, the n-dimensional cube has the smallest Monge-Amp`ere eigenvalue.

The story is more or less easier for the minimum, it should arrive with the ball $B_{n-1}$ due to the brunn-minkowski inequality, which claim the eigenvalue is a convex function on convex body space.

I need explain the basic set first, we consider the Dirchlet eigenvalue problem of Monge-Ampere equation, $$det(D^2u)=\lambda |u|^{n}\ in\ \Omega$$ $$u=0 \ on \ \partial \Omega$$ This equation is natural to consider due to a rescaling argument, just consider rescaling $u_{\epsilon}(x)=\epsilon\cdot u(x)$, then $det(D^2 u_{\epsilon})={\epsilon}^ndet(D^2u)=\epsilon^n\lambda|u|^n=\lambda|u_{\epsilon}|^n$.

Lions showed there is a unique constant $\lambda>0$ such that the eigenvalue function have a solution. And there is a variational characterization of $\lambda$, $$\lambda(\Omega)=\inf_{u\in C_0^1(\bar \Omega)\cap C^2(\Omega), u \ convex, u|_{\partial \Omega}=0}\frac{\int_{\Omega}(-u) \cdot det(D^2u)dx}{\int_{\Omega}(-u)^{n+1}dx}$$

The point is, I think this $\lambda$ should have a geometric characterization, related to some quality of convex body $\Omega$ itself, I do not know if it is right, but I expect the following result:

Conejecture 2 There is a geometric characterization of $\lambda$, that is, for convex body $\Omega$, $$\lambda=\inf_{T }\mu_{n-1}( T(\partial\Omega))$$ Where $T$ runs in all affine map fix the original point and the Lebesgue measure, i.e. under a orthogonal basis, the determination of the matrix of $T$ is 1.

Motivation Let me explain why I believe this conjecture could be true. we know, for equation $det(D^2u)=\lambda|u|^n$, look it locally, by area formula with the map $F:\mathbb R^n\to \mathbb{TR}^n$, under a basis, $F:(e_1,...,e_n)\to u_{e_1},...,u_{e_n}$, any subset $A\subset \Omega$ we have $$\int_{A} u\cdot det(D^2u)dx\overset{area \ formula}=\int_{\nabla A}ude$$ where $\nabla A=\{\nabla u(x),x\in A\}$. So the geometric meaning of locally solution of $det(D^2u)=\lambda|u|^n\ \in \Omega$ is $\forall A\in \Omega$, $|\nabla A|=\int_A \lambda|u|^n$, so $\lambda=\sup_{A\to \Omega}\inf_u \frac{\int_{\nabla A}ude}{\int_{\Omega}(-u)^{n+1}dx} (*)$.

So what is the meaning of $(*)$ by intuition, it should be the optimal choice of a sires of level set, with the zero level set ecocide with $\partial \Omega$. because at once you fix the fiberation of level set, the choice of $u$ is more or less the same. So this eigenvalue characterize the geometry of $\Omega$, but I can not go further, due to three obstacle:

1. The first one is I do not know what is the universal choice of $u$ to arrive minimum $\lambda$ when fix a fiber of level set, I think it is come from a equal condition of holder inequality, but I can not work it out.
2. The second one is I do not know what is the best choice of level set fibration, I think it come from the fibration center at the "center of mass of $\Omega$" and then do the most natural one, but I do not know how to proof this.
3. If we can proof 1,2. Then how to explain the product $\lambda$ by this thing could coincide with the statement of $\lambda$ in conjecture 2.

May be this approaches is useless. In any case, I wish we can say some thing about it, whatever positive answer or negative answer. I will appreciate to any interesting argument, thank you for your attention!

### Representing mathematical statements as SAT instances

Math Overflow Recent Questions - Wed, 12/27/2017 - 05:37

The following problem (call it THEOREMS) belongs to class NP.

• Input: Mathematical statement $S$ (written in some formal system such as ZFC) and positive integer $n$ written in unary.

• Output: "Yes" if $S$ has a formal proof of length at most $n$. "No" otherwise.

It is known that there is an algorithm which, in a number of steps polynomial in $n$ (and in the length of $S$, which is usually negligible if $n$ is large), converts every instance of THEOREMS to an instance of (say) SAT.

My questions are the following:

1. Has this algorithm been implemented in full generality? That is, I could download it, input my $S$ and $n$, press a button, wait for some time, and get an instance of SAT?

2. If not, is there at least theoretical analysis what could be the length of the resulting SAT in terms of $n$, $n^{100}$ or $n \log n$?

3. Erdos Discrepancy Problem, at least for discrepancy 2, has been reduced to SAT. Are you aware about similar conversion of any other famous problem, like Riemann Hypothesis?

Note: I am not discussing how feasible would be to actually solve the SAT instance corresponding to "proving Riemann Hypothesis in a million of steps". My question is just about GENERATING this and similar SAT instances.

### Uniform convergence of resolvents of Markov processes

Math Overflow Recent Questions - Wed, 12/27/2017 - 05:36

I have a question about convergence of resolvents of Markov processes.

Let $X$, $X^n$ be Markov processes on a locally compact separable metric space $E$. We denote $\{ R_{\alpha}\}_{\alpha>0}$ and $\{ R_{\alpha}^n\}_{\alpha>0}$ by the resolvents of $X$ and $X^n$, respectively.

We assume the following:

• for any bounded measurable function $f$ and $\alpha>0$, $R_{\alpha}f$ and $R_{\alpha}^nf$ are continuous functions on $E$.
• for any bounded measurable function $f$ and $\alpha>0$, $\lim_{n \to \infty}\sup_{x \in E}|R_{\alpha}f(x)-R_{\alpha}^nf(x)|=0$.

My question

Let $\{p_t\}_{t>0}$ and $\{p_t^n\}$ be the semigroups of $X$ and $X^n$, respectively. Then, can we have the following?

• for any bounded measurable function $f$ and $t>0$, $\lim_{n \to \infty}\sup_{x \in E}|p_tf(x)-p_t^nf(x)|=0$.

There exists a related result in Theorem 3.4.2 of Pagy's book. However we cannot apply this results to my question since the space of continuous functions on $E$ is not a Banach space. If you know any other related results, please let me know.

### About reducing the rank of a matrix by substract a diagonal matrix (generalization of eigenvalue problem)

Math Overflow Recent Questions - Wed, 12/27/2017 - 05:34

Given a positive definite matrix $Q\in\mathbb{R}^{n \times n}$, I want to find a diagnonal matrix $D$ such that $rank(Q-D) \leq k < n$.

I think this can be regarded as a generalization of eigenvalue problem, which is basically problem of finding a diagonal matrix $\lambda I$ such that $rank(Q-\lambda I) < n$.

### Reference request on stochastic PDE problem

Math Overflow Recent Questions - Wed, 12/27/2017 - 04:38

I am trying to find references in the literature that connect solutions of any two of the problems given bellow. I study stochastic conservation laws. I am especially interested in solutions of the problems (2) and (4). Any other reference that connects any other combination of problems may help me too.

Deterministic Cauchy problem: $\hspace{1cm} (1) \hspace{1cm} \begin{cases} u_t+f(u)_x=0 \\[2ex] u(x,0)=u_0 (x) \end{cases}$

Deterministic Riemann problem: $\hspace{1cm} (2) \hspace{1cm} \begin{cases} u_t+f(u)_x=0 \\[2ex] u(x,0)= \begin{cases} u_l, x<0 \\[2ex] u_r, x\geqq0 \end{cases} \end{cases}$

Stochastic Riemann problem: $\hspace{1cm} (3) \hspace{1cm} \begin{cases} u_t+f(u)_x=g(u)W(t) \\[2ex] u(x,0)= \begin{cases} u_l, x<0 \\[2ex] u_r, x\geqq0 \end{cases} \end{cases}$

Stochastic Cauchy problem: $\hspace{1cm} (4) \hspace{1cm} \begin{cases} u_t+f(u)_x=g(u)W(t) \\[2ex] u(x,0)=u_0 (x) \end{cases}$

Here u $\in \mathbb{R}^n$ and W(t) is a white noise. For $n=1$ we have one equation and for $n>1$ we have system of conservation laws. Function $g$ depends of $u$ so we say that we have multiplicative noise.

So far I only find reference that studies connection between solutions of problems (1) and (2). That is TP Liu: Large-Time Behavior of Solutions of Initial and Initial-Boundary Value Problems of a General System of Hyperbolic Conservation Laws, Comm. Math. Phys. Volume 55, Number 2 (1977), 163-177; projecteuclid, DOI: 10.1007/BF01626518.

### What is the chromatic number of the Erdős–Rényi graph G(n,d/n) when d < 1?

Math Overflow Recent Questions - Wed, 12/27/2017 - 04:32

What is the chromatic number of the ER graph $G(n,d/n)$, when $d < 1$ (there exist expressions for $d > 1$, but what if the graph is super sparse?). Here $n$ is the number of vertices and $d/n$ is the edge generation probability.

### My understanding of the "story" of the Hilbert transform [on hold]

Math Overflow Recent Questions - Wed, 12/27/2017 - 00:19

I have been reading about the Hilbert transform recently, and I want to check my understanding of how it interacts with complex analysis and Fourier analysis. Is my understanding of the Hilbert transform correct?

By the Paley-Weiner theorem, given an $L^2$ function on $\mathbb{R}$, we can extend $f$ to a holomorphic function on the upper half plane should its Fourier transform vanish for negative input. (This is analogous to the case on the circle where the non-negatively indexed Fourier coefficients define the power series of a holomorphic function on the disc). Unfortunately, this is not always possible. Given some $f \in L^2(\mathbb{R})$, we would like to consider the Fourier inversion of $\hat{f}|_{(0,\infty)}$, which we denote $P(f)$.

By Fourier inversion, $f(x) = \int_{\mathbb{R}} \hat{f}(\xi)e^{2 \pi i x \xi}d \xi$. This motivates the definition of the Hilbert transform $H(f)(x) = \frac{1}{i}\int_{\mathbb{R}} \text{sign}(\xi)\hat{f}(\xi)e^{2 \pi i x \xi} d \xi$ because we can observe that $P = \frac{1}{2}(I + iH)$.

One can show that $H(f)(x) = \frac{1}{\pi} \lim\limits_{\varepsilon \to 0} \int_{|t| > \varepsilon} \frac{f(x - t)dt}{t}$, which theoretically allows us to compute the Hilbert transform without having to compute the Fourier transform.

If we want to recover the upper half-pane holomorphic extension $F(x + iy)$ of $P(f)$, then we need to solve the following two Laplace equations: $\Delta \text{Re }F = 0$, $\text{Re }F(x) = \frac{1}{2}f(x)$ and $\Delta \text{Im }F = 0$, $\text{Im }F(x) = \frac{1}{2} H(f)(x)$.

These PDEs are solved by convolving the boundary values with the Poisson kernel. So $\text{Re }F(x + iy) = (\frac{1}{2}f * P_y)(x)$ and $\text{Im }F(x+iy) = (\frac{1}{2} H(f) * P_y)(x)$. It can also be shown that rather than convolving the Hilbert transform with a Poisson kernel, we can convolve the original function with the conjugate Poisson kernel.

Therefore, we can recover the associated upper half plane Hardy function for any $f \in L^2(\mathbb{R})$ without Fourier transforms! In theory. I don't know how practical this is.

### How to find a set of integers that satisfy certain linear conditions

Math Overflow Recent Questions - Tue, 12/26/2017 - 11:21

Suppose I have a sequence of non-negative integers $J=\{j_1,j_2,\ldots,j_n\}$ and want to find (if possible) a set of integers $I=\{0=i_1<i_2< \cdots < i_m\}$ such that $j_t$ counts the number of pairs $(i_k, i_\ell)$ with $i_\ell>i_k$ and $i_\ell-i_k=t$.

E.g., if $J=\{3,2,2,2,1\}$, then we can take $I=\{0,1, 2, 4, 5\}$. Of course, $\sum_{k=1}^{n} j_{k}=m(m-1)/2$, $i_m=n$, $j_n=1$.

My question is what is known about this problem (citations to the literature,...) and whether there exists an efficient algorithm for finding such $I$ for a given $J$, or determining that no such $I$ exists for a given $J$.

### The graph of Rule 110 and vertices degree

Math Overflow Recent Questions - Mon, 12/25/2017 - 20:48

Consider the elementary cellular automaton called Rule 110 (famous for being Turing complete):

It induces a map $R: \mathbb{N} \to \mathbb{N}$ such that the binary representation of $R(n)$ is that of $n$ after the application of Rule 110. For examples, $R(0)=0$, $R(1)=3$, $R(2)=6$ and $R(3)=7$.
See below the illustration for $R(571)=1647$:

There is an OEIS sequence computing $R(n)$ for $n<2^{10}$: A161903.

Definition: Let $\mathcal{G}$ be the graph with $\mathbb{N}$ as set of vertices and $\{\{n,R(n)\}, n \in \mathbb{N} \}$ as set of edges.

The graph $\mathcal{G}$ has infinitely many connected components and its vertices degree is not bounded above.
The proof follows from Lemmas D and E, below.

Question: Is the vertices degree bounded above on each connected component of $\mathcal{G}$?

Lemma A: For $n,r>0$, we have that $2^{r-1}n<R^r(n)<2^{r+1}n$.
Proof: Immediate. $\square$

Lemma B: $R(n)$ is even iff $n$ is even.
Proof: A portion $(\epsilon_1,\epsilon_2,0)$ gives $0$ by applying Rule 110 iff $\epsilon_2=0$. $\square$

Lemma C: For $r,k>0$, $R^r(n) = 2kn$ iff $n=0$.
Proof: If $n>0$ then there is $s \ge 0$ such that $n=2^sm$ and $m$ odd. But $R^r(2^sm) = 2^s R^r(m)$, so $R^r(m)=2km$, it follows by Lemma B that $m$ is even, contradiction. $\square$

Lemma D: For $n,r>0$, $n$ and $2^rn$ are not in the same connected component of $\mathcal{G}$.
Proof: If $n$ and $2^rn$ are in the same connected component then there are $r_1,r_2>0$ such that $R^{r_1}(n) = R^{r_2}(2^rn) = 2^r R^{r_2}(n)$, so by Lemma A, $r_1 = r_2 +r$. Then, $R^{r}(m)=2^rm$ with $m=R^{r_2}(n)$, thus $m=0$ by Lemma C, contradiction. $\square$

Lemma E: For any $n>0$, there is a vertex of $\mathcal{G}$ of (finite) degree $\ge n$.
Proof: The pattern of $r \ge 2$ successive black cells (corresponding to the vertex $2^r-1$) is the image of any pattern of $r-1$ cells without successive white cells, without three successive black cells and whose first and last cells are black, see for example below with $r=27$:

Clearly, for $r$ large enough, the vertex $2^r-1$ has degree $\ge n$. $\square$

Exercise: Show that $|R^{-1} (\{ 2^r-1 \}) | = \sum_{2a+b = r} {a \choose b}$, known as the Padovan sequence.

Bonus question: What is the sequence $\mathcal{S}$ of minimal numbers of the connected components of $\mathcal{G}$?

Note that $\mathcal{S} \subset \mathbb{N} \setminus R(\mathbb{N}^*) = \{0, 1, 2, 4, 5, 8, 9, 10, 11, 16, 17, 18, 19, \dots \}$, so:

• $\{0,1,2,4,8\} \subset \mathcal{S}$, by Lemmas B and D.
• $5 \in \mathcal{S}$ iff $\forall r_1, r_2>0$ then $R^{r_1}(1) \neq R^{r_2}(5)$.
• $11 \not \in \mathcal{S}$ because $R^4(1) = R(11)=31$.
• I don't know for the other numbers appearing above.

A search for "$0, 1, 2, 4, 5, 8, 9, 10, 16, 17, 18$" gives one result only, the Fibbinary numbers $\mathcal{F}$, i.e. the integers whose binary representation contains no consecutive ones (the number of such numbers with $n$ bits is the $n$th Fibonacci number). It is related to Zeckendorf's theorem.

Is it true that $\mathcal{F} \subseteq \mathcal{S}$, or even $\mathcal{F} = \mathcal{S}$?

Note that $\mathcal{F} \subset \mathbb{N} \setminus R(\mathbb{N}^*)$ because a portion $(0,0,1,\epsilon)$ gives $(1,1)$ by applying Rule 110.
I don't know whether $19 \in \mathcal{S}$, but $19 \not \in \mathcal{F}$.

### Seeking references for finding primes infinitely often

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

I've been pondering this weakened version of the finding primes problem for a while:

Is there an algorithm which given $k$ outputs a prime $p > 2^k$ in time $F(\log_2(p))$?

This differs from the ordinary finding primes problem, which I'll state as:

Is there an algorithm which given $k$ outputs a prime $p > 2^k$ in time $F(k)$?

Equivalently, the weak version is that there is a deterministic algorithm to find a prime $p > 2^k$ which runs in time $F(k)$ on infinitely many inputs $k$. Another formulation of the weak problem is to determine the values of $\displaystyle\liminf_{p\rightarrow\infty}{\frac{L(p)}{\log_2(\log_2(p))}}$ and $\displaystyle\liminf_{p\rightarrow\infty}{\frac{L(p)}{\log_2(p)}}$ where $p$ is prime and $L$ is the Levin complexity.

I consider both problems to be defined with respect to the class of models of computation possessing a time-translation to a single-tape Turing machine satisfying $T' \in T^{1+o(1)} \cdot S^{O(1)}$, where $T$ is the time used in the other model and $S$ is the space. This class includes the various RAM models and multi-tape Turing machines. However, the equivalence is sharper than a polynomial time-translation, and we can witness a specific value of the time exponent with an algorithm satisfying $S \in T^{o(1)}$ in any model in the class. For example, searching an interval $[2^n, 2^n + 2^{\epsilon \cdot n})$ for a prime can be accomplished in time $2^{\epsilon \cdot n + o(n)}$ in all of these models because the AKS test is simultaneously in subexponential time and subexponential space. But we won't be able to place the AKS test itself in a particular time class like $n^{6+o(1)}$ unless we can adapt it to simultaneously use space $n^{o(1)}$, until then the best we can say is that its runtime is $n^{O(1)}$ in every model. If either finding primes problem can be solved in polynomial time, assuming model-invariance won't make it any harder to prove that, and (suspending disbelief) it can only help to prove a lower bound on the exponent of exponential-time algorithms. It's plausible that it would present an obstruction to improving the exponential upper bound — for example, an algorithm that finds a prime $p > 2^k$ using $p^{\frac{1}{3}}$ time and $p^{\frac{1}{3}}$ space on some particular machine wouldn't qualify as an improvement under model-invariance. That's because the time exponent doesn't translate when the space is exponential — $\frac{1}{3}$ becomes $\frac{b+1}{3}$ after a $T' = T \cdot S^b$ time-translation. The exponential-time algorithms I refer to below are all in subexponential space anyway so this issue doesn't seem to actually come into play.

For the ordinary version, all we know is $F(k) \in 2^{0.525 \cdot k + o(k)}$, and I haven't been able to find any better bound for the weak version.

A more recent result in this area is Rubinstein's theorem which says $\text{FACTORING} \in \text{DTIME}(2^{\frac{n}{3} + o(n)})$. My understanding from the polymath page is that we don't know if having factoring for free can help us find primes. Can it help us find primes infinitely often?

An attractive aspect of the finding primes problem is that there are many conjectures which imply improvements. For example, the Riemann hypothesis puts $F(k) \in 2^{\frac{k}{2} + o(k)}$, Cramér's conjecture implies $F(k) \in k^{O(1)}$, and $\text{P}=\text{NP}$ implies $F(k) \in k^{O(1)}$. For my version of the problem, we additionally have that infinitely many Mersenne or Fermat primes gives $F(k) \in k^{O(1)}$, infinitely many $n^2+1$ primes implies $F(k) \in 2^{\frac{k}{2}+o(k)}$, and Bunyakovsky's conjecture implies $F(k) \in 2^{o(k)}$. Some other conjectures have similar implications. A world where we can't find primes infinitely often would be a very weird place, even weirder than one where we just can't find primes!

That is my main motivation behind studying this problem, to try and understand what that world would be like.

I'm looking for more information about finding primes infinitely often. In particular, is there any better time bound than what is known for the ordinary version? I haven't found it discussed in the polymath threads or elsewhere, and I haven't identified any open problems that any improvement implies, despite all the open problems that imply improvements. So for all I know, there's a simple and provably fast algorithm that I just can't think of myself.

### Co/completeness of truncated 2-category

Math Overflow Recent Questions - Mon, 12/25/2017 - 04:13

There seems to be many ways to obtain a 1-category out of a 2-category:

1. Dumb truncation. $\delta: 2\text{-Cat} \to \text{Cat}$ sends a 2-category $\cal K$ into the 1-category obtained forgetting the 2-cells. Only works with strict 2-categories.
2. Core truncation. $c : 2\text{-Cat} \to \text{Cat}$ sends a 2-category $\cal K$ into the 1-category obtained taking isomorphism classes of 1-cells. Apparently this works also with bicategories.
3. Geometric truncation. $\pi_{0*} : 2\text{-Cat} \to \text{Cat}$ sends a 2-category $\cal K$ into the 1-category obtained applying hom-wise the $\pi_0$ functor (so takes connected components of ${\cal K}(x,y)$).

Under which conditions is ${\cal K}^\delta, {\cal K}^c, {\pi_{0*}\cal K}$ a co/complete 1-category?

Non-strictness is not a big deal, I'm fine with strict 2-categories.

### Homotopy equivalence of diffeomorphism groups

Math Overflow Recent Questions - Mon, 12/25/2017 - 02:12

Let $M$ be a closed connected smooth manifold and let ${\rm Diff}^r(M)$ be the group of $C^r$-diffeomorphisms equipped with the compact-open $C^r$-topology. I am looking for a reference to the fact that the natural inclusion ${\rm Diff}^r(M)\to {\rm Diff}^1(M)$ is a homotopy equivalence for $1\leq r\leq \infty$.

### Complexes in stable categories

Math Overflow Recent Questions - Sun, 12/24/2017 - 16:47

Generalizing from 1-category theory, there's a simple definition of a "naive complex" in a stable $\infty$-category. Considering bounded positive graded chain complexes, they are a sequence of maps

$$A_n \xrightarrow{d_n} A_{n-1} \xrightarrow{d_{n-1}} \ldots \xrightarrow{d_1} A_0$$

with the property that $d_k d_{k+1} \simeq 0$. If I've not made any errors, then at first blush they seem to have a reasonable theory, along with a nice "realization" given by iteratively taking homotopy cofibers:

$$|A| = \mathrm{cofib}(\mathrm{cofib}(\ldots) \to A_0)$$

that parallels taking the total complex of a bicomplex. This realization can also be given by the colimit of the diagram

$$A_n \rightrightarrows^{d_n}_0 A_{n-1} \rightrightarrows \ldots \rightrightarrows^{d_1}_0 A_0$$

However, naive complexes don't seem to be studied. Instead, in Higher Algebra, Lurie proves a Dold-Kan correspondence stable $\infty$-category asserting equivalences between the categories of:

• Simplicial objects
• Filtered objects (i.e. arbitrary $\mathbb{Z}_{\geq 0}$-indexed diagrams)
• upper-triangular array with zeroes along the diagonal, in which every square is a pushout

and it is this last sort of thing that Lurie calls a complex. (Specifically, a $\mathbb{Z}_{\geq 0}$-complex)

It is only when looking at the homotopy category does Lurie say anything about a correspondence between simplicial objects and naive complexes.

So my question is whether this is an oversight; i.e.

Is the $\infty$-category of simplicial objects in a stable $\infty$-category equivalent to the $\infty$-category of (unbounded, positively graded) naive complexes?

and if the answer is no, what goes wrong?

### Diophantine equation $x^p+ax=y^p+by$

Math Overflow Recent Questions - Sun, 12/24/2017 - 15:15

Problem. Is there a prime number $p$ (desirably $p\le 3$) and an infinite set $A\subset\mathbb N$ such that for any distinct numbers $a,b\in A$ the Diophantine equation $x^p+ax=y^p+by$ has no positive integer solutions?

### Finding or constraining "last common ancestors" in digraphs

Math Overflow Recent Questions - Sun, 12/24/2017 - 11:46

Fix an unweighted, weakly connected digraph $\Gamma$, possibly with loops, and of bounded degree.

Call $p$ a common $n$-ancestor of $q_0,q_1$ if there are $n$-paths (directed paths of length exactly $n$) from $p$ to each $q_i$, and a last common ancestor if intuitively there are no common ancestors in between, i.e. for every common $k$-ancestor $p' \ne p$ of $q_0,q_1$, the shortest path from $p$ to $p'$ has length $> n-k$.

It is not hard to see that last common ancestors must be somewhat constrained: for example, if $p$ is a last common ancestor of $q_0$ and $q_1$ then every pair of shortest $n$-paths from $p$ to the respective $q_i$ must be disjoint; what's more, any path leading between two such respective $n$-paths must be of at least a certain length, depending on which points it connects between.

The question then is: how much further, and under what circumstances, can we further constrain the possible last common ancestors of a pair of nodes $q_i$? I'm particularly interested in when we can infer some smallish upper bound on $n$, and especially when both $q_i$ have arcs pointing to a common target node (which may itself be one of the $q_i$, since loops are allowed).

Some properties which might make the problem easier, in roughly increasing order of how much I'd prefer to avoid them:

the graph

• has a loop at every node;
• is strongly connected;
• is undirected;
• has polynomial growth;
• is finite (but still "large" compared with the size of bounds I'm interested in).

Not sure how best to tag this one.

### Lines in upper half-space

Math Overflow Recent Questions - Sun, 12/24/2017 - 11:34

A couple of years ago, I taught an undergraduate class introducing various aspects of classical geometry, learning the (beautiful!) subject as I went. I found one thing that really bothered me: the definition of lines in the upper half-plane model of the hyperbolic plane felt rather ad hoc. Although there is a nice explanation in terms of differential geometry, the algebraist in me was hoping that they could be alternatively explained through Galois theory. I gave this a shot and was unable to get it to come together, and (as an obvious novice in the subject) I was hoping someone could point me to where this has already been considered.

$\newcommand{\Re}{\mathrm{Re}} \newcommand{\Im}{\mathrm{Im}} \newcommand{\R}{\mathbb R} \newcommand{\C}{\mathbb C} \newcommand{\RP}{\R\mathrm P} \newcommand{\CP}{\C \mathrm P} \newcommand{\Q}{\mathbb Q} \DeclareMathOperator{\Gal}{Gal}$First, a few relevant facts about the upper half-plane model:

• Lines take one of two forms: they are the (nonempty) complex solution sets to $\Re(z) = b$ or $z \bar z - b(z + \bar z) + c = 0$ for $b$ and $c$ real.
• Lines in the upper half-plane are determined by their pair of incidences on the horizon line $\RP^1$.
• Isometries of the upper half-plane fix the horizon $\RP^1$ and are also determined by their behavior on it.

A common feature of the above facts is the governance of the reals: everything in sight is Galois-invariant for $\Gal(\C/\R)$. Accordingly, rather than privilege the upper half-plane, I would like to interpret this model as the quotient of $\CP^1$ by the Galois action of $\Gal(\C/\R)$. In particular, isometries of this object are then inherited from those of $\CP^1$ which fix $\RP^1$: these are the expected real linear fractional transformations.

In an effort to recover the formulas for the lines, let's pick incidence points $p$ and $q$ in $\RP^1$ and go looking for a quadratic Galois-invariant expression that contains these points in its zero locus. (Forgive me for working away from infinity in what follows.) We might first write down $(z - p)(z - q)$—and this obviously does not have the expected solution set in $\CP^1$, as it is a polynomial and hence has finitely many zeroes. The next thing to try, knowing that $\bar z$ appears in the expected equation, is averaging this polynomial with its Galois conjugate: $$\frac{(z - p)(z - q) + (\bar z - p)(\bar z - q)}{2} = \Re(z^2) - (p+q)\Re(z) + pq.$$ While this does have an infinite solution set, it again is not the expected result. Instead, though, if we tweak the original expression by shuffling the Galois action through, we arrive at $$0 = \frac{(z-p)(\bar z - q) + (\bar z - p)(z - q)}{2} = z \bar z - c(z + \bar z) + (c^2 - r^2)$$ for $c = (p+q)/2$ and $|r| = |p - q|/2$.

At this point, I'm excited to have guessed the right answer, but I'm unable to conceptualize why I should have jumped right here from the start. Accordingly, my question is a bit nebulous:

Question: Is there a conceptual reason why it's reasonable to have shuffled the Galois conjugation action through the expression for the real quadratic with roots $p$ and $q$? Is there a purely Galois perspective on why this equation deserves to be called anything like a "line" in $\CP^1\;//\;\Gal(\C/\R)$?

Question: What happens if $\C/\R$ is replaced with something like $E/\Q$ or $E_p / \Q_p$ a quadratic extension? Is there a fruitful theory of plane geometry here? (What about larger extensions?)

I previously asked a version of this question on math.stackexchange, and while I learned something, I don't think it got properly answered.

### Is the solution of this PDE a constant

Math Overflow Recent Questions - Sun, 12/24/2017 - 11:18

I have a problem: Suppose bounded function $u(x, y) \in C^{2}(\mathbb{R}^{2})$ is a solution of $u_{xx}-2u_{xy}+\beta u_{yy}+2\beta u_{x}-\beta^{2} u_{y}=0$. Is it true that $u\not\equiv\operatorname{const}$ when a) $\beta>5$, b) $\beta<-5$?

I reduce equation to canonical form and have no other idea. Do you have one?

EDIT

I get the following form canonical form: $(\beta-1)u_{rr}+(\beta^{2}-1)u_{tt}+(2\beta-\beta^{2})u_{r}-\sqrt{\beta^{2}-1}u_{t}=0$ in coordinates $r=x+y,t=-\sqrt{\beta^{2}-1}x$.