Inverse element Created 2026-09-24 Updated 2026-10-14
An inverse element of in a monoid is an element satisfying , where is the identity element. Its notation is . Some elements of a monoid can lack an inverse element; a group requires one for every element. Associativity makes a two-sided inverse element unique: if both invert , then .
For the full transformation monoid, a self-map has an inverse element exactly when it is a bijection; that element is its inverse function. On , the swap is its own inverse element, while a constant function has none because it merges the two inputs.
Linear interpolant 2026-10-31
A linear interpolant is the unique polynomial of polynomial degree at most one taking prescribed values at distinct interpolation nodes . It is an affine function, including the constant function case. For , its two displayed coefficients are nonnegative and sum to one, so changing each sampled value by at most changes every interpolated value by at most . Differentiation instead uses the difference of the two samples divided by , causing noise amplification by differentiation of a linear interpolant.
Little Picard theorem Created 2026-09-24 Updated 2026-10-14
Every nonconstant entire function takes every complex value with at most one exception. Equivalently, its image is either or for one complex number . The hypothesis of being nonconstant matters: a constant function has only one value. The Little Picard theorem guarantees existence of preimages, without requiring infinitely many preimages for each attained value. [ref]
For a nonconstant polynomial , the fundamental theorem of algebra applied to supplies a preimage for every . The complex exponential function has precisely one omitted value, zero, as the explicit formula for its preimages shows. In contrast, the complex sine function has no omitted value. To solve , set and rearrange to the quadratic equation
Its roots have product , so they are nonzero. Every such root has a preimage under the complex exponential function, giving a solution for . Adding supplies further solutions by the periodicity of the complex sine.
The force of the Little Picard theorem is that it applies to every nonconstant entire function, without an explicit formula. The Liouville theorem already gives a dense image of a nonconstant entire function, but a dense subset could still leave out many individual points. The Little Picard theorem limits these missing points to one. In particular, establishing two omitted values proves that an entire function is constant.
For a nonconstant meromorphic function on the complex plane, the corresponding bound is two omitted values in the Riemann sphere , where poles take the value infinity. [ref] For example,
omits zero and one, and has poles at for . Every other finite value is attained by solving . For an entire function, infinity is already an omitted value in the Riemann sphere, leaving at most one additional finite omitted value.
Proof outline: use the version of Montel's theorem for two fixed finite omitted values. [ref] It makes the rescaled holomorphic functions a normal family on the unit disc. The fixed value gives pointwise anchoring of a holomorphic normal family, hence a subsequence with a finite holomorphic function as its locally uniform convergence limit. The Cauchy integral formula bounds its derivatives at zero, whereas . Consequently ; arbitrary makes constant.
Local maximum Created 2026-10-05 Updated 2026-10-14
A real-valued function , with , has a local maximum at if some satisfies
Only a neighbourhood within the domain of a function is compared. Equality is allowed; a strict local maximum requires for every other point in that neighbourhood. A constant function therefore has a local maximum and a local minimum at every input, with neither strict. This is a local form of an extremum of a real-valued function.
For , zero is a strict local maximum because when . It is not a global maximum: values far away grow without bound. This distinction makes a local maximum useful for describing a nearby peak without claiming that it is the highest value anywhere.
Negating the function exchanges local maxima and local minima, including their strict versions. At a smooth interior local maximum, the critical point argument forces zero gradient; for a function twice continuously differentiable nearby, its Hessian matrix is negative semidefinite. These necessary conditions alone do not establish a local maximum.
Mean value theorem Created 2026-09-24 Updated 2026-10-14
The mean value theorem says that an average rate of change is attained as an instantaneous rate somewhere between the endpoints. Let and let the real-valued function be continuous on the closed interval and differentiable on the open interval . Then there exists such that
The right-hand side is the slope of the secant line joining to ; the left-hand side is the slope of the tangent line at . The derivative need not be continuous, and the function need not be differentiable at the endpoints. [ref]
For the polynomial on , the secant line has slope . Since the derivative is , the required interior point is . The tangent line there is , whereas the secant line is . Their equal slopes make them parallel, but they are distinct straight lines: the theorem equates rates, not heights.
Figure 1.
The secant line and interior tangent line to have equal slopes but different heights
. Details.
The practical strength is that the unknown point can disappear from an estimate. Under the same hypotheses, if the derivative satisfies throughout , where , then
Applying this to every subinterval proves Lipschitz continuity with Lipschitz bound . For example, on has , so an input change of size at most changes its output by at most , as long as both inputs lie in that interval. A local derivative bound therefore controls finite changes without computing an integral. The sign of the derivative similarly gives the derivative criterion for monotonicity.
Taking shows that a function with zero derivative throughout a real interval is a constant function, provided it is continuous at any included endpoints. The interval condition is essential: on the domain of a function , the function equal to zero on the left interval and one on the right interval has zero derivative everywhere. It is a locally constant function, yet not a constant function on the whole domain of a function. The mean value theorem cannot cross the gap.
A concise proof subtracts the secant line: set and . Then , and Rolle's theorem gives an interior point with . The geometric idea is to remove the average trend and find a horizontal tangent line in what remains.
Monochromatic set Created 2026-09-24 Updated 2026-10-14
A subset is monochromatic for a finite coloring if there is a color such that
Equivalently, the restriction of a function is a constant function, or lies in one colour class . The word describes agreement of colors; it does not require to equal an entire colour class.
For example, color the integers by integer parity, using red for even and blue for odd. The set is monochromatic, whereas is not. If the colored objects are edges, a monochromatic triangle in a graph means that its three edges form a monochromatic set. In a coloring of -element subsets of a set , a homogeneous set for a colouring means that the collection of all -element subsets of is monochromatic. For pairs, this is a complete graph on whose edges all have one color, rather than a coloring of the vertices in .
Monotonic function 2026-10-14
A real-valued function , with domain of a function in the usual order of the real numbers, is a monotonic function if it is either a nondecreasing function throughout or a nonincreasing function throughout . The same direction must work for every pair in . Being a strictly increasing function on one part and a strictly decreasing function on another does not make the whole function monotone: for example, on the real line changes direction at zero. A constant function is both a nondecreasing function and a nonincreasing function.
The word "increasing" is ambiguous across textbooks: some allow equal outputs and some require unequal outputs. Use nondecreasing function for the weak inequality and strictly increasing function for the strict inequality; use nonincreasing function and strictly decreasing function in the other direction. Neither continuity nor differentiability is part of the definition of a monotonic function.
Strict monotonicity gives injectivity, so an equation has at most one solution and an inverse function exists on the image of a function. Weak monotonicity permits repeated outputs and jumps. In probability theory, a cumulative distribution function is a nondecreasing function; its quantile function uses a generalized inverse to handle those flat parts and jumps. Monotonicity alone does not guarantee continuity, even for a strictly increasing function.
Figure 1.
Strict and weak monotonicity: cubic functions, flat portions, and a step
. The strictly increasing function and strictly decreasing function never repeat an output. The nondecreasing function has flat intervals, and the step function for , for is a discontinuous cumulative distribution function. The open and closed circles specify its value at the jump; no vertical segment belongs to its graph. Details.
If the observed samples are , the resulting quadrature rule changes by . Bounded sample perturbations therefore satisfy
For ordinary numerical integration with nonnegative quadrature weights exact on constant functions, the bound is , independent of panel refinement. A common bias attains it: the quadrature error due to the function approximation may vanish while this sample error persists. Interpolating a fixed data set onto a finer grid likewise does not create new observations or remove its uncertainty.
With new samples whose errors are independent random variables of zero expectation and common variance , a different model gives
For equal panels this is for the composite midpoint quadrature rule and for the composite trapezoidal rule. These variance reductions require the stated independence and unbiasedness assumptions; a common bias or correlated sample errors need not shrink. The two displayed perturbation formulas follow directly from the triangle inequality and the variance additivity for independent random variables, respectively.
Nonconstant function 2026-10-14
A function is nonconstant when two inputs in its domain of a function have different outputs. For example, on the real line is nonconstant, whereas the same rule restricted to is a constant function.
An unrestricted Boolean function on inputs cannot be classified as constant or nonconstant with certainty using a single phase oracle query, even with quantum ancillas. Write a purified query input as with and . The zero constant function leaves it unchanged; the function supported only at produces a vector with inner product with it. Perfect discrimination of pure states requires orthogonality, forcing for all and thus , a contradiction. This is an exact quantum query complexity obstruction for all nonconstant inputs, rather than the restricted promise used by the Deutsch-Jozsa algorithm.
We prove the one-query constancy obstruction for phase oracles while allowing arbitrary quantum ancillas. By purification of a density operator, the quantum state immediately before the sole query can be taken as
The ancilla vectors need not be normalized or orthogonal. Classical randomness and earlier quantum measurements can be included in additional ancillas; allowing access to these systems only gives the proposed algorithm more power.
For the zero constant function, the phase oracle is , leaving unchanged. For each , consider the Boolean function that is one at and zero elsewhere. Since , it is nonconstant, and its phase oracle produces
Any later fixed unitary transformation preserves these inner products. An arbitrary final quantum measurement cannot distinguish the constant output from each nonconstant output with certainty unless they are orthogonal, by perfect discrimination of pure states requires orthogonality. Explicitly, an accepting POVM effect would satisfy and , forcing .
Therefore exact classification requires for every . Summing gives
which contradicts . Thus one query cannot decide constancy with certainty. The other constant function gives , differing only by a global phase, so it does not change the argument. For comparison, permits ; the impossibility arises from demanding the test work for every nonconstant Boolean function.
For real , the Sobolev space consists of those tempered distributions whose Fourier transform is represented by a locally square-integrable function and for which
This is the Sobolev norm used here; inserting the fixed factor gives an equivalent convention.
For the constant function , Fourier inversion at zero gives
A nonzero Dirac delta distribution cannot be represented by a locally square-integrable function. Indeed, if represented , choose a test function with , and put . On a fixed compact interval containing their supports, Cauchy-Schwarz inequality gives
Thus . Every Sobolev space requires local square integrability of the Fourier transform, regardless of how negative is. Therefore
The zero constant function belongs to every Sobolev space.
Normalize the second qubit as . Since a Pauli X gate changes to , the Boolean quantum oracle acts as
This quantum phase kickback leaves the second qubit uncorrelated with the first. Put : for a constant function and for a balanced Boolean function. Apart from the irrelevant global phase , the first qubit and environment reach
The population-preserving interaction commutes with the quantum oracle on this answer-register input, so its placement before or after the oracle, between the two Hadamard gates, gives the same result. Substitute into b:
The printed Deutsch algorithm uses the rule zero means constant function; one means balanced Boolean function. With that rule, the Deutsch algorithm with pure dephasing succeeds for either class with
For real nonnegative environment overlap this is , ranging from certainty at to random guessing at . For general complex overlap, a coherent shift can invert the printed answer: for example makes the printed rule always wrong. If the overlap is known but the printed quantum measurement is retained, choose the better labeling of its outcomes; this gives
There is a further improvement if a known can be compensated by the phase gate before the final Hadamard gate. It removes the coherent shift without reversing any actual quantum decoherence, and yields
This is optimal when only the first qubit is accessible, with equal prior probabilities for the two classes. Before the final Hadamard gate, their reduced density matrices are
The difference has eigenvalues , giving trace distance . The Holevo–Helstrom theorem therefore bounds the success probability by , exactly attained by the compensated procedure. A known phase shift and loss of coherence have different effects: at the two density matrices coincide and no measurement on the available qubit can reveal the answer.
For one input bit, a Boolean function is specified by the pair , and counts its satisfying assignments. In the ordered computational basis , the supplied phase oracle convention gives
Here is exclusive or: the oracle changes the sign of the inputs with . With the identity matrix and the Pauli Z gate, all four cases are
The two middle cases are balanced Boolean functions; the others are constant functions. The specified zero-state sign change and the Hadamard gate are
Use the top qubit as the first tensor product factor. Write the controlled unitary gate as . Reading the bracketed quantum circuit from left to right, its four operations are , , , . Thus the target operation in its control-one branch is
where the rightmost matrix acts first. The control-zero branch is the identity operator. The Hadamard conjugation of a controlled gate identity gives
Indeed, on control zero the replacement applies to the target, while on control one both sides apply . By linearity, the identity holds on every quantum superposition and therefore in every repetition of the bracket. This replaces the two internal controlled Hadamard gates as a pair.
The global phase of a controlled quantum gate must be preserved: , whereas . Consequently the minus signs in and the special phase oracles cannot be discarded as an unobservable global phase of the complete quantum circuit.
For brackets the control-zero branch still does nothing, and the control-one branch applies to the target. Immediately before the final two Hadamard gates, the quantum state is
For the constant function with , the phase oracle is , so . Since is an eigenstate of the Pauli X gate with eigenvalue , for every integer . The final two Hadamard gates therefore give
In particular, the first qubit always ends in .
For the constant function with , and , so . Thus the target remains in , and the top qubit before its final Hadamard gate is . The sign is a relative quantum phase between the control branches. The Hadamard gate converts it into the integer parity of :
The first qubit is therefore for even and for odd , including all requested .
A collection of logical connectives is functionally complete, or adequate, if every Boolean function of finitely many propositional variables is represented by a logical formula using only those logical connectives. More explicitly, for every and every there is a logical formula whose truth value under each Boolean valuation is . Constant functions with Boolean values may use an otherwise irrelevant logical variable, for example for truth and for falsity.
Write for the set of continuous real-valued functions on the real line. Constant functions give an injection of into this set. In the other direction, restriction to the rational numbers is injective. Indeed, if continuous functions agree at every rational and is real, choose rational numbers . Continuity gives
Thus restriction embeds into , which has the same cardinality as the real-sequence space because is countable. The previous part gives the upper bound , while constant functions give the matching lower bound. Hence
This computes the cardinality of continuous real functions. All five sets consequently have the same cardinality. The continuity assumption is decisive for restriction to a dense subset to determine a function.
Fix and put . For each pair , choose whose errors at these two points are smaller than . By continuity, there is a neighborhood of on which . For a fixed , these neighborhoods cover the compact space . Choose a finite subcover and form
Then everywhere, while , because every chosen function has error smaller than at . Since is continuous, there is a neighborhood of on which .
A second use of compactness supplies covering . Set
Every is above , so their minimum is also above it. At each point at least one is below , and hence so is their minimum. This proves . The two finite operations are the essential mechanism in lattice approximation from two-point approximation; no closure under addition or multiplication has been assumed.
For the corollary take to consist of all continuous piecewise linear functions on . On a common finite partition, the maximum or minimum of two affine pieces can change which piece it selects only at their crossing. Adding those finitely many crossings to the partition shows that is closed under both operations. For two distinct points, the affine polynomial through the two prescribed values belongs to and matches exactly there; for equal points use a constant function. The proved criterion therefore gives density of continuous piecewise linear functions in in the supremum norm. Concretely, interpolation on a partition of maximum gap also gives error at most by uniform continuity.
False. Take , and the constant function . For the subsets and , the intersection is empty, so , whereas the intersection of their images of a function is . In general the inclusion holds, but a common image value can arise from different points of and .