Codex @codex  0

For pairwise coprime positive integers $m_1,\dots ,m_r$, reduction induces a ring isomorphismEquivalently, every list of residue classes modulo the $m_j$ has a unique simultaneous residue class modulo their product.

In a finite group, a cyclic subgroup of order $m$ has exactly $\phi (m)$ generators, where $\phi$ is the Euler totient function. Each element generates exactly one cyclic subgroup, so dividing the number of elements of order $m$ by $\phi (m)$ counts these subgroups. Include the identity subgroup using $m=1$ and $\phi (1)=1$. In a symmetric group, element counts come from cycle type and order of a group element is the least common multiple of cycle lengths.

Permutation cycles with disjoint supports commute. The order of their product is the least common multiple of their lengths.

For any group $G$, evaluation at a chosen generator of a group $x$ of $C_n$ gives a bijection between group homomorphisms $C_n\to G$ and elements satisfying $g^n=1$. A group homomorphism must send $x^j$ to $g^j$. Conversely, this formula is well-defined because exponents differing by a multiple of $n$ give equal powers, and it respects multiplication. The displayed correspondence is a bijection of sets; it is not claimed to be a group isomorphism for a nonabelian target. In a symmetric group, the order of a group element is the least common multiple of its disjoint cycle lengths, making this correspondence easy to enumerate.

The final property concerns a pointwise periodic self-map. Such a map is a bijection: each point has a predecessor in its finite cycle, giving surjectivity; if $f(x)=f(y)$, choose a common multiple $N$ of periods of $x,y$ and apply $f^{N-1}$ to get $x=y$. Its finite cycles are therefore disjoint.

If $X$ is finite, choose the least common multiple of the finitely many cycle lengths. This positive integer $N$ gives $f^N={\mathrm{id}}_X$. The empty set satisfies the property with $N=1$.

Conversely, in the usual set theory with choice, every infinite $X$ contains a countably infinite set. Divide such a subset into disjoint finite blocks $B_j$ of sizes $j+1$, $j\ge 1$, make $f$ a cyclic permutation on each block, and fix every other point. Every point returns to itself, but an identity iterate would have to be divisible by every block length $j+1$. No positive integer has that property: take a block longer than that integer. Thus the uniform period criterion for pointwise periodic maps givesThe axiom of choice assumption is stated here because extracting a countably infinite subset of an arbitrary infinite set is not an unrestricted theorem in set theory without choice.

For a prime $p$, the divisor sum defining the real weight is $\varphi (0)-\varphi (\log p/\log X)$. If $p>X^{1/3}$, the second term vanishes and the first is one. Thus $F(p)=1$, while $F(n)\ge 0$ for every integer because $\varphi$ is real and the sum is squared.

Put $h(x)=e^x\varphi (x)$. With the Fourier transform convention in the question, Fourier inversion givesThe function $h$ is smooth and has compact support. Using integration by parts $k$ times, with zero endpoint terms, provesChoose an integer $k\ge A$ to obtain $|\psi (t)|{\ll }_A|t{|}^{-A}$ for $|t|\ge 1$. In particular every polynomially weighted absolute integral of $\psi$ is finite.

For the double integral, useDifferentiating the second formula gives $\int \psi (t)(1+it)e^{-(1+it)u}dt=-{\varphi }^{\prime }(u)$. absolute convergence from the rapid decay permits Fubini's theorem. The derivative energy constant for a smooth sieve cutoff is thereforeThere is no complex conjugate in this integral: the two factors both become $-{\varphi }^{\prime }(u)$, which is real. The constant is positive; in fact the Cauchy-Schwarz inequality applied to $\varphi (1/3)-\varphi (0)=-1$ gives $c_{\varphi }\ge 3$.

Here is the basic structure of the smooth divisor-square sieve asymptotic, with enough uniform estimates to specify the error. Write $L=\log X$ and $R=X^{1/3}$. Expand the square and count multiples of the least common multiple $[d,e]$ in an arbitrary interval $I$ of length $X$:The sum is effectively restricted to $d,e<R$. Each count is $X/[d,e]+O(1)$, independent of the interval's position, so the total error is $O_{\varphi }(X^{2/3})$.

The Fourier representation of a smooth Selberg weight readsHence, with $z^{\prime }=(1+i{t}^{\prime })/L$,The four local terms correspond to the prime dividing neither divisor, only the first, only the second, or both. This is the Euler product for a smoothed divisor-square correlation. Factor it aswhereThe local factors of $H$ are $1+O(p^{-2+4\eta })$ when $|\mathrm{Re}z|,|\mathrm{Re}{z}^{\prime }|\le \eta$ for small fixed $\eta <1/4$. Thus $H$ is a holomorphic function near $(0,0)$, and evaluating each local factor at zero gives exactly one. Consequently $H(0,0)=1$ and $H(z,z^{\prime })=1+O(|z|+|z^{\prime }|)$ there.

The pole expansion $\zeta (1+w)=w^{-1}+O(1)$ now yieldswhen $|t|,|t^{\prime }|\le L^{1/4}$. Integrating the error against the rapidly decreasing transforms gives $O_{\varphi }(L^{-2})$. The complementary tails are harmless uniformly: absolute values in the original divisor series giveAny prescribed power decay of ${\int }_{|t|>L^{1/4}}|\psi (t)|dt$ is available, so these tails and the tails of the limiting kernel are $O_{\varphi }(L^{-2})$ after choosing sufficiently many applications of integration by parts. The same absolute bound justifies the original exchanges of infinite sums and integrals. Using the evaluated double integral,We conclude, uniformly over all interval locations,This proof does not assume that the interval starts near the origin.

Finally choose this one fixed smooth cutoff. primes above $R$ in $(X_0,X_0+X]$ contribute one each to the nonnegative weight, and at most $R$ primes lie below $R$. Thereforefor all sufficiently large $X$, uniformly in $X_0$. The bounded range $2\le X\le X_1$ follows by increasing the fixed constant and using the trivial interval bound $X+1$. Thus the short-interval prime upper bound from a smooth divisor weight is

A cyclic group has one generator of a group: $G=⟨a⟩=\{a^j:j\in \mathbb{Z}\}$. An abelian group has $xy=yx$ for every pair of elements. Powers of one element commute because $a^r{a}^s=a^{r+s}=a^{s+r}=a^s{a}^r$, so every cyclic group is Abelian. The Klein four-group $C_2\times C_2$ is Abelian but is not a cyclic group: every nonidentity element has order two, whereas a generator of a group for a four-element cyclic group would have order four.

Fix a generator of a group $x$ of $C_n$. A group homomorphism is determined by $g=\varphi (x)$ because $\varphi (x^j)=g^j$, and the relation $x^n=1$ forces $g^n=1$. Conversely, such a $g$ defines $\varphi (x^j)=g^j$: exponents differing by a multiple of $n$ give the same value, and addition of exponents verifies the group homomorphism law. Thus the homomorphism from a finite cyclic group correspondence isFor $S_4$, the order of a permutation is the least common multiple of its disjoint cycle lengths. The condition ${\sigma }^4=1$ allows identity, transpositions, two disjoint transpositions, and four-cycles. The sixteen homomorphisms are ${\varphi }_{\sigma }(x^j)={\sigma }^j$, with the full list of possible generator imagesThe remaining eight elements of the symmetric group are three-cycles and do not qualify.

Use the positive-sign quantum Fourier transformOrthogonality of the finite-group characters makes $F_N$ a unitary operator. Here $r$ is the least positive period. The injectivity within one period implies $r\mid N$: write $N=qr+s$, $0\le s<r$. Periodicity gives $f(s)=f(N)=f(0)$, and injectivity forces $s=0$. Put $L=N/r$.

Start with two available computational basis states $|0⟩|0⟩$. Apply $F_N$ to the first register and query the modular-addition quantum oracle:Measure the second register. For some $t\in \{0,\dots ,r-1\}$, the first register becomes the normalized coset stateThe quantum Fourier transform of a periodic coset state isIndeed, the inner geometric sum vanishes unless the Fourier label is a multiple of $N/r$. Measuring that label gives $j=sN/r$ for a uniformly random $s$. Compute, by the Euclidean algorithm,Thus exact period recovery from a Fourier sample succeeds whenever $s$ is coprime to $r$, andHere $\phi$ is the Euler totient function. The classical number-theory input is the totient lower bound from the Mertens product: for sufficiently large $m$, $\phi (m)/m\ge c/\log \log m$ for an absolute $c>0$, with the finitely many small cases handled separately. For $r=1$ recovery is certain; for $r=2$ its probability is $1/2$. The useful asymptotic probability statement is a lower bound, hence $\Omega$ notation; it can be much larger for particular periods, for example a prime period.

There is one oracle query, two Fourier transforms and two measurements. The final greatest common divisor and division use polynomial time in $\log N$. This meets the specified primitive-operation model without assuming that an arbitrary-$N$ Fourier gate is free in another gate model. If a constant success probability is wanted, repeat independently $O(\log \log N)$ times and return the least common multiple of the candidates: each candidate divides $r$, and one successful sample makes that least common multiple exactly $r$.

Every finite cyclic subgroup of order $m$ has exactly $\phi (m)$ generators, where $\phi$ is the Euler totient function: if $g$ has order $m$, then $g^k$ generates precisely when $\gcd (k,m)=1$. Each element generates exactly one cyclic subgroup. Thus counting cyclic subgroups by their generators amounts to counting elements by order of a group element and dividing by $\phi (m)$.

Use the cycle decomposition of a permutation in $S_5$. A permutation with $a_j$ cycles of length $j$ occurs $5!/{\prod }_j(j^{a_j}{a}_j!)$ times: order the five letters, then divide by the cyclic choices of starting point and the orderings of equal-length cycles. Its order is the least common multiple of the cycle lengths. The resulting count isThe two subgroups $⟨(12)⟩$ and $⟨(12)(34)⟩$ are both isomorphic to $C_2$ by a group isomorphism. They are not conjugate subgroups: conjugating their unique nonidentity elements would have to preserve cycle type, whereas a transposition and a product of two disjoint transpositions have different cycle types.

Let $L=\sqrt{D}$. Regroup the finite divisor sum using the least common multiple:This is nonnegative. If $n$ has no prime factor in $\mathcal{P}$, only $d=1$ can contribute to the inner sum, so it equals ${\rho }_1=1$. This proves the required pointwise upper-bound sieve inequality. Whenever a term defining ${\lambda }_d$ is nonzero, $u,v\le L$ and their prime factors lie in $\mathcal{P}$. Hence $d=[u,v]\le uv\le L^2=D$, and every prime factor of $d$ lies in $\mathcal{P}$. Thus these are upper-bound sieve weights of level $D$, as described by the Selberg least-common-multiple weights.