\(^\ast \)Dr. Rack Consulting GmbH, Steubenstrasse 26a, 58097 Hagen, Germany, e-mail: heinz-joachim.rack@drrack.com

\(^\bullet \)Bolyai Institute, University of Szeged, Aradi Vertanuk tere 1, 6720 Szeged, Hungary, e-mail: vajdar@math.u-szeged.hu. 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.

1 Introduction and historical remarks

Let \(\boldsymbol {I}=[-1,1]\subset \mathbb {R}\) denote the unit interval and let \(T_n\) denote the \(n\)-th Chebyshev polynomial of the first kind with respect to \(\boldsymbol {I}\). Chebyshev’s classical extremal problem (CEP) of 1854 [ 8 ] is to determine among all monic polynomials of degree \(n\ge 1\), given by

where \(a_{k,n}\in {\mathbb R}\) are arbitrary coefficients (and \(a_{n,n}=1\) is fixed), that particular one, call it \(T^{*}_n\), which deviates least from the zero-function on \(\boldsymbol {I}\) measured in the uniform norm \(\Vert \cdot \Vert _{\infty }\). Chebyshev found that the solution \(T^{*}_n\) is given on \(\boldsymbol {I}\) by

with least deviation \(\Vert T^{*}_n\Vert _{\infty }=2^{1-n}\) 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, \(a_{n-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\ge 2\), represented as

where \(s\in \mathbb {R}\backslash \{ 0\} \) is prescribed, that particular one, call it \(Z^{*}_{n,s}\), with

which deviates least from the zero-function on \(\boldsymbol {I}\) in the uniform norm \(\Vert \cdot \Vert _{\infty }\).

Or put alternatively, the goal is to determine, for a prescribed \(s\), the best uniform approximation on \(\boldsymbol {I}\) to \((-n s)x^{n-1}+x^n\) by polynomials of degree \({\lt}n-1\). It is well-known that one may restrict the parameter \(s\) to \(s{\gt}0\), and that for \(0{\lt}s\le \tan ^2\left(\pi /(2n)\right)\) the solution is given by a distorted \(T^{*}_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, for \(s{\gt}\tan ^2\left(\pi /(2n)\right)\), the solution \(Z^{*}_{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 ] , or hard-core [ 40 ] monic Zolotarev polynomial. Here we shall confine ourselves to proper monic Zolotarev polynomials, noting that \(0{\lt}\tan ^2\left(\pi /(2n)\right){\lt}1\) holds for \(n{\gt}2\), and writing \(Z_{n,s}\) in place of \(Z^{*}_{n,s}\), if \(s{\gt}\tan ^2\left(\pi /(2n)\right)\) is not specified.

Zolotarev provided a solution to ZFP in 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 \(Z_{n,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 solution. 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 proper \(Z_{n,s}\) algebraically. 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 solutions to ZFP (in terms of parameterized coefficients) are known only for polynomial degrees \(2\le n\le 5\), see Section 2. Added in proof: But see our recent one-parameter power form solution for \(n=6\) in [ 38 ] .

The purpose of the present paper is to provide new explicit algebraic solutions to ZFP for polynomial degrees \(6\le n\le 12\). To this end, we shall explore in some detail two different solution paths for \(n=6\) and for \(n=7\). The first one is based on the Abel-Pell differential equation which must be satisfied by \(Z_{n,s}\) and computes Groebner bases with the computer algebra system Mathematica™ [ 50 ] to actually construct it. The second solution path, also backed by Mathematica, expresses \(Z_{n,s}\) tentatively as \(Z_{n,\alpha ,\beta }\), a form which depends on two parameters \(\alpha \) and \(\beta \), so that \(Z_{n,\alpha ,\beta }\) can be stored, once and for all, in an electronic library. Upon assigning a fixed \(s{\gt}\tan ^2\left(\pi /(2n)\right)\), \(\alpha \) and \(\beta \) can then be conveyed to real numbers so that \(Z_{n,\alpha ,\beta }\) turns into \(Z^{*}_{n,s}\). Both of our approaches have in common that for a given \(s\in \mathbb {Q}\) the optimal coefficients of \(Z^{*}_{n,s}\) can be expressed explicitly by means of root objects of dedicated integer polynomials. Because of the growing bulkiness of the intermediate results needed to compute \(Z_{n,s}\) where \(n\ge 8\), we will transfer our findings for the polynomial degrees \(8\le n\le 12\) to a web repository [ 53 ] , see also Section 6.

Ours is not the first investigation of an algebraic solution to ZFP. 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 particular \(n\). But actually V. A. Malyshev [ 21 ] , see also [ 20 ] , provided explicit constructions only for \(2\le n\le 5\) by deploying certain pairs of polynomials, parameterized by \(s\), which are key to the determination of the parameters \(\alpha \) and \(\beta \) when \(s\) is 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\le n\le 12\). Malyshev [ 21 ] had predicted (correctly, as we have now verified) only their degrees for \(6\le n\le 8\), but did not communicate their coefficients. Further papers relevant to ZFP 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,\alpha ,\beta , y_1,\dots ,y_m}\) and algorithmic steps are delineated how to compute the parameters. By modifying these steps, we eliminate the parameters \(y_1,\dots ,y_m\). The remaining parameters \(\alpha \) and \(\beta \) we then determine as roots of the Malyshev polynomials and that eventually leads to \(Z_{n,s}\).

The provision of a solution to ZFP for \(n{\gt}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 ZFP for \(6\le n\le 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\le n\le 12\), are revealed: Explicit tentative representations \(Z_{n,\alpha ,\beta }\) 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)\) of \(Z_{n,s}\), and a representation of the \(a_{k,n}(s)\) as root objects of dedicated integer polynomials if \(s\in \mathbb {Q}\).

The first-named author has presented a poster on ZFP at the IX Jaen Conference 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, September 2018) [ 37 , 48 ] . We have agreed to publish our individual findings in a joint manuscript.

2 Known explicit algebraic solutions to ZFP for \(2\leq n\leq 5\)

The demand for a description of the solution to ZFP without elliptic functions has been vibrant from the outset. Scaled proper Zolotarev polynomials, for \(2\le n\le 4\), given in an algebraic power form, found application already in the proof of the famous Markov inequalities [ 22 ] , [ 24 ] . Algebraic expressions for scaled proper Zolotarev polynomials (with uniform norm \(1\) on \(\boldsymbol {I}\)) for \(2\le n\le 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 recently in [ 12 ] , [ 13 ] , [ 14 ] , see also [ 35 ] . A partial result for \(n=5\) is due to  [ 9 ] .

These polynomials, whose coefficients depend injectively on one parameter,

are expressed, for \(2\le n\le 5\), in the analytic form

where \(I_n\) denotes a dedicated open interval. To deduce, for a given \(s{\gt}\tan ^2\left(\pi /(2n)\right)\), 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 coefficient \(a_{n,n}(t)\) yielding \(\sum _{k=0}^{n-1} b_{k,n}(t) x^k + x^n\); then equate \(b_{n-1,n}(t)\) with \((-ns)\) and solve for \(t\); insert the solution \(t=t^{*} \in I_n\) into \(\sum _{k=0}^{n-1} b_{k,n}(t) x^k + x^n\) 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{\gt}5\) and for an assigned fixed \(s{\gt}\tan ^2\left(\pi /(2n)\right)\) in the way just sketched would be an elegant path to solve ZFP avoiding elliptic functions. However, to the best of our knowledge, analytical forms (2.1) for (scaled) proper Zolotarev polynomials currently do not exist if \(n{\gt}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 composition 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 \(\boldsymbol {I}\) exactly as many times as the degree indicates, and hence they cannot be proper (scaled) Zolotarev polynomials, see also Section 3 below.

3 Preliminaries

It is well known (see e.g. [ 2 ] , [ 10 ] , [ 42 ] , [ 45 ] ) that a proper monic Zolotarev polynomial \(Z_{n,s}\) (where \(s{\gt}\tan ^2\left(\pi /(2n)\right)\)) has \(n\) equioscillation points on \(\boldsymbol {I}\), including the endpoints \(\pm 1\), at which it takes its uniform norm \(L:=\Vert Z_{n,s}\Vert _{\infty }\) with alternating sign. For definiteness we assume that in particular, at \(x=-1\) the value \((-1)^n L\) is attained and at \(x=1\) the value \(-L\) is attained. Additionally, there exists an interval \([\alpha ,\beta ]\) with

such that at \(x=\alpha \) the value \(-L\) is attained and at \(x=\beta \) the value \(L\) is attained, and at

there vanishes \(Z'_{n,s}\), the first derivative of \(Z_{n,s}\) with respect to \(x\). Thus on \(\boldsymbol {I}\cup [\alpha ,\beta ]\) we have \((Z_{n,s})^2\le L^2\), and \((Z_{n,s})^2{\gt} L^2\) on \(\mathbb {R}\backslash (\boldsymbol {I}\cup [\alpha ,\beta ])\).

Furthermore, \(Z_{n,s}\) satisfies the following so-called Abel-Pell differential equation:

We introduce for \(n\in 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\in 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\in \{ 2,3,4,5\} \) and somehow unmotivated since in [ 20 ] different polynomials were used. The coefficients, and hence the degrees, of \(F_{m(n),s}\) and \(G_{m(n),s}\) as given below and in [ 53 ] , verify that Malyshev in [ 21 ] has predicted correctly the degrees \(m(n)\) for \(n\in \{ 6,7,8\} \) as well as a curious skew-symmetry relating \(F_{m(n),s}\) to \(G_{m(n),s}\), if \(n\in N\) is even:

Furthermore, we shall need, for the description of the case \(n=7\), the following polynomials \(H_{22}\) and \(K_{9,s,\beta }\) of degree 22 respectively 9, given by:

4 Explicit algebraic solution to ZFP for polynomials of           degree \(n = 6\)

4.1 First solution path: Abel-Pell differential equation and Groebner basis

This approach builds on the Abel-Pell differential equation representation 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 characterization 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 polynomials. 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 to ZFP among the finitely many candidates.

Let \(s{\gt}\tan ^2\left(\pi /12\right)(=7-4\sqrt3=0.07179\dots )\) be arbitrary, but fixed. We search for the solution of ZFP in the form

Let \(L\) be the uniform norm of \(P_{6a,s}\) on \(\boldsymbol {I}\). By using the fact that for the solution to ZFP we have \(P_{6a,s}(1)=-L, P_{6a,s}(-1)=L\), we may consider

If \(\beta {\gt}\alpha {\gt}1\) denotes the uniquely existing points where \(P_{6,s}(\alpha )=-L\) and \(P_{6,s}(\beta )=L\), then it is known that the sought-for polynomial satisfies the differential equation (3.3), here for \(n=6\):

By clearing denominators and by a coefficient-comparison we get polynomial equations in \(s,\alpha ,\beta ,L,a_2,a_3,a_4\). To be able to distinguish between \(\alpha \) and \(\beta \) we add the constraints \(P_{6,s}(\alpha )=-L, P_{6,s}(\beta )=L\) to the system. By reducing the equations to zero, we are left with a system \(Q6=\{ q_{601},\dots ,q_{615}\} \) 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 by \(Q6\) is a zero-dimensional ideal and if we choose that variable order where \(s\) and \(\alpha \) are the smallest in the ordering, we get a polynomial as the first element of the basis which splits into two factors:

and the factor \(F_{8,s}\) given in (3.4).

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

but this polynomial cannot be the proper solution of ZFP, because it has less than four inner equioscillation points in \(\boldsymbol {I}\). So we consider the second factor, \(F_{8,s}\). For \(s\) fixed, \(\alpha \) 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{\lt}1/3\), there is definitely no other choice for \(\alpha \), because then \(F_{8,s}\) has only one real root \({\gt}1\) (this can be confirmed with the CylindricalDecomposition call in Mathematica). By continuity arguments we see, that this is the case also for \(s{\gt}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. 1).

We adopt, here and in what follows, the Mathematica notation \({\rm Root[}f,k{\rm ]}\) for the \(k\)-th root of \(f\). With this notation, \(\alpha ={\rm Root[}F_{8,s},2{\rm ]}\). Not only \(\alpha \), but also all the coefficients, the norm \(L\) and the other outer equiscillation point \(\beta \) are uniquely determined by \(s\), in fact, as the elimination ideals show, they are rational expressions of \(\alpha \) and \(s\). Thus we have obtained a parametrization of the monic sextic Zolotarev polynomials by \(s\). However, to condense the description, we note that \(\beta \) can be equivalently described as the second root of the degree-eight polynomial \(G_{8,s}(\beta )\), see (3.5), and we are able to give the solution in a recursive way, because already in some of the 15 input polynomials \(q_{6j}\)’s in \(Q6\), the coefficients of \(P_{6,s}\) and its norm \(L\) occur linearly. For instance, we have

and solving \(q_{613}=0\) for the variable \(a_4\) gives \(a_4=a^{*}_{4,6}(s)\) as in Theorem 4.1 below. Hence, \(a_4\) is uniquely determined once \(\alpha \) and \(\beta \) are known (for fixed \(s\)).

4.2 Second solution path: Modification of Malyshev’s and Schiefermayr’s approach

Our second solution path to ZFP was inspired by the papers [ 21 ] and [ 41 ] . We merge and modify their approaches to ZFP.

Example 4.6

The goal is to determine \(Z^{*}_{6,s=1/8}\), the sextic proper monic Zolotarev polynomial with parameter \(s=s_0=1/8=0.125{\gt}\tan ^2(\pi /12)\) and \(L^*\), its least deviation from the zero-function on \(\boldsymbol {I}\). We get with \(s=1/8\)

\begin{align} F_{8,s}(\alpha )=& -\tfrac {38851047}{65536} + \tfrac {1577289 \alpha }{512} - \tfrac { 1036789 \alpha ^2}{512} - \tfrac {1061481 \alpha ^3}{128} \\ & +\tfrac { 600285 \alpha ^4}{128} + \tfrac {41539 \alpha ^5}{4} - 5382 \alpha ^6 - 5250 \alpha ^7 + 3125 \alpha ^8 \nonumber \end{align}

and

\begin{align} G_{8,s}(\beta )=& -\tfrac {51554663}{65536} + \tfrac {250969 \beta }{512} + \tfrac {2498291 \beta ^2}{512} - \tfrac { 1188689 \beta ^3}{128} \\ & -\tfrac {624547 \beta ^4}{128} + \tfrac {62795 \beta ^5}{4} - 2482 \beta ^6 - 7250 \beta ^7 + 3125 \beta ^8. \nonumber \end{align}

Solving for the appropriate positive root \({\gt}1\) of these polynomials gives

\begin{equation} \alpha =\alpha ^*={\rm Root[}F_{8,s},2{\rm ]}=1.2107637\dots \quad {\rm respectively} \end{equation}

4.24

\begin{equation} \beta =\beta ^*={\rm Root[}G_{8,s},2{\rm ]}=1.2826256\dots \, . \end{equation}

4.25

Inserting these real numbers into the expression (4.15) and rearranging yields

\begin{align} Z^{*}_{6,s=1/8}(x)\! =\! (-0.0500034\dots )\! +\! (-0.2023092\dots )x\! +\! 0.7382004\dots x^2\\ +0.8898304\dots x^3+(-1.6881970\dots )x^4+\left(-\tfrac {3}{4}\right)x^5+x^6, \nonumber \end{align}

and evaluating \(|Z^{*}_{6,s=1/8}(1)|\) yields

\begin{equation} L^{*}=0.0624788\dots \, . \end{equation}

4.27

A corresponding call in Mathematica would read here

\begin{equation} \label{M6callspec} {\bf N[}Z6\alpha \beta /.\alpha \! \! \rightarrow \! {\bf Root[}F8s/.s\rightarrow \! \tfrac {1}{8},2{\bf ]} /.\beta \! \! \rightarrow \! {\bf Root[}G8s/.s\rightarrow \! \tfrac {1}{8},2],8{\bf ]//Expand} \end{equation}

4.28

Upon using the RootReduce call we would get here the following explicit algebraic expression for \(a^{*}_{4,6}\) by means of a root object (and similar expressions for the other coefficients):

\begin{align} & a^{*}_{4,6}(s=1/8)= \label{coeffa46s18}\\ & {\rm Root[}14776676496736461 + 65194824742046316 x + 124565949527455296 x^2 \nonumber \\ & +134777006368948224 x^3 + 90433468346204160 x^4 + 38602113736900608 x^5 \nonumber \\ & +10265567828115456 x^6 + 1562042695680000 x^7 + 104857600000000 x^8 , 1{\rm ]}. \nonumber \end{align}

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

\begin{equation} {\bf Collect[}Z6\alpha \beta /.\alpha \! \! \rightarrow \! {\bf Root[}F8s,2{\bf ]}/.\beta \! \% \rightarrow \! {\bf Root[}G8s,2{\bf ]} /.s\! \! \rightarrow \! \tfrac {1}{8}{,x\bf ]}//{\bf RootReduce} \end{equation}

4.30

In Fig. 2 the graph of \(Z^{*}_{6,s=1/8}\) is displayed, with vertical lines to the right of \(x=1\) indicating \(\alpha ^{*}\) and \(\beta ^{*}\).â–¡

5 Explicit algebraic solution to ZFP for polynomials of degree \(n = 7\)

5.1 First solution path: Abel-Pell differential equation and Groebner basis

Let \(s{\gt}\tan ^2\left(\pi /14\right)=0.05209\dots \) be arbitrary but fixed. We search for the septic solution of ZFP in the form analogous to (4.2) given in Section 4.1. Let

and let \(L\) be the uniform norm of \(P_{7a,s}\) on \(\boldsymbol {I}\). By using the fact that for the solution to ZFP we have \(P_{7a,s}(1)=-L, P_{7a,s}(-1)=-L\), we may consider

If \(\beta {\gt}\alpha {\gt}1\) denotes the uniquely existing points where \(P_{7,s}(\alpha )=-L\) and \(P_{7,s}(\beta )=L\), then it is known that the sought-for polynomial satisfies the differential equation (3.3), here for \(n=7\):

By clearing denominators and by a coefficient-comparison we get polynomial equations in \(s,\alpha ,\beta ,L,a_2,a_3,a_4,a_5\). To be able to distinguish between \(\alpha \) and \(\beta \) we add the constraints \(P_{7,s}(\alpha )=-L, P_{7,s}(\beta )=L\) to the system. By reducing the equations to zero, we are left with a system \(Q7=\{ q_{701},\dots ,q_{717}\} \) consisting 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 by \(Q7\) is a zero-dimensional ideal and if we choose that variable order where \(s\) and \(\alpha \) are the smallest in the ordering, we get the irreducible polynomial \(F_{12,s}(\alpha )\) given in (3.6) as the first element of the basis.

Again, analogously to the sextic case, for a fixed \(s\), the univariate polynomial \(F_{12}(\alpha )\) 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{\lt}3/7\), and the sixth root otherwise.

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

5.2 Second solution path: Modification of Malyshev’s and Schiefermayr’s approach

Example 5.5

The goal is to determine \(Z^{*}_{7,s=2/7}\), the septic proper monic Zolotarev polynomial with parameter \(s=s_0=2/7=0.28571\dots {\gt}\tan ^2(\pi /14)\) and \(L^*\), its least deviation from the zero-function on \(\boldsymbol {I}\). We get with \(s=2/7\)

\begin{align} & G_{12,s}(\beta )=\\ =& 114017536 \! -\! 370762752 \beta \! -\! 72818688 \beta ^2 + 1295790848 \beta ^3 \! -\! 812143744 \beta ^4 \! \nonumber \\ & -1467020480 \beta ^5 + 1711977904 \beta ^6 + 351336256 \beta ^7 - 1196850736 \beta ^8 \nonumber \\ & + 360786800 \beta ^9 + 231651000 \beta ^{10} - 165375000 \beta ^{11} + 28940625 \beta ^{12} \nonumber \end{align}

and hence \(\beta ^{*}={\rm Root[}G_{12,s},4{\rm ]}=2.23672\dots \, \). Furthermore we get (with \(s=2/7\) and \(\beta ^{*}= 2.23672\dots \)) \(\alpha ^{*}={\rm Root[}K_{9,s,\beta ^{*}},3{\rm ]}=2.23541\dots \, \).

Inserting these real numbers into the expression (5.10) and rearranging yields

\begin{align} & Z^{*}_{7,s=2/7}(x)=0.05920\dots +(-0.18072\dots )x+(-1.09752\dots )x^2 \\ & +1.16679\dots x^3+2.97213\dots x^4+(-1.98606\dots )x^5+(-2)x^6+x^7, \nonumber \end{align}

and evaluating \(|Z^{*}_{7,s=2/7}(1)|\) yields

\begin{equation} L^{*}=0.06618\dots \, . \end{equation}

5.24

Upon using the Mathematica RootReduce call we would get here the following explicit algebraic expression for \(a^{*}_{5,7}\) by means of a root object (and similar expressions for the other coefficients):

\begin{align} & a^{*}_{5,7}(s=2/7)= \label{coeffa57s27}\\ & ={\rm Root[}-873554110083 - 4116902938848 x - 2952492262344 x^2 \nonumber \\ & \ \ +20299695208200 x^3 + 65095318796016 x^4 + 97104326777504 x^5 \nonumber \\ & \ \ +91201373079984 x^6 + 61157144577920 x^7 + 31360014030976 x^8 \nonumber \\ & \ \ + 12198778044800 x^9 + 3294494784000 x^{10} + 529200000000 x^{11} \nonumber \\ & \ \ +37044000000 x^{12}, 2{\rm ]}. \nonumber \end{align}

In Fig. 3 the graph of \(Z^{*}_{7,s=2/7}\) on \(\boldsymbol {I}\) is displayed. â–¡

6 Explicit algebraic solution to ZFP for polynomials of degree \(n{\gt}7\)

As mentioned before, for \(n\in \{ 8,9,10,11,12\} \) we transfer our contributions to ZFP to a web-based repository [ 53 ] due to the bulky terms that occur for those values of \(n\).

In particular, we store there

• the Malyshev polynomials \(F_{m(n),s}\) and \(G_{m(n),s}\) of degree \(m(8)=16\), \(m(9)=18\), \(m(10)=24, m(11)=30\) and \(m(12)=32\),

• the recursive solution formulas for \(n\in \{ 8,9,10,11,12\} \), similar to those given in Theorem 4.1 and 5.1,

• the tentative terms \(Z_{n,\alpha ,\beta }\) for \(Z_{n,s}\) if \(n\in N\), including their coefficients when \(Z_{n,\alpha ,\beta }\) is expanded in power form.

In our second solution path the algebraic equation for the unknown variable \(y\) (see the proofs of Theorem 4.3 and 5.2 in Section 7) is of degree \(5\) if \(n=12\), see [ 41 , Formula (26) ] , so that \(Z_{12,\alpha , \beta }\) may contain root objects.

In Fig. 4 the graph of \(Z_{n,s}\) is displayed on \(\boldsymbol {I}\) for \(n=12\) and \(s=1\), used as an example for a solution of ZFP for polynomials of degree \(n=12\).

7 Proofs

A detailed proof of Theorems 4.1 and 5.1, which is based on executed Mathematica calls, is provided in [ 53 ] .

This is the corrected version (for \(n=6\)) of the misprinted second equation in [ 41 , Formula (37) ] , see the updated version of [ 41 ] on professor K. Schiefermayr’s homepage http://research.fh-ooe.at/de/publication/2410.

Here, \(\alpha \) and \(\beta \) are the (undetermined) endpoints of the alternation interval \([\alpha ,\beta ]\) to the right of \(\boldsymbol {I}\), and \(y_1\) and \(y_2\) are the (undetermined) alternation points in the interior of \(\boldsymbol {I}\) where \(Z_{6,s}\) is to attain the value \(-L\). To determine the optimal values of \(y_1\) and \(y_2\) we utilize Formula (26) of [ 41 , Theorem 2 ] which amounts to solve, for \(n=6\), a quadratic equation in the variable \(y\) and with coefficients which are certain well-defined determinants. After evaluation of these determinants, the quadratic equation in \(y\) reads as follows:

Computing its solutions \(y_1\) and \(y_2\) and inserting them into the representation (7.1) yields, after simplifications, the identity (4.15).

From (4.15) we extract here only the coefficient \(a_{5,6}(\alpha , \beta )\), which must be equal to \(-6s\), and in this way we obtain, after division by \((-6)\), a representation of \(s\) which depends solely on \(\alpha \) and \(\beta \)

With the goal to find the optimal values of the parameters \(\alpha \) and \(\beta \) we deploy Formula (34) of [ 41 , Corollary 3 ] which is a bivariate polynomial equation in the variables \(\alpha \) and \(\beta \). After evaluation of the well-defined determinants occurring there and after simplification we arrive at the following identity

The first factor, \(-(2+\alpha -\beta )\), we may neglect as it does not contribute to our overall goal to determine \(Z_{6,s}\), as we have convinced ourselves in an auxiliary calculation, see also the analogous exclusion carried out in our first solution path. We now merge equation (7.5) with the equation \(\tilde{h}(\alpha ,\beta )=0\), which is (7.10), but with factor \(-(2+\alpha -\beta )\) deleted. This we accomplish with the Mathematica call

and with the analogous call when solving for \(\beta \).

The outcome of these reductions is that for an assigned fixed \(s{\gt}\tan ^2\left(\pi /12\right)\), but \(s\neq 1/3\), the optimal parameters \(\alpha ^{*}\) and \(\beta ^{*}\) are to be determined as indicated in (4.17), that is, as certain positive roots \({\gt}1\) of \(F_{8,s}\) and \(G_{8,s}\) as given in (3.4), (3.5) and, for \(s=1/3\), as roots of \(f_6\) and \(g_6\) as given in (4.19) and (4.20).

This agrees with the second equation of Formula (36) in [ 41 ] .

Here, \(\alpha \) and \(\beta \) are the (undetermined) endpoints of the alternation interval \([\alpha ,\beta ]\) to the right of \(\boldsymbol {I}\), and \(y_1\) and \(y_2\) are the (undetermined) alternation points in the interior of \(\boldsymbol {I}\) where \(Z_{7,s}\) is to attain the value \(-L\). To determine the optimal values of \(y_1\) and \(y_2\) we utilize Formula (22) of [ 41 , Theorem 1 ] which amounts to solve, for \(n=7\), a quadratic equation in the variable \(y\) and with coefficients which are certain well-defined determinants. After evaluation of these determinants, the quadratic equation in \(y\) reads as follows:

Computing its solutions \(y_1\) and \(y_2\) and inserting them into the representation (7.20) yields, after simplifications, the identity (5.10).

From (5.10) we extract here only the coefficient \(a_{6,7}(\alpha , \beta )\), which must be equal to \(-7s\), and in this way we obtain, after division by \((-7)\), a representation of \(s\) which depends solely on \(\alpha \) and \(\beta \)

With the goal to find the optimal values of the parameters \(\alpha \) and \(\beta \) we utilize Formula (32) of [ 41 , Corollary 3 ] which is a bivariate polynomial equation in the variables \(\alpha \) and \(\beta \). After evaluation of the well-defined determinants occurring there and after simplification we arrive at the following identity

We now merge equation (7.34) with equation (7.35). This we accomplish with the Mathematica call

and with the analogous call when solving for \(\beta \). The outcome of this reduction is that for an assigned fixed \(s{\gt}\tan ^2\left(\pi /14\right)\), but \(s\neq 1/7\), the optimal parameters \(\alpha ^{*}\) and \(\beta ^{*}\) are to be determined as indicated in (5.12)–(5.15).

For the special case \(s=1/7\) the above reduction implies that the optimal parameters \(\alpha ^*\) and \(\beta ^{*}\) are to be determined as indicated in (5.16), (5.17), (5.18).

8 Concluding remarks

Note added in proof. After the submission of the present paper, we have addressed the open problem as described in Remark 8.4 above. We have shown in Theorem 3.1 of [ 38 ] that, for \(n=6\), an explicit univariate and radical parametrization exists for proper Zolotarev polynomials with uniform norm \(1\) on the interval \([-1, 1]\). Thus there are now three methods available to solve ZFP algebraically for \(n=6\): According to Theorem 4.1 and Theorem 4.3 of the present paper, and according to the description at the end of Section 2 above which is exemplified in [ 38 , Example 3.2 ] .