|
On Shallit's Minimization Problem
S. Yu. Sadov Moscow
Abstract:
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.
Keywords:
Shallit's constant, minimization, hyperbolic point, local linearization, rate of convergence.
Received: 07.05.2019 Revised: 29.05.2021
Citation:
S. Yu. Sadov, “On Shallit's Minimization Problem”, Mat. Zametki, 110:3 (2021), 386–404; Math. Notes, 110:3 (2021), 375–392
Linking options:
https://www.mathnet.ru/eng/mzm12436https://doi.org/10.4213/mzm12436 https://www.mathnet.ru/eng/mzm/v110/i3/p386
|
|