Sturmian word 2026-10-20
Subadditivity of the base-p digit sum Created 2026-09-28 Updated 2026-10-18
For nonnegative integers and an integer base ,In column addition, every arithmetic carry replaces units in one numeral digit by one unit in the next position and therefore decreases the base-p digit sum by . Count each outgoing carry separately, including each step of a chain. There is equality precisely when there are no carries. For prime number bases, Kummer's theorem turns this digit-sum deficit into a prime exponent.
Subgroup of an infinite cyclic group Created 2026-10-20 Updated 2026-11-05
For infinite, every subgroup is for a unique integer . This is the classification of subgroups of the additive group of integers transported through a group isomorphism. For the subgroup index is and the subgroup is again an infinite cyclic group; for it is trivial and has infinite subgroup index.
Subgroups generated by circle rotations 2026-10-14
Fix a real angle fraction , and repeatedly multiply by in the circle group. The generated cyclic subgroup is . Equivalently, the angle fractions are the fractional parts of , with one full turn identified with zero.
If is a rational number in lowest terms, with and coprime, then and no smaller positive power is . Hence is a finite cyclic group of order , consisting of equally spaced points. For , the successive angle fractions, starting at , areThe subgroup is finite, so it is a closed subgroup of the circle group; it is also a discrete subgroup. It is not an open subgroup, since every ambient neighbourhood of any of its points contains an arc, rather than only these seven points.
If is an irrational number, no nonzero integer satisfies , so the powers never repeat. The stronger statement is that is a dense set in the circle group: every nonempty open arc contains a power . Thus its closure is all of , while itself is a countable proper subgroup and is not a closed subgroup or a discrete subgroup. See irrational rotation and everywhere interval frequency under an irrational rotation for the corresponding motion and its long-term frequencies.
For , direct computation of the fractional parts of gives, to six decimal places,For example, and . These calculations specify exactly which points the diagram displays.
Seven repeating rational-rotation points and the first eight and sixty-four irrational-rotation points
. Labels give the power index ; the points are . The first panel uses , and the other two use . Each finite sample is only an illustration: a finite plot cannot establish that the infinite subgroup is a dense set. Reproduce the diagram with rational-versus-irrational-rotations.py. Details.This example shows why algebraic generation and closure must be distinguished: one irrational rotation generates a countable cyclic subgroup, yet its closure is the whole uncountable compact group.
Submask 2026-11-05
A submask of a bit mask is a bit mask whose set bits are all set in , equivalently . It represents a subset of the positions selected by . If has set bits, it has exactly submasks, including zero.
To enumerate them in descending order, start at , output , stop if , and otherwise replace it by . Subtracting one clears the lowest set bit and fills lower positions; masking removes positions unavailable in . For , the sequence is . Testing for zero before the next update is essential: under the common integer conventions, updating zero produces again and repeats the cycle.[ref]
Enumerating submasks of a bitmask in the CP-Algorithms documentation. Enumerating all submasks of a given mask
The number of outputs is exponential in the number of selected positions, even though each fixed-word update is inexpensive. Submodular rank function 2026-10-31
On a finite ground set , a submodular rank function is a normalised set function with , a monotone set function, and a submodular set function, such that for . Equivalently, require nonnegative integer values, monotonicity, submodularity and . The diminishing returns characterization of submodularity bounds each marginal by its singleton value. Thus .
These functions are precisely the rank functions of matroids. To see the converse direction, define . It contains the empty set. If , the unit marginal bounds give , so and heredity holds. For augmentation, suppose with . If every had zero marginal over , diminishing returns would keep each marginal zero as they are added successively. This would give , contradicting monotonicity. Some marginal is therefore one, giving an independent augmentation.
Finally any inclusion-maximal in this independence family has for every remaining . Successively adding them and using diminishing returns shows , so the resulting matroid really has rank . The forward direction is submodularity of matroid rank. These integer increment conditions distinguish matroid ranks from arbitrary real-valued submodular functions.
Submodule Created 2026-09-24 Updated 2026-11-05
A submodule of a left module is a nonempty subset closed under addition, additive inverses and the scalar action of the ring . Equivalently, it contains zero and is closed under expressions for and .
For example, is a submodule of the integer module , and its quotient module is . The empty subset is excluded: closure conditions stated without nonemptiness would hold vacuously there, but it is not an additive group.
Subnormal number 2026-10-14
A subnormal number is a nonzero representable value smaller in magnitude than the least positive normalized value . Keep the exponent scale fixed at and allow a zero leading digit: the positive values are for integers . This fills the gap toward zero with constant absolute spacing, at the cost of fewer significant digits. Goldberg describes this gradual approach to zero and why it matters for differences of small numbers.[ref]
https://docs.oracle.com/cd/E19957-01/806-3568/ncg_goldberg.html. Goldberg, 1991, §Denormalized Numbers
For binary64 the least positive normalized value is , and subnormal numbers are spaced by . With nearest rounding and gradual underflow enabled, an exact result with has absolute rounding error at most . A uniform relative bound by unit roundoff fails here: rounds to zero under the even-last-digit tie rule, giving relative error one. Machine epsilon measures resolution near one; it does not measure the distance from zero to the first positive value.
Subset-sum pigeonhole bound 2026-10-25
Let be a finite set of positive integers and let . Every sum of a subset is an integer in . If , the pigeonhole principle forces two distinct subsets to have equal sums. Thus cannot be a dissociated set.
Cancelling their common intersection even produces two disjoint subsets with the same sum. Positivity means neither remaining subset can be empty. Conversely, equality of two distinct subset sums gives a nonzero relation with coefficients in , exactly the obstruction to being a dissociated set.
For an -element subset of , the largest possible is . Thereforeis a sufficient condition forcing a collision for every such subset. This counting bound is sufficient rather than necessary. Powers of two show how a collision-free collection can instead use the binary representation to make all sums different.
Success-count and waiting-time duality 2026-10-20
The same stopping rule connects a waiting count to a fixed-length count. Let be the trial number of the th success, and let count successes in the first trials, so has a binomial distribution. For any nonnegative integer ,The target is still unmet after trials exactly when fewer than successes have occurred. With , and , this gives ; equivalently, , matching . At , the event identity still holds, with and deterministically.
Sudoku Created 2026-10-20 Updated 2026-10-25
A finite constraint satisfaction problem on a array. Each entry must be one of the integers , and every row, column, and designated box must contain each value once. Given entries constrain the possible completions; backtracking searches those completions.
Sum map from words to homothetic copies 2026-10-14
For a finite pattern in a real vector space, pull a finite colouring back to words through the displayed sum map. A combinatorial line with active coordinates J maps to . The Hales-Jewett theorem therefore forces a monochromatic homothetic copy. Integer patterns remain in the integer lattice; choosing b sufficiently large gives the positive-lattice version.
Summation loop verification Created 2026-10-18 Updated 2026-10-31
Compute , the triangular number , for a nonnegative integer . The empty sum gives zero when . Use exact mathematical integers and keep the input unchanged; every comparison and variable assignment is a terminating operation. The original sequential procedure isThe order of the two variable assignments matters: the addition uses the newly incremented . For , the pairs at successive condition checks are . At the last check, is false, and the returned sum is .
require n is an integer and n >= 0
i = 0
s = 0
while i < n:
i = i + 1
s = s + i
return sThe precondition is with , under the exact-arithmetic model just stated. The postcondition for returned value is , with still equal to its starting value. At each condition check use the loop invariantand the loop variant . The equation says that the accumulator is the triangular number for precisely the processed prefix ; the inequalities connect that prefix to the loop's condition.
The summation loop restores its invariant before each condition check
. Original sequential control flow for the summation loop verification. The blue loop head carries the loop invariant; the orange body increments before adding it to . A false condition leads to the postcondition. The loop variant decreases on the return arrow. All values are mathematical integers and remains unchanged. Details.Initialization gives , so holds, including when . For preservation, let the old values satisfy and . Write and for the values after both variable assignments. Since are integers, gives , andThus the completed body restores . Between the two variable assignments, the equation can be false; the loop invariant is required at the loop head. This preservation step is mathematical induction on the number of completed iterations.
At exit, the false condition gives , while gives . Hence , so : this proves partial correctness. For algorithm termination, gives the nonnegative integer . When the condition is true, ; the terminating body gives . Therefore the loop cannot repeat forever. Together these arguments prove total correctness for every permitted input, including .
Two changes expose what the proof checks. Swapping the two body instructions computes , returning rather than for . Leaving unchanged can preserve an initial equation forever without producing any answer. The first change breaks the intended postcondition; the second breaks algorithm termination. A trace can reveal these failures, while the two proof obligations explain them.
The exact-arithmetic assumption has a concrete boundary. In a stipulated unsigned eight-bit model where each addition wraps modulo , fits in the input representation, but its intended triangular number is . The stored accumulator instead finishes at , so the mathematical postcondition fails. This is integer overflow, and the proof above does not apply to that altered model. Restricting the same implementation to prevents overflow in its stored loop values, since ; alternatively use a representation supporting the required exact integer arithmetic. The equations in the proof are mathematical statements, not instructions to evaluate products in eight bits.
Summatory totient function 2026-10-20
The summatory totient function is . It counts the coprime ordered pairs with . The identity yields for a positive integer .
Sum of prime factors with multiplicity 2026-10-25
For an integer with prime factorization , this is the sum of its prime factors with each repeated times. For example, . It differs from the sum of distinct prime factors.
Sum of reduced residues 2026-10-14
The map is a bijection of the integers between one and that are coprime to . If their sum is , this bijection gives , so . This works even at , where the single residue is fixed. The same identity follows from the weighted inclusion-exclusion principle by excluding multiples of the prime factors of .
Sum of two squares Created 2026-10-20 Updated 2026-11-05
A sum of two squares representation of a nonnegative integer is an equality with integers . For example, has two representations even before changing signs or interchanging the two terms.
Counting conventions matter. If ordered pairs and signs are distinguished, the representation generates eight pairs, whereas generates only four and only one. Every perfect square is zero or one modulo four, so an integer congruent to three modulo four is impossible. That quick obstruction is insufficient by itself: also has no representation. The exact prime factorization criterion is the sum of two squares theorem.
Sum of two squares theorem Created 2026-09-24 Updated 2026-11-05
A positive integer is a sum of two squares of integers exactly when every prime factor congruent to three modulo four has an even prime exponent in its prime factorization. The zero-square convention permits ; zero itself separately has .
For necessity, let divide . If , then , contradicting Euler's criterion for minus one at such a prime. Hence , and then as well. Divide both coordinates by and repeat. Each removal subtracts two from the prime valuation of , forcing it to be even.
For sufficiency, two is . A prime number congruent to one modulo four has a square root of minus one by Euler's criterion, and the congruence lattice proof of the prime sum of two squares turns that root into a representation of the prime. Each even power of a prime congruent to three modulo four is already a perfect square, hence a sum of two squares with a zero term. Finally, the Brahmagupta-Fibonacci identity combines the representations across all prime powers in .
Sumset Created 2026-09-24 Updated 2026-10-13
For finite sets in an abelian group , their sumset isEach distinct value occurs only once in this set, even if many ordered pairs produce it. When , repetitions are allowed: belongs to . For the two integer sets introduced above,For , the value comes from . For , two ordered pairs give the same sum only when one reverses the other, apart from a pair being identical to itself. Thus its four pairs and six pairs with distinct members, counted without regard to order, produce ten distinct sums.
Every nonempty finite set of integers satisfies . To see this, list its members as . The distinct sumsall belong to . A nonconstant arithmetic progression attains this bound. The ordered list is essential: in the cyclic group , the subgroup instead satisfies , of cardinality three. Addition wraps around, for example in this group.
Sylvester identity for bordered minors 2026-11-05
Let a square matrix have a leading block . For row and column indices , let be the determinant formed by bordering with row and column , keeping that order. For and , the Sylvester identity for bordered minors isIt is a polynomial identity and remains valid when is singular; dividing by requires an additional nonzero condition.[ref]
For and , the bordered minors are , , . The identity reads . In Bareiss algorithm, this identity explains why division by a previous pivot can be exact over the integers.


