betaFeedback

WorksMathematics

An exact algebraic construction for Erdős's interpolation minimum

Abstract

For distinct nodes in [−1,1][-1,1], 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 n≥2n\geq2, put k=n−1k=n-1 and d=2n(n−1)d=2n(n-1). A rational symmetric polynomial matrix of order (d+1)k(d+1)^k determines a nonzero rational polynomial of degree at most kd(d+1)kkd(d+1)^k. 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 X=(x1,…,xn)X=(x_1,\ldots,x_n) consist of distinct real nodes in [−1,1][-1,1]. Its Lagrange cardinal polynomials are

ℓiX(x)=∏j≠ix−xjxi−xj,1≤i≤n.(1)\ell_i^X(x)=\prod_{j\ne i}\frac{x-x_j}{x_i-x_j}, \qquad1\le i\le n. \tag*{(1)}

We use the empty product convention when n=1n=1. Define

I(X)=∫−11∑i=1nℓiX(x)2 dx,mn=inf⁡xi∈[−1,1]xi≠xj (i≠j)I(X).(2)I(X)=\int_{-1}^{1}\sum_{i=1}^{n}\ell_i^X(x)^2\,dx,\qquad m_n=\inf_{\substack{x_i\in[-1,1]\\x_i\ne x_j\ (i\ne j)}} I(X). \tag*{(2)}

The integral is taken with respect to ordinary Lebesgue measure. The value of I(X)I(X) 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-nn 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 tt is an attained minimum is a first-order formula over Q\mathbb{Q}. Quantifier elimination then describes the singleton {mn}\{m_n\} 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 HH, write

sig⁡H=n+(H)−n−(H),\operatorname{sig} H = n_{+}(H)-n_{-}(H),

where n+(H)n_{+}(H) and n−(H)n_{-}(H) count positive and negative eigenvalues with multiplicity. Zero eigenvalues contribute zero.

Theorem 1.1. For every positive integer nn, the infimum in (2) is attained. For n=1n=1 it equals 2. For n≥2n\ge2, every minimizing node set contains both endpoints, and

2n≤mn<2.(3)\frac{2}{n}\le m_n<2. \tag*{(3)}

Fix n≥2n\ge2 and put

k=n−1,d=2n(n−1),M=(d+1)k.k=n-1,\qquad d=2n(n-1),\qquad M=(d+1)^k.

There are an explicitly defined symmetric polynomial matrix and a nonzero polynomial satisfying

Hn(t)∈Sym⁡M(Q[t]),0≠Rn(t)∈Q[t],deg⁡Rn≤kdM,H_n(t)\in\operatorname{Sym}_M(\mathbb{Q}[t]),\qquad0\ne R_n(t)\in\mathbb{Q}[t],\qquad\deg R_n\le kdM,

constructed in Sections 5 and 7, with the following property. Let r1<⋯<rsr_1<\cdots<r_s be the distinct real roots of RnR_n in (0,2)(0,2), put rs+1=2r_{s+1}=2, and choose rational numbers ρj∈(rj,rj+1)\rho_j\in(r_j,r_{j+1}) for 1≤j≤s1\le j\le s. Then s≥1s\ge1 and

mn=r1+cn,cn=#{j:1≤j≤s, sig⁡Hn(ρj)=1}.(4)m_n=r_{1+c_n},\qquad c_n=\#\{j:1\le j\le s,\ \operatorname{sig} H_n(\rho_j)=1\}. \tag*{(4)}

The construction and the rule depend only on nn 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 SX(x)=∑iℓiX(x)2S_X(x)=\sum_i \ell_i^X(x)^2.

Lemma 2.1. The minimum mnm_n is attained, and mn≥2/nm_n\ge2/n.

Proof. Choose a basis p0,…,pn−1p_0,\ldots,p_{n-1} of the polynomials of degree at most n−1n-1 that is orthonormal for the inner product ⟨f,g⟩=∫−11fg\langle f,g\rangle=\int_{-1}^{1}fg. Let Vij=pj−1(xi)V_{ij}=p_{j-1}(x_i). Distinctness of the nodes makes VV invertible. The coefficient vector of ℓiX\ell_i^X in this basis is V−1eiV^{-1}e_i. Consequently,

I(X)=∥V−1∥F2=tr⁡((VTV)−1).(5)I(X)=\lVert V^{-1}\rVert_F^2=\operatorname{tr}\bigl((V^{T}V)^{-1}\bigr). \tag*{(5)}

Here ∥⋅∥F\lVert\cdot\rVert_F is the Frobenius norm.

Suppose a sequence of ordered configurations tends to a collision in the closed ordered region −1≤x1≤⋯≤xn≤1-1\le x_1\le\cdots\le x_n\le1. The limiting evaluation matrix has two equal rows, so its smallest singular value tends to zero. Since

I(X)≥σmin⁡(V)−2,I(X)\ge\sigma_{\min}(V)^{-2},

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 n=1n=1 the same conclusion follows directly from ℓ1X=1\ell_1^X=1.

The interpolation identity ∑iℓiX(x)=1\sum_i\ell_i^X(x)=1 and the Cauchy–Schwarz inequality give SX(x)≥1/nS_X(x)\ge1/n. Integration proves the lower bound. □

Lemma 2.2. For every n≥2n \ge2, there is a node configuration with I(X)<2I(X) < 2.

Proof. Maximize the Vandermonde product

Δ(X)=∏a<b(xb−xa)\Delta(X) = \prod_{a<b}(x_b-x_a)

on the closed ordered node region. The maximum is positive, hence the maximizing nodes are distinct. Moving the leftmost node to −1-1 strictly increases the product unless it is already there. The corresponding argument at the right gives xn=1x_n=1.

For every interior maximizing node, logarithmic differentiation yields

0=∑j≠i1xi−xj=(ℓiX)′(xi).(6)0 = \sum_{j\ne i}\frac{1}{x_i-x_j} = \bigl(\ell_i^X\bigr)'(x_i). \tag*{(6)}

The polynomial SXS_X equals 1 at each node. At an interior node,

SX′(xi)=2∑jℓjX(xi)(ℓjX)′(xi)=2(ℓiX)′(xi)=0.S_X'(x_i)=2\sum_j\ell_j^X(x_i)\bigl(\ell_j^X\bigr)'(x_i)=2\bigl(\ell_i^X\bigr)'(x_i)=0.

Moreover, SXS_X has degree exactly 2n−22n-2, since its leading coefficient is a sum of positive squares. Counting the endpoint zeros and the double interior zeros of 1−SX1-S_X now gives

1−SX(x)=c(1−x2)∏i=2n−1(x−xi)2,c>0.(7)1-S_X(x)=c(1-x^2)\prod_{i=2}^{n-1}(x-x_i)^2,\qquad c>0. \tag*{(7)}

The sign of cc follows from the leading coefficient. The right-hand side is nonnegative on [−1,1][-1,1] and is positive except at finitely many points. Thus I(X)<2I(X)<2.

Proposition 2.3. Every minimizing node set with n≥2n\ge2 contains −1-1 and 11.

Proof. Let XX be a minimizing configuration with hull [a,b][a,b], and put L=b−a>0L=b-a>0. For x<ax<a, every factor of

ℓ1X(x)=∏j>1x−xja−xj\ell_1^X(x)=\prod_{j>1}\frac{x-x_j}{a-x_j}

is greater than one. Thus SX(x)>1S_X(x)>1 on [−1,a)[-1,a). The same argument with ℓnX\ell_n^X gives SX(x)>1S_X(x)>1 on (b,1](b,1].

Suppose L<2L<2, and write

A=∫abSX(x) dx,B=∫[−1,1]∖[a,b]SX(x) dx.A=\int_a^b S_X(x)\,dx,\qquad B=\int_{[-1,1]\setminus[a,b]}S_X(x)\,dx.

Then B>2−LB>2-L. Lemma 2.2 gives A+B=mn<2A+B=m_n<2, so A<LA<L. The affine map from [a,b][a,b] onto [−1,1][-1,1] carries XX to an admissible configuration YY. Its cardinal polynomials transform by composition, and change of variables gives I(Y)=2A/LI(Y)=2A/L. Consequently,

I(X)−I(Y)=B−2−LLA>(2−L)(1−AL)>0,I(X)-I(Y)=B-\frac{2-L}{L}A>(2-L)\left(1-\frac{A}{L}\right)>0,

contradicting minimality. Hence L=2L=2, which forces a=−1a=-1 and b=1b=1.

The affine hull argument also occurs in the exact four-node analysis of White [6]. Proposition 2.3 gives the reduction for every n≥2n\ge2.

A rational homogeneous encoding

Fix n≥2n \ge2, and retain k=n−1k=n-1 and d=2n(n−1)d=2n(n-1). For u=(u1,…,uk)u=(u_1,\ldots,u_k) define

ga=ua2,T=∑a=1kga,Yi=−T+2∑a<iga(1≤i≤n).(8)g_a=u_a^2,\qquad T=\sum_{a=1}^{k}g_a,\qquad Y_i=-T+2\sum_{a<i}g_a\quad(1\le i\le n). \tag*{(8)}

In particular, Y1=−TY_1=-T, Yn=TY_n=T, and Yi+1−Yi=2ui2Y_{i+1}-Y_i=2u_i^2. For an nn-tuple yy, let y(i,w)y^{(i,w)} denote the tuple obtained by replacing its iith entry by ww.

Define the Q[u]\mathbb{Q}[u]-linear functional Lz\mathcal{L}_z on Q[u,z]\mathbb{Q}[u,z] by

Lz(zj)={2/(j+1),j even,0,j odd.(9)\mathcal{L}_z(z^j)= \begin{cases} 2/(j+1), & j\text{ even},\\ 0, & j\text{ odd}. \end{cases} \tag*{(9)}

Thus Lz\mathcal{L}_z is integration in zz over [−1,1][-1,1]. Put

D(u)=Δ(Y)2,N(u)=∑i=1nLz(Δ(Y(i,Tz))2).(10)D(u)=\Delta(Y)^2,\qquad N(u)=\sum_{i=1}^{n}\mathcal{L}_z\left(\Delta\left(Y^{(i,Tz)}\right)^2\right). \tag*{(10)}

These are rational homogeneous forms of degree dd. Indeed, every entry of YY and the replacement TzTz has uu-degree two, and the Vandermonde has degree n(n−1)/2n(n-1)/2 in its entries.

Lemma 3.1. For real uu with every coordinate nonzero,

N(u)D(u)=I(Y1/T,…,Yn/T).(11)\frac{N(u)}{D(u)}=I(Y_1/T,\ldots,Y_n/T). \tag*{(11)}

Every ordered configuration with endpoints −1-1 and 11 arises in this way. For every real uu, D(u)≥0D(u)\ge0 and N(u)≥0N(u)\ge0, and D(u)=0D(u)=0 precisely when some ua=0u_a=0.

Proof. If all coordinates are nonzero, then T>0T>0 and (8) gives strictly increasing normalized nodes with the required endpoints. For any distinct-node tuple xx, the Vandermonde replacement identity is

ℓix(z)=Δ(x(i,z))Δ(x).\ell_i^x(z)=\frac{\Delta\left(x^{(i,z)}\right)}{\Delta(x)}.

Scaling all entries by TT shows that this ratio for x=Y/Tx=Y/T equals Δ(Y(i,Tz))/Δ(Y)\Delta\left(Y^{(i,Tz)}\right)/\Delta(Y). Squaring, summing, and integrating gives (11).

Conversely, for ordered nodes with these endpoints choose

ua=xa+1−xa2.u_a=\sqrt{\frac{x_{a+1}-x_a}{2}}.

Then T=1T=1 and Yi=xiY_i=x_i. Finally, DD is a square, and its zero set is determined by the successive differences 2ua22u_a^2. Each summand defining NN is the integral of a real square, which proves its nonnegativity even when several gaps vanish. □\square

For a real parameter tt, define

Pt(u)=N(u)−tD(u).(12)P_t(u)=N(u)-tD(u). \tag*{(12)}

Proposition 3.2. For every real tt,

Pt(u)≥0 for every u∈Rk⟺t≤mn.(13)P_t(u)\ge0\text{ for every }u\in\mathbb{R}^k\quad\Longleftrightarrow\quad t\le m_n. \tag*{(13)}

Proof. If t≤mnt\le m_n and D(u)>0D(u)>0, Lemma 3.1 gives Pt(u)=D(u)(I(Y/T)−t)≥0P_t(u)=D(u)(I(Y/T)-t)\ge0. At every remaining real point, D(u)=0D(u)=0 and Pt(u)=N(u)≥0P_t(u)=N(u)\ge0.

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 Pt(u)≥0P_t(u)\ge0 implies mn≥tm_n\ge t. □\square

Detecting the threshold by critical points

Set

Qt(u)=Pt(u)+∑a=1kuad+2.(14)Q_t(u) = P_t(u) + \sum_{a=1}^{k} u_a^{d+2}. \tag*{(14)}

Since dd is even, the added form is strictly positive away from the origin.

Proposition 4.1. The polynomial QtQ_t is coercive for every real tt, and

{u∈Rk:∇Qt(u)=0}={0}⟺t≤mn.(15)\{u \in\mathbb{R}^k : \nabla Q_t(u) = 0\} = \{0\} \quad\Longleftrightarrow\quad t \le m_n. \tag*{(15)}

Proof. On the unit sphere, ∑auad+2\sum_a u_a^{d+2} has a positive minimum, while ∣Pt(u)∣|P_t(u)| has a finite maximum. Homogeneity therefore gives constants c>0c > 0 and Ct≥0C_t \ge0 such that

Qt(u)≥c∥u∥d+2−Ct∥u∥d.Q_t(u) \ge c\lVert u\rVert^{d+2} - C_t\lVert u\rVert^d.

This proves coercivity. In particular, QtQ_t attains a global minimum. The origin is a critical point because d≥4d \ge4.

If t>mnt > m_n, Proposition 3.2 gives vv with Pt(v)<0P_t(v) < 0. For sufficiently small s>0s > 0,

Qt(sv)=sd(Pt(v)+s2∑avad+2)<0.Q_t(sv) = s^d\left(P_t(v) + s^2\sum_a v_a^{d+2}\right) < 0.

A global minimizer of QtQ_t is then a nonzero real critical point.

Conversely, at a nonzero real critical point vv, Euler’s identity gives

0=v⋅∇Qt(v)=dPt(v)+(d+2)∑avad+2.(16)0 = v \cdot\nabla Q_t(v) = dP_t(v) + (d+2)\sum_a v_a^{d+2}. \tag*{(16)}

The last sum is positive, so Pt(v)<0P_t(v) < 0. By Proposition 3.2, this implies t>mnt > m_n. □

Remark 4.2. At a nonzero real critical point, all gap coordinates are nonzero. Indeed, Pt(v)<0P_t(v) < 0 is incompatible with the nonnegativity of NN on D=0D = 0. 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 Q[t]\mathbb{Q}[t], write P(u,t)=N(u)−tD(u)P(u,t) = N(u) - tD(u) and set

hi(u,t)=−1d+2∂P∂ui(u,t),fi(u,t)=uid+1−hi(u,t).(17)h_i(u,t) = -\frac{1}{d+2}\frac{\partial P}{\partial u_i}(u,t), \qquad f_i(u,t) = u_i^{d+1} - h_i(u,t). \tag*{(17)}

Thus fi=(d+2)−1∂Qt/∂uif_i = (d+2)^{-1}\partial Q_t/\partial u_i. Each hih_i is homogeneous of uu-degree d−1d-1 and has coefficients affine in tt. For a multi-index, write ∣α∣=∑iαi|\alpha| = \sum_i \alpha_i. Fix the lexicographic order on the set

B={uα:α∈{0,1,…,d}k},∣B∣=M=(d+1)k.(18)\mathcal{B} = \{u^\alpha: \alpha\in\{0,1,\ldots,d\}^k\}, \qquad|\mathcal{B}| = M = (d+1)^k. \tag*{(18)}

The reduction rule is

uid+1⟼hi(u,t).(19)u_i^{d+1} \longmapsto h_i(u,t). \tag*{(19)}

Lemma 5.1. Reduction by (19) terminates and gives a unique normal form in the span of B\mathcal{B}. The residue classes of B\mathcal{B} form a basis of

A=Q[t,u1,…,uk]/(f1,…,fk)(20)\mathcal{A} = \mathbb{Q}[t,u_1,\ldots,u_k]/(f_1,\ldots,f_k) \tag*{(20)}

as a Q[t]\mathbb{Q}[t]-module. For every real τ\tau, the same monomials form a basis of

Aτ=R[u1,…,uk]/(f1(u,τ),…,fk(u,τ)),\mathcal{A}_\tau= \mathbb{R}[u_1,\ldots,u_k]/(f_1(u,\tau),\ldots,f_k(u,\tau)),

and normal forms commute with specialization t=τt = \tau.

Proof. Every replacement reduces total uu-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 ii and jj, write the monomial as uid+1ujd+1vu_i^{d+1}u_j^{d+1}v. The two replacements give hiujd+1vh_i u_j^{d+1}v and uid+1hjvu_i^{d+1}h_jv. In the first expression replace the displayed ujd+1u_j^{d+1} factor, and in the second replace the displayed uid+1u_i^{d+1} factor. Both paths reach hihjvh_i h_jv. 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 NF⁡\operatorname{NF} denote the resulting Q[t]\mathbb{Q}[t]-linear normal-form map. For a monomial vv, the defining replacement shows NF⁡(vfi)=0\operatorname{NF}(vf_i)=0. Hence NF⁡\operatorname{NF} annihilates the ideal (f1,…,fk)(f_1,\ldots,f_k). Each reduction changes a polynomial by an element of this ideal, so p−NF⁡(p)p-\operatorname{NF}(p) belongs to the ideal for every pp. These two facts show that B\mathcal{B} spans the quotient and that a linear combination of B\mathcal{B} belonging to the ideal must be zero.

This proof works over R\mathbb{R} after any specialization. Moreover, the reduction uses only addition and multiplication of coefficients and the fixed rational factor (d+2)−1(d+2)^{-1}. Specialization therefore commutes with the entire reduction. □\square

For g∈Q[t,u]g\in\mathbb{Q}[t,u], let Mg(t)M_g(t) be the matrix of multiplication by gg in the ordered basis B\mathcal{B}. Its column indexed by uβu^\beta consists of the coefficients of NF⁡(guβ)\operatorname{NF}(gu^\beta). Define

Hn(t)α,β=tr⁡(Muα+β(t)),uα,uβ∈B.(21)H_n(t)_{\alpha,\beta}=\operatorname{tr}(M_{u^{\alpha+\beta}}(t)),\qquad u^\alpha,u^\beta\in\mathcal{B}. \tag*{(21)}

This is a symmetric matrix over Q[t]\mathbb{Q}[t]. Lemma 5.1 identifies Hn(τ)H_n(\tau) with the trace-form matrix of AτA_\tau for every real τ\tau.

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 AA, the trace form is the symmetric bilinear form

(a,b)⟼tr⁡(Lab),(a,b)\longmapsto\operatorname{tr}(L_{ab}),

where LcL_c denotes multiplication by cc on AA.

Proposition 6.1 (Hermite trace identity). Let A=R[u1,…,uk]/JA=\mathbb{R}[u_1,\ldots,u_k]/J be a nonzero finite-dimensional algebra. The signature of its trace form is the number of distinct real common zeros of JJ.

Proof. Let AC=A⊗RCA_{\mathbb{C}}=A\otimes_{\mathbb{R}}\mathbb{C}. The multiplication operators on ACA_{\mathbb{C}} commute. They are simultaneously upper triangular in a suitable basis. For completeness, a finite commuting family over C\mathbb{C} 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 ACA_{\mathbb{C}} suffices.

Every diagonal position defines a unital C\mathbb{C}-algebra homomorphism χ:AC→C\chi:A_{\mathbb{C}}\to\mathbb{C}, since diagonal entries add and multiply under upper triangular matrix operations. The values χ(ui)\chi(u_i) give a common zero of JJ. Let ZZ be the finite set of zeros obtained in this way, and let mζm_\zeta be the number of diagonal positions yielding ζ\zeta. Then mζm_\zeta is a positive integer and

tr⁡(Lg)=∑ζ∈Zmζg(ζ)(g∈AC).(22)\operatorname{tr}(L_g)=\sum_{\zeta\in Z}m_\zeta g(\zeta)\qquad(g\in A_{\mathbb{C}}). \tag*{(22)}

Every complex common zero is in ZZ. To prove this, suppose ww is a common zero outside ZZ. There is a polynomial qq over C\mathbb{C} with q(w)=1q(w)=1 and q(ζ)=0q(\zeta)=0 for all ζ∈Z\zeta\in Z. Such a polynomial is obtained by multiplying, for each ζ\zeta, a normalized coordinate difference separating ww and ζ\zeta. The matrix LqL_q is then strictly upper triangular, so Lqdim⁡A=0L_q^{\dim A}=0. Applying this operator to 11 gives qdim⁡A=0q^{\dim A}=0 in ACA_{\mathbb{C}}, contradicting evaluation at ww. Complex conjugation permutes ZZ. It also preserves the multiplicities. Indeed, choose a polynomial qζq_\zeta that equals one at ζ\zeta and zero at the other points of ZZ. Conjugation of coefficients gives

tr⁡(Lqζ‾)=tr⁡(Lqζ)‾=mζ.\operatorname{tr}(L_{\overline{q_\zeta}})=\overline{\operatorname{tr}(L_{q_\zeta})}=m_\zeta.

By (22), the left side is mζ‾m_{\overline{\zeta}}.

Write rr for the number of real points of ZZ and choose one point from each of its cc nonreal conjugate pairs. Evaluation defines a surjective real linear map

A⟶Rr×Cc.(23)A \longrightarrow\mathbb{R}^{r} \times\mathbb{C}^{c}. \tag*{(23)}

To see surjectivity, first interpolate arbitrary values at the finite set ZZ, 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 a,ba,b, equation (22) now expresses the trace form as the pullback under (23) of

∑ζ realmζa(ζ)b(ζ)+∑{ζ,ζ‾}2mζRe⁡(a(ζ)b(ζ)).(24)\sum_{\zeta\ \mathrm{real}}m_\zeta a(\zeta)b(\zeta)+\sum_{\{\zeta,\overline{\zeta}\}}2m_\zeta\operatorname{Re}(a(\zeta)b(\zeta)). \tag*{(24)}

Each real summand has one positive direction. On C≅R2\mathbb{C}\cong\mathbb{R}^{2}, the form 2mRe⁡(zw)2m\operatorname{Re}(zw) has matrix diag⁡(2m,−2m)\operatorname{diag}(2m,-2m) 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 rr. □

Corollary 6.2. For every real tt,

sig⁡Hn(t)=#{u∈Rk:∇Qt(u)=0},sig⁡Hn(t)=1⟺t≤mn.(25)\operatorname{sig} H_n(t)=\#\{u\in\mathbb{R}^{k}:\nabla Q_t(u)=0\},\qquad\operatorname{sig} H_n(t)=1\Longleftrightarrow t\le m_n. \tag*{(25)}

Proof. Lemma 5.1 gives a quotient algebra of dimension MM at every parameter. Its defining equations are nonzero scalar multiples of the partial derivatives of QtQ_t. Apply Proposition 6.1 and then Proposition 4.1. □

The boundary polynomial and the selected root

Expand the characteristic polynomial as

Cn(t,λ)=det⁡(λIM−Hn(t))=∑j=0Mcj(t)λj.(26)C_n(t,\lambda)=\det(\lambda I_M-H_n(t))=\sum_{j=0}^{M}c_j(t)\lambda^j. \tag*{(26)}

Since cM=1c_M=1, the following definition is finite and unambiguous.

Definition 7.1. Let ee be the smallest index for which ce(t)c_e(t) is a nonzero polynomial, and put Rn(t)=ce(t)R_n(t)=c_e(t).

Lemma 7.2. Every entry of Hn(t)H_n(t) has degree at most kdkd in tt, and

deg⁡Rn≤kdM.(27)\deg R_n\le kdM. \tag*{(27)}

Proof. Consider a diagonal coefficient of multiplication by uα+βu^{\alpha+\beta} on the basis element uγu^\gamma. Reduction starts at total degree ∣α∣+∣β∣+∣γ∣|\alpha|+|\beta|+|\gamma|. Every step decreases this degree by exactly two. A term contributing to the coefficient of uγu^\gamma therefore uses exactly

∣α∣+∣β∣2≤kd\frac{|\alpha|+|\beta|}{2}\le kd

steps. If this number is not an integer, there is no such term. The coefficient introduced by each step has tt-degree at most one. Thus every contributing coefficient has tt-degree at most kdkd. Taking the trace preserves the bound.

Each coefficient of the determinant in (26) is a sum of products of at most MM matrix entries. Its degree is at most kdMkdM, which proves (27). □

Lemma 7.3. The signature of Hn(t)H_n(t) is constant on each interval containing no real root of RnR_n, and Rn(mn)=0R_n(m_n)=0.

Proof. If Rn(t)≠0R_n(t) \ne0, equation (26) shows that zero is an eigenvalue of algebraic multiplicity exactly ee. Symmetry identifies this multiplicity with the nullity. The eigenvalues of a continuously varying real symmetric matrix vary continuously. Near a given parameter where Rn≠0R_n \ne0, the nonzero eigenvalues retain their signs, and the nullity remains ee. The signature is consequently locally constant there, and hence constant on every such interval.

If Rn(mn)≠0R_n(m_n) \ne0, there would be an interval about mnm_n on which the signature is constant. Corollary 6.2 gives signature one to the left of mnm_n 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 HnH_n is (21), using the rational forms (10) and the reduction (19). Definition 7.1 specifies RnR_n, and Lemma 7.2 gives its degree bound. Since 0<mn<20<m_n<2, Lemma 7.3 shows that mn=rhm_n=r_h for some 1≤h≤s1\le h\le s.

For j<hj<h, the rational sample ρj\rho_j is less than mnm_n; for j≥hj\ge h, it is greater than mnm_n. By Corollary 6.2,

sig⁡Hn(ρj)=1⟺j<h.\operatorname{sig} H_n(\rho_j)=1 \quad\Longleftrightarrow\quad j<h.

Exactly h−1h-1 samples therefore have signature one, proving (4).

Finally, all polynomials and matrices in the construction are obtained by finite rational arithmetic. The index ee is determined by testing the finitely many rational coefficient polynomials for equality to zero. Univariate real root isolation orders the roots of RnR_n in (0,2)(0,2) 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 nn. □

Corollary 7.4. For n≥2n\ge2, the number mnm_n is algebraic over Q\mathbb{Q} of degree at most

2n(n−1)2(2n(n−1)+1)n−1.2n(n-1)^2\left(2n(n-1)+1\right)^{n-1}.

Proof. The minimal polynomial of mnm_n divides the nonzero polynomial RnR_n. 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 bb is nonzero, use the block

(0bb0)\begin{pmatrix}0&b\\b&0\end{pmatrix}

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 n=2n=2, one has k=1k=1, d=4d=4, and

D(u)=4u4,N(u)=163u4.D(u)=4u^4,\qquad N(u)=\frac{16}{3}u^4.

Put a=83(t−43)a=\frac{8}{3}\left(t-\frac{4}{3}\right). The normalized critical equation is u5−au3=0u^5-au^3=0, so reduction uses u5=au3u^5=au^3. On the basis 1,u,u2,u3,u41,u,u^2,u^3,u^4, the trace matrix is

H2(t)=(502a02a202a02a202a02a202a302a202a302a202a302a4)(28)H_2(t)= \begin{pmatrix} 5 & 0 & 2a & 0 & 2a^2 \\ 0 & 2a & 0 & 2a^2 & 0 \\ 2a & 0 & 2a^2 & 0 & 2a^3 \\ 0 & 2a^2 & 0 & 2a^3 & 0 \\ 2a^2 & 0 & 2a^3 & 0 & 2a^4 \end{pmatrix} \tag*{(28)}

The trace moments follow directly from the multiplication matrix: tr⁡(M1)=5\operatorname{tr}(M_1)=5, tr⁡(Mu2j)=2aj\operatorname{tr}(M_{u^{2j}})=2a^j for j≥1j \ge1, and all odd moments vanish. Expanding the characteristic polynomial gives

R2(t)=−12a3(1+a2)2.R_2(t)=-12a^3(1+a^2)^2.

Its only real root is t=4/3t=4/3, and (4) yields m2=4/3m_2=4/3.

For n=3n=3, Proposition 2.3 reduces the configuration to (−1,y,1)(-1,y,1) with −1<y<1-1<y<1. Its cardinal polynomials are

(x−y)(x−1)2(1+y),1−x21−y2,(x+1)(x−y)2(1−y).\frac{(x-y)(x-1)}{2(1+y)},\qquad\frac{1-x^2}{1-y^2},\qquad\frac{(x+1)(x-y)}{2(1-y)}.

Their squared integrals sum to

I(−1,y,1)=43−43(1−y2)+8(3+y2)15(1−y2)2(29)I(-1,y,1)=\frac{4}{3}-\frac{4}{3(1-y^2)}+\frac{8(3+y^2)}{15(1-y^2)^2} \tag*{(29)}

As a function of s=y2∈[0,1)s=y^2\in[0,1), its derivative is

36+28s15(1−s)3>0.\frac{36+28s}{15(1-s)^3}>0.

Thus the unique ordered minimizing triple is (−1,0,1)(-1,0,1) and m3=8/5m_3=8/5. Theorem 1.1 selects this same value from R3R_3.

Acknowledgments

The authors acknowledge assistance from AI systems developed by OpenAI in mathematical exploration, checking, and preparation of this manuscript.

References

References

  1. [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. [2]T. F. Bloom (ed.), Erdős Problem 1131, Erdős Problems, online problem collection, accessed November 11, 2026. erdosproblems.com/1131.
  3. [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. [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. [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. [6]P. White, Erdős #1131: the four-node minimum, exactly, Erdős Problem a Day, August 11, 2026, online article.

Paper details

vlnc:W_772naw7x
Version
v1 · latest
Published
Fresh — published within the last 30 days
License
CC BY 4.0
Usage

views · 9

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

AI systems developed by OpenAI

View statement
Looking for related papers…
Contents