Geodesic
On Shallit's Minimization Problem
Matematičeskie zametki, Tome 110 (2021) no. 3, pp. 386-404.

Voir la notice de l'article provenant de la source Math-Net.Ru

In Shallit's problem (SIAM Review, 1994), it was proposed to justify a two-term asymptotics of the minimum of a rational function of $n$ variables defined as the sum of a special form whose number of terms is of order $n^2$ as $n\to\infty$. Of particular interest is the second term of this asymptotics (“Shallit's constant”). The solution published in SIAM Review presented an iteration algorithm for calculating this constant, which contained some auxiliary sequences with certain properties of monotonicity. However, a rigorous justification of the properties, necessary to assert the convergence of the iteration process, was replaced by a reference to numerical data. In the present paper, the gaps in the proof are filled on the basis of an analysis of the trajectories of a two-dimensional dynamical system with discrete time corresponding to the minimum points of $n$-sums. In addition, a sharp exponential estimate of the remainder in Shallit's asymptotic formula is obtained.
Mots-clés : Shallit's constant
Keywords: minimization, hyperbolic point, local linearization, rate of convergence. 
@article{MZM_2021_110_3_a5,
     author = {S. Yu. Sadov},
     title = {On {Shallit's} {Minimization} {Problem}},
     journal = {Matemati\v{c}eskie zametki},
     pages = {386--404},
     publisher = {mathdoc},
     volume = {110},
     number = {3},
     year = {2021},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MZM_2021_110_3_a5/}
}
TY  - JOUR
AU  - S. Yu. Sadov
TI  - On Shallit's Minimization Problem
JO  - Matematičeskie zametki
PY  - 2021
SP  - 386
EP  - 404
VL  - 110
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/MZM_2021_110_3_a5/
LA  - ru
ID  - MZM_2021_110_3_a5
ER  - 
%0 Journal Article
%A S. Yu. Sadov
%T On Shallit's Minimization Problem
%J Matematičeskie zametki
%D 2021
%P 386-404
%V 110
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/MZM_2021_110_3_a5/
%G ru
%F MZM_2021_110_3_a5
S. Yu. Sadov. On Shallit's Minimization Problem. Matematičeskie zametki, Tome 110 (2021) no. 3, pp. 386-404. http://geodesic.mathdoc.fr/item/MZM_2021_110_3_a5/

[1] J. Shallit, “A minimization problem”, SIAM Rev., 36:3 (1994), 490–491 | DOI

[2] S. Finch, Mathematical Constants, Princeton Univ. Press, Princeton, 2003 | MR

[3] The On-Line Encyclopedia of Integer Sequences A086276, https://oeis.org/A086276

[4] R. L. Brown, K. R. Davidson, J. Shallit, “Problem 10433”, Amer. Math. Monthly, 102:2 (1995), 170 | MR

[5] S. Sadov, “Lower bound for cyclic sums of Diananda type”, Arch. Math. (Basel), 106:2 (2016), 135–144, doi 10.1007/s00013-015-0853-3 | DOI | MR

[6] S. Sadov, Minimization of the Sum Under Product Constraints, 2020, arXiv: 2012.15517

[7] C. C. Grosjean, H. E. De Meyer, “Solution of Problem 94-15: A minimization problem”, SIAM Rev., 37:3 (1995), 451–458 | DOI

[8] A. B. Katok, B. Khasselblat, Vvedenie v sovremennuyu teoriyu dinamicheskikh sistem, Faktorial, M., 1999 | MR | Zbl

[9] P. Hartman, “On local homeomorphisms of Euclidean spaces”, Bol. Soc. Mat. Mexicana (2), 5 (1960), 220–241 | MR