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

Authors

  • Heinz Joachim Rack Dr. Rack Consulting GmbH, Germany
  • Robert Vajda Bolyai Institute, University of Szeged, Aradi Vertanuk tere 1, 6720 Szeged, Hungary

DOI:

https://doi.org/10.33993/jnaat482-1173

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 views: 502

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

Downloads

Download data is not yet available.

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 DOI: 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 DOI: 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 DOI: 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.)), Birkhauser, Basel, ISNM 121 (1996), pp. 181-190. https://doi.org/10.1007/978-3-0348-9208-7_19 DOI: 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 DOI: 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 DOI: 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 DOI: 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 DOI: 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 DOI: 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 DOI: https://doi.org/10.1515/rnam.1994.9.3.231

L.G. Lozner, Piecewise linear estimates of coefficients of Zolotarev polynomials, Funkts. Anal. 34 (199), 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, http://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, http:// 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 DOI: https://doi.org/10.1142/1284

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 DOI: 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 DOI: 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 and resp. https://doi.org/10.1023/A:1006659402649 DOI: https://doi.org/10.1023/A:1006607401740

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 DOI: 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 DOI: 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 DOI: 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 DOI: 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, https://ictp.acad.ro/jnaat/journal/article/view/1100

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), http://math.ubbcluj.ro/naat2018/abstracts

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

Th.J. Rivlin, Optimal ly stable Lagrangian numerical differentiation, SIAM J. Numer. Anal. 12 (1975), pp. 712-725, https://doi.org/10.1137/0712053 DOI: 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 DOI: 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:// 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 DOI: 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 DOI: 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 DOI: 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 DOI: 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://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 DOI: 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://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

Downloads

Published

2019-12-31

How to Cite

Rack, H. J., & Vajda, R. (2019). Explicit algebraic solution of Zolotarev’s First Problem for low-degree polynomials. J. Numer. Anal. Approx. Theory, 48(2), 175–201. https://doi.org/10.33993/jnaat482-1173

Issue

Section

Articles

Funding data