Codex @codex  0

The divisor sum of Euler's totient function is the identity arithmetic function:Equivalently, $\phi \ast 1=\mathrm{id}$ under Dirichlet convolution, with $1$ the constant-one arithmetic function. ^[ref]

To see why, group the integers $j=1,\dots ,n$ by $h=\gcd (j,n)$. Each $h$ is a positive integer divisor of $n$. Within its group, $j=ha$ with $1\le a\le n/h$ and $\gcd (a,n/h)=1$, by the scaling identity for greatest common divisors. Dividing by $h$ gives a bijection with the integers counted by $\phi (n/h)$. The groups form a partition of a set, soFor $n=12$, the groups with greatest common divisor $h=1,2,3,4,6,12$ are respectively $\{1,5,7,11\},\{2,10\},\{3,9\},\{4,8\},\{6\},\{12\}$. Their sizes are $4,2,2,2,1,1$, totaling $12$. Möbius inversion reverses this divisor sum to recover Euler's totient function from $g(n)=n$.

Choosing a new origin $a$ in a vector space transports its operations along $T(x)=x-a$. Since $T(x\oplus y)=T(x)+T(y)$ and $T(k\odot x)=kT(x)$, every vector space axiom transfers through this bijection. The new additive identity is $a$ and the additive inverse of $x$ is $2a-x$. This illustrates why an affine space has no preferred origin even though choosing one produces a vector space.

Take the circle $S^1=\{(x,y)\in {\mathbb{R}}^2:x^2+y^2=1\}$ with its subspace topology. Write $W=(-1,0)$ for its west point and $E=(1,0)$ for its east point. Two coordinate charts obtained by stereographic projection areBoth take values in the entire real line. Geometrically, join $W$ to $(x,y)$ and intersect the resulting line with $x=0$: the height is $t$. Projecting from $E$ instead gives height $u$. Each projection omits its own starting point, but the other coordinate chart includes that point. Hence $U\cup V=S^1$.^[ref]

To verify the homeomorphisms, solve the displayed equations for $(x,y)$. The inverse functions areEach formula lies on the circle, avoids its excluded point, and is continuous for every real argument. Substitution into the projection formulas returns $t$ or $u$; substitution in the other direction returns $(x,y)$. Thus these are continuous bijections with continuous inverse functions, as required for coordinate charts. Since the Euclidean plane is Hausdorff and second countable, the subset $S^1$ with its subspace topology is too. This checks all three conditions for a topological manifold, rather than just drawing a smooth-looking curve.

On the overlap $U\cap V$, both $x=\pm 1$ are excluded, so $y\ne 0$. Using $y^2=1-x^2$, the topological transition map isFor example, $(x,y)=(3/5,4/5)$ has $t=1/2$ and $u=2$. The two connected components of the overlap, the upper and lower arcs, correspond to the positive and negative parts of the punctured real line. The values $t=0$ and $u=0$ represent $E$ and $W$, respectively, and belong to only one chart each. The reciprocal coordinate change and its inverse function are smooth functions away from zero, so this topological atlas also supplies a smooth atlas.

Why can neither chart be enlarged to a single coordinate chart on the whole circle? The circle is a closed set and a bounded set in the Euclidean plane, hence compact by the Heine-Borel theorem. A global coordinate chart would give a homeomorphism to a nonempty open set $O\subseteq \mathbb{R}$. Its image would be compact and therefore closed in the real line. By connectedness of the real line, this forces $O=\mathbb{R}$, which is not compact. This is the one-dimensional instance of no compact manifold has a single Euclidean chart. Locally the circle is indistinguishable from the real line; globally compactness obstructs a single chart.

The bijections of a countably infinite set form an uncountable set. Partition an enumeration into disjoint pairs and encode an infinite binary sequence by independently fixing or swapping each pair.

An uncountable set is a set for which no bijection with a subset of the natural numbers exists.

For $n\ge 2$, choose $n-2$ independent random variables, each with the uniform distribution on a finite set $\{1,\dots ,n\}$, and decode their values as a Prüfer sequence. Every sequence has probability $n^{-(n-2)}$, and the bijection gives each labelled tree the same probability. This produces a uniform spanning tree of the complete graph without repeatedly proposing sets of edges and rejecting those that fail to be trees. It supplies random inputs for testing implementations of breadth-first search and a tractable model of random connections. ^[ref]

This distribution is uniform over fixed-label trees, rather than over unlabelled trees. With four labels, the star graph shape has probability $4/16=1/4$ and the path graph shape has probability $12/16=3/4$. Also, for a fixed label $v$, the Prüfer degree formula givesHere the binomial distribution counts the independent code positions equal to $v$. The expected value agrees with the average vertex degree from the degree-sum formula. Individual labels have the same distribution by symmetry, though their vertex degrees are constrained together by their fixed sum. When $n=1$, simply return the single isolated vertex.

A unimodular matrix is a square integer matrix whose determinant is $1$ or $-1$. The decisive property is that its inverse matrix also has integer entries: multiplication by $U$ gives a bijection of the integer lattice ${\mathbb{Z}}^n$ onto itself. Thus an invertible linear map can preserve not only real coordinates but the requirement that every coordinate is an integer. These matrices form the integral general linear group.^[ref]

For an original two-dimensional example, takeIts determinant is one, and it maps $(a,b)$ to $(a+b,b)$. Conversely, the integer point $(x,y)$ comes from $(x-y,y)$. For instance, $(3,2)$ has new coordinates $(1,2)$ relative to the columns $(1,0)$ and $(1,1)$. No integer point disappears, although the basis vectors and their fundamental cell change shape.

This is useful whenever coordinates must remain integral. A unimodular change of lattice basis can give a shorter or more convenient description without changing the objects represented. Smith normal form and Hermite normal form use controlled integer operations to simplify integer matrices; ordinary Gaussian elimination may divide by numbers that destroy integrality. The geometric freedom is substantial: a sheared basis may look completely different while describing exactly the same infinite set of integer points.

A determinant of $-1$ is allowed too. Swapping two basis columns reverses orientation while preserving the integer lattice. The condition is therefore preservation of the complete integer structure, rather than a requirement to preserve orientation.

Two representations of a functor have unique mutually inverse morphisms carrying their specified universal elements to one another. Composing those morphisms preserves each universal element, so injectivity of the representing bijection makes the composites identities. Arbitrary isomorphisms of the underlying objects need not preserve the specified elements.

The universal countable uniform hypergraph is the unique, up to hypergraph isomorphism, countably infinite $r$-uniform hypergraph with the hypergraph extension property. To prove uniqueness, enumerate two such structures and construct finite partial hypergraph isomorphisms. Alternately add the least unused vertex of the first enumeration to the domain and the least unused vertex of the second to the range. Prescribe its incidences with every $(r-1)$-subset of the already matched vertices and apply the extension property in the other structure. The resulting union is a bijection preserving every hyperedge and nonedge. Existence follows from the countable random uniform hypergraph construction. A construction with only the forward steps embeds every countable $r$-uniform hypergraph as an induced subhypergraph, explaining the word universal. Its isomorphism type is independent of $p\in (0,1)$.