WorksMathematics
An exact algebraic construction for Erdős's interpolation minimum
Abstract
For distinct nodes in , consider the integral of the sum of the squares of their Lagrange cardinal polynomials. We give a finite algebraic construction of its minimum for every positive number of nodes. For , put and . A rational symmetric polynomial matrix of order determines a nonzero rational polynomial of degree at most . The minimum is a specified real root of this polynomial. Its index is obtained from signatures at rational sample points. All steps of the value rule use rational polynomial arithmetic, univariate real root isolation, and rational symmetric elimination.
Introduction and main result
Let consist of distinct real nodes in . Its Lagrange cardinal polynomials are
We use the empty product convention when . Define
The integral is taken with respect to ordinary Lebesgue measure. The value of is invariant under a permutation of the nodes, so ordered nodes may be used throughout.
This minimization is among the classical interpolation problems of Erdős; see Erdős, Szabados, Varma, and Vértesi [4]. Brutman and Toledano [3] studied the finite minima numerically and their asymptotic behavior. The problem is also recorded as Erdős Problem 1131 [2]. Our result concerns the exact finite- minimum.
Algebraicity and an effective value procedure follow from general real algebraic methods [1]. Indeed, after clearing the positive squared Vandermonde denominator on the ordered node region, the assertion that is an attained minimum is a first-order formula over . Quantifier elimination then describes the singleton by univariate polynomial sign conditions. The construction below gives explicit polynomial and matrix data for this particular objective. It uses the classical Hermite trace principle and its parametric form; see [1, 5]. We include the trace argument needed here, including the treatment of multiplicities.
For a real symmetric matrix , write
where and count positive and negative eigenvalues with multiplicity. Zero eigenvalues contribute zero.
Theorem 1.1. For every positive integer , the infimum in (2) is attained. For it equals 2. For , every minimizing node set contains both endpoints, and
Fix and put
There are an explicitly defined symmetric polynomial matrix and a nonzero polynomial satisfying
constructed in Sections 5 and 7, with the following property. Let be the distinct real roots of in , put , and choose rational numbers for . Then and
The construction and the rule depend only on and use finitely many exact rational operations and univariate real root isolations.
The proof proceeds by an endpoint reduction, a homogeneous polynomial encoding, and a coercive perturbation whose real critical points detect the minimum. A fixed quotient basis makes the trace matrix valid at every real parameter. The last step identifies the correct root by counting signatures on the intervals between consecutive roots.
Attainment and endpoint reduction
Write .
Lemma 2.1. The minimum is attained, and .
Proof. Choose a basis of the polynomials of degree at most that is orthonormal for the inner product . Let . Distinctness of the nodes makes invertible. The coefficient vector of in this basis is . Consequently,
Here is the Frobenius norm.
Suppose a sequence of ordered configurations tends to a collision in the closed ordered region . The limiting evaluation matrix has two equal rows, so its smallest singular value tends to zero. Since
the objective tends to infinity along such a sequence. A minimizing sequence has bounded objective by comparison with any fixed distinct-node configuration. Compactness of the closed ordered region therefore gives a convergent subsequence with a distinct-node limit. Continuity of (5) at that limit proves attainment. For the same conclusion follows directly from .
The interpolation identity and the Cauchy–Schwarz inequality give . Integration proves the lower bound. □
Lemma 2.2. For every , there is a node configuration with .
Proof. Maximize the Vandermonde product
on the closed ordered node region. The maximum is positive, hence the maximizing nodes are distinct. Moving the leftmost node to strictly increases the product unless it is already there. The corresponding argument at the right gives .
For every interior maximizing node, logarithmic differentiation yields
The polynomial equals 1 at each node. At an interior node,
Moreover, has degree exactly , since its leading coefficient is a sum of positive squares. Counting the endpoint zeros and the double interior zeros of now gives
The sign of follows from the leading coefficient. The right-hand side is nonnegative on and is positive except at finitely many points. Thus .
Proposition 2.3. Every minimizing node set with contains and .
Proof. Let be a minimizing configuration with hull , and put . For , every factor of
is greater than one. Thus on . The same argument with gives on .
Suppose , and write
Then . Lemma 2.2 gives , so . The affine map from onto carries to an admissible configuration . Its cardinal polynomials transform by composition, and change of variables gives . Consequently,
contradicting minimality. Hence , which forces and .
The affine hull argument also occurs in the exact four-node analysis of White [6]. Proposition 2.3 gives the reduction for every .
A rational homogeneous encoding
Fix , and retain and . For define
In particular, , , and . For an -tuple , let denote the tuple obtained by replacing its th entry by .
Define the -linear functional on by
Thus is integration in over . Put
These are rational homogeneous forms of degree . Indeed, every entry of and the replacement has -degree two, and the Vandermonde has degree in its entries.
Lemma 3.1. For real with every coordinate nonzero,
Every ordered configuration with endpoints and arises in this way. For every real , and , and precisely when some .
Proof. If all coordinates are nonzero, then and (8) gives strictly increasing normalized nodes with the required endpoints. For any distinct-node tuple , the Vandermonde replacement identity is
Scaling all entries by shows that this ratio for equals . Squaring, summing, and integrating gives (11).
Conversely, for ordered nodes with these endpoints choose
Then and . Finally, is a square, and its zero set is determined by the successive differences . Each summand defining is the integral of a real square, which proves its nonnegativity even when several gaps vanish.
For a real parameter , define
Proposition 3.2. For every real ,
Proof. If and , Lemma 3.1 gives . At every remaining real point, and .
Conversely, Lemma 2.1 and Proposition 2.3 provide a minimizing configuration with both endpoints. Apply the converse parametrization in Lemma 3.1. Its denominator is positive, so implies .
Detecting the threshold by critical points
Set
Since is even, the added form is strictly positive away from the origin.
Proposition 4.1. The polynomial is coercive for every real , and
Proof. On the unit sphere, has a positive minimum, while has a finite maximum. Homogeneity therefore gives constants and such that
This proves coercivity. In particular, attains a global minimum. The origin is a critical point because .
If , Proposition 3.2 gives with . For sufficiently small ,
A global minimizer of is then a nonzero real critical point.
Conversely, at a nonzero real critical point , Euler’s identity gives
The last sum is positive, so . By Proposition 3.2, this implies . □
Remark 4.2. At a nonzero real critical point, all gap coordinates are nonzero. Indeed, is incompatible with the nonnegativity of on . Thus the critical-point threshold also respects every collision face of the node region.
A fixed quotient basis and its trace matrix
In the coefficient ring , write and set
Thus . Each is homogeneous of -degree and has coefficients affine in . For a multi-index, write . Fix the lexicographic order on the set
The reduction rule is
Lemma 5.1. Reduction by (19) terminates and gives a unique normal form in the span of . The residue classes of form a basis of
as a -module. For every real , the same monomials form a basis of
and normal forms commute with specialization .
Proof. Every replacement reduces total -degree by two, so reduction terminates. We prove uniqueness by induction on the total degree of a monomial. If two possible first replacements use the same index, their results agree. If they use distinct indices and , write the monomial as . The two replacements give and . In the first expression replace the displayed factor, and in the second replace the displayed factor. Both paths reach . Every intermediate monomial has smaller degree than the original one. The induction hypothesis makes all subsequent normal forms equal. Linearity extends the conclusion to polynomials.
Let denote the resulting -linear normal-form map. For a monomial , the defining replacement shows . Hence annihilates the ideal . Each reduction changes a polynomial by an element of this ideal, so belongs to the ideal for every . These two facts show that spans the quotient and that a linear combination of belonging to the ideal must be zero.
This proof works over after any specialization. Moreover, the reduction uses only addition and multiplication of coefficients and the fixed rational factor . Specialization therefore commutes with the entire reduction.
For , let be the matrix of multiplication by in the ordered basis . Its column indexed by consists of the coefficients of . Define
This is a symmetric matrix over . Lemma 5.1 identifies with the trace-form matrix of for every real .
The real trace identity, including multiplicities
We give the finite-dimensional trace argument to account explicitly for multiple zeros. For a finite-dimensional real algebra , the trace form is the symmetric bilinear form
where denotes multiplication by on .
Proposition 6.1 (Hermite trace identity). Let be a nonzero finite-dimensional algebra. The signature of its trace form is the number of distinct real common zeros of .
Proof. Let . The multiplication operators on commute. They are simultaneously upper triangular in a suitable basis. For completeness, a finite commuting family over has a common eigenvector: restrict the family to an eigenspace of one member and continue, decreasing dimension whenever necessary. Its common invariant line gives a commuting family on the quotient. Induction on dimension then gives simultaneous upper triangularization. Applying this to the multiplication operators of a vector-space basis of suffices.
Every diagonal position defines a unital -algebra homomorphism , since diagonal entries add and multiply under upper triangular matrix operations. The values give a common zero of . Let be the finite set of zeros obtained in this way, and let be the number of diagonal positions yielding . Then is a positive integer and
Every complex common zero is in . To prove this, suppose is a common zero outside . There is a polynomial over with and for all . Such a polynomial is obtained by multiplying, for each , a normalized coordinate difference separating and . The matrix is then strictly upper triangular, so . Applying this operator to gives in , contradicting evaluation at . Complex conjugation permutes . It also preserves the multiplicities. Indeed, choose a polynomial that equals one at and zero at the other points of . Conjugation of coefficients gives
By (22), the left side is .
Write for the number of real points of and choose one point from each of its nonreal conjugate pairs. Evaluation defines a surjective real linear map
To see surjectivity, first interpolate arbitrary values at the finite set , assigning conjugate values at conjugate points. Polynomial interpolation at finitely many distinct points follows from the same separating coordinate products. Averaging the interpolating polynomial with its coefficientwise conjugate gives real coefficients and preserves the assigned values.
For real , equation (22) now expresses the trace form as the pullback under (23) of
Each real summand has one positive direction. On , the form has matrix and hence one positive and one negative direction. Choose a real vector-space complement to the kernel of evaluation. Surjectivity identifies the trace form on that complement with (24); the kernel contributes zero directions. The signature is therefore . □
Corollary 6.2. For every real ,
Proof. Lemma 5.1 gives a quotient algebra of dimension at every parameter. Its defining equations are nonzero scalar multiples of the partial derivatives of . Apply Proposition 6.1 and then Proposition 4.1. □
The boundary polynomial and the selected root
Expand the characteristic polynomial as
Since , the following definition is finite and unambiguous.
Definition 7.1. Let be the smallest index for which is a nonzero polynomial, and put .
Lemma 7.2. Every entry of has degree at most in , and
Proof. Consider a diagonal coefficient of multiplication by on the basis element . Reduction starts at total degree . Every step decreases this degree by exactly two. A term contributing to the coefficient of therefore uses exactly
steps. If this number is not an integer, there is no such term. The coefficient introduced by each step has -degree at most one. Thus every contributing coefficient has -degree at most . Taking the trace preserves the bound.
Each coefficient of the determinant in (26) is a sum of products of at most matrix entries. Its degree is at most , which proves (27). □
Lemma 7.3. The signature of is constant on each interval containing no real root of , and .
Proof. If , equation (26) shows that zero is an eigenvalue of algebraic multiplicity exactly . Symmetry identifies this multiplicity with the nullity. The eigenvalues of a continuously varying real symmetric matrix vary continuously. Near a given parameter where , the nonzero eigenvalues retain their signs, and the nullity remains . The signature is consequently locally constant there, and hence constant on every such interval.
If , there would be an interval about on which the signature is constant. Corollary 6.2 gives signature one to the left of and a strictly larger signature to its right, a contradiction. □
Proof of Theorem 1.1. Attainment and the lower bound follow from Lemma 2.1. The one-node integral is 2. Lemma 2.2 and Proposition 2.3 prove the remaining assertions about minimizers. The explicit construction of is (21), using the rational forms (10) and the reduction (19). Definition 7.1 specifies , and Lemma 7.2 gives its degree bound. Since , Lemma 7.3 shows that for some .
For , the rational sample is less than ; for , it is greater than . By Corollary 6.2,
Exactly samples therefore have signature one, proving (4).
Finally, all polynomials and matrices in the construction are obtained by finite rational arithmetic. The index is determined by testing the finitely many rational coefficient polynomials for equality to zero. Univariate real root isolation orders the roots of in and supplies rational samples between them. The signatures of the rational symmetric matrices at those samples are obtained by exact symmetric elimination. These operations terminate for every positive integer . □
Corollary 7.4. For , the number is algebraic over of degree at most
Proof. The minimal polynomial of divides the nonzero polynomial . Apply (27). □
Remark 7.5. Exact symmetric elimination requires only rational operations. At a nonzero diagonal entry, a congruence and its Schur complement remove a one-dimensional block. If all diagonal entries vanish and some off-diagonal entry is nonzero, use the block
which has one positive and one negative eigenvalue, and remove it by a block Schur complement. An all-zero remaining matrix contributes only zero eigenvalues. Dimension decreases at every step, including at singular parameter values.
The two- and three-node cases
The first two nontrivial cases illustrate both the encoding and the selected-root rule. For , one has , , and
Put . The normalized critical equation is , so reduction uses . On the basis , the trace matrix is
The trace moments follow directly from the multiplication matrix: , for , and all odd moments vanish. Expanding the characteristic polynomial gives
Its only real root is , and (4) yields .
For , Proposition 2.3 reduces the configuration to with . Its cardinal polynomials are
Their squared integrals sum to
As a function of , its derivative is
Thus the unique ordered minimizing triple is and . Theorem 1.1 selects this same value from .
Acknowledgments
The authors acknowledge assistance from AI systems developed by OpenAI in mathematical exploration, checking, and preparation of this manuscript.
References
References
- [1]S. Basu, R. Pollack, and M.-F. Roy, Algorithms in Real Algebraic Geometry, second ed., Algorithms and Computation in Mathematics, vol. 10, Springer, Berlin, 2006. doi:10.1007/3-540-33099-2.DOI
- [2]T. F. Bloom (ed.), Erdős Problem 1131, Erdős Problems, online problem collection, accessed November 11, 2026. erdosproblems.com/1131.
- [3]L. Brutman and D. Toledano, An extremal problem of Erdős in interpolation theory, Computers & Mathematics with Applications 34 (1997), no. 12, 37–47. doi:10.1016/S0898-1221(97)00232-0.DOI
- [4]P. Erdős, J. Szabados, A. K. Varma, and P. Vértesi, On an interpolation theoretical extremal problem, Studia Scientiarum Mathematicarum Hungarica 29 (1994), 55–60.
- [5]H. P. Le and M. Safey El Din, Solving parametric systems of polynomial equations over the reals through Hermite matrices, Journal of Symbolic Computation 112 (2022), 25–61. doi:10.1016/j.jsc.2021.12.002; arXiv:2011.14136.DOI
- [6]P. White, Erdős #1131: the four-node minimum, exactly, Erdős Problem a Day, August 11, 2026, online article.