Computational Exploration of the Degree Sequence of the Malyshev Polynomials

Abstract

which is one of Kaltofen's favorite open problems in symbolic computation [5], asks to select the one among all monic polynomials of fixed degree ∗Supported by the EU-funded Hungarian grant EFOP-3.6.1-16-2016-00008 and by grant TUDFO/47138-1/2019-ITM of the Ministry for Innovation and Technology, Hungary.

Keywords

• Malyshev
• Abel-Pell diferential equation
• degree sequence
• extremal polyno-

-

≥ 2 and fixed 2nd leading coeficient ates the least from zero on the interval −1 = − ( >

tan2( 2 )) which devi= [−1, 1]. It turns out that this extremal polynomial also deviates least from zero among the monic polynomials of fixed degree on the set

which consists of two disjoint intervals, = ∪ [ ( ), ( )], 1 < = ( ) < = ( ), and can be characterized uniquely by roots of bivariate integer polynomials = (, ), = (, ).

These polynomials were coined Malyshev polynomials in [ 11 ], since Malyshev was the first who systematically enumerated these polynomials in 2002 [ 8 ] up to degree 5. In this paper we investigate the degree sequence of and

via symbolic computation up to degree 16 and seek for general patterns in the sequence. We analyse the obtained results by exploiting a connection of the Malyshev polynomials to Schiefermayr’s (asymmetric) homogeneous 4variate polynomials, whose zeros are so-called T -tuples [ 13 ] and to the generalized Zolotarev polynomials of Lebedev [ 7 ]. Moreover, we sketch a recursive method for computing the degree sequence without the explicit knowledge of the coeficients of the Malyshev polynomials. For the computations we used the computer algebra systems Maple and Mathematica.

1. Introduction

Definition 1.1.

tarev’s first problem

Let = [−1, 1] and let ||.||∞ denote the sup-norm on . Zolo(ZFP) amounts, for a given ≥ 2, to the determination of ︁∑ ( 0,··· , −2)∈R −1 || , ||∞ = ( ), where

min , ( ) = + (− ) −1 + , (1.1) and the second leading coeficient, and of the extremal polynomial, ,* , where ∈ R is assumed. Thus = 1 −1 = (− ), although thought of as being ifxed, may attain arbitrary values, so that we save the notation 0 for a concrete prescribed number . It sufices to consider the c“omplicated” cases see [ 1, 2, 7, 15 ]. From these sources we adapt the following theorem: > tan2( 2 ),

Theorem 1.2. For all

and is called a monic proper Zolotarev polynomial.

≥ 2 and > tan2( 2 ) the solution , * of (1.1) is unique

The above best-approximation problem was posed by Chebyshev to Zolotarev, see [15, p.2]. It is the first of four famous problems in Approximation Theory which were considered by Zolotarev [ 15 ], hence the name ZFP. Recently, with the advance of symbolic computation, Kaltofen ranked ZFP and the related computational (quantifier elimination) problem for > 5 to one of his favorite open problems in symbolic computation [ 5 ]. From the quoted literature there follows: Lemma 1.3. For fixed ≥ 2 and varying ∈ (tan2( 2 ), ∞), , * parameter family of polynomials which may be parametrized, for instance, with . forms a oneinterval [, A particular ,* 0 zero among the monic polynomials of fixed degree on the set which consists of ], where 1 < = ( 0) <

= ( 0). ,* 0 also deviates the least from two disjoint intervals, = ∪˙[,

], see Figure 1. equioscillates on

times and twice on the uniquely determined Example 1.4. For = 4 and = 0 = 5/18 (> tan2( 8 ) = 3 − 2 power form solution to (1.1) with least deviation 4(5/18) = 169460803 is √2) the explicit 4*,5/18( ) = 53 243 + 15470 19683 − 243 296 2 − 9 10 3 + 4 with [ 0, 0] = ︂[ 37 43 ]︂ .

Remark 1.5. The coeficients of the extremal polynomial are all rationals. However, for >

4 no rational solution is known and in fact one can prove that for 4 < <

14, all parametrizations of the monic proper Zolotarev polynomials must be non-rational ones, for = 5 see [4], and for = 6 see [ 12 ] 4*,5/18 in Example 1.4 and see also the genuses in Table 3. -1 -1.0 -0.5 0.5 1 1.0 α β

1.5 0.2 -0.2 -0.4

Surprisingly, Zolotarev in 1877 solved ZFP with the aid of elliptic functions. However, this solution is “too complicated to be useful in practice,” see [ 12 ], and indeed even for the simplest interesting case = 2, the transformation of this solution formula to a pure algebraic power form is highly nontrivial, see [2]. We also note that numerical (approximate) solutions of ZFP for a particular = 0 can be obtained via the Remez-exchange algorithm [ 10 ].

However, in this article, we use neither the elliptic solution-formulae nor the approximate solutions for a possible reconstruction of the exact algebraic symbolic solution. For our purposes, that is, to derive a generic symbolic algebraic solution for a particular , but for an arbitrary , we found that the most useful characterization of the solution ,* is given by the Abel-Pell diferential equation, see [1, p.17]. For the description of the solution of ZFP, we make use of the bivariate Malyshev polynomials. We will introduce them via a suitable form of the Abel-Pell diferential equation in the next sections.

We note that recent research papers solved ZFP symbolically and algebraically completely for ≤ 12 ([ 6, 11 ]), however, our explicit investigation of the degree sequence of the Malyshev polynomials for 1 < ≤ 16 and of their intrinsic characteristic properties seems to be novel.

ZFP can be formulated as a real quantifier elimination problem, see [ 3, 14 ]. If we exploit the equioscillation property of the sought-for best-approximating polynomial, then the formula matrix of the quantifier elimination problem consist of mainly (nonlinear) polynomial equations and only a few polynomial inequalities which can be considered as side conditions of the solutions of the equation system. Since for a particular and , the equation system has only finitely many solutions, our computational strategy, which first solves the polynomial equation system via Groebner Basis and then selects the proper solution of ZFP, proves to be the most promising one.

Still, somewhat surprisingly, not all the known descriptions of the algebraic solutions in the literature use the Abel-Pell diferential equation representation and the Malyshev polynomials as we propose, see e.g. [ 3, 6 ]. 2. The degree sequence of the Malyshev polynomials Definition 2.1. The uniquely determined endpoints of the interval [, ] = [ ( ), ( )], which is given in Lemma 1.3, can be characterized by roots of integer bivariate polynomials ( )(, ) and ( )(, ) of degree ( ). We coin these polynomials

( ), ( ) Malyshev polynomials in view of [ 8 ], see also [ 11 ].

The main subject of this article is to determine the degree sequence ( ) of the Malyshev polynomials for small ’s and to explore some patterns in this sequence. The here computed values ( ) for > 12 are new.

Example 2.2. (4) = 4 and the polynomials 4 (4) and 4 (4) (see also [ 8 ]) are given as 4 (4)(, ) = 44(, ) = (−13 − 136 − 448 2 − 896 3 + 256 4)+ (44 + 184 + 128 2 − 640 3) + (−22+168 + 576 2) 2 + (−36−216 ) 3 + 27 4, 4 (4)(, ) = 44(, ) = 44(−, − ) = (−13 + 136 −448 2 + 896 3 + 256 4)+ (−44 + 184 − 128 2 − 640 3) + (−22−168 + 576 2) 2 + (36−216 ) 3 + 27 4. Lemma 2.3. The solution = ( ) of (1.1) satisfies the Abel-Pell diferential equation

(1 − 2)( − )( − )( ′)2( ) = 2( 2 ( ) − 2( ))( − ( + )/2 + )2, (2.1) where the intended meaning of ( ) is given in Definition 1.1 and and are given in Definition 2.1.

For a proof, see [ 1, 13 ].

Lemma 2.4. Relying on Lemma 2.3, a coeficient comparison will transform the problem of solving ZFP to a solution of a nonlinear polynomial system for each particular . This is then analysed by Groebner basis techniques. From the finitely many solutions of this the desired one, which yields the proper monic Zolotarev polynomial, can be strategically selected with the aid of equality and inequality constraints. Considering as an indeterminate in the above , the computation of ( ) and ( ) ( ≤ 16) is accomplished with the aid of the computer algebra systems Maple [ 9 ] and Mathematica [ 17 ]. For the concrete coeficients of the Malyshev polynomials we refer, because of the bulkiness of the formulae, to the web-based repository [ 16 ]. ( ) 3. Computational results Theorem 3.1. Table 1 shows the first 15 elements of the degree sequence ( ) of the Malyshev polynomials

and . These elements were computed according to Lemma 2.3 and 2.4. are displayed in Figure 2.

Remark 3.2. We note that for a fixed (rational) = 0, a suitable real root of the then univariate

( ) and ( ) describes the endpoints of the interval [, ]. An alternative characterization would be to provide the bivariate polynomial ( ) (, ) where the points of a suitable part of the planar curve ( ) (, ) = 0 correspond to the ordered pair (, ), see [ 4, 11 ]. The bivariate polynomial has the same degree as the Malyshev polynomials ( equals to the factor of degree ( ) of the resultant

( ( ), ( ))). For reference purposes, they also have been put to the repository [ 16 ], and we point out that they are novel for 6 (6) = 86 and 7 (8) = 172 are given in [ 11 ]. The planar curves for = 2, 3, 4, 5 ≥ 8. β α factors of the in ascending order and in particular, to consider the odd and even cases of separately.

Lemma 3.3. If, in Table 1, is an odd prime, then we have

( ) = (2 + 1) = and for 2-powers in Table 1 we have (3.1) (3.2) (3.3) ︂⌊ 2 ⌋︂ 4 7 12 12 = 8 16 16 2

However, for composite numbers, neither of the simple formulae (3.1), (3.2) works. Rather, the following Theorem 3.4 holds, which explains the gap between the formulae and the computed values.

Theorem 3.4 (Lebedev [ 7 ]). For a composite number , the Abel-Pell diferential equation (2.1) without side conditions has polynomial solution(s) diferent from the proper Zolotarev polynomial ,* .

With the natural side conditions (−1) = (−1) , (1) = − , ( ) = − , ( ) = , ( ̸ = ̸ = ±1) one can rule out some of these solutions, but not all of them. The additional polynomial solutions satisfying the natural side conditions are generalized Zolotarev polynomials. They have the form ( ,* ), where is the -th Chebyshev polynomial of the first kind on and = · , >

1. It turns out that if 2 ̸ | , then ( ,* ) solves (2.1) with the natural side conditions above (and no other polynomial solution exists). Therefore, for some composite , the bivariate polynomial 1 = 1(, ) in the variable and or 2 = 2(, ) in the variable

and , in the elimination ideal defined by the nonlinear polynomial system

and the natural side conditions, decomposes into several factors. However, the sum of their total degrees is actually ( ) =

4 ︃{ 24−1 , if n is odd,

2 , if n is even. light the cases where there is a positive gap between the two sequences. Remark 3.5. We note that in [ 13 ], Schiefermayr defines 4-variate homogeneous polynomials ∈ C[, , ,

] in a constructive way via determinants which characterize whether a slightly generalized version of the Abel-Pell equation (2.1), namely ( − )( − )( − )( − )( ′)2( ) = 2( ( )2 − Λ2 ( ))( − ( + + + )/2 + )2, (depending on the complex numbers , , , ), has a (polynomial) solution =

T . It is proved there that the solution exists, which is not a solution for / 2, if and only if the polynomial inverse image T−1[−1, 1] consists of two Jordan arcs with endpoints , , , . The (, , ,

)-quadruples formed by the endpoints are called T -tuples. Then these endpoints are described purely algebraically.

The elements in the quadruple ( 0, 0, 0, 0) can occur as endpoints of the curves if and only if ( 0, 0, 0, 0) = 0. The polynomial is of degree ( ) as given in (3.3), and with the special choice = , = 1, = −1, = (see [13, Section 4.2]) (which corresponds to normalizing one of the curves), specializes to 2(, ) and for odd primes and 2-powers to ( ) (, ).

Summarizing our results, we sketch a simple (recursive) algorithm for the computation of ( ) without the explicit knowledge of the Malyshev polynomials

( ), ( ).

Lemma 3.6. If >

1 is an odd prime or a 2-power, then ( ) = ( ) as given in (3.3). Otherwise, assume that ( ) is computed, if < .

If is even, let ′ = / 2 1 , that is, the product of the odd prime powers in . conditions and we have to subtract (2 1 2) from ( ).

Assume that ′ decomposes into two factors, ′ = 1 · 2, where the first factor is nontrivial. Then 1 ( 2* 1 · 2 , ) is also a solution of (2.1) with the natural side In a similar way, if is an odd composite number and thus ′ = , then both · factors 1 and 2 should be nontrivial.

Example 3.7.

because in the latter case ′ = 18/2 = 9 and ′ factors into 9 = 9 · 1 = 3 · 3. Since 9( 2*, ) and 3( 6*, ) also solves (2.1) with the natural side conditions, we have to subtract (2) = 1 and (6) = 8 from (18) = 81.

Remark 3.8. The computed elements of the sequence ( ) may also play a role in the analysis of the coeficients of the polynomials ( ). For instance, while the coeficient of ( ) is 1 in ( ), the constant term of ( ) seems to be 2 ( ). Remark 3.9. For the -polynomials, we also computed the genus of the curve ( ) = 0, up to degree 13. This information may be used for the parametrization of the Zolotarev polynomials. Table 3 shows the result, which confirms and extends the data given in [4, p. 179] and [ 12 ]. The = 2, 3, 4 cases are classical results.

The

= 5, 7, 8, 11 cases were first given in [4] and = 6 case in [ 12 ]. The = 9, 10, 12, 13 cases seem to be new. (18) = (18) − (2) − (6) =

− 1 − 8 = 72, 172 − 1 4 182 4 serve that the sequence ( ) does coincide with the infinite sequence A002620 in the OEIS database (see oeis.org). It was also observed in [ 11 ] that the finite sequence { ( )}12=2 coincides with the first 11 elements in the infinite sequence A055932. As the particular case = 13 now shows, this coincidence breaks down for ≥ 13.

4. Conclusion

Based on the Abel-Pell diferential equation and deploying Groebner basis techniques, we computed symbolically the bivariate Malyshev polynomials , and the polynomials

(defining a reduced relation curve) up to degree = 16. All of them play a crucial role in the purely algebraic description of the solutions to ZFP.

The bulky expressions for , ,

have been stored in the ZFP web-based repository [ 16 ]. By analysing the patterns in the degree sequence of the Malyshev polynomials and consulting the current literature, we gave a recursive algorithm for computing an arbitrary element of the degree sequence without the explicit knowledge of the Malyshev polynomials. We also computed the genuses of the curves classical and generalized Zolotarev polynomials. = 0 for

≤ 13. The computational results contribute to the analysis of the

Acknowledgements.

The author thanks Dr. Heinz-Joachim Rack, Hagen (Germany) for helpful comments on an earlier version of the paper. (Russian 1987). [1] Achieser, N.I., Function theory according to Chebyshev. In: Mathematics of the 19th century, Vol. 3 (A.N. Kolmogorov et al. (Eds.)), Birkhäuser, Basel, 1998, 1–81 [2] Carlson, B.C., Todd, J., Zolotarev’s first problem - the best approximation by polynomials of degree ≤ − 2 to − −1 in [−1, 1], Aeq. Math, Vol. 26 (1983), [3] Collins, G. E., Application of quantifier elimination to Solotaref’s approximation problem. In: Stability Theory (Hurwitz Centenary Conference, Ascona, Switzerland, 1995, R. Jeltsch et al. (Eds.)), Birkhäuser, Basel, ISNM, Vol. 121 (1996), 181–190. [4] Grasegger,

G.,

Vo, N.Th., An algebraic-geometric method for computing Zolotarev polynomials. In: Proceedings International Symposium on Symbolic and

References

Algebraic Computation (ISSAC '17, Kaiserslautern , Germany, M. Burr (Ed.)), ACM, New York, 2017 , 173 - 180 .

[5] Kaltofen , E. , Challenges of symbolic computation: My favorite open problems , J. Symb. Comput. , Vol. 29 ( 2000 ), 891 - 919 .

[6] Lazard , D. , Solving Kaltofen's challenge on Zolotarev's approximation . In: Proceedings International Symposium on Symbolic and Algebraic Computation (ISSAC '06 , Genoa , Italy, B. Trager (Ed.)), ACM, New York, 2006 , 196 - 203 .

[7] Lebedev V.I. , Zolotarev polynomials and extremum problems , Russ. J. Numer. Anal. Math. Model. , Vol. 9 ( 1994 ), 231 - 263 .

[8] Malyshev , V.A. , Algebraic solution of Zolotarev's problem, St . Petersburg Math. J. , Vol. 14 ( 2003 ), 711 - 712 ( Russian 2002 ).

[9] Maplesoft , Maple 2019 , Maplesoft, a division of Waterloo Maple Inc ., Waterloo , Ontario, Canada.

[10] Remez , E. Ya , Sur le calcul efectif des polynomes d'approximation de Tchebichef. C. R. Paris, Vol. 199 ( 1934 ), 337 - 340 .

[11] Rack , H.-J., Vajda , R. , Explicit algebraic solution of Zolotarev's first problem for low-degree polynomials , J. Numer. Anal. Approx. Theory , Vol. 48 ( 2019 ) 175 - 201 .

[12] Rack , H.-J., Vajda , R. , An explicit univariate and radical parametrization of the sextic proper Zolotarev polynomials in power form , Dolomites Res. Notes Approx ., Vol. 12 ( 2019 ), 43 - 50 .

[13] Schiefermayr K. , Inverse polynomial images which consists of two Jordan arcs - An algebraic solution , J. Approx. Theory , Vol. 148 ( 2007 ), 148 - 157 .

[14] Vajda , R. , Efective real quantifier elimination , In: J. Karsai , R. Vajda (eds.), Interesting Mathematical Problems in Sciences and Everyday Life - 2011 , University of Szeged, 1 - 18 .

[15] Zolotarev , E.I. , Applications of elliptic functions to problems on functions deviating least or most from zero (Russian), Zapiski Imper . Akad. Nauk St. Petersburg Vol. 30 ( 1877 ), Collected Works , Vol. 2 , Leningrad , 1932 , 1 - 59 . URL http://www.math.technion.ac.il/hat/fpapers/zolo1.pdf

[16] www.math.u-szeged.hu/∼vajda/ZFP

[17] Wolfram Research , Inc., Mathematica, Version 12 .0, Champaign (IL), USA, 2019 .