# Explicit algebraic solution of Zolotarev’s First Problem for low-degree polynomials

December 21, 2018; accepted: May 28, 2019; published online: January 31, 2020.

\(^\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.

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\in {\mathbb N}\backslash \{ 1\} \) and for a given \(s\in {\mathbb R}\backslash \{ 0\} \), the monic polynomial solution \(Z^{*}_{n,s}\) to the following best approximation problem: Find

where the \(a_k\), \(0\le k\le n-2\), vary in \(\mathbb R\). It suffices to consider the cases \(s{\gt}\tan ^2\left(\pi /(2n)\right)\).

In 1868 Zolotarev provided a transcendental solution for all \(n\geq 2\) in terms of elliptic functions. An explicit algebraic solution in power form to *ZFP*, as is suggested by the problem statement, is available only for \(2\le n\le 5\).\({}^{1}\) We have now obtained an explicit algebraic solution to *ZFP* for \(6\le n\le 12\) in terms of roots of dedicated polynomials.

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

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

**MSC.** 41A10, 41A29, 41A50.

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

# 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\)).

An algebraic solution to *ZFP* for \(n=6\) and for an assigned fixed \(s{\gt} \tan ^2\left(\pi /12\right)\), but \(s\neq 1/3\), can be deduced recursively as follows, see (4.1), (4.2):

For the special choice \(s=1/3\), \(\alpha ^{*}\) and \(\beta ^{*}\) needs to be computed as given in (4.18), (4.19) and (4.20). â–¡

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

and

Picking the appropriate (largest) positive root \({\gt}1\) of these polynomials gives

Inserting these real numbers into the expression for \(a_{4}\) in Theorem 4.1 gives

Similarly, after computing the other coefficients and the norm, we get

and

## 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*.

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 \(\alpha \) and \(\beta \), that is

and

We refrain here from representing \(Z_{6,\alpha ,\beta }\) in the power form since the expansion \(Z_{6,\alpha ,\beta }(x)=\sum _{k=0}^6 a_{k,6}(\alpha ,\beta ) x^k\) with \(a_{5,6}(\alpha ,\beta )=-6s\) and \(a_{6,6}(\alpha ,\beta )=1\) produces bulky coefficients \(a_{k,6}(\alpha ,\beta )\) for \(k=0,\dots , 4\). But we provide them, for the reader’s convenience, in our web-based repository [ 53 ] .

For the special choice \(s=1/3\), determine the corresponding optimal \(\alpha ^*\) and \(\beta ^{*}\) as

where

(iii) Then replace in the expression (4.15) above, the parameter \(\alpha \) by the real number \(\alpha ^*{\gt}1\) and the parameter \(\beta \) by the real number \(\beta ^{*}{\gt}1\) (with \(1{\lt}\alpha ^*{\lt}\beta ^*\)) and rearrange terms in order to obtain a power form representation of the sextic polynomial in the variable \(x\). Its coefficients \(a_{k,6}(\alpha ^{*},\beta ^{*})\) agree with the optimal coefficients \(a^{*}_{k,6}(s)\), for \(k=0,\dots ,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(\alpha ^*,\beta ^*)=L^*\) in (4.16), the least deviation of \(Z^{*}_{6,s}\) on \(\boldsymbol {I}\) from the zero-function. â–¡

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, for \(s\neq 1/3\), by executing the following simple *Mathematica* call (where \(Z6\alpha \beta =Z_{6,\alpha ,\beta }\), \(F8s=F_{8,s}\), \(G8s=G_{8,s}\) and \(s_0\) is an assigned fixed value for \(s\), and \(p\) is an assigned fixed integer value for the \(p\)-digit precision of the numerical result):

If we assume that \(s{\gt}\tan ^2(\pi /12)\) is an integer or a rational number \(a/b\), then we can explicitly express each \(a^{*}_{k,6}(s)\) as a root object \({\rm Root[}P_8,k{\rm ]}\) (where \(P_8\) is a dedicated integer polynomial of degree eight), for example by executing the *Mathematica* call **RootReduce**.

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\)

and

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

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

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

A corresponding call in *Mathematica* would read here

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):

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

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:

An algebraic solution to *ZFP* for \(n=7\) and for an assigned fixed \(s{\gt}\tan ^2\left(\pi /14\right)\), but \(s\ne 1/7\), can be deduced recursively as follows, see (5.1), (5.2):

For the special choice \(s=1/7\), \(\alpha ^{*}\) and \(\beta ^{*}\) needs to be computed as given in (5.16), (5.17) and (5.18). â–¡

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

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 \(\alpha \) and \(\beta \), that is

and

We refrain here from representing \(Z_{7,\alpha ,\beta }\) in the power form since the expansion \(Z_{7,\alpha ,\beta }(x)=\sum _{k=0}^7 a_{k,7}(\alpha ,\beta ) x^k\) with \(a_{6,7}(\alpha ,\beta )=-7s\) and \(a_{7,7}(\alpha ,\beta )=1\) produces bulky coefficients \(a_{k,7}(\alpha ,\beta )\) for \(k=0,\dots , 5\). But we provide them, for the reader’s convenience, in our web-based repository [ 53 ] .

Deploying the polynomial as given in (3.9) and inserting there the number \(\beta ^{*}\), calculate the corresponding optimal \(\alpha =\alpha (s,\beta ^{*})=\alpha ^{*}\) (with \(1{\lt}\alpha ^{*}{\lt}\beta ^{*}\)) as

For the special choice \(s=1/7\) calculate the corresponding optimal \(\alpha ^{*}\) and \(\beta ^{*}\) as

where

and

(iii) Then replace in the expression (5.10) above, the parameter \(\alpha \) by the real number \(\alpha ^*{\gt}1\) and the parameter \(\beta \) by the real number \(\beta ^{*}{\gt}1\) (with \(1{\lt}\alpha ^*{\lt}\beta ^*\)) and rearrange terms in order to obtain a power form representation of the septic polynomial in the variable \(x\). Its coefficients \(a_{k,7}(\alpha ^{*},\beta ^{*})\) agree with the optimal coefficients \(a^{*}_{k,7}(s)\), for \(k=0,\dots ,5\), of the sought-for monic proper Zolotarev polynomial \(Z^{*}_{7,s}\). Finally, evaluate \(Z^{*}_{7,s}(x)\) at \(x=1\) in order to get, up to sign, the real number \(L(\alpha ^*,\beta ^*)=L^*\) in (5.11), the least deviation of \(Z^{*}_{7,s}\) on \(\boldsymbol {I}\) from the zero-function. â–¡

The just described step allows to generate numerical values of arbitrary precision for the optimal coefficients \(a^{*}_{k,7}(s)\) of \(Z^{*}_{7,s}\) and can be accomplished, for \(s\neq 1/7\), by executing the following *Mathematica* call (where \(Z7\alpha \beta =Z_{7,\alpha ,\beta }\), \(G12s=G_{12,s}\) and \(K9s\beta =K_{9,s,\beta }\) and \(s_0\) is an assigned fixed value for \(s\), and \(\kappa =3,4,6\) according to the position of \(s\) on the positive \(x\)-axis, and \(p\) is an assigned fixed integer value for the \(p\)-digit precision of the numerical result):

Likewise as for \(n=6\), if we assume that \(s{\gt}\tan ^2(\pi /14)\) is an integer or a rational number \(a/b\), then we can explicitly express each \(a^{*}_{k,7}(s)\) as a root object \({\rm Root[}P_{12},k{\rm ]}\) (where \(P_{12}\) is a dedicated integer polynomial of degree twelve), for example by executing the *Mathematica* call **RootReduce**.

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\)

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

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

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):

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

S. N. Bernstein provided the following asymptotic approximation, \(L_{\infty }\), to the constant \(L\), the least deviation of the proper monic Zolotarev polynomial from the zero-function on \(\boldsymbol {I}\) (see [ 3 , p. 1057 ] , [ 4 , p. 24 ] , [ 5 , p. 208 ] and also [ 32 ] ):

Upon comparing \(L_{\infty }\) to the special instances of \(L\) which we have obtained in Examples 4.2, 4.6, 5.5, one observes that Bernstein’s formula is quite satisfactory.

We note that Bernstein also addressed the computational complexity he encountered when he tried to determine the uniform norm of \(Z_{n,s}\)
[
5
,
p. 511
]
: *When I first considered this same problem [of determining \(L\)] in 1913, I soon recognized its algebraic difficulties, which increase rapidly with the degree \(n\) of the polynomial, and it occurred to me to formulate the asymptotic problem.*

It is known that \(\alpha =\alpha (n,s)\) and \(\beta =\beta (n,s)\) converge to \(ns\), the negative second leading coefficient of the proper monic Zolotarev polynomial \(Z_{n,s}\), when \(n\to \infty \), see *e.g.*
[
30
,
p.
69
]
. For \(n\in N\) we have in particular

These inequalities turn out to be useful in checking calculations or reducing search trees in connection with *ZFP*. To prove (8.2), we use Formulas (30), (31) in
[
41
]
which are based on the \(y_j\) (alternation points in the interior of \(\boldsymbol {I}\) where the value \(-L\) is attained). But we also need the analogous formulas based on the \(x_j\) (alternation points in the interior of \(\boldsymbol {I}\) where the value \(L\) is attained) which are not given in
[
41
]
. These formulas read:

The analogous proof rests on Vieta’s theorem applied to the polynomial \(Z_{n,s}-L\). Inequalities (8.2) then follow from [ 41 , Formulas (30), (31) ] and (8.3) by considering the transformation of the graph of \(Z_{n,s}\) when \(s\) tends towards the boundaries of the interval \((\tan ^2\left(\pi /(2n)\right),\infty )\), see [ 1 , p. 19 ] , [ 18 , pp. 247-248 ] .

It is an open problem to investigate which type of explicit parameterized representation (rational, radical, etc.) exists for proper Zolotarev polynomials, if \(n{\gt}5\), see Section 2. Based on the methods and results of the present paper, we intend to address this problem in a future joint research project. *Added in proof*: See our recent one-parameter power form solution for \(n=6\) in
[
38
]
.

*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
]
.

# Bibliography

- 1
*N.I. Achieser*,*Function theory according to Chebyshev*. In: Mathematics of the 19th century, Vol. 3 (A.N. Kolmogorov et al. (Eds.)), Birkhäuser, Basel, 1998, pp. 1-81 (Russian 1987).- 2
*N.I. Achieser*,*Theory of Approximation*, Dover Publications, Mineola (NY), USA, 2003 (Russian 1947).- 3
*S.N. Bernstein*,*Sur quelques propriétés asymptotiques des polynomes*, C. R.**157**(1913), pp. 1055-1057.- 4
*S.N. Bernstein*,*Leçons sur les Propriétés Extrémales et la Meilleure Approximation des Fonctions Analytiques d’une Variable Réelle*, Gauthier-Villars, Paris, France, 1926.- 5
*S.N. Bernstein*,*Collected Works, Vol. I. Constructive Theory of Functions (1905- 1930)*(Russian), Akad. Nauk SSSR, Moscow, Russia, 1952.- 6
- 7
- 8
- 9
- 10
*P. Erdős, G. Szegő*,*On a problem of I. Schur*, Ann. Math.**43**(1942), pp. 451-470.- 11
*R.F. Farkhutdinova*,*Approximate analytical formulas for the coefficients of Zolotarev polynomials and an economization process with the use of Zolotarev polynomials*(Russian). In: Uniform approximations and moment problems (Work Collection (Russian), M.Ja. Zinger (Ed.)), Vladivostok, Russia, 1977, pp. 126-135.- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
*L.G. Lozner*,*Piecewise linear estimates of coefficients of Zolotarev polynomials*, Funkts. Anal.**34**(1993), pp. 35-39.- 20
*V.A. Malyshev*,*The Abel equation*, St. Petersburg Math. J.**13**(2002), pp. 893-938 (Russian 2001).- 21
*V.A. Malyshev*,*Algebraic solution of Zolotarev’s problem*, St. Petersburg Math. J.**14**(2003), pp. 711-712 (Russian 2002).- 22
- 23
*A.A. Markov*,*Lectures on functions of minimal deviation from zero*(Russian), 1906. In: Selected Works: Continued fractions and the theory of functions deviating least from zero, OGIZ, Moscow-Leningrad, 1948, pp. 244-291.- 24
- 25
- 26
*S. Paszkowski*,*The Theory of Uniform Approximation I. Non-asymptotic Theoretical Problems*, Rozprawy Matematyczne XXVI, PWN, Warsaw, 1962.- 27
- 28
- 29
- 30
- 31
- 32
- 33
*H.-J. Rack*,*On polynomials with largest coefficient sums*, J. Approx. Theory**56**(1989), pp. 348-359.- 34
- 35
- 36
*H.-J. Rack*,*Explicit algebraic solution to Zolotarev’s First Problem for polynomials of degree \(n\in \{ 6,7,8\} \)*, Abstract in: IX Jaén Conference on Approximation Theory (Úbeda, Spain, July 8-13, 2018).- 37
- 38
- 39
*Th.J. Rivlin*,*Chebyshev Polynomials*, 2nd edition, J. Wiley & Sons, New York (NY), USA, 1990.- 40
- 41
- 42
- 43
- 44
*M.L. Sodin, P.M. Yuditskii*,*Functions that deviate least from zero on closed subsets of the real axis*, St. Petersburg Math. J.**4**(1993), pp. 201-241.- 45
- 46
- 47
- 48
- 49
- 50
*Wolfram Research, Inc.*,*Mathematica*, Version 11.0, Champaign (IL), USA, 2016.- 51
*E.I. Zolotarev*,*On a problem of least values, Dissertation pro venia legendi*(Russian), lithographed paper, St. Petersburg (1868), Collected Works, vol. 2, Leningrad 1932, pp. 130-166.- 52
- 53