TITLE: Starting point of Vinogradov-Korobov method
QUESTION [0 upvotes]: Let's define, for $n,k,P\in\Bbb N$
$$
J_{k,n}(P):=\int_0^1\cdots\int_0^1\left|\sum_{x=1}^Pe(\alpha_1x+\alpha_2x^2+\cdots+\alpha_nx^n)\right|^{2k}\,d\alpha_1d\alpha_2\cdots d\alpha_n\;\;,
$$
where $e(x):=e^{2\pi ix}$.
Observing now that $|z|^2=z\bar z$ and that $\int_0^1e(kx)\,dx$ equals $1$ if $k=0$ and vanishes for any other integer value of $k$, how can I show that $J_{n,k}(P)$ expresses all the integer solutions of the system
$$
x_1+x_2+\cdots+x_k-x_{k+1}-x_{k+2}-\cdots-x_{2k}=0\\
x_1^2+x_2^2+\cdots+x_k^2-x_{k+1}^2-x_{k+2}^2-\cdots-x_{2k}^2=0\\
\vdots\\
x_1^n+x_2^n+\cdots+x_k^n-x_{k+1}^n-x_{k+2}^n-\cdots-x_{2k}^n=0\\
$$
where $1\le x_1,x_2,\dots,x_{2k}\le P$ ?
I'm trying to rewrite $J_{k,n}(P)$ in different ways, but I think it's something that should be seen quite quickly, not writing down all the details... but I can't see how.
Can someone helps me?
These kind of subjects are the starting point of the Vinogradov-Korobov method in the theory of the Riemann Zeta Function (I'm reading 6th chapter of Ivic Book).

REPLY [2 votes]: The idea is to expand out the integrand; we write it as
\[\prod_{j = 1}^{k} \left(\sum_{x_j = 1}^{P} e\left(\alpha_1 x_j + \cdots + \alpha_n x_j^n\right)\right) \times \prod_{j = k + 1}^{2k} \left(\sum_{x_j = 1}^{P} e\left(-\alpha_1 x_j - \cdots - \alpha_n x_j^n\right)\right).\]
We then expand everything and group like terms, obtaining
\[\sum_{x_1 = 1}^{P} \cdots \sum_{x_{2k} = 1}^{P} \prod_{\ell = 1}^{n} e\left(\alpha_{\ell} \left(x_1^{\ell} + \cdots + x_k^{\ell} - x_{k + 1}^{\ell} - \cdots - x_{2k}^{\ell}\right)\right).\]
We now interchange the order of summation and integration. The key point is that the integral will vanish unless the coefficient of $\alpha_j$ is $0$ for all $j \in \{1,\ldots,n\}$. This happens precisely when $x_1,\ldots,x_{2k}$ are solutions to the system of equations.


TITLE: Show a function is monotonically decreasing.
QUESTION [4 upvotes]: Show that $f(x)=\dfrac{\sin x}{x}$ is monotonically decreasing on $[0,\frac{\pi}{2}]$
I'm trying to show that $f'(x)\leq0$ to show it's monotonically decreasing.  So $f'(x)=\dfrac{x\cos x-\sin x}{x^2}$.   I can see that $f'(x)\leq0$ but having trouble proving it.

REPLY [3 votes]: To show $f'(x)\lt 0$ in the interval $(0,\pi/2)$, it is enough to show that $g(x)\lt 0$ in the interval, where $g(x)=x\cos x-\sin x$.
Note that $g(0)=0$ and $g'(x)=-x\sin x$. Thus $g(x)$ is decreasing in the interval $(0,\pi/2)$, indeed all the way to $\pi$. It follows that $g(x)\lt 0$ in our interval.


text:
\begin{document}
\maketitle

\begin{abstract}
Hoffmann-Ostenhof's Conjecture states that the edge set of every connected cubic graph can be decomposed into a spanning tree, a matching and a $2$-regular subgraph. In this paper, we show that the conjecture holds for claw-free subcubic graphs and $4$-chordal subcubic graphs.
\end{abstract}

\section{Introduction}\label{sec1}
In this paper, all graphs are assumed to be finite without loops or multiple edges. Let $G$ be a finite undirected graph with the vertex set $V(G)$ and the edge set $E(G)$. For a vertex $v\in V(G)$, the degree of $v$ in $G$ and the maximum degree of $G$ are denoted by $d_G(v)$ and $\bigtriangleup(G)$, respectively. Here $N_G(v)$ denotes the set of all neighbours of $v$.  The complete graph of order $n$ is denoted by $K_n$.  The complete bipartite graph with partite sets of sizes $m$ and $n$ is denoted by $K_{m, n}$.  A graph is called \textit{cubic} if the degree of every vertex is $3$ and it is called a \textit{subcubic} graph if its maximum degree is at most $3$.
   A graph is called \textit{claw-free} if it has no induced subgraph isomorphic to $K_{1,3}$. A cycle is called \textit{chordless} if it has no chord. A graph $G$ is called \textit{chordal} if every cycle of $G$ of length greater than $3$ has a chord and a graph is \textit{$4$-chordal} if it has no induced cycle of length greater than $4$.  A \textit{cut-edge} of a connected graph $G$ is an edge $e\in E(G)$ such that $G\setminus e$ is disconnected. A subdivision of a graph $G$ is a graph obtained from $G$ by replacing some of the edges of $G$ by internally vertex-disjoint paths.

Hoffmann-Ostenhof proposed the following conjecture in his thesis \cite{Hoff1},  this conjecture also was appeared as a problem of BCC22 \cite{Cameron}.
\vspace{2mm}

\noindent \textbf{Hoffmann-Ostenhof's Conjecture.} Let $G$ be a connected cubic graph. Then the edges of $G$ can be decomposed into a spanning tree, a matching and a $2$-regular subgraph.

\vspace{2mm}
An edge decomposition of a graph $G$ is called a {\it good decomposition}, if  the edges of $G$ can be decomposed into a spanning tree, a matching and a $2$-regular subgraph (matching or $2$-regular subgraph may be empty). A graph is called {\it good} if it has a good decomposition. Hoffmann-Ostenhof's Conjecture is known to be true for some families of cubic graphs. Kostochka \cite{Kostochka} showed that the Petersen graph, the prism over cycles, and many other graphs are good. Bachstein \cite{Bachstein} proved that every $3$-connected cubic graph embedded in torus or Klein-bottle is good. Furthermore, Ozeki and Ye \cite{Ozeki} proved that $3$-connected cubic plane graphs are good. Akbari et. al. \cite{Akbari} showed that hamiltonian cubic graphs are good. Also, it has been proved that the traceable cubic graphs are good \cite{Abdolhosseini}. In $2017$, Hoffmann-Ostenhof et. al. \cite{Hoff3} proved that planar cubic graphs are good. In this paper it is shown that the connected claw-free subcubic graphs and the connected $4$-chordal subcubic graphs are good.

\section{Connected Claw-free Subcubic Graphs are Good}
In this section we show that in the case of claw-free graphs, Hoffmann-Ostenhof's Conjecture holds even for  claw-free subcubic graphs.
\begin{theorem}\label{A}
If $G$ is a connected claw-free subcubic graph, then $G$ is good.
\end{theorem}
\begin{proof}
We apply by induction on $n=|V(G)|$. If $|V(G)|=3$, then the assertion is trivial. Now, we consider the following two cases:
\\
\noindent\textbf{Case 1.} Assume that the graph $G$ has a cut-edge $e$. Let $H$ and $K$ be the connected components of $G\setminus e$. By induction hypothesis, both $H$ and $K$ are good. Let $T_i$, $i=1, 2$, be the desired spanning trees in the good decompositions of $H$ and $K$. Add $e$ to $T_1\cup T_2$ and consider this tree as the spanning tree in a good decomposition of $G$. Note that we keep cycles and matchings in the good decompositions of $H$ and $K$ to obtain a good decomposition for $G$.\\
\noindent\textbf{Case 2.} Let $G$ be $2$-edge connected. If $G$ is triangle-free, then since $G$ is claw-free, we conclude that $\bigtriangleup (G)\leq 2$. Thus $G$ is a cycle and hence in this case the assertion is trivial. \\
Now, let $xyz$ be a triangle in $G$. First assume that $d_G(x)=d_G(y)=d_G(z)=3$. Since $G$ is $2$-edge connected, $H=G\setminus \{x, y, z\}$ is connected. By induction hypothesis, $H$ admits a good decomposition. Let $e, f$ and $g$ be the three edges with one end-point in $\{x,y,z\}$, and another end-point in $V(H)$. Add $e$, $f$ and $g$ to $T_1$ to obtain a spanning tree for $G$, where $T_1$ is the spanning tree in the good decomposition of $H$. Now, consider $xyz$ as a cycle in the good decomposition of $G$, as desired.
If $d_G(x)=d_G(y)=2$ and $d_G(z)=3$, then $G$ has a cut-edge, a contradiction.\\
Finally assume that $d_G(x)=2$  and $d_G(y)=d_G(z)=3$. Assume that $y$ and $z$ have a common neighbour, say $b\neq x$. Clearly, if $d_G(b)=2$, then $G$ is good. Now, if $d_G(b)=3$, then $G$ has a cut-edge, a contradiction. Now, assume that $N_G(y)\cap N_G(z)= \{x\}$. Identify $x, y$ and $z$. Call the new vertex $a$ and denote the resulting graph by $H'$. Clearly, $H'$ is a claw-free subcubic graph. By induction hypothesis $H'$ has a good decomposition. Let $T_1$ be the spanning tree in the good decomposition of $H'$. If $d_{T_1}(a)=2$, then let $T$ be the spanning tree of  the good decomposition of $G$ formed by $T_1\cup \{xy, yz\}$. Also consider $xz$ as an edge of the matching in the good decomposition of $G$. Finally, assume that $d_{T_1}(a)=1$ and the edge incident with $z$ is contained in $T_1$. Let $T$ be a spanning tree of $G$ formed by $T_1\cup\{xy, yz\}$. Note that $xz$ is contained in the matching in the good decomposition of $G$. The proof is complete.
\end{proof}
\section{Connected $4$-Chordal Subcubic Graphs are Good}
In this section it is shown that every connected $4$-chordal subcubic graph is good.
\begin{theorem}
If $G$ is a connected $4$-chordal subcubic graph, then $G$ is good.
\end{theorem}
\begin{proof}
 We show that if $G$ is not good, then $G$ is planar. By the contrary,
 suppose that  $G$ is not planar. By Kuratowski's Theorem \cite[p.310]{West}, $G$ either contains a subdivision of $K_5$ or a subdivision of $K_{3,3}$. Since every vertex of $K_5$ has degree $4$, $G$ cannot contain a subdivision of $K_5$. Now, suppose that $G$ contains a subdivision of $K_{3,3}$. \\
 First, we introduce some notation which we need for the rest of the proof.\\
 Let $K_{3,3}^*$ be a subgraph of $G$ which is a subdivision of $K_{3,3}$.
For every edge $e\in E(K_{3,3})$, let $L(e)$ be the set of all new added vertices on the edge $e$ in $G$. For every $v\in V(K_{3,3})$, denote the set of all edges incident with $v$ by $\{e_i(v)\mid 1\leq i\leq 3\}$. If for every $e\in E(K_{3,3})$, $L(e)=\varnothing$, then $G= K_{3,3}$ and so $G$ is good, as desired. The rest of the proof is based on the following three claims:
\vspace{2mm}

\noindent{\bf Claim 1.}\label{1}
For every $e\in E(K_{3,3})$, $|L(e)|\geq 2$.\\
\textit{Proof.}
If there exists an edge $e\in E(K_{3,3})$ such that $L(e)=\{p\}$ and $e$ is incident with the vertex $a$ in $K_{3,3}^*$, then let $C$ be a $4$-cycle of $K_{3,3}$ containing $e$. Let $C^*$ be the subdivision of $C$ in $K_{3,3}^*$. Assume that $\langle C^*\rangle$ denotes the induced subgraph of $G$ on $V(C^*)$. If $\langle C^*\rangle$ is chordless, then $G$ has an induced cycle of length at least $5$, a contradiction. Now, let $vw$ be a chord of $\langle C^*\rangle$ in $G$ such that the cycle $a\ldots wv\ldots up$ is chordless in $G$ (Note that maybe there are some vertices between $a$ and $w$ and  also between $v$ and $u$), see Figure 1. So $G$ contains  an induced cycle of length at least $5$,  a contradiction.  The claim is proved.

\vspace{2mm}
\begin{figure}[h!]
\centering
\includegraphics[scale=0.3]{2}
\caption{The subdivision of  a $4$-cycle in $K_{3,3}^*$}
\end{figure}

For every $v\in V(K_{3,3})$, let $M(e_{i}(v))$ be the set of two vertices in $L(e_{i}(v))$ which have the smallest distances from $v$. In particular, for $a\in V(K_{3,3})$, let $M(e_1(a))=\{p,q\}$, $M(e_2(a))=\{r,s\}$ and $M(e_3(a))=\{t,z\}$, see Figure 2.
\begin{figure}[h!]
\centering
\includegraphics[scale=0.3]{1}
 \caption{The subdivision of $K_{3,3}$ in $G$}
 \label{22}
\end{figure}

\vspace{2mm}

\noindent {\bf Claim 2.}\label{2}
 If there exists $v\in \{a,b,c\}$  and $y\in M(e_i(v))$,  for some $i$, $1\leq i\leq 3$, such that  $N_G(y)\cap M(e_j(v))=\varnothing$ for every $j\in \{1, 2, 3\}\setminus\{i\}$, $1 \leq j\leq 3 $, then $G$ is good.\\
\textit{Proof.}
 With no loss generality, assume that $v=a$ and $y=p$. Since $d_G(q)\leq 3$, there exists $j$, $j\in\{2, 3\}$, such that $N_G(q)\cap M(e_j(a))=\varnothing$. Now, consider the $4$-cycle in $K_{3,3}$ containing $e_1(a)$ and $e_j(a)$ and call it by $C$. With no loss generality, let $j=3$.
 Assume that $C^*$ is the subdivision of $C$ in $K_{3,3}^*$.  If $\langle C^*\rangle$ is chordless, then by Claim 1,  $C^*$ is an induced cycle of length at least $12$, a contradiction. Now, suppose that the cycle $\langle C^*\rangle$ has at least one chord. Let $wv$ be that chord in $\langle C^*\rangle$ such that the cycle  $atz\ldots wv\ldots qp$ is chordless (note that maybe $w\in\{t,z\}$). This implies that $G$ has an induced cycle of length at least $5$, see Figure 3, a contradiction.

\begin{figure}[h!]
\centering
\includegraphics[scale=0.3]{3}
\caption{The subdivision of  a $4$-cycle in $K_{3,3}^*$}
\end{figure}
\vspace{2mm}

\noindent {\bf Claim 3.}
If  for every $v\in \{a, b, c\}$ and any $y\in M(e_i(v))$, $i=1,2,3$, $$N_G(y)\cap (\cup_{j\in \{1,2,3\}\setminus \{i\}} M_j(v))\neq \varnothing,$$ then $G$ is good. \\
\textit{Proof.}
 Assume that $v=a$ and with no loss generality $N_G(p)\cap M(e_2(a))= \{r\}$ and $N_G(q)\cap M(e_3(a))= \{z\}$. Obviously, $t$ and $s$ are adjacent and so $G$ contains a $6$-cycle $C: prstzq$. Note that there is no vertex between $p$ and $q$, $r$ and $s$, $t$ and $z$.  Thus this $6$-cycle is  an induced cycle in $G$, a contradiction.
 \vspace{2mm}

Note that if there are $v\in \{a, b, c\}$ and some $i$, $1\leq i\leq 3$ such that  $M(e_i(v))$ contains a vertex of degree $2$, then  by the same  proof of Claim 2, we conclude that $G$ is good. Thus $G$ is planar and  by Corollary $3$ of \cite{Hoff3}, $G$ is good.
\end{proof}

{\small

config: arxiv


TITLE: How can I show that double integral exists?
QUESTION [2 upvotes]: For $Q= [0,1] \times [0,1]$
$$f(x,y) = \begin{cases} 1, \text{ if $x = y$} \\ 0 ,\text{ if $x \neq y$} \end{cases}$$
prove that double integral exists and equals to $ 0$
So I tried to prove this by showing that function is bounded
$0<f<1$ so there is sup and inf.
If I can show sup and inf are the same, then I can say double integral exists.
But how can I show that they are the same?

REPLY [1 votes]: Consider partitioning the unit square $[0,1] \times [0,1]$ into a grid of squares of size $1/n \times 1/n$. Call this partition $\mathcal{P}_n$. Let's calculate the upper sum $U(\mathcal{P}_n,f)$ and the lower sum $L(\mathcal{P}_n,f)$. If we can show that:
$$\lim_{n \rightarrow \infty} U(\mathcal{P}_n,f) = \lim_{n \rightarrow \infty} L(\mathcal{P}_n,f) = 0$$
Then the function is integrable and its integral is zero.
First, $L(\mathcal{P}_n,f) = 0$, since the function $f$ takes the value $0$ at least once on every square.
Second, $U(\mathcal{P}_n,f) = \frac{k}{n^2}$, where $k$ is the number of squares on which $f(x,y) = 1$ for some point in that square. This only happens for squares that intersect the diagonal. Those are the squares on the diagonal (there are $n$ of these), the squares directly above the diagonal ($n-1$ of these) and directly below (also $n-1$). So $k = n + n-1 + n-1 = 3n-2$. And so:
$$\lim_{n \rightarrow \infty} U(\mathcal{P}_n,f) = \lim_{n \rightarrow \infty} \frac{3n - 2}{n^2} = 0$$


TITLE: show that the characteristic polynomial of this matrix has negative coefficients
QUESTION [6 upvotes]: Let $n\geq 2$,  $A$ be the $n\times n$ matrix $A=(a_{ij})$ where $a_{ij}=\max(i,j)$.
Can anybody show that the characteristic polynomial
$P(x)=\det(xI-A)$ has all its coefficients negative except the leading one?
I have checked this for $2 \leq n \leq 20$.

REPLY [3 votes]: Here is a sketch. The calculations that need to be filled in are easy to do, but please let me know if you'd like me to edit it for more detail.
We have:

$$A^{-1}=\begin{bmatrix} -1 & 1 & 0 & 0 & 0 & \cdots & 0& 0 & 0\\1 & -2 & 1 & 0&0&\cdots & 0& 0 & 0\\ 0 & 1 & -2 & 1 & 0 & \cdots & 0& 0 & 0\\\vdots&\vdots&\vdots&\vdots&\vdots&\ddots&\vdots&\vdots&\vdots\\0 & 0 & 0 &0  & 0 & \cdots & 1& -2 & 1\\0 & 0 & 0 &0  & 0 & \cdots & 0& 1 & \frac{1-n}{n}
\end{bmatrix}.$$

The important point here is that $A^{-1}$ is a tridiagonal matrix and so the recursion to find the determinant is nice. In particular, we have $$\det(xI-A^{-1}) = \left(x+\frac{n-1}{n}\right)f_{n-1}(x)-f_{n-2}(x),$$ where $f_m(x)$ is the characteristic polynomial of the $m\times m$ leading principle submatrix. Note that all of these have the same form and so the recursive formula for the determinant yields the following, which is also straightforward to check by induction.

For $1\leq m\leq n-1$,  we have $$f_m(x) = \sum_{k=0}^m{m+k\choose m-k}x^k.$$

A little work now shows:

$$\det(xI-A^{-1}) = x^n + \sum_{k=1}^{n-1}\left({n-1+k\choose n-k}-\frac{1}{n}{n-1+k\choose n-1-k}\right)x^k - \frac{1}{n}.$$

All coefficients besides the constant one are positive. This implies your desired fact using the well-known relation between the characteristic polynomial of $A$ and $A^{-1}$.


TITLE: Extended Liouville Polynomial Inequality
QUESTION [2 upvotes]: I am trying to show that the noted inequality holds without using the Euclidean Algorithm. This appears in Complex Analysis by Newman and Bak on the top of page 63 (remark 1, my paraphrase):
If $\alpha$ is a zero of an $n^{th}$ degree polynomial $P_n$, then $P_n(z)=(z-\alpha)P_{n-1}$, where $P_{n-1}$ is a polynomial of degree $n-1$. This can be seen by noting that
$$|\frac{P_n(z)}{z-\alpha}|\le A+B|z|^{n-1}$$
and hence is equal to an $(n-1)^{st}$ degree polynomial by the Extended Liouville Theorem.
I am having trouble showing the noted inequality. Furthermore, even if the inequality holds, doesn't the Extended Liouville Theorem merely say that the degree of the polynomial is at most $n-1$?

REPLY [1 votes]: I suggest a completely different approach:
From the geometric sum formula (which I assume you are familiar with)
$$
(z^k-\alpha^k)=(z-\alpha)(z^{k-1}+z^{k-2}\alpha+\cdots+z\alpha^{k-2}+\alpha^{k-1})\tag{1}.
$$
Since $P$ is a polynomial of degree $n$, it is on the form
$$
P(z)=a_nz^n+\cdots+a_1z+a_0.
$$
In particular, if $\alpha$ is a zero of $P$, then
$$
\begin{aligned}
P(z)&=P(z)-P(\alpha)\\
&=a_n(z^n-\alpha^n)+\cdots+a_k(z^k-\alpha^k)+\cdots+ a_1(z-\alpha)+a_0-a_0
\end{aligned}
$$
Here, we can factor $z-\alpha$ from each term according to $(1)$. From the first term, we get the highest order term,
$$
a_n(z^n-\alpha^n)=(z-\alpha)(a_n z^{n-1}+\cdots).
$$
Thus, we condlude that
$$
P(z)=(z-\alpha)\tilde{P}(z),
$$
where $\tilde{P}$ is a polynomial of degree $n-1$ (the coefficient in front of $z^{n-1}$ is $a_n$).
Now, I guess you can proceed proving the inequality (if you really want to).


TITLE: Finding foot of perpendicular of centre of ellipse on its variable tangent
QUESTION [2 upvotes]: Find the locus of the foot of perpendicular from the centre of the ellipse $${x^2\over a^2} +{y^2\over b^2} = 1$$
on the chord joining the points whose eccentric angles differ by $π/2.$
Ref:Locus of foot of perpendicular of origin from tangent of ellipse, related

The points may be given as $(a\cos \alpha, b\sin \alpha)$ and $(-a\sin \alpha , b \cos \alpha )$, then their midpoint is given as: $\left( \frac{a}{2} (\cos \alpha - \sin \alpha) , \frac{b}{2} (\cos \alpha + \sin \alpha) \right)=(\kappa, \beta)$, the equation of chord given midpoint of ellipse is:
$$ \frac{\kappa X}{a^2} + \frac{\beta Y}{b^2} = \frac{\kappa^2}{a^2} + \frac{\beta^2}{b^2} $$
Let $u= \frac{\cos \alpha - \sin \alpha}{2}$ and $ v=\frac{\cos \alpha + \sin \alpha}{2}$, then our equation becomes:
$$\frac{ uX}{a} + \frac{ vY}{b} = u^2 + v^2 $$
Foot of perpendicular from origin for above line is given as:
$$ \frac{ax}{u}= \frac{by}{v}= \frac{(ab)^2 (u^2 +v^2)}{b^2u^2 +a^2v^2}$$
$ax= u(\frac{(ab)^2 (u^2 +v^2)}{b^2u^2 +a^2v^2})$
and $by =v (\frac{(ab)^2 (u^2 +v^2)}{b^2u^2 +a^2v^2})$, following the last line of this answer, I squared and added:
$$(ax)^2 + (by)^2 = (ab)^4  \left[ \frac{u^2 +v^2}{b^2 u^2 +a^2v^2} \right]^2= \frac{(ab)^4}{4} \left[ \frac{1}{b^2 u^2 + a^2 v^2}\right]^2$$
How do I write bracketed term in purely $(x,y)$?

REPLY [2 votes]: You are missing a $(u^2+v^2)$ when you add $(ax)^2$ and $(by)^2$.
Just in case, you want to finish continuing from the point you got to,
$(ax)^2 + (by)^2 = (ab)^4 (u^2+v^2)  \left[ \frac{u^2 +v^2}{b^2 u^2 +a^2v^2} \right]^2$
$ = \cfrac{(ab)^4}{2}  \left[ \frac{(u/v)^2 +1}{b^2 (u/v)^2 + a^2} \right]^2$
Now note that $\cfrac{u}{v} = \cfrac{ax}{by}$
That leads to $2 (x^2+y^2)^2 = (ax)^2 + (by)^2$
or we could have substituted $u = k a x, v = k by$ in RHS.


TITLE: non time constructible functions
QUESTION [10 upvotes]: A function $T: \mathbb N  \rightarrow \mathbb N$ is time
  constructible if $T(n) \geq n$    and there is a $TM$  $M$ that computes
  the function $x \mapsto \llcorner T(\vert x\vert) \lrcorner$ in time $T(n)$. ($\llcorner T(\vert x\vert) \lrcorner$ denotes the binary representation of
  the number $T(\vert x\vert)$.)
Examples for time-constructible
  functions are $n$, $nlogn$, $n^2$, $2^n$. Time bounds that are not
  time constructible can lead to anomalous results.

--Arora, Barak.
This is the definition of time-constructible functions in Computational Complexity - A Modern Approach by Sanjeev Arora and Boaz Barak.
It is hard to find valid examples of non-time-constructible functions. $f(n)=c$ is an example of a non-time-constructible function. What more (sophisticated) examples are out there?

REPLY [1 votes]: According to the definition of Arora, trigonometric functions are not good counter-examples since they are not functions from $\mathbb{N}$ to $\mathbb{N}$.
However, the function $TUC : \mathbb{N} \rightarrow \mathbb{N}$ defined by $TUC(n) = n$ if $M_n(n) \neq n$ and $TUC(n) = 2n + 1$ otherwise, is not time-constructible:
Suppose there exists $M$ that computes $TUC$ in $TUC(n)$ time, then there exist $n$ such that $M = M_n$ (cf. encoding of a Turing machine in Arora's book), but
-if $TUC(n) = n$, then $M(n) \neq n$ and so $TUC(n) \neq n$ $\rightarrow$ contradiction.
-if $TUC(n) = 2n +1 $, then $M(n) = n$ and so $TUC(n) = n$ $\rightarrow$ contradiction.
Both cases end up to a contradiction so $TUC$ is not time-constructible.


TITLE: What are the other ways of energy transfer apart from heat and work?
QUESTION [3 upvotes]: In my physics textbook I've seen that heat and work are non mechanical and mechanical forms of transfer of energy. Why can't electrical or chemical or nuclear energy or energies like that be a form of transfer of energy? Why is it only heat and work?

REPLY [4 votes]: As defined in thermodynamics, heat is energy that crosses a boundary of a system without mass transfer due solely to a temperature difference between the system and its surroundings, and work is energy that crosses a boundary of a system without mass transfer due to any intensive property difference other than temperature between the system and its surroundings.  So, work includes all non-temperature driven transfers of energy across a system boundary, excluding mass transfer, such as electrical work in addition to mechanical work (force causing movement). Note that neither heat nor work include mass transfer.
Mass transfer across a system boundary is another way besides heat and work for energy to enter or leave a system.  Thermodynamics addresses mass transfer by using an open system, one defined where mass transfer occurs across the system boundary.
A closed system is defined in thermodynamics as one for which no heat, work, or mass transfer occurs. Within a closed system, exothermic chemical or nuclear reactions can increase the pressure/temperature within the system, and in that sense are transfers of energy. Classical thermodynamics address such internal energy sources using heat of formation or heat of reaction.  We now know, thanks to Einstein, that such exothermic reactions convert rest mass to kinetic energy.  (That is, the rest masses of the products of the exothermic reaction are less than the rest masses of the reactants, and that difference is an increase in kinetic energy of the products over the reactants.)


text:
\renewcommand{\partname}{}
\renewcommand{\thesection}{\Roman{section}}
\part{Supplementary material}

In this supplementary material (SM), we provide the proofs and computation details leading to the results presented in the main manuscript.
In Sec.~\ref{appendix:definitions}, we first recall the definition of the statistical model used in Sec.~\ref{sec:introduction} and we give proper definitions of the denoising distributions involved in the analysis of the Bayes-optimal and Empirical Risk Minimization (ERM) estimation. In particular, we provide the analytical expressions of the denoising functions used in Sec.~\ref{sec:applications} to analyze ridge, hinge and logistic regressions.
In Sec.~\ref{appendix:generalization_error}, we detail the computation of the binary classification generalization error leading to the expressions in Proposition.~\ref{main:thm:generalization_errors} and Thm.~\ref{main:thm:fixed_point_equations_bayes} respectively for ERM and Bayes-optimal estimation.
In Sec.~\ref{appendix:proof}, we present the proofs of the central theorems stated in Sec.~\ref{sec:fixed_point}. In particular, we derive the Gordon-based proof of the Thm.~\ref{main:thm:gordon_fixed_points:classification} in the more general \emph{regression} (real-valued) version and provide as well the proof of Corollary.~\ref{main:corollary:equivalence_gordon_replicas_formulation_l2} which establishes the equivalence between the set of fixed-point equations of the Gordon's proof in the binary classification case and the one resulting from the heuristic replica computation.
The corresponding statistical physics framework used to analyze Bayes and ERM statistical estimations and the replica computation leading to expressions in Corollary.~\ref{main:corollary:equivalence_gordon_replicas_formulation_l2} are detailed In Sec.~\ref{appendix:replicas}.
The section \ref{appendix:applications} is devoted to provide additional technical details on the results with $\rL_2$ regularization addressed in Sec.~\ref{sec:applications}. In particular, we present the large $\alpha$ expansions of the generalization error for the \emph{Bayes-optimal}, \emph{ridge}, \emph{pseudo-inverse} and \emph{max-margin} estimators, and we investigate the performances of logistic regression on non-linearly separable data.
Finally in Sec.~\ref{appendix:optimal_loss_reg}, we show the derivation of the fine-tuned loss and regularizer provably leading to Bayes-optimal performances, as explained and advocated in Sec.~\ref{sec:optimality}, and we show some numerical evidences that ERM achieves indeed Bayes-optimal error in Fig.~\ref{fig:opt_loss_reg_sign_gaussian_numerics}.

\newpage
\setcounter{tocdepth}{4}
\parttoc
\newpage

\section{Definitions and notations}
\input{files/supplementary/definitions.tex}

\newpage
\section{Binary classification generalization errors}
\input{files/supplementary/generalization_error.tex}

\newpage
\section{Proofs of the ERM fixed points}
\input{files/supplementary/proof.tex}

\newpage
\section{Replica computation for Bayes-optimal and ERM estimations}
\input{files/supplementary/replicas.tex}

\newpage
\section{Applications}
\input{files/supplementary/applications.tex}

\newpage
\section{Reaching Bayes optimality}
\input{files/supplementary/optimality.tex}


TITLE: What does "smooth solution" of Ricci flow mean?
QUESTION [13 upvotes]: A way to formalize smoothness of a flow is to think of the spacetime, see e.g.
here. Let's say we are flowing a compact manifold $M$.
Which of the following is true?

$g_{ij}$ is a $C^1$ in time and $C^\infty$ in the space coordinate.
$g_{ij}$ is a $C^\infty$ function on the spacetime?
$g_{ij}$ is a $C^1$ function on the spacetime?

I think 2 is correct but then I am confused about Shi's estimates for higher derivatives. If two nearby metrics are $C^\infty$ close then all derivatives of the curvature tensor are also close, but Shi's estimates blow up when $t\to 0$. What am I missing? Update:  I see the source of my confusion about Shi's estimates: the constants there depend only on the dimension and bounds on
curvature tensor, but are otherwise independent of the initial metric.
So this does not contradict 2.
I suppose the answer is based on a general PDE principle. What is a good reference?
Finally, will anything change if we a flowing a non-compact manifold (on which Ricci flow exists and is smooth)?

REPLY [0 votes]: #2 is correct. You can see for instance sections 4-6 of Hamilton's 1982 paper, where his Nash-Moser theorem is applied directly on the Fréchet space of smooth sections of the pullback of the symmetric 2-tensor bundle to $M\times[0,1]$.
On any manifold whatsoever, "elliptic/parabolic regularity" results will imply that a family of metrics of even low assumed regularity which satisfy the Ricci flow equation must be smooth in the #2 sense. This is a purely local question and so is covered by purely PDE results. A standard reference with various levels of assumed regularity is Lieberman "Second order parabolic differential equation."


TITLE: For which values of parameter $a$, the sequence is convergent in $L^2$?
QUESTION [2 upvotes]: For which values of parameter $a$, the series $Z_{n} = n^{\frac{1}{3}}(S_{n}-a)$ is convergent in $L^2$?
Where $ S_{n} = \frac{1}{n}(X_{1} + \cdots + X_{n}) $ with density $f(x) = 3x^{2}\mathbb{1}_{[0,1]}$
Edit:
$X_{1} \ldots X_{n}$ are i.i.d. from, they have the same density function .
Converges in the p-th mean $X_{n}$ to $X $ in $L^p$ if the r-th absolute moments $E(|X_{n}|^{p})$ and $E(|X|^{p})$ of $X_{n}$ and $X$ exist, and $\lim _{n\to \infty }\operatorname {E} \left(|X_{n}-X|^{2}\right)=0$.
From Strong law of large number, we have that
$S_{n}$ converges almost surely to $E(X_{1}) = \frac{3}{4}$

If $ a \neq E(X_{1}) $ then $Z_{n}$ not converges.
IF $ a = E(X_{1}) $ then $Z_{n}$ converges to $0$.

This is my result.

REPLY [1 votes]: This is indeed correct, but some justifications are needed. For example, when $a\neq 3/4$ we know that we do not have the almost sure convergence to $0$ but this would not a priori exclude that we have convergence in $L^2$. But convergence in $L^2$ implies almost sure convergence of a subsequence hence it $Z_n$ was convergent in $L^2$ to $0$, we would have that $Z_{n_k}\to 0$ almost surely for a subsequence $(Z_{n_k})$, a contradiction.
When $a=3/4$, $Z_n=\frac 1{n^{4/3}}\sum_{i=1}^n\left(X_i-3/4\right)$ and the variance can be computed by noticing that the random variables $X_i-3/4$, $1\leqslant i\leqslant n$, are uncorrelated.


TITLE: $T_1$ space violating cardinal bound which every $T_2$ space satisfy
QUESTION [2 upvotes]: Let $X$ be a $T_2$ space. $T_2$ space is a topological space where every singleton is the intersection of its closed neighbourhoods i.e. $\{x\} = \bigcap_{x \in U, U \text{open}} \overline{U}$. If $D$ is a dense subset of $X$, $\{x\} = \bigcap_{x \in U, U \in B(x)} \overline{D \cap U}$, where $B(x)$ is a local base for $x$. Every $x$ is determined by $\lvert B(x) \rvert$ subsets of $D$, thus $\lvert X \rvert \le 2^{d(X)\chi(X)}$, where $d(X)$ is the density and $\chi(X)$ is the character. We can get a more tight bound. For every $U \in B(x)$, pick $x_U \in U \cap D$, and let $D(x) = \{ x_U \mid U \in B(x) \}$. Since $\{x\} = \bigcap_{x \in U, U \in B(x)} \overline{D(x) \cap U}$, every $x$ is determined by $\lvert B(x) \rvert$ subsets of $D$ whose cardinality is $\le \lvert B(x) \rvert$. Thus $\lvert X \rvert \le d(x)^{\chi(X) \times \chi(X)} = d(X)^{\chi(X)}$ when $\chi(X)$ is infinite. If $\chi(X)$ is finite $X$ is discrete thus $d(X) = \lvert X \rvert$, making the inequality trivial.
I want to find a $T_1$ space which violates $\lvert X \rvert \le d(X)^{\chi(X)}$, but cofinite topology didn't work since $\chi(X) = \lvert X \rvert$. Any counterexamples?

REPLY [0 votes]: Choose a cardinal $\kappa\gt\mathfrak c$. Then $\tau=\{\varnothing\}\cup\{U\subseteq\kappa:\omega\setminus U\text{ is finite}\}$ is a $T_1$ topology on $\kappa$. The space $X=(\kappa,\tau)$ has $d(X)=\chi(X)=\omega$ but $|X|=\kappa$.


TITLE: Probability of A,B,C's individual occurrences in groups of 2
QUESTION [0 upvotes]: First. If anyone can help me with a title for this to more accurately describe my issue that'd be greatly appreciated. If you have 3 events that occur in groups such as:
AA
AB
AC
BB
BC
CC
(AB is the same as BA), then what is the probability of the groups including A or B or C. It seems that out of the 6 groups, each individual event occurs in half the groups. I know you can't have 3 events with each having a probability of .5 so I'm unsure how to actually analyze this problem.

REPLY [1 votes]: Actually, you can have three events having probability of 0.5. There would only be a problem if those events could not overlap.
If the process is: choose one of $\{A,B,C\}$ to be the first element, and choose one of $\{A,B,C\}$ to be another element, then mixed pairs are more likely than duplicates:
$$\begin{array}{c|ccc}
&A&B&C\\\hline
A&AA & AB & AC \\
B&BA  & BB & BC \\
C&CA  &  CB   & CC
\end{array}$$
and the probability of, say, the result containing $A$ is $\frac{5}{9}$, because five of the nine entries contain A. The same is true for the result containing $B$, or the result containing $C$. These cases overlap (e.g. there's an entry containing $A$ and containing $B$), so these probabilities aren't a problem.

But the process might instead be: choose one of the six different possible pairs uniformly at random from this table.
$$\begin{array}{c|ccc}
&A&B&C\\\hline
A&AA & AB & AC \\
B&   & BB & BC \\
C&   &    & CC
\end{array}$$
Here are your six events. You can see three of them contain A, three contain B, and three contain C, so the probability of each of those cases is 3/6 = 50%.  The cases overlap (e.g. there's one that contains A and contains B), so there's no problem with these probability results.