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

  • Heinz Joachim Rack Dr. Rack Consulting GmbH
  • Robert Vajda Bolyai Institute, University of Szeged, Aradi Vertanuk tere 1, 6720 Szeged, Hungary
Keywords: Abel-Pell differential equation, algebraic solution, best approximation, Chebyshev, first problem, Groebner basis, least deviation from zero, Malyshev, polynomial, Schiefermayr, two fixed leading coefficients, uniform norm, Zolotarev

Abstract

E.I. Zolotarev's classical so-called First Problem (ZFP), which was posed to him by P.L. Chebyshev, is to determine, for a given \(n\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
\[
\min_{a_k}\max_{x\in[-1,1]}|a_0+a_1 x+\dots+a_{n-2}x^{n-2}+(-n s)x^{n-1}+x^n|,
\]
where the \(a_k, 0\le k\le n-2\), vary in \(\mathbb R\). It suffices to consider the cases \(s>\tan^2\left(\pi/(2n)\right)\).

In 1868 Zolotarev provided a transcendental solution for all \(n\geq2\) 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].

References

N.I. Achieser, Function theory according to Chebyshev. In: Mathematics of the 19th century, Vol. 3 (A.N. Kolmogorov et al. (Eds.)), Birkhauser, Basel, 1998, pp. 1-81 (Russian 1987), https://doi.org/10.1007/978-3-0348-8851-6_1

N.I. Achieser, Theory of Approximation, Dover Publications, Mineola (NY), USA, 2003 (Russian 1947).

S.N. Bernstein, Sur quelques proprietes asymptotiques des polynomes, C. R. 157 (1913), pp. 1055-1057.

S.N. Bernstein, Lecons sur les Proprietes Extremales et la Meilleure Approximation des Fonctions Analytiques d’une Variable Reelle, Gauthier-Villars, Paris, France, 1926.

S.N. Bernstein, Collected Works, Vol. I. Constructive Theory of Functions (1905-1930) (Russian), Akad. Nauk SSSR, Moscow, Russia, 1952.

B. Buchberger, Theoretical basis for the reduction of polynomials to canonical forms, ACM SIGSAM Bull. (ACM) 10 (1976), pp. 19-29. https://doi.org/10.1145/1088216.1088219

B.C. Carlson, J. Todd, Zolotarev’s first problem - the best approximation by polynomials of degree ≤n−2 to xn−nσx n−1 in [−1, 1], Aeq. Math 26 (1983), pp. 1-33. https://doi.org/10.1007/bf02189661

P.L. Chebyshev, Theorie des mecanismes connus sous le nom de parallelogrammes, Mem. Acad. Sci. St. Petersburg 7 (1854), pp. 539-568.

G.E. Collins, Application of quantifier elimination to Solotareff’s approximation problem. In: Stability Theory (Hurwitz Centenary Conference, Ascona, Switzerland, 1995, R. Jeltsch et al. (Eds.)), Birkh ̈auser, Basel, ISNM 121 (1996), pp. 181-190. https://doi.org/10.1007/978-3-0348-9208-7_19

P. Erdos, G. Szego, On a problem of I. Schur, Ann. Math. 43 (1942), pp. 451-470. https://doi.org/10.2307/1968803

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.

G. Grasegger, N.Th. Vo, An algebraic-geometric method for computing Zolotarev polynomials, Technical Report no. 16-02 (RISC Report Series, Johannes Kepler University, Linz, Austria), 2016, pp. 1-17. https://doi.org/www3.risc.jku.at/publications/download/risc_5271/RISCReport1602.pdf

G. Grasegger, An algebraic-geometric method for computing Zolotarev polynomials-Additional information, Technical Report no. 16-07 (RISC Report Series, Johannes Kepler University, Linz, Austria), 2016, pp. 1-12, https://doi.org/www3.risc.jku.at/publications/download/risc_5340/RISC1607.pdf

G. Grasegger, N.Th. Vo, An algebraic-geometric method for computing Zolotarev polynomials. In: Proceedings International Symposium on Symbolic and Algebraic Computation (ISSAC ’17, Kaiserslautern, Germany, M. Burr (Ed.)), ACM, New York, 2017, pp. 173-180, https://doi.org/10.1145/3087604.3087613

W. Haussmann, K. Zeller, Approximate Zolotarev polynomials, Comput. Math. Appl. Part B12 (1986), pp. 1133-1140, https://doi.org/10.1016/0898-1221(86)90237-3

E. Kaltofen, Challenges of symbolic computation: My favorite open problems, J. Symb. Comput. 29 (2000), pp. 891-919, https://doi.org/10.1006/jsco.2000.0370

D. Lazard, 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, pp. 196-203, https://doi.org/10.1145/1145768.1145803

V.I. Lebedev, Zolotarev polynomials and extremum problems, Russ. J. Numer. Anal. Math. Model. 9 (1994), pp. 231-263, https://doi.org/10.1515/rnam.1994.9.3.231

L.G. Lozner, Piecewise linear estimates of coefficients of Zolotarev polynomials, Funkts. Anal. 34 (1993), pp. 35-39.

V.A. Malyshev, The Abel equation, St. Petersburg Math. J. 13 (2002), pp. 893-938 (Russian 2001).

V.A. Malyshev, Algebraic solution of Zolotarev’s problem, St. Petersburg Math. J. 14 (2003), pp. 711-712 (Russian 2002).

A.A. Markov, On a question of D.I. Mendeleev (Russian), Zapiski Imper. Akad. Nauk St. Petersburg 62 (1889), pp. 1-24, https://doi.org/www.math.technion.ac.il/hat/fpapers/mar1.pdf

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.

V.A. Markov, On functions deviating least from zero on a given interval (Russian), Izdat. Akad. Nauk St. Petersburg 1892, https://doi.org/www.math.technion.ac.il/hat/fpapers/vmar.pdf

G.V. Milovanovic, D.S. Mitrinovic, Th.M. Rassias, Topics in Polynomials: Extremal Problems, Inequalities, Zeros, World Scientific, Singapore, 1994, https://doi.org/10.1142/9789814360463

S. Paszkowski, The Theory of Uniform Approximation I. Non-asymptotic Theoretical Problems, Rozprawy Matematyczne XXVI, PWN, Warsaw, 1962.

F. Peherstorfer, Orthogonal-and Chebyshev polynomials on two intervals, Acta Math. Hung. 55 (1990), pp. 245-278, https://doi.org/10.1007/bf01950935

F. Peherstorfer, On the connection of Posse’s L1- and Zolotarev’s maximum- norm problem, J. Approx. Theory 66 (1991), pp. 288-301, https://doi.org/10.1016/0021-9045(91)90032-6

. F. Peherstorfer, K. Schiefermayr, Description of extremal polynomials on several intervals and their computation I, II, Acta Math. Hungar. 83 (1999), pp. 27-58, pp. 59-83, https://doi.org/10.1023/a:1006607401740%20and%2010.1023/a:1006659402649

F. Peherstorfer, K. Schiefermayr, Description of inverse polynomial images which consist of two Jordan arcs with the help of Jacobi’s el liptic functions, Comput. Methods Funct. Theory 4 (2004), pp. 355-390, https://doi.org/10.1007/bf03321075

F. Peherstorfer, Asymptotic representation of Zolotarev polynomials, J. London Math. Soc. 74 (2006), pp. 143-153, https://doi.org/10.1112/s0024610706022885

H.-J. Rack, On polynomials with largest coefficient sums, J. Approx. Theory 56 (1989), pp. 348-359, https://doi.org/10.1016/0021-9045(89)90124-x

H.-J. Rack, The first Zolotarev case in the Erdos-Szego solution to a Markov-type extremal problem of Schur, Stud. Univ. Babes-Bolyai Math. 62 (2017), pp. 151-162, https://doi.org/10.24193/subbmath.2017.2.02

H.-J. Rack, The second Zolotarev case in the Erdos-Szego solution to a Markov-type extremal problem of Schur, J. Numer. Anal. Approx. Theory 46 (2017), pp. 54-77.

H.-J. Rack, Abstract: Explicit algebraic solution to Zolotarev’s First Problem for polynomials of degree n∈ {6, 7, 8}, In: IX Jaen Conference on Approximation Theory (Ubeda, Spain, July 8-13, 2018), https://doi.org/www.ujaen.es/revista/jja/jca/principal.pdf

H.-J. Rack, Abstract: Explicit algebraic solution to Zolotarev’s First Problem for polynomials of degree n∈{6, 7, 8}. In: IV International Conference on Numerical Analysis and Approximation Theory (Cluj-Napoca, Romania, September 6-9, 2018),https://doi.org/ath.ubbcluj.ro/naat2018/abstracts

—hrefhttps://doi.org/10.14658/pubj-drna-2019-1-4 H.-J. Rack, R. Vajda, An explicit univariate and radical parametrization of the sextic proper Zolotarev polynomials in power form, Dolomites Res. Notes Approx. 12 (2019), pp. 43-50.

Th.J. Rivlin, Chebyshev Polynomials, 2nd edition, J. Wiley & Sons, New York (NY), USA, 1990,https://doi.org/10.2307/2153227

Th.J. Rivlin, Optimal ly stable Lagrangian numerical differentiation, SIAM J. Numer. Anal. 12 (1975), pp. 712-725, https://doi.org/10.1137/0712053

K. Schiefermayr, Inverse polynomial images which consists of two Jordan arcs – An algebraic solution, J. Approx. Theory 148 (2007), pp. 148-157, https://doi.org/10.1016/j.jat.2007.03.003

A. Shadrin, Twelve proofs of the Markov inequality. In: Approximation Theory – A volume dedicated to B. Bojanov (D.K. Dimitrov et al. (Eds.)), M. Drinov Acad. Publ. House, Sofia, 2004, pp. 233-298, https://doi.org/www.damtp.cam.ac.uk/user/na/people/Alexei/papers/markov.pdf

A. Shadrin, The Landau-Kolmogorov inequality revisited, Discrete Contin. Dyn.Syst. 34 (2014), pp. 1183-1210, https://doi.org/10.3934/dcds.2014.34.1183

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.

M.L. Sodin, P.M. Yuditskii, Algebraic solution of a problem of E.I. Zolotarev and N.I. Akhiezer on polynomials with smallest deviation from zero, J. Math. Sci. 76 (1995), pp. 2486-2492, https://doi.org/10.1007/bf02364906

V.M. Tikhomirov, II. Approximation Theory. In: Analysis II (R.V. Gamkrelidze (Ed.)), Encyclopaedia of Mathematical Sciences, Vol. 14, Springer, New York (NY), USA, 1990, pp. 93-243 (Russian 1987), https://doi.org/10.1007/978-3-642-61267-1_2

J. Todd, Applications of transformation theory: A legacy from Zolotarev (1847-1878), In: Approximation Theory and Spline Functions, Proceedings NATO Advanced Study Institute (ASIC 136, St. John’s, Canada, 1983, S.P. Singh et al. (Eds.)), 1984, pp. 207-245, https://doi.org/10.1007/978-94-009-6466-2_11

R. Vajda, Abstract: Explicit algebraic solution of the Zolotarev problem via Groebner basis. In: IV International Conference on Numerical Analysis and Approximation Theory (Cluj-Napoca, Romania, September 6-9, 2018),https://doi.org/math.ubbcluj.ro/naat2018/abstracts

E.V. Voronovskaja, The Functional Method and its Applications, Translations of Mathematical Monographs, Vol. 28, AMS, Providence (RI), USA, 1970 (Russian 1963), https://doi.org/10.1090/mmono/028

Wolfram Research, Inc., Mathematica, Version 11.0, Champaign (IL), USA, 2016.

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.

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

www.math.u-szeged.hu/∼vajda/ZFP, https://doi.org/%20www.math.u-szeged.hu/$/sim%20$%7B%7Dvajda/ZFP

Published
2020-01-31
How to Cite
Rack, H. J., & Vajda, R. (2020). Explicit algebraic solution of Zolotarev’s First Problem for low-degree polynomials. J. Numer. Anal. Approx. Theory, 48(2), 175-201. Retrieved from https://ictp.acad.ro/jnaat/journal/article/view/1173
Section
Articles