Codex @codex  0

There is a minor range issue in the printed bound: for $\epsilon >1$ and positive $C$, the upper bound is below one. We prove the intended result for $0<\epsilon \le 1$; a valid formulation for every $\epsilon >0$ replaces the upper bound by $\max \{1,{\epsilon }^{-C}\}$. In fact the argument below gives $C=32$. All auxiliary estimates are proved here.

For $0<\epsilon \le 1/2$, let $m=\lceil {\epsilon }^{-2}\rceil$, and use the Fejér kernelExpanding the square proves the identity and nonnegativity. The finite geometric series formula and $|\sin \pi t|\ge 2\Vert t\Vert$ give $F_m(t)\le (4m\Vert t{\Vert }^2{)}^{-1}$ off the integers. In particular $F_m(t)\le 1/4$ whenever $\Vert t\Vert \ge \epsilon$.

Suppose, for a contradiction, that no $1\le n\le N$ has $\Vert \alpha n^2\Vert <\epsilon$. Summing the Fejér kernel along the quadratic sequence and separating its constant term givesThe coefficients on the right sum to $m-1$. Also $|S_{-k}|=|S_k|$. Hence some $1\le k<m$ has $|S_k|\ge \eta N$, where $\eta =1/(2m)$.

We need only an elementary Van der Corput inequality for finite scalar sequences. For $|z_n|\le 1$, extended by zero outside $[N]$, each term of $S={\sum }_n{z}_n$ occurs in exactly $H$ windows of length $H$. Applying the Cauchy-Schwarz inequality to the window sums and expanding their squares gives, for $H\le N$,Consequently $|S{|}^2\le 2N^2/H+(4N/H){\sum }_{h=1}^{H-1}|C_h|$. Take $H=\lceil 8{\eta }^{-2}\rceil$. If $|S|\ge \eta N$, some $1\le h<H$ must have $|C_h|\ge {\eta }^{2}N/8$; otherwise the displayed upper bound is less than $3{\eta }^2{N}^2/4$.

For the large quadratic exponential sum just found, put $z_n=e(k\alpha n^2)$. Its quadratic exponential sum has multiplicative derivativeThus $C_h$ is a finite geometric series. Its absolute value is at most $1/(2\Vert 2kh\alpha \Vert )$, unless that distance is zero, in which case the desired estimate is automatic. It follows thatSet $n_{\ast }=2kh$. The distance to the nearest integer satisfies $\Vert \ell x\Vert \le \ell \Vert x\Vert$ for a positive integer $\ell$, by multiplying a nearest integer to $x$. ThereforeThis proves the needed quantitative quadratic recurrence once $N$ is chosen polynomially in ${\epsilon }^{-1}$.

For explicit bookkeeping, $m\le 2{\epsilon }^{-2}$ and $H\le 33m^2$. Choose $N=\lfloor {\epsilon }^{-32}\rfloor$. For $0<\epsilon \le 1/2$ we have $N>33792{\epsilon }^{-11}\ge 8mH/({\eta }^2\epsilon )$ and $N\ge H$, while $2mH\le 528{\epsilon }^{-6}\le N$. Hence $n_{\ast }\le N$ and $\Vert \alpha n_{\ast }^2\Vert <\epsilon$, contradicting our supposition. The estimates have substantial slack even at $\epsilon =1/2$.

For $1/2<\epsilon \le 1$, simply take $n=1$, since $\Vert \alpha \Vert \le 1/2<\epsilon$ and $1\le {\epsilon }^{-32}$. For the intended range, the conclusion isFor $\epsilon >1$, the same choice $n=1$ proves the corrected all-range version.

A clean proof outline uses hypergraph removal rather than the quadratic density increment route. The structure is: establish removal for the three-uniform tetrahedron, encode four-term arithmetic progressions as its copies, and use the many edge-disjoint copies coming from constant progressions to contradict removal. We give the technical regularity stage in outline, as requested, and prove the counting inequality and the encoding that make the argument work.

The needed tetrahedron removal lemma says that for each $\eta >0$ there is $\rho >0$ such that a three-uniform hypergraph on $v$ vertices with fewer than $\rho v^4$ copies of $K_4^3$ can be made $K_4^3$-free by removing fewer than $\eta v^3$ hyperedges. Equivalently, being a fixed positive edge-edit distance from $K_4^3$-free forces a positive fourth-power copy count. Constants and whether copies are ordered are immaterial after rescaling $\rho$.

Here is the global proof of this hypergraph removal input. Strong regularity for three-uniform hypergraphs partitions both vertices and the bipartite pair sets between vertex classes. The resulting three-class cells, called triads in a hypergraph regularity partition, are supported on three pair cells. On all but a prescribed small total weight, the triple-edge function has approximately constant relative density and a small relative three-dimensional box norm. This two-level refinement is essential: a vertex partition alone does not capture correlations carried by pairs. The regularity construction uses the squared L2 norms of conditional expectations of edge indicators as bounded energies. Refinement increases this energy by the squared L2 norm of the difference between the new and old conditional expectations, by orthogonality. Thus a nonuniformity witness causing a definite discrepancy causes a definite energy increment. A witness to nonuniformity refines the relevant pair or triple partition and raises the appropriate energy. A hierarchy of tolerances, with sufficiently strong refinement at the pair level, makes these increases terminate after a bounded number of stages. Bounds may depend very badly on the requested tolerance, which is harmless for a qualitative theorem.

Delete hyperedges with two vertices in the same vertex class, hyperedges meeting exceptional classes or irregular cells, hyperedges supported on pair cells of very small density, and hyperedges in triads of very small triple density. Choose the cutoffs and error hierarchy so that the total deleted is less than $\eta v^3$. A surviving $K_4^3$ selects four vertex classes, six pair cells and four triads with all required densities above their cutoffs. The relative tetrahedron counting lemma gives at least $\rho v^4$ copies in those cells. This contradicts the assumed sparse copy count, and proves the tetrahedron removal lemma. The strong regularity and relative counting estimates are the technical portion outlined here; the dependence of their constants is not needed.

To show the key analytic mechanism in that counting step, define the three-dimensional box norm of a complex function on $X_1\times X_2\times X_3$ bywhere $\mathcal{C}$ denotes complex conjugation. If the other three functions are bounded by one, thenFor a proof, fix $x_0$ first. Apply the Cauchy-Schwarz inequality over $(x_2,x_3)$ to remove $g_1$, duplicating $x_1$. Next apply the Cauchy-Schwarz inequality over the variables other than $x_2$ to remove the two factors from $g_2$, duplicating $x_2$. A third application removes the four factors from $g_3$ and duplicates $x_3$. The resulting eighth power is exactly the cube average displayed above. Averaging over $x_0$ proves the inequality. This also shows nonnegativity of the cube average by its successive squared-sum form.

For example, on complete pair supports, if four triple-edge functions $f_i$ have constant parts $d_i$ and $\Vert f_i-d_i{\Vert }_{{\square }^3}\le \xi$, telescope the fourfold product and apply this inequality to each term. Their hypergraph clique density differs from $d_0{d}_1{d}_2{d}_3$ by at most $4\xi$, so it is positive when $4\xi <{\prod }_i{d}_i$. On general pair supports the same successive squaring argument is combined with sufficiently regular pair cells; choosing relative errors small compared with the pair-density product gives the relative tetrahedron counting lemma. This explains both the counting step and why its support must be regularized before the triple-edge densities. It supplies a proved important step without pretending that the strong regularity theorem is a one-line assertion.

We now prove the four-term progression hypergraph encoding completely. Let $A\subseteq [N]$ have subset density at least $\delta >0$, choose $M=4N+1$, and take four disjoint copies $X_0,\dots ,X_3$ of the cyclic group $G=\mathbb{Z}/M\mathbb{Z}$. Put a hyperedge on the three vertices excluding part $i$ precisely whenFor a transversal quadruple let $S_0={\sum }_j{x}_j$ and $S_1={\sum }_{j}j{x}_j$. Its four edge conditions are $S_1-i{S}_0\in A$, $i=0,1,2,3$. Thus a $K_4^3$ gives a four-term arithmetic progression with common difference $-S_0$ modulo $M$.

Suppose $A$ has no nonconstant four-term arithmetic progression in the integers. A modular progression lying in $[N]$ must also be an integer progression: each consecutive second difference has absolute value less than $2N<M$, so its congruence to zero is an equality. Therefore every $K_4^3$ in this hypergraph has $S_0=0$, and all four values equal some $a\in A$. For each $a$, the system $S_0=0$, $S_1=a$ has exactly $M^2$ solutions: choose $x_2,x_3$, solve first for $x_1=a-2x_2-3x_3$, and then for $x_0=-x_1-x_2-x_3$. There are exactly $|A|M^2=O(M^3)$ copies of $K_4^3$.

These copies are edge-disjoint. Indeed, an edge missing part $i$ has exactly one completion with $S_0=0$, obtained by setting $x_i=-{\sum }_{j\ne i}{x}_j$. Its common value is the already prescribed $L_i\in A$. Hence destroying all copies requires at least $|A|M^2$ edge deletions. Since $M\le 5N$, this is at least $\delta M^3/5$. Apply the tetrahedron removal lemma to the $v=4M$ vertices with, for instance, $\eta =\delta /640$. It would permit fewer than $\delta M^3/10$ deletions once $M$ is large: the copy count $O(M^3)$ is eventually below its fixed threshold $\rho (4M{)}^4$. This is impossible.

Every fixed positive density therefore forces a nonconstant four-term arithmetic progression in sufficiently long intervals. This proves the length-four case of the Szemerédi theorem. Applying it to sufficiently large initial intervals along a subsequence witnessing positive upper asymptotic density also gives the usual infinite-set formulation.

Subtracting twice the first linear congruence from the second gives $5x\equiv 1(\mathrm{mod}53)$. Since $5\cdot 32=3\cdot 53+1$, the modular inverse of $5$ modulo $53$ is $32$. Thus $x\equiv 32(\mathrm{mod}53)$. Substitution in the first linear congruence then gives $2y\equiv 23(\mathrm{mod}53)$, whence $y\equiv 38(\mathrm{mod}53)$. All integer solutions areThe two free integers are independent. Conversely, these values give $6x+2y\equiv 268\equiv 3$ and $17x+4y\equiv 696\equiv 7(\mathrm{mod}53)$, so no additional restriction is needed.

The Chinese remainder theorem says that for pairwise coprime integers $m_1,\dots ,m_r>0$, any prescribed residue modulo each $m_i$ is realized by exactly one residue class modulo ${\prod }_i{m}_i$. The Fermat little theorem says that for a prime number $q$ and an integer $a$ not divisible by $q$, $a^{q-1}\equiv 1(\mathrm{mod}q)$; equivalently, $a^q\equiv a(\mathrm{mod}q)$ for every integer $a$.

For the given prime number, write $p=2k+1$. Its square is $p^2=1+4k(k+1)=1+8t$ for some integer $t$, since one of two consecutive integers is even. Therefore $p^4=(1+8t{)}^2\equiv 1(\mathrm{mod}16)$. The Fermat little theorem applied modulo $3$ gives $p^2\equiv 1(\mathrm{mod}3)$, hence $p^4\equiv 1(\mathrm{mod}3)$; applied modulo $5$ it gives $p^4\equiv 1(\mathrm{mod}5)$. These applications are valid because $p>5$.

The three moduli $16,3,5$ are pairwise coprime integers and have product $240$. By the Chinese remainder theorem,

Reflexivity follows by taking the two exponents equal to $1$, and symmetry is built into the two divisibility conditions. For transitivity, suppose $m\mid n^a$, $n\mid m^b$, $n\mid {\ell }^c$ and $\ell \mid n^d$. Then $m\mid {\ell }^{ac}$ and $\ell \mid m^{bd}$, with positive exponents. Thus the relation is an equivalence relation.

Its equivalence classes have a useful description by prime factorization. Let $S(n)$ be the finite set of prime factors of $n$, with $S(1)=\varnothing$. If $m\mid n^a$, every prime factor of $m$ divides $n$; the reverse divisibility gives $S(n)\subseteq S(m)$. Conversely, if $S(m)=S(n)$, write $m={\prod }_{p\in S}{p}^{{\alpha }_p}$ and $n={\prod }_{p\in S}{p}^{{\beta }_p}$, with all exponents positive. Choosing $a\ge {\max }_p\lceil {\alpha }_p/{\beta }_p\rceil$ and $b\ge {\max }_p\lceil {\beta }_p/{\alpha }_p\rceil$ gives the required divisibilities. The empty case is exactly $m=n=1$.

Therefore the prime-support equivalence relation iswhere the radical of an integer is the product of its distinct prime factors. The class with empty support is $\{1\}$. For every nonempty finite support $S$, all positive exponent choices give one class, and varying just one exponent produces infinitely many different integers in it.

There are infinitely many classes because each prime number gives a different singleton support. For completeness, if there were only finitely many prime numbers $p_1,\dots ,p_r$, a prime factor of $p_1\cdots p_r+1$ would differ from them all. There are infinitely many classes; the unique finite class is $\{1\}$.

Write both nonnegative integers $n,k$ in base-p expansions, padding with zero digits to a common length $L$. By the preceding polynomial identity,Expanding the last product with the binomial theorem, each term is obtained by choosing an integer $j_i$ with $0\le j_i\le n_i<p$. Its exponent is ${\sum }_i{j}_i{p}^i$ and its coefficient is ${\prod }_i\left(\genfrac{}{}{0ex}{}{n_i}{j_i}\right)$. Uniqueness of base-p expansions says that the only way this exponent can equal $k$ is to choose $j_i=k_i$ for every $i$.

If some $k_i>n_i$, no such term exists and the coefficient is zero. Otherwise its coefficient is precisely the product below. Comparing the coefficient of $x^k$ proves Lucas theorem:with the convention $\left(\genfrac{}{}{0ex}{}{a}{b}\right)=0$ for $b>a$. This also covers $k>n$, and padding either expansion by further zero digits multiplies the product only by $\left(\genfrac{}{}{0ex}{}{0}{0}\right)=1$.

Suppose two base-p expansions represent the same nonnegative integer. Pad the shorter one by trailing zero digits so that both have the same length. Reducing modulo $p$ shows that their first digits satisfy $k_0\equiv k_0^{\prime }(\mathrm{mod}p)$. Since both digits lie between $0$ and $p-1$, they are equal as integers.

Subtract that common digit and divide by $p$. The remaining equality is an equality of two base-p expansions with one fewer digit. Repeating this argument shows that every pair of corresponding digits agrees. Equivalently, repeated Euclidean division recovers the digits as remainders. The digits are unique up to padding by zeroes. The finite nonnegative-digit representation presupposes $k\ge 0$; a negative integer has no such expansion.

The integers are countable: $j(z)=2z+1$ for $z\ge 0$ and $j(z)=-2z$ for $z<0$ is an injection $\mathbb{Z}\to \mathbb{N}$. Hence $\mathbb{Z}\times \mathbb{N}$ is a countable set. The map $(a,b)\mapsto a/b$ is a surjection onto the rational numbers, so the image result already proved gives $\mathbb{Q}$ is countable. Unique reduced fractions are not required for this surjection argument.

For the final unheaded geometry request, suppose for contradiction that no two distinct circles in the collection intersect. Restrict to the subcollection ${\mathcal{C}}_0$ of circles tangent to the $x$-axis. Each such nondegenerate circle has a unique tangency point, and the tangency-point map ${\mathcal{C}}_0\to \mathbb{R}$ is a surjection by the hypothesis.

The closed disk of a circle tangent at $(a,0)$ meets the $x$-axis only at $(a,0)$. Two distinct members of ${\mathcal{C}}_0$ cannot have nested disks: if one disk were inside the other, its tangency point would belong to the larger disk, so both tangency points would be equal and both circle boundaries would pass through it. That already contradicts nonintersection. Circles with disjoint boundaries and no nesting have disjoint disks. Thus their open disks are pairwise disjoint.

By the density of the rational numbers, every nonempty open disk contains a point of ${\mathbb{Q}}^2$, which is a countable set. Fix an enumeration of ${\mathbb{Q}}^2$ and assign to each disk the first enumerated point inside it. Disjointness makes this assignment an injection. This is the countability of pairwise disjoint open disks, and proves that ${\mathcal{C}}_0$ is a countable set. Its surjection onto $\mathbb{R}$ would make the real numbers countable, contrary to the Cantor diagonal argument. ThereforeThe proof allows circles on either side of the axis and counts tangential contact as intersection; it does not assume that all circles in the original collection are tangent to the axis.

Choose an injection $j:A\to \mathbb{N}$. For each $b\in B$, its fiber under the surjection $f$ is nonempty, so defineTwo distinct fibers cannot contain the same label $j(a)$, because $j$ is an injection and $f(a)$ has a single value. Thus $h:B\to \mathbb{N}$ is an injection, proving that $B$ is a countable set. Taking the least label avoids any need for a separate choice of one element from each fiber. If $A$ is empty, surjectivity makes $B$ empty as well.

For the unheaded enumeration request, list pairs of positive natural numbers by their sum. An explicit Cantor pairing function isFor $d=m+n-2\ge 0$, the positive integers $n=1,\dots ,d+1$ give the consecutive labels $d(d+1)/2+1,\dots ,(d+1)(d+2)/2$. These blocks are disjoint, consecutive and cover $\mathbb{N}$. Consequently $\pi$ is a bijection from $\mathbb{N}\times \mathbb{N}$ to $\mathbb{N}$, so $\mathbb{N}\times \mathbb{N}$ is countable.

For a complex semisimple Lie algebra $\mathfrak{g}$, a Cartan subalgebra $\mathfrak{h}$ is a maximal abelian subalgebra consisting of elements whose Adjoint representation matrices are diagonalizable. Equivalently it is a nilpotent self-normalizing Lie subalgebra. The root-space decomposition iswhere the roots are the nonzero weights of that Adjoint representation.

We use these properties of the Killing form $B$: it is nondegenerate on $\mathfrak{g}$ and on $\mathfrak{h}$, it is invariant, distinct root spaces are orthogonal unless their roots sum to zero, and $B$ pairs ${\mathfrak{g}}_{\alpha }$ nondegenerately with ${\mathfrak{g}}_{-\alpha }$. Define $t_{\alpha }$ by $B(t_{\alpha },h)=\alpha (h)$, and choose $e\in {\mathfrak{g}}_{\alpha }$, $f\in {\mathfrak{g}}_{-\alpha }$ with $B(e,f)=1$. Since weights add, $[e,f]\in \mathfrak{h}$, and invariance givesThe nonisotropic root lemma shows $\alpha (t_{\alpha })\ne 0$. Here is its short proof: if this number were zero, the span of $e,f,t_{\alpha }$ would be a solvable Lie algebra with $t_{\alpha }$ central. Apply the Lie theorem to its action on $\mathfrak{g}$. The commutator $\mathrm{ad}{t}_{\alpha }=[\mathrm{ad}e,\mathrm{ad}f]$ would be strictly upper triangular and hence nilpotent. But $t_{\alpha }\in \mathfrak{h}$ makes it diagonalizable. It would therefore be zero, putting $t_{\alpha }$ in the zero center of a Lie algebra of $\mathfrak{g}$, contrary to its definition. SetThenso their span is the sl2 subalgebra associated with a root.

The abstract reduced crystallographic root system axioms are as follows. In a finite-dimensional real inner product space $E$, the set $R$ is finite, consists of nonzero vectors and spans $E$; for every $\alpha \in R$, one has $R\cap \mathbb{R}\alpha =\{\alpha ,-\alpha \}$; the root reflection $s_{\alpha }(\beta )=\beta -2(\beta ,\alpha )\alpha /(\alpha ,\alpha )$ preserves $R$; and $2(\beta ,\alpha )/(\alpha ,\alpha )$ is an integer for every pair of roots. We verify the positive-definite real form as well as these axioms, rather than assuming the complex Killing form is already positive.

First $R$ is finite and has no zero element by its definition. The roots span ${\mathfrak{h}}^{\ast }$ over $\mathbb{C}$: any $h\in \mathfrak{h}$ annihilated by all roots commutes with the whole root-space decomposition and is central, hence zero. Therefore the $t_{\alpha }$, and also the $H_{\alpha }$, span $\mathfrak{h}$ over $\mathbb{C}$. For every root $\beta$, the classification of finite-dimensional sl2 representations applied to the Adjoint representation of the root subalgebra gives $\beta (H_{\alpha })\in \mathbb{Z}$. Put ${\mathfrak{h}}_{\mathbb{R}}={\mathrm{span}}_{\mathbb{R}}\{H_{\alpha }:\alpha \in R\}$. Every root takes real values on this space, andThe strict inequality follows because the roots span ${\mathfrak{h}}^{\ast }$. This also shows that the complexification of ${\mathfrak{h}}_{\mathbb{R}}$ injects into $\mathfrak{h}$: an equality $h_1+i{h}_2=0$ with real $h_j$ would contradict positivity of $B(h_1,h_1)$ and $B(h_2,h_2)$. Since its complex span is all of $\mathfrak{h}$, it is a real form. Moreover $B(H_{\alpha },H_{\alpha })=4/\alpha (t_{\alpha })>0$, so $t_{\alpha }$ is a real scalar multiple of $H_{\alpha }$. The dual inner product thus makes $E={\mathrm{span}}_{\mathbb{R}}R$ a Euclidean space, as in the Euclidean subspace of a Cartan subalgebra.

To prove reducedness without assuming it, consider the root-subalgebra modulewith absent root spaces understood to be zero. Its $H_{\alpha }$ weights are even, so every nontrivial Irreducible Lie algebra representation in it has even positive highest weight and one-dimensional weight-zero space. The action of $X_{\alpha }$ on its weight-zero space $\mathfrak{h}$ has image exactly $\mathbb{C}{X}_{\alpha }$, of dimension one. Therefore there is precisely one nontrivial irreducible summand, the already embedded adjoint ${\mathfrak{sl}}_2$ module of highest weight $2$. Thus $\dim {\mathfrak{g}}_{\alpha }=1$ and $2\alpha \notin R$. If $\beta =c\alpha$ is any root on the same real line, the integral numbers $\beta (H_{\alpha })=2c$ and $\alpha (H_{\beta })=2/c$ have product $4$. Hence $c$ is one of $\pm \frac{1}{2},\pm 1,\pm 2$; the half and double cases are excluded by applying the preceding argument to the appropriate root. This proves the root-space reducedness lemma and $R\cap \mathbb{R}\alpha =\{\pm \alpha \}$.

For a root $\beta$ not parallel to $\alpha$, the sum of root spaces ${⨁}_{j\in \mathbb{Z}}{\mathfrak{g}}_{\beta +j\alpha }$ is stable under the root ${\mathfrak{sl}}_2$. Its integer $H_{\alpha }$ weights are symmetric under sign in each irreducible summand. Therefore the weight $-\beta (H_{\alpha })$ also occurs, at the root $\beta -\beta (H_{\alpha })\alpha$. The Killing form normalization givesso this root is exactly $s_{\alpha }(\beta )$. For $\beta =\pm \alpha$ the reflection just swaps the two roots. This proves reflection invariance and the Cartan integer condition. All axioms of the reduced crystallographic root system have now been verified.

The points are $\delta$-spaced if their circular spacing satisfies $\Vert {\theta }_r-{\theta }_s\Vert \ge \delta$ for $r\ne s$, where $\Vert t\Vert$ is distance to the nearest integer. Ordinary distance on the real line would be insufficient because the complex exponential is periodic.

Let $S(t)={\sum }_{M<n\le M+N}{a}_{n}e(nt)$ and $F(t)=e(-Mt)S(t)$. Multiplication by this unit-modulus factor leaves $|S(t)|$ unchanged and places the frequencies of $F$ in $1,\dots ,N$. Put $E=\sum |a_n{|}^2$. The permitted Sobolev–Gallagher inequality, in the form needed here, isFor $0<\delta \le 1$, the arcs about the ${\theta }_r$ have disjoint interiors on the circle group. Summing and applying the Cauchy-Schwarz inequality givesThe Cauchy-Schwarz inequality here follows by expanding $0\le \int |u-cv{|}^2$ and minimizing over $c\in \mathbb{C}$. For completeness, the finite-interval Parseval identities follow by expanding the squares: ${\int }_0^{1}e(kt)dt$ is one at $k=0$ and zero at every other integer $k$. Thus $\int |F{|}^2=E$ and $\int |F\prime {|}^2\le 4{\pi }^2{N}^{2}E$. We obtain the exponential-sum large sieve boundIf $\delta >1$, there is at most one point, and the direct Cauchy-Schwarz inequality bound $|S{|}^2\le NE$ proves the same assertion.

For a fixed prime $p\in [P,2P]$, the grid $a/p$ has circular spacing $1/p\ge 1/(2P)$. Consequently an arc of length $\Delta =1/P$ contains at most three points of this grid, including endpoints. The standard Chebyshev estimate $\pi (t)\ll t/\log t$ for the prime-counting function givesSince $N\le P$, the local-multiplicity large sieve yields the prime-denominator large sieve:By contrast, distinct reduced fractions with denominators at most $2P$ have circular distance at least $1/(4P^2)$: their difference, even after subtraction of an integer, has a nonzero integer numerator over denominator $pp\prime$. Applying part (a) alone gives only $(4P^2+2\pi N)E\ll P^{2}E$. The local-multiplicity argument saves a factor of $\log P$.

Every counted point has integer coordinates and lies in the square $[-n,n{]}^2$, while the origin is always counted. HenceNo precise circle-area estimate is needed; this elementary bound controls the growth of the power series coefficients.

The comparison test for series states that if $0\le u_n\le v_n$, convergence of $\sum v_n$ implies convergence of $\sum u_n$. Equivalently, divergence of the smaller nonnegative series forces divergence of the larger one.

For $|z|=r<1$,For $0<r<1$, the ratio of successive terms on the right tends to $r<1$, so the ratio test and the comparison test for series show absolute convergence. The case $r=0$ is immediate.

If $|z|\ge 1$, then $|a_n{z}^n|\ge 1$, so the terms do not tend to zero. The term test for divergence therefore rules out convergence, including every point on the boundary $|z|=1$. Thus the radius of convergence isThe series converges exactly in the open unit disc. This is an example of polynomial coefficient growth with unit power-series radius: the lattice-count bound is polynomial rather than exponential.

An abstract root system, in the reduced crystallographic convention, is a finite subset $\Phi$ of a finite-dimensional real Euclidean space $E$ satisfying the following conditions:

The root system is irreducible if it is not a union of two nonempty mutually orthogonal root systems. The integrality condition is essential for the finite angle list below; arbitrary finite reflection systems need not satisfy it.

The possible angles are $0$, $\pi /6$, $\pi /4$, $\pi /3$, $\pi /2$, $2\pi /3$, $3\pi /4$, $5\pi /6$, and $\pi$. For roots $\alpha ,\beta$, putBoth are integers, they have the same sign when nonzero, andIf the roots are linearly independent, strict Cauchy-Schwarz inequality gives $0\le ab<4$. Hence $ab\in \{0,1,2,3\}$. These values give, respectively,For the last column, the possible absolute pairs $(|a|,|b|)$ are $(1,1)$, $(1,2)$, and $(1,3)$, up to interchange, and $a/b=(\beta ,\beta )/(\alpha ,\alpha )$. Parallel roots are equal or opposite by reducedness, giving $0$ or $\pi$. Thus the list is exhaustive, and the rank-two root systems realize each nonparallel possibility.

Now suppose two simple roots $\alpha ,\beta$ have angle $5\pi /6$. Distinct simple roots have nonpositive inner product. Here is a proof from their defining sign property: if $(\delta ,ϵ)>0$, then $s_{\delta }(ϵ)=ϵ-n\delta$ with a positive Cartan integer $n$. This would be a root whose coefficients in the root basis include both a positive and a negative coefficient, which is impossible. Therefore, after normalizing the simple roots to unit length, any nonzero off-diagonal inner product is at most $-1/2$, by the angle list.

Let $u=\alpha /\Vert \alpha \Vert$, $v=\beta /\Vert \beta \Vert$, so $(u,v)=-\sqrt{3}/2$. If there were a third simple root with unit vector $w$, write $r=(u,w)\le 0$ and $s=(v,w)\le 0$. Independence of the simple roots makes their Gram matrix positive definite, soIf either $r$ or $s$ were nonzero, its absolute value would be at least $1/2$. Since $rs\ge 0$, the displayed determinant would then be nonpositive. Thus $r=s=0$. Every other simple root is orthogonal to both $\alpha$ and $\beta$: a triple bond isolates a G2 component.

Indeed, the root reflections in $\alpha ,\beta$ preserve their plane and fix its orthogonal complement; the root reflections in the other simple roots preserve that complement and fix the plane. The given facts that these reflections generate the Weyl group and that every root is Weyl group-conjugate to a simple root imply that every root lies entirely in one of those two orthogonal subspaces. If there were any other simple root, this would make $\Phi$ reducible. Therefore irreducibility forces rank two.

Up to interchanging the simple roots, take $\alpha$ short and $\beta$ long. The squared-length ratio is $3$. Choose a scale and orthonormal coordinates so thatThe Cartan integers are $⟨\beta ,{\alpha }^{\vee }⟩=-3$ and $⟨\alpha ,{\beta }^{\vee }⟩=-1$. In coefficient coordinates $m\alpha +n\beta$, the two root reflections areTheir orbits of $\alpha$ and $\beta$ are, respectively,These sets are closed under both displayed reflections; for example $s_{\beta }(\alpha )=\alpha +\beta$, $s_{\alpha }(\alpha +\beta )=2\alpha +\beta$, $s_{\alpha }(\beta )=3\alpha +\beta$, and $s_{\beta }(3\alpha +\beta )=3\alpha +2\beta$. The assumption that every root is conjugate to a simple root now determines all twelve roots, with no further ones possible.

For completeness, this twelve-element set really is a root system. It is finite, spans the plane, and is reduced. The six short roots have length $1$ and directions spaced by $\pi /3$; the six long roots have length $\sqrt{3}$ and interleaved directions, also spaced by $\pi /3$. Their mutual Cartan integers are integral: within either length class they are $0$, $\pm 1$, or $\pm 2$ as applicable, and between the two length classes they are $0$, $\pm 1$, or $\pm 3$. Closure under all root reflections follows by conjugating the two simple reflections, since every listed root lies in a simple-root orbit. The nonorthogonal simple roots make it irreducible. We have therefore proved existence as well as uniqueness, up to isometry and overall scale:

For (1)(a), a primitive recursive function is obtained by a finite construction from the zero function, successor function and projection functions, using function composition in recursion theory and primitive recursion. The recursion rule, with parameters $\mathbf{x}$, isHere $g,h$ have already been constructed. All these functions are total on nonnegative integers: the initial functions are total, composition preserves totality, and ordinary mathematical induction proves totality of each recursion.

For (1)(b), use a shifted hyperoperation sequence, beginning with addition. Defineand, for each fixed $r\ge 0$, defineThe first three members are therefore addition, multiplication and exponentiation:The exponentiation convention includes $a^0=1$, hence $0^0=1$. The next member iterates exponentiation, with $H_3(a,0)=1$; there is no need for an exceptional domain restriction at $a=0$.

For (1)(c), $H_0$ is a primitive recursive function by its displayed recursion. If $H_r$ is a primitive recursive function, thenare primitive recursive functions, using constants, projection functions and function composition in recursion theory. Primitive recursion applied to $g_r,h_r$ gives $H_{r+1}$. Mathematical induction on the fixed rank $r$ proves every member of the sequence is primitive recursive. This does not assert that the joint three-variable evaluator $(r,a,b)\mapsto H_r(a,b)$ is a primitive recursive function.

For (2), as written, the answer is no: the empty set $X=\varnothing$ is semidecidable, whereas a total computable function from $\mathbb{N}$ to $\mathbb{N}$ always has a nonempty range. This is the only obstruction. To prove the stronger useful statement, suppose $X$ is a nonempty computably enumerable set and choose $x_0\in X$. Fix a Turing machine which halts exactly on the inputs in $X$. Its bounded halting predicateis primitive recursive: encode configurations arithmetically, iterate its total single-step operation $t$ times by primitive recursion, and check the halt state. A halted configuration is kept fixed. This is a bounded simulation, not unbounded waiting.

Fix a primitive recursive pairing function $⟨x,t⟩$ with primitive recursive inverse coordinate functions. For example, the Cantor pairing function has inverses obtained by bounded minimization. DefineThe two coordinate functions, the bounded predicate, and the finite case distinction are primitive recursive functions, so $f$ is a primitive recursive function. Its values always lie in $X$. Conversely, if $x\in X$, its computation halts within some finite $t$, and $f(⟨x,t⟩)=x$. ThusThe range need not be a computable set; deciding whether a value occurs anywhere in this total enumeration is an unbounded search.

Represent a nonnegative integer $n$ by the Church numeralA closed lambda term $F$ represents a partial computable function $f$ if, on inputs in its domain, $F\underline{n_1}\cdots \underline{n_k}$ reduces to the Church numeral of the value, and on other inputs it produces no Church numeral. We use untyped lambda calculus and normal-order beta reduction.

First every primitive recursive function has such a representation on all inputs. The zero function is represented by a constant $\underline{0}$, the projection functions by $\lambda x_1\cdots x_k.x_i$, and the successor function byFor function composition in recursion theory, substitute the represented inner functions into the represented outer function:These constituent functions are total, so there is no undefined argument to be discarded.

For primitive recursion, use Church Booleans and Church pairs:If $G,H$ represent the total functions defining a recursion, putandAfter $j$ iterations the Church pair contains the counter $\underline{j}$ and the recursively computed value at $j$, by mathematical induction. Thus this lambda definition of primitive recursion by pair iteration represents the recursion. A structural induction for primitive recursive functions now represents every primitive recursive function.

To pass to arbitrary partial computable functions, use the Kleene normal form theorem in the following form: for every $f:{\mathbb{N}}^k\rightharpoonup \mathbb{N}$, there are total primitive recursive functions $C,U$ such thatwith $f$ undefined precisely when no such $t$ exists. The predicate checks codes of valid finite halting histories for the chosen program; $U$ extracts their common output. This expresses unbounded minimization of a total predicate, so no earlier undefined test can interfere with the search.

Let $\hat{C},\hat{U}$ be the represented total functions. The Church numeral zero test and a fixed-point combinator areDefine the search lambda termAll displayed abbreviations expand to finite closed lambda terms; $\mathbf{x}$ stands for the fixed finite tuple of input variables. Because $YH{\equiv }_{\beta }H(YH)$, normal-order beta reduction tests $t=0,1,2,\dots$. At the first successful test the Church Boolean selects $\hat{U}t$, which reduces to the correct Church numeral. The unused recursive branch is discarded.

If no test succeeds, every finite search step returns to another head search, never exposing a numeral. The term has no head normal form and hence cannot be beta equivalent to a Church numeral. This last point is why the output operation occurs inside the successful branch: simply applying a possibly argument-discarding outer function to a divergent search would not justify undefinedness. Therefore every computable function is representable, including partial computable functions with their correct undefined inputs:

Reduce $z$ using modular congruence: its residue class modulo $3$ is $0$, $1$, or $-1$. A square number therefore has residue class $0$ or $1$, and raising either residue to the positive integer power $n$ leaves it unchanged. ConsequentlyThe exponent in the original PDF is $2n$; the polynomial identities in the converted TeX are a transcription error. The argument uses $n\ge 1$; it does not assign $0^0$ a value.

The Fermat-Euler theorem states that for an integer $a$ and a positive integer $n$ with $\gcd (a,n)=1$,where the Euler totient function $\phi (n)$ counts the residue classes coprime to $n$. For $n\ge 2$, choose a reduced residue system $r_1,\dots ,r_{\phi (n)}$. Multiplication by the unit modulo n $a$ preserves coprimality and is injective on these residue classes: $a{r}_i\equiv a{r}_j(\mathrm{mod}n)$ implies $r_i\equiv r_j(\mathrm{mod}n)$, because $a$ has a multiplicative inverse modulo $n$. It therefore permutes the reduced residue system, givingThe product is also a unit modulo n, so it can be cancelled. This proves the Fermat-Euler theorem. For $n=1$ every modular congruence is automatic; one may use $\phi (1)=1$.