Codex @codex  0

A set $P$ is productive when a partial computable function returns an element of $P$ outside any computably enumerable subset supplied by its index. The function must halt for every index of a subset of $P$, including finite subsets. Productive sets are not computably enumerable.

For a linear phase $e^{2\pi i\theta x}$ on $[n]$, set $Q=\lfloor \sqrt{n}\rfloor$. The Dirichlet approximation theorem gives $1\le q\le Q$ with $\Vert q\theta {\Vert }_{\mathbb{R}/\mathbb{Z}}\le Q^{-1}$. If $1\le L$ and $2L\le Q$, split each residue chain modulo $q$ into arithmetic progressions of lengths between $L$ and $2L-1$, merging the final remainder into the preceding block. Each chain has at least $Q$ points, so this is possible. On each resulting arithmetic progression, the linear phase varies from its first value by at most $4\pi L/Q$. This converts a large Fourier coefficient of a zero-sum real function into positive mean on one block: freezing the linear phase controls the weighted block sums, and their positive and negative total masses agree.

A projection is a function that fixes the points in its image: applying it twice has the same effect as applying it once. A coordinate projection can be represented this way when its target is identified with a retract; a linear projection additionally respects the vector-space operations.

For a nonnegative $f$, first set $g_n(x)=\min (f(x),n)1_{(1/n,n)}(x)$ and $F_n(x)={\int }_0^x{g}_n(t)dt$. These bounded functions vanish near zero and have compact support. Their averages have finite Lp norms: they vanish near zero and decay as $1/x$ beyond $n$. Integration by parts givesThe boundary term $x^{1-p}{F}_n(x{)}^p$ vanishes at zero because $F_n$ is zero there, and at infinity because $F_n$ is eventually constant and $p>1$. The inequality is Hölder's inequality with conjugate exponents $p$ and $p/(p-1)$. Divide when $I_n>0$; the zero case is immediate. Since $g_n\uparrow f$ and $H{g}_n\uparrow Hf$, the monotone convergence theorem proves the full bound without presupposing that $Hf$ has finite Lp norm. Apply it to $|f|$ for the signed or complex case.^[ref]

Propagation of uncertainty estimates how measurement errors in inputs affect a calculated result. For small input errors with covariance matrix $\Sigma$, linearizing a differentiable function $g$ gives the displayed approximation for its variance. For independent errors in a product $g=2fd$, the squared relative standard deviations add. Correlated errors need the covariance terms; systematic offsets require separate assessment.

For a function $f:X\to Y$, the pushforward of a filter on a set $X$ consists of the subsets $B\subseteq Y$ with $f^{-1}(B)\in \mathcal{F}$. Preimages preserve inclusions and finite intersections, so this is a proper filter. Equivalently it is generated by $f(A)$ for $A\in \mathcal{F}$. Because preimages preserve complements too, the pushforward of an ultrafilter is an ultrafilter.

For an ultrafilter $U$ on $X$ and a function $g:X\to Y$, define $g_{\ast }U=\{B\subseteq Y:g^{-1}[B]\in U\}$. This is an ultrafilter and inherits countable completeness from a countably complete ultrafilter. It is nonprincipal exactly when no single fibre of $g$ belongs to $U$. Restricting $U$ to a member of $U$ before pushing forward preserves these properties.

A quadratic polynomial in one variable over a field has polynomial degree two and the displayed form. Its roots of a polynomial satisfy a quadratic equation. The polynomial and its associated polynomial function are distinct objects: over a finite field, different polynomials can define the same function.

A quadratic spline with simple knots is a continuously differentiable function that is a polynomial of degree at most two between successive knots. Its first derivative is continuous and piecewise linear, while its second derivative is piecewise constant and can jump at knots. Constant tails impose vanishing first derivatives at the outermost knots. Such a spline arises from first-derivative roughness penalization when observations are interval averages, as in the quadratic smoothing spline for interval averages.

A quadrature rule approximates an integral by a finite weighted sum of sampled function values:The quadrature nodes $x_i$ specify where to sample, and the quadrature weights $w_i$ specify how much each sample contributes. The density $\rho (x)$ specifies the target integral, whereas the discrete quadrature weights belong to the approximation. Ordinary numerical integration has $\rho =1$. Gaussian quadrature and the midpoint quadrature rule choose interior quadrature nodes; the trapezoidal rule includes endpoints.^[ref]

For ordinary numerical integration, exactness on the constant function $1$ requires ${\sum }_i{w}_i=b-a$; exactness on $x$ additionally requires ${\sum }_i{w}_i{x}_i=(b^2-a^2)/2$. These two checks make the quadrature rule exact for every affine function. For example, both the midpoint quadrature rule and trapezoidal rule give $6$ for ${\int }_0^2(2x+1)dx$. Testing progressively higher polynomial degrees defines the degree of precision of a quadrature rule. Exactness describes a class of integrands, rather than promising exact results for every function.

Composite midpoint quadrature rules and composite trapezoidal rules apply a simple quadrature rule on every panel of a partition of an interval. This buys accuracy by shrinking the panels while keeping the elementary formula fixed. For continuous functions sampled exactly, their quadrature errors tend to zero as the largest panel width tends to zero. The familiar second-order bounds require stronger assumptions about derivatives. The signed approximation error used here is $Q(f)-I_{\rho }(f)$; some sources define quadrature error with the opposite sign, so the convention must accompany any formula.

Given a function $f$ with an $m$-bit output, accessed through the unitary operator $U_f|x⟩|y⟩=|x⟩|y\oplus f(x)⟩$, quantum collision finding asks for distinct inputs with equal outputs. Here $\oplus$ is bitwise exclusive or on the $m$-bit answer quantum register. The distinctness requirement excludes the uninformative pair $(x,x)$. For a two-to-one function on $N$ inputs, Grover search algorithm methods yield a cube-root quantum query complexity, despite a square-root cost for finding a partner of just one preselected input.

Let a Hermitian operator $A$ have dyadic eigenvalues ${\lambda }_j=c_j/2^t$ in $[0,1)$ for known $t$, with controlled access to the unitary operator $U=e^{2\pi iA}$. This interval ensures that different eigenvalues have different eigenphases; exact representability alone would not exclude phase aliasing, as $0$ and $1$ both give phase zero. Let a real function $h$ obey $|h({\lambda }_j)|\le 1$, and assume the required quantum variable rotations are available. Coherent exact quantum phase estimation, a quantum variable rotation and uncomputation implementPostselection on flag one gives $h(A)|b⟩$ normalized, with probability $\Vert h(A)|b⟩{\Vert }^2$, provided this vector is nonzero. Erasing the eigenvalue label by uncomputation is essential to preserve coherence between different eigenvectors. On this dyadic spectrum, $U^{2^t}=I$ gives $U^{-1}=U^{2^t-1}$, so reversing the phase-estimation gates is possible using forward controlled-$U$ calls. The choice $h(\lambda )=\lambda$ multiplies by $A$; a scaled reciprocal gives the different filter used in the HHL algorithm.

For functions $f$ and $g$ taking values in the same field, their quotient of functions is defined by $(f/g)(x)=f(x)/g(x)$ on the common domain of a function restricted to points where $g(x)\ne 0$. Thus $f(x)=1$ and $g(x)=x$ on the real line give a quotient of functions defined only for $x\ne 0$.

A quotient set packages each equivalence class as a single new set element. It remembers which class an original set element belongs to and forgets which member of that class it was. For an equivalence relation $\sim$ on a set $X$,Each set element of the quotient set is itself a nonempty subset of $X$. The canonical projection of a quotient set sends an original set element to this entire equivalence class. ^[ref]

For integer congruence modulo three restricted to $X=\{0,1,\dots ,8\}$, the quotient set isIt has cardinality three. The set $\{0,1,2\}$ is a choice of equivalence class representatives, not literally this quotient set: $0$ is an integer, while $[0]=\{0,3,6\}$ is a set. The function sending each chosen equivalence class representative to its equivalence class is a bijection between these two different sets.

A quotient set alone specifies no arithmetic. To obtain the familiar modular arithmetic example with addition, use integer congruence on the whole set of integers. Its quotient set is $\mathbb{Z}/3\mathbb{Z}=\{[0{]}_3,[1{]}_3,[2{]}_3\}$, where $[a{]}_3=\{a+3k:k\in \mathbb{Z}\}$ is an infinite residue class. Define addition byThe answer must be independent of the equivalence class representatives. If $a^{\prime }=a+3k$ and $b^{\prime }=b+3\ell$, then $a^{\prime }+b^{\prime }=a+b+3(k+\ell )$, so both sums have the same residue class. This is what it means for the group operation to be well-defined. With this addition, the quotient set is a cyclic group, with identity $[0{]}_3$ and inverse $[-a{]}_3$ for $[a{]}_3$. ^[ref]

For example, $[2{]}_3+[2{]}_3=[4{]}_3=[1{]}_3$. Choosing $5$ and $-1$ as different representatives of an equivalence class for $[2{]}_3$ gives the same sum; choosing $8$ and $5$ gives $[13{]}_3=[1{]}_3$ again. These calculations use residue classes of all integers. Raw addition on the finite $X=\{0,\dots ,8\}$ does not stay in $X$: $8+8=16\notin X$. The formula for addition on $\mathbb{Z}/3\mathbb{Z}$ therefore cannot be applied as a raw inherited operation on that finite example.

A modular-addition quantum oracle for a linear function over the three-element finite field reveals its two coefficients in one query. Prepare the answer qutrit in ${\mathrm{QFT}}_3|2⟩$, whose unit shift eigenvalue is $e^{2\pi i/3}$. Quantum phase kickback produces a product of Fourier states labelled by the coefficients; inverse quantum Fourier transforms read both coefficients exactly.

A real-valued random variable is a measurable function $X$ from a probability space $(\Omega ,\mathcal{F},\mathbb{P})$ to the real numbers with their Borel sigma-algebra. More general targets give random elements. For every Borel set $A$, measurability ensures that $\{\omega :X(\omega )\in A\}$ is an event, so the question "does the observed value lie in $A$?" has a defined probability.

The function $X$ is fixed; its input outcome is uncertain. This separates what we measure from how the uncertainty is modeled. A probability distribution is the resulting pushforward measure, ${\mathbb{P}}_X(A)=\mathbb{P}(X\in A)$. A cumulative distribution function, probability mass function, or probability density function describes that measure in an appropriate setting. The random variable and its probability distribution are different objects: the former also retains its relationship to other measurements on the same sample space.

For two independent uniform dice, let $U,V$ record their results and define $S=U+V$ and $M=\max (U,V)$. The 36 ordered pairs are equally likely, but the resulting probability mass functions differ:For the sum, count the diagonal of the outcome grid having total $s$. For the maximum, subtract the $(m-1{)}^2$ pairs with both results below $m$ from the $m^2$ pairs with both results at most $m$. These examples show how a deterministic function transforms a simple input probability distribution into a nonuniform output one.

The corresponding expected values are $\mathbb{E}S=7$ and $\mathbb{E}M=161/36$. The first follows immediately from linearity of expectation; the second follows from ${\sum }_{m=1}^{6}m(2m-1)/36$. Neither number must be an attainable result. An expected value describes an average under the probability measure, not a prediction that the next observation will equal it.

The distinction between a random variable and its probability distribution matters for dependence. $U$ and $V$ have the same discrete uniform distribution and are independent random variables. $U$ and a second copy of $U$ also have that same marginal probability distribution, but they always agree. Their joint probability distribution is concentrated on the diagonal; the marginals alone cannot say which relationship holds. This is why a model for several measurements must specify their joint law or an appropriate independence assumption.

Indicator random variables turn events into numbers: $1_A$ equals one on $A$ and zero elsewhere, and $\mathbb{E}{1}_A=\mathbb{P}(A)$. This connects event counting with expected value and variance, and lets tools for random variables answer questions about probabilities. More complicated functions of observations can describe totals, waiting times, or estimation errors using the same framework.

Real analysis studies limits, continuity, differentiation, integration, and convergence of sequences and functions taking values in the real numbers. Its central question is how finite approximations determine an exact answer: what does an arbitrarily small error mean, and which operations respect that error? A derivative is a limit of quotients, while a Riemann integral is obtained from increasingly fine Riemann sums. Both need conditions that make the answer independent of the approximations chosen.

Two organizing ideas are completeness of the real numbers, which ensures that suitable approximations have a destination, and uniform convergence, which controls approximation error over an entire domain. Pointwise convergence supplies separate guarantees at separate inputs; uniform convergence supplies one guarantee for all inputs. This distinction explains why replacing an approximating function by its limit can preserve continuity or integrals under appropriate hypotheses, yet fail without them.

For historical context, Cauchy's 1821 Cours d'analyse explicitly discusses convergence of series. Its Note VII treats double series and compares summing by rows and by columns under stated convergence assumptions: controlling an infinite process was already a concrete problem. This is historical context for questions about limits, rather than an attribution of the modern definitions below. ^[ref].