On minimal absorption index for an $n$-dimensional simplex

M. V. Nevskii ; A. Yu. Ukhalov

Modelirovanie i analiz informacionnyh sistem, Tome 25 (2018) no. 1, pp. 140-150.

Résumé

Let $n\in{\mathbb N}$ and let $Q_n$ be the unit cube $[0,1]^n$. For a nondegenerate simplex $S\subset{\mathbb R}^n$, by $\sigma S$ denote the homothetic copy of $S$ with center of homothety in the center of gravity of $S$ and ratio of homothety $\sigma.$ Put $\xi(S)=\min \{\sigma\geq 1: Q_n\subset \sigma S\}.$ We call $\xi(S)$ an absorption index of simplex $S$. In the present paper, we give new estimates for the minimal absorption index of the simplex contained in $Q_n$, i. e., for the number $\xi_n=\min \{ \xi(S): \, S\subset Q_n \}.$ In particular, this value and its analogues have applications in estimates for the norms of interpolation projectors. Previously the first author proved some general estimates of $\xi_n$. Always $n\leq\xi_n n+1$. If there exists an Hadamard matrix of order $n+1$, then $\xi_n=n$. The best known general upper estimate has the form $\xi_n\leq \frac{n^2-3}{n-1}$ $(n>2)$. There exists a constant $c>0$ not depending on $n$ such that, for any simplex $S\subset Q_n$ of maximum volume, inequalities $c\xi(S)\leq \xi_n\leq \xi(S)$ take place. It motivates the use of maximum volume simplices in upper estimates of $\xi_n$. The set of vertices of such a simplex can be consructed with application of maximum $0/1$-determinant of order $n$ or maximum $-1/1$-determinant of order $n+1$. In the paper, we compute absorption indices of maximum volume simplices in $Q_n$ constructed from known maximum $-1/1$-determinants via a special procedure. For some $n$, this approach makes it possible to lower theoretical upper bounds of $\xi_n$. Also we give best known upper estimates of $\xi_n$ for $n\leq 118$.

Détail

Keywords: $n$-dimensional simplex, $n$-dimensional cube, homothety, numerical methods.
Mots-clés : absorption index, interpolation

Bibliographie

[1] Klimov V. S., Ukhalov A. Yu., Reshenie zadach matematicheskogo analiza s ispolzovaniem sistem kompyuternoi matematiki, P. G. Demidov Yaroslavl State University, Yaroslavl, 2014, 96 pp. (in Russian)

[2] Nevskij M. V., Khlestkova I. V., “K voprosu o minimalnoi lineinoi interpolyacii”, Sovremennye problemy matematiki i informatiki, 9, P. G. Demidov Yaroslavl State University, Yaroslavl, 2008, 31–37 (in Russian)

[3] Nevskij M. V., “On a certain relation for the minimal norm of an interpolational projection”, Modeling and Analysis of Information Systems, 16:1 (2009), 24–43 (in Russian)

[4] Nevskii M. V., “On a property of $n$-dimensional simplices”, Math. Notes, 87:4 (2010), 543–555 | DOI | DOI | MR

[5] Nevskii M. V., Geometricheskie ocenki v polinomialnoy interpolyacii, P. G. Demidov Yaroslavl State University, Yaroslavl, 2012 (in Russian)

[6] Nevskii M. V., Ukhalov A. Yu., “On numerical characteristics of a simplex and their estimates”, Modeling and Analysis of Information Systems, 23:5 (2016), 603–619 (in Russian) | MR

[7] Nevskii M. V., Ukhalov A. Yu., “New estimates of numerical values related to a simplex”, Modeling and Analysis of Information Systems, 24:1 (2017), 94–110 (in Russian) | MR

[8] Hall M. (Jr), Combinatorial theory, Blaisdall publishing company, Waltham (Massachusets)–Toronto–London, 1967 (in English) | MR | MR

[9] Hudelson M., Klee V., Larman D., “Largest $j$-simplices in $d$-cubes: some relatives of the Hadamard maximum determinant problem”, Linear Algebra Appl., 241–243 (1996), 519–598 | DOI | MR

[10] Lassak M., “Parallelotopes of maximum volume in a simplex”, Discrete Comput. Geom., 21:3 (1999), 449–462 | DOI | MR

[11] Mangano S., Mathematica cookbook, O'Reilly Media Inc., Cambridge, 2010

[12] Nevskii M., “Properties of axial diameters of a simplex”, Discrete Comput. Geom., 46:2 (2011), 301–312 | DOI | MR

[13] Scott P. R., “Lattices and convex sets in space”, Quart. J. Math. Oxford (2), 36 (1985), 359–362 | DOI | MR

[14] Scott P. R., “Properties of axial diameters”, Bull. Austral. Math. Soc., 39:3 (1989), 329–333 | DOI | MR