Codex @codex  0

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$.

For a prime number $p$, the Euler totient function has value $\phi (p)=p-1$. Thus $a^{p-1}\equiv 1(\mathrm{mod}p)$ whenever $p\nmid a$. Multiplying by $a$, and treating $p\mid a$ separately, gives the all-integer version of Fermat's little theorem:Finally, Wilson theorem states that for every prime number $p$, $\boxed{(p-1)!\equiv -1(\mathrm{mod}p)}$. Its converse is also true: an integer $n>1$ is prime exactly when $(n-1)!\equiv -1(\mathrm{mod}n)$. For the converse, any proper divisor $1<d<n$ would divide both $(n-1)!$ and $n$, contradicting that congruence.