TITLE: Is this type of "definable bijective solution" of combinatorial identities symmetric?
QUESTION [10 upvotes]: Say that a combinatorial problem is a pair of first-order sentences $\langle\varphi,\psi\rangle$ in (disjoint and relational, for simplicity) finite languages $\Sigma=\{R_1,...,R_l\},\Pi=\{S_1,...,S_m\}$ respectively such that for each finite set $X$, the sets $Mod_X(\varphi),Mod_X(\psi)$ of isomorphism types of models of $\varphi,\psi$ respectively with domain $X$ have the same cardinality. (The components of a combinatorial problem are just particularly simple combinatorial species.)
I'm interested in the class of combinatorial problems $\langle\varphi,\psi\rangle$ for which we can, in a first-order-definable way, establish a bijection between $\varphi$-models and $\psi$-models (on a fixed finite set) possibly with the additional help of some auxiliary structure on that set. Formally, say that $\langle\varphi,\psi\rangle$ is definably solvable iff there is a language $\Gamma=\{T_1,...,T_n\}$ disjoint from both $\Sigma$ and $\Pi$, a first-order $\Gamma$-sentence $\lambda$, and a tuple of $\mathsf{FOL}[\Sigma\cup\Gamma]$-formulas $(\theta_i)_{1\le i\le m}$ such that the following hold for every finite set $X$:

Whenever $Mod_X(\varphi)\not=\emptyset$ we also have $Mod_X(\lambda)\not=\emptyset$.

For each $1\le i\le m$, $\theta_i$ is a formula with the same arity (in terms of free variables) as the symbol $S_i$.

If $Mod_X(\varphi)\not=\emptyset$, $\mathcal{X}$ is a $\Sigma\cup\Gamma$-structure with domain $X$ such that $\mathcal{X}\models\lambda\wedge\varphi$, then:

The structure $(X;(\theta_i^\mathcal{X})_{1\le i\le m})$ is a model of $\psi$.

For every $\Sigma\cup\Gamma$-structure $\mathcal{Y}\models\lambda\wedge\varphi$ with domain $\mathcal{X}$, we have $$\mathcal{X}\upharpoonright\Sigma\cong\mathcal{Y}\upharpoonright\Sigma\quad\iff\quad(X;(\theta_i^\mathcal{X})_{1\le i\le m})\cong (X;(\theta_i^\mathcal{Y})_{1\le i\le m}).$$

For example, with $E$ a binary relation symbol let $\pi_2$ = "$E$ is a partition of the domain into pairs or singletons" and let $\pi^2$ = "$E$ is a partition of the domain into two pieces." This question sketches why the combinatorial problem $\langle\pi_2,\pi^2\rangle$ is definably solvable. With a bit of tedium, one can show that $\langle\pi^2,\pi_2\rangle$ is also definably solvable. I'm curious whether this always holds:

If $\langle\varphi,\psi\rangle$ is a definably solvable combinatorial problem, must $\langle\psi,\varphi\rangle$ also be definably solvable?

(I would also be interested in results for the analogous notion defined with some not-too-strong logic $\mathcal{L}$ in place of first-order logic. Even second-order logic isn't so strong, at first glance, as to trivialize the situation! But my main focus is on $\mathsf{FOL}$.)

REPLY [2 votes]: It’s not symmetric. Here are two examples. The idea is to take $\Sigma,\phi$ to be $\Pi,\psi$ augmented with hard-to-compute but uniquely determined structure.
I’ll make use of results for $AC^0/\text{poly}$ circuits. A first-order formula can be implemented as $AC^0$ circuits by replacing quantifiers by conjunctions or disjunctions over the domain. Details are given in Immerman’s Descriptive Complexity Theorem 5.22 (and Meta-Proposition 11.19).
No use is made of the assumption that $\lambda$ is first-order.
First example:
$\Sigma,\phi$: a total order $<$ and a compatible BIT predicate, and a 1-ary relation $R_1$ that is an initial segment of $<$
$\Pi,\psi$: no axioms, just a 1-ary relation $S_1$
The BIT predicate can be axiomatized by specifying that the least element has all zero bits, and the bits of the successor of $n$ are calculated by flipping the least significant bits of $n$ up to and including the least significant zero.
There are $|X|+1$ models of each theory. $\langle \phi_1,\psi_1\rangle$ is definably solvable by taking $\theta_1(x)=R_1(x).$
Suppose that $\langle \psi,\phi\rangle$ were definably solvable.Then there would be quasipolynomial size constant depth circuits for computing the parity function, contradicting Håstad's switching lemma bound.
Fix $X$ and a $\Gamma$-structure satisfying $\lambda.$ Let $N_{X}$ be the set of $\lfloor n/2\rfloor$ possible values of $|R_1|$ that you get from inputs with $|S_1|$ odd. (More precisely: values of $|\theta_1^{\mathcal X}|$ where $\mathcal X$ is a $\Pi\cup\Gamma$ structure with the chosen $\Gamma$ structure as a reduct, and with $|S_1^{\mathcal X}|$ odd.) The circuit takes (the characteristic function of an interpretation of) $S_1$ as input, and can apply circuits for the $\theta_i$ formulas to compute $<,$ BIT, and $R_1$ as polynomial-size, constant depth subcircuits. It guesses the $<$-first $\log n$ elements, trying all $n^{\log n}$ options in parallel, verifying using circuits for $<.$ It then tests the BIT representation of the $<$-first element $x$ satisfying $\neg R_1(x)$ (if any) against each of the values in $N_X.$ The circuit outputs $1$ if any of these values is hit, or if $|X|\in N_X$ and $\forall x.R_1(x)$ holds.
Second example:
$\Sigma,\phi$: a total order, and a 1-ary relation $R_1,$ and a deterministic  easily-verifiable derivation of the output of the function $h$ in Sampling Lower Bounds: Boolean Average-Case and Permutations, Emanuele Viola, Theorem 2, applied to the characteristic function of $R_1$
$\Pi,\psi$: a total order, and a 1-ary relation $S_1$
For example, the derivation could be an encoding of a complete record of every step taken by a fixed polynomial-time Turing machine computing $h,$ including the entire tape at each step as a polynomial-sized bitstring, together with basic arithmetic operations to make all this data verifiable by a first-order predicate.
There are $2^{|X|}$ models of each theory. $\langle \phi,\psi\rangle$ is definably solvable by taking $\theta_1(x)=R_1(x).$  Suppose that $\langle \psi,\phi\rangle$ were definably solvable. Then there would be polynomial size constant depth circuits giving the correct distribution on $(R_1,h(R_1))$ when given a uniformly chosen bitstring $S_1$ as input. Viola’s Theorem 2 says that such a small circuit cannot give anything like the correct distribution.


text:
\section{Anytime pMHE Algorithm}
\label{sec: iteration scheme}
In this section, we propose a novel pMHE iteration scheme in which, at each time instant $k$, problem (\ref{condensed}) is approximately solved by executing  a fixed number $\mathrm{it}(k) \in \mathbb{N}_+$ of optimization algorithm iterations. In more details, at each time $k$, a suitable warm start $\mathbf{\hat{z}}^{0}_{k}$ is generated from a stabilizing a priori estimate $\mathbf{\bar{z}}_k$ and an iterative optimization update is  carried out, from which the sequence   $\big\lbrace  \mathbf{\hat{z}}^{i}_{k}   \big\rbrace $ with $i=1,\cdots,\mathrm{it}(k)$ is obtained. The steps of the scheme are given in Algorithm~\ref{alg: eta changes} and illustrated in Figure \ref{Fig: iteration scheme}.
\begin{figure}[ht]
  \centering
\input{figures/iteration_scheme_sketch}
\caption{Illustration of the steps of the pMHE iteration scheme at the time instants $k-1$ and $k$, with the corresponding $\mathrm{it}(k-~1)=4$  and $\mathrm{it}(k)=3$ optimization iterations. }
\label{Fig: iteration scheme}
\end{figure}
~\\Before we explain the proposed  algorithm in more detail, and for the sake of clarity, let us first introduce  some notations. The index $k$ denotes the time instant in which we receive a new measurement and $\mathrm{it}(k)$ is the number of iterations of the optimization algorithm between time instants $k$ and $k+1$. Moreover, we introduce
\begin{align}
\label{notation}
\hspace{-0.4cm}\mathbf{\hat{z}}^{ i}_{k} \coloneqq \begin{bmatrix}
				 \hat{x}^{ i}_{k-N} \\[0.2em]  \hat{w}_{k-N}^{ i} \\\vdots  \\[0.2em]  \hat{w}_{k-1}^{ i}    \end{bmatrix}, \enskip
 \mathbf{\bar{z}}_k \coloneqq \begin{bmatrix}
 \bar{x}_{k-N}\\[0.2em]  \bar{w}_{k-N}\\\vdots  \\[0.2em]  \bar{w}_{k-1}
 \end{bmatrix}, \enskip
     \mathbf{z}_k \coloneqq \begin{bmatrix}
				 x_{k-N}  \\[0.21em] 0 \\\vdots  \\[0.21em]  0  \end{bmatrix}.
 \end{align}
  With $\mathbf{\hat{z}}^{ i}_{k} $, we denote the $i$-th iterate of the optimization algorithm at time $k$.
With $ \mathbf{\bar{z}}_k $, we refer to the a priori estimate at time $k$ and with   $ \mathbf{z}_k$ 	 to the true state $x_{k-N}$ with true model residual sequence    $  \lbrace  0  , \cdots , 0  \rbrace $.

Upon arrival of a new measurement at time $k$, the optimization algorithm is initialized based on the a priori estimate~$\mathbf{\bar{z}}_k$.  In particular, we compute the warm start $\mathbf{\hat{z}}^{0}_{k}$ as the Bregman projection  of $\mathbf{\bar{z}}_k$ onto the constraint set $ \mathcal{S}_k$ as formulated in line~3 of Algorithm \ref{alg: eta changes}.
Then, a fixed number $\mathrm{it}(k)$ of optimization iterations is performed via (\ref{optAdap}), generating $\big\lbrace  \mathbf{\hat{z}}^{1}_{k}, \cdots,\mathbf{\hat{z}}^{\mathrm{it}(k)}_{k} \big\rbrace $. Here, $\eta_k^i >0$ denotes the step size employed at the $i$-th iteration at time $k$. From this sequence of iterates, an arbitrary iterate  $\mathbf{\hat{z}}^{\mathrm{j}(k)}_{k} $, $\mathrm{j}(k) \in \lbrace 0,\cdots,\mathrm{it}(k)\rbrace$ can be chosen, based on which the state estimate $\hat{x}_k$ is obtained using
\begin{align}
		\label{StateEst}
\hat{x}_k =A^N\, \hat{x}^{\mathrm{j}(k)}_{k-N}+ \!\!\sum_{j=k-N} ^ {k-1}\! \! A^{k-1-j}\, \left( B\,  u_j+ \hat{w}^{\mathrm{j}(k)}_{j} \right)
\end{align}
for $k>N$ (see Remark \ref{rem: indices} for the case where $0< k \leq N$). Moreover, the a priori estimate $ \mathbf{\bar{z}}_{k+1} $ for the next time instant is computed through the operator $\Phi_k : \mathbb{R}^{(N+1)n} \rightarrow \mathbb{R}^{(N+1)n}$ which will be defined in~\eqref{Adap: warm}.  As mentioned above, the basic idea of the  pMHE framework is to use the Bregman distance~$D_\psi$ as a proximity measure to a  stabilizing a priori estimate in order to inherit its  stability properties. Since the Luenberger observer  appears as a simple candidate for constructing the a priori estimates,  we require that the operator $\Phi_k$ incorporates its dynamics as follows:
			    \begin{align}
			     \label{Adap: warm}
\Phi_k \left( \mathbf{\hat{z}}^{ \mathrm{j}(k)}_{k} \right) \! \coloneqq  \!  \begin{bmatrix}
   \! A\,  \hat{x}_{k-N}^{ \mathrm{j}(k)} +\!B\, u_{k-N}+\!L \left(y_{k-N} - C  \hat{x}_{k-N}^{ \mathrm{j}(k)} \right)     \\\mathbf{0}
     \end{bmatrix}\!,
       \end{align}
where $\mathbf{0}\in \mathbb{R}^{Nn}$. Here, the observer gain $L$ is chosen such that all the eigenvalues of $A-LC$ are strictly within the unit circle.
 \begin{algorithm} [t]
\caption{Anytime pMHE}
\label{alg: eta changes}
\begin{algorithmic}[1]
\State  \textbf{Initialize:}   Choose  $ \hat{x}_0  $ and set $ \bar{\mathbf{z}}_0  =\hat{x}_0$
  \For {$k=1,2, \cdots$  }
    \State  $ \mathbf{\hat{z}}_k^0= \argmin\limits_{\quad\enskip\mathbf{z}\in  \mathcal{S}_k} \quad  D_\psi (\mathbf{z},\mathbf{\bar{z}}_k)$  warm start
      \For {$i= 0,\dots, \mathrm{it}(k)-1$ } optimizer update
      \begin{align}
  \label{optAdap}
\hspace*{-0.2cm}  \mathbf{\hat{z}}^{i+1}_{k}=\argmin_{\quad\enskip\mathbf{z}\in  \mathcal{S}_k}\left\lbrace  \eta_k^i\,    \nabla f_k\left(  \mathbf{\hat{z}}^{i}_{k} \right)^\top \mathbf{z}+ D_\psi (\mathbf{z},  \mathbf{\hat{z}}^{i}_{k}) \right\rbrace
   \end{align}
		\EndFor
		\State for some $\mathrm{j}(k) \in \lbrace 0,\cdots,\mathrm{it}(k)\rbrace$ obtain $\hat{x}_k$ from (\ref{StateEst})
		\State  $\mathbf{\bar{z}}_{k+1} =\Phi_k \left( \mathbf{\hat{z}}^{\mathrm{j}(k)}_{k} \right)$
		\EndFor
\end{algorithmic}
\end{algorithm}
In the following, we compare Algorithm~\ref{alg: eta changes} with our earlier formulation of pMHE, given in  Algorithm~\ref{alg: optimal pMHE}.
 Observe that, while a solution of the optimization problem  (\ref{condensedpMHE}) is computed,  step~4 in Algorithm \ref{alg: eta changes} employs the so-called  mirror descent algorithm~\cite{beck2003mirror} that iterates~\eqref{optAdap}  until  a given number of iterations $\mathrm{it}(k)$ is achieved. For $D_\psi \left( \mathbf{z}_1, \mathbf{z}_2 \right) = \frac{1}{2} \left\Vert \mathbf{z}_1 -  \mathbf{z}_2 \right\Vert^2$ and $ \mathcal{S}_k=\mathbb{R}^{(N+1)n}$, the optimizer update step (\ref{optAdap}) corresponds to an iteration step of the classical gradient descent algorithm and hence step 4
 can be executed very quickly.
In the constrained case, (\ref{optAdap}) can be regarded as a generalization of the projected gradient algorithm \cite{beck2003mirror}.  For this reason, we can view Algorithm  \ref{alg: eta changes} as a real-time version of the pMHE scheme given  in  Algorithm~\ref{alg: optimal pMHE}. \rev{Note also that choosing the so-called Kullback-Leiber divergence  as Bregman distance yields the efficient entropic descent algorithm if the constraint set is given by the unit simplex  \cite{beck2003mirror}.} An appealing feature of  Algorithm \ref{alg: eta changes} is that, depending on the available computation time between two subsequent time instants $k$ and $k+1$, the user can specify a maximum number of iterations $\mathrm{it}(k)$ after which   the optimization algorithm at time $k$ has to return a solution. \\
Another key difference between the two algorithms is that Algorithm \ref{alg: optimal pMHE}  is biased by the stabilizing a priori estimate $\bar{\mathbf{z}}_k$, while this bias  is fading away  in  Algorithm \ref{alg: eta changes}. In other words, the a priori estimate constructed based on the Luenberger observer (\ref{Adap: warm}) has less impact at each optimization iteration, which improves the performance of the pMHE iteration scheme.
This is due to the fact that $\bar{\mathbf{z}}_k$
might  degenerate  performance in Algorithm \ref{alg: optimal pMHE}, since
the  solution lies in proximity to the a priori estimate.
In Algorithm \ref{alg: eta changes}, however, the Luenberger observer enters
only in the warm start. From this point of view,
it is quite surprising that, even though the effect of this stabilizing ingredient is fading away, stability is provably preserved, as we will show in the subsequent section. Thus, this "implicit stabilizing regularization"
approach of the a priori estimate
is in contrast to the explicit stabilizing regularization proposed in \cite{sui2014linear,gharbi2018proximity} (see also \cite{belabbas2020implicit}).
Moreover, the proposed MHE algorithm possesses the anytime property.
  The \emph{anytime} property refers to the fact that the algorithm will yield stable estimation errors after any number of  optimization algorithm iterations. This is similar in spirit to anytime model predictive control (MPC) algorithms, which compute stabilizing  control inputs after any  optimization iteration \cite{feller2017stabilizing,feller2018sparsity}.
\begin{rem} \label{rem: indices} For $k \leq N$, we can employ the steps of Algorithm \ref{alg: eta changes} by setting all the negative indices to zero. More specifically,
$  \mathbf{\hat{z}}^{ i}_{k} =\begin{bmatrix} (\hat{x}^{ i}_{0})^\top &  (\hat{w}_{0}^{ i})^\top & \hdots  & (\hat{w}_{k-1}^{ i})^\top    \end{bmatrix}^\top$ and  $\mathbf{\bar{z}}_{k}  =\begin{bmatrix} \hat{x}_{0}^\top &  0 & \hdots  & 0 \end{bmatrix}^\top$ where $\mathbf{\hat{z}}^{ i}_{k},\mathbf{\bar{z}}_{k}   \in \mathbf{R}^{(k+1)n} $. In order to compute the state estimate, \eqref{StateEst} has to be explicitly modified to
 \begin{align}
\hat{x}_k =A^k\, \hat{x}^{ \mathrm{j}(k)}_{0}+  \sum_{j=0} ^ {k-1}  A^{k-1-j}\,\left( B\,   u_j + \hat{w}^{ \mathrm{j}(k)}_{j} \right).
\end{align}
 \end{rem}
We impose the following assumptions.
\begin{ass}[Properties of $ \mathcal{S}_k$] \label{ass: S closed}
 The  set $ \mathcal{S}_k$ of constraints is closed and convex with nonempty interior.
\end{ass}
  \begin{ass}[Convexity of $f_k$] \label{ass: f convex}
The sum of stage costs  $f_k$ is continuously differentiable,  convex for all $k> 0$, and achieves its minimum at $\mathbf{z}_k$.
   \end{ass}
     \begin{ass}[Strong smoothness of $f_k$] \label{ass: f strngSmooth}
The sum of stage costs  $f_k$ is strongly smooth with constant $L_f>0 $:
\begin{align}
 f_k(\mathbf{z}_2) \leq  f_k(\mathbf{z}_1)  +\nabla f_k(\mathbf{z}_1)^\top   ( \mathbf{z}_2 -\mathbf{z}_1)  + \frac{L_f}{2} \Vert  \mathbf{z}_1 - \mathbf{z}_2  \Vert^2
\end{align}
for all $\mathbf{z}_1, \mathbf{z}_2 \in \mathbb{R}^{(N+1)n}  $ and $k>0$.
   \end{ass}
 \begin{ass} [Strong convexity and smoothness of $D_\psi$] \label{ass: Bregman}  The function $\psi$ is continuously differentiable, strongly convex  with constant $\sigma>0$ and strongly smooth with constant  $\gamma>0$, which implies the following for the Bregman distance
 \begin{align}
 \frac{\sigma}{2 } \Vert  \mathbf{z}_1 - \mathbf{z}_2  \Vert^2  \leq   D_\psi (\mathbf{z}_1, \mathbf{z}_2 ) \leq  \frac{\gamma}{2} \Vert  \mathbf{z}_1 - \mathbf{z}_2  \Vert^2
 \end{align}
 for all $\mathbf{z}_1, \mathbf{z}_2 \in \mathbb{R}^{(N+1)n}  $.
   \end{ass}
In Assumption \ref{ass: f convex}, we can ensure that $f_k$ achieves its minimum at $\mathbf{z}_k$ by designing the stage costs $r(\cdot)$ and $q(\cdot)$ such that their corresponding minimum is achieved at zero. \rev{Requiring strong smoothness of $f_k$ in Assumption \ref{ass: f strngSmooth} is	rather customary in the analysis of first-order optimization algorithms \cite{mokhtari2016online} and will prove central in the subsequent theoretical studies of the pMHE iteration scheme. Notice that Assumption \ref{ass: Bregman} restricts the  class of employed  Bregman distances to functions which can be quadratically lower and upper bounded. Obviously, this includes the important special case of quadratic distances which are widely used as prior weighting in the MHE literature in order to ensure stability of the estimation error. In addition,we can use any Bregman distance $D_{\psi}$ constructed based on the function  $\psi(\mathbf{z})= \frac{1}{2}\Vert \mathbf{z} \Vert_{P}^2 + B(\mathbf{z})$, where $B:\mathbb{R}^{(N+1)n} \rightarrow \mathbb{R}$ is a convex and strongly smooth function, i.e., a convex function whose gradient is Lipschitz continuous. }

config: arxiv


TITLE: Bessel's equation using method of Frobenius.
QUESTION [0 upvotes]: I am dealing with Bessel's equation of order $0$.
$$x\frac{d^2y}{dx^2}+\frac{dy}{dx}+xy=0$$
We assume that this is a first solution to the Bessel's equation,
$$J_0(x)=\sum_{n=0}^\infty \frac{(-1)^n}{(n!)^2}({\frac{x}{2}})^{2n}$$
Writing out a few terms
$$J_0(x)=1-\frac{x^2}{4}+\frac{x^4}{64}-\frac{x^6}{2304}+...$$
We want to seek another linearly independent solution to the differential equation,
Now using method of reduction of order we found that,
$$y_2(x)=J_0(x)\int \frac{e^{-\int\frac{dx}{x}}}{[J_0(x)]^2}dx$$
$$y_2(x)=J_0(x)\int \frac{dx}{x[J_0(x)]^2}$$
$$[J_0(x)]^2=1-\frac{x^2}{2}+\frac{3x^4}{32}-\frac{5x^6}{576}+...$$
$$\frac{1}{[J_0(x)]^2}=1+\frac{x^2}{2}+\frac{5x^4}{32}+\frac{23x^6}{576}+...$$
I want to know how to get the reciprocal?

REPLY [1 votes]: Other than long division, I prefer undermined coefficient:
Let $a_0, a_1, a_2, ....$ be given, we wish to find $b_0, b_1, b_2, ...$ such that $$(a_0+a_1x+a_2x^2+a_3x^3+...)(b_0+b_1x+b_2x^2+b_3x^3+...) = 1$$
Such $b_i$'s can always be sought given that $a_0 \neq 0$.
Comparing the constant term: $a_0b_0 = 1$, since $a_0 \neq 0$, we can find $b_0$
Comparing the coefficient of $x$: $a_0b_1+b_0a_1 = 0$, since we already found $b_0$ and $a_0, a_1$ is known from the start, we can find $b_1$ from this equation.
Comparing the coefficient of $x^2$: $a_0b_2+b_1a_1+b_0a_2= 0$, since we already found $b_0, b_1$ and $a_0, a_1, a_2$ is known from the start, we can find $b_2$ from this equation.
Continue this process, you can find all $b_i$'s, they might not have a nice general formula, but they can always be found.


TITLE: Run time/Efficiency of finding Least Common Multiple
QUESTION [1 upvotes]: The algorithm is:
  $$\mathrm{lcm}(x,y)=\frac{xy}{\gcd(x,y)}$$
  And we can  use the Euclidean algorithm for finding $\gcd$.

How is the complexity for above method $O(n^3)$, if $x,y$ can at maximum be $n$?

REPLY [1 votes]: The solution stated [$O(n^3)$] is wrong. Euclid's algorithm for finding $\text{gdc}(p,q):p>q$ converges
in at most $1+ \frac{\ln p}{\ln \phi}$ steps, where $\phi$ is the golden ratio $\frac{1+\sqrt{5}}{2}$.
You can see this as follows:  Label the numbers encountered $p_k = p, p_{k-1} = q, p_{k-2} \ldots p_0 = 0$.  Say, when you are at least one step from completion, the larger number is $p_n$ and the smaller is $p_{n-1}$. Then the step taken for $\text{gdc}(p_{n+1},p_n)$ was
$$
p_{n+1} = k_n p_n + p_{n-1}$$
with $k_n \geq 1$; thus
$$p_{n+1} \geq 1 \cdot p_n$$
Now what happened for $p_{n+2}$?
$$
p_{n+2} = k_{n+1} p_{n+1} + p_n = (1 + k_{n+1}k_n) p_n + p_{n-1} \geq 2 p_n$$
And for $p_{n+3}$:
$$
p_{n+3} = k_{n+2} p_{n+2} + p_{n+1} \geq 2\cdot p_n + 1 \cdot p_n = 3 p_n$$
Then $$p_{n+4} \geq (3+2)\cdot p_n$$ and so forth.
So the smallest possible number for $p$ in a $k$-step algorithm grows like the FIbonacci number  $F_k$, which grows like $\phi^k$.
Since multiplication (or division) is itself an $O( \log n)$ operation, the algorithmic complexity of Euclid's algorithm is no greater than
$$O((\log p)^2)$$
and if all multiplies and adds and divisions are counted as 1 operation, it is
$$ O(\log p)$$ where $p$ is the larger of the two numbers to start with.


TITLE: Regarding the mechanics of a Gauss Cannon
QUESTION [0 upvotes]: In the lab the other day, my friend and I constructed a "simple" gauss cannon consisting of 1-3 metal balls lying side by side on a bend surface and one magnetic ball lying next to one of the other balls. Then we had a final metal ball that was send down towards the remaining balls on the surface.
If we only place the magnetic ball on the surface and push a single ball down the slope towards the magnetic ball it appears that the two balls collide and freeze on the spot. The same happens is we let 1-2 balls lie alongside the magnetic ball and push a ball down towards them. The "system" of balls will slide only a little before coming to rest (We reasoned this very small displacement was due to a higher friction of the non-rolling ball system). Finally if we lay 3 balls and 1 magnetic ball on the surface and pushed the last ball down towards them we experienced the Gauss Cannon effect, where the final ball in the row was send away with high velocity.
How do you physically describe the three cases above? Why do the single magnetic ball just "drain" all the kinetic energy (and where does it go?)? Why will there be no repulsion of the outert magnetic ball if we use 1-2 balls alongside the magnetic ball on the surface? And why WILL there be a repulsion if we increase the number of balls to 3 (alongside the magnetic ball)?
Thanks!

REPLY [0 votes]: As the trigger ball is moving towards the magnetic ball, at a close enough distance the magnetic ball starts moving towards the trigger ball, these motions nearly counteract each other and most of the momentum is converted into friction, sound and heat as the combined pair move back slightly making it seem like they have not changed position. If you did this on a friction-less surface you would probably get some left over combined momentum. (If you had a very high speed trigger ball this would not be the case, or a very weak magnetic ball, or a high friction or non-frictional surface).
With two balls, there is more momentum left over because the magnetic ball is not free to accelerate towards the trigger ball, since it is now dragging additional mass and additional frictional forces. But the magnetic force is strong enough to prevent the attached dragged ball firing off. Again, use a weaker magnet or a stronger trigger force and you will see it detach and fire off.
With additional drag balls, there could be a number of affects happening to do with the weaker magnetic attachment to the magnetic ball due to distance, the greater drag forces meaning the magnetic ball can hardly move at all, and the entire system will act much more like a  non magnetic series of balls, but with the additional trigger force of the momentum plus the magnetic attraction of the virtually fixed magnetic ball. If you tried this with a stronger magnet ball, you would need more drag balls before they could fire off. The sideways movement is much increased because of conservation of momentum, until the final drag ball has enough momentum transferred to it to escape the magnetic pull.
A verbose and probably confusing answer but everything you saw was a consequence, as you rightly thought, of momentum, friction, sound and heat energies. (Plus a negligible loss of energy radiating in the distortion of the magnetic field).


TITLE: How to calculate an expression based on given information
QUESTION [3 upvotes]: How to solve the question:
  If $A=(2+1)(2^2+1)(2^3+1)......(2^{2048}+1)$, what shall be the value of $(A+1)^{1/2048}$.
I have not been able to think of anything in any direction, Tobe honest!

REPLY [0 votes]: First, I think the third term in your expression should be $2^{2^2}+1$ as hkmather802 pointed out. The general term should be $2^{2^n}+1$.
If this is the case, here is a solution.
Write $A$ as $A=(2-1)A$ and use difference square formula $a^2-b^2=(a+b)(a-b)$, you can get
$$A=2^{4096}-1.$$
Thus $$(A+1)^{1/2048}=(2^{4096})^{1/2048}=2^2=4.$$
If it is your case, I have no idea.


TITLE: The distribution of sample proportion for given population proportion and sample size
QUESTION [1 upvotes]: If the population proportion is 0.90 and a sample of size 64 is taken, what is the probability that the sample proportion is more than 0.89? (4dp)

work: $n=64$,  $\hat p=0.89$, so $X=n \hat p =56.96$.
$$ P(\hat p >0.89)=P( X >56.95)=1- P( X <56.95)$$
      and then how to do it?
The answer is $0.6064$
More details of the solutions would be great, thanks

REPLY [0 votes]: Since $np > 10$ we can apply Central Limit Theorem and use the formula $\mathbb{P}\!\left(p < \hat{p}\right)= \mathbb{P}\!\left(Z<\frac{p-\hat{p}}{s}\right)$ where $s = \sqrt{\frac{p(1-p)}{n}}$ and $Z \sim N(0,1)$.
My answer came out to be .6052 (I didn't use a standard normal table).


TITLE: Closed - form expression for the finite sum $\sum _{k=0}^{n-1} (-1)^k \sec \left(\frac{\pi\, k}{n}+\frac{\pi }{2 \ n}\right)$
QUESTION [5 upvotes]: Is there a closed -
 form expression for the finite sum on the secant function :  $$\sum _{k=0}^{n-1} (-1)^k \sec \left(\frac{\pi \, k}{n}+\frac{\pi }{2\,n}\right)$$
as a function of n?
Motivation:
The sum is part of a more elaborated solution of Eric Naslund of the integral:
$$\int_0^{\infty } \text{sech}(z)\,\text{sech}(n\,z) \, dz = \frac{\pi}{2\,
n} \sum _{k=0}^{n-1} (-1)^k \sec \left(\frac{\pi\, k}{n}+\frac{\pi }{2\,n}\right)+\frac{1}{2} \pi  \sec \left(\frac{\pi\, n}{2}\right)$$
which holds for any even number n.
Attempt at a solution:
There are some interesting papers, WEN CHANG CHU, Djurdje Cvijovic, H.M. Srivastava and HONGWEI CHEN, considering the summation of finite secant sums.
Investigations of the first bibliographical reference lead to the closed form expression for the similar finite sum:
$$\sum _{k=0}^n (-1)^k \sec \left(2 \left(\frac{\pi\,k}{n}+y\right)\right)=\frac{2\,n \,\sin \left(\frac{\pi\,n}{4}\right) \,\cos \left(\frac{n\,y}{2}\right)}{\cos
(n\,y)-\cos \left(\frac{\pi\,n}{2}\right)}+\sec (y)$$
with $y = \frac{1}{2\,n}$, which can be further investigated by:
$$\sec (2\,z) = \frac{\sec ^2(z)}{2-\sec ^2(z)}$$
and
$$\sec (\frac{z}{2})=\frac{\sqrt{2}}{\sqrt{\cos (z)+1}} (-1)^{\left\lfloor \frac{\pi +\Re(z)}{2 \pi }\right\rfloor } \left(1-\left((-1)^{\left\lfloor -\frac{\pi +\Re(z)}{2 \pi }\right\rfloor
+\left\lfloor \frac{\pi +\Re(z)}{2 \pi }\right\rfloor }+1\right) \theta (-\Im(z))\right)
$$
where $\Theta$ is the "unitstep" - function.
In case of the last bibliographical reference, the main difference to the sum above is, that [HONGWEI CHEN], deals only with higher powers of a similar sum - but without that "factor 2" - e.g.
$$S_{2 n}(\text{q})\text{:=}\sum _{p = 0\,\text{;}\,p\neq \frac{q}{2}  (\text{q is even})}^{q-1} \sec ^{2\, n}\left(\frac{\pi\,  p}{q}\right)$$
Another attempt at a solution is to write the sum as a "q-series" Dieckmann.
EDIT
A new approach is to split the sum e.g.
for $n=4,8,12,...$ [Claude Leibovici]
$$\sum _{k=0}^{n-1} (-1)^k \sec \left(\frac{\pi  (2\,k+1)}{2\,n}\right)=2 \sum _{l=0}^{\frac{n}{4}-1} (-1)^l \sec \left(\frac{\pi \, (2\,l+1)}{2\,n}\right)-2
\sum _{l=0}^{\frac{n}{4}-1} (-1)^l \csc \left(\frac{\pi\,  (2\,l+1)}{2\,n}\right)$$
The summary of the preliminary work give some evidence that a closed -
 form expression exists:
The finite sum can be simplified to:
$$S_{n}=\sum _{k=0}^{n-1} (-1)^k \sec \left(\frac{\pi\,k}{n}+\frac{\pi }{2\,n}\right)=2 \,\sum _{k=0}^{\frac{n}{2}-1} \sec \left(\frac{2\,\pi\,k}{n}+\frac{\pi}{2\,n}\right)$$
For the proof one has to split the sum in even and odd "k's".
From expressions of the first bibliographical reference and the help of Dieckmann the following identity can be proven:
$$W_{n}=\sum _{k=0}^n \frac{1}{\cos \left(\frac{2\, \pi\,  k}{n}\right)+z}=\frac{ n \,\cot \left(\frac{n}{4}\, \left(2\, \sin^{-1}(z)+\pi \right)\right)}{\sqrt{1-z^2}}+\frac{1}{z+1}$$
From the proof of the main result of [HONGWEI CHEN] one derive the further identity:
$$V_{n}=\sum _{k=0}^n \frac{1}{\cos \left(\frac{\pi \, k}{n}\right)+z}=\frac{z}{z^2-1}-\frac{n \cot \left(n \cos ^{-1}(z)\right)}{\sqrt{1-z^2}}$$
Now we split the finite sum $W_{n}$ for even numbers n:
$$W_{n}=\sum _{k=0}^{\frac{n}{2}} \frac{1}{\cos \left(\frac{2 \,\pi \, k}{n}\right)+z}+\sum _{k=\frac{n}{2}+1}^n \frac{1}{\cos \left(\frac{2\,\pi \,k}{n}\right)+z}$$
We express the first sum of $W_{n}$ by $V_{n}$ and solve for the last sum. This leads to:
$$S_{z,w,n}=2 \sum _{k=0}^{n-1} \frac{1}{z-\cos \left(\frac{\pi \, k}{n}+\frac{\pi}{w\,n}\right)}$$
For $w=1$ we have:
$$S_{z,1,n}=\frac{2\, n \,\left(\cot \left(n \cos ^{-1}(z)\right)+2\, \cot \left(\frac{1}{2} \,n \,\left(2 \,\sin ^{-1}(z)+\pi \right)\right)\right)}{\sqrt{1-z^2}}+\frac{2}{1-z^2}$$
The limit $\lim_{z\to 0}$ and $w=4$ gives the solution. With other words we need a general expression, dependent of $w$, with $S_{z,1,n}$ for $w=1$.
EDIT II
Mathematica can find a solution expressed in closed form using the q-polygamma function:
$$S_{\frac{n}{2}}=\frac{2\,n}{\pi } \left(\psi _{e^{-\frac{i\,\pi}{n}}}\left(\frac{1}{4}-\frac{n}{2}\right)-2\, \psi _{e^{-\frac{i\,\pi }{n}}}\left(\frac{1}{4}+\frac{n}{2}\right)+\psi_{e^{-\frac{i\,\pi }{n}}}\left(\frac{1}{4}+\frac{3\,n}{2}\right)\right)$$
where $\psi _q(z)$ is the q-polygamma function. With the function "FunctionExpand" Mathematica expands the q-polygamma function with the complex argument and one can verify the radicals of [Vepir].
Numerically the values can be optained by the well-known identity for the q-polygamma function:
$$\psi _q(x+1)=\psi _q(x)-\frac{q^x \log (q)}{1-q^x}$$
Using the identity n-times recursively, in the expression $S_{\frac{n}{2}}$, $\psi _q(x)$ for $x=\frac{1}{4}$ vanishes!
Summary
These results are the same!

$$\mathcal{I}\left( n \right)=\int_0^{\infty } \text{sech}(z)\,\text{sech}(n\,z) \, dz$$
$$\mathcal{I}\left( n \right)=\frac{1}{n}\sum _{k=0}^{\infty } (-1)^k \left(\psi \left(\frac{3 n+2k+1}{4 n}\right)-\psi \left(\frac{n+2 k+1}{4 n}\right)\right)$$
$$\mathcal{I}\left( n \right)=\frac{\pi}{2\,n} \sum _{k=0}^{n-1} (-1)^k \sec \left(\frac{\pi\, k}{n}+\frac{\pi }{2\,n}\right)+\frac{1}{2} \pi  \sec \left(\frac{\pi\, n}{2}\right)$$
$$\mathcal{I}\left( n \right)=\frac{\pi} {2 \,n} \left(\sum _{l=0}^{\infty } \frac{\left(E_l\right){}^2 \left(\frac{i\, \pi }{2\, n}\right)^l}{l!}-n \,i^n\right)+\frac{1}{2} \pi  \sec \left(\frac{\pi\, n}{2}\right)$$
$$\mathcal{I}\left( n \right)=\frac{1}{2} \left(\psi _{e^{-\frac{2\, i \,\pi}{n}}}\left(\frac{1-n}{4}\right)-2\, \psi _{e^{-\frac{2\, i\, \pi }{n}}}\left(\frac{1+n}{4}\right)+\psi_ {e^{-\frac{2\, i\, \pi }{n}}}\left(\frac{1}{4} (1+3 \,n)\right)\right)+  \\
+\frac{1}{2} \pi  \sec \left(\frac{\pi\, n}{2}\right)$$
$$\mathcal{I}\left( n \right)=\frac{\pi}{2\,n} \left((n+1)-\sec\left(\frac{\pi }{2 \,n}\right)\left(\sin \left(\frac{\pi }{2\, n}\right)-3\right)+\\
+ 2\, \sum _{m=-\frac{n}{4}}^{\frac{n}{4}} \cot \left(\frac{\pi \, \left(m-\frac{1}{4}\right)}{n}\right)+2 \sum_{m=-\frac{n}{2}}^{\frac{n}{2}} \frac{1}{\cot\left(\frac{\pi \, \left(m-\frac{1}{4}\right)}{n}\right)-1}\right) +\frac{1}{2} \pi  \sec \left(\frac{\pi\, n}{2}\right)$$

"6." follows from "5" and has a nice form for $n=2,6,10,\cdots$. The first term is the approximation of [Claude Leibovici].

REPLY [6 votes]: Define the sequence of numbers for all positive even integer $n$
$$ a_n := \sum _{k=0}^{n-1} (-1)^k \sec \left(\frac{\pi \, k}{n}+\frac{\pi }{2\,n}\right). \tag{1} $$
The sequence has an asymptotic power series expansion in
powers of $\,1/n\,$
$$ a_n \sim -n\,i^n + \sum_{k=0}^\infty \frac{E_k^2}{k!}
\left(\frac{\pi\, i}{2\, n}\right)^k. \tag{2} $$
All terms with odd $\,k\,$ in the summation
are zero since the Euler number $\,E_k=0.\,$ The series is
asymptotic so the partial sums start to converge but
after a certain point they diverge to infinity. However,
the Wikipedia article on divergent series lists several methods of summing
divergent series and one or more of them may be of use here.
Note that Euler numbers are OEIS sequence A122045 with e.g.f. $\text{sech}(x),\,$ but the sequence of its squares $\,E_k^2\,$
is not in OEIS and so it is unlikely for its
e.g.f. to have a simple closed form, but it still may be possible.
The Wikipedia article 1-1+2-6+24-120+... gives hope that this may be the case.
The Wolfram language code I used for exploring $q$-digamma based on the
expression of the OP.
ClearAll[ank, a, ax, qd, f];
ank[n_,k_] := (-1)^k Sec[Pi k/n + Pi/2/n];
a[n_?EvenQ] := a[n] = Sum[ ank[n, k], {k, 0, n-1}];
ax[n_, t_] := -n I^n + Sum[ EulerE[k]^2 (I Pi/2/n)^k/k!, {k, 0, 2*t}];
qd[z_, q_] := QPolyGamma[z, q]; (* q-digamma = psi_q(z) *)
f[n_, q_:0] := Module[{q1 = If[q==0, Exp[2 Pi I/n], q]},
    n/Pi (qd[(1-n)/4, q1] - 2 qd[(1+n)/4, q1] + qd[(1+3n)/4, q1])];

Notice that evaluating the $q$-digamma in f[n] at roots of unity
blows up and Mathematica will leave it unevaluated. You can verify
this by evaluating f[n,Exp[2 Pi I/n]x] where $x$ is close to $1$.
Also, notice that f[n]//FunctionExpand//N does not evaluate to
a numerical value for even integer values of $\,n\ge12.\,$


TITLE: Prove that $ (X, d) $ is a metric space
QUESTION [0 upvotes]: Let $ X $ be the set of $ n$-letters word, that is $ X = \{(x_{1}, x_{2}, \dots, x_{n}) \} $ where $ x_{i} $ is an alphabetical character. Define $ d(x, y) $ between two words $ x = (x_{1}, \; x_{2}, \; \dots, \; x_{n}) $ and $ y = (y_{1}, \; y_{2}, \; \dots, \; y_{n}) $ to be the number of places in which the $ 2 $ words have difference letters. Prove that $ (X, d) $ is a metric space.
I am having trouble proving the triangle inequality $ d(x, y) \le d(x, z) + d(z, y). $ Also, if one says that $ (\mathbb{C}, |.|) $ is a metric space where $ \mathbb{C} $ is the set of complex numbers, what does the symbol $ |.| $ mean? Does it mean the absolute value of the product of $ 2 $ elements in $ \mathbb{C}? $

REPLY [1 votes]: HINT: If $x_k\ne y_k$, then either $x_k=z_k\ne y_k$, $x_k\ne z_k=y_k$, or $x_k\ne z_k\ne y_k\ne x_k$. Each $k$ of the first type also contributes to $d(x,y)$ $d(z,y)$ but not to $d(x,z)$. Each $k$ of the second type also contributes to $d(x,z)$ but not to $d(z,y)$. And each $k$ of the third type contributes to both $d(x,z)$ and $d(z,y)$. If there are $a$ indices $k$ of the first type, $b$ of the second, and $c$ of the third, then $d(x,y)=a+b+c$. Show that $d(x,z)+d(z,y)$ must be at least this big.
One does not correctly say that $\langle\Bbb C,|\cdot|\rangle$ is a metric space: $|\cdot|$ is the absolute value function on $\Bbb C$, so that $|a+bi|=\sqrt{a^2+b^2}$, and this is not a metric. (The dot stands for the missing argument of the function.) What is meant is presumably that the metric is given by $d(x,y)=|x-y|$.


TITLE: Understanding the Leontief inverse
QUESTION [12 upvotes]: What I remember from economics about input/output analysis is that it basically analyses the interdependencies between business sectors and demand. If we use matrices we have $A$ as the input-output matrix, $I$ as an identity matrix and $d$ as final demand. In order to find the final input $x$ we may solve the Leontief Inverse:
$$
x = (I-A)^{-1}\cdot d
$$
So here's my question: Is there a simple rationale behind this inverse? Especially when considering the form:
$$
   (I-A)^{-1} = I+A + A^2 + A^3\ldots
$$
What happens if we change an element $a_{i,j}$ in $A$? How is this transmitted within the system? And is there decent literature about this behaviour around? Thank you very much for your help!

REPLY [0 votes]: $
\def\p{\partial}
\def\LR#1{\left(#1\right)}
\def\grad#1#2{\frac{\p #1}{\p #2}}
\def\B{\LR{I-A}^{-1}}
$The gradient of a matrix with respect to one of its components is given by
$$\eqalign{
\grad{A}{A_{ij}} &= E_{ij} \\
}$$
where the components of the matrix $E_{ij}$ are all zero, except for the $(i,j)$ component which equals one. Applying this to the given expression yields
$$\eqalign{
x &= \B d \\
dx &= -\B\LR{-dA}\B d \\
  &= +\B\;dA\;x \\
\grad{x}{A_{ij}} &= \B E_{ij}\,x \\
}$$
which answers the question about how changes to $A$ will propagate through the solution.


TITLE: Being on the same wavelength
QUESTION [0 upvotes]: The usage of physics terminology outside of technically minded people seems limited. That's why I am curious about the phrase being on the same wavelength which as far as I understand is generally understood (and also exists in at least the German language, that's why I ask here and not at English language stackexchange).

What is the origin of this phrase?
Does it refer originally to interference or resonance or...?
What other physics/maths/engineering terms have made it into everyday English language?

REPLY [1 votes]: I imagine it originate from early radio transmissions, a clue only, I only really know that for two radios to communicate they must be tuned to the same wavelength.


TITLE: Sound Horizon in cosmology
QUESTION [2 upvotes]: I was trying to write the sound horizon in terms of the scale factor, however I don't understand all the steps in the derivation.
I know that I should get:
$$r_{s}=\int_{0}^{a_{d}}\frac{da}{a^{2}H(a)}$$
What I tried
$$c_{s}dt=a(t) dr$$
Where $a(t)$ is the scale factor as the function of time, and $c_{s}$ is the velocity of the sound wave
Integrating the last equation:
$$r_{s}=\int _{0}^{t_{d}}\frac{dt}{a(t)}  $$
If I use the relation $H=\frac{\dot{a}}{a}$, then:
$$\mathrm{d} t= \frac{\mathrm{d} a}{Ha}$$
So
$$r_{s}=\int_{0}^{a_{d}}\frac{da}{a^{2}H(a)}  $$
Question
I don't understand what is the meaning of the equation $c_{s}dt=a(t)dr$, I just write that equation because I found it in a book.
So where does the equation $c_{s}dt=a(t)dr$ come from ?
EDIT
If you have another derivation it will be really helpul if you explain it or provide a link to read about that, I search but I can't find anything clear, most of the books just put the formula and don't explain where it comes from.

REPLY [1 votes]: The equation for the sound horizon is simply the equation for the particle horizon, with the speed of light replaced by the speed of sound, there's nothing more to it. Nevertheless, you have to keep in mind that the speed of sound also changes with time, since the matter density dilutes with a growing scale factor, so you have to treat the speed of sound as a function of the scale factor and integrate over it as well.


TITLE: What would signify hierarchy collapse to first level?
QUESTION [14 upvotes]: We know that
$$\mathsf{NP\subseteq P/Poly \iff coNP\subseteq P/Poly\implies PH=\Sigma_2^P}=\mathsf{\Pi_2^P}$$
$$\mathsf{NP\subseteq P/Log\iff coNP\subseteq P/Log\implies PH=\Sigma_0^P=\Pi_0^P}$$

Is there any circuit result that could imply
  $$\mathsf{PH=\Sigma_1^P=\Pi_1^P}$$ but still $$\mathsf{PH\neq\Sigma_0^P=\Pi_0^P}$$ is a possibility?
Is there a possible similar collapse result from non-circuit containment?

Conjecture:

Such result does not exist.

REPLY [1 votes]: It is perhaps reasonable to think that circuits that people would come up with would come along with easily verifiable proofs of their correctness. (This was indirectly inspired by Dietrich & Wilson's notion of "groups of black box type", and is in the spirit of Hartmanis's "provable complexity.") Towards this end, we consider:

Definition: "Certified $\mathsf{P/poly}$" or "$\mathsf{Cert}$-$\mathsf{P/poly}$" consists of those languages $L$ such that $L$ is in $\mathsf{P/poly}$ and there is a poly-bounded certification of this fact. More precisely, $L \in \mathsf{Cert}\text{-}\mathsf{P/poly}$ if there exists a poly-time $V$, and for all $n$, there exists $C_n, \pi_n$ with $\max\{|C_n|,|\pi_n|\} \leq poly(n)$ such that

$V$ is a Cook-Reckhow proof system for the language $\{C : C \text{ correctly computes } L \text{ at length } \ell=\text{# inputs to C}\}$, that is (a) If $C(x) = L(x)$ for all $x \in \Sigma^\ell$, where $\ell$ is the number of inputs to $C$, then there exists a $\pi$ such that $V(C,\pi)=1$ and (b) If there is $x \in \Sigma^\ell$ such that $C(x) \neq L(x)$, then there is no $\pi$ such that $V(C,\pi)=1$.

For all $n$, $C_n$ has $n$ inputs and $V(C_n,\pi_n)=1$.

Then $\mathsf{Cert}\text{-}\mathsf{P/poly}$ contains $\mathsf{NPSV}_t$-uniform $\mathsf{P/poly}$, so it is probably not just $\mathsf{P}$. And we have the desired statement:

Proposition: $\mathsf{NP} \subseteq \mathsf{Cert}\text{-}\mathsf{P/poly} \Longleftrightarrow \mathsf{coNP} \subseteq \mathsf{Cert}\text{-}\mathsf{P/poly} \Longrightarrow \mathsf{PH} = \mathsf{\Sigma_1 P} = \mathsf{\Pi_1 P}$.

Proof: First we show that $\mathsf{Cert}\text{-}\mathsf{P/poly} \subseteq \mathsf{NP}$, giving the final "$\Longrightarrow$" in the statement. Suppose $L \in \mathsf{Cert}\text{-}\mathsf{P/poly}$ with verifier $V$ and $V$-verified circuit family $\{(C_n,\pi_n)\}_{n=1,2,3,...}$. The following is a nondeterministic poly-time algorithm for $L$: on input $x$ of length $n$, guess $C_n,\pi_n$, and run $V(C_n,\pi_n)$; if it accepts, then output $C_n(x)$.
Next, we show that Certified $\mathsf{P/poly}$ is closed under complement, giving the first "$\Longleftrightarrow$" in the statement. Suppose $L \in \mathsf{Cert}\text{-}\mathsf{P/poly}$, with verifier $V$ as in the above definition. Since $L \in \mathsf{NP}$ by the preceding paragraph, there is some $c$ such that $L \in \mathsf{NTIME}(n^c) \subseteq \mathsf{DTIME}(2^{n^c})$. Let $V'(C',\pi)$ compute as follows: if $C'$ has a negation gate as its output gate, then write $C' = \neg C$, and define $V'(C',\pi) = V(C,\pi)$. Otherwise, $V'(C',\pi)$ checks whether $|\pi|=2^{\ell + \ell^c}$ (where $\ell$ is the number of inputs to $C'$); if not, then $V'$ rejects, and if so, then $V'$ simply enumerates all strings $y$ of length $\ell$, and checks whether $C'(y)=L(y)$, using the $2^{\ell^c}$ deterministic algorithm for $L$, which takes time $poly(|\pi|)$. (This latter yoga was needed to make sure that $V'$ satisfies property 1 in the definition.) If $\{(C_n,\pi_n)\}$ is a certified family of circuits for $L$ with verifier $V$, then $\{(\neg C_n, \pi_n)\}$ is a certified family of circuits for $L^c$ with verifier $V'$. QED


TITLE: What is the minimum value of $X= (a+2b +3c+...)$, given $X - ( a+b+c+...) \ge N$, where all variables $\ge 0$
QUESTION [2 upvotes]: Given $X= (a+2b +3c+...)$, i.e this pattern sum of a set of $i$ variables.
And $Y = ( a+b+c+...)$, i.e the sum of the same set of $i$ variables,
given the  constraint
 $X - Y\ge N$, where $N$ is a positive number,
Find the minimum value of $ X$. All variables are greater or equal to zero.
I am tempted to say:
$X = N +Y$ , so when $Y = 0$ then the
Minimum value of $X$ is $ N$.
 But if Y is zero then all of $a,b,c...$ will all be zero and so  $X -Y$ will no longer be greater or equal to $N$.
Is there an intuitive way to find the minimum value of X, or at least express it as a  linear sum of $a,b,c...?$
Thanks in advance!

REPLY [2 votes]: Given $X=a+2b+3c+\cdots+i\,z$ ($i$ terms) to minimise and $b+2c+\cdots + (i-1)\,z\geqslant N$, it is immediate that this is an L.P. So the minimum is at one of the corners bounded by the hyper plane $b+2c+\cdots +(i-1)\,z=N$ and the axes - where except one all other variables are $0$.  Suppose the $k$th variable, say $\alpha$, is non-zero, then we have
$$(k-1)\alpha =N \implies X = k\,\alpha=\frac{k}{k-1}N$$
As this is decreasing in $k$, we must have the last variable non-zero, to get a minimum of $X_{min}=\frac{i}{i-1}N$.


TITLE: Rewrite the following differential equation in Sturm-Liouville form
QUESTION [1 upvotes]: Rewrite the following differential equation in Sturm-Liouville form
$x^2 y''(x)+ 3xy' (x)=-\lambda y(x)$, $x>0$.

REPLY [9 votes]: What you need to do is write the equation as
$$
\frac{d}{d x}\left\{p(x) \frac{d y}{d x}\right\} + \big(q(x) + \lambda r(x)\big)y = 0
$$
In order to do that, multiply the ODE by an integrating factor $\mu(x) > 0$,
$$
x^2 \mu y'' + 3 x \mu y' + \lambda \mu y = 0
$$
The first term can be written as
$$
\frac{d}{dx} \left\{ x^2 \mu \frac{d y}{d x}\right\} - \frac{d y}{d x} \frac{d}{d x}\left(x^2 \mu\right)
$$
and then the ODE becomes
$$
\left(x^2 \mu y'\right)' + \left[3 x \mu - \left(x^2 \mu\right)'\right]y' + \lambda \mu y = 0 \tag{1}
$$
If
$$
3x\mu - (x^2 \mu)' = 0 \tag{2}
$$
then the ODE $(1)$ is of the Sturm-Liouville form. Clearly, the solution for $(2)$ is
$$
\mu (x) = x
$$
which means that, if we multiply the original equation by $x$, then
$$
x\left(x^2 y'' + 3 x y' + \lambda y\right) = x^3 y'' + 3 x^2 y' + \lambda x y = \color{red}{\left(x^3 y'\right)' + \lambda x y = 0}.
$$


TITLE: Chain rule for gradient on a Riemannian manifold
QUESTION [0 upvotes]: I have that $f$ and $h$ are two smooth functions on a Riemannian manifold $(M,g)$ and am told that
\begin{equation}
\int_M\langle\nabla f,\nabla|\nabla h|^4\rangle_g\,dv_g = \int_M 4|\nabla h|^2\,\nabla^2h\big(\nabla f,\nabla h\big)\,dv_g.
\end{equation}
It seems that this follows from some sort of chain rule on $\nabla|\nabla h|^4$, but I don't understand how the inner product $\langle\cdot,\cdot\rangle_g$ in the integral on the left becomes the action of the Hessian $\nabla^2h$ on the vectors $\nabla f$ and $\nabla h$ in the integral on the right. Could someone please explain what is going on here, perhaps in more generality than just this particular example - I can't seem to find anything online corresponding to 'chain rule for gradient on Riemannian manifolds'. Thanks in advance.

REPLY [1 votes]: I think the main confusion here is in the various ways the symbol $\nabla$ is being used: it's simultaneously the differential, gradient and covariant derivative. Inner products can appear/disappear when we swap differentials for gradients. This usage is very standard in Riemannian geometry (and the different interpretations of any expression turn out to be equal thanks to metric-compatibility), but for the purposes of learning it's helpful to start with different notations. Thus I would instead write this equation as $$\def\g{\operatorname{grad}}\def\n{\nabla}\def\ip#1#2{\left\langle #1, #2 \right\rangle} \ip{\g f}{\g |d h|^4}  = 4 |d h|^2 \,\operatorname{Hess} h(\g f, \g h).\tag 1$$
Here the one-form $dh$ is the usual differential of a function, the vector $\g h$ is the gradient defined by $\ip{\g h}X = dh(X)=D_X h$  and $\operatorname{Hess}h(X,Y)=(\n \n h)(X,Y) = \ip{\n_X \g h}{Y}$ is the Hessian.
To show this identity, first note that by definition of the gradient we have $$\ip{\g f}{ \g |dh|^4}=d(|dh|^4)(\g f) = D_{\g f}(|dh|^4).\tag 2$$
Applying the chain rule to $|dh|^4 = (|dh|^2)^2$ yields $$d(|dh|^4)=2|dh|^2 d\ip{\g h}{\g h}$$
since $\left|\g h\right|=|dh|$; so $$D_X(|dh|^4)=2|dh|^2D_X\ip{\g h}{\g h}=4|dh|^2\ip{\nabla_X \g h}{\g h}$$ by metric compatibility. Recognizing the Hessian here, we can write this as $$D_X(|dh|^4)=4|dh|^2\operatorname{Hess} h(X,\g h).$$Now just substitute $X = \g f$ and combine with $(2)$ to arrive at $(1).$


TITLE: Is there a trigonometric field which is different enough from real numbers?
QUESTION [4 upvotes]: I found this topic in a book 'Metric Affine Geometry' by Ernst Snapper and Robert J. Troyer.
I call a field $k$ trigonometric iff there is a quadratic form $q$ over $k^2$ such that every two lines through the origin in $k^2$ is isometric with respect to $q$. This condition is sufficient to introduce trigonometric functions over $\mathbf{SO}(k^2,q)$ in a geometric fashion. Hence, a name.
Obviously, $\mathbb{R}$ is trigonometric. I know, that to be trigonometric the field $k$ must be Pythagorean, that is for every finite sequence of values $(\alpha_i)^n_{i=1} \in k^n$ there is a $\gamma \in k$ such that
$$
 \sum^n_{i=1} \alpha_i^2 = \gamma^2,
$$
namely every sum of squares is a square. Secondly it must be a formally real field, which means that $-1$ is not a sum of  squares. Hence, sadly $\mathbb{Q},\mathbb{C},\mathbb{R}(x),\mathbb{Q}_p,\mathbb{F}_p$ are all not trigonometric. Probably some extension of $\mathbb{R}(x)$ which allows square roots of formally positive functions may work. But I still doubt that it can be totally-ordered, and probably there are some clews in differential Galois theory. Maybe $\hat{\mathbb{Q}} \cap \mathbb{R}$, where $\hat{\mathbb{Q}}$ are algebraic numbers will work, or just adjoining enough real algebraic square roots to $\mathbb{Q}$ (call it a Pythagorean closure $\overline{\mathbb{Q}}$). At least it is Pythagorean and formally real. But I don't think it is interesting enough.
But I'm very a curious about finding an interesting example of trigonometric field different from $\mathbb{R}$. Trigonometric field $k$ different from $\mathbb{R}$ may mean formally that $k$ is not between $\overline{\mathbb{Q}}$ and $\mathbb{R}$.  I would be very grateful if you could suggest one.
If the result are negative, this would mean that class of all trigonometric fields has certain lower and upper bounds.

REPLY [4 votes]: A field $K$ is trigonometric iff the sum of 2 squares is a square and $-1$ is not a square (equivalently, the set of nonzero squares is stable under addition), in which case the standard scalar product on $K^2$ satisfies the required condition.
Indeed, suppose that $K$ is trigonometric, so there is a nonzero quadratic form $q$ on $K^2$ such that $\mathrm{O}(q)$ is transitive on $\mathbf{P}^1(K)$ (if $q=0$ is allowed the condition is void! if nonzero, the kernel is invariant by the isometry group, so has to be reduced to $\{0\}$, i.e. $q$ is nondegenerate). Up tp rescale $q$ and change basis, we can suppose that $q(x,y)=x^2+ty^2$ for some $t\in K$. Transitivity of $\mathrm{O}(q)$ implies that $q(x,y)$ is nonzero for all nonzero $(x,y)$, and that $q(x,y)/q(x',y')$ is a square for all nonzero $(x,y)$ and $(x',y')$. Applying this to $(1,0)$ and $(0,1)$ already implies that $t$ is a square, and hence after again changing the basis, we can suppose that $t=1$.
Since $q(x,y)/q(1,0)$ is a square for all $x,y$, we obtain that $x^2+y^2$ is a square for all $x,y$. If $-1$ were a square, say $i^2=-1$, the element $(1,i)$ would have $q(1,i)=0$, contradiction.
Conversely (the converse is already in the comments), suppose that the conditions are satisfied, and fix the standard scalar product. Consider $(a,b)\neq (0,0)$. Since $a^2+b^2$ is a square, we can rescale it to assume $a^2+b^2=1$, and then it is in the orbit of $(1,0)$, using the rotation matrix $\begin{pmatrix} a&-b\\b&a\end{pmatrix}$.
(Note that the proof also implies that if a 2-dimensional quadratic form $q$ has $\mathrm{O}(q)$ transitive on $\mathbf{P}^1(K)$, then $q$ is equivalent to a scalar multiple of the usual scalar product.)

(Added) Examples:

real-closed fields;
more generally, fields for which $x\le y$ $\Leftrightarrow$ y-x is a square defines a total order. The smallest subfield of $\mathbf{R}$ among those stable under taking square roots of positive elements has this property, yet isn't real-closed;
there are more examples, namely it can happen that there are elements $y$ such that neither $y$ nor $-y$ is a square. This is for instance the case for the ring $\mathbf{R}(\!(t)\!)$. Indeed, in this field, the nonzero squares are the elements of the form $t^{2n}P$ where $P\in\mathbf{R}[\![t]\!]$ has $P(0)>0$ and $n\in\mathbf{Z}$. In this field, none of $\pm t$ is a square.


TITLE: Learning roadmap for Complex Geometry
QUESTION [3 upvotes]: I am still an undergraduate and I have taken courses like complex analysis and differential geometry. Also, I learnt myself manifold theory. (the book by Loring Tu).
Currently, I am quite interested in complex geometry, where I guess it is the intersection between complex analysis and geometry. But what is the roadmap for me to reach that research field? What particular mathematics is required? Do I need to learn PDE?

REPLY [0 votes]: I'd suggest starting with something like smooth manifolds by John Lee together with some good text on elementary complex analysis, such as the classical book by Ahlfors. I'd then learn a little about sheaves from, e.g., Gunning and Rossi's classic book -- Analytic functions of several complex variables. Then I'd start working through Huybrechts' Complex Geometry, Principles of Algebraic Geometry by Griffiths--Harris, and for additional details Voisin's book on Hodge Theory and Complex Algebraic Geometry.