View of Explicit algebraic solution of Zolotarev's First Problem for low-degree polynomials

J. Numer. Anal. Approx. Theory, vol. 48 (2019) no. 2, pp. 175–201 ictp.acad.ro/jnaat

EXPLICIT ALGEBRAIC SOLUTION OF ZOLOTAREV’S FIRST PROBLEM FOR LOW-DEGREE POLYNOMIALS

HEINZ-JOACHIM RACK^∗and ROBERT VAJDA^†

Abstract. E.I. Zolotarev’s classical so-called First Problem (ZFP), which was posed to him by P.L. Chebyshev, is to determine, for a given n ∈ N\{1} and for a givens∈R\{0}, the monic polynomial solutionZn,s^∗ to the following best approximation problem: Find

min

a_k max

x∈[−1,1]|a0+a1x+· · ·+an−2xⁿ⁻²+ (−ns)xⁿ⁻¹+xⁿ|,

where the ak, 0 ≤ k ≤ n−2, vary in R. It suffices to consider the cases s >tan²(π/(2n)).

In 1868 Zolotarev provided a transcendental solution for alln≥2 in terms of elliptic functions. An explicit algebraic solution in power form toZFP, as is suggested by the problem statement, is available only for 2≤n≤5.¹ We have now obtained an explicit algebraic solution toZFPfor 6≤n≤12 in terms of roots of dedicated polynomials.

In this paper, we provide our findings for 6 ≤ n ≤ 7 in two alternative fashions, accompanied by concrete examples. The cases 8≤n ≤12 we treat, due to their bulkiness, in a separate web repository.

1Added in proof: But see our recent one-parameter power form solution for n= 6 in [38].

MSC 2010. 41A10, 41A29, 41A50.

Keywords. Abel-Pell differential equation, algebraic solution, best approxima- tion, Chebyshev, first problem, Groebner basis, least deviation from zero, Maly- shev, polynomial, proper, Schiefermayr, two fixed leading coefficients, uniform norm, Zolotarev.

1. INTRODUCTION AND HISTORICAL REMARKS

Let I = [−1,1] ⊂ R denote the unit interval and let Tn denote the n- th Chebyshev polynomial of the first kind with respect to I. Chebyshev’s classical extremal problem (CEP) of 1854 [8] is to determine among all monic

∗Dr. Rack Consulting GmbH, Steubenstrasse 26a, 58097 Hagen, Germany, e-mail:

[email protected].

†Bolyai Institute, University of Szeged, Aradi Vertanuk tere 1, 6720 Szeged, Hungary, e-mail: [email protected]. The work of this author has been supported by the Ministry of Human Capacities, Hungary, grant 20391-3/2018/FEKUSTRAT and the EU- funded Hungarian grant EFOP-3.6.1-16-2016-00008.

polynomials of degree n≥1, given by

(1.1) Pn(x) =

n−1

X

k=0

a_k,nx^k+xⁿ,

whereak,n∈Rare arbitrary coefficients (andan,n= 1 is fixed), that particular one, call it T_n^∗, which deviates least from the zero-function on I measured in the uniform normk · k∞. Chebyshev found that the solution T_n^∗ is given onI by

(1.2) T_n^∗(x) =

n−1

X

k=0

a^∗_k,nx^k+xⁿ= 2¹⁻ⁿTn(x) = 2¹⁻ⁿcos(narccos(x)), with least deviation kT_n^∗k_∞ = 2¹⁻ⁿ and known optimal coefficients a^∗_k,n, see [25, p. 384] or [39, p. 6, p. 67] for details.

In 1867 Chebyshev himself proposed to his student Zolotarev, see [52, p. 2], an extension of CEP by requiring that not only the first but also the second leading coefficient, an−1,n, is to be kept fixed. This extended CEP, which was later renamed as Zolotarev’s first problem (ZFP), can be stated as follows:

To determine among all polynomials of degree n≥2, represented as

(1.3) Pn,s(x) =

n−2

X

k=0

a_k,nx^k+ (−ns)xⁿ⁻¹+xⁿ

where s∈R\{0} is prescribed, that particular one, call it Z_n,s^∗ , with (1.4) Z_n,s^∗ (x) =

n−2

X

k=0

a^∗_k,n(s)x^k+ (−ns)xⁿ⁻¹+xⁿ,

which deviates least from the zero-function on I in the uniform norm k · k_∞. Or put alternatively, the goal is to determine, for a prescribed s, the best uniform approximation on I to (−ns)xⁿ⁻¹ + xⁿ by polynomials of degree

< n−1. It is well-known that one may restrict the parameterstos >0, and that for 0< s≤tan²(π/(2n)) the solution is given by a distortedT_n^∗ (see e.g.

[1, p. 16], [2, p. 280], [7], [25, p. 405] for details), and is called an improper monic Zolotarev polynomial. However, fors >tan²(π/(2n)), the solutionZ_n,s^∗ to ZFP is considered as very complicated (see e.g. [7], [25, p. 407], [28]) or even as mysterious [47], and is called a proper [49, p. 160], orhard-core [40]

monic Zolotarev polynomial. Here we shall confine ourselves to proper monic Zolotarev polynomials, noting that 0<tan²(π/(2n))<1 holds forn >2, and writingZ_n,s in place of Z_n,s^∗ , ifs >tan²(π/(2n)) is not specified.

Zolotarev provided a solution to ZFPin 1868 [51], and in a reworked form in 1877 [52], where he was considering altogether four extremal problems, of which ZFP was the first in the row (hence the name). Much to the surprise of his contemporaries, as well as of today’s students, Zolotarev presented the proper Zn,s in terms of elliptic functions (see e.g. [1, p. 18], [2, p. 280], [7], [10], [25, p. 407], [31]) rather than, as is suggested by the task, in terms of

explicit optimal coefficients of an algebraic polynomial in power form. When compared to the two-fold solution (1.2) of CEP, Zolotarev’s unwieldy [46, p. 118] elliptic (or transcendental) solution of ZFP would correspond to the trigonometric right-hand solution in (1.2) without providing an equivalent algebraic left-hand term. The following statement by A. A. Markov [23, p.

264] indicates a reservation about Zolotarev’s elliptic solution: Being based on the application of elliptic functions, Zolotarev’s solution is too complicated to be useful in practice.

It is tempting to derive an algebraic solution to ZFP from the elliptic so- lution. However, even for the first reasonable polynomial degree n = 2 this path turns out be unexpectedly complicated, see [7] for details. Therefore, alternative solution paths have been pursued to determine the properZn,s al- gebraically. For example,A. A. Markov himself tried to employ the theory of continued fractions in order to find an algebraic solution [to ZFP], but he was not fully successful, because an algebraic solution requires an amazing amount of calculations, as is remarked in [20, p. 932]. Actually, explicit algebraic so- lutions to ZFP (in terms of parameterized coefficients) are known only for polynomial degrees 2 ≤ n ≤ 5, see Section 2. Added in proof: But see our recent one-parameter power form solution forn= 6 in [38].

The purpose of the present paper is to provide new explicit algebraic solu- tions toZFPfor polynomial degrees 6≤n≤12. To this end, we shall explore in some detail two different solution paths forn= 6 and for n= 7. The first one is based on the Abel-Pell differential equation which must be satisfied by Zn,s and computes Groebner bases with the computer algebra system Mathe- matica™ [50] to actually construct it. The second solution path, also backed by Mathematica, expresses Zn,s tentatively as Zn,α,β, a form which depends on two parameters α and β, so that Z_n,α,β can be stored, once and for all, in an electronic library. Upon assigning a fixed s >tan²(π/(2n)), α and β can then be conveyed to real numbers so that Zn,α,β turns intoZ_n,s^∗ . Both of our approaches have in common that for a givens∈Qthe optimal coefficients of Z_n,s^∗ can be expressed explicitly by means of root objects of dedicated inte- ger polynomials. Because of the growing bulkiness of the intermediate results needed to compute Z_n,s where n ≥ 8, we will transfer our findings for the polynomial degrees 8≤n≤12 to a web repository [53], see also Section6.

Ours is not the first investigation of an algebraic solution toZFP. In 2004 A.

Shadrin [42] remarked: Recently, the interest in an explicit algebraic solution of ZFP was revived in the papers [21], [27], [45], but it is only Malyshev who demonstrates how his theory can be applied to some explicit constructions for particularn. But actually V. A. Malyshev [21], see also [20], provided explicit constructions only for 2 ≤ n ≤ 5 by deploying certain pairs of polynomials, parameterized by s, which are key to the determination of the parameters α and β when sis prescribed. We coin them Malyshev polynomials and will be taking advantage of them in our solution. To this end, we will have to calculate

their coefficients for 6≤n≤12. Malyshev [21] had predicted (correctly, as we have now verified) only their degrees for 6≤n≤8, but did not communicate their coefficients. Further papers relevant toZFP are [18], [29], [30], [41] and [44], see also Section 2. We have benefited from [41] where a methodical algebraic approach to ZFP based on well-defined determinants is provided:

A tentative expression of Z_n,s is given in the parametric form Z_{n,α,β,y1,...,ym} and algorithmic steps are delineated how to compute the parameters. By modifying these steps, we eliminate the parametersy1, . . . , ym. The remaining parameters α and β we then determine as roots of the Malyshev polynomials and that eventually leads to Zn,s.

The provision of a solution toZFPforn >5 via computer algebra methods has been stated as an open problem in [16]. Based on an advanced computer algebra strategy, the conference paper [17] claims to have algebraically solved ZFPfor 6≤n≤12. We do not share this view, since the theoretical strategy in [17] appears not granulated finely enough for the purpose of enabling the construction of Z_n,s^∗ for a given n and s (e.g. n = 6 and s = 1/8, see our example below), the more so as no concrete solution formulas are provided in [17]. But we leave it to the reader to form an opinion.

We point out that in none of the references quoted in the present paper the following of our findings, for 6≤n≤12, are revealed: Explicit tentative rep- resentations Z_n,α,β of Z_n,s, explicit coefficients of the Malyshev polynomials, granulated algorithmic steps (accompanied by examples) for the recursive or direct creation of the optimal coefficients a_k,n(s) ofZ_n,s, and a representation of the a_k,n(s) as root objects of dedicated integer polynomials if s∈Q.

The first-named author has presented a poster onZFPat the IX Jaen Con- ference on Approximation Theory (Spain, July 2018) [36] and each of us has given a talk on ZFP at the Fourth International Conference on Numerical Analysis and Approximation Theory (NAAT, Cluj-Napoca, Romania, Sep- tember 2018) [37,48]. We have agreed to publish our individual findings in a joint manuscript.

2. KNOWN EXPLICIT ALGEBRAIC SOLUTIONS TOZFP^FOR2≤n≤5 The demand for a description of the solution to ZFPwithout elliptic func- tions has been vibrant from the outset. Scaled proper Zolotarev polynomials, for 2 ≤ n ≤ 4, given in an algebraic power form, found application already in the proof of the famous Markov inequalities [22], [24]. Algebraic expres- sions for scaled proper Zolotarev polynomials (with uniform norm 1 onI) for 2≤n≤4 can be found in [7], [9], [12], [13], [14], [18], [26, p. 156], [33], [35], [42], [49, p. 98] (the latter with respect to [0,1]). The case n = 4 (rational parametrization) is of particular interest, see [34, p. 160].

The case n = 5 (radical parametrization) has been settled only quite re- cently in [12], [13], [14], see also [35]. A partial result forn= 5 is due to [9].

These polynomials, whose coefficients depend injectively on one parameter,

are expressed, for 2≤n≤5, in the analytic form (2.1)

n

X

k=0

a_k,n(t)x^k, with an,n(t)6= 0 and parameter t∈In, where I_n denotes a dedicated open interval. To deduce, for a given s >

tan²(π/(2n)), from (2.1) a proper Zolotarev polynomial Z_n,s^∗ according to (1.4), one may proceed as follows (see also [10, Theorem 3]): Divide (2.1) by the coefficienta_n,n(t) yielding^Pn−1_k=0b_k,n(t)x^k+xⁿ; then equatebn−1,n(t) with (−ns) and solve fort; insert the solutiont=t^∗∈I_n into^Pn−1_k=0b_k,n(t)x^k+xⁿ to get Z_n,s^∗ . An example of such a deduction, for n = 5 and s = 2, is given in [35, Chapter 5]. To determine Z_n,s^∗ for a given n > 5 and for an assigned fixed s >tan²(π/(2n)) in the way just sketched would be an elegant path to solveZFPavoiding elliptic functions. However, to the best of our knowledge, analytical forms (2.1) for (scaled) proper Zolotarev polynomials currently do not exist if n > 5, see also [43, p. 1185]. Added in proof: But see our recent one-parameter power form solution for n= 6 in [38].

Regrettably, the contrary is claimed elsewhere. But the sextic scaled monic polynomial given in [14, Section 4.5], (see also [12, Section 4.5]) and the com- position of Chebyshev with scaled proper Zolotarev polynomials, as given in [14, Corollary 4.3], (see also [13, Corollary 2.2], and [35, Remark 9]), do not alternate on I exactly as many times as the degree indicates, and hence they cannot be proper (scaled) Zolotarev polynomials, see also Section 3below.

3. PRELIMINARIES

It is well known (seee.g. [2], [10], [42], [45]) that a proper monic Zolotarev polynomial Zn,s (where s >tan²(π/(2n))) has nequioscillation points on I, including the endpoints ±1, at which it takes its uniform normL:=kZ_n,sk_∞ with alternating sign. For definiteness we assume that in particular, at x =

−1 the value (−1)ⁿL is attained and at x = 1 the value −L is attained.

Additionally, there exists an interval [α, β] with

(3.1) 1< α=α(s)< β=β(s) and β >1 + 2 tan² _2n^π

such that at x = α the value −L is attained and at x = β the value L is attained, and at

(3.2) x=γ := (α+β−2s)/2 with 1< γ < α

there vanishes Z_n,s⁰ , the first derivative of Z_n,s with respect to x. Thus on I∪[α, β] we have (Zn,s)² ≤L², and (Zn,s)²> L² on R\(I ∪[α, β]).

Furthermore,Z_n,ssatisfies the following so-called Abel-Pell differential equa- tion:

(3.3) ^(1−x2)(x−α)(x−β)(Z_n,s⁰ (x))²

n²(x−γ)² =L²−(Z_n,s(x))².

We introduce for n ∈ N = {6,7,8,9,10,11,12} new polynomials F_m(n),s, G_m(n),s which depend on s and whose degree m(n) depends on n ∈ N, see also Section 6 below. They are an outcome of our proofs and we term them Malyshev polynomials because related polynomials appeared first in [21] in connection with ZFP, but only for n∈ {2,3,4,5} and somehow unmotivated since in [20] different polynomials were used. The coefficients, and hence the degrees, ofF_m(n),sandG_m(n),s as given below and in [53], verify that Malyshev in [21] has predicted correctly the degreesm(n) for n∈ {6,7,8} as well as a curious skew-symmetry relating F_m(n),s toG_m(n),s, ifn∈N is even:

F_m(6),s =F8,s with F8,s(α) =

(3.4)

= (−59 + 2000s−34688s²−16128s³−318816s⁴

−3960576s⁵−2861568s⁶−1492992s⁷+ 186624s⁸) + (−376 + 16976s+ 57792s²−220800s³

+ 3162240s⁴+ 3117312s⁵−995328s⁶−995328s⁷)α + (−2564−18672s+ 284160s²−637440s³

−1873728s⁴+ 4154112s⁵+ 2280960s⁶)α² + (1816−89584s−39296s²

+ 1278720s³−2888064s⁴−2923776s⁵)α³

+ (8558 + 27248s−589440s²+ 705792s³+ 2282400s⁴)α⁴ + (−2312 + 121584s−22080s²−1104000s³)α⁵

+ (−8932−11600s+ 320000s²)α⁶+ (1000−50000s)α⁷+ 3125α⁸. (3.5) G_m(6),s =G_8,s with G_8,s(β) =F8,−s(−β).

F_m(7),s =F12,s with F12,s(α) =

(3.6)

= 1792 + 163072s²+ 8410752s⁴−376438384s⁶+ 2733221568s⁸ + 2029209952s¹⁰−282475249s¹²+ (64512s−1436288s³

+ 447392736s⁵−6100537632s⁷−322828856s⁹+ 1129900996s¹¹)α + (−19712 + 1728384s²−223227536s⁴+ 5813877440s⁶

−7355415480s⁸−1395081842s¹⁰)α²+ (−868224s

+ 78809024s³−3231784416s⁵+ 12151057632s⁷−668716916s⁹)α³ + (100864−23298576s²+ 1235270400s⁴−9953009360s⁶

+ 4106538345s⁸)α⁴+ (4101216s−351315552s³+ 5195725584s⁵−

−5802179768s⁷)α⁵+ (−279792 + 70263872s²−1874768224s⁴ + 4661407044s⁶)α⁶+ (−8268960s+ 469393568s³−2424683464s⁵)α⁷ + (410688−77006160s²+ 843673425s⁴)α⁸+ (7295400s−194631500s³) α⁹+ (−297000 + 28428750s²)α¹⁰−2362500sα¹¹+ 84375α¹².

G_m(7),s =G_12,s with G_12,s(β) =

(3.7)

= 565504−102271232s²+ 3016577984s⁴+ 196082294128s⁶

−158647323520s⁸+ 571729903976s¹⁰+ 13841287201s¹² + (74400256s−6755815808s³−186738408864s⁵

+ 874115128544s⁷−1168317629864s⁹+ 55365148804s¹¹)β

+ (−10513664 + 4103042048s²+ 22357074768s⁴−1148314476288s⁶ + 1805996857280s⁸−485292477782s¹⁰)β²+ (−953905792s

+ 34684357568s³+ 570329544736s⁵−2201060316896s⁷ + 1228202382652s⁹)β³+ (78266944−16893148272s²

−43921473792s⁴+ 1570190613600s⁶−1640714247809s⁸)β⁴ + (3041893344s−65016346976s³−537505339280s⁵

+ 1310441386632s⁷)β⁵+ (−196530768 + 26344802176s² + 14921350640s⁴−627807535124s⁶)β⁶+ (−4059208608s

+ 52325237216s³+ 152679225048s⁵)β⁷+ (229065984−17822979720s² + 4354873775s⁴)β⁸+ (2480095800s−14912439500s³)β⁹

+ (−129654000 + 4425986250s²)β¹⁰−578812500sβ¹¹+ 28940625β¹². Furthermore, we shall need, for the description of the casen= 7, the following polynomialsH₂₂ andK_9,s,β of degree 22 respectively 9, given by:

H₂₂(s) =−1852140918261583566501829703 (3.8)

+ 171585036770132443429137970874s² + 2930085129784195818098662450718s⁴

−473949851650913723472627359963298s⁶

−1585996952444813524706539216972904s⁸ + 366512197633009736432152719309634722s¹⁰ + 1650042285262881985677338126342078930s¹² + 3112847096718540855667326636507713306s¹⁴−

−18636143487984483194506534138649825s¹⁶ + 84095343008722987455587706968148716s¹⁸

−10611056498918269743170304104511456s²⁰ + 532346879028669698329938821906624s²²,

K_9,s,β(α) = (3.9)

1792s−256β−3584sβ²+ 256β³+ 1120sβ⁴+ 32β⁵+ 448sβ⁶−112β⁷

−21sβ⁸+ 7β⁹+α(−512 + 256β²−2688sβ³+ 256β⁴+ 1344sβ⁵−272β⁶ + 56sβ⁷−14β⁸) +α²(−3584s−256β+ 3136sβ²−64β³−2240sβ⁴+ 80β⁵ + 84sβ⁶−28β⁷) +α³(768−2688sβ−896β²+ 896sβ³+ 368β⁴−504sβ⁵ + 80β⁶) +α⁴(1120s+ 800β−2240sβ²−80β³+ 770sβ⁴+ 10β⁵) +α⁵(−128 + 1344sβ+ 592β²−504sβ³−172β⁴) +α⁶(448s−400β+ 84sβ²+ 164β³) +α⁷(−176 + 56sβ−32β²) +α⁸(−21s−25β) + 10α⁹.

4. EXPLICIT ALGEBRAIC SOLUTION TOZFPFOR POLYNOMIALS OF DEGREEn= 6

4.1. First solution path: Abel-Pell differential equation and Groebner basis. This approach builds on the Abel-Pell differential equation represen- tation of the sought-for proper Zolotarev polynomial Z_n,s, see (3.3). This representation was used, although for a slightly different purpose, in [12]. In this respect it differs from the approach taken in [9,17], where the characteri- zation of the optimal polynomial was based on the inner equioscillation points, although it shares with the latter the computational strategy that it considers first the variety which contains the semialgebraically definable solution. The Abel-Pell differential equation gives rise to a system of multivariate polyno- mials. Its properties are investigated with Groebner basis computations [6].

It will turn out that for each of the parameters, the ideal in the associated polynomial ring is zero-dimensional and with a semialgebraic extra condition one can select the proper solution toZFPamong the finitely many candidates.

Let s >tan²(π/12) (= 7−4√

3 = 0.07179. . .) be arbitrary, but fixed. We search for the solution of ZFPin the form

(4.1) P_6a,s(x) =a₀+a₁x+a₂x²+a₃x³+a₄x⁴+ (−6s)x⁵+x⁶.

Let L be the uniform norm of P6a,s on I. By using the fact that for the solution to ZFPwe have P6a,s(1) =−L, P_6a,s(−1) =L, we may consider P6,s(x) = (−1−a₂−a₄) + (−a3−L+ 6s)x+a2x²+a3x³+a4x⁴+ (−6s)x⁵+x⁶. (4.2)

If β > α > 1 denotes the uniquely existing points where P6,s(α) = −L and P_6,s(β) =L, then it is known that the sought-for polynomial satisfies the differential equation (3.3), here for n= 6:

(4.3) (1−x²)36(x−(1/2)(α+β−2s))^{(x−α)(x−β) 2}(P_6,s⁰ (x))²=L²−(P_6,s(x))².

By clearing denominators and by a coefficient-comparison we get polynomial equations ins, α, β, L, a₂, a₃, a₄. To be able to distinguish betweenαandβwe add the constraintsP6,s(α) =−L, P_6,s(β) =Lto the system. By reducing the equations to zero, we are left with a system Q6 = {q₆₀₁, . . . , q₆₁₅} consisting of 15 polynomials. We then compute a lexicographic Groebner basis (with Mathematica) for Q6. As a result, we obtain that for each particular s the ideal generated byQ6 is a zero-dimensional ideal and if we choose that variable order where sand α are the smallest in the ordering, we get a polynomial as the first element of the basis which splits into two factors:

(4.4) (2s−1−α),

and the factor F8,s given in (3.4).

The first factor, (4.4), leads to a rational solution of the differential equation (4.3):

(−1 + 3s²) + (−6s+ 6s³)x+ (3−15s²)x² (4.5)

+(12s−8s³)x³+ (−3 + 12s²)x⁴−6sx⁵+x⁶,

but this polynomial cannot be the proper solution ofZFP, because it has less than four inner equioscillation points in I. So we consider the second factor, F_8,s. Forsfixed,α must be chosen to be the largest, that is, the second, real root of F_8,s, to obtain the solution to ZFP. For s < 1/3, there is definitely no other choice for α, because then F8,s has only one real root >1 (this can be confirmed with theCylindricalDecompositioncall inMathematica). By continuity arguments we see, that this is the case also fors >1/3 and that the uppermost branch of the real algebraic curve F_8,s = 0 must be taken for the construction of the extremal polynomial (see Fig. 4.1). We adopt, here and in what follows, the Mathematica notation Root[f, k] for the k-th root of f.

With this notation,α= Root[F_8,s,2]. Not onlyα, but also all the coefficients, the normLand the other outer equiscillation pointβ are uniquely determined bys, in fact, as the elimination ideals show, they are rational expressions ofα ands. Thus we have obtained a parametrization of the monic sextic Zolotarev polynomials by s. However, to condense the description, we note that β can be equivalently described as the second root of the degree-eight polynomial G8,s(β), see (3.5), and we are able to give the solution in a recursive way, because already in some of the 15 input polynomialsq_6j’s inQ6, the coefficients of P6,s and its norm Loccur linearly. For instance, we have

q₆₁₃=36 + 24a₄+ 396s²−360sα−360sβ (4.6)

−36αβ+ 432s(−2s+α+β) + 9(−2s+α+β)²,

5 10 15 s

5 10 15 20 25 30

α

α^*

F8s=0

Fig. 4.1. Largest positive root ofF8,s.

and solving q613 = 0 for the variable a4 gives a4 =a^∗_4,6(s) as in Theorem 4.1 below. Hence,a4is uniquely determined onceαandβ are known (for fixeds).

Theorem4.1. An algebraic solution to ZFP for n= 6 and for an assigned fixed s > tan²(π/12), but s6= 1/3, can be deduced recursively as follows, see (4.1), (4.2):

α=α^∗(s) = Root[F_8,s,2], (4.7)

β=β^∗(s) = Root[G_8,s,2],

a4=a^∗_4,6(s) = ³₈(−4 + 48s²−4sα−α²−4sβ+ 2αβ−β²), a₃=a^∗_3,6(s) = ¹₃(30s+ 4a₄s−180s³+ 3α+ 2a₄α−3s²α

+ 9sα²+ 3β+ 2a4β−3s²β−12sαβ+ 9sβ²),

a2=a^∗_2,6(s) =₂₄¹ (−24a4−10a²₄+54a3s−450s²+396a4s²−648s⁴+ 18a3α

−180sα−60a4sα+ 648s³α−9a₄α²−162s²α²+ 18a₃β−180sβ

−60a4sβ+ 648s³β−18αβ+ 6a4αβ+ 126s²αβ−9a4β²−162s²β²), L=L^∗(s) = _1−α¹ (1 +a₂+a₄+a₃α−6sα−a₂α²−a₃α³−a₄α⁴+ 6sα⁵−α⁶), a1=a^∗_1,6(s) =−a₃−L+ 6s,

a0=a^∗_0,6(s) =−1−a2−a4.

For the special choice s = 1/3, α^∗ and β^∗ needs to be computed as given in

(4.18), (4.19) and (4.20).

Example 4.2. The goal is to determine Z_6,s=1^∗ , the sextic proper monic Zolotarev polynomial with parameter s = s₀ = 1 > tan²(π/12) and L^∗, its

least deviation from the zero-function on I. We get withs= 1 F_8,s(α) =−8496203 + 4142488α+ 4186828α²−4660184α³ (4.8)

+ 2434558α⁴−1006808α⁵+ 299468α⁶−49000α⁷+ 3125α⁸ and

G_8,s(β) =2439189−306168β−2809172β²+ 1190904β³ (4.9)

+ 968478β⁴−958024β⁵+ 322668β⁶−51000β⁷+ 3125β⁸. Picking the appropriate (largest) positive root >1 of these polynomials gives (4.10) α=α^∗= Root[F_8,s,2] = 6.082716. . . respectively

(4.11) β=β^∗= Root[G_8,s,2] = 6.0828088. . . .

Inserting these real numbers into the expression for a4 in Theorem4.1 gives a^∗_4,6(s= 1) =

(4.12)

= Root[−24974796693375 + 518755962600x+ 4763147078844x²

−1611134445672x³+ 249132993894x⁴−21634573608x⁵ + 1098618876x⁶−31095000x⁷+ 390625x⁸,1] =−1.74828. . . . Similarly, after computing the other coefficients and the norm, we get

Z_6,s=1^∗ (x) = (−0.06207. . .)+(−1.86731. . .)x+0.81036. . . x²+ (4.13)

7.48972. . . x³+ (−1.74828. . .)x⁴+ (−6)x⁵+x⁶ and

(4.14) L^∗= 0.377586. . . .

4.2. Second solution path: Modification of Malyshev’s and Schiefer- mayr’s approach. Our second solution path to ZFP was inspired by the papers [21] and [41]. We merge and modify their approaches to ZFP.

Theorem 4.3. An algebraic solution to ZFP for n = 6 can be deduced in three algorithmic steps as follows:

(i) Express the sought-for sextic proper Zolotarev polynomial and its norm L in a tentative form which depends on the (undetermined) parametersα and β, that is

Z_6,α,β(x) = (4.15)

=(−(−1+β)(−α+β)(256−3α⁸+ 8α⁷β−512β²+ 160β⁴+ 64β⁶3β⁸

−24α⁵β(−8 + 3β²) + 4α⁶(16 + 3β²) + 8αβ³(−48 + 24β²+β⁴)

−8α³β(48−16β²+ 9β⁴) + 10α⁴(16−32β²+ 11β⁴) + 4α²(−128 + 112β²−80β⁴+ 3β⁶))²+ 2(−1 +x)(x−α)·

·(−256 + 3α⁸+ 8α⁷β−512β²+ 864β⁴−128β⁶+ 35β⁸

−24α⁵β(−8 + 11β²) +α⁶(−64 + 52β²)−24α³β(16−16β²+ 3β⁴)

−8αβ³(48−56β²+ 7β⁴) + 2α⁴(−80−128β²+ 153β⁴)

+α²(512 + 64β²−576β⁴−12β⁶) + 16x²(64 +α⁶+ 6α⁵β−16β²

−52β⁴+ 5β⁶+α⁴(44−29β²) + 4α³β(−4 + 9β²)

+α²(−80 + 104β²−9β⁴)−2αβ(−48 + 40β²+ 5β⁴))−16x(α+β)² (α⁵+ 3α⁴β+α³(24−22β²)−3α(4−3β²)²+α²(−40β+ 38β³)

+β(48−56β²+ 7β⁴)))²)/

(512(64 +α⁶+ 6α⁵β−16β²−52β⁴+ 5β⁶+α⁴(44−29β²) + 4α³β (−4 + 9β²) +α²(−80 + 104β²−9β⁴)−2αβ(−48 + 40β²+ 5β⁴))²), and

(4.16) L=L(α, β) =|Z_6,α,β(1)|.

Remark 4.4. We refrain here from representing Z6,α,β in the power form since the expansion Z6,α,β(x) =^P6_k=0ak,6(α, β)x^k witha5,6(α, β) = −6sand a_6,6(α, β) = 1 produces bulky coefficients a_k,6(α, β) for k= 0, . . . ,4. But we provide them, for the reader’s convenience, in our web-based repository [53].

(ii) For an assigned fixed s > tan²(π/12), but s 6= 1/3, determine the corresponding optimal α = α(s) = α^∗ and β = β(s) = β^∗ as a positive root

>1 of F_8,s respectively ofG_8,s (see (3.4) and (3.5)), more precisely, (4.17) α^∗= Root[F_8,s,2] respectively β^∗ = Root[G_8,s,2].

For the special choice s = 1/3, determine the corresponding optimal α^∗ and β^∗ as

(4.18)

α^∗= Root[f6,2] = 2.233289. . . respectively β^∗ = Root[g6,2] = 2.238828. . . , where

f₆(α) =−257923−33678α+ 156979α² (4.19)

+52988α³+ 7187α⁴−84750α⁵+ 28125α⁶, g6(β) = 46493−397778β+ 944755β² (4.20)

−1098684β³+ 676787β⁴−215250β⁵+ 28125β⁶.

(iii) Then replace in the expression (4.15) above, the parameter α by the real number α^∗ >1and the parameterβ by the real numberβ^∗ >1(with 1< α^∗ <

β^∗) and rearrange terms in order to obtain a power form representation of the sextic polynomial in the variable x. Its coefficients ak,6(α^∗, β^∗) agree with the optimal coefficients a^∗_k,6(s), for k = 0, . . . ,4, of the sought-for monic proper Zolotarev polynomial Z_6,s^∗ . Finally, evaluate Z_6,s^∗ (x) at x = 1 in order to get,

up to sign, the real number L(α^∗, β^∗) = L^∗ in (4.16), the least deviation of

Z_6,s^∗ onI from the zero-function.

Remark 4.5. The just described step allows to generate numerical values of arbitrary precision for the optimal coefficients a^∗_k,6(s) of Z_6,s^∗ and can be accomplished, fors6= 1/3, by executing the following simpleMathematicacall (where Z6αβ = Z_6,α,β, F8s = F_8,s, G8s = G_8,s and s₀ is an assigned fixed value fors, and pis an assigned fixed integer value for thep-digit precision of the numerical result):

(4.21)

N[Z6αβ/.α→Root[F8s/.s→s₀,2]/.β→Root[G8s/.s→s₀,2], p]//Expand If we assume thats >tan²(π/12) is an integer or a rational number a/b, then we can explicitly express eacha^∗_k,6(s) as a root object Root[P8, k] (whereP8 is a dedicated integer polynomial of degree eight), for example by executing the Mathematica callRootReduce.

Example 4.6. The goal is to determine Z_6,s=1/8^∗ , the sextic proper monic Zolotarev polynomial with parameters=s₀ = 1/8 = 0.125>tan²(π/12) and L^∗, its least deviation from the zero-function on I. We get withs= 1/8

F_8,s(α) =− ^38851047₆₅₅₃₆ +^1577289α₅₁₂ −^1036789α₅₁₂ ² − ^1061481α₁₂₈ ³ (4.22)

+ ^600285α₁₂₈ ⁴ + ^41539α₄ ⁵ −5382α⁶−5250α⁷+ 3125α⁸ and

G_8,s(β) =−^51554663₆₅₅₃₆ + ^250969β₅₁₂ +^2498291β₅₁₂ ² −^1188689β₁₂₈ ³ (4.23)

−^624547β₁₂₈ ⁴ +^62795β₄ ⁵ −2482β⁶−7250β⁷+ 3125β⁸. Solving for the appropriate positive root >1 of these polynomials gives (4.24) α=α^∗= Root[F8,s,2] = 1.2107637. . . respectively (4.25) β=β^∗= Root[G8,s,2] = 1.2826256. . . .

Inserting these real numbers into the expression (4.15) and rearranging yields Z_6,s=1/8^∗ (x) = (−0.0500034. . .)+(−0.2023092. . .)x+0.7382004. . . x² (4.26)

+0.8898304. . . x³+ (−1.6881970. . .)x⁴+−³₄x⁵+x⁶, and evaluating |Z_6,s=1/8^∗ (1)|yields

(4.27) L^∗= 0.0624788. . . .

A corresponding call inMathematica would read here (4.28)

N[Z6αβ/.α→Root[F8s/.s→¹₈,2]/.β→Root[G8s/.s→¹₈,2],8]//Expand

Upon using the RootReduce call we would get here the following explicit algebraic expression fora^∗_4,6by means of a root object (and similar expressions for the other coefficients):

a^∗_4,6(s= 1/8) = (4.29)

Root[14776676496736461 + 65194824742046316x+ 124565949527455296x² + 134777006368948224x³+ 90433468346204160x⁴+ 38602113736900608x⁵ + 10265567828115456x⁶+ 1562042695680000x⁷+ 104857600000000x⁸,1].

A corresponding call in Mathematica would read (where Collect means to collect together terms with the same power of x):

(4.30)

Collect[Z6αβ/.α→Root[F8s,2]/.β→Root[G8s,2]/.s→¹₈, x]//RootReduce In Fig. 4.2 the graph ofZ_6,s=1/8^∗ is displayed, with vertical lines to the right

of x= 1 indicatingα^∗ and β^∗.

Fig. 4.2. Z_6,^∗1 8

.

5. EXPLICIT ALGEBRAIC SOLUTION TOZFPFOR POLYNOMIALS OF DEGREEn= 7

5.1. First solution path: Abel-Pell differential equation and Groebner basis. Let s > tan²(π/14) = 0.05209. . . be arbitrary but fixed. We search for the septic solution of ZFPin the form analogous to (4.2) given in Section 4.1. Let

(5.1) P_7a,s(x) =a₀+a₁x+a₂x²+a₃x³+a₄x⁴+a₅x⁵+ (−7s)x⁶+x⁷, and let L be the uniform norm of P_7a,s on I. By using the fact that for the solution to ZFPwe have P7a,s(1) =−L, P_7a,s(−1) =−L, we may consider

P_7,s(x) =(−a₂−a₄−L+ 7s) + (−1−a₃−a₅)x (5.2)

+a2x²+a3x³+a4x⁴+a5x⁵+ (−7s)x⁶+x⁷.

If β > α > 1 denotes the uniquely existing points where P7,s(α) = −L and P_7,s(β) = L, then it is known that the sought-for polynomial satisfies the differential equation (3.3), here for n= 7:

(5.3) (1−x²)49(x−(1/2)(α+β−2s))^{(x−α)(x−β) 2}(P_7,s⁰ (x))²=L²−(P_7,s(x))².

By clearing denominators and by a coefficient-comparison we get polynomial equations ins, α, β, L, a2, a3, a4, a5. To be able to distinguish betweenαandβ we add the constraints P7,s(α) =−L, P_7,s(β) =Lto the system. By reducing the equations to zero, we are left with a system Q7 = {q₇₀₁, . . . , q₇₁₇} con- sisting of 17 polynomials. We compute a lexicographic Groebner basis (with Mathematica) for Q7. As a result, we obtain that for each particular s the ideal generated byQ7 is a zero-dimensional ideal and if we choose that variable order where s and α are the smallest in the ordering, we get the irreducible polynomial F12,s(α) given in (3.6) as the first element of the basis.

Again, analogously to the sextic case, for a fixeds, the univariate polynomial F₁₂(α) has several real roots, but we have to take the largest real root for the construction of the extremal polynomial, that is, the fourth root, if s <3/7, and the sixth root otherwise.

Not only α, but also all the coefficients, the norm L and the other outer equiscillation pointβ are uniquely determined bys, in fact, as the elimination ideals show, they are rational expressions ofα and s. Thus we have obtained a parametrization of the monic septic Zolotarev polynomials by s. However, to condense the description, we note that β can be equivalently described as a uniquely determined root of the degree-twelve polynomial G12,s(β), see (3.7). For the precise characterization of the root index we need an auxiliary polynomial H22 given in (3.8), which is a factor of a discriminant of G12,s. Now we are able to give the solution in a recursive way as follows:

Theorem5.1. An algebraic solution to ZFP for n= 7 and for an assigned fixed s > tan²(π/14), but s6= 1/7, can be deduced recursively as follows, see (5.1), (5.2):

α=α^∗(s) =

(Root[F12,s,4] if s <3/7 Root[F12,s,6] if s≥3/7, β=β^∗(s) =











Root[G_12,s,3] if s≤Root[H₂₂,4] = 0.12277. . . Root[G12,s,4] ifRoot[H22,4]< s <3/7

Root[G_12,s,6] if s≥3/7,

a₅=a^∗_5,7(s) = ₁₆⁷(−4 + 56s²−4sα−α²−4sβ+ 2αβ−β²), a₄=a^∗_4,7(s) = ₁₂¹(168s+ 20a₅s−1176s³+ 14α+ 8a₅α−14s²α

+ 49sα²+ 14β+ 8a5β−14s²β−70sαβ+ 49sβ²),

a3 =a^∗_3,7(s) = ₂₂₄¹ (−280a₅−96a²₅+ 616a4s−7056s²+ 5096a5s² (5.4)

−9604s⁴+ 168a₄α−2352sα−672a₅sα+ 9604s³α−98a₅α²

−2401s²α²+ 168a4β−2352sβ−672a5sβ+ 9604s³β−196αβ + 84a₅αβ+ 2254s²αβ−98a₅β²−2401s²β²),

a₂ =a^∗_2,7(s) =−a₄+ 7s−α−a₃α−a₅α−a₄α² + 7sα²−α³−a5α³+ 7sα⁴−α⁵,

L=L^∗(s) = ¹₂(−a₂−a₄+ 7s−β−a₃β−a₅β+a₂β² +a3β³+a4β⁴+a5β⁵−7sβ⁶+β⁷),

a1 =a^∗_1,7(s) =−1−a3−a5, a₀ =a^∗_0,7(s) =−a₂−a₄−L+ 7s.

For the special choice s = 1/7, α^∗ and β^∗ needs to be computed as given in

(5.11), (5.12) and (5.13).

5.2. Second solution path: Modification of Malyshev’s and Schiefer- mayr’s approach.

Theorem 5.2. An algebraic solution to ZFP for n = 7 can be deduced in three algorithmic steps as follows:

(i) Express the sought-for septic proper Zolotarev polynomial and its norm L in a tentative form which depends on the (undetermined) parametersα and β, that is

Z7,α,β(x) = (5.5)

= ((−4 + (α−β)(3α+β))²((α−β)(−1 +β²)

(−1024 + 1280α²+ 384α⁴−736α⁶+ 44α⁸−7α¹⁰+ 6α(−256 + 256α² + 32α⁴−112α⁶+ 7α⁸)β+ 3(768−2304α²+ 1056α⁴+ 48α⁶−29α⁸)β² + 8α(−64−496α²+ 260α⁴+ 3α⁶)β³+ 42(−64 + 48α²−44α⁴+ 5α⁶)β⁴

−84α(16−8α²+ 5α⁴)β⁵+ 42(4−3α²)²β⁶+ 24α(20−7α²)β⁷+ 3(36 + 7α²)

·β⁸+ 10αβ⁹−3β¹⁰)²−2(−1 +x²)(−x+α)(−1024−7α¹⁰+ 14α⁹β

+ 1280β²+ 384β⁴−736β⁶+ 44β⁸−7β¹⁰+ 8α⁷β(−28 + 5β²) +α⁸(44 + 5β²) +α⁶(−736 + 464β²−254β⁴) +α⁵(64β−544β³+ 404β⁵) +α⁴(384 + 224β²+ + 520β⁴−254β⁶) + 8α³β(64 + 112β²−68β⁴+ 5β⁶) +α²(1280−1792β² + 224β⁴+ 464β⁶+ 5β⁸) + 2αβ(−256 + 256β²+ 32β⁴−112β⁶+ 7β⁸)

−8x²(−4 +α²+ (−4 +β)β−2α(2 +β))(−4 +α²−2α(−2 +β) +β(4 +β))·

·(−4 + (α−β)(3α+β))(4 + (α−β)(α+ 3β)) + 4x(α+β)(−256 + (α−β)² (256 + 32α²+ 7(−4 +α)α⁴(4 +α) + 448αβ−10α³(32 +α²)β+ (32−160α²

−23α⁴)β²+ 4α(−80 + 13α²)β³−(112 + 23α²)β⁴−10αβ⁵+ 7β⁶)))²))/

(128(4−3α²+ 2αβ+β²)⁴(−4 +α²+ (−4 + β)β−2α(2 +β))² (−4 +α²−2α(−2 +β) +β(4 +β))²(4 + ( α−β)(α+ 3β))²), and

(5.6) L=L(α, β) =|Z_7,α,β(1)|.

Remark 5.3. We refrain here from representing Z_7,α,β in the power form since the expansion Z_7,α,β(x) =^P7_k=0a_k,7(α, β)x^k witha6,7(α, β) = −7sand a_7,7(α, β) = 1 produces bulky coefficients a_k,7(α, β) for k= 0, . . . ,5. But we provide them, for the reader’s convenience, in our web-based repository [53].

(ii) For an assigned fixed s > tan²(π/14), but s 6= 1/7, determine the corresponding optimal β = β(s) = β^∗ as a positive root > 1 of G12,s (see (3.7)), more precisely (utilizing the polynomialH₂₂ as given in (3.8)):

β^∗= Root[G12,s,3],if tan² ₁₄^π< s≤Root[H22,4], (5.7)

β^∗= Root[G12,s,4],if Root[H22,4]< s < ³₇,buts6= ¹₇, (5.8)

β^∗= Root[G12,s,6],if ³₇ ≤s.

(5.9)

Deploying the polynomial as given in(3.9) and inserting there the number β^∗, calculate the corresponding optimal α=α(s, β^∗) =α^∗ (with 1< α^∗ < β^∗) as (5.10) α^∗ = Root[K_9,s,β^∗,3].

For the special choice s= 1/7 calculate the corresponding optimal α^∗ and β^∗ as

(5.11)

α^∗= Root[f₉,3] = 1.40565. . .respectivelyβ^∗= Root[g₉,3] = 1.42240. . . , where

f9(α) =−289327−2055393α−3863708α²−2195188α³+ 207262α⁴ (5.12)

+10020402α⁵+ 7009300α⁶−10930500α⁷−4134375α⁸+ 4134375α⁹ and

g₉(β) = (5.13)

= 1375897−23273607β+ 138777636β²−351747852β³+ 390461870β⁴−

−40305346β⁵−356725100β⁶+ 382378500β⁷−169509375β⁸+ 28940625β⁹. (iii) Then replace in the expression (5.5) above, the parameter α by the real number α^∗ >1and the parameterβ by the real numberβ^∗ >1(with 1< α^∗ <

β^∗) and rearrange terms in order to obtain a power form representation of the