Radical ideal Created 2026-09-29 Updated 2026-11-05
An ideal is radical when for some positive integer implies . Over an algebraically closed field, the Hilbert Nullstellensatz identifies the vanishing ideal of with the radical .
Radical of an integer Created 2026-10-06 Updated 2026-10-20
The radical of an integer is the product of its distinct prime factors, each included exactly once. If the prime factorization is with distinct prime numbers and positive integer exponents , thenThus the radical of an integer remembers which prime factors occur and forgets their prime valuations. At , the empty product gives . The domain of a function here is the positive integers; zero is excluded. [ref]
https://pub.math.leidenuniv.nl/~evertsejh/dio12-ex4.pdf. Jan-Hendrik Evertse, Diophantine approximation, Homework IV, Exercise 20: definition of the integer radical
For example, has distinct prime factors , so . Similarly,using the prime factorizations , and . The prime omega function counts the retained prime factors, while the total number of prime factors counts their occurrences before repetitions are removed.
The radical of an integer is its largest squarefree divisor. Indeed, a squarefree divisor chooses at most one copy of each prime factor, so it divides ; the radical of an integer itself is a squarefree divisor. Consequently,The last statement follows because every nonzero prime valuation is then one. It includes , a squarefree integer. Applying the radical of an integer twice also changes nothing: .
The radical of an integer for : squarefree integers lie on the diagonal, and horizontal families share their prime support of an integer
. Details. For any positive integers , the exact product rule isTo prove it, a prime factor dividing just one input occurs once in the numerator and not in the denominator. A prime factor dividing both occurs twice in the numerator and once in the denominator, since it divides their greatest common divisor. Each prime factor of therefore remains exactly once. For coprime integers, the denominator is , proving the radical of an integer is a multiplicative function. It is not a completely multiplicative function: .
For a worked example with shared prime factors, take and . Their greatest common divisor is , and , soThis explains why prime support of an integer is useful: questions about the presence of prime factors can discard their multiplicities. For example, the squarefree divisors of are exactly the integer divisors of , namely . Also if and only if , because coprimality depends only on shared prime factors.
A further characterization uses mutual divisibility of powers: for positive integers ,If their prime supports of an integer agree, sufficiently large make all the required prime valuations large enough. Conversely, these two divisibility relations force each prime factor of either input to divide the other. For and , one can take and : and .
Radix 2026-10-14
The radix is the base of positional notation. In the ordinary integer-base case it is an integer , and successive place values differ by a factor of .
Radix sort key encoding 2026-10-18
An encoding for radix sort must make the intended total order of sort keys agree with the lexicographic order of its fixed-width numerical digit tuples. The positional notation for bounded nonnegative integers has this property. At the most significant differing position , a one-unit numerical digit difference contributes , while all lower positions together contribute at mostThis geometric series shows why lower numerical digits cannot reverse that comparison. Leading zero padding works here because it preserves place values and the represented integer.
For signed integers in a known integer interval , encode and choose with . This order-preserving function is also injective: exactly when . For , the four-bit encodings of are after adding eight. Restore the original signed sort keys when displaying the complete sorting records; the encoding need not replace their data. Sorting the unsigned values of raw two's complement bit patterns would put nonnegative integers before negative ones, so their representation alone is not this ordered encoding.
For variable-length strings, first specify the alphabet order and whether a proper prefix precedes its extensions. As an original construction, use , let every string have length at most three, encode as one and as two, and append zeros to width three. Zero is reserved for an end marker strictly below every real symbol. The strings encode as in radix three, which preserves their lexicographic order. A differing real symbol decides the comparison; at a prefix boundary, the shorter string's zero comes before the extension's one or two. Left padding would instead encode as and as , reversing . Padding raw bytes with zero also fails if zero is an allowed data symbol: distinct strings can then receive the same encoding. A reserved end marker and an explicit symbol ordering are essential; byte order alone does not establish a desired human text order.
Stable ties preserve lower digits; suitable encodings preserve the intended order
. Original counterexample above: reversing a tens tie destroys the units order and a later stable hundreds pass cannot repair it. Below: signed integer offsets and a reserved end marker for bounded strings produce increasing fixed-width encodings. All entries are exact constructed examples. Details. Radix sort suffix invariant 2026-10-18
After passes, , the array is in nondecreasing order of , the integer represented by its lowest numerical digits. Equivalently it is ordered by the tuple under lexicographic order, with the most significant processed numerical digit first. Among equal suffixes it retains the original order of the complete sorting records.
The loop invariant has a simple mathematical induction proof. Before any pass, for every sort key, so the original array satisfies it. Suppose it holds after passes. The next stable digit sort puts smaller groups first and preserves the existing order within each tie. Sincethe new array is ordered by . Equal new suffixes have equal current numerical digits and equal old suffixes, so their original order is also preserved. Every pass is a permutation of complete sorting records, establishing sorting permutation preservation. At termination , the assumption gives : the invariant becomes whole-key sortedness, together with stable sorting.
Ramanujan sum Created 2026-10-05 Updated 2026-11-05
The Ramanujan sum is . It is an integer: insert , sum the geometric series, and obtain . Here is the Möbius function. Such sums connect roots of unity with integer character of a representation values.
Ramification bound for a primitive pth root of unity Created 2026-10-07 Updated 2026-11-05
If a finite extension of the P-adic numbers contains a primitive th root of unity , the identity gives . The ratios of these factors reduce to the nonzero integers in the residue field. Thus an extension with has only roots of unity of order prime to .
Ramsey number 2026-10-14
For positive integers , the Ramsey number is the least integer such that every red-blue edge coloring of the complete graph contains either a red clique on vertices or a blue clique on vertices. The complete graph has all unordered pairs as edges; every edge gets exactly one color, with no requirement that incident edges have different colors. The definition and its graph interpretation appear in D. Yogeshwaran's Discrete Mathematics notes, section 5.3.
For example, asks how many vertices force a monochromatic triangle in a graph. Swapping colors gives . Also : either a red edge exists, or all edges are blue. On vertices, an all-blue coloring avoids both a red edge and a blue -clique. Under the convention that a one-vertex clique qualifies in either color, .
For , splitting the neighbors of one vertex by the colors of their incident edges givesIndeed, in a complete graph of the order on the right, at least neighbors are joined to that vertex by red edges, or at least are joined by blue edges. In the red case, the defining property of the smaller Ramsey number supplies either a blue -clique among the neighbors or a red -clique that extends by the chosen vertex; the blue case is symmetric. Starting from the one-vertex base cases, this recursively proves finite existence. The binomial upper bound for a Ramsey number packages the resulting estimate. [ref]
https://www.its.caltech.edu/~dconlon/RamseyLecture1.pdf. David Conlon's Graph Ramsey Theory notes, Lecture 1
present the neighbor argument and the sharp Ramsey number for triangles.Equivalently, every graph on at least vertices has an -clique or a -element independent set: color its edges red and the edges of its complement graph blue. This is the Ramsey theorem in graph theory. Larger monochromatic patterns have their own thresholds, such as a graph Ramsey number, matching Ramsey number or triangle-packing Ramsey number; these ask different questions from finding one clique.
Random number generation Created 2026-10-20 Updated 2026-11-05
Random number generation produces values intended to follow a prescribed probability distribution. A physical source uses a measured uncertain process; a pseudorandom number generator deterministically expands a seed into a reproducible sequence. For a uniform integer on , reducing a uniform -bit integer modulo is biased unless divides . Rejection sampling fixes this by accepting only values below before taking the remainder. For , accept : each residue then has exactly two preimages.
Random walk Created 2026-09-24 Updated 2026-10-14
A random walk is a stochastic process formed by accumulating random steps. In its additive form, the increments are independent and identically distributed random variables and the position after steps isThe steps can have more choices than and : they may be integers, real numbers, or vectors. A random walk on a graph instead describes steps between vertices along edges; its available moves can depend on the current vertex.
For example, starting at zero, the steps produce the positions . This is one sample path; other step sequences can have the same endpoint. A simple random walk on the integer line makes this distinction particularly tangible: repeated Bernoulli trials determine both a whole sample path and an endpoint with a binomial distribution. All positions below are dimensionless quantities measured in steps of length one, and counts discrete updates.
The model is useful because it separates an average tendency from accumulated fluctuations. A fair simple symmetric random walk has zero expected value at every time, yet its standard deviation grows: cancellation across many possible sample paths does not keep each walker near zero. The two figures below compare sample paths with exact endpoint probabilities. For the basic additive construction and its independent increments, see MIT, Stochastic Processes I, section 2.
Rank function of a partially ordered set Created 2026-10-20 Updated 2026-11-05
A rank function of a partially ordered set assigns an integer to each element so that whenever covers . In a finite ranked partially ordered set with minimal elements normalized to zero, is the length of every saturated chain from a minimal element to .
For subsets ordered by inclusion, cardinality is a rank function of a partially ordered set. For a chain , the normalized ranks are . An order with two saturated chains of unequal lengths between the same endpoints cannot have a rank function of a partially ordered set, because the required increments would assign conflicting values. This notion is distinct from the rank of a set in cumulative set theory.
Rankin–Selberg unfolding identity for a holomorphic Eisenstein series Created 2026-09-24 Updated 2026-11-05
Let and be level-one cusp forms of respective weights and , with an even integer greater than two. Use the unnormalized lattice Eisenstein sumwhose constant Fourier coefficient is . With the Petersson inner product linear in its first argument and the elementary Rankin–Selberg convolution , unfolding givesThe sum over primitive bottom rows unfolds the fundamental domain to the translation strip. Integration in the real direction keeps equal Fourier modes, and supplies the factor. If instead one uses the normalized Eisenstein series , the factor is absent. The stated level and normalization are essential to the displayed formula.
Rational arithmetic Created 2026-10-20 Updated 2026-11-05
Exact arithmetic on rational numbers represented by integer numerators and nonzero integer denominators. Common factors can be removed with the greatest common divisor. Exact rational arithmetic avoids rounding error when deciding equality or integrality.
Rational conjugation of finite-index modular subgroups Created 2026-10-05 Updated 2026-11-05
For any finite-index subgroup and rational positive-determinant , the intersection has finite index. Multiply by a positive rational scalar to obtain an integral matrix with positive integer determinant . For , is integral, so lies in . This intersection has finite index. Its further intersection with has relative index at most . No assumption that itself is a congruence subgroup is needed.
Rational homogeneity of an additive function 2026-10-18
For every additive function , every real number , and every rational number , one has . This is the scalar multiplication part of being a linear map over the rational numbers.
First gives , and gives . Repeated addition gives for each positive integer , and the negative case follows from the sign identity. If with and , thenNo continuity was used. In particular fixes , , and every other rational value, even for a discontinuous additive function.
Rational-linear map 2026-10-31
A rational-linear map is a linear map when its domain and codomain are regarded as vector spaces over the rational numbers. An additive map on a rational vector subspace of the real numbers is automatically rational-linear: integer homogeneity follows by repeated addition, and division by a positive integer gives rational homogeneity of an additive function.
Rational matrix Created 2026-10-05 Updated 2026-11-05
A rational matrix is a matrix whose entries are rational numbers. Multiplying by a common denominator produces an integer matrix and preserves its homogeneous solution set.
Rational number Created 2026-09-24 Updated 2026-11-05
A rational number is a quotient of integers with . The numerator can be negative or zero; the denominator can be chosen positive by transferring its sign to . For example, and .
Different fractions describe the same rational number exactly when cross multiplication gives . Dividing the entries by their greatest common divisor produces the unique reduced fraction with positive denominator, including for zero.
The rational numbers form a field: addition, subtraction, multiplication and division by a nonzero rational number remain rational. They are dense in the real line, by density of the rational numbers, although they do not fill it: the square root of two is an irrational number.
Rational polynomial content 2026-10-31
For a nonzero polynomial , choose a positive integer clearing its denominators and set , where the polynomial content of an integer-coefficient polynomial is the positive greatest common divisor of its coefficients. This is independent of : if , then , hence .
The integer-coefficient product formula from Gauss lemma for polynomials givesMoreover is an integer-coefficient primitive polynomial: if , then . For example,This normalization proves a useful divisibility descent. If is primitive, and for , then is an integer. Since , it follows that .
Rational representation of the general linear group Created 2026-10-07 Updated 2026-11-05
The matrix coefficients of a rational action belong to its coordinate ring . Multiplying the action by a sufficiently large determinant twist clears all determinant denominators and produces a polynomial representation. Irreducible rational actions are indexed by decreasing integer highest weights, with negative coordinates allowed.

