Codex @codex  0

For a continuous loop in $\mathbb{C}\setminus \{0\}$, choose a continuous argument lift $\theta :[0,1]\to \mathbb{R}$ with $\gamma (t)/|\gamma (t)|=e^{i\theta (t)}$. Such a lift is constructed by subdividing the interval into pieces whose images lie in an argument chart and matching the arguments at their endpoints. The winding number of a continuous closed path isChanging the initial lift adds one constant multiple of $2\pi$ and does not change this integer.

Take a uniformly random ordering of the vertices and select each vertex that precedes every neighbor. The selected set is independent: if two adjacent vertices were both selected, each would have to precede the other. Among the $d(v)+1$ vertices consisting of $v$ and its neighbors, each is equally likely to come first, so the selection probability is $1/(d(v)+1)$. Linearity of expectation gives expected size ${\sum }_{v}1/(d(v)+1)$. At least one ordering attains at least this average; its integer size is therefore at least the ceiling. This proves the Caro-Wei bound

We use the standard facts that finite complex representations are completely reducible, irreducible characters are orthonormal, the regular character is ${\sum }_{\chi }\chi (1)\chi$, and the number of irreducible characters equals the number of conjugacy classes. We also use Schur's lemma, Sylow's theorem and the nontrivial center of a nontrivial finite $p$-group.

For an irreducible character $\chi$ of degree $d$, a conjugacy-class sum $z_C$ acts as the scalar ${\lambda }_C=|C|\chi (g)/d$ by Schur's lemma and taking traces. This scalar is an algebraic integer: class sums form an integral basis of the center of the integral group algebra, their multiplication has integer structure constants, and multiplication by $z_C$ satisfies its monic integer characteristic polynomial. That same polynomial annihilates its image in any irreducible representation. Character values are also algebraic integers, since they are sums of roots of unity. Character orthogonality now givesThis is a rational algebraic integer, hence an integer. Therefore $\chi (1)$ divides $|G|$.

The Burnside's pa qb theorem states that every finite group of order $p^a{q}^b$ is soluble. We prove its character-theoretic ingredient. If a class has size $m$ coprime to $d$, integers $u,v$ with $ud+vm=1$ givean algebraic integer. Every algebraic conjugate of this number is the average of $d$ roots of unity and has modulus at most one. If it is nonzero, its algebraic norm is a nonzero integer of absolute value at least one; since every factor has modulus at most one, all must have modulus one. In particular $|\chi (g)|=d$. Equality in the triangle inequality for the unit-modulus eigenvalues implies that $\rho (g)$ is scalar. Thus if $(m,d)=1$, either $\chi (g)=0$ or $\rho (g)$ is scalar.

Suppose a group of order $p^a{q}^b$ were nonabelian simple, with both primes present. Choose a nonidentity $g$ in the center of a Sylow $p$-subgroup. Its centralizer contains that Sylow subgroup, so its class size is a power of $q$. Every nontrivial irreducible representation is faithful by simplicity. If it sent $g$ to a scalar, faithfulness would make $g$ central in the group, impossible in a nonabelian simple group. The ingredient above therefore gives $\chi (g)=0$ for every nontrivial character with degree coprime to $q$. Evaluating the regular character at $g\ne 1$ givesThe right side is an algebraic integer, but $1/q$ is not, a contradiction. A group of prime-power order cannot be nonabelian simple either, by its nontrivial center. Induct on the order: every nonsimple group has a proper nontrivial normal subgroup, and that subgroup and the quotient have smaller orders with at most these two prime divisors. By induction both are soluble; their derived-series extensions make the original group soluble. Simple abelian groups have prime order and start the induction. This proves Burnside's theorem.

For the final divisibility, let $|G|=n$ be odd and let $k$ be its number of conjugacy classes. All irreducible degrees are odd by the divisibility just proved. We use the standard Frobenius-Schur indicator theorem: $\nu (\chi )=n^{-1}{\sum }_g\chi (g^2)$ is zero precisely for an irreducible character not equal to its conjugate, and is $\pm 1$ otherwise. Squaring is a bijection on an odd-order group: for each $g$, its unique square root is $g^{(n+1)/2}$, since every element order divides $n$. For every nontrivial irreducible character, orthogonality to the trivial character consequently gives $\nu (\chi )=n^{-1}{\sum }_g\chi (g)=0$. The nontrivial characters therefore occur in distinct conjugate pairs of equal odd degree. Since an odd square is one modulo eight,is a sum of pairs $2(d^2-1)$, each divisible by sixteen; the trivial character contributes zero. Hence

The continued fraction starts $\sqrt{29}=[5;2,\dots ]$, since $1/(\sqrt{29}-5)=(\sqrt{29}+5)/4$ has integer part $2$. Its next continued fraction convergent is $5+1/2=11/2$. Direct substitution gives

Put $\alpha =\sqrt{N}$. Every positive solution satisfiesAfter reducing $x/y=p/q$, we still have $|\alpha -p/q|<1/(2q^2)$. Here is the continued fraction convergent criterion with its proof. If $p/q$ is reduced and obeys this inequality, it is a strict best approximation of the second kind: for any different $r/s$ with $0<s\le q$, the assumption $|s\alpha -r|\le |q\alpha -p|$ would givea contradiction. Choose consecutive continued fraction convergents $p_j/q_j,p_{j+1}/q_{j+1}$ with $q_j\le q<q_{j+1}$. Their determinant is $\pm 1$, their errors $e_j=q_j\alpha -p_j$ alternate in sign, and every integer pair $(r,s)$ is uniquely $a(p_j,q_j)+b(p_{j+1},q_{j+1})$. For $0<s<q_{j+1}$, either $b=0$, or $a,b$ have opposite signs: positive $a,b$ would make $s\ge q_{j+1}$, negative $a,b$ make $s<0$, and $a=0$ is impossible. Opposite signs make $a{e}_j$ and $b{e}_{j+1}$ have the same sign, so $|s\alpha -r|\ge |e_j|$. If $b=0$, reduction gives the $j$th convergent itself. Thus a strict best approximation must be a convergent. The determinant and alternating-error facts follow immediately from the recurrence $p_j=a_j{p}_{j-1}+p_{j-2}$, $q_j=a_j{q}_{j-1}+q_{j-2}$ and the positive continued-fraction tail formula. Therefore the reduced ratio $x/y$ is a convergent of $\sqrt{N}$. Without assuming $\gcd (x,y)=1$, the unreduced pair may be a common multiple of the convergent's numerator and denominator; for example $(10,2)$ for $N=24,M=4$ reduces to $5/1$.

Factor $n={\prod }_j{q}_j^{e_j}$. Since it is not a square, one exponent, say $e_1$, is odd. Choose a nonzero quadratic nonresidue $a$ modulo $q_1$; one exists because the squaring map on the nonzero residues is two-to-one and hence has only $(q_1-1)/2$ images. The Chinese remainder theorem supplies a positive odd integer $m>1$ satisfyingThen $\gcd (m,n)=1$ and $(m/n)=(-1{)}^{e_1}=-1$. The Jacobi reciprocity law proved in part (i), together with $m\equiv 1(\mathrm{mod}4)$, gives $(n/m)=-1$. Factoring $m={\prod }_{\ell }{p}_{\ell }^{r_{\ell }}$ givesAll $p_{\ell }$ are odd and none divides $n$. At least one factor must be negative, yielding an odd prime number $\boxed{p\text{ with }(n/p)=-1}$. No theorem about primes in arithmetic progressions is needed.

For odd coprime positive integers $a={\prod }_i{p}_i^{e_i}$ and $b={\prod }_j{q}_j^{f_j}$, define the Jacobi symbol by multiplying Legendre symbols over the prime factorization of the denominator. Multiplicativity in the numerator givesBy quadratic reciprocity for the Legendre symbol, this is $(-1{)}^{UV}$, where $U={\sum }_i{e}_i(p_i-1)/2$ and $V={\sum }_j{f}_j(q_j-1)/2$. For odd $x,y$, $(xy-1)/2\equiv (x-1)/2+(y-1)/2(\mathrm{mod}2)$, since $(x-1)(y-1)/2$ is even. Thus $U\equiv (a-1)/2$ and $V\equiv (b-1)/2(\mathrm{mod}2)$. We obtainIf $a,b$ are not coprime, both symbols are zero and the equivalent identity $(a/b)=(-1{)}^{(a-1)(b-1)/4}(b/a)$ still holds. The convention $(a/1)=1$ handles denominator one.

A Euclidean lattice in ${\mathbb{R}}^2$ is a discrete additive subgroup, equivalently the integer span of zero, one or two real-linearly independent vectors. Its rank is the number of these generators, or the dimension of its real span. Discreteness makes its intersection with any bounded set finite, so shortest nonzero vectors exist.

First $\Lambda \cap \mathbb{R}{w}_1=\mathbb{Z}{w}_1$. Otherwise an element $t{w}_1$ with noninteger $t$ could be reduced by its nearest integer multiple of $w_1$ to a nonzero vector of length at most $|w_1|/2$, contradicting minimality. Therefore $w_2\notin \mathbb{Z}{w}_1$ is not parallel to $w_1$.

Write any $v\in \Lambda$ as $v=a{w}_1+b{w}_2$ with real coefficients. Subtract nearest integer multiples to obtain $r=s{w}_1+t{w}_2\in \Lambda$, with $|s|,|t|\le 1/2$. If $t\ne 0$, it is not on the first axis, yetwith strict inequality because the independent vectors cannot achieve equality in the triangle inequality; if one coefficient vanishes the inequality is also strict. This contradicts minimality of $w_2$. If $t=0$ and $r\ne 0$, then $|r|\le |w_1|/2$, contradicting minimality of $w_1$. Thus $r=0$ and both original coefficients are integers. Hence $\boxed{\Lambda =\mathbb{Z}{w}_1+\mathbb{Z}{w}_2}$.

For $w_1=(1,0)$ and $w_2=(x,y)$, minimality implies $x^2+y^2\ge 1$ and $|w_2|\le |w_2\pm w_1|$, hence $|x|\le 1/2$. The exact region isThese conditions are sufficient: in the generated lattice, vectors with second coefficient $\pm 1$ have smallest length when the first coefficient is zero, allowing ties at $|x|=1/2$. A vector with second coefficient of magnitude at least two has length at least $2|y|>\sqrt{x^2+y^2}$, since $|y{|}^2\ge 3/4$ and $x^2\le 1/4$. Vectors on the first axis have length at least one. Thus the shaded region includes exactly all allowable choices, including ties on its boundary.

For a second lattice basis, write $v_1=a{w}_1+b{w}_2$, $v_2=c{w}_1+d{w}_2$ with integer coefficients, as just proved. Conversely each $w_i$ is an integer combination of the $v_j$. The change-of-basis matrix $\left(\begin{array}{cc}a& c\\ b& d\end{array}\right)$ and its inverse therefore both have integer entries. Their determinants are integers with product one, giving $\boxed{ad-bc=\pm 1}$. Thus lattice bases are related by a unimodular matrix.

For any positive integer $m$, put $N=(m+1)!$. Each of $N+2,N+3,\dots ,N+m+1$ is composite, since $N+j$ is divisible by $j$ and larger than $j$. Let $p$ be the largest prime number at most $N+1$, and let $q$ be the smallest prime number at least $N+m+2$. Such $q$ exists by part (i), and no prime lies strictly between $p$ and $q$. Therefore these are consecutive prime numbers withSince $m$ is arbitrary, gaps between consecutive prime numbers are unbounded.

Suppose the prime numbers were the finite list $p_1,\dots ,p_r$. The integer $N=p_1\cdots p_r+1>1$ has a prime factor, by repeatedly factoring any composite factor until a prime is reached. But division by any $p_j$ leaves remainder one, so that prime factor is absent from the list. This contradiction proves there are infinitely many prime numbers. The argument does not require $N$ itself to be prime.

Since $7\equiv 3(\mathrm{mod}4)$, the ring of integers is $\mathbb{Z}[\sqrt{7}]$. A unit $a+b\sqrt{7}$ has norm $a^2-7b^2=\pm 1$. Norm minus one is impossible: it would give $a^2\equiv -1(\mathrm{mod}7)$, whereas the squares modulo seven are $0,1,2,4$. The element $\epsilon =8+3\sqrt{7}$ has norm one and exceeds one.

Suppose a positive unit $u$ in the chosen real embedding satisfies $1<u<\epsilon$. Its conjugate is $1/u>0$, soThis expression is strictly increasing in $u$, and at $u=\epsilon$ it equals three. Thus the integer $b$ is one or two. But then $a^2=7b^2+1$ is eight or twenty-nine, neither a square. Therefore there is no positive unit strictly between one and $\epsilon$.

For any positive unit $u$, choose an integer $k$ such that $1\le u{\epsilon }^{-k}<\epsilon$. The remaining unit must be one, so $u={\epsilon }^k$. Multiplication by minus one handles negative units. Hencewhich proves that $8+3\sqrt{7}$ is fundamental, using no continued fractions.

The Dirichlet unit theorem states that for a number field with $r_1$ real embeddings and $r_2$ conjugate pairs of nonreal embeddings,where $\mu (K)$ is its finite cyclic group of roots of unity. Equivalently there exist $r_1+r_2-1$ multiplicatively independent fundamental units such that every unit is a unique product of a root of unity and integer powers of those units.

Embed the ring of integers into ${\mathbb{R}}^2$ by its two real embeddings. Its image is a full Euclidean lattice of some covolume $d>0$. Fix $C>d$ and consider the symmetric rectangle $|{\sigma }_1(\alpha )|\le T$, $|{\sigma }_2(\alpha )|\le C/T$. Its area is $4C>4d$, so the Minkowski convex body theorem gives a nonzero algebraic integer ${\alpha }_T$ in it. Its algebraic norm is a nonzero integer with $|N({\alpha }_T)|\le C$.

As $T\to \infty$, infinitely many distinct ${\alpha }_T$ must occur: a finite collection of nonzero elements has a positive minimum of $|{\sigma }_2(\alpha )|$, whereas here that coordinate tends to zero. The principal ideals $({\alpha }_T)$ have norm $|N({\alpha }_T)|\le C$. There are only finitely many ideals of bounded norm: they are subgroups of bounded index in a rank-two free abelian group, and integer Hermite normal forms give finitely many possibilities at each such index. Thus infinitely many of these elements generate one ideal. Ratios of two generators of the same ideal are units, because inclusion in both directions supplies inverse algebraic integers. Among infinitely many distinct generators choose two whose ratio is not $\pm 1$. This gives a non-trivial unit without assuming Dirichlet's theorem.

For an open cover $X=A\cup B$, the Mayer–Vietoris theorem gives the long exact sequenceThe same sequence holds for a union of simplicial subcomplexes. All homology groups here have integer coefficients.

An explicit triangulation of $X_q$ is as follows. Take vertices $b_0,b_1,b_2$ forming a target circle, a circle of $3q$ vertices $a_0,\dots ,a_{3q-1}$, and a cone vertex $c$. With subscripts on $a$ interpreted modulo $3q$ and on $b$ modulo three, include trianglesfor every $j$, together with all their faces. The first two types triangulate the mapping cylinder of the degree-$q$ covering $a_j\mapsto b_j$; the last type fills the inner circle by a disc. A filled disc with an attached annular collar is still a disc, and identifying the outer collar boundary by this covering gives exactly the source quotient. Distinct inner vertices ensure this is a genuine simplicial complex, not just a one-cell presentation.

Let $A$ be the mapping cylinder and $B$ the coned disc. Then $A$ retracts to the target circle, $B$ is contractible and $A\cap B$ is the inner circle. Its inclusion into $A$ induces multiplication by $q$ on $H_1$. The exact sequence therefore reduces toConnectedness and the absence of higher-dimensional simplices giveThis is a two-dimensional Moore space with torsion in degree one.

The suspension of a connected complex is the union of two cones whose intersection retracts to the original complex. Reduced Mayer-Vietoris givesIn particular its $H_1$ vanishes. For the wedge of two connected polyhedra, choose neighborhoods retracting onto the two summands with contractible intersection at the wedge point. ThenDecompose each prescribed $G_i$ into cyclic summands. Realize each infinite cyclic summand in degree $i$ by $S^i$, and each finite nontrivial summand $\mathbb{Z}/q$ by $S^{i-1}{X}_q$, meaning $i-1$ successive suspensions. Take their finite wedge, or a point if there are no summands. The suspension formula shifts the torsion to degree $i$ and creates no other positive-degree homology, while the wedge formula adds summands. Thus the resulting connected polyhedron satisfies $\boxed{H_0(X)=\mathbb{Z},H_i(X)=G_i(1\le i\le n),H_i(X)=0(i>n)}$. The finite triangulations above, their simplicial suspensions and wedges provide an actual polyhedron.

Normalize the nonvanishing loop to $\gamma (t)/|\gamma (t)|$. A continuous argument lift is a continuous function $\theta :[0,1]\to \mathbb{R}$ such that $\gamma (t)/|\gamma (t)|=e^{i\theta (t)}$. Such a lift exists on an interval; any two differ by a constant integer multiple of $2\pi$. The winding number isIts value is independent of the lift. This definition applies to continuous loops without assuming a differentiable contour.

The homotopy invariance of winding number states: if $H:[0,1{]}^2\to \mathbb{C}\setminus \{0\}$ is continuous and $H(s,0)=H(s,1)$ for every $s$, then $w(H(s,\cdot );0)$ is independent of $s$. Neither the loops nor their moving basepoints may pass through zero. One may justify invariance by uniformly subdividing the homotopy into nearby loops whose normalized values have a continuous argument difference of magnitude less than $\pi$; that argument difference has equal endpoint values, so their winding numbers agree.

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.

Fermat's little theorem says that for a prime $p$ and $p\nmid a$, $a^{p-1}\equiv 1(\mathrm{mod}p)$; equivalently $a^p\equiv a(\mathrm{mod}p)$ for every integer $a$. The Wilson theorem says $(p-1)!\equiv -1(\mathrm{mod}p)$ for a prime $p$ (and, conversely, this congruence characterizes primes among integers greater than one).

For $p=2$, $x=1$ is a square root of minus one modulo a prime. If $p$ is odd and $x^2\equiv -1$, Fermat's little theorem givesso $(p-1)/2$ is even and $p\equiv 1(\mathrm{mod}4)$. Conversely, put $h=(p-1)/2$. Pairing $j$ with $p-j$ in the factorial gives $(p-1)!\equiv (-1{)}^h(h!{)}^2$. For $p\equiv 1(\mathrm{mod}4)$, $h$ is even, so the Wilson theorem yields $(h!{)}^2\equiv -1$. Thusand in the latter case $x=h!$ supplies a solution.

For the multiplicative order assertion, divide $k$ by $d$: $k=qd+r$, $0\le r<d$. Since $x^d\equiv 1$ and $x^k\equiv 1$, it follows that $x^r\equiv 1$. Minimality of the positive order excludes $0<r<d$, hence $r=0$ andIn particular $d\mid p-1$ by Fermat's little theorem. Negative $k$, if included, are handled by the same division using the modular inverse of $x$.

A Fermat number in the paper has $n\ge 1$. If a prime $p$ divides $F_n=2^{2^n}+1$, it is odd and $2^{2^n}\equiv -1(\mathrm{mod}p)$. Squaring gives $2^{2^{n+1}}\equiv 1$, so the order $d$ divides $2^{n+1}$. It does not divide $2^n$, since $-1\ne 1$ modulo an odd prime. Every divisor of $2^{n+1}$ is a power of two, so the only possibility isIf two different Fermat numbers shared a prime factor, the same element $2$ modulo that prime would have two different orders. This is impossible, proving pairwise coprimality. Also $2^{n+1}\mid p-1$, so for $n\ge 1$ every such prime is $1$ modulo $4$. No prime $3$ modulo $4$ can occur.

A prime $1$ modulo $4$ need not occur: take $p=13$. It is prime, $2^6=64\equiv -1(\mathrm{mod}13)$, and $2^4\equiv 3\ne 1$. Since the order divides $12$, the first congruence excludes every divisor of $6$ and the second excludes $4$; hence the order is $12$. This is not a power of two, so $13$ is not a prime divisor of a Fermat number. The index restriction matters: the conventional extra number $F_0=3$ is outside the paper's positive-$n$ family.

For $P(x)=x^3+4x-7$, the derivative $P^{\prime }(x)=3x^2+4$ is positive everywhere, so the mean value theorem makes $P$ strictly increasing. Since a polynomial is a continuous function, the intermediate value theorem and the values $P(1)=-2$, $P(2)=9$ locate its unique real root in $(1,2)$. By the rational root theorem, a rational root of a monic integer polynomial must be an integer. There is no integer in $(1,2)$, so the unique real root is an irrational number. The denominator part of that theorem also follows directly: if $a/b$ in lowest terms were a root, $a^3+4a{b}^2-7b^3=0$ would force $b\mid a^3$, hence $b=1$.

The exponential function series gives Euler's number $e={\sum }_{k=0}^{\infty }1/k!$. Suppose $e=a/b$ with integers $a,b$ and $b>0$. Choose $n\ge \max (b,2)$. Since $b$ divides $n!$, the numberis an integer. But its positive tail satisfiesThe inequality is strict because the factors after the first exceed $n+1$ when $j\ge 2$. No integer lies strictly between zero and one. This proves the irrationality of e:

If ${\log }_{2}3=a/b$ were a rational number, choose positive integers $a,b$ because ${\log }_{2}3>0$. Exponentiation gives $2^a=3^b$, but the left side is even and the right side is odd. ThusThis is the basic irrational logarithm criterion: a rational logarithm would force positive integer powers of its base and argument to coincide.