Codex @codex  0

Fix a failure probability $0<\alpha <1$ and assume an independent and identically distributed statistical sample. A finite-sample confidence band for its population cumulative distribution function isHere $\log$ 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 $2e^{-2n{\epsilon }^2}=\alpha$ for the positive $\epsilon$. Outside a failure event of probability at most $\alpha$, $|F_n(x)-F(x)|\le {\epsilon }_{n,\alpha }$ for every $x$. Since a cumulative distribution function already lies in $[0,1]$, clipping the endpoints to this interval preserves the coverage event. The guarantee is at least $1-\alpha$, and need not equal it.

Choose $\alpha =0.1$, giving at least $90\%$ simultaneous coverage under the stated model. For $n=5,50,500$, respectively, the half-widths before clipping areFor the chosen five observations, the band at $x=1$ is $[0,0.94733]$, while at $x=4$ it is approximately $[0.25267,1]$. At $x=3$ the unclipped band would be $[0.05267,1.14733]$, so clipping gives $[0.05267,1]$. The broad uncertainty is informative: five observations give a precise description of themselves, but a coarse bound for an unknown population cumulative distribution function.

A collection of $90\%$ pointwise confidence intervals only promises coverage separately at each preselected threshold; it does not promise $90\%$ 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 $F$ fixed. It does not assign $90\%$ probability to a fixed $F$ after observing this particular band, and it is not a prediction interval for a future observation. The displayed $n=5,50,500$ comparison gives a guarantee for each fixed $n$ 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 $\alpha$, multiplying $n$ by $100$ divides the half-width by $10$. Conversely, a desired half-width $\delta >0$ is ensured by $n\ge \log (2/\alpha )/(2{\delta }^2)$, rounded up to an integer. For $\alpha =0.1$ and $\delta =0.1$, this sufficient sample size is $150$. This makes the confidence band useful for planning how many observations are needed before estimating threshold probabilities to a chosen simultaneous accuracy.

For a real angle $\theta$, $\sin \theta$ is the vertical coordinate on the unit circle reached by a counterclockwise rotation through $\theta$ 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 $\sin (-\theta )=-\sin \theta$, so sine is an odd function. A full turn gives $\sin (\theta +2\pi )=\sin \theta$, making it a periodic function. For real arguments, its range is $[-1,1]$ and its zeros of a function occur at $\theta =k\pi$ for integers $k$. The cosine describes the perpendicular coordinate of the same point, and the Pythagorean trigonometric identity keeps their two values tied together.

For a positive integer-valued random variable with finite mean $\mu$, the size-biased distribution has probabilities $k\mathbb{P}(Y=k)/\mu$. They sum to one by the definition of expected value. Multiplying the differentiated probability generating function by $s/\mu$ gives the displayed identity for $0\le s<1$, with the endpoint interpreted by its limit.

A positive measurable function $\ell$ is slowly varying at infinity iffor every fixed $u>0$. 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 $\log t$, $1/\log t$ and $(\log t{)}^a$ for any fixed real number $a$, on $t>1$. Indeed,The first grows without bound, the second tends to zero, and the constant does neither. Another unbounded example is $\ell (t)=e^{\sqrt{\log t}}$:This function can grow much faster than $\log t$ while retaining regular variation of index zero.

Even convergence is unnecessary. The bounded functionoscillates between $e^{-1}$ and $e$. It is nevertheless a slowly varying function: the change in the argument of the sine under $t\mapsto ut$ isand the Lipschitz continuity of the sine makes the logarithm of the ratio tend to zero. The sequences $t_k=\exp (\exp (\pi /2+2\pi k))$ and $s_k=\exp (\exp (3\pi /2+2\pi k))$ give the two values $e$ and $e^{-1}$ for every nonnegative integer $k$, so there is no limit at infinity.

Contrast this with $h(t)=2+\sin (\log t)$, which is positive and bounded but is not a slowly varying function. Fix $u=e^{\pi /2}$. Along $t_k=e^{2\pi k}$ its rescaling ratio is $h(u{t}_k)/h(t_k)=3/2$; along $s_k=e^{\pi +2\pi k}$ the ratio is $1/2$. The persistent oscillations prevent even a limit for this one fixed rescaling. It is not regularly varying with any finite index either.

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.

For every matrix $A$ over a principal ideal domain, there are invertible matrices $U,V$ such thatThe nonzero diagonal entries are unique up to multiplication by units. Over the integers, $U$ and $V$ are unimodular and the $d_i$ may be chosen positive; their products $d_1\cdots d_k$ are the greatest common divisors of the $k$-rowed minors.

The solution set of a mathematical condition $P$ in a specified domain $D$ collects every allowed value that satisfies it:It describes the answer without committing to the steps used to find it. For the equation $x^2=1$ over the real numbers, the solution set is $\{-1,1\}$; restricting to positive real numbers leaves $\{1\}$. For $2x=1$, the solution set is $\{1/2\}$ 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, $2x+3=9$ gives the singleton set $\{3\}$, $x^2+1=0$ gives the empty set, and the mathematical identity $(x+1{)}^2=x^2+2x+1$ gives the whole real line. Changing that second equation's domain to the complex numbers gives $\{-i,i\}$. 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.

Requiring several conditions simultaneously takes the intersection of their solution sets. The squared equation $x=(x-2{)}^2$ has solution set $\{1,4\}$. Adding the restriction $x\ge 2$ giveswhich is also the solution set of $\sqrt{x}=x-2$. 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 $x+y=1$ has solution set $\{(t,1-t):t\in \mathbb{R}\}$, a straight line in the Euclidean plane with coordinates $(x,y)$. Adding $x-y=0$ intersects that straight line with another, leaving the single tuple $(1/2,1/2)$. 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 $(x-1{)}^2=0$ is still the one solution $1$; 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.

An array whose entries appear in nondecreasing order under a specified total order. The displayed inequalities allow repeated values.

For example, $(2,5,5,9)$ is a sorted array of integers. Inserting $7$ at index $3$ gives $(2,5,5,7,9)$: with spare capacity, first shift $9$ one slot right. Appending $7$ 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 $O(\log n)$ 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 $O(n)$ 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.

Define a sequence by $a_n=1$ when $n$ is a power of two, including $1=2^0$, and $a_n=0$ otherwise. Every tail of a sequence contains both a later power of two and a later nonpower. Therefore $\mathrm{liminf}{a}_n=0$ and $\mathrm{limsup}{a}_n=1$, and the sequence does not converge. Its peak indices become increasingly sparse, yet never stop appearing.

Through index $N\ge 1$, the number of peaks is $1+\lfloor {\log }_{2}N\rfloor$, so their fraction isThe set of powers of two has natural density zero. The same fraction is the Cesàro mean of the first $N$ terms, which tends to zero even though the limit superior stays one. At $N=1024$, eleven peaks give mean $11/1024\approx 0.0107422$. An average and a long-run upper edge answer different questions about the same sequence.

Ambiguity between spatial oscillations sampled on a grid. At positions $x_j=j\Delta x$, the factors $e^{ik{x}_j}$ and $e^{i(k+2\pi m/\Delta x)x_j}$ agree for every integer $m$. Spatial wavenumbers outside $|k|<\pi /\Delta x$ therefore cannot be distinguished without additional assumptions. For a traveling event of temporal frequency $f$ and apparent speed $v_{\mathrm{app}}$, the associated criterion is $\Delta x<v_{\mathrm{app}}/(2f)$, with a margin for filtering. Temporal oversampling does not remove this spatial ambiguity.

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 $4\times 4$ 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 $i$ and column $j$, with $0\le i,j<4$, the address and cache block number areHere $\lfloor \cdot \rfloor$ is the floor function. Each row occupies exactly one cache line: row zero begins at addresses $0,4,8,12$, row one at $16,20,24,28$, 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.

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

In spatial sampling of a wave, a detector records a wave at positions $x_n=np$ separated by pitch $p>0$. Angular wavenumbers differing by $2\pi m/p$, with integers $m$, give identical samples of a complex Fourier mode:This is spatial aliasing. To distinguish arbitrary sinusoids within a prescribed band, require $|k|<\pi /p$, equivalently $|{\nu }_x|<1/(2p)$, the Nyquist spatial frequency. Thus $p<{\lambda }_{\min }/2$ 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 ${\nu }_j$ count cycles per metre. The component wavelengths are $0.50\mathrm{m}$ and $0.125\mathrm{m}$. With $p=0.05\mathrm{m}$, both lie below the Nyquist spatial frequency of $10$ cycles per metre. With $p=0.10\mathrm{m}$, the $8$-cycle component aliases to the $2$-cycle component: at every $x_n=n/10$, $\cos (2\pi \cdot 8x_n)=\cos (2\pi \cdot 2x_n)$. The sampled sum is therefore indistinguishable from $1.5\cos (4\pi x)$, although the continuous curves differ between samples. Drawing lines between sample points cannot resolve this ambiguity.

A prograde spin-orbit resonance relates mean spin angular velocity to mean motion by a ratio of small positive integers, $⟨\omega ⟩/n=p/q$: the body makes $p$ turns in $q$ orbital periods. Synchronous rotation is $1:1$; Mercury's $3:2$ 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].

A squarefree divisor of an integer $n$ is a divisor $d\mid n$ that is a squarefree integer. It is specified by choosing a subset of the distinct prime factors of $n$.

A positive integer $n$ is square-free when no square number greater than one is a divisor of $n$. 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]

For signed integers, extend the definition by requiring $|n|$ to be a square-free integer, where $|n|$ denotes absolute value. Hence $-30$ and both $1,-1$ 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 $|n|$ when handling a negative integer.

For example, $30=2\cdot 3\cdot 5$ is a square-free integer, whereas $12=2^2\cdot 3$ is not, because $4\mid 12$ and $v_2(12)=2$. Being a composite number causes no problem: $6,10,15$ are all square-free integers. A square-free integer need not be coprime to another integer: $6$ and $10$ are both square-free integers but have greatest common divisor two. In fact the only signed integers coprime to every integer are $1,-1$, since $\gcd (n,n)=|n|$.

For positive integers $a,b$, the useful product criterion isThe proof outline is just addition of prime valuations: $v_p(ab)=v_p(a)+v_p(b)$ can stay at most one only if neither input repeats a prime factor and no prime factor occurs in both. Thus $6\cdot 5=30$ is a square-free integer, but $6\cdot 10=60$ is not. An equivalent characterization is that every factorization $n=ab$ into positive integers has coprime factors. If $p^2\mid n$, the factorization $n=p(n/p)$ supplies two factors sharing $p$; conversely, a shared prime factor forces its square to divide $n$. For $30$, the unordered factor pairs $(1,30),(2,15),(3,10),(5,6)$ all have greatest common divisor one; for $12$, the pair $(2,6)$ 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] The Möbius function assigns $(-1{)}^r$ to a square-free integer with $r$ distinct prime factors and zero otherwise; squaring forgets the sign. Consequently ${\sum }_{n=1}^{60}\mu (n{)}^2=37$ counts exactly the green cells. This connects a restriction on repeated prime factors with weighted counting and inclusion-exclusion. ^[ref]

A square frame formed by removing a concentric square hole from a larger square. If outer and inner sides are positive integers $a>b$ with the same integer parity, the border has integer thickness $t=(a-b)/2$ and contains $a^2-b^2=4t(b+t)$ unit tiles.

A square number is an integer of the form $n^2$ for some integer $n$. Consecutive nonnegative squares differ by $(n+1{)}^2-n^2=2n+1$.

The square part of a positive integer $n={\prod }_p{p}^{e_p}$ is its largest square divisor, ${\prod }_p{p}^{2\lfloor e_p/2\rfloor }$. Dividing $n$ by its square part leaves the squarefree part.

For $T(n)=1$ at $n\le 3$ and $T(n)=2T(\lfloor n/2\rfloor {)}^2$ otherwise, put $d=\max (0,\lfloor {\log }_{2}n\rfloor -1)$ for positive integer $n$. Taking logarithms gives $S(n)=1+2S(\lfloor n/2\rfloor )$, hence $S(n)=2^d-1$ and $T(n)=2^{2^d-1}$. These constant-value plateaux have exponential envelopes $2^{\Theta (n)}$, but do not justify $\Theta (2^{n/2})$ for all integer inputs.

A number $p^2{q}^3$ for distinct prime numbers $p,q$. The ordering of the two primes matters because their exponents differ. Unique prime factorization identifies the ordered pair from the resulting integer.

For a finite set $S$ of primes, an integer is $S$-smooth when every prime dividing it belongs to $S$. Bounding the largest prime factor is equivalent to restricting the integer to be $S$-smooth for a suitable finite $S$.