Smallest prime factor Created 2026-10-20 Updated 2026-11-05
For an integer , its smallest prime factor is the least prime divisor of . If is prime, it equals ; if is composite, it is at most , because otherwise every product of two prime factors would exceed .
For example, . A sieve can tabulate smallest prime factors for all integers up to a bound. Repeatedly replacing by then produces its prime factorization. The value at one is a sentinel convention in implementations, since one has no prime factor.
Smallest prime factor sieve Created 2026-10-20 Updated 2026-11-05
A smallest prime factor sieve stores the least prime divisor for integers up to a bound . Initialize entries unset; scan primes in increasing order and fill their still-unset multiples. A composite first marked by has no smaller prime divisor, so the stored value is correct. For example, repeatedly dividing by its stored factors gives , hence . A table uses entries and accelerates repeated factorizations; the values at zero and one need a separate sentinel convention.
Small Type I and Type II sums Created 2026-10-14 Updated 2026-11-05
Extend by zero, and assume . In one dyadic endpoint convention, Type I sums are -small if for every dyadic and every choice of integer intervals , . Type II sums are -small if for all dyadic and coefficients . Empty tails are handled by zero extension.
Smith normal form Created 2026-09-24 Updated 2026-11-05
For every matrix over a principal ideal domain, there are invertible matrices such thatThe nonzero diagonal entries are unique up to multiplication by units. Over the integers, and are unimodular and the may be chosen positive; their products are the greatest common divisors of the -rowed minors.
Solution set Created 2026-10-14 Updated 2026-10-31
The solution set of a mathematical condition in a specified domain collects every allowed value that satisfies it:It describes the answer without committing to the steps used to find it. For the equation over the real numbers, the solution set is ; restricting to positive real numbers leaves . For , the solution set is over the rational numbers and the empty set over the integers. The domain is part of the question.
An equation can have one solution, several solutions, no solutions, or an entire domain of solutions. Over the real numbers, gives the singleton set , gives the empty set, and the mathematical identity gives the whole real line. Changing that second equation's domain to the complex numbers gives . The elementary definition by values that satisfy an equation and the classification by solution sets appear in College Algebra 2e, §2.2: Solving Linear Equations in One Variable.
Three equivalent equations have the same singleton set of solutions , even though their displayed function values differ
. Details. Requiring several conditions simultaneously takes the intersection of their solution sets. The squared equation has solution set . Adding the restriction giveswhich is also the solution set of . The extraneous solution example explains why the sign restriction is needed. Requiring at least one of several conditions instead takes their union. This turns logical combinations of constraints into reusable operations on sets.
For several variables, a solution is an ordered assignment, usually represented by a tuple. The real equation has solution set , a straight line in the Euclidean plane with coordinates . Adding intersects that straight line with another, leaving the single tuple . A system of linear inequalities has no solution exactly when the intersection of its individual solution sets is the empty set. For optimization constraints, this common solution set is the feasible region.
Because a solution set is a set, the order in which its members are listed is irrelevant. The multiple root of is still the one solution ; its multiplicity of a root is additional polynomial information, rather than a second occurrence inside the solution set. Equivalent equations preserve the solution set on the stated domain, even if their algebraic forms differ.
Somenath Biswas 2026-11-05
Somenath Biswas coauthored the 2003 paper on primality testing and polynomial identity testing with Manindra Agrawal. Their randomized algorithm reduces a candidate integer's primality to a univariate polynomial identity over the integers modulo that candidate.[ref]
A polynomial can have very high polynomial degree while being represented by a small arithmetic circuit. Expanding every polynomial coefficient can then be impractical. The paper also gives randomized algorithms for multivariate polynomial identity testing with running time polynomial in the circuit representation size and an error parameter. The input representation and probability of error are consequently essential parts of the algorithmic statement.
Sorted array 2026-10-13
An array whose entries appear in nondecreasing order under a specified total order. The displayed inequalities allow repeated values.
For example, is a sorted array of integers. Inserting at index gives : with spare capacity, first shift one slot right. Appending would violate the sorted array property. Updating an entry also requires preserving the total order, or removing and reinserting it in a suitable position.
The useful combination is order plus direct indexed access: binary search eliminates a whole interval of candidates at each comparison, giving search time complexity under constant-cost comparisons and the array cost model. A sorted array is therefore attractive for many lookups between changes, while keeping it sorted can still require shifting work per insertion. A sorted linked list has the ordering information but does not supply the same constant-cost access to a middle index.
Space complexity Created 2026-09-24 Updated 2026-11-05
The space complexity of an algorithm measures the maximum working storage used during its computation as a function of encoded input length. A machine-level definition must state which storage counts. In a common Turing machine convention, a read-only input tape and a write-only output tape are excluded, while visited work-tape cells are counted.
For example, count the ones in a binary string of length by scanning once and retaining a binary counter. Its value ranges from zero to , requiring bits for the counter. Keeping a separate copy of the full input would instead require bits. The computation can therefore use much less working storage than the amount of data it examines.
The maximum concerns simultaneously retained storage, not the total amount allocated and later reused over time. Bit complexity and a unit-cost model also need care here: treating an arbitrarily large integer as one storage cell can hide its growing representation size.
Sparse peaks can determine a limit superior 2026-10-14
Define a sequence by when is a power of two, including , and otherwise. Every tail of a sequence contains both a later power of two and a later nonpower. Therefore and , and the sequence does not converge. Its peak indices become increasingly sparse, yet never stop appearing.
Through index , the number of peaks is , so their fraction isThe set of powers of two has natural density zero. The same fraction is the Cesàro mean of the first terms, which tends to zero even though the limit superior stays one. At , eleven peaks give mean . An average and a long-run upper edge answer different questions about the same sequence.
Spatial aliasing 2026-10-25
Ambiguity between spatial oscillations sampled on a grid. At positions , the factors and agree for every integer . Spatial wavenumbers outside therefore cannot be distinguished without additional assumptions. For a traveling event of temporal frequency and apparent speed , the associated criterion is , with a margin for filtering. Temporal oversampling does not remove this spatial ambiguity.
Spatial locality 2026-10-13
Spatial locality is the tendency to access nearby locations in computer memory within a short interval. A sequential scan of a contiguous array has spatial locality even when each element is read only once. A memory cache can exploit spatial locality by fetching a whole cache line on a cache miss: later reads of neighbouring elements become cache hits. Proximity is in the address layout, so visually adjacent entries in a table need not be adjacent bytes.
Consider a array of 32-bit integers, each occupying four eight-bit bytes, stored contiguously in row-major order. Use toy physical addresses starting at zero, aligned to a 16-byte cache line boundary. For row and column , with , the address and cache block number areHere is the floor function. Each row occupies exactly one cache line: row zero begins at addresses , row one at , and so on. Row-major order describes this storage layout; traversal can follow rows or columns without moving the elements.
Read all sixteen elements and compute their integer sum, keeping the accumulator outside the modelled memory cache. Only the sixteen array reads count as memory references. The toy fully associative cache starts empty, holds exactly one 16-byte cache line, fetches the requested cache block on every cache miss, and uses LRU replacement. No cache block is fetched ahead of a request, and no writeback costs are counted because the modelled accesses are reads.
- Traversing by rows, with varying fastest, requests cache blocks . Each first read in a row is a cache miss; the next three are cache hits. Total: four cache misses and twelve cache hits in sixteen memory references.
- Traversing by columns, with varying fastest, requests cache blocks four times. Every read replaces the sole resident cache line, so the next read always causes a cache miss. Total: sixteen cache misses and zero cache hits in sixteen memory references.
Every element is read once in both traversals. The row traversal exploits spatial locality between distinct elements and temporal locality of their shared cache block. The column traversal returns to each cache block after three other distinct cache blocks, too late for the one-line memory cache. Increase the fully associative cache to four cache lines and both traversals give four compulsory misses and twelve cache hits: no loaded cache block needs eviction. The difference therefore depends on capacity as well as access order and layout.
This makes spatial locality useful and beautiful: the same logical operation on the same elements can use a fetched cache line much more fully simply by changing traversal order. The toy counts do not predict a universal speed ratio on real hardware. Actual cache line sizes, capacities, placement rules, fetching ahead of requests and overlapping work affect runtime; measure a concrete implementation with statistical program profiling. Ulrich Drepper's November 2007 authored paper explains cache line transfers and gives array and matrix access examples connecting layout, temporal locality and spatial locality. Its hardware measurements are historical examples, rather than specifications for every present-day CPU. [ref]
// Destination: computer-science.bigb
Spatial sampling of a wave 2026-10-14
In spatial sampling of a wave, a detector records a wave at positions separated by pitch . Angular wavenumbers differing by , with integers , give identical samples of a complex Fourier mode:This is spatial aliasing. To distinguish arbitrary sinusoids within a prescribed band, require , equivalently , the Nyquist spatial frequency. Thus for the shortest allowed wavelength. At equality a sine can vanish at every sample, so phase information can be lost. The Nyquist–Shannon sampling theorem states the precise reconstruction conditions for a bandlimited function; a finite scan introduces further limitations.
The synthetic two-tone snapshot iswhere both count cycles per metre. The component wavelengths are and . With , both lie below the Nyquist spatial frequency of cycles per metre. With , the -cycle component aliases to the -cycle component: at every , . The sampled sum is therefore indistinguishable from , although the continuous curves differ between samples. Drawing lines between sample points cannot resolve this ambiguity.
Synthetic two-tone spatial waveform: fine samples distinguish the components, coarse samples hide the shorter wavelength
. Details. Special orthogonal sphere fibration Created 2026-10-14 Updated 2026-11-05
For an integer , the last-column map has fiber , included as . Local completion of a unit vector by the Gram-Schmidt process gives local fiber bundle charts. Consequently it has the homotopy lifting property and the long exact sequence of homotopy groups of a fibration.
Spectral gap for powers of a positive line bundle Created 2026-10-06 Updated 2026-11-05
Let be a positive holomorphic line bundle on a compact complex manifold of complex dimension , and use as the Kähler form. There is a constant independent of the positive integer such that, on smooth -valued -forms with ,In particular, for sufficiently large , the Dolbeault Laplacian is bounded below by on every positive antiholomorphic degree.
To see the positive sign, identify these forms with -forms valued in , using the canonical bundle and its dual bundle. The Bochner-Kodaira-Nakano identity writes the quadratic form as a nonnegative derivative term plus the curvature commutator. The contribution acts by in bidegree ; the inverse-canonical contribution has uniformly bounded size on compact . This gives . Applying the curvature commutator directly in bidegree without this twist would give the wrong sign.[ref]
Complex Analytic and Differential Geometry by Jean-Pierre Demailly. Chapter VII, §§1–2, Bochner-Kodaira-Nakano identity and basic a priori inequality, printed pp.329–333
The estimate rules out nonzero harmonic forms in these degrees. The Dolbeault Hodge decomposition and Dolbeault theorem therefore imply for and sufficiently large . The additive constant matters for small powers; the linear spectral gap is an eventual statement.
Spin-orbit resonance 2026-10-14
A prograde spin-orbit resonance relates mean spin angular velocity to mean motion by a ratio of small positive integers, : the body makes turns in orbital periods. Synchronous rotation is ; Mercury's spin-orbit resonance is nonsynchronous. The relevant combination of spin and orbital angles must stay bounded around a preferred orientation, not merely have a near-integer frequency ratio. For an elongated body on an eccentric orbit, the companion's gravitational torque on the permanent shape can sustain the resonance while tidal dissipation permits capture. [ref].
Splitting of prime ideals Created 2026-10-20 Updated 2026-11-05
In a finite extension of number fields , a nonzero prime ideal of factors uniquely as . The distinct prime ideals are the primes above , the exponents are ramification indices, and are residue degrees. They satisfy .
A prime splits completely if it has distinct factors, all with . In the Gaussian integers, splits, is an inert prime, and ramifies because . The three behaviors distinguish factorization of ideals from factorization of ordinary integers.
Square class Created 2026-10-06 Updated 2026-11-05
The square class of is its image in the square-class group of a field . Two nonzero elements have the same square class exactly when their quotient is a square. Every element of this quotient has order dividing . Over the rational numbers, a square class has a unique signed squarefree integer representative.
Square factor Created 2026-09-24 Updated 2026-11-05
A square factor of an integer is a positive perfect square dividing . Every integer has the trivial square factor one; usually the useful question is whether a nontrivial one, with , occurs.
A positive integer has a nontrivial square factor if and only if some prime number satisfies . One direction takes ; for the other, choose any prime factor of . Equivalently, some prime exponent in is at least two. For example, twelve has square factor four and eighteen has square factor nine, whereas thirty has none other than one. A positive integer without a nontrivial square factor is a square-free integer.
Squarefree divisor Created 2026-10-06 Updated 2026-10-14
A squarefree divisor of an integer is a divisor that is a squarefree integer. It is specified by choosing a subset of the distinct prime factors of .
Square-free integer Created 2026-09-24 Updated 2026-11-05
A positive integer is square-free when no square number greater than one is a divisor of . It suffices to exclude squares of prime numbers; equivalently, every prime valuation is zero or one:Thus the prime factorization of a square-free integer is a product of distinct prime factors, with no repetitions. One is included: its prime factorization is an empty product and all its prime valuations are zero. These equivalent tests are stated in Grinberg's notes. [ref]
Floor and arithmetic functions by Darij Grinberg. Darij Grinberg, MIT 18.781, Floor and arithmetic functions, Definition 2.1.2 and footnote 6
For signed integers, extend the definition by requiring to be a square-free integer, where denotes absolute value. Hence and both qualify. Zero does not: every prime number has its square as a divisor of zero. The Möbius function and radical of an integer below use their existing positive integer domains, so apply them to when handling a negative integer.
For example, is a square-free integer, whereas is not, because and . Being a composite number causes no problem: are all square-free integers. A square-free integer need not be coprime to another integer: and are both square-free integers but have greatest common divisor two. In fact the only signed integers coprime to every integer are , since .
Exact square-free integer classification of the integers from one to sixty
. Green cells are square-free integers; each red cell displays a prime number square that divides its label, choosing the smallest such prime number. Only need testing in this range. There are green cells. This original finite arithmetic diagram is an exact enumeration, not a measurement or an assertion about a limiting frequency. Details.For positive integers , the useful product criterion isThe proof outline is just addition of prime valuations: can stay at most one only if neither input repeats a prime factor and no prime factor occurs in both. Thus is a square-free integer, but is not. An equivalent characterization is that every factorization into positive integers has coprime factors. If , the factorization supplies two factors sharing ; conversely, a shared prime factor forces its square to divide . For , the unordered factor pairs all have greatest common divisor one; for , the pair fails.
Two existing arithmetic functions turn the definition into practical tests:The radical of an integer keeps one copy of each prime factor, so it changes precisely the integers with a repeated prime factor. Its definition is given in Evertse's exercise sheet. [ref]
https://pub.math.leidenuniv.nl/~evertsejh/dio12-ex4.pdf. Jan-Hendrik Evertse, Diophantine approximation, Homework IV, Exercise 20
The Möbius function assigns to a square-free integer with distinct prime factors and zero otherwise; squaring forgets the sign. Consequently counts exactly the green cells. This connects a restriction on repeated prime factors with weighted counting and inclusion-exclusion. [ref]Floor and arithmetic functions by Darij Grinberg. Darij Grinberg, MIT 18.781, Definition 2.1.2: the Möbius function





