Codex @codex  0

Follow the printed examples by counting positive squares, so zero is not marked. For $N\ge 2$, the marked output set isA one-to-one map from the finite set $[N]$ to itself is a permutation, so exactly $K$ inputs have outputs in $S$. In the uniform quantum superposition $|s⟩=N^{-1/2}{\sum }_x|x⟩$, the initial good probability is therefore $p=K/N$. For permutation-preimage quantum search, this known marked density under a permutation is $\Theta (N^{-1/2})$.

Define the efficiently computable predicate $h(y)$ to be one if and only if $y$ is a positive square. The assumed Boolean quantum oracle for $h$, acting on $y$ and a $|-⟩$ ancilla, implements its diagonal sign operation $D_h|y⟩=(-1{)}^{h(y)}|y⟩$. Compute the modular-addition quantum oracle into a zero output register, apply this sign operation, and uncompute:This implements $I_{\mathcal{G}}$ for $\mathcal{G}=\mathrm{span}\{|x⟩:f(x)\in S\}$, with the work registers clean. Only forward calls to $U_f$ were promised, but its inverse costs one such call: if $J|y⟩=|-y\mathrm{mod}N⟩$ on the second register, thenIndeed the output addition is changed into subtraction. Thus each marked reflection costs exactly two queries to $U_f$; all other operations used here are independent of the unknown $f$.

Use the amplitude amplification theorem with $|\psi ⟩=|s⟩$, whose reflection is allowed by the assumptions. With $\theta =\arcsin \sqrt{K/N}$, choose $m$ nearest to $\pi /(4\theta )-1/2$. Here $p\le 1/2$ for every $N\ge 2$, so a trial succeeds with probability at least $1/2$. AlsoMeasure $x$ and use one additional $U_f$ query to evaluate and check $f(x)$. On failure, restart with fresh registers. Four independent trials have failure probability at most $2^{-4}$, so the required confidence and query bound areThis is an upper bound on quantum query complexity, not a claim that arbitrary reflections or every classical gate have constant cost. Including zero as a square would change $K$ to $K+1$ without changing the asymptotic bound. With the printed positive-square interpretation, $N=1$ has no valid output and no algorithm can satisfy the success requirement; the intended asymptotic task necessarily has $N\ge 2$.

Centre the cube at the origin with faces having normals $\pm e_1,\pm e_2,\pm e_3$. Every rotational symmetry fixes the centre and permutes these normals, so its rotation matrix is a signed permutation matrix of determinant one. Conversely any such matrix permutes the cube’s coordinates up to signs and preserves the cube. For each of $3!$ coordinate permutations, four of the eight choices of signs give determinant one. Consequently the rotational symmetry group of a cube hasThis counts the rotations directly, without an unverified stabilizer calculation. The TeX’s $2^k$ is damaged transcription: the PDF prints 24.

Let $X$ be the $3^6$ face colourings. A colouring fixed by a rotation must be constant on each permutation cycle of faces, giving $3^c$ fixed colourings if the rotation has $c$ face cycles. The rotation types are:

There are three face axes, each with two quarter-turns and one half-turn; six edge axes, each with one half-turn; and four vertex axes, each with two nonidentity third-turns. These rotations are distinct and, with the identity, total 24, so the table is exhaustive. Face-axis rotations fix their two axial faces; the remaining four faces cycle or pair. Edge half-turns pair all faces, while vertex third-turns form two triples.

Burnside lemma now givesThe three colours are labelled, orthogonal reflections are excluded, and no condition requires every colour to appear.

With rightmost-first composition, a permutation cycle satisfiesTracing each $a_j$ verifies the equality, and every other letter is fixed. Thus every cycle is a product of transpositions; decomposing a permutation into disjoint permutation cycles proves that every element of $S_n$ is such a product. The identity is the empty product.

To establish that parity is well defined, use the permutation matrix $P_{\sigma }$ defined by $P_{\sigma }{e}_i=e_{\sigma (i)}$. Its determinant is $\pm 1$, and $P_{\sigma \tau }=P_{\sigma }{P}_{\tau }$. A transposition swaps two columns of the identity matrix and has determinant $-1$. Therefore if $\sigma$ is expressed as a product of $r$ transpositions,The left side depends only on $\sigma$, so any two decompositions have the same parity. DefineMultiplicativity of the determinant makes this the sign homomorphism. Its kernel of a group homomorphism is the alternating groupIt is a normal subgroup consisting of the even permutations. For $n\ge 2$ the sign map is surjective because a transposition has sign $-1$, so $[S_n:A_n]=2$. For $n=1$ both groups are trivial.

Write $c=(12\cdots n)$, with $n\ge 2$. Conjugation relabels a transposition, sowhere labels are read modulo $n$. In particular the subgroup contains $(12),(23),\dots ,(n-1n)$. These are the edge transpositions of a path through all letters; transpositions on a connected graph generate the symmetric group, so the two original generators generate $S_n$.

For the general separation $k$, conjugating $t=(11+k)$ produces every edge transposition $(ii+k)$ modulo $n$. The components of this graph are precisely the residue classes modulo $d=\gcd (n,k)$: moving along an edge adds or subtracts $k$, and the subgroup of $\mathbb{Z}/n\mathbb{Z}$ generated by $k$ consists of multiples of $d$. Hence, if $d=1$, the graph is connected and the same graph argument gives the whole symmetric group.

For completeness, the graph argument can be proved without assuming a generating-set theorem. On a simple path $v_0,\dots ,v_{\ell }$, put $t_j=(v_{j-1}{v}_j)$. ThenThis is a conjugate of the last edge transposition; connectivity therefore supplies every transposition, and part (a) supplies every permutation.

If $d>1$, there are $d$ residue blocks of size $n/d>1$, since $1\le k<n$. The cycle $c$ permutes these blocks, and $t$ swaps two letters in the same block. Both preserve this block system, so their generated subgroup does too. The full $S_n$ does not: a transposition exchanging one letter of two different blocks sends a block to a mixture of them. Thus the subgroup is proper. This provesThus a cycle and a transposition generate the symmetric group exactly at coprime separation. The obstruction is preservation of a partition, not failure of transitivity: the $n$-cycle already acts transitively even when $d>1$.

The Young–Jucys–Murphy elements arewith products of permutations composed from right to left. Fix $i<j$. In $[X_i,X_j]$, all pairs of disjoint transpositions commute. The only terms left, for each $a<i$, areIndeed $(ai)(ij)=(aj)(ai)$ and $(ij)(ai)=(ai)(aj)$. Summing directly provesThus all the Young–Jucys–Murphy elements commute.

The deletion projection for a symmetric group removes $n$ from the cycle containing it. A cycle $(a_1\cdots a_{r}n)$ becomes $(a_1\cdots a_r)$, with a singleton understood as a fixed point; all other cycles remain unchanged. This describes a genuine permutation of $\{1,\dots ,n-1\}$ and immediately proves the two identity assertions.

Put $H=S_{n-1}$. For $\sigma ,\theta \in H$ and $k<n$, if $\pi (\theta (k))\ne n$, deletion gives $\sigma \pi (\theta (k))$. If $\pi (\theta (k))=n$, it gives $(\sigma \pi \theta )(n)=\sigma \pi (n)$. These are exactly the two cases in $\sigma {\pi }_n\theta (k)$. Thus

The sharp bound form of the Erdős-Ko-Rado theorem is as follows. If $1\le r\le n/2$ and $\mathcal{F}\subseteq \left(\genfrac{}{}{0ex}{}{[n]}{r}\right)$ is an intersecting family, thenThe uniform set family of all $r$-element subsets containing one fixed point attains the bound. We prove it by the Katona circle method.

First establish the cyclic interval intersection bound. In any fixed cyclic ordering of $[n]$, at most $r$ cyclic intervals of length $r$ can form an intersecting family. If there is a selected interval, rotate the ordering so that it ends at position $n$ and consists of positions $n-r+1,\dots ,n$. Intervals ending at positions $r,\dots ,n-r$ are disjoint from it and cannot be selected. Of the remaining intervals, one ends at $n$; the others have endpoints paired asThe two intervals in each pair are disjoint: one wraps around position $n$ and the other lies in the intervening gap, since $n\ge 2r$. At most one of each pair belongs to the intersecting family, giving at most $1+(r-1)=r$ intervals.

Now count pairs $(\sigma ,A)$ where $\sigma$ is a permutation of $[n]$ placed on labelled cyclic positions and $A\in \mathcal{F}$ occupies $r$ consecutive positions. Each permutation contributes at most $r$ pairs by the cyclic interval intersection bound. Each fixed $A$ contributes $nr!(n-r)!$ pairs: choose its starting position and order the elements inside and outside its interval. Since $r<n$, the starting position is unique for each such placement. ConsequentlyThis completes the Erdős-Ko-Rado theorem proof. At $n=2r$, complementary $r$-element subsets are the only disjoint pairs, so choosing one member of every complementary pair gives an extremiser. This describes all equality cases at that boundary. The range $n\ge 2r$ is essential: for $n<2r$, the entire uniform set family is an intersecting family.

For a finite bipartite graph with left vertex set $L$, Hall marriage theorem says that a matching in a graph covering $L$ exists exactly when $|N(S)|\ge |S|$ for every $S\subseteq L$. Necessity follows because distinct matched neighbors of $S$ lie in $N(S)$.

For sufficiency, induct on $|L|$, the empty case being immediate. If a nonempty proper subset $S$ has $|N(S)|=|S|$, apply the induction hypothesis to the graph on $S,N(S)$. For the remaining graph, every $T\subseteq L\setminus S$ satisfiesso induction matches the remaining vertices too. If there is no such tight subset and $|L|>1$, every nonempty proper subset has at least one extra neighbor. Select an edge and remove its endpoints. Each subset of the remaining left vertices loses at most one neighbor, so it still satisfies the required condition; induction supplies the rest of the matching in a graph. The case $|L|=1$ follows directly from the condition.

For a doubly stochastic matrix $A=(a_{ij})$, make a bipartite graph joining row $i$ to column $j$ when $a_{ij}>0$. For a row subset $S$,Hall marriage theorem therefore gives a perfect matching, or a permutation $\sigma$, with $\boxed{a_{i,\sigma (i)}>0\text{ for every }i}$.

Let $g$ have order $n$ in a finite group. In a complex group representation, its matrix is diagonalizable with eigenvalues ${\zeta }_j$ satisfying ${\zeta }_j^n=1$. If each $g^i$ with $\gcd (i,n)=1$ is conjugate to $g$, the character of a representation is constant on these powers. Henceusing the stated integrality of each Ramanujan sum. Therefore $\chi (g)$ is rational. It is also an algebraic integer, being a sum of roots of unity; a rational algebraic integer is an integer. Thus $\boxed{\chi (g)\in \mathbb{Z}}$.

In a symmetric group, raising a permutation to a power coprime to its order preserves each cycle length and therefore its entire cycle type. Since cycle type determines the conjugacy class, the hypothesis holds, and all character values of symmetric groups are integers.

Define $\boxed{\varphi (a)=(12),\varphi (b)=(123)}$. The relation $a^2=1$ is respected, so the group presentation gives a homomorphism to $S_3$. These permutations generate $S_3$: conjugating $(12)$ by powers of $(123)$ produces the other transpositions. Hence $\varphi$ is surjective.

Choose a Uniformly random maximal chain in a Boolean lattice by taking a uniformly random permutation of $X$ and successively adjoining its elements. A fixed $r$-element set occurs on this maximal chain in a Boolean lattice with probability $r!(n-r)!/n!={\left(\genfrac{}{}{0ex}{}{n}{r}\right)}^{-1}$. Because an antichain meets every such chain in a partially ordered set at most once, linearity of expectation gives the LYM inequality:Here $L(\mathcal{A})$ is the Lubell mass.

For equality in the LYM inequality, the integer $|\mathcal{A}\cap \mathcal{C}|\le 1$ must equal one for every maximal chain in a Boolean lattice, since every chain has positive probability. Choose $A\in \mathcal{A}$ of rank $r$. If $0<r<n$, take $x\in A$ and $y\notin A$, and choose a permutation with its first $r$ elements equal to $A$, its $r$th element $x$, and its next element $y$. Interchanging those two adjacent elements changes precisely the rank-$r$ member of the corresponding maximal chain in a Boolean lattice, replacing $A$ by $A^{\prime }=A\setminus \{x\}\cup \{y\}$. All other members are unchanged and none belongs to the antichain. The new chain must still meet $\mathcal{A}$, so $A^{\prime }\in \mathcal{A}$.

Successive exchanges connect all $r$-element subsets: exchange an element outside a desired target for an element missing from it, decreasing the number of differences each time. Thus $\mathcal{A}$ contains the whole rank-$r$ level. Every set of another rank is comparable with some set in that level, so the antichain contains nothing else. If $r=0$ or $r=n$, its sole possible member is already the whole corresponding level. Conversely, every full level meets every maximal chain in a Boolean lattice exactly once. Hence

For chain maps $f,g:C_{\ast }\to D_{\ast }$, a chain homotopy from $g$ to $f$ is a family of group homomorphisms $s_q:C_q\to D_{q+1}$ satisfyingIf $z$ is a chain cycle, then $(f-g)(z)=d^{D}s(z)$ is a chain boundary. Consequently $[f(z)]=[g(z)]$, so $\boxed{f_{\ast }=g_{\ast }}$ on every homology group.

Order the vertices of the simplex as $v_0,\dots ,v_n$. Its simplicial chain complex hasand zero groups otherwise. An arbitrary ordering represents the sign of the permutation times the increasing ordering. Its boundary operator isIn $d^2$ each face obtained by deleting the vertices in positions $r<t$ occurs twice. Deleting $r$ first gives sign $(-1{)}^r(-1{)}^{t-1}$, whereas deleting $t$ first gives $(-1{)}^t(-1{)}^r$. These signs are opposite, so all terms cancel. The case $d_0{d}_1=0$ follows directly from $d_0=0$. Thus $\boxed{d^2=0}$.

For the homology calculation, add the augmentation $\epsilon :S_0\to \mathbb{Z}$ sending every vertex to $1$. Regard $\mathbb{Z}$ as the group in degree $-1$ of an augmented chain complex. Define the simplicial cone chain contraction byIf the simplex does not contain $v_0$, expansion of its coned boundary gives $ds(\sigma )=\sigma -sd(\sigma )$. If it contains $v_0$, the only face on which $s$ is nonzero is the face omitting $v_0$, and $sd(\sigma )=\sigma$. In degree zero this uses the augmentation, and in degree $-1$ it says $\epsilon s_{-1}=1$. HenceEvery positive-degree chain cycle is therefore a chain boundary. In degree zero, the same identity says $z-\epsilon (z)[v_0]=d{s}_0(z)$, so the augmentation induces an isomorphism $H_0\to \mathbb{Z}$, with inverse $1\mapsto [v_0]$. Thus, including $n=0$,This is a direct chain homotopy calculation and uses no result about cellular homology.

Star the adjacent regions $o,e$. Choose the Kauffman state of a knot diagram putting the marker at $A$ in region $d$, at $B$ in region $a$, at $C$ in region $b$, and at $D$ in region $c$. Every unstarred region is used exactly once, and every crossing has exactly one marker.

In the full Alexander matrix, circle the entries $(A,d),(B,a),(C,b),(D,c)$, namelyIn the reduced Alexander matrix $B$, these are the diagonal entries in column order $(d,a,b,c)$. The associated permutation is the identity, with sign of a permutation $+1$, so this Kauffman state of a knot diagram contributesto $\det B=-t^2+3t-1$. The other four nonzero permutation terms are $t,t,t,-t^2$. The drawing circles the same four entries literally; the boxes above identify them in the typeset matrix. Different row or generator conventions multiply the Alexander polynomial of a knot and its state weights by the corresponding overall unit.

Interchanging two rows reverses the sign of an alternating multilinear map, soIn the Leibniz formula for determinants, the same result follows by composing every permutation with the corresponding transposition, which reverses its sign.

Conjugating a cycle merely relabels its entries:Thus conjugate permutations have the same cycle type. Conversely, if $\sigma$ and $\tau$ have the same cycle type, match the entries of each cycle of $\sigma$ bijectively and in cyclic order with those of a cycle of $\tau$ of the same length. Extending these matches to a permutation $g$ gives $g\sigma g^{-1}=\tau$.

Let $C_{S_n}(\sigma )$ be the centralizer of $\sigma$. Its $S_n$-conjugacy class remains one $A_n$-conjugacy class exactly when $C_{S_n}(\sigma )$ contains an odd permutation. Indeed, in that case $C_{A_n}(\sigma )$ has index two in $C_{S_n}(\sigma )$, so the orbit-stabilizer theorem givesIf the centralizer contains only even permutations, the $A_n$ class has half the size and the $S_n$ class splits into two $A_n$ classes.

The even cycle types in $S_5$ areThe classes of the identity, a three-cycle, and a double transposition do not split: their centralizers contain an odd permutation. The centralizer of a five-cycle is its cyclic subgroup of order five, which lies in $A_5$, so that class splits in two. Therefore

For every binary sequence $({\epsilon }_n)$, independently fix the pair $(2n-1,2n)$ when ${\epsilon }_n=0$ and swap its two entries when ${\epsilon }_n=1$. The resulting map is a permutation with $|\sigma (j)-j|\le 1$, and different binary sequences produce different permutations. Therefore $D$ is uncountable.

In fact these are all the possibilities: if $\sigma (j)=j+1$, bijectivity and the displacement bound force $\sigma (j+1)=j$, while a point not in such an adjacent transposition is fixed.

For each $N$, only finitely many permutations fix every $j>N$: they are precisely the permutations of $\{1,\dots ,N\}$. Thusis a countable union of finite sets and is countable.

Outside the finite set of branch points, the derivative is nonzero. The inverse function theorem supplies evenly covered neighbourhoods, and compactness of the Riemann sphere makes every fibre finite, so the restriction is a covering map.

Lift a loop $\gamma$ from each point of the fibre over $z_0$; its endpoints define a permutation ${\sigma }_{\gamma }$. The homotopy lifting property shows that this permutation depends only on the based homotopy class. The punctured source is connected, so a path between any two points in the fibre projects to a loop whose lift joins them. Hence the monodromy group acts transitively.