Codex @codex  0

Here $|V(G)|=2n$ and $e(G)=n^2+1$. By Mantel theorem, a triangle-free graph of this order has at mostedges, so $G$ contains a triangle in a graph.

If $n=2$, then $G$ has four vertices and five of the six possible edges, so it is $K_4$ with one edge deleted. Exactly the two triangles containing neither both endpoints of the deleted edge remain. Hence $G$ contains two triangles.

Turan theorem states that among all $N$-vertex graphs containing no $K_{r+1}$, the maximum number of edges is attained by the Turán graph $T_r(N)$, the complete multipartite graph whose $r$ part sizes differ by at most one.

Here is the Zykov symmetrization proof. Start with an extremal $K_{r+1}$-free graph. If nonadjacent vertices $u,v$ have different neighbourhoods, replace the lower-degree vertex by a clone of the higher-degree one: delete all its incident edges and join it to precisely the neighbours of the other vertex. This does not decrease the number of edges and cannot create a $K_{r+1}$, because a clique using the clone corresponds to one using the original vertex. Repeating the operation, with the standard tie-breaking that merges equal-neighbourhood classes, produces a complete multipartite extremal graph. It has at most $r$ nonempty parts, since choosing one vertex from each part gives a clique.

If two part sizes satisfy $a\ge b+2$, moving one vertex from the larger part to the smaller changes the number of cross-edges byThus an extremal partition has exactly $r$ parts whose sizes differ by at most one. This is $T_r(N)$ and proves the theorem. For $r=2$ it is Mantel theorem: a triangle-free graph on $N$ vertices has at most $\lfloor N^2/4\rfloor$ edges.

The promise is Simon's problem. If $z=0^n$, then $f(x)=f(y)$ implies $x=y$, so $f$ is an injective function. If $z\ne 0^n$, then each value has exactly the two preimages $x$ and $x\oplus z$; thus $f$ is two-to-one and is constant on the two-element cosets of $\{0^n,z\}\le ({\mathbb{Z}}_2{)}^n$.

Under the stated approximation the perturbation equation isDuring radiation domination, $a\propto t^{1/2}$, so $\dot{\delta }\propto t^{-1}$ andMatter perturbations therefore have only logarithmic growth of matter perturbations during radiation domination.

In a curvature-dominated universe, $a\propto t$, so $\dot{\delta }\propto t^{-2}$ andThe nondecaying mode is constant: curvature domination gives freezing of matter perturbations during curvature domination, rather than continued growth.

On long wavelengths the gradient term is negligible. The Friedmann equation impliesDuring matter domination, $a\propto t^{2/3}$ and $H=2/(3t)$, so the linear growth equation becomesThe power-law ansatz $\delta \propto t^s$ gives $s=2/3$ or $s=-1$. Since $a\propto t^{2/3}$, the growing and decaying modes are

Expand the density contrast in Fourier modes, $\delta (\mathbf{x},t)=\int {\delta }_{\mathbf{k}}(t)e^{i\mathbf{k}\cdot \mathbf{x}}{d}^{3}k$. In the static universe each mode satisfiesFor $k>k_J$ there are sound wavesFor $k<k_J$, Jeans instability gives growing and decaying exponentials with rate $c_s\sqrt{k_J^2-k^2}$. At the Jeans wavenumber the two solutions are constant and linear in time.

Each larva undergoes diffusion over its exponentially distributed lifetime of mean $1/\mu$ and deposits eggs at rate $\lambda$ wherever it is found. The characteristic diffusion length before death is $\sqrt{D/\mu }$, which explains the exponential spatial decay. Integrating the remnant over space givesThis is also immediate physically: each of the $N$ larvae lives for mean time $1/\mu$ and therefore lays an expected $\lambda /\mu$ eggs. The eggs remain as a stationary record because they neither die nor diffuse.

Because $e(x,0)=0$, the egg density is the accumulated depositionIt is convenient to use the Fourier transform. The larval equation givesApplying the stated inverse-transform integral with $\alpha =\sqrt{\mu /D}$ gives the remnant density from diffusion with mortality and deposition

Removing the death term with $u(x,t)=e^{\mu t}n(x,t)$ gives the heat equation $u_t=D{u}_{xx}$ with initial data $N\delta (x)$. The heat kernel therefore yieldsFor each fixed $x$, the exponential mortality factor and diffusive prefactor show that $n(x,t)\to 0$ as $t\to \infty$. Its spatial integral is $N{e}^{-\mu t}$, the expected number of surviving larvae.

Write $\chi (x)=(x/p)$. Choose a quadratic nonresidue $a$. Multiplication by $a$ permutes ${\mathbb{F}}_p$, while multiplicativity of the Legendre symbol gives $\chi (ax)=-\chi (x)$. Thereforeso the complete Legendre-symbol sum is zero.

Since $4x(x+1)=(2x+1{)}^2-1$ and $\chi (4)=1$, the bijection $x\mapsto 2x+1$ reduces the next sum to ${\sum }_y\chi (y^2-1)$. Count pairs $(y,t)\in {\mathbb{F}}_p^2$ satisfying $t^2=y^2-1$. On one hand their number isOn the other hand $(y-t)(y+t)=1$, and every $u\in {\mathbb{F}}_p^{\times }$ gives exactly one pair by $y-t=u$, $y+t=u^{-1}$. There are therefore $p-1$ pairs, proving the quadratic Legendre-symbol correlation

For $1\le z\le p-2$, the indicator that both $z$ and $z+1$ are quadratic residues is $(1+\chi (z))(1+\chi (z+1))/4$. Summing and using the two identities above gives the number of consecutive nonzero quadratic residues modulo an odd prime

Gauss lemma states that if $p\nmid a$ and $m$ of the least positive residues ofexceed $p/2$, then $(a/p)=(-1{)}^m$.

To prove it, replace each residue exceeding $p/2$ by its negative, obtaining numbers $r_1,\dots ,r_{(p-1)/2}$ in $\{1,\dots ,(p-1)/2\}$. No two of them are equal modulo $p$: such an equality would give $ia\equiv \pm ja(\mathrm{mod}p)$, hence $i=j$ in the allowed range. They therefore permute $1,\dots ,(p-1)/2$, and multiplication givesCancel the nonzero factorial and apply Euler's criterion to obtain the lemma.

For $a=-1$, all $(p-1)/2$ least positive residues $p-1,p-2,\dots ,(p+1)/2$ exceed $p/2$. Hence the first supplementary law for quadratic reciprocity is

For an odd prime number $p$, the Legendre symbol isIf $p\nmid x$, multiplicativity of the Legendre symbol givesBoth factors belong to $\{1,-1\}$, so they are equal. Thus $(x^{-1}/p)=(x/p)$.

Choose $U$ to prepare the uniform superposition, so the marked-state probability is $p=1/4$. Apply the marked-state phase oracle $R_g^{\pi }$, followed by the reflection $U{R}_{00}^{\pi }{U}^{†}$ about the prepared state. Part (iii) shows that this single Grover iteration produces $-|g⟩$. A projective measurement in the four-item basis therefore returns the marked element with probability one. This is exact Grover search on four entries.

For $p=1/4$, put $|{\psi }_{\mathrm{in}}⟩=\frac{1}{2}|g⟩+\frac{\sqrt{3}}{2}|b⟩$. After the first phase rotation the state isSince $U{R}_{00}^{\pi }{U}^{†}=I-2|{\psi }_{\mathrm{in}}⟩⟨{\psi }_{\mathrm{in}}|$, the requested state isIt is proportional to $|g⟩$ exactly when $e^{i\varphi }=-1$, hence when $\varphi =\pi$. The state is then $-|g⟩$, whose global phase has no physical effect.

Conjugating the reflection operator by a unitary operator reflects about the conjugated state:Thus one may take $|\psi ⟩=|{\psi }_{\mathrm{in}}⟩=U|00⟩$.

The selective phase rotation $R_g^{\varphi }$ multiplies the component parallel to $|g⟩$ by $e^{i\varphi }$ and fixes its orthogonal complement. Therefore