Shortest-path pursuit distance bound 2026-10-25
Suppose two pieces occupy a common connected component of a graph in an unweighted undirected graph. For integers , in each round an evader moves at most edges, then a pursuer moves up to edges along a shortest path to the new evader position, stopping upon capture. Let be their finite graph distance at a surviving round boundary.
The triangle inequality bounds the separation after the evader moves by . If that separation is at most , the pursuer captures it. Otherwise the pursuer reduces it by exactly , givingHence every surviving history has at most rounds. With a finite branching factor, the surviving search tree is finite and depth-first tree search becomes a complete search algorithm. This does not make its first goal optimal for arbitrary rewards. Initial reachability is essential: an infinite graph distance supplies no decreasing finite bound.
Siegel's lemma Created 2026-10-14 Updated 2026-11-05
Let be a number field of degree , and let be linear forms in variables with coefficients in and projective height at most . There is a nonzero satisfying every andFor , this follows by applying the pigeonhole principle to the images of the integer box under . Expanding coefficients in a rational basis of gives the factor in the general count.
Sieve of Eratosthenes 2026-10-14
The sieve of Eratosthenes finds all prime numbers at most an integer . Start with the integers marked as candidates. For each surviving candidate in increasing order, mark the multiples up to as composite numbers. Stop processing candidates once : the surviving candidates are exactly the prime numbers. Starting at saves work because any smaller proper multiple of already has a smaller prime factor. [ref]
https://web.stanford.edu/class/cs106aj/res/handouts/36-Section-6.pdf. Jerry Cain, Stanford CS106AJ, Section Handout 6, Problem 4: the sieve of Eratosthenes
.For a complete run with , the only prime numbers at most are , since . Exclude one before starting; it is not a prime number. The four marking passes are:
- : mark , removing 29 candidates.
- : mark . The nine newly removed candidates are ; the even integers were already marked.
- : mark . Only are newly removed.
- : mark . Only is newly removed.
There are surviving prime numbers:The next surviving candidate is , and , so no further marking pass is necessary. A prime number used for marking remains a candidate: starting at never marks itself.
Four passes of the sieve of Eratosthenes through 60 leave seventeen prime numbers
. Blue cells are newly marked composite numbers; gray cells were removed earlier. White cells are candidates in the first three panels, and green cells are the final prime numbers. The outlined cell identifies the prime number used for that pass. One is excluded throughout. Details.The saving from starting at is justified by the smaller multiplier: if with , then has a prime factor , so has already marked . For , the earlier multiples have already been marked using or . The first new possibility is .
For , only the prime numbers need marking passes. They remove all the composite numbers, leaving 25 prime numbers. The diagram colors each composite number by its smallest prime factor, so it shows which marking pass removes it first. The excluded integer one is shown separately.
Why does the algorithm work? A surviving candidate cannot be a composite number, since its smaller prime factor would already have removed it. Conversely, marking proper multiples never removes a prime number. Every composite number at most has a prime factor at most , so no later pass is needed. The sieve of Eratosthenes is useful when an entire bounded list is wanted; primality testing of one large integer is a different computational task.
The historical name is supported by a surviving primary account: Nicomachus, in Book I, chapter 13 of Introduction to Arithmetic, names Eratosthenes and describes separating prime numbers from composite numbers by marking multiples among the odd integers beginning with three. That passage documents the sieve tradition; the bounded algorithm above and its starting rule are the formulation explained here, rather than instructions quoted from Euclid's Elements. [ref]
https://stoicheiamath.com/wp-content/uploads/2025/09/Nicomachus-Introduction-to-Arithmetic-Student-Edition.pdf#page=28. Nicomachus, Introduction to Arithmetic I.13.2–8, Martin Luther D'Ooge translation (1926), revised classroom edition by Nathanael Hahn (2025), pp. 24–25
Sieve theory Created 2026-09-24 Updated 2026-11-05
Sieve theory estimates the number or total weight of integers that avoid specified residue classes modulo prime numbers. The sifting function records what survives. Local information, such as how often an integer polynomial vanishes modulo each prime number, is combined with bounds for the accumulated counting errors.
For example, among the positive integers at most , deleting multiples of , , and leaves . The Chinese remainder theorem predicts a survival density over a full period of length . In more complicated problems, inclusion-exclusion is exact but has too many terms, so one replaces it with manageable upper or lower bounds.
The Selberg sieve uses quadratic weights to obtain upper bounds, while a lower-bound sieve must prove that enough elements survive. The fundamental lemma of sieve theory gives accurate estimates when the sifting range is sufficiently small relative to the available distribution information. This proves results about almost primes; distinguishing primes from some almost-prime patterns encounters the parity problem in sieve theory.[ref]
Sign-bracketing binary search 2026-10-24
Suppose integer endpoints satisfy and . Repeatedly test an interior midpoint and replace the endpoint with its matching sign. The loop invariant is the ordered opposite-sign bracket. The positive integer width is a loop variant, and at termination . Thus an adjacent sign transition can be located in evaluations without assuming that is monotone. If extends continuously between the endpoints, the intermediate value theorem associates the sign bracket with a zero. This is different from finding the first true position of a globally monotone predicate.
Signed power-of-two division by biasing 2026-10-25
For signed two's complement integers, a conditional positive bias converts the rounding behaviour of an arithmetic right shift into C integer division. It can be formed without a conditional branch by turning the sign bit into either zero or a low--bit bit mask.
Proof. Nonnegative needs no adjustment. If , write , . Then , whose quotient rounded down is , exactly the quotient truncated towards zero. The bias fits safely for in an -bit signed word: it is added only to negative inputs, and the largest possible adjusted input is . The corresponding remainder is , where .
Sign extension 2026-10-24
To widen an -bit two's complement integer to bits, preserve the original low bits and fill the new high positions with the old sign bit . The change in signed positional weights is , so the represented signed value is unchanged. Zero extension instead preserves the unsigned interpretation, and changes the signed value of negative inputs.
Simple continued fraction Created 2026-10-06 Updated 2026-11-05
A continued fraction with integer and positive integer for . Its partial numerators are all one. The continued fraction convergents have the standard two-term numerator and denominator recurrences.
Simple counting process 2026-11-05
A simple counting process counts individual events without simultaneous multiplicities. In the usual convention, , its sample paths are nondecreasing, integer-valued and càdlàg, every jump discontinuity has size one, and is finite for every finite . Equivalently,where the finite arrival times are strictly increasing and have no finite accumulation point.
Simplicity specifies how arrivals are counted; it does not assert independent increments or a Poisson distribution. Deterministic arrivals at times give a simple counting process, as does a renewal process with strictly positive independent and identically distributed interarrival times. A system that records an entire batch as several events at exactly the same time can have a jump discontinuity larger than one and therefore is not simple. The Poisson process adds particular increment laws to these counting-path properties.
Simple random walk Created 2026-09-24 Updated 2026-10-14
A simple random walk on a locally finite graph chooses each vertex in the current vertex's graph neighbourhood with equal probability, assuming there is at least one available neighbour. On the integer line there are two choices, one unit left or right, so each has probability . This is the one-dimensional simple symmetric random walk. Terminology varies: a simple random walk on the integer line is also often allowed unequal step probabilities, with “symmetric” specifying the fair case.
For a simple symmetric random walk starting at , each increment has the Rademacher distribution, with expected value zero and variance one. Thus linearity of expectation and the variance of a sum of independent random variables giveFor example, after steps the expected value is zero, the variance is , and the standard deviation is . Doubling the typical distance scale takes four times as many steps. This square-root growth explains why a random walk can wander far even when there is no preferred direction.
Four fair and two biased unit-step random-walk paths, with their expected values and bands one standard deviation wide on either side.
Details. The colored curves are illustrative sample paths, not averages over all possible walks. The dashed curves show the expected values; the shaded bands show the expected value plus or minus one standard deviation at each time. These bands are a scale of spread, not confidence intervals, and give no guarantee that an entire sample path stays inside them.
Zero expected value does not make this a stationary process: its one-time probability distribution changes with , as the increasing variance already proves. It does have stationary increments and independent increments, because blocks of fresh steps have the same probability distribution at any starting time and disjoint blocks use independent random variables. This separation of position from increment is one reason the random walk is such a useful first example of a stochastic process.
Simple random walk on the integer line Created 2026-09-24 Updated 2026-10-14
A simple random walk on the integer line starts at and takes independent and identically distributed random variables as unit increments, withThe simple symmetric random walk has ; a biased random walk has . At or every step is deterministic, giving or respectively.
Count the rightward steps using indicator functions:Thus the endpoint is a shifted and rescaled random variable with a binomial distribution. For a worked example, at the endpoint means exactly three rightward steps and one leftward step. There are possible orders, so its probability is , equal to in the fair case. More generally the binomial coefficient counts the orders, giving the exact probability mass functionIn particular, the endpoint must have the same integer parity as : . For the support of a probability distribution is exactly . At only even integers in are reachable; at only odd integers are reachable. This restriction is easy to lose if one draws a smooth curve instead of discrete probability masses. The fair-walk counting argument is also presented in Grinstead and Snell, Introduction to Probability, section 12.1.
Exact binomial endpoint probabilities for fair walks of 20 and 80 steps and a biased walk of 80 steps; only even endpoints are possible.
Details. The endpoint identity and the binomial distribution give the expected value, variance, and standard deviationA short direct check gives and , hence . Then apply linearity of expectation and the variance of a sum of independent random variables.
The absolute width and the width relative to the number of steps answer different questions. In the fair case the standard deviation grows from to , while shrinks from to . At , the standard deviation is , or times the fair width, and . Centering and dividing by each walk's own standard deviation gives, for ,This rescaling equalizes the variances, not the entire probability distributions. The spacing between reachable endpoints is two, so its rescaled spacing is : approximately for the fair -step walk, for the fair -step walk, and for the biased -step walk.
The positions themselves are dependent. For , , where the second term is independent of . Their covariance is thereforeFor example, in the fair case allows or , whereas allows or . Nevertheless the position process is a Markov chain: given its current position, the next fresh increment has no dependence on its past. Its transition probabilities areThese transition probabilities are the same at every time and every integer position: shifting both and by the same integer leaves unchanged. Thus the Markov property and independent increments coexist with dependent positions.
Simple root Created 2026-09-24 Updated 2026-11-05
A simple-root system is a fundamental system of a root system: a basis consisting of roots such that every root has coordinates all nonnegative or all nonpositive. Its nonnegative linear combinations select the associated positive roots. For a reduced crystallographic root system, these simple roots are precisely the positive roots that cannot be written as the sum of two positive roots; every root is then an integer combination of simple roots with coefficients of one sign.
For the A2 root system, take and . The third positive root is , so it is not simple. In a complex semisimple Lie algebra, the simple roots select raising and lowering generators through their root vectors, while their coroots define the Dynkin labels of a highest weight.
Simple type Created 2026-10-13 Updated 2026-10-24
In the examples here, a simple type is a finite expression built from the base types
int and bool using function types:For example, describes a function accepting an integer and producing a Boolean value. During type inference, the grammar is extended with type variables such as for types not yet determined. A type scheme additionally binds such type variables; it is distinct from the individual simple type used at one call.Fix a failure probability and assume an independent and identically distributed statistical sample. A finite-sample confidence band for its population cumulative distribution function isHere is the natural logarithm. The DKW inequality impliesThis is simultaneous coverage over the whole real line, valid at each fixed sample size.[ref]
To obtain the band, solve for the positive . Outside a failure event of probability at most , for every . Since a cumulative distribution function already lies in , clipping the endpoints to this interval preserves the coverage event. The guarantee is at least , and need not equal it.
Choose , giving at least simultaneous coverage under the stated model. For , respectively, the half-widths before clipping areFor the chosen five observations, the band at is , while at it is approximately . At the unclipped band would be , so clipping gives . The broad uncertainty is informative: five observations give a precise description of themselves, but a coarse bound for an unknown population cumulative distribution function.
Finite-sample simultaneous uncertainty around an empirical distribution function
. Left: the chosen five observations give and its band clipped to , using . Right: theoretical half-widths for , with no additional samples constructed. The confidence band has coverage at least under independent and identically distributed sampling; the drawing illustrates the procedure and does not establish its coverage. Details.A collection of pointwise confidence intervals only promises coverage separately at each preselected threshold; it does not promise coverage of an entire cumulative distribution function. Here the one simultaneous event permits inspecting any threshold after seeing the data. The probability refers to repeated sampling of the entire statistical sample, with fixed. It does not assign probability to a fixed after observing this particular band, and it is not a prediction interval for a future observation. The displayed comparison gives a guarantee for each fixed separately, not simultaneous validity over all sample sizes or an optional stopping rule. The chosen observations are an illustration; the coverage claim follows from the DKW inequality, not from their appearance or a simulation. Dependence or observations with different sampling laws require another argument.
At fixed , multiplying by divides the half-width by . Conversely, a desired half-width is ensured by , rounded up to an integer. For and , this sufficient sample size is . This makes the confidence band useful for planning how many observations are needed before estimating threshold probabilities to a chosen simultaneous accuracy.
Simultaneous exponentiation by squaring Created 2026-10-24 Updated 2026-11-05
Several powers with the same nonnegative integer exponent can share one exponentiation by squaring loop. Initialize , and . The loop invariants are .
At each step, multiply every by if is an odd integer, then replace every by and by . Indeed,so all invariants are preserved. The loop variant strictly decreases whenever it is positive. At , the accumulators are exactly the requested powers. For , no iteration is needed and every result is one.
For bases, the method uses multiplications and stored arithmetic values. These are arithmetic-operation counts; exact integer products can grow in bit length. For modular exponentiation, reducing each update modulo its intended integer modulus keeps the stored residues bounded. Sharing the exponent loop does not require mixing the bases' arithmetic types.
Sine Created 2026-09-24 Updated 2026-10-14
For a real angle , is the vertical coordinate on the unit circle reached by a counterclockwise rotation through radians. For an acute angle in a right triangle, it is the opposite side divided by the hypotenuse. In particular,The first-quarter rise and second-quarter fall are visible in the circle projection; the lower semicircle gives negative values.
Reflecting the unit circle across the horizontal axis gives , so sine is an odd function. A full turn gives , making it a periodic function. For real arguments, its range is and its zeros of a function occur at for integers . The cosine describes the perpendicular coordinate of the same point, and the Pythagorean trigonometric identity keeps their two values tied together.
Size-biased probability generating function Created 2026-10-31 Updated 2026-11-05
For a positive integer-valued random variable with finite mean , the size-biased distribution has probabilities . They sum to one by the definition of expected value. Multiplying the differentiated probability generating function by gives the displayed identity for , with the endpoint interpreted by its limit.
sl3 interlacing character formula Created 2026-10-06 Updated 2026-11-05
For the special linear Lie algebra , the irreducible highest-weight representation with Dynkin labels has the displayed formal character on diagonal matrices with . The interlacing rows , and enumerate a Gelfand–Tsetlin basis; each triple contributes the exponent differences as its weight. This gives exact integer weight multiplicities, including repeated weights, without floating-point character evaluation.
Slowly varying function Created 2026-10-05 Updated 2026-10-14
A positive measurable function is slowly varying at infinity iffor every fixed . It has regular variation of index zero. “Slowly” concerns relative change under multiplication of the argument; it does not mean that the function must be bounded, have a small derivative, or converge to a finite value.
Every positive constant is a slowly varying function. So are , and for any fixed real number , on . Indeed,The first grows without bound, the second tends to zero, and the constant does neither. Another unbounded example is :This function can grow much faster than while retaining regular variation of index zero.
Even convergence is unnecessary. The bounded functionoscillates between and . It is nevertheless a slowly varying function: the change in the argument of the sine under isand the Lipschitz continuity of the sine makes the logarithm of the ratio tend to zero. The sequences and give the two values and for every nonnegative integer , so there is no limit at infinity.
Contrast this with , which is positive and bounded but is not a slowly varying function. Fix . Along its rescaling ratio is ; along the ratio is . The persistent oscillations prevent even a limit for this one fixed rescaling. It is not regularly varying with any finite index either.
Two bounded oscillating functions: logarithmic rescaling makes one ratio approach one, while the other keeps oscillating
. The horizontal coordinate is , and the fixed rescaling is . The displayed range illustrates the formulas; the limiting claims follow from the arguments in the text. Details.The useful distinction is whether a fixed proportional change of input eventually produces a negligible proportional change of output. A slowly varying function can therefore preserve the scaling exponent of a power law while changing its magnitude substantially. The decomposition in regular variation explains why a logarithmic factor can matter in numerical estimates without changing the limiting exponent.
Small divisor Created 2026-10-07 Updated 2026-11-05
A denominator such as which may become small for large integer vectors . Inverting a directional derivative on a torus divides the nonzero Fourier coefficients by . A Diophantine condition bounds this loss polynomially, so exponential Fourier decay still gives convergence on a smaller complex strip.





