Trial-division divisor counting Created 2026-10-25 Updated 2026-11-05
Factor a positive integer while multiplying the exponent-plus-one contributions to its divisor count. After removing all prime factors below the current trial factor, a trial factor that divides the remainder must itself be prime. Remove its full power and advance. Once the trial factor's square exceeds the remainder, any remainder greater than one is prime and contributes a factor two. The invariant separates the original integer into removed prime powers and the remaining coprime factor; no factor array is necessary.
Truncated Perron formula Created 2026-09-24 Updated 2026-11-05
Suppose the Dirichlet series converges absolutely at a fixed real . For and , put
Then
As in Perron's formula, the prime denotes half weight at an integer endpoint. If , interpret the minimum as ; the sharper endpoint kernel error is .
To prove the bound, interchange the absolutely convergent coefficient sum with the finite integral and apply the truncated Perron kernel estimate term by term. The logarithmic denominator explains why coefficients near require separate control: truncating the contour cannot instantly distinguish the two sides of the endpoint. This estimate is a starting point for explicit Prime number theorem error bounds.
Truncated power function Created 2026-10-07 Updated 2026-11-05
For integer , the truncated power is zero for and equals for . It is globally and its th derivative has a jump at . Order zero is the step-function convention . Knot divided differences of these functions produce B-splines.
Truncation toward zero 2026-10-14
Truncation toward zero removes the fractional magnitude of a real number, giving the integer obtained by applying the floor function to its absolute value and restoring the original sign; a magnitude below one gives zero. More precisely,
The result is zero for . For example, and , whereas . Python's math.trunc uses this towards-zero convention, so replacing it by math.floor changes calculations with negative noninteger inputs. [ref].
Figure 1.
Truncation toward zero is symmetric in sign, while the fractional part defined by the floor function is always nonnegative
. Left: exact integer endpoint values distinguish the two sign-dependent truncation rules; a whole neighborhood of zero maps to zero. Right: takes the sign of a noninteger input, while lies in on both sides of zero. Open endpoints show excluded limiting values. Details.
For every real number ,
The discarded difference has the sign of when is noninteger. In contrast, the fractional part is always in . At , these two differences are and . Thus specifying a signed fractional remainder requires specifying which integer-valued operation is used.
Unlike the floor function and ceiling function, truncation toward zero need not commute with adding an integer. At and , , whereas . This matters if negative coordinates are assigned to equal-width bins by converting a quotient to an integer: belongs to the bin under the floor function, but truncation gives zero. The appropriate operation follows from the declared bin intervals.
Truncation toward zero is a nondecreasing function with a discontinuity of a function at each nonzero integer. It has no discontinuity of a function at zero, because it is identically zero on . Its agreement with the floor function on the positive side and the ceiling function on the negative side explains the different closed endpoints in the diagram.
Turán graph Created 2026-09-29 Updated 2026-10-14
The Turán graph is a complete multipartite graph with independent sets of sizes differing by at most one, with every cross edge present. Empty parts are allowed when .[ref]
Figure 1.
The Turán graph has three independent sets of sizes , giving edges and no four-vertex clique
. Details.
In this example, the independent sets are , and . Count the edges between each pair of parts:
Any four vertices put at least two in the same independent set, by the pigeonhole principle, so they cannot form . Conversely, every choice of one vertex from each part is a triangle in a graph, giving triangles in a graph. Clique exclusion here does not mean triangle-free.
For the exact count, Euclidean division writes , where uses the floor function and is the remainder, with . There are parts of size and of size . For any part sizes summing to , count cross edges by expanding the square:
Therefore
For , we have , giving . The Quadratic Turan edge bound gives instead: the exact correction subtracts .
Balancing is an integer optimization with a simple reason. If two part sizes satisfy , moving one vertex from the larger part to the smaller decreases their contribution to the sum of squares by
so it increases the edge count by . For eight vertices, parts give edges; moving one vertex produces and edges. The most symmetric permitted sizes pack the most cross edges, which explains the sharp construction in Turán's theorem.
Turán's theorem Created 2026-10-14 Updated 2026-10-14
How many edges can we retain while excluding a prescribed clique? For integers and , every simple graph on vertices containing no complete subgraph satisfies
Equality holds exactly for the Turán graph , up to graph isomorphism. Thus the extremal number is .[ref]
For example, has independent sets of sizes and edges, as counted in Turán graph. It contains triangles in a graph, but no four-vertex clique. Consequently any simple graph on eight vertices with edges contains , while edges alone do not force one. Excluding larger cliques permits denser graphs; Mantel theorem is precisely the first nontrivial case.
A short proof outline uses Zykov symmetrization. If an extremizer is not a complete multipartite graph, it has vertices with absent and present. If either or has larger vertex degree than , clone that vertex in place of . Otherwise replace both by nonadjacent clones of , gaining edges. Both contradict extremality; balancing the resulting at most parts gives .[ref]
The vertex cloning in a graph step preserves clique exclusion because any clique using a clone can substitute its original vertex; nonadjacent clones cannot occur together in a clique. At most parts can be nonempty, since selecting one vertex from each gives a clique. If fewer than parts are nonempty and one has at least two vertices, splitting it creates more edges, so it cannot be extremal. For the bound is zero. For , the Turán graph is , and the bound is the total possible edges.
Two distinguished classes of discriminant minus eight q Created 2026-09-24 Updated 2026-11-05
For an odd prime , the forms
are primitive binary quadratic forms of discriminant of a binary quadratic form . Their diagonal polynomial coefficients are positive, so they are positive definite, and makes both satisfy the reduced positive definite binary quadratic form inequalities.
Their proper equivalence classes are distinct. The first represents one at , but the second has minimum positive value two: if , , while and give at least two. Since proper equivalence preserves represented integers, the two forms cannot be equivalent.
Thus . If the class number of a negative discriminant is exactly two, these are all its primitive proper classes. That completeness hypothesis is the reason a local square test can select one specific form in prime representation when h of minus eight q equals two.
Two-generator Frobenius theorem Created 2026-10-20 Updated 2026-11-05
For coprime integers , the Frobenius number is .
First, cannot equal with nonnegative integers . Reducing modulo gives ; coprimality forces to be a positive multiple of . Hence , a contradiction.
Now take any integer . Multiplication by permutes the residue classes modulo , so choose with . The difference is a multiple of and satisfies . It is therefore nonnegative, giving and . This proves both the largest gap and representability of every greater integer.
For , , the two-isogeny formula companion is . With the positive-sign standard isogenies, the two preimages of under the dual are and . The two-torsion square-class homomorphism on detects membership in the image of the forward isogeny of elliptic curves by the class of . Thus either preimage lifts precisely when its first coordinate is a rational square. Their being integers turns rational squareness into integer squareness.
Type class Created 2026-09-28 Updated 2026-10-25
The type class contains all length- strings with empirical distribution . Each must be a nonnegative integer and the counts must sum to ; otherwise the class is empty. Distinct type classes partition : every string belongs to exactly one class.
For four binary symbols there are five type classes, indexed by the number of ones. Their cardinalities are , which sum to . The balanced class contains exactly . These are six different strings, not six different empirical distributions.
Figure 1.
Sixteen binary strings form five type classes
. An exact enumeration of all four-symbol strings. Each column fixes the number of ones; the central column has six orderings of the same empirical distribution. Details.
Typesetting badness 2026-11-05
Typesetting badness scores the spacing strain needed to fit a line. For ordinary finite stretch or permitted finite shrink, a useful smooth guide is
where is the line adjustment ratio. Doubling the required ratio multiplies this guide by eight, so it strongly penalizes large adjustments. The convex function on nonnegative ratios rewards more evenly distributed spacing strain.
TeX computes an integer approximation with saturation rather than evaluating that real-valued expression exactly. With stretch coefficient in the routine's internal units, excess widths give ratios and routine outputs . In particular, the first differs from the smooth guide value 12.5.[ref]
Figure 1.
Cubic spacing cost and integer typesetting badness
. Original calculation comparing the smooth guide with TeX's badness routine at chosen finite stretch coefficients. The right panel enlarges the integer steps near r=0.5. All plotted ratios describe stretching. Details.
The sentinel 10000 represents saturated badness in the routine. Excessive shrinking is tested separately in paragraph breaking; higher-order stretch has its own treatment. A paragraph's typesetting demerits also include typesetting penalties and possible neighbour-dependent charges, so choosing solely by badness can miss the best layout.
Type system 2026-10-13
A type system assigns types to program expressions and supplies rules governing their use. A type constrains permitted operations: in our teaching programming language, int admits integer addition, bool supplies true and false for conditions, and a function type specifies an argument type and a result type. Storage as bits alone does not explain these distinctions; the type system determines whether an expression can serve as an argument, a condition or an operand.
A typing judgment says that expression has type under the assumptions in the typing context . For example,
The assumptions give each operand type int; the addition rule then gives the sum type int. Changing to type bool prevents this derivation. Our teaching programming language has distinct int and bool types and no implicit conversions between them.
The conditional rule requires a Boolean condition and the same type for both branches:
Thus if true then 1 else 2 has type int, while if true then 1 else false is rejected: its branches would require and simultaneously. Even a branch that will not execute is checked by this rule. This is a rule of this particular type system; a different programming language can choose different rules. [ref]
The useful feature is compositional reasoning: after checking the parts, a rule explains how to check the whole. The function type diagram shows this for a call. Type inference can discover the required types automatically, and type variables let one express relationships that recur across many concrete types. The result is both a practical early error detector and a small, readable derivation explaining why an expression fits its intended use.
The guarantee depends on the rules and execution model. Type safety can exclude specified failures such as adding a Boolean or calling an integer as a function. It does not by itself establish every desired runtime property or guarantee that execution terminates. A type system that permits unrestricted recursion can accept a computation that runs forever; exception handling also needs its own account of permitted outcomes.
U(1) charge Created 2026-10-25 Updated 2026-11-05
For the circle group parameterized by with period , a one-dimensional representation acts as , and its integer label is its charge. Periodicity forces . A tensor product representation adds U(1) charges, a dual representation negates them, and restriction to the finite cyclic group generated by retains only . Integer normalization must be fixed before discussing a largest finite subgroup left by a condensate.
U(1) connection Created 2026-10-14 Updated 2026-11-05
A U(1) connection is a principal connection on a principal bundle with circle group . In a local trivialization it has a real one-form potential , with convention under a gauge transformation . Its curvature form is globally defined, although need not be a global one-form.
For a closed curve , choose a local trivialization of the pulled-back circle bundle along . In unit-charge normalization the holonomy is . Changing that local trivialization changes the integral by times an integer, leaving the exponential unchanged. When computing with several local potentials, transition phases must be included at chart changes.
On the trivial circle bundle over a circle, has but holonomy . Thus zero curvature form need not imply trivial holonomy. On any closed oriented surface, the integral is the integral First Chern class, relating the curvature form to the topology of the circle bundle.
Ulam sequence 2026-10-20
Starting with two distinct positive integers , repeatedly append the smallest integer larger than the previous term that is expressible in exactly one way as the sum of two distinct earlier terms. Requiring distinct summands and counting unordered pairs are both essential parts of the definition.
Ultrametric space Created 2026-09-24 Updated 2026-11-05
An ultrametric space is a metric space whose metric satisfies the ultrametric inequality. The rational numbers with , and their P-adic number completion, are examples. Their geometry organizes points into nested clusters rather than measuring separation along a number line.
For integers and , the definition of the p-adic valuation gives
Thus a closed ball of radius in the integers is a congruence class modulo . In the p-adic integers the same closed ball is . More shared low-order digits mean a smaller p-adic absolute value of the difference.
Figure 1.
The integers from zero to fifteen form nested congruence classes modulo powers of two in the 2-adic absolute value
. Details.
The binary tree first splits the sixteen integers into even and odd congruence classes, then refines modulo , , and . Each node fixes one more low-order digit. The leaves and share the class modulo , then separate modulo , so their distance is exactly . The leaves are deliberately ordered by their low-order digits; horizontal spacing and edge lengths are layout choices, not the metric. The singleton leaves describe this finite sample; a congruence class modulo in all p-adic integers remains infinite.
The ultrametric inequality also explains the unusual behavior of balls. Every point of an open ball can serve as its center: if , then if and only if . Two open balls that intersect are nested, since a point of their intersection serves as a common center and their radii can be compared. The same nesting rule holds for closed balls and for a pair consisting of one open ball and one closed ball.
Every open ball is a clopen set. For a point outside , the open ball stays outside : if , the ultrametric inequality forces . Hence the complement is an open set. Also every closed ball of positive radius is an open set, because lies in the closed ball of radius around whenever . A radius-zero closed ball is a singleton and need not be an open set. Distinct points can therefore be separated by a clopen set, proving that an ultrametric space is totally disconnected. These ball properties turn distance thresholds into a hierarchy of compatible clusters. [ref]
Unary numeral system 2026-10-31
Represent a nonnegative integer by , using delimiters when several quantities are encoded. The length is , rather than the length of a binary numeral system representation. Despite the parent category for numerical notation, this is not a positional base-one place-value system.
Unary operation 2026-11-05
A unary operation on a set is a function taking one input and returning an element of the same set. Examples include the additive inverse on the integers and inversion in a group.
Unary operations can be composed and iterated. The identity function and all maps form a monoid under function composition. For negation, ; for a successor map on the nonnegative integers, iteration instead produces an unbounded sequence.
An operation's identities are extra data. Being unary alone says nothing about injectivity, surjectivity or whether repeated application returns to the starting element.
Unbounded element orders in imaginary quadratic ideal class groups Created 2026-10-25 Updated 2026-10-31
For every positive integer , some imaginary quadratic field has an ideal class of order of a group element greater than . Specifically, take a prime number with . In , the Dedekind factorization theorem gives , with distinct prime ideals and of ideal norm five. If for , the field norm equation forces . Then is even and , contradicting unique factorization of ideals in a number field. Thus has order of a group element greater than . The existence of suitable follows from Dirichlet's theorem on arithmetic progressions.
Uniform convergence Created 2026-09-24 Updated 2026-10-14
A sequence of functions converges uniformly to , where is a metric space with metric , precisely when
For real numbers, use the absolute value . Compare the universal quantification and existential quantification:
The decisive change is whether can depend on . Uniform convergence implies pointwise convergence.[ref]
For functions taking values in real numbers on a nonempty domain of a function, the supremum error is , allowing . Then uniform convergence is equivalent to . The supremum need not be a maximum: pointwise strict bounds below only give , so use tolerance when proving this equivalence. This single error bound controls every possible input, including one chosen after seeing the index.
For and its pointwise limit on , the error is zero at one but approaches one as from below. Consequently
for every positive integer . This supremum is never attained: below one the error is , and at one it is zero. Deleting the endpoint leaves the same supremum error on . To disprove uniform convergence directly, choose : for any proposed , take and . The error equals , violating the strict tolerance. Thus a moving input defeats every proposed common threshold.
On the smaller interval , for a fixed , the pointwise limit is zero and
For and , the exact first successful common threshold is
The logarithm and floor function turn an infinite approximation statement into a finite stopping rule. At , fails tolerance , while succeeds. At and , the ratio is exactly three: is necessary because equality is insufficient. For , every error is zero. The domain of a function determines whether one threshold can certify every input.
Figure 1.
Supremum error and common thresholds distinguish uniform convergence from pointwise convergence
. Left: the error of remains one on and , but falls below from onward on . Right: the first successful threshold at a fixed input grows without bound near one. A common threshold covers all inputs at most . Both vertical axes use a logarithmic scale. Details.
For another explicit stopping rule, let on . Its uniform limit is zero and its supremum error is . For every , works, using the ceiling function. Unlike on , it controls even the endpoint.
The practical beauty of uniform convergence is that one quantitative bound can survive further operations: the uniform limit theorem preserves continuity, and uniform convergence preserves integrals on a compact interval controls accumulated error. Differentiation needs additional hypotheses, such as uniform derivative convergence with an anchored value. These results distinguish an approximation that looks accurate at selected inputs from one that justifies replacing a whole function in a calculation.