text:
Sum-of-squares: proofs, beliefs, and algorithms — Boaz Barak and David Steurer

# Limitations of the sum of squares algorithm

In the last lecture we have seen how the sum of squares algorithm can achieve non-trivial performance guarantees for several interesting problems. But it is not all powerful. In this lecture we will see some negative results for the sum of squares algorithm, showing lower bounds on the degree needed to certify certain problems. In many cases, we do not know of any algorithms that do better, but in some cases we do, and we will see examples of both types. In the standard parlance, these negative results are known as integrality gaps, since these are instances in which there is a gap between the value that the pseudo-distribution “pretends” and the true objective value.The name “integrality gap”, as well as the related notion of a “rounding algorithm” arise from the setting of using a linear program as a relaxation of an integer linear program, where the optimal value of the linear programming relaxation is known as the fractional value, and the opitmal value of the integer linear program is known as the integral value.

## The cycle as an integrality gap for Cheeger’s Inequality and Max-Cut

Recall that the discrete Cheeger’s inequality states that every $$d$$-regular graph $$G$$ with adjacency matrix $$A$$ satisfies $$\lambda \geq \Omega(\varphi(G)^2)$$, where $$\lambda$$ is the second smallest eigenvalue of the normalized Laplacian $$L_G = I - \tfrac{1}{d}A$$. It turns out the humble cycle shows that this bound is tight.

Let $$C_n$$ be the cycle on $$n$$ vertices and let $$L_{C_n}$$ be its normalized Laplacian. Then the second smallest eigenvalue of $$L_{C_n}$$ is at most $$O(1/n^2)$$.

The lemma shows that Cheeger’s inequality is tight for the $$C_n$$ because every subset $$S\subseteq V(C_n)$$ with $$1\le \card{S}\le n-1$$ has at least one neighbor outside of $$S$$. Therefore, the expansion of $$C_n$$ is at least $$\varphi(C_n) \geq \Omega(1/n)$$.

Let $$\omega=e^{2\pi {\mathrm{i}}/n}\in {\mathbb C}$$ be the $$n$$-th root of unity. The vector $$v = (\omega^0,\omega^1,\dots,\omega^{n-1})$$ is orthogonal to the all-ones vector $$\Ind$$, $\iprod{v,\Ind} = \sum_{\ell=0}^{n-1} \omega^\ell = \frac {\omega^0 - \omega^n}{1- \omega} = 0$ using the formula for the sum of a geometric progression. At the same time, we can upper bound the quadratic form of $$L_{C_n}$$ at $$v$$, \begin{aligned} \iprod{v,L_{C_n} v} & = \sum_{\ell=0}^{n-1} \abs{\omega^\ell - \omega^{\ell+1}}^2 \\ & = \abs{1-\omega}^2 \cdot n\\ & \le O(1/n^2)\cdot \norm{v}^2\,. \quad \text{} \end{aligned} The last step uses $$|1-\omega|^2= O(1/n^2)$$. It follows that the second smallest eigenvalue of $$L_{C_n}$$ is $$O(1/n^2)$$In fact, it turns out that the second eigenvalue of $$L_{C_n}$$ is exactly $$\iprod{v,L_{C_n} v} / \norm{v}^2$$ and $$v$$ is an eigenvector corresponding to this eigenvalue.

In one of the exercises in the chapter about Max Cut you showed that if a graph $$G$$ satisfies $${\mathrm{maxcut}}(G) \leq 1 -\e$$ then every degree-$$2$$ pseudo-distribution $$\mu$$ satisfies that $$\pE_\mu f_G(x) \leq 1 - \Omega(\e^2)$$. The following lemma shows that this tradeoff is tight for cycles with an odd number of vertices. Concretely, if $$n$$ is odd then $$C_n$$ is not bipartite. Therefore, $${\mathrm{maxcut}}(C_n) \leq 1 - 1/n$$. In contrast, there are degree-2 pseudo-distributions $$\mu$$ such that $$\pE_\mu f_{C_n}(x)\ge 1-O(1/n^2)$$.

Let $$n\in \N$$ be odd. Then, there exists a degree two pseudo-distribution $$\mu$$ such that $$\pE_\mu f_{C_n}(x) \geq 1 - O(1/n^2)$$.

Let $$\omega\in {\mathbb C}$$ be the $$n$$-th complex root of unity as before. Suppose $$n=2k+1$$. Let $$u\in {\mathbb C}^n$$ with $(0,\omega^k, \omega^{2k},\dots,\omega^{(n-1) k})$ Let $$v,w\in \R^n$$ be the real and imaginary part of $$u$$ so that $$u=v+{\mathrm{i}}\cdot w$$. Let $$X$$ be the $$n$$-by-$$n$$ positive-semidefinite matrix, $X = \dyad v + \dyad w\,.$ Since $$X_{ii}=v_i^2 + w_i^2=\abs{u_i}=1$$, the diagonal of $$X$$ is the all-ones vector $$\Ind$$.

We have seen that we can specify a pseudo-distribution $$\mu$$ by specifying its pseudo-expectation operator. Specifically, we will fix the expectation operator such that \begin{aligned} \pE_{\mu(x)} x &= \tfrac12 \Ind\,, \\ \pE_{\mu(x)} \dyad x &= \tfrac 14 \cdot \dyad{\Ind} + \tfrac14 \cdot X\,. \end{aligned}

We leave it as an exercise to the reader to verify that the above is indeed a valid degree two pseudo-expectation.Hint: This holds because the diagonal of the second moment $$\tfrac 14 \cdot \dyad{\Ind} + \tfrac14 \cdot X$$ agrees with mean $$\tfrac12 \Ind$$ and the formal covariance $$\pE \dyad{\Paren{x-\tfrac12 \Ind}}=\tfrac14 \cdot X$$ is positive semidefinite. See exercise below.

It remains to estimate the pseudo-expectation of $$f_G$$ with respect to $$\mu$$, \begin{aligned} \pE_{\mu(x)} f_G(x) & = \tfrac 14 \sum_{\set{i,j}\in E(G)} (v_i - v_j)^2 + (w_i-w_j)^2\\ & = \tfrac 14 \sum_{\set{i,j}\in E(G)} \abs{u_i - u_j}^2\\ & = \tfrac 14 n \cdot \abs{1-\omega^{k}}^2\ge n \cdot \Paren{1-O\Paren{1/n^2}} \\ \end{aligned} In the last step, we use that $\begin{split} \abs{1-\omega^{k}}^2 & = (1-\omega^{-k})(1-\omega^k) =2-\omega^{k}-\omega^{-k}\\ & = 2 + 2 \cos\tfrac\pi n \ge 4-O\Paren{\tfrac 1 {n}}^2\,. \end{split}$

Show that for every vector $$v\in \R^n$$ and every matrix $$M\in \R^{n\times n}$$ with $$\diag(M)=v$$ and $$M-\dyad v\succeq 0$$, there exists a degree-2 pseudo-distribution $$\mu$$ over the hypercube $$\bits^n$$ with $$\pE_{\mu(x)} x=v$$ and $$\pE_{\mu(x)}\dyad x = M$$.

### Eigenvalues of Cayley graphs

The above ad-hoc computations of eigenvalues are actually special cases of a more general theory. Let $$(\Gamma,\cdot)$$ be a group and $$S\subseteq \Gamma$$. The Cayley graph corresponding to $$\Gamma$$ and $$S$$, which we denote as $$G(\Gamma,S)$$, has vertices corresponding to $$\Gamma$$ and edges $$a,b$$ for every $$a,b \in \Gamma$$ such that $$ab^{-1} \in S\cup S^{-1}$$. The $$n$$-cycle is simply the Cayley graph corresponding to the group $$\Z_n$$ (integers in $$\set{0,\ldots,n-1}$$ with addition modulo $$n$$) and the set $$S = \set{1}$$.

It turns out that for every Abelian group $$\Gamma$$ and Cayley graph $$G(\Gamma,S)$$, we can explicitly calculate the eigenvectors and eigenvalues of $$G(\Gamma,S)$$. The following series of exercises works this out, first for cyclic groups and then for every Abelian group:

Let $$n\in\N$$ and $$\omega = e^{2\pi {\mathrm{i}}/n}$$. For every $$\alpha \in\Z_n$$, we define $$\chi^\alpha\in {\mathbb C}^n$$ to be the vector $$\chi^\alpha_j = \omega^{\alpha \cdot j}$$. Prove that if $$S\subseteq \Z_n$$, and $$A$$ is the adjacency matrix of $$G=G(\Z_n,S)$$, then $$A\chi^\alpha = \lambda_\alpha \cdot \chi^\alpha$$ where $$\lambda_\alpha = \sum_{j\in S}\omega^{\alpha \cdot j}$$. (In particular, $$\chi^\alpha$$ is an eigenvector of $$A$$ with eigenvalue $$\alpha$$.)

Adjacency matrices of (potentially weighted) Cayley graphs over the group $$\Z_n$$ are known as circulant matrices.

Let $$\Gamma$$ be an Abelian group of the form $$\Gamma = \Z_{n_1}\times \cdots \times Z_{n_\ell}$$, and let $$\omega_t = e^{2\pi{\mathrm{i}}/n_t}$$. For every $$\alpha=(\alpha_1,\ldots,\alpha_\ell) \in \Gamma$$, we define a vector $$\chi^{\alpha}\in {\mathbb C}^\Gamma$$ (called character) such that for every $$j=(j_1,\ldots,j_\ell)\in \Gamma$$ $\chi^{\alpha}_j = \prod_{t=1}^\ell \omega_t^{\alpha_t\cdot j_t}\,.$ Prove that if $$S\subseteq \Gamma$$ and $$A$$ is the adjacency matrix of $$G(\Gamma,S)$$, then every vector $$\chi^\alpha$$ is an eigenvector of $$A$$ with eigenvalue $$\lambda_\alpha = \sum_{j\in S} \prod_{t=1}^\ell \omega_t^{\alpha_t \cdot j_t}$$ so that $$A\chi^{\alpha} = \lambda_\alpha\cdot \chi^{\alpha}$$. .

One of the most common instantiations of this result in computer science is for the case that $$\Gamma$$ is the Boolean cube $$\bits^\ell$$ with the XOR operation. In this case we can think of $$\Gamma$$ as $$\Z_2^\ell$$, and then, since $$e^{2\pi {\mathrm{i}}/2}=-1$$, we get that the eigenvectors of the adjacency matrix of a graph $$G(\bits^n,S)$$ have the form $$\chi^\alpha\in\R^{\bits^\ell}$$ where $$\chi^\alpha_\beta = -1^{\iprod{\alpha,\beta}}$$ with $$\alpha,\beta\in\bits^n$$. The corresponding eigenvalue is $$\sum_{\beta\in S} -1^{\iprod{\alpha,\beta}}$$.

The map that transforms a vector $$v\in{\mathbb C}^\Gamma$$ from its representation in the standard basis into its representation in the basis of characters of $$\Gamma$$ (which are the eigenvectors of $$G(\Gamma,S)$$) is known as the Fourier transform). For more on this topic, let us point again to the textbook (O’Donnell 2014).

## A sharper integrality gap for Max Cut

The odd cycle shows that, at least for degree $$2$$ pseudo-distributions, our analysis was tight up to a constant factor, but it does not yield the optimal constant. However, there is a more sophisticated example, due to Feige and Schechtman (2002), that yields a tight bound. Recall that the approximation ratio was $$\alpha_{{\mathrm{GW}}} = \min_{0\leq x \leq 1} \tfrac{\arccos(1-2x)}{\pi x} \approx 0.878$$ and was achieved at $$x_{{\mathrm{GW}}} \approx 0.845$$.

For every $$\e>0$$, there exists a graph $$G=(V,E)$$ such that $${\mathrm{maxcut}}(G) \leq \alpha_{{\mathrm{GW}}}\cdot x_{{\mathrm{GW}}}+\e$$ and there is a degree $$2$$ pseudo-distribution $$\mu$$ with $$\pE_\mu f_G(x) \geq x_{{\mathrm{GW}}}$$.

Let’s think of $$\e$$ as some small $$o(1)$$ value that we will fix later. Looking at the analysis of the GW rounding algorithm, we see that to prove the theorem we need to come up with a graph $$G$$ on $$n$$ vertices and a degree $$2$$ pseudo-distribution $$\mu$$ on $$\bits^n$$ such that $${\mathrm{maxcut}}(G) \leq \alpha_{{\mathrm{GW}}}x_{{\mathrm{GW}}}+o(1)$$ but for almost all edges $$\{i,j\}$$ of $$G$$, $$\pE_{\mu} (x_i-x_j)^2 \geq x_{{\mathrm{GW}}} -o(1)$$. By the same calculations we did before, if we assume $$\pE_\mu x_i = 1/2$$, then this corresponds to the normalized covariance of $$x_i$$ and $$x_j$$ satisfying $$\pE_{\mu} (x_i-1/2)(x_j-1/2)\leq (\rho_{{\mathrm{GW}}}+o(1))1/4$$ where $$\rho_{{\mathrm{GW}}} = 1 -2x_{{\mathrm{GW}}}$$ (note that $$\rho_{{\mathrm{GW}}}$$ is roughly $$-0.69$$). Typically, we think of the graph as fixed and then we come up with the pseudo-distribution, but for this proof we will do this the other way around. We will first come up with $$\mu$$ and then define the graph $$G$$ to correspond to those pairs $$\{i,j\}$$ in which $$\pE_\mu x_ix_j$$ is roughly equal to $$\rho_{{\mathrm{GW}}}$$. Moreover, borrowing an idea from the rounding algorithm, we will let $$\mu$$ be an actual distribution, but one over $$\R^n$$ instead of $$\bits^n$$. In fact, $$\mu$$ will correspond to an actual multivariate Gaussian distribution over $$\R^n$$, with $$\E_\mu x_i = 1/2$$ for all $$i$$ (and hence $$\E_\mu (x_i-1/2)^2 = 1/4$$ for all $$i$$). How do we come up with such a distribution? First note that we can make the number of vertices $$n$$ as large as we like as a function of our desired accuracy $$\e$$, and hence we will think of $$n$$ as very large. In fact, we will think of $$n$$ as very very large: so large that it is practically infinite or even continuous! Concretely, we will identify the vertices of the graph $$G$$ with the $$d-1$$ dimensional unit sphere $$\cS^{d-1}$$ in $$\R^d$$ (for some dimension parameter $$d$$ depending on the desired accuracy) - that is the vertex set is the set of all $$v\in\R^d$$ with $$\norm{v}=1$$. (The one dimensional sphere is a circle, the two dimensional sphere is the boundary of a 3 dimensional ball, and so on..)

The set $$E$$ of edges will be the set of pairs of vectors $$(u,v) \in \cS^{d-1}\times\cS^{d-1}$$ such that $$\iprod{u,v} \leq \rho_{{\mathrm{GW}}}+\epsilon$$. We can think of the max cut value of $$G$$ as the maximum over all measurable subsets $$S$$ of $$\cS^{d-1}$$, of the measure of $$E \cap S \times (\cS^{d-1} \setminus S)$$. Ultimately, we will obtain a finite graph by sampling $$n$$ such vectors, but as long as $$n$$ is large enough $$(n\gg 2^d$$ will do) then this finite graph will inherit both the max-cut value, as well as the pseudo-distribution value. However, the heart of the argument happens in the continuous setting, so you can ignore for the moment that final sampling stage.

We now need to come up with a collection of correlated random variables $$\{ X_v \}_{v\in\R^d}$$ such that for every $$v\in\R^d$$, $$\pE X_v = 1/2$$ and every edge $$(u,v)$$, the covariance of $$X_u$$ and $$X_v$$ is at most $$-\rho_{{\mathrm{GW}}}+O(\e)$$. This collection will be very simple: we choose a random standard Gaussian $$g\in\R^d$$ (i.e., $$g\in\R^n$$ is chosen with $$g_i \in N(0,1)$$ independently for all $$i$$), and for every $$v\in\R^d$$, we define $$X_v = 1/2 + \iprod{v,g}/2$$. Note that $$\E X_v = 1/2$$ and that $$\E (X_v-1/2)^2 = \E \iprod{v,g}^2/4 = 1/4$$.Both equations follow from the rotational symmetry of a standard Gaussian, which means that without loss of generality $$v=e_1$$, in which case $$\iprod{g,v}=g_1$$ is simply a one dimensional standard Gaussian.
Now the normalized covariance (subtracting the expectation and dividing by the standard deviation) of $$u$$ and $$v$$ corresponds to $$\E \iprod{u,g}\iprod{v,g}$$ which by standard manipulations is the same as $$\E \Tr(uv^\top gg^\top)$$ (thinking of $$u,v,g$$ as column vectors and hence $$uv^\top$$ and $$gg^\top$$ are $$n\times n$$ matrices. But by linearity of trace and expectation this is the same as $$Tr(uv^\top \E gg^\top)$$ and since for a standard Gaussian $$g$$, $$\E gg^\top = \Id$$, we get that this normalized covariance is equal to $$\Tr(uv^\top)= \iprod{u,v}$$ which equals at most $$\rho_{{\mathrm{GW}}}+\e$$ by our definition of the edge set.

The above shows that we have a degree two pseudo-distribution $$\mu$$ satisfying that with high probability over $$\{u,v\} \in E$$, $$\pE_\mu (X_u-X_v)^2 \geq x_{{\mathrm{GW}}}-\e$$. But we still need to show that the true maximum cut value is at most $$\alpha_{{\mathrm{GW}}}x_{{\mathrm{GW}}} + o(1)$$. Luckily, here we can “stand on the shoulders of giants” and use previously known results. Specifically, by the geometric nature of this graph, intuitively the maximal cuts would be obtained via a gemoetric partition. Indeed, Borell (1975) (and, independently Sudakov and Cirel$$'$$son (1974) ), proved that over the unit sphere, when we define the edge sets in such geometric terms, then the maximum cuts that optimize this will always be spherical caps. That is, the set $$S$$ would be of the form $$\{ v\in \R^d : \iprod{v,a_0} \geq b_0 \}$$ for some $$a_0 \in \R^d$$ and $$b_0 \in \R$$. Specifically, in this case, one can show that the bipartition that would maximize the number of cut edges would be a balanced one (where $$S$$ and $$\cS^{d-1}\setminus S$$ have the same measure) and hence $$b_0=0$$. By the rotational symmetry of the sphere (and appropriately scaling $$b_0$$), we can assume without loss of generality that $$a_0$$ is simply the first standard basis vector $$(1,0,\ldots,0)$$. Now, since a random edge $$(u,v)\in E$$ is chosen by letting $$v$$ be a random vector with correlation roughly $$\rho_{{\mathrm{GW}}}$$ with $$u$$, and since the first coordinate of a random unit vector has (essentially) the Gaussian distribution with mean zero and variance $$1/n$$, computing the value of the cut reduces to computing the probability that two $$\rho_{{\mathrm{GW}}}$$ correlated Gaussians disagree in their sign. This latter quantity is exactly what we computed in the last lecture as $$1-\arccos(\rho_{{\mathrm{GW}}})/\pi = \alpha_{{\mathrm{GW}}}$$.

Based on our construction, we can see that if the final graph has $$n$$ vertices, then there is a unit vector $$v_i$$ associated with each vertex $$i$$, and the pseudo-expectation operator is defined as $$\pE x_ix_j = 1/2+1/2\iprod{v_i,v_j}$$. The resulting matrix is the sum of the psd all-$$1/2$$ matrix plus the Gram matrix (i.e., matrix of dot products) of the vectors $$\{v_1,\ldots,v_m\}$$. It is not hard to verify that such a matrix is psd- see also the exercises below:

Prove that an $$n\times n$$ matrix $$M$$ is a psd matrix of rank $$d$$ if and only if there exist $$v_1,\ldots,v_n \in \R^d$$ such that $$M_{i,j}=\iprod{v_i,v_j}$$.

Suppose that $$M,N$$ are two $$n\times n$$ psd matrices such that $$M_{i,j}=\iprod{v_i,v_j}$$ and $$N_{i,j}=\iprod{u_i,u_j}$$. Show explicitly a tuple of vectors $$(w_1,\ldots,w_n)$$ such that the psd matrix $$L=M+N$$ satisfies $$L_{i,j}=\iprod{w_i,w_j}$$.

## Isoperimetry, extremal questions, and sum of squares

The result of (Borell 1975,Sudakov and Cirel$$'$$son (1974)) we used above is one in a long line of work on isoperimetric inequalities and their many generalizations. The classical isoperimetric problem is to prove that among all shapes in the plane, the circle is the one that minimizes the ratio of its boundary to its volume. This question has been generalized to many other geometric spaces and notions of volume and boundaries. Indeed, it corresponds to the question we have already seen of finding the least expanding set in the graph: if we think of a very fine grid graph that discretizes the plane, then the isoperimetric problem corresponds to proving that the circle is the set of vertices that minimizes the expansion.

Isoperimetric questions themselves are just a special case of more general questions of finding and characterizing extremal objects. The general setting can be thought of as follows. We have:

• Some “universe” $$\cU$$ of possible objects (e.g., all subsets of a graph, all closed curves in the plane, all functions or vectors in some space).
• Some “objective” function $$F:\cU\rightarrow\R$$ (e.g., the ratio of boundary to volume, the sum of violations of some constraints)
• Some “nice” family $$\cS \subseteq \cU$$ (e.g., shifts of circles, spherical caps, codewords)

The type of theorems we might want to prove (in increasing order of difficulty, and, often, usefulness) would be:

• An optimality theorem: If $$S\in\cU$$ is a global minimum of $$F(\cdot)$$ then $$S\in\cS$$. Like in the isoperimetric case, such optimality theorem are often phrased as inequalities of the form $$F(S) \geq \alpha^*$$ for every $$S\in\cU$$, where $$\alpha^*$$ is the (typically easily computable) minimum of $$F(S)$$ among all the “nice” $$S\in\cS$$.
• A stability theorem: If $$S\in\cU$$ is a “near global minimum” (i.e., $$F(S)$$ is close to $$\min_{S'\in\cU} f(S')$$) then $$S$$ is “close” to some “nice” $$S^*\in\cS$$. The notion of “close” here of course needs to be defined and depends on the context.
• An inverse theorem: If $$S\in\cU$$ has “non trivial $$F(\cdot)$$ value” (i.e., $$F(S)$$ is significantly smaller than the expected value of $$F(S')$$ for a random $$S'$$) then $$S$$ is “somewhat correlated” with some “nice” $$S^*\in \cS$$. Again, the notion of “somewhat correlated” is context-dependent. Sometimes inverse theorems come with a “list decoding” variant in which the condition is that the non-trivial value of $$F(S)$$ can be explained by expressing $$S$$ as some combination of a small number of “nice” objects in $$\cS$$ where again what is “small” and what combinations is one allowed to take.

A related question is the notion of structure vs. randomness as discussed by Tao (see for example (Tao 2007b; Tao 2007a; Tao 2008)). Given some object $$S\in\cU$$ and some family of tests/objectives $$\cF$$, we want to decompose $$S$$ into the “structured part” that is some combination of objects from the “nice” family $$\cS$$ and the “random part” which we can think of as some “noise” object $$N$$ such that $$F(N)$$ is close to the expectation of $$F(S)$$ over a random $$S\in\cU$$ for all $$F\in\cF$$.

There are often algorithmic questions associated with such theorems. One such question is the “decoding” task of finding the “nice” $$S^*$$ that is close to an $$S$$ with small $$F(\cdot)$$ value. Another is the task of, given some description of $$\cU$$ and $$F(\cdot)$$, certifying an optimality theorem. Indeed, we will see that a very interesting question is often whether such an inequality has a low degree sum of squares proof. Often, an algorithmic proof of an optimality theorem will imply at least a stability theorem if not stronger results. Indeed such algorithmic proofs often give an explicit process for optimizing $$F$$ that given any starting point $$S$$ ends up in an optimum point. Typically, if the starting point $$S$$ already had a pretty good $$F(\cdot)$$ value then the algorithm would presumably not take too many steps and hence its final output will be “close” to the initial point.

At this point, when we’ve seen only one concrete example, this discussion might feel somewhat abstract, but many important results, including hypercontractivity, the “invariance principle”, Brascamb Lieb inequalities, results on list decoding, the Gowers norm, and others can be thought of as falling into this general framework. We will see several other examples of such results in this course.

## Beyond degree $$2$$

The examples above show that the rounding algorithms of the previous lecture are tight with respect to degree two pseudodistributions. But of course, we can run the sum of squares algorithm for larger degrees. We do pay a price in the running time, but it remains polynomial time for every constant degree, and as long as the degree is significantly smaller than $$n$$ it would still be significantly faster than brute force.

Could it be that using larger, but still small degree, we can beat the guarantees for max cut, graph expansion, or boolean quadratic forms that are achieved respectively by Goemans-Willamson, Cheeger, or Grothendieck? The short answer that we do not know. It is known that if Khot’s Unique Games Conjecture is true (or the closely related Small Set Expansion Hypothesis) then no polynomial (or even $$2^{n^{o(1)}}$$ time) algorithms can beat those guarantees. In particular, for every $$d = n^{o(1)}$$ these conjectures predict that we can obtain instances with the same gaps as we showed in this lecture but with respect not to merely degree $$2$$ but to the value achieved by degree $$d$$ pseudo-distributions. However, even for $$d=O(1)$$ (even $$d=4$$) this is still wide open. What we do know is that the same examples that we saw in this leture do not yield such gaps. Here is one example:

Let $$n$$ be odd and $$C_n$$ be the $$n$$-length cycle. Prove that for every degree $$6$$ pseudo-distribution $$\mu$$ over $$\bits^n$$, $$\pE_\mu f_{C_n} \leq (1-1/n)|E|$$.Hint: Start by showing the square triangle inequality for degree $$6$$ pseudo-distributions. That is prove that for every degree $$6$$ pseudo-distribution $$\mu$$ over $$\bits^n$$ and every $$i,j,k\in [n]$$, $$\pE_\mu (x_i-x_k)^2 \leq \pE_\mu (x_i-x_j)^2+(x_j-x_k)^2$$.

# References

Borell, Christer. 1975. “The Brunn-Minkowski Inequality in Gauss Space.” Invent. Math. 30 (2): 207–16.

Feige, Uriel, and Gideon Schechtman. 2002. “On the Optimality of the Random Hyperplane Rounding Technique for MAX CUT.” Random Struct. Algorithms 20 (3): 403–40.

O’Donnell, Ryan. 2014. Analysis of Boolean Functions. Cambridge University Press, New York. doi:10.1017/CBO9781139814782.

Sudakov, V. N., and B. S. Cirel$$'$$son. 1974. “Extremal Properties of Half-Spaces for Spherically Invariant Measures.” Zap. Naučn. Sem. Leningrad. Otdel. Mat. Inst. Steklov. (LOMI) 41: 14–24, 165.

Tao, Terence. 2007a. “Structure and Randomness in Combinatorics.” In FOCS, 3–15. IEEE Computer Society.

———. 2007b. “The Dichotomy Between Structure and Randomness, Arithmetic Progressions, and the Primes.” In International Congress of Mathematicians. Vol. I, 581–608. Eur. Math. Soc., Zürich. doi:10.4171/022-1/22.

———. 2008. Structure and Randomness. American Mathematical Society, Providence, RI. doi:10.1090/mbk/059.


text:
# Question #3a0d4

Most common experiences with magnets involve ferromagnetism. The name derives from the term "ferrous" which simply refers to the element iron (chemical symbol $F e$). Said again, alloys which contain iron generally respond to magnetic fields by becoming magnetized. In some cases, this magnetization is permanent (or mostly permanent).
Interesting footnote: some other elements and alloys are ferrous but contain no iron. Nickel and Cobalt are ferrous. Chromium Oxide can be ferrous ($C r {O}_{2}$).

format: plain


text:
# Definition

For $C$ a category, a cylinder functor on $C$ is a functor denoted

$(-)\times I : C \to C$

equipped with three natural transformations

$e_0, e_1 : Id_C \to (-)\times I$
$\sigma : (-)\times I \to Id_C$

such that $\sigma e_0 = \sigma e_1 = Id_C$.

# Remarks

• A cylinder functor functorially provides cylinder objects used for talking about homotopy.

• The notation is supposed to be suggestive of a product with an object $I$. While this is the motivating example, the interval functor need not be of that form.

## Cylindrical model structures

Richard Williamson has developed a way to build a model structure from the simple point of departure of a structured interval in a monoidal category - more generally, a structured cylinder and a structured co-cylinder in a category. This is given in his thesis and also in the ArXiv article listed below.

# References

A very brief introduction to cylinder functors is given starting on page 9 of Abstract Homotopy Theory.

A fuller development of their properties is given in

• K. H. Kamps and T. Porter, Abstract Homotopy and Simple Homotopy Theory (GoogleBooks)

Cylinder functors also form one of the key elements in Baues’ approach to algebraic homotopy:

• H. J. Baues: Algebraic Homotopy, Cambridge studies in advanced mathematics 15, Cambridge University Press, (1989).
• H. J. Baues: Combinatorial Homotopy and 4-Dimensional Complexes, de Gruyter Expositions in Mathematics 2, Walter de Gruyter, (1991).
• H. J. Baues: Homotopy Types, in I.M.James, ed., Handbook of Algebraic Topology, 1–72, Elsevier, (1995).

Cylindrical model structures are discussed in

Revised on January 20, 2015 21:02:47 by Tim Porter (2.26.30.233)


text:
# Math Help - to solve the equation

1. ## to solve the equation

Please help to solve the following equation. At the end of the calculation, I dont know how to factorise the equation. Please help me with simple steps
(x+1/x-2 + 3x) - (1/x+1) = 6

With Many Thanks
Alan Paul

2. ## Re: to solve the equation

Originally Posted by alanpaul
Please help to solve the following equation. At the end of the calculation, I dont know how to factorise the equation. Please help me with simple steps
(x+1/x-2 + 3x) - (1/x+1) = 6

With Many Thanks
Alan Paul
$\dfrac{x+1}{x-2}+\dfrac{3x-1}{x+1}=6$

$\dfrac{(x+1)^2+(3x-1)(x-2)}{(x-2)(x+1)}=6$

$\dfrac{x^2+2x+1+3x^2-7x+2}{(x-2)(x+1)}=6$

$\dfrac{4x^2-5x+3}{x^2-x-2}=6$

$4x^2-5x+3=6(x^2-x-2)=6x^2-6x-12$

$2x^2-x-15=0$

$(x-3)(2x+5)=0$

$x=3$ OR $x=-\dfrac 5 2$


text:
# 150 oranges are bought for Rs. 400 and sold at the rate of Rs. 72 per dozen. What is the percentage of profit or loss?

23 views
150 oranges are bought for Rs. 400 and sold at the rate of Rs. 72 per dozen. What is the percentage of profit or loss?
posted Aug 14


text:
### Bond’s Holding Period Return, Duration, and Investment Horizon

Although short-term interest rate risk is a concern to some investors, other investors have a long-term horizon. Day-to-day changes in bond prices cause unrealized capital gains and losses. A long-term investor is concerned mostly with the total return over the investment horizon. The investor considers both coupon reinvestment risk as well as market price risk in case the bond needs to be sold before maturity.

The buy-and-hold investor has a higher total return if interest rates rise and a lower total return if rates fall. When interest rates rise, duration measures the immediate drop in value or price. Then, as time passes, the bond price is “pulled to par.” At some point in the lifetime of the bond, those two effects offset each other, and the gain on reinvested coupons is equal to the loss on the sale of the bond. That point is the Macaulay duration statistic.

## Duration Gap

The duration gap is the difference between the Macaulay duration and the investment horizon. Mathematically:

$$\text{Duration gap = MacDur – Investment quad horizon}$$

• When the investment horizon is greater than the Macaulay duration of a bond, coupon reinvestment risk dominates market price risk. The investor’s risk is to lower interest rates. The duration gap is negative.
• When the investment horizon is equal to the Macaulay duration of a bond, coupon reinvestment risk offsets market price risk. As such, the investor is hedged against interest rate risk, and the duration gap is zero.
• When the investment horizon is less than the Macaulay duration of the bond, market price risk dominates coupon reinvestment risk. The investor’s risk is to higher interest rates, and the duration gap is positive.

## Question

Assume that an investor plans to retire in 10 years. The investor buys a newly issued, 10-year, 8% annual coupon payment bond. Macaulay duration is 8.6 years. What is the duration gap at the time of purchase?

A. -1.400

B. -1.425

C. -1.525

Solution

The correct answer is A.

Duration gap = MacDur – Investment horizon

= 8.6 – 10 = -1.400

Reading 46 LOS 46k:

Describe the relationships among a bond’s holding period return, its duration, and the investment horizon

Isha Shahid
2020-11-21
Literally the best youtube teacher out there. I prefer taking his lectures than my own course lecturer cause he explains with such clarity and simplicity.
Artur Stypułkowski
2020-11-06
Excellent quality, free materials. Great work!
2020-11-03
One of the best FRM material provider. Very helpful chapters explanations on youtube by professor James Forjan.
Rodolfo Blasser
2020-10-15
The content is masters degree-level, very well explained and for sure a valuable resource for every finance professional that aims to have a deep understanding of quantitative methods.
Mirah R
2020-10-15
Great course! Very helpful
Priyanka
2020-09-29
Analyst Prep has actually been my soul guide towards this journey of FRM.I really appreciate the videos ad they are ALIGNED , good speed, and the Professor just keeps everything Super CASUAL. If I Clear my exams Ultimately credit goes to you guys. Keep sharing. God bless.
Sar Dino
2020-09-29
Had a test on actuarial science coming up and was dead on all the concepts (had to start from ground zero). came across the channel as it had small bits of FM chapters consolidated by the professor Stephen paris. this made it easy for me to look at the chapters i was having trouble with (basically everything lol). I love the way he explains the questions, and the visualization! its so helpful for me to see the diagrams and how the formulas move around. he really did a great job explaining, and i understand so much better. 7 weeks worth of lessons condensed into 3 days of binge watching their videos.... Amazing and i am truly baffled as to why the videos have not gained traction as they should have!

Share:

#### Related Posts

##### Measures for Fixed-Rate Bonds and Floating-Rate Notes

Yield Measures for Fixed-rate Bonds Fixed-rate bonds are those that pay the same...

##### Credit Risk – Default Probability and Loss Severity

The credit risk is the risk of loss resulting from a borrower’s (debt...


text:
Lemma 76.6.1. Let $S$ be a scheme. Let $X$ be a decent algebraic space locally of finite type over $S$. Let $\mathcal{F}$ be a finite type, quasi-coherent $\mathcal{O}_ X$-module. Let $s \in S$ such that $\mathcal{F}$ is flat over $S$ at all points of $X_ s$. Let $x' \in \text{Ass}_{X/S}(\mathcal{F})$. If the closure of $\{ x'\}$ in $|X|$ meets $|X_ s|$, then the closure meets $\text{Ass}_{X/S}(\mathcal{F}) \cap |X_ s|$.

Proof. Observe that $|X_ s| \subset |X|$ is the set of points of $|X|$ lying over $s \in S$, see Decent Spaces, Lemma 67.18.6. Let $t \in |X_ s|$ be a specialization of $x'$ in $|X|$. Choose an affine scheme $U$ and a point $u \in U$ and an étale morphism $\varphi : U \to X$ mapping $u$ to $t$. By Decent Spaces, Lemma 67.12.2 we can choose a specialization $u' \leadsto u$ with $u'$ mapping to $x'$. Set $g = f \circ \varphi$. Observe that $s' = g(u') = f(x')$ specializes to $s$. By our definition of $\text{Ass}_{X/S}(\mathcal{F})$ we have $u' \in \text{Ass}_{U/S}(\varphi ^*\mathcal{F})$. By the schemes version of this lemma (More on Flatness, Lemma 38.18.1) we see that there is a specialization $u' \leadsto u$ with $u \in \text{Ass}_{U_ s}(\varphi ^*\mathcal{F}_ s) = \text{Ass}_{U/S}(\varphi ^*\mathcal{F}) \cap U_ s$. Hence $x = \varphi (u) \in \text{Ass}_{X/S}(\mathcal{F})$ lies over $s$ and the lemma is proved. $\square$

In your comment you can use Markdown and LaTeX style mathematics (enclose it like $\pi$). A preview option is available if you wish to see how it works out (just click on the eye in the toolbar).


text:
Why must all equilateral triangles be similar?

Nov 25, 2015

See explanation.

Explanation:

There are 3 ways of recognizing if two triangles are similar. One of them is:

1. If corresponding angles of two triangles are equal, then the
triangles are similar. (aaa)
2. If the ratios of corresponding sides of two triangles are equal, then the triangles are similar. (sss)
3. If the ratios of 2 corresponding sides are equal and the angles
between the sides are equal, then the triangles are similar.(sas)

In equilateral triangles all angles are equal, so the condition of similarity stated above in point 1 (aaa) is met.


text:
## Some inequalities involving perimeter and torsional rigidity

created by prinari on 09 Jul 2020

[BibTeX]

Submitted Paper

Inserted: 9 jul 2020
Last Updated: 9 jul 2020

Year: 2020

ArXiv: 2007.02549 PDF

Abstract:

We consider shape functionals of the form $F_q(\Omega)=P(\Omega)T^q(\Omega)$ on the class of open sets of prescribed Lebesgue measure. Here $q>0$ is fixed, $P(\Omega)$ denotes the perimeter of $\Omega$ and $T(\Omega)$ is the torsional rigidity of $\Omega$. The minimization and maximization of $F_q(\Omega)$ is considered on various classes of admissible domains $\Omega$: in the class $\mathcal{A}_{all}$ of all domains, in the class $\mathcal{A}_{convex}$ of convex domains, and in the class $\mathcal{A}_{thin}$ of thin domains.


text:
Circular Motion of Charges in Magnetic Fields Video Lessons

Concept

# Problem: A proton moves in the magnetic field B? =0.40i^T with a speed of 1.0 x 107m/s in the directions shown in the figure.-In Figure (a), what is the magnetic force F on the proton? Give your answers in component form.F = ???    N-In Figure (b), what is the magnetic force F on the proton? Give your answers in component form.F = ???     N

###### FREE Expert Solution

Magnetic force:

$\overline{)\stackrel{\mathbf{⇀}}{\mathbf{F}}{\mathbf{=}}{\mathbf{q}}\stackrel{\mathbf{⇀}}{\mathbf{v}}\stackrel{\mathbf{⇀}}{\mathbf{B}}{\mathbf{s}}{\mathbf{i}}{\mathbf{n}}{\mathbf{\theta }}}$

(a)

q = 1.6 × 10-19 C

v = 1.0 × 107m/s

B = 0.40 T

θ = 45°

The field is directed in the positive x-direction. The velocity is directed in the positive z-direction making an angle of 45° with the field. Thus, the resultant force will be in the y-direction.

F = (1.6 × 10-19)(1.0 × 107)(0.40) sin 45 = 4.5 × 10-13 N j

83% (108 ratings)
###### Problem Details

A proton moves in the magnetic field B? =0.40i^T with a speed of 1.0 x 107m/s in the directions shown in the figure.

-In Figure (a), what is the magnetic force F on the proton? Give your answers in component form.

F = ???    N

-In Figure (b), what is the magnetic force on the proton? Give your answers in component form.

F = ???     N


text:
Q

# How many litres of milk can a hemispherical bowl of diameter 10.5 cm hold?

Q : 5    How many litres of milk can a hemispherical bowl of diameter $\small 10.5\hspace{1mm}cm$ hold?

Views

The radius of the hemispherical bowl = $r = \frac{10.5}{2}\ cm$

We know, Volume of a hemisphere = $\frac{2}{3}\pi r^3$

The volume of the given hemispherical bowl = $\frac{2}{3}\times\frac{22}{7}\times \left (\frac{10.5}{2} \right )^3$

$= \frac{2}{3\times8}\times22\times1.5\times10.5\times10.5$

$= 303.1875\ cm^3$

The capacity of the hemispherical bowl = $= \frac{303.1875}{1000} \approx 0.303\ litres\ \ \ (approx.)$

Exams
Articles
Questions


text:
# Tag Info

13

To simplify the problem, let us consider normal local volatilities $\sigma \left ( S_t, t \right)$ and implied volatilities $\sigma_i \left ( K, T \right)$ such that the model is: $$dS_t = \sigma \left ( S_t, t \right) dW$$ (no rate, repo, dividends, etc.) and $\sigma_i \left ( K, T \right)$ is the normal volatility input into Bachelier's formula ...

8

Some points below as food for thought: Suppose you possess an implied volatility surface over a continuous strike cross time to expiry domain (how to get there from the discrete market specification is another question). Further assume that you have to price a path-dependent option, e.g. a Barrier or an Asian. If you are using Black-Scholes, what implied ...

4

The following source contains detailed answers to your questions in a research paper from ETH Zürich. van der Weijst, Roel (2017). "Numerical Solutions for the Stochastic Local Volatility Model" http://resolver.tudelft.nl/uuid:029cbbc3-d4d4-4582-8be2-e0979e9f6bc3

3

I worked on a single name Equity Derivatives trading desk. Implied volatility is remarked at least once per day, but that depends also on market movements, volatility movements, volumes, etc. For this reason it is usually marked at the end of the day and re-checked after opening. About intra-day risk management, they mostly use a prior end-of-day ...

2

Note that with $H(\cdot)$ the Heaviside function $$\frac{d}{ds} H(s-K) = \delta(s-K)$$ but $$\frac{d}{dK} H(s-K) = \color{red}{-}\delta(s-K)$$ You can also use the Leibniz integral rule to write that $$\frac{d}{dK} \int_K^\infty \phi_{S_T}(T,s) ds = -\phi(S_T,K)$$

2

As spot goes to infinity, the transition density goes to zero, and hence the result. Underlying assumption being that it goes to zero faster than quadratic($s^2$). Ps: there seems to be a typo in your derivative but does not matter for the purpose here.

2

Let us denote $\mathcal{C}$ the European call prices and consider the map $K\mapsto\mathcal{C}(t,T,S_t,K)$ the market price of calls maturing at $T$. We can obtain a link between the risk-neutral probability distribution of the stock price and current call prices via the Breeden-Litzenberger formula: $$f^S_T(K)=f_{S_T|S_t}(S_T=K)=e^{r(T-t)}\frac{\partial^2\... 1 Reposting comments as an answer: If you are doing Monte Carlo you'd have a new volatility function to use (rather than a constant vol like in black scholes) for each time and stock price from the local volatility model (It's usually written \sigma (S, t)). So you could use this local volatility function during a simulation regardless of the type of payoff.... 1 Just the chain rule; \frac{d}{dK} H \left (S-K\right)=\delta \left (S-K\right) \frac{d}{dK} \left (S-K\right)=-\delta \left (S-K\right)  1 Although a local volatility model$$ dS_t = \sigma(S_t,t) S_t dW_t  is able to fit exactly quoted market prices of vanilla options, the concept of vega in a local volatility model is at best ill-defined, even for vanilla options. However, if you insist on obtaining vega for an option in a pure local volatility model, then you could bump the functional ...

1

In his article, Dupire (1994) developed the local volatility approach under the assumption that options are traded for a continuum of maturities and strikes. In reality, only a finite number of options generating a grid of strikes and maturities is traded. Then the reconstruction of the local volatility function is obtained by interpolation methods. However,...

1

Unfortunately not written in Python, but in R. If you have experience with R this real life example posted on an underground quant blog has step by step what you may be looking for: (Scroll down to conclusion) https://quantipy.wordpress.com/2017/08/21/implementation-of-dupires-formula-for-local-volatilities/ (I do not take credit for this persons work), ...

1

I first want to clarify one statement. You write "the local volatility of the option ...". A local volatility is, unlike an implied volatility, not a property of an option but instead a function of time and the underlying assets price. I.e. an option does not have an implied volatility but the local volatility function describes the dynamics of the ...

1

In equity options a no-arbitrage argument shows that implied volatility has to be continuous along the forward line The "forward line" is the path of forward levels as a function of the maturity T conditional on a certain value of the spot at T=0 or conditional on the terminal value $F_T$ at maturity. The forward line that terminates at $F_T = K$ is the ...

1

The benefit of Dupire formula is that you can find a local volatility function from the market price of vanilla options, then you can use these local volatilities (by constructing a surface) to value exotic options. Also, this single (theoretically) unique volatility function will value all the vanilla options in line with their market prices rather than ...

1

From a cursory look, the FdBlackScholesBarrierEngine seems to do what you want; when the localVol parameter is set to true, it will use the local volatility contained in the passed process. I'd suggest you to check the code, though. As a further note: the GeneralizedBlackScholesProcess class converts the Black volatility to the local one internally (see the ...

Only top voted, non community-wiki answers of a minimum length are eligible


text:
## Introduction

Musca domestica Linnaeus is an economic pest of animal agriculture and public health which grows rapidly in unhygienic environmental conditions. It is not only a source of nuisance but also plays a role in disease transmissions through its rapid expansion and forcing the affected communities to rely on the heavy use of various insecticides1. This practice has been adopted worldwide with the resulting evolution of resistance in M. domestica against a number of insecticides2,3,4,5,6. As a consequence, the affected people shift from the recommended dose to over-dosage of insecticides with the ultimate negative impact on the environment and public health7. Therefore, the search for new insecticides to manage resistant insects and to develop resistance management strategies is of prime importance8. Among these relatively new insecticides, spinosad (derivative of a soil actinomycete Saccharopolyspora spinosa), has been considered safe due to very low toxicity towards mammals and other non-target organisms9,10,11,12. However, different insect pests like Aedes albopictus (Skuse)13, Drosophila melanogaster Meigen14, Plutella xylostella L.15, Helicoverpa armigera (Hübner)16, Tribolium castaneum17 and M. domestica6,18 have developed resistance against spinosad in some parts of the world.

There are some important factors which contribute to an insect pest developing resistance to a particular insecticide. These factors include the performance of biological parameters of a species in the presence of insecticide selection pressure, fitness costs, frequency of resistance allele(s), pest management practices and population dynamics19,20. Among these factors, fitness costs and the performance of biological parameters associated with resistance to a particular insecticide seem to vary considerably among species and insecticides21. The fitness costs i.e., lengthened developmental time, reduced fecundity and survival, have been widely assumed to be linked with mutations that confer insecticide resistance22. Generally speaking, fitness costs can be enhanced under stressful environments like the presence of insecticide selection pressure23. The poor performance of biological parameters and fitness costs due to insecticide resistance contribute to limiting an increase in resistance alleles24. Similarly, in the presence of these factors in a population, the stability of resistance allele(s), and subsequent transmissions to the next generations could be prevented by integrated management practices along with the wise use of insecticides24,25.

Previously, we have reported low levels of resistance to spinosad in M. domestica from Pakistan26. Thereafter, in order to understand the nature of resistance, we have reported on the inheritance and preliminary mechanism of spinosad resistance in M. domestica under laboratory selections27. The resistance was inherited autosomally, incompletely dominant and governed by more than one gene. In addition, absence of metabolic mechanism of resistance was reported in the resistant strain suggesting the possibility of an altered target site mechanism18. However, resistance development to spinosad was unstable and declined rapidly when spinosad selection pressure was lifted, thus forming the basis of a hypothesis that decline in resistance could be associated with fitness costs. There are a number of reported cases where high fitness costs were linked with spinosad resistance development in different insect species28,29,30,31. However, this information is sparse in the case of M. domestica. Studies on fitness costs in resistant populations are important for devising an effective resistance management strategy, and to prevent the misuse of insecticides32. Such studies ultimately help to minimize environmental pollution and negative impacts on public health. Therefore, the purpose of the present study was to determine the effects of spinosad resistance on different fitness/biological parameters of M. domestica. For this purpose, a near isogenic strain of M. domestica resistant to spinosad was established since such an approach is generally regarded asthe best for fitness assessments33.

## Results

The median lethal concentrations (LC50s) for Spin-UNSEL and Spin-SEL strains were 1.93 and 122.56 µg/ml, respectively. The Spin-SEL strain showed 155.14 fold resistance ratio (RR) to spinosad when compared with the Lab-susceptible strain27 (Table 1). In the process of isolating the near isogenic line with spinosad resistance, the RR values in the BCnF1 progeny decreased significantly after backcrossing with the susceptible recurrent parent; however, these values increased in the BCnF2 progeny after self-breeding. The LC50 value increased to 143.86 µg/ml in the BC5F2 progeny, and did not fluctuate in the next progenies (BC5F3, or BC5F4) based on the overlapping 95% CIs, suggesting that the near isogenic line (Spin-R) with spinosad resistance was established (Table 1).

The comparison of various biological parameters of Spin-UNSEL, Spin-SEL and Spin-R strains revealed significant differences (Table 2), that might reflect the presence of fitness costs in M. domestica. For instance, the survival of the Spin-R strain at the larval stage was significantly lower (65 ± 4.86%) compared with the Spin-SEL (71.33 ± 2.07%) and Spin-UNSEL (87.67 ± 1.80%) strains (F = 33.6; df = 2,12; p < 0.01). The larval stage took more time to complete in the Spin-R strain (6.20 ± 0.57days) as compared with the Spin-SEL (5.20 ± 0.12days) and Spin-UNSEL (4.40 ± 0.19days) strains (F = 21.2; df = 2,12; p < 0.05). Relatively heavier pupae were observed in the case of Spin-UNSEL (19.90 ± 0.56 mg) compared with the Spin-SEL (17.54 ± 0.21 mg) and Spin-R (16.08 ± 0.32 mg) strains (F = 29.9; df = 2,12; p < 0.01). The pupae of the Spin-UNSEL strain developed faster (4.80 ± 0.27days) than those of the Spin-SEL (5.70 ± 0.27days) and Spin-R (6.90 ± 0.42days) strains. In short, the total development time (from egg hatching to adult formation) lengthened in case of the Spin-R strain (13.30 ± 0.57days) compared with the Spin-SEL (12.20 ± 0.27days) and Spin-UNSEL (10.20 ± 0.45days) strains (F = 12.35; df = 2,12; p < 0.001).

Besides developmental time, other biological parameters were also significantly different between the studied strains of M. domestica. For example, 82.67% pupae of the Spin-UNSEL strain were successfully eclosed to adults as compared to 75 and 65% in the case of Spin-SEL and Spin-R pupae, respectively (F = 27.8; df = 2,12; p < 0.05). Comparison of the resultant adults revealed a relatively higher number of female M. domestica in the Spin-UNSEL strain (49.98 ± 3.13%) followed by the Spin-R and Spin-SEL strains (F = 4.41; df = 2,12; p < 0.05). Moreover, resultant female M. domestica of the Spin-UNSEL strain produced a higher number of eggs in their lifetime (340.80 ± 11.37) compared with the Spin-SEL and Spin-R strains (F = 545; df = 2,12; p < 0.001), and the proportion of egg hatching also showed the same trend. Regarding survival at the adult stage, the adults of the Spin-UNSEL strain lived significantly longer compared with the Spin-SEL and Spin-R strains (Table 2).

The comparison of fitness parameters including the intrinsic rate of natural increase (rm), biotic potential (bp), mean relative growth rate (MRGR), net reproductive rate (Ro), and relative fitness also revealed significant differences among all the strains. The values of all of the above fitness parameters were significantly higher in the Spin-UNSEL strain than those of the Spin-SEL and Spin-R strains (F = 198; df = 2,12; p < 0.01 for rm, F = 8.97; df = 2,12; p < 0.05 for MRGR, F = 120; df = 2,12; p < 0.001 for bp, and F = 202; df = 2,12; p < 0.001 for Ro, Table 2).

## Discussion

Environmental contamination resulting from the excessive use of pesticides in agriculture and health sectors can exert strong selection pressure on the exposed populations. Resultantly, survival of the fittest phenotypes with the ability to combat contaminations may arise as a consequence of evolution of resistance to the environmental contaminants1. Such directional evolutions in the selected populations are usually expected to have detrimental effects on fitness in the absence of environmental contaminants or selection pressure, thus constrain the evolution of resistance34. For example, worker honey bees reared in a pesticide-contaminated brood were found with lower survivorship, lengthened developmental time and higher brood mortality rates compared with bees reared in relatively uncontaminated brood, leading to the assumption that the bees in the contaminated brood were less fit and unable to evolve resistance against pesticides35.

The present study was based on the effects of spinosad resistance development on biological parameters in M. domestica. In our previous work27, the Spin-SEL strain showed rapid development of resistance to spinosad under laboratory selections, but resistance was unstable when the selected strain was reared without spinosad. Based on the unstable nature of resistance, it was hypothesized that fitness costs were associated with resistance in the selected strain of M. domestica. In the present study a near isogenic Spin-R strain was established to confirm the presence of fitness costs and the results have further strengthened the above hypothesis. The comparison of biological parameters of resistant and susceptible strains is a logical approach to evaluate fitness costs; however, misinterpretation of the fitness data may occur owing to genetic background variations between strains36. Therefore, in the present study, the near isogenic line of M. domestica resistant to spinosad was established. Theoretically speaking, the genetic variations between recurrent parental strain and the near isogenic line would only be in a limited number of genes, including the selected gene of interest37.

In the present work, the Spin-R strain was compared with Spin-SEL and Spin-UNSEL in terms of development from the egg stage to the adult formation, and in the performance of subsequent adults (fecundity, egg hatching, male to female ratio and survival). The results revealed significant differences in the performance of all the studied biological parameters among the studied strains which showed fitness costs associated with spinosad resistance. The Spin-R strain took significantly more time at the larval stage, which did not translate into heavier pupae compared with Spin-SEL and Spin-UNSEL. The Spin-R strain took more time to develop into adults as compared with Spin-SEL and Spin-UNSEL. Moreover, fecundity, egg hatching and survival at adulthood also decreased significantly in the Spin-R strain. Therefore, spinosad resistance in the Spin-R strain of M. domestica probably imposes direct fitness costs thus suggesting a natural compromise in the distribution of resources between biological parameters and resistance development allele(s) of the selected strain38.

Insecticide resistance mechanisms (e.g., target site or metabolic) could be responsible for inducing fitness costs in the Spin-R strain of M. domestica. Previously, it has been reported in different insect species that exon skipping39, point mutations40, or the production of truncated proteins41 might be responsible for spinosad resistance in the nicotinic acetylcholine receptor site and associated fitness costs. Similarly, for metabolic resistance mechanism, if the production of detoxifying enzyme is costly, then resistant individuals would not produce such enzymes in the absence of insecticide selection pressure22. Overexpression of cytochrome P450 genes has been reported in a spinosad resistant strain (791spin)42 and a Danish field strain (791a)43 of M. domestica. However, a high level of spinosad resistance in of M. domestica are not associated with P450 mediated mechanisms18,44. Similarly, resistance to spinosad in our Spin-SEL strain of M. domestica was unchanged upon pretreatment with an enzyme inhibitor PBO which pointed to the likely absence of P450 metabolic resistance mechanism27. However, further studies are needed to confirm the exact mechanism of spinosad resistance in the Spin-SEL strain and associated fitness costs.

The values of fitness parameters like MRGR, bp, rm and Ro of the Spin-SEL strain were also significantly reduced. These parameters indicate the potential of a certain population to increase under given environmental conditions49,50. The reduced rates of all these parameters in the Spin-R strain clearly demonstrate the presence of the fitness costs phenomenon. In this case, fitness costs is advantageous in terms of managing insecticide resistance since the removal of selection pressure will likely cause a decrease in the number of resistance allele(s)29,38, and ultimately reversion of insecticide resistance. This has already been reported in our previous work in which the Spin-SEL strain showed reversion of spinosad resistance when the selection pressure was lifted27.

In conclusion, the data of the present study demonstrate that fitness costs are most probably associated with spinosad resistance in the Spin-R strain of M. domestica. We found significantly reduced rates of adult eclosion, fecundity, egg hatching, survival, and lengthened developmental time in the Spin-R strain. Moreover, the values of different fitness parameters like biotic potential, mean relative growth rate, intrinsic rate of natural increase, and net reproductive rate, were also significantly reduced in the Spin-R strain, which reflect fitness costs most probably linked with spinosad resistance. The presence of fitness costs suggests likely instability of resistance to spinosad in M. domestica which can be reverted by relaxing spinosad selection pressure and rotation with alternate insecticides. The wise use of insecticides will ultimately help to manage resistance in this pest and minimize environmental pollution. Therefore, combined with our previous findings27, spinosad resistance in M. domestica could be managed by rotational use of insecticides. This will help to manage resistant insects effectively and minimize environmental pollution.

## Materials and Methods

### Musca domestica strains

A field strain of M. domestica was collected from Lahore (31° 32′59 N; 74° 20′37 E) and divided into two sub strains. One sub strain was kept unselected and reared up to 10 generations without exposure to any insecticide, and this strain was designated as “Spin-UNSEL”. The other sub strain was cultured under spinosad selection pressure for 10 consecutive generations and resulted in a 155 fold resistance development compared with the laboratory susceptible strain (Lab-susceptible)27. This sub strain was designated as “Spin-SEL”. A near isogenic line (Spin-R) with spinosad resistance was established following the methodology of Horikoshi, et al.36. In short, the Spin-R strain was derived by repeatedly backcrossing Spin-SEL females with Spin-UNSEL males. The offspring of the backcrosses were referred to as the BCnF1 progeny (n = number of backcrosses). The self-bred BCnF1 progeny yielded BCnF2 progeny which was selected with spinosad using the concentration level to cause 70% mortality (i.e., LC70), and then the surviving females were backcrossed to Spin-UNSEL males. The detailed methodology for selection experiment and bioassays has already been reported previously27. The selection bioassays and backcrossing were completed when the LC50 values of the self-bred progenies BCnF2, BCnF3, and BCnF4 had become stable. All the strains were maintained under laboratory conditions as described previously26,51.

### Survival and development of Spin-UNSEL, Spin-SEL and Spin-R strains

Survival and development was checked by following the work of Khan, et al.50 with a few modifications. Briefly, batches of 60 first instar larvae (<12 h old) of Spin-UNSEL, Spin-SEL and Spin-R strains were maintained on larval media under the above laboratory conditions. These batches were replicated five times to study fitness parameters, and the total number of larvae studied per strain was 300. The growth and survival of the tested larvae were checked twice daily. The parameters recorded were: duration of the larval (1st to 3rd instar) and pupal stages, survival at larval and pupal stages, and total developmental time from hatching to adult formation.

### Fecundity, egg hatching and survival at adulthood

To compare the number of eggs laid, egg hatching and survival at the adulthood stage, five pairs of all the strains (<24 h old) each were kept in separate wooden mesh cages (30 × 30 × 30 cm). The cages were provided with adult food, and larval medium for egg laying and immature development. The cages were kept under the same laboratory conditions as stated earlier. The cages were observed twice daily to count the number of eggs laid, eggs hatched and survival of the adults till the mortality of each pair.

### Fitness parameters

In order to calculate the mean relative growth rate (MRGR), 1st instar larvae (n = 50) of all the strains were taken from their respective cages, weighed, and divided into five equal batches. Each batch was reared separately in a 250 ml glass beaker containing 100 g larval medium. After the completion of the larval stage, pupae were removed and weighed to calculate MRGR according to the following formula52,53:

$${\rm{MRGR}}=\frac{[\,\mathrm{ln}\,.({\rm{pupal}}\,{\rm{weight}})-\,\mathrm{ln}\,.({\rm{initial}}\,{\rm{larval}}\,{\rm{weight}})]}{{\rm{Time}}\,{\rm{from}}\,{\rm{the}}\,{\rm{larval}}\,{\rm{stage}}\,{\rm{to}}\,{\rm{the}}\,{\rm{pupal}}\,{\rm{stage}}\,({\rm{T}})}$$
(1)

Net reproductive rate (Ro), intrinsic rate of natural increase (rm) and biotic potential (bp) were calculated as described previously53.

Biotic potential was determined by dividing the log fecundity with total developmental time50,53, and relative fitness (w) was calculated by dividing Ro of Spin-SEL or Spin-R strain with Ro of Spin-UNSEL strain.

To compare each biological parameter of the Spin-SEL, Spin-UNSEL and Spin-R strain, the data were analyzed by the multivariate analysis of variance (MANOVA) and means were compared by Tukey’s HSD test.

### Ethical statement

The study/bioassay protocols used against M. domestica were performed according to the standard guidelines and regulations and approved by the institutional research project evaluation committee.


text:
Lemma 86.9.1. Let $A$ be a Noetherian ring and $I \subset A$ an ideal. Let $J \subset A$ be a nilpotent ideal. Consider a commutative diagram

$\xymatrix{ C \ar[r] & C_0 \ar@{=}[r] & C/JC \\ & B_0 \ar[u] \\ A \ar[r] \ar[uu] & A_0 \ar[u] \ar@{=}[r] & A/J }$

whose vertical arrows are of finite type such that

1. $\mathop{\mathrm{Spec}}(C) \to \mathop{\mathrm{Spec}}(A)$ is étale over $\mathop{\mathrm{Spec}}(A) \setminus V(I)$,

2. $\mathop{\mathrm{Spec}}(B_0) \to \mathop{\mathrm{Spec}}(A_0)$ is étale over $\mathop{\mathrm{Spec}}(A_0) \setminus V(IA_0)$, and

3. $B_0 \to C_0$ is étale and induces an isomorphism $B_0/IB_0 = C_0/IC_0$.

Then we can fill in the diagram above to a commutative diagram

$\xymatrix{ C \ar[r] & C/JC \\ B \ar[u] \ar[r] & B_0 \ar[u] \\ A \ar[r] \ar[u] & A/J \ar[u] }$

with $A \to B$ of finite type, $B/JB = B_0$, $B \to C$ étale, and $\mathop{\mathrm{Spec}}(B) \to \mathop{\mathrm{Spec}}(A)$ étale over $\mathop{\mathrm{Spec}}(A) \setminus V(I)$.

Proof. Set $X = \mathop{\mathrm{Spec}}(A)$, $X_0 = \mathop{\mathrm{Spec}}(A_0)$, $Y_0 = \mathop{\mathrm{Spec}}(B_0)$, $Z = \mathop{\mathrm{Spec}}(C)$, $Z_0 = \mathop{\mathrm{Spec}}(C_0)$. Furthermore, denote $U \subset X$, $U_0 \subset X_0$, $V_0 \subset Y_0$, $W \subset Z$, $W_0 \subset Z_0$ the complement of the vanishing set of $I$. Here is a picture to help visualize the situation:

$\xymatrix{ Z \ar[dd] & Z_0 \ar[l] \ar[d] \\ & Y_0 \ar[d] \\ X & X_0 \ar[l] } \quad \quad \quad \xymatrix{ W \ar[dd] & W_0 \ar[l] \ar[d] \\ & V_0 \ar[d] \\ U & U_0 \ar[l] }$

The conditions in the lemma guarantee that

$\xymatrix{ W_0 \ar[r] \ar[d] & Z_0 \ar[d] \\ V_0 \ar[r] & Y_0 }$

is an elementary distinguished square, see Derived Categories of Spaces, Definition 73.9.1. In addition we know that $W_0 \to U_0$ and $V_0 \to U_0$ are étale. The morphism $X_0 \subset X$ is a finite order thickening as $J$ is assumed nilpotent. By the topological invariance of the étale site we can find a unique étale morphism $V \to X$ of schemes with $V_0 = V \times _ X X_0$ and we can lift the given morphism $W_0 \to V_0$ to a unique morphism $W \to V$ over $X$. See Étale Morphisms, Theorem 41.15.2. Since $W_0 \to V_0$ is separated, the morphism $W \to V$ is separated too, see for example More on Morphisms, Lemma 37.10.3. By Pushouts of Spaces, Lemma 79.9.2 we can construct an elementary distinguished square

$\xymatrix{ W \ar[r] \ar[d] & Z \ar[d] \\ V \ar[r] & Y }$

in the category of algebraic spaces over $X$. Since the base change of an elementary distinguished square is an elementary distinguished square (Derived Categories of Spaces, Lemma 73.9.2) we see that

$\xymatrix{ W_0 \ar[r] \ar[d] & Z_0 \ar[d] \\ V_0 \ar[r] & Y \times _ X X_0 }$

is an elementary distinguished square. It follows that there is a unique isomorphism $Y \times _ X X_0 = Y_0$ compatible with the two squares involving these spaces because elementary distinguished squares are pushouts (Pushouts of Spaces, Lemma 79.9.1). It follows that $Y$ is affine by Limits of Spaces, Proposition 68.15.2. Write $Y = \mathop{\mathrm{Spec}}(B)$. It is clear that $B$ fits into the desired diagram and satisfies all the properties required of it. $\square$

Second proof. This proof uses a little bit of deformation theory to construct $B$. By induction on the smallest $n$ such that $J^ n = 0$ we reduce to the case $J^2 = 0$. Denote by a subscript zero the base change of objects to $A_0 = A/J$. Since $J^2 = 0$ we see that $JC$ is a $C_0$-module.

Consider the canonical map

$\gamma : J \otimes _{A_0} C_0 \longrightarrow JC$

Since $\mathop{\mathrm{Spec}}(C) \to \mathop{\mathrm{Spec}}(A)$ is étale over the complement of $V(I)$ (and hence flat) we see that $\gamma$ is an isomorphism away from $V(IC_0)$, see More on Morphisms, Lemma 37.10.1. In particular, the kernel and cokernel of $\gamma$ are annihilated by a power of $I$ (use that $C_0$ is Noetherian and that the modules in question are finite). Observe that $J \otimes _{A_0} C_0 = (J \otimes _{A_0} B_0) \otimes _{B_0} C_0$. Hence by More on Algebra, Lemma 15.84.16 there exists a unique $B_0$-module homomorphism

$c : J \otimes _{A_0} B_0 \to N$

with $c \otimes \text{id}_{C_0} = \gamma$ and $\mathop{\mathrm{Ker}}(\gamma ) = \mathop{\mathrm{Ker}}(c)$ and $\mathop{\mathrm{Coker}}(\gamma ) = \mathop{\mathrm{Coker}}(c)$. Moreover, $N$ is a finite $B_0$-module, see More on Algebra, Remark 15.84.19.

Choose a presentation $B_0 = A[x_1, \ldots , x_ r]/K$. To construct $B$ we try to find the dotted arrow $m$ fitting into the following pushout diagram

$\xymatrix{ 0 \ar[r] & N \ar@{..>}[r] & B \ar@{..>}[r] & B_0 \ar[r] & 0 \\ 0 \ar[r] & K/K^2 \ar[r] \ar@{..>}[u]_ m & A[x_1, \ldots , x_ r]/K^2 \ar[r] \ar@{..>}[u] & A[x_1, \ldots , x_ r]/K \ar@{=}[u] \ar[r] & 0 \\ & J \otimes _{A_0} B_0 \ar[u] \ar@/^2pc/[uu] |!{[lu];[u]}\hole }$

where the curved arrow is the map $c$ constructed above and the map $J \otimes _{A_0} B_0 \to K/K^2$ is the obvious one.

As $B_0 \to C_0$ is étale we can write $C_0 = B_0[y_1, \ldots , y_ r]/(g_{0, 1}, \ldots , g_{0, r})$ such that the determinant of the partial derivatives of the $g_{0, j}$ is invertible in $C_0$, see Algebra, Lemma 10.142.2. We combine this with the chosen presentation of $B_0$ to get a presentation $C_0 = A[x_1, \ldots , x_ r, y_1, \ldots , y_ s]/L$. Choose a lift $\psi : A[x_ i, y_ j] \to C$ of the map to $C_0$. Then it is the case that $C$ fits into the diagram

$\xymatrix{ 0 \ar[r] & JC \ar[r] & C \ar[r] & C_0 \ar[r] & 0 \\ 0 \ar[r] & L/L^2 \ar[r] \ar[u]_\mu & A[x_ i, y_ j]/L^2 \ar[r] \ar[u] & A[x_ i, y_ j]/L \ar@{=}[u] \ar[r] & 0 \\ & J \otimes _{A_0} C_0 \ar[u] \ar@/^2pc/[uu] |!{[lu];[u]}\hole }$

where the curved arrow is the map $\gamma$ constructed above and the map $J \otimes _{A_0} C_0 \to L/L^2$ is the obvious one. By our choice of presentations and the fact that $C_0$ is a complete intersection over $B_0$ we have

$L/L^2 = K/K^2 \otimes _{B_0} C_0 \oplus \bigoplus C_0 g_ j$

where $g_ j \in L$ is any lift of $g_{0, j}$, see More on Algebra, Lemma 15.33.6.

Consider the three term complex

$K^\bullet : J \otimes _{A_0} B_0 \to K/K^2 \to \bigoplus B_0 \text{d}x_ i$

where the second arrow is the differential in the naive cotangent complex of $B_0$ over $A$ for the given presentation and the last term is placed in degree $0$. Since $\mathop{\mathrm{Spec}}(B_0) \to \mathop{\mathrm{Spec}}(A_0)$ is étale away from $V(I)$ the cohomology modules of this complex are supported on $V(IB_0)$. Namely, for $a \in I$ after inverting $a$ we can apply More on Algebra, Lemma 15.33.6 for the ring maps $A_ a \to A_{0, a} \to B_{0, a}$ and use that $\mathop{N\! L}\nolimits _{A_{0, a}/A_ a} = J_ a$ and $\mathop{N\! L}\nolimits _{B_{0, a}/A_{0, a}} = 0$ (some details omitted). Hence these cohomology groups are annihilated by a power of $I$.

Similarly, consider the three term complex

$L^\bullet : J \otimes _{A_0} C_0 \to L/L^2 \to \bigoplus C_0 \text{d}x_ i \oplus \bigoplus C_0 \text{d}y_ j$

By our direct sum decomposition of $L/L^2$ above and the fact that the determinant of the partial derivatives of the $g_{0, j}$ is invertible in $C_0$ we see that the natural map $K^\bullet \to L^\bullet$ induces a quasi-isomorphism

$K^\bullet \otimes _{B_0} C_0 \longrightarrow L^\bullet$

Applying Dualizing Complexes, Lemma 47.9.8 we find that

86.7.2.1
$$\label{restricted-equation-go-down} \mathop{\mathrm{Hom}}\nolimits _{D(B_0)}(K^\bullet , E) = \mathop{\mathrm{Hom}}\nolimits _{D(C_0)}(L^\bullet , E \otimes _{B_0} C_0)$$

for any object $E \in D(B_0)$.

The maps $\text{id}_{J \otimes _{A_0} C_0}$ and $\mu$ define an element in

$\mathop{\mathrm{Hom}}\nolimits _{D(C_0)}(L^\bullet , (J \otimes _{A_0} C_0 \to JC))$

(the target two term complex is placed in degree $-2$ and $-1$) such that the composition with the map to $J \otimes _{A_0} C_0[2]$ is the element in $\mathop{\mathrm{Hom}}\nolimits _{D(C_0)}(L^\bullet , J \otimes _{A_0} C_0[2])$ corresponding to $\text{id}_{J \otimes _{A_0} C_0}$. Picture

$\xymatrix{ J \otimes _{A_0} C_0 \ar[r] \ar[d]_{\text{id}_{J \otimes _{A_0} C_0}} & L/L^2 \ar[r] \ar[d]^\mu & \bigoplus C_0 \text{d}x_ i \oplus \bigoplus C_0 \text{d}y_ j \\ J \otimes _{A_0} C_0 \ar[r]^-\gamma & JC }$

Applying (86.7.2.1) we obtain a unique element

$\xi \in \mathop{\mathrm{Hom}}\nolimits _{D(B_0)}(K^\bullet , (J \otimes _{A_0} B_0 \to N))$

Its composition with the map to $J \otimes _{A_0} B_0[2]$ is the element in $\mathop{\mathrm{Hom}}\nolimits _{D(C_0)}(K^\bullet , J \otimes _{A_0} B_0[2])$ corresponding to $\text{id}_{J \otimes _{A_0} B_0}$. By Lemma 86.3.4 we can find a map of complexes $K^\bullet \to (J \otimes _{A_0} B_0 \to N)$ representing $\xi$ and equal to $\text{id}_{J \otimes _{A_0} B_0}$ in degree $-2$. Denote $m : K/K^2 \to N$ the degree $-1$ part of this map. Picture

$\xymatrix{ J \otimes _{A_0} B_0 \ar[r] \ar[d]_{\text{id}_{J \otimes _{A_0} B_0}} & K/K^2 \ar[r] \ar[d]^ m & \bigoplus B_0 \text{d}x_ i \\ J \otimes _{A_0} B_0 \ar[r]^-c & N }$

Thus we can use $m$ to create an algebra $B$ by push out as explained above. However, we may still have to change $m$ a bit to make sure that $B$ maps to $C$ in the correct manner.

Denote $m \otimes \text{id}_{C_0} \oplus 0 : L/L^2 \to JC$ the map coming from the direct sum decomposition of $L/L^2$ (see above), using that $N \otimes _{B_0} C_0 = JC$, and using $0$ on the second factor. By our choice of $m$ above the maps of complexes $(\text{id}_{J \otimes _{A_0} C_0}, \mu , 0)$ and $(\text{id}_{J \otimes _{A_0} C_0}, m \otimes \text{id}_{C_0} \oplus 0, 0)$ define the same element of $\mathop{\mathrm{Hom}}\nolimits _{D(C_0)}(L^\bullet , (J \otimes _{A_0} C_0 \to JC))$. By Lemma 86.3.4 there exist maps $h : L^{-1} \to J \otimes _{A_0} C_0$ and $h' : L^0 \to JC$ which define a homotopy between $(\text{id}_{J \otimes _{A_0} C_0}, \mu , 0)$ and $(\text{id}_{J \otimes _{A_0} C_0}, m \otimes \text{id}_{C_0} \oplus 0, 0)$. Picture

$\xymatrix{ J \otimes _{A_0} C_0 \ar[r] \ar[d]_{\text{id}_{J \otimes _{A_0} C_0}} & K/K^2 \otimes _{B_0} C_0 \oplus \bigoplus C_0 g_ j \ar@{..>}[ld]_ h \ar[r] \ar@<-1ex>[d]_\mu \ar[d]^{m \otimes \text{id}_{C_0} \oplus 0} & \bigoplus C_0 \text{d}x_ i \oplus \bigoplus C_0 \text{d}y_ j \ar@{..>}[ld]_{h'}\\ J \otimes _{A_0} C_0 \ar[r]^-\gamma & JC }$

Since $h$ precomposed with $d_ L^{-2}$ is zero it defines an element in $\mathop{\mathrm{Hom}}\nolimits _{D(C_0)}(L^\bullet , J \otimes _{A_0} C_0[1])$ which comes from a unique element $\chi$ of $\mathop{\mathrm{Hom}}\nolimits _{D(B_0)}(K^\bullet , J \otimes _{A_0} B_0[1])$ by (86.7.2.1). Applying Lemma 86.3.4 again we represent $\chi$ by a map $g : K/K^2 \to J \otimes _{A_0} B_0$. Then the base change $g \otimes \text{id}_{C_0}$ and $h$ differ by a homotopy $h'' : L^0 \to J \otimes _{A_0} C$. Hence if we modify $m$ into $m + c \circ g$, then we find that $m \otimes \text{id}_{C_0} \oplus 0$ and $\mu$ just differ by a map $h' : L^0 \to JC$.

Changing our choice of the map $\psi : A[x_ i, y_ j] \to C$ by sending $x_ i$ to $\psi (x_ i) + h'(\text{d}x_ i)$ and sending $y_ j$ to $\psi (y_ j) + h'(\text{d}y_ j)$, we find a commutative diagram

$\xymatrix{ N \ar[r] & JC \\ K/K^2 \ar[r] \ar[u]_ m & L/L^2 \ar[u]_\mu \\ J \otimes _{A_0} B_0 \ar[u] \ar@/^2pc/[uu]^ c \ar[r] & J \otimes _{A_0} C_0 \ar[u] \ar@/_2pc/[uu]_\gamma }$

At this point we can define $B$ as the pushout in the first commutative diagram of the proof. The commutativity of the diagram just displayed, shows that there is an $A$-algebra map $B \to C$ compatible with the given map $N = JB \to JC$. As $N \otimes _{B_0} C_0 = JC$ it follows from More on Morphisms, Lemma 37.10.1 that $B \to C$ is flat. From this it easily follows that it is étale. We omit the proof of the other properties as they are mostly self evident at this point. $\square$

In your comment you can use Markdown and LaTeX style mathematics (enclose it like $\pi$). A preview option is available if you wish to see how it works out (just click on the eye in the toolbar).


text:
# The following diagram shows a triangle ABS, where BC=5,\ \hat{B}=60^{\circ},\

The following diagram shows a triangle ABS, where $$\displaystyle{B}{C}={5},\ \hat{{{B}}}={60}^{{\circ}},\ \hat{{{C}}}={40}^{{\circ}}$$. Calculate AB to the nearest whole number.

• Questions are typically answered in as fast as 30 minutes

### Plainmath recommends

• Get a detailed answer even on the hardest topics.
• Ask an expert for a step-by-step guidance to learn to do it yourself.

Lupe Kirkland
Step 1
The Law of Sines is the relationship between the sides and angles of non-right (oblique) triangles.
Simply, it states that the ratio of the length of a side of a triangle to the sine of the angle opposite that side is the same for all sides and angles in a given triangle.
Step 2
Using hte law of sine in $$\displaystyle\triangle{A}{B}{C}$$
$$\displaystyle\Rightarrow{\frac{{{A}{C}}}{{{\sin{{B}}}}}}={\frac{{{A}{B}}}{{{\sin{{C}}}}}}$$
$$\displaystyle\Rightarrow{\frac{{{5}}}{{{\sin{{60}}}^{{\circ}}}}}={\frac{{{x}}}{{{\sin{{40}}}^{{\circ}}}}}$$
$$\displaystyle\Rightarrow{{\sin{{40}}}^{{\circ}}=}{0.643}$$ and $$\displaystyle{{\sin{{60}}}^{{\circ}}=}{0.866}$$
$$\displaystyle\Rightarrow{x}={\frac{{{5}\times{\sin{{40}}}^{{\circ}}}}{{{\sin{{60}}}^{{\circ}}}}}={\frac{{{5}\times{0.643}}}{{{0.866}}}}={3.71}{c}{m}$$
$$\displaystyle\Rightarrow{x}={4}{c}{m}$$ (to the nearest whole number)


text:
# numpy.correlate#

numpy.correlate(a, v, mode='valid')[source]#

Cross-correlation of two 1-dimensional sequences.

This function computes the correlation as generally defined in signal processing texts:

$c_k = \sum_n a_{n+k} \cdot \overline{v_n}$

with a and v sequences being zero-padded where necessary and $$\overline x$$ denoting complex conjugation.

Parameters
a, varray_like

Input sequences.

mode{‘valid’, ‘same’, ‘full’}, optional

Refer to the convolve docstring. Note that the default is ‘valid’, unlike convolve, which uses ‘full’.

old_behaviorbool

old_behavior was removed in NumPy 1.10. If you need the old behavior, use multiarray.correlate.

Returns
outndarray

Discrete cross-correlation of a and v.

See also

convolve

Discrete, linear convolution of two one-dimensional sequences.

multiarray.correlate

Old, no conjugate, version of correlate.

scipy.signal.correlate

uses FFT which has superior performance on large arrays.

Notes

The definition of correlation above is not unique and sometimes correlation may be defined differently. Another common definition is:

$c'_k = \sum_n a_{n} \cdot \overline{v_{n+k}}$

which is related to $$c_k$$ by $$c'_k = c_{-k}$$.

numpy.correlate may perform slowly in large arrays (i.e. n = 1e5) because it does not use the FFT to compute the convolution; in that case, scipy.signal.correlate might be preferable.

Examples

>>> np.correlate([1, 2, 3], [0, 1, 0.5])
array([3.5])
>>> np.correlate([1, 2, 3], [0, 1, 0.5], "same")
array([2. ,  3.5,  3. ])
>>> np.correlate([1, 2, 3], [0, 1, 0.5], "full")
array([0.5,  2. ,  3.5,  3. ,  0. ])

Using complex sequences:

>>> np.correlate([1+1j, 2, 3-1j], [0, 1, 0.5j], 'full')
array([ 0.5-0.5j,  1.0+0.j ,  1.5-1.5j,  3.0-1.j ,  0.0+0.j ])

Note that you get the time reversed, complex conjugated result ($$\overline{c_{-k}}$$) when the two input sequences a and v change places:

>>> np.correlate([0, 1, 0.5j], [1+1j, 2, 3-1j], 'full')
array([ 0.0+0.j ,  3.0+1.j ,  1.5+1.5j,  1.0+0.j ,  0.5+0.5j])


text:
# No. of solutions of two equations?

What is the number of distinct primes $p$ such that $$\binom{\frac{p+1}2}2\ =\ 5\cdot r\cdot q$$ where $5<r<q<p$ are primes. (See the answer given by avz2611 in the following). Similarly, if $$\binom{\frac{p+1}2}2\ =2\cdot 3\cdot\ 5\cdot r\cdot q$$ what's the number of distinct primes $p$?

• Please clarify. Do you mean that $r,q$ are fixed, and we're looking for $p$? Something else...? – Amitai Yuval Sep 27 '14 at 8:45
• I am sorry that the question what I put is not clear. Here, $r,q$ are not fixed. I just want to find all the primes $p$ such that $\binom{\frac{p+1}2}2$ has three prime divisors $5,r,q$ with $5<r<q<p$. Please see the following. – Liu Sep 28 '14 at 1:21

$(p+1)(p-1)=40.r.q$ now (p+1) or (p-1) one of them have to be a multiple of 3 so you should have a multiple of 3 on the right hand side but 40 is not divisible by 3 and as both $r$ & $q$ are greater 3 and are primes even they are not divisible by 3 so no solutions possible
• Can I ask you a question more? If $(p+1)(p-1)=2^4.3.5.r.q$, then what about $p$? Do three many distinct primes $p$ exist? Thank you. – Liu Sep 28 '14 at 2:26


text:
# Geographic Data Science - Lecture VIII

## Today

• The point of points
• Point patterns
• Visualization of point patterns

## Points like polygons

Points can represent "fixed" entities

In this case, points are qualitatively similar to polygons/lines

The goal here is, taking location fixed, to model other aspects of the data

## Points like polygons

Examples:

• Cities (in most cases)
• Buildings
• Polygons represented as their centroid
• ...

## When points are not polygons

Point data are not only a different geometry than polygons or lines...

... Points can also represent a fundamentally different way to approach spatial analysis

## Points unlike polygons

• Rather than exhausting the entire space, points can be events subject to occur anywhere
• The location of the event is part of what we are trying to understand/model
• The interest focuses on characterizing the pattern that the points follow over space

[Source]

[Source]

## Point patterns

Distribution of points over a portion of space

Assumption is a point can happen anywhere on that space, but only happens in specific locations

• Unmarked: locations only
• Marked: values attached to each point

Point Pattern Analysis

Describe, characterize, and explain point patterns, focusing on their generating process

• Visual exploration
• Clustering properties and clusters
• Statistical modeling of the underlying processes

## Visualization of PPs

Two routes (today):

• Aggregate  ↔  "Histogram"
• Smooth  ↔  KDE

## Aggregation

Points meet polygons

Use polygon boundaries and count points per area

[Insert your skills for choropleth mapping here!!!]

But, the polygons need to "make sense" (their delineation needs to relate to the point generating process)

## Hex-binning

If no polygon boundary seems like a good candidate for aggregation...

...draw a hexagonal (or squared) tesselation!!!

Hexagons...

• Are regular
• Exhaust the space (Unlike circles)
• Have many sides (minimize boundary problems)

## But...

(Arbitrary) aggregation may induce MAUP (see Lecture 4)

+

Points usually represent events that affect only part of the population and hence are best considered as rates (see Lecture 4)

## Kernel Density Estimation

Estimate the (continuous) observed distribution of a variable

• Probability of finding an observation at a given point
• "Continuous histogram"
• Solves (much of) the MAUP problem, but not the underlying population issue

[Source]

## Bivariate (spatial) KDE

Probability of finding observations at a given point in space

• Bivariate version: distribution of pairs of values
• In space: values are coordinates (XY), locations
• Continuous "version" of a choropleth

## Finding clusters of PPs

Cluster is a hard to define term

Concentrations/agglomerations of points over space, significantly more so than in the rest of the space considered

Huge literature spanning spatial analysis, statistics and computer science. Today, we'll look at...

Density

Based

Spatial

Clustering of

Applications with

Noise