| Математический сборник |
|
|
|
|
|
Перечисление целочисленных триангуляций: уравнения Фредгольма в комбинаторике С. Ю. Оревков Математический институт им. В. А. Стеклова Российской академии наук, г. Москва
Англоязычная версия:
Sbornik: Mathematics, 2022, Volume 213, Issue 11, Pages DOI: https://doi.org/10.4213/sm9727e 
Реферативные базы данных:
     § 1. ВведениеЦелочисленная триангуляция (lattice triangulation) многоугольника в $\mathbb R^2$ – это триангуляция с вершинами в $\mathbb Z^2$. Как показано в [3], целочисленные триангуляции играют важную роль в алгебраической геометрии (см. также [9]). Целочисленная триангуляция называется примитивной (или унимодулярной), если каждый ее треугольник примитивен, т.е. имеет минимально возможную площадь $1/2$ (является сдвигом треугольника $[(0,0),(x_1,y_1),(x_2,y_2)]$, где $x_1y_2- x_2y_1=1$). Обозначим число примитивных целочисленных триангуляций прямоугольника $m\times n$ через $f(m,n)$. Пусть
$$
\begin{equation*}
\begin{gathered} \, c(m,n)=\frac{\log_2f(m,n)}{mn}, \qquad c_m=\sup_n c(m,n)=\lim_{n\to\infty} c(m,n), \\ c=\sup_m c_m=\lim_{m\to\infty} c_m =\sup_n c(n,n)=\lim_{n\to\infty} c(n,n). \end{gathered}
\end{equation*}
\notag
$$
Существование пределов доказано в [4; предложение 3.6]. Число $c(m,n)$ названо в [4] емкостью прямоугольника $m\times n$. В [8] получена верхняя оценка $c<6$ (которая автоматически улучшается до $c<\log_2 27= 4.755$: достаточно просто не различать случаи $v_j=1$ и $v_j=2$ в обозначениях из [8]). В дальнейшем намного лучшую оценку $c<3$, а также $c_m<3-1/m$ доказал Анклин (см. [1]). Еще лучшая оценка $c<4\log_2\frac{1+\sqrt5}2=\log_2 6.854=2.777$ получена в [7] и анонсирована в [12] (я не видел рукописи [7], но профессор Велцль любезно прислал мне слайды своего доклада [13], в которых ясно изложено доказательство этой оценки). Легко видеть, что что дает нижнюю оценку $c\geqslant 2$. В [4] также вычислено, что $c\geqslant c_4\geqslant c(4,32)=2.055702$. В [4; п. 2.1] написано: “Для $f(2,n)$ у нас нет явной формулы и мы не умеем точно вычислять асимптотику”. У нас по-прежнему нет явной формулы для $f(2,n)$, но мы приводим главный член асимптотики.Точное значение $c_3$ в некотором смысле будет дано в предложении 4.5, где мы выразим $c_3$ в терминах решения уравнения Фредгольма на производящие функции. В частности, предложение 4.5 дает алгоритм, позволяющий вычислить $c_3$ с точностью до $n$ знаков за время, полиномиальное по $n$. Код на языке Mathematica, реализующий основной шаг этого алгоритма, будет приведен в конце § 4. Теорема 1.2. Предел с точностью до $360$ знаков равен Мы вычислили значение $c_3$ с такой высокой точностью в надежде найти для него алгебраическое уравнение или связать его с какими-нибудь известными константами. Этого сделать пока не удалось. В п. 2.2 мы приведем результаты вычисления точных значений чисел $f(m,n)$ для некоторых $m$ и $n$. В частности, они дают оценку $c\geqslant c(5,115)= 2.10449551\dots$ . В § 6 будет приведена асимптотическая верхняя оценка числа всех (не обязательно примитивных) целочисленных триангуляций. Скорее всего она далека от оптимальной. Оставшаяся часть статьи (кроме п. 2.2 и § 6) посвящена доказательству теорем 1.1 и 1.2. А именно, в п. 2.1 приведены рекуррентные формулы для примитивных триангуляций многоугольников, лежащих в полосе фиксированной ширины. Они похожи на формулы в [4], но, по нашему мнению, проще и эффективнее. Теоремы 1.1 и 1.2 доказываются в § 3 и § 4 соответственно с использованием соотношений на производящие функции, отвечающих рекурсии из п. 2.1. Как было сказано выше, $c_3$ выражается через решение интегрального уравнения Фредгольма на интегралы Коши от производящих функций. В § 5 оценивается ошибка приближения для самого простого численного метода решения уравнения Фредгольма с аналитическим ядром. БлагодарностьЯ благодарю рецензента за исправления и ценные замечания. § 2. Рекуррентные соотношения для полосы фиксированной ширины2.1. Рекуррентные соотношенияДля многоугольника $P\subset\mathbb R^2$ назовем верхней частью его границы множество $\{(x,y)\in P\mid y'>y\Rightarrow (x,y')\not\in P\}$, а вертикальной стороной назовем сторону, лежащую на некоторой прямой вида $\{x=x_0\}$. Пусть $\mathcal T$ – триангуляция многоугольника $P$ в $\mathbb R^2$. Будем говорить, что $Q$ есть элемент замощения (tile) для $\mathcal T$ в следующих трех случаях:
Назовем многоугольник $y$-выпуклым, если его пересечение с любой прямой $x=\mathrm{const}$ либо пусто, либо является точкой или отрезком. Лемма 2.1. Пусть $\mathcal T$ – триангуляция $y$-выпуклого многоугольника $P$ в $\mathbb R^2$. Тогда существует $Q$ – элемент замощения для $\mathcal T$ такой, что вся верхняя часть его границы лежит на границе многоугольника $P$. Доказательство. Пусть $\Gamma_P$ – верхняя часть границы $P$. Пусть $Q_1,\dots, Q_n$ – все элементы замощения для $\mathcal T$, у которых хотя бы одна сторона лежит на $\Gamma_P$. Пусть $\Gamma_i$ – объединение сторон элемента $Q_i$, лежащих на $\Gamma_P$. Ясно, что $\Gamma_i$ – либо сторона $Q_i$, либо объединение двух его смежных сторон. Ясно также, что проекции множеств $\Gamma_i$ на ось $x$ имеют попарно не пересекающиеся внутренности, следовательно, мы можем предполагать, что $\Gamma_1,\dots,\Gamma_n$ занумерованы слева направо.
Скажем, что элемент $Q_i$ заслонен слева (соответственно заслонен справа), если верхняя часть его границы содержит отрезок $I$ такой, что $I\not\subset\Gamma_P$ и $I$ лежит слева (соответственно справа) от $\Gamma_i$ (рис. 1). Ясно, что ни один из элементов $Q_1,\dots,Q_n$ не может быть заслонен и справа, и слева одновременно. Поэтому без ограничения общности можно считать, что хотя бы один из элементов замощения не заслонен справа. Пусть $i_0$ – минимальное число такое, что $Q_{i_0}$ не заслонен справа. Тогда $Q_{i_0}$ – искомый элемент, у которого верхняя часть границы лежит в $\Gamma_P$. В самом деле, по определению он не заслонен справа. Он также не может быть заслонен слева, поскольку иначе $Q_{i_0-1}$ не был бы заслонен справа, что противоречило бы минимальности числа $i_0$. Лемма доказана. Фиксируем теперь целое число $m>0$ и будем рассматривать примитивные целочисленные триангуляции многоугольников, расположенных в вертикальной полосе $\{0\leqslant x\leqslant m\}$ и ограниченных графиками непрерывных кусочно линейных функций. По аналогии с терминологией, введенной в [4; п. 2.2], будем говорить, что функция $\varphi\colon [0,m]\to\mathbb R$ допустима, если она непрерывна, кусочно линейна и ее график является объединением отрезков с концами в $\mathbb Z^2$. Фиксируем допустимую функцию $\varphi_0$. Функцию $\varphi\colon [0,m]\to\mathbb R$ назовем $\varphi_0$-допустимой, если она допустима и $\varphi(x)\geqslant \varphi_0(x)$ при всех $x\in[0,m]$. Назовем $\varphi_0$-допустимой фигурой ($\varphi_0$-admissible shape) многоугольник $S$ вида $\{(x,y)\in\mathbb R^2\mid 0\leqslant x\leqslant m,\, \varphi_0(x)\leqslant y\leqslant\varphi(x)\}$ для некоторой $\varphi_0$-допустимой функции $\varphi$. По аналогии с вышеприведенным определением элемента замощения для триангуляции будем говорить, что $Q$ есть примитивный целочисленный элемент замощения, в следующих трех случаях:
Примитивный целочисленный элемент замощения $Q$ назовем $P$-максимальным для многоугольника $P$, если $Q\subset P$ и верхняя часть границы $Q$ лежит в верхней части границы $P$. Скажем, что $S'$ является $\varphi_0$-допустимой подфигурой $\varphi_0$-допустимой фигуры $S$, если $S'$ – замыкание множества $S\,{\setminus}\,(Q_1\,{\cup}\,{\cdots}\,{\cup}\, Q_n)$, где $Q_1,\dots,Q_n$ суть $S$-максимальные примитивные целочисленные элементы замощения с попарно не пересекающимися внутренностями. Следуя [4], положим в этом случае $\#(S',S)=n$. Заметим, что отношение “быть допустимой подфигурой” нетранзитивно. Обозначим число примитивных целочисленных триангуляций многоугольника $P$ через $f^*(P)$. Когда $P$ лежит в полосе $\{0\leqslant x\leqslant m\}$, обозначим также через $f(P)$ число тех примитивных целочисленных триангуляций многоугольника $P$, у которых нет внутреннего ребра, проекция которого на ось $x$ совпадает с отрезком $[0,m]$ (мы выбрали более простое обозначение для более сложного понятия, так как числа $f(P)$ будут использоваться чаще, чем числа $f^*(P)$). Следующая лемма – это формула включений-исключений для данной ситуации. Доказательство то же, что и для леммы 2.2 из [4]. Лемма 2.2. Для любой $\varphi_0$-допустимой фигуры $S$ имеют место равенства где левая сумма берется по всем собственным $\varphi_0$-допустимым подфигурам фигуры $S$, а правая сумма – по тем собственным $\varphi_0$-допустимым подфигурам фигуры $S$, верхняя часть границы которых содержит точку из $\mathbb Z^2\cap\{0< x< m\}$. Пример 2.3. Пусть $m=2$ и $\varphi_0=0$. Для целых неотрицательных $a,b,c$ через $S_{a,b,c}$ обозначим $\varphi_0$-допустимую фигуру, ограниченную сверху отрезками $[(0,a),(1,b)]$ и $[(1,b),(2,c)]$. Пусть $f_{a,b,c}\,{=}\,f(S_{a,b,c})$. Положим также $f_{a,b,c}\,{=}\,0$ при $\min(a,b,c)<0$. Тогда (рис. 2) рекуррентная формула из леммы 2.2 принимает вид Пусть $F(x,y,z)=\sum_{a,b,c}f_{a,b,c}x^ay^bz^c$ – производящая функция. Тогда, суммируя рекуррентное соотношение по всем тройкам $(a,b,c)\ne(0,0,0)$, получим откуда следует $F(x,y,z)=1/(1-x-y-z+xz)$. Пример 2.4. Пусть $\varphi_0$ и $S_{a,b,c}$ те же, что и в примере 2.3. Для неотрицательных $a$, $c$ разной четности через $S'_{a,c}$ обозначим $\varphi_0$-допустимую фигуру, ограниченную сверху отрезком $[(0,a),(2,c)]$. Положим $f^*_{a,b,c}=f^*(S_{a,b,c})$ и $g^*_{a,c}=f^*(S'_{a,c})$. Положим также $f^*_{a,b,c}=0$ при $\min(a,b,c)<0$ и $g^*_{a,c}=0$ при $\min(a,c)<0$ или $a\equiv c \mod2$. Тогда при $(a,b,c)\ne(0,0,0)$ рекуррентное соотношение из леммы 2.2, примененное к $S_{a,b,c}$, имеет вид что дает соотношение
$$
\begin{equation*}
F^*(x,y,z)(1-x-y-z+xz)=1+y^{1/2} G^*(xy^{1/2},y^{1/2}z).
\end{equation*}
\notag
$$
Применим теперь рекуррентное соотношение к $S'_{a,c}$. Единственной допустимой подфигурой фигуры $S'_{a,c}$ является $S_{a,(a+c-1)/2,c}$, следовательно, соотношение для $S'_{a,c}$ имеет вид $g^*_{a,c}=f^*_{a,(a+c-1)/2,c}$. В терминах производящих функций это означает
$$
\begin{equation*}
\begin{aligned} \, &G^*(x,z) = \sum_{a,c} f^*_{a,(a+c-1)/2,c}x^a z^c =\operatorname{coef}_{u^0}\biggl[\sum_{a,b,c} f^*_{a,b,c}x^a u^{2b-a-c+1} z^c\biggr] \\ &\qquad=\operatorname{coef}_{u^0}\biggl[u\sum_{a,b,c} f^*_{a,b,c}(xu^{-1})^a (u^2)^b (zu^{-1})^c\biggr] =\operatorname{coef}_{u^0}\bigl(u F^*(xu^{-1},u^2,zu^{-1})\bigr). \end{aligned}
\end{equation*}
\notag
$$
2.2. Некоторые точные значения $f(m,n)$Рекуррентные соотношения леммы 2.2 дают алгоритм вычисления $f(m,n)$ для малых $m$ и $n$, аналогичный алгоритму, описанному в [4; п. 2.2]. Мы произвели вычисления по этому алгоритму, и из табл. 1 можно видеть, что нам удалось продвинуться намного дальше по сравнению с [4]. Этому есть три причины, влияние которых более или менее сопоставимо. Таблица 1.
Первая причина (очевидная) в том, что компьютеры стали более мощными. Вторая причина в том, что мы использовали другое определение допустимой фигуры, что позволило в $3^{m-1}$ раз сократить используемую память, а это довольно существенно при $m=9$ (как справедливо отмечено в [4], для алгоритмов такого рода “узкое место (bottleneck) в вычислениях – это всегда память”). Третья причина в том, что вместо длинной арифметики мы использовали вычисления по модулю различных простых чисел с последующим восстановлением результата при помощи китайской теоремы об остатках. Этот прием позволил “конвертировать” память во время, нехватка которого была не столь критична. Мы вычислили $f(3,n)$ до $n=600$ и $f(4,n)$ до $n=200$. Точное значение $f(3,600)$ имеет 1127 цифр и дает $c_{3,600}=2.07966\dots$ . Сравнивая эту величину с пределом $c_3=2.08385$, мы видим, что сходимость очень медленная. Для $m=4$ последнее найденное точное значение равно
$$
\begin{equation*}
\begin{aligned} \, f(4,200)=\, &262199334303965073140522141167072596609151907003573304927487 \\ &419128543906730659218480439253346584137204205604500628092962 \\ &697997426095545403404830271634194339979807927812812142668569 \\ &097560203843935394728621308903256950859658838687531965864231 \\ &570521446370439565640979852878302993978768696718322811686043 \\ &307749541067654061321020767838164602474781629699981105797912 \\ &385346265396601164596410043968216134349971638142523003353406 \\ &530183843913302635663917084864069175263416748948835535483336 \\ &4717309018125451550646500; \\ c(4,200) &=2.09455\dotsc\,. \end{aligned}
\end{equation*}
\notag
$$
В табл. 2–6 представлены некоторые другие результаты вычислений в том же виде, что и в [4]. Все вычисленные точные значения доступны на веб-странице https://www.math.univ-toulouse.fr/~orevkov/tr.html. Таблица 2.
Таблица 3.
Таблица 4.
Таблица 5.
Таблица 6.
2.3. Гипотеза выпуклости для чисел $f(m,n)$Следующая гипотеза подтверждается всеми вычисленными точными значениями чисел $f(m,n)$ (по соглашению $f(m,0)=1$). Предложение 2.6. Если верна гипотеза 2.5, то $c_m\geqslant (n+1)c(m,n+1)-nc(m,n)$ при всех $m,n\geqslant 1$. В частности, из гипотезы 2.5 следовало бы, что Доказательство. Положим $d(m,n)=\log_2 f(m,n+1)-\log_2 f(m,n)$. Тогда из гипотезы 2.5 следует откуда Деля это неравенство на $km$ и переходя к пределу при $k\to\infty$, получаем
Предложение доказано. § 3. Точное значение $c_2$ (доказательство теоремы 1.1)При $a,c\geqslant 0$, $a\equiv c\mod 2$, обозначим через $g^*_{a,c}$ число примитивных целочисленных триангуляций трапеции $T(a,c)$ с вершинами $(0,0)$, $(a,0)$, $(1,2)$, $(1+c,2)$ (если $a=0$ или $c=0$, то $T(a,c)$ вырождается в треугольник). При $a\not\equiv c\mod 2$ положим $g^*_{a,c}=0$. Положим также $g^*_{0,0}=1$. Обозначим через $G^*(x,z)$ производящую функцию для $g^*_{a,c}$:
$$
\begin{equation*}
\begin{aligned} \, G^*(x,z) &= \sum_{a,c\geqslant0} g^*_{a,c}x^a z^c \\ &= 1+(x^2+xz+z^2)+(6x^4+10x^3 z+12 x^2 z^2+10 x z^3+6z^4)+\dotsb \end{aligned}
\end{equation*}
\notag
$$
(здесь $g^*_{a,c}$ и $G^*$ определяются иначе, чем в примере 2.4). Обозначим через $g^*_n$ коэффициент при $x^{2n}$ в степенном ряде $G^*(x,x)=\sum_{n\geqslant0} g^*_nx^{2n}$, т.е.
$$
\begin{equation*}
g^*_n=g^*_{0,2n}+g^*_{1,2n-1}+g^*_{2,2n-2}+\dots+g^*_{2n,0}.
\end{equation*}
\notag
$$
Тогда теорема 1.1 непосредственно вытекает из лемм 3.1 и 3.2. Доказательство. Прямоугольник $2\times(n-1)$ можно поместить в $T(n,n)$, значит, $f(2,n-1) < g^*_n$. С другой стороны, объединение $T(a,c)$ со своим образом при центральной симметрии относительно $(\frac12(a+c+1),1)$ является трапецией $T(a+c,a+c)$, причем ее можно поместить в прямоугольник $2\times(a+c+1)$, следовательно, $(g^*_{a,c})^2 < f(2,a+c+1)$. Поэтому откуда что дает требуемый результат, так как $\frac1n\log(2n)\to 0$.
Лемма доказана. Лемма 3.2. Имеет место где $\alpha$ такое, как в теореме 1.1. Доказательство. При $a,c\geqslant 0$, $a\equiv c\mod 2$, пусть $g_{a,c}$ – число тех примитивных целочисленных триангуляций трапеции $T(a,c)$, у которых нет внутренних ребер вида $[(k,0),(l,2)]$, другими словами, примитивных целочисленных триангуляций, согласованных с изображенным на рис. 3 (слева) разбиением трапеции $T(a,c)$ на два треугольника и две трапеции. Если $a+c$ нечетно, положим $g_{a,c}=0$. По соглашению $g_{0,0}=0$. Пусть $G(x,z)=\sum_{a,c\geqslant 0} g_{a,c}x^a z^c$ – производящая функция.
Ребра вида $[(k,0),(l,2)]$ делят $T(a,c)$ на меньшие трапеции. Их можно преобразовать в трапеции $T(a_i,c_i)$, для которых $\sum a_i=a$ и $\sum c_i=c$, однозначно определенными автоморфизмами целочисленной решетки вида $(x,y)\mapsto(x+p_iy+q_i,y)$, где $p_i,q_i\in\mathbb Z$ (см. рис. 3). Поэтому
$$
\begin{equation*}
g^*_{a,c}= \sum_{\substack{a_1+\dots+a_k=a \\ c_1+\dots+c_k=c}}\, \prod_{j=1}^k g_{a_j,c_j},
\end{equation*}
\notag
$$
значит, Легко видеть (ср. с (1)), что числа примитивных целочисленных триангуляций узких (т.е. ширины 1) трапеций на рис. 3 – это биномиальные коэффициенты, следовательно,
$$
\begin{equation*}
G(x,z)=(x^2+xz+z^2)+(5x^4+8x^3z+9x^2z^2+8xz^3+5z^4)+\dotsb.
\end{equation*}
\notag
$$
Легко также проверить, что $g_{a,c}=f_{a,(a+c)/2-1,c}$, где $f_{a,b,c}=f(S_{a,b,c})$ – числа, обсуждавшиеся в примере 2.3. Поэтому (ср. с примером 2.4)
$$
\begin{equation*}
\begin{aligned} \, G(x,z) &=\sum_{a,c} f_{a,(a+c)/2-1,c}x^az^c =\operatorname{coef}_{u^0} \biggl[\sum_{a,b,c}f_{a,b,c}x^a u^{2b-a-c+2}z^c\biggr] \\ &=\operatorname{coef}_{u^0}\biggl[u^2\sum_{a,b,c}f_{a,b,c}(xu^{-1})^a u^{2b}(zu^{-1})^c\biggr] =\operatorname{coef}_{u^{-1}}[u F(xu^{-1},u^2,zu^{-1})]. \end{aligned}
\end{equation*}
\notag
$$
Так как функция $1/(1-x-y-z+xz)=1/\bigl((1-x)(1-z)-y\bigr)$ аналитична в области $\max\bigl(|x|,|2y|,|z|\bigr)<1/2$, ее степенной ряд $\sum f_{a,b,c}x^ay^bz^c$ (см. пример 2.3) сходится к ней в этой области. Поэтому при $0<\varepsilon\ll r<1/2$ ряд Лорана функции $F(x/u,u^2,z/u)$ сходится в области $\max(|x|,|z|)<\varepsilon$, $r-\varepsilon<|u|<r+\varepsilon$. Следовательно, при достаточно малых $x$ имеем
$$
\begin{equation*}
\begin{gathered} \, G(x,x)=\operatorname{coef}_{u^{-1}}\biggl[F\biggl(\frac xu,u^2,\frac xu\biggr)\biggr] =\frac{1}{2\pi i}\oint_{|u|=r}\frac{u\,du}{(1-x/u)^2-u^2}, \\ \begin{split} \frac{u}{(1-x/u)^2-u^2} &= -\frac{u}{2(u^2+u-x)}-\frac{u}{2(u^2-u+x)} \\ &=\sum_{j=1}^2\frac 1{2(u_j^+-u_j^-)}\biggl(\frac{u_j^+}{u-u_j^+}+\frac{u_j^-}{u-u_j^-}\biggr), \end{split} \end{gathered}
\end{equation*}
\notag
$$
где при достаточно малом $|x|$
$$
\begin{equation*}
u_1^\pm=-\frac12(1\pm\sqrt{1+4x}), \quad u_2^\pm=\frac12(1\pm\sqrt{1-4x}), \qquad |u_j^+|>r, \quad |u_j^-|<r.
\end{equation*}
\notag
$$
Таким образом,
$$
\begin{equation*}
G(x,x)=\sum_{j=1}^2\operatorname{Res}_{u=u_j^-}(\dots) =\sum_{j=1}^2\frac{u_j^-}{2(u_j^+-u_j^-)} =\frac1{4\sqrt{1-4x}}+\frac1{4\sqrt{1+4x}}-\frac12.
\end{equation*}
\notag
$$
График функции $y=G(x,x)$ лежит на алгебраической кривой
$$
\begin{equation*}
(2y+1)^2(16x^2-1)\bigl(4x^2+(y^2+y)(16x^2-1)\bigr)+x^2=0.
\end{equation*}
\notag
$$
В силу (2) полюсы функции $G^*(x,x)$ – это $x$-координаты пересечения этой кривой с прямой $y=1$, т.е. корни многочлена $5184x^4-611 x^2+18$, меньший из которых равен $\pm\sqrt{1/\alpha}$, а ветвление эта функция имеет в точках $\pm1/4$. Следовательно, радиус сходимости ряда $G^*(x,x)=\sum g^*_n x^{2n}$ равен $\sqrt{1/\alpha}$, откуда получаем Лемма 3.2 доказана. § 4. Вычисление $c_3$ (доказательство теоремы 1.2)4.1. ПодготовкаДля $a,d\geqslant0$ таких, что $a\not\equiv d+1\mod3$, обозначим через $h^*_{a,d}$ число примитивных целочисленных триангуляций трапеции $T_3(a,d)$ с вершинами $(0,0),(1,3),(1+d,3),(a,3)$. Положим $h^*_{0,0}=1$ и $h^*_{a,d}=0$ при $a\equiv d+1\mod 3$ и рассмотрим производящую функцию
$$
\begin{equation*}
H^*(x)=\sum_n h^*_n x^n=\sum_{a,d\geqslant 0}h^*_{a,d}x^{a+d} =1+x+3x^2+19x^3+125 x^4 +\dotsb.
\end{equation*}
\notag
$$
Как и в начале доказательства леммы 3.2, определим $h_{a,d}$ как число примитивных триангуляций трапеции $T_3(a,d)$, не имеющих ребер вида $[(k,0),(l,3)]$, и рассмотрим производящую функцию
$$
\begin{equation*}
H(x)=\sum_n h_n x^n=\sum_{a,d\geqslant 0}h_{a,d} x^{a+d}=x+2x^2+14 x^3+86 x^4+712 x^5 +\dotsb.
\end{equation*}
\notag
$$
Эти функции удовлетворяют соотношению, аналогичному специализации соотношения (2) для $x=z$: Действительно, ребра вида $[(k,0),(l,3)]$ разбивают $T_3(a,d)$ на меньшие трапеции. Каждая из них отображается на стандартную единственным автоморфизмом решетки вида $(x,y)\mapsto(x+py+q,y)$ или $(x,y)\mapsto(x+py+q,3-y)$, где $p,q\in\mathbb Z$ (в отличие от § 2, здесь верхнее и нижнее основания трапеции могут меняться местами, из-за чего нет аналога соотношения (2) для производящих функций от двух переменных). На рис. 4 проиллюстрировано соотношение
$$
\begin{equation*}
h^*_3=h^*_{03}+h^*_{12}+h^*_{30} =h_{01}^3+2h_{01}(h_{11}+h_{20})+(h_{03}+h_{12}+h_{30}) =h_1^3+2 h_1 h_2+h_3.
\end{equation*}
\notag
$$
Как и в лемме 3.1, имеем
$$
\begin{equation*}
\lim_n f(3,n)^{1/n}=\lim_n(h^*_{2n})^{1/n}=\frac{1}{\beta^{2}},
\end{equation*}
\notag
$$
где $\beta$ – первый вещественный корень уравнения $H(x)=1$, следовательно, 4.2. Рекуррентные соотношенияВ обозначениях из § 2 положим $m= 3$, $\varphi_0(x)=\frac13x-1$ и
$$
\begin{equation*}
\begin{gathered} \, F(x,y,z,w)=\sum_{a,b,c,d} f_{a,b,c,d}x^ay^bz^cw^d, \\ G_1(x,z,w)=\sum_{a,c,d} g^{(1)}_{a,c,d}x^a z^c w^d, \qquad G_2(x,y,w)=\sum_{a,b,d} g^{(2)}_{a,b,d}x^a y^b w^d, \\ H_k(x,w)=\sum_{a,d}h^{(k)}_{a,d}x^a w^d, \qquad k=1,2, \end{gathered}
\end{equation*}
\notag
$$
где все коэффициенты имеют вид $f(S)$ (см. § 2) для $\varphi_0$-допустимых фигур на рис. 5, причем если буквы $a$, $b$, $c$ и $d$ присутствуют в индексах, то $(0,a)$, $(1,b)$, $(2,c)$ и $(3,d)$ – координаты целых точек на верхней части границы фигуры $S$. Нижние вершины $S$ – это точки $(0,-1)$ и $(3,0)$. Если не выполнены сравнения, указанные на рис. 5, то соответствующие числа равны нулю. Если $\min(a+1,b,c,d)<0$, то они тоже равны нулю (этот случай не отвечает никакой $\varphi_0$-допустимой фигуре). По соглашению $h_{-1,0}^{(2)}=0$ (случай вырождения фигуры $S$ в отрезок). В терминах производящих функций рекуррентные соотношения из леммы 2.2 принимают вид (ср. с примерами 2.3 и 2.4)
$$
\begin{equation*}
\begin{gathered} \, \begin{split} & F(x,y,z,w)(1-x-y-z-w+xz+yw+xw) \\ &\qquad =y^{1/2}(1-w)G_1(xy^{1/2},y^{1/2}z,w)+z^{1/2}(1-x)G_2(x,yz^{1/2},z^{1/2}w), \end{split} \\ \begin{split} G_1(x,z,w)(1-w) &=\operatorname{coef}_{u^{-1}}\biggl[F\biggl(\frac xu,u^2,\frac zu,w\biggr)(1-w)\biggr]+x^{-1}, \\ G_2(x,y,w)(1-x) &=\operatorname{coef}_{u^{-1}}\biggl[F\biggl(x,\frac yu,u^2,\frac wu\biggr)(1-x)\biggr] \end{split} \end{gathered}
\end{equation*}
\notag
$$
(асимметрия между $G_1$ и $G_2$ вызвана асимметричностью функции $\varphi_0$),
$$
\begin{equation*}
\begin{aligned} \, H_1(x,w) &=\operatorname{coef}_{u^{-1}}\biggl[ G_1\biggl(\frac xu,u^3,\frac{w}{u^2}\biggr)\biggr], \\ H_2(x,w) &=\operatorname{coef}_{u^{-1}}\biggl[ G_2\biggl(\frac{x}{u^2},u^3,\frac wu\biggr)\biggr]. \end{aligned}
\end{equation*}
\notag
$$
Заметим, что в этом пункте производящие функции понимаются как формальные степенные ряды. Рассмотрим симметризованные производящие функции
$$
\begin{equation*}
\begin{aligned} \, \widetilde F(x,y,z,w) &= F(x,y,z,w)+F(w,z,y,x), \\ \widetilde G(x,z,w) &= G_1(x,z,w)+G_2(w,z,x), \\ \widetilde H(x,w) &= H_1(x,w)+H_2(w,x). \end{aligned}
\end{equation*}
\notag
$$
Из вышеприведенных соотношений для $F$, $G_1$, $G_2$, $H_1$, $H_2$ непосредственно вытекает
$$
\begin{equation}
\begin{split} &\widetilde F(x,y,z,w)(1-x-y-z-w+xz+yw+xw ) \\ &\qquad =y^{1/2}(1-w)\widetilde G(xy^{1/2},y^{1/2}z,w) +z^{1/2}(1-x)\widetilde G(x,yz^{1/2},z^{1/2}w), \end{split}
\end{equation}
\tag{3}
$$
$$
\begin{equation}
\widetilde G(x,z,w)(1-w)=\operatorname{coef}_{u^{-1}} \biggl[\widetilde F\biggl(\frac xu,u^2,\frac zu,w\biggr)(1-w)\biggr]+x^{-1},
\end{equation}
\tag{4}
$$
$$
\begin{equation}
\widetilde H(x,w)=\operatorname{coef}_{u^{-1}} \biggl[\widetilde G\biggl(\frac xu,u^3,\frac{w}{u^2}\biggr)\biggr].
\end{equation}
\tag{5}
$$
4.3. УравнениеМы собираемся получить уравнение на $\widetilde G(xt^{-1/2}, t^{3/2},t^{-1}x)$, выразив $\widetilde F$ через $\widetilde G$ из (3) и подставив результат в (4). Для этого нам потребуется делить степенные ряды на многочлены. Однако если степени каких-то переменных меняются от $-\infty$ до $+\infty$, смысл такого деления требует уточнения. Поясним возможную неоднозначность на примере. Рассмотрим выражение $\operatorname{coef}_{u^{-1}}\bigl[1/(x-uy)\bigr]$. Его можно понимать либо как
$$
\begin{equation*}
\operatorname{coef}_{u^{-1}}\biggl[ \frac{x^{-1}}{1-uyx^{-1}}\biggr] =\frac1x\operatorname{coef}_{u^{-1}}\biggl[1+\frac{uy}x+\frac{u^2y^2}{x^2}+\dotsb\biggr] =0,
\end{equation*}
\notag
$$
либо как
$$
\begin{equation*}
\operatorname{coef}_{u^{-1}}\biggl[ -\frac{(uy)^{-1}}{1-x(uy)^{-1}}\biggr] =-\operatorname{coef}_{u^{-1}}\biggl[\frac1{uy}\biggl(1+\frac{x}{uy}+\frac{x^2}{u^2y^2} +\dotsb\biggr)\biggr] =-\frac1y.
\end{equation*}
\notag
$$
Во избежание неоднозначностей такого рода мы введем новую формальную переменную $q$ и рассмотрим формальные ряды
$$
\begin{equation*}
\begin{gathered} \, F_q(x,y,z,w)=F(xq,yq^2,zq^2,wq), \\ G_{1,q}(x,z,w)=G_1(xq^2,zq^3,wq), \\ G_{2,q}(x,y,w)=G_2(xq,yq^3,wq^2), \\ H_{k,q}(x,w)=H_k(xq^3,wq^3), \qquad k=1,2, \end{gathered}
\end{equation*}
\notag
$$
которые будем понимать как элементы кольца
$$
\begin{equation*}
\mathbb Z\bigl[x^{\pm1},y^{\pm1/2},z^{\pm1/2},w^{\pm1},u^{\pm1/2},t^{\pm1/2}\bigr]((q))
\end{equation*}
\notag
$$
формальных степенных рядов от $q$ (возможно, начинающихся с отрицательных степеней), коэффициенты которых являются многочленами Лорана от $x,y^{1/2},\dots$ . Геометрический смысл показателя степени переменной $q$ – это удвоенная площадь $\varphi_0$-допустимой фигуры, соответствующей данному моному, т.е. $\displaystyle2\int_0^3\varphi(x)\,dx$, где $\varphi$ – функция, график которой задает верхний край фигуры. Несложно проверить вручную, что
$$
\begin{equation*}
\begin{aligned} \, F_q &=(xq)^{-1}+(1+x^{-1}w)+(x+w+x^{-1}y+x^{-1}z+x^{-1}w^2)q+\dotsb, \\ G_{1,q} &=x^{-1}q^{-2}+w(xq)^{-1}+w^2x^{-1}+w^3x^{-1}q+(x+w^4x^{-1})q^2+\dotsb, \\ G_{2,q} &=x^{-1}wq+(w+yx^{-1})q^2+(wx+2y)q^3+(wx^2+4xy)q^4+\dotsb, \\ H_{1,q} &=wx^{-1}+xq^3+4w^2 q^6+(30wx^2+24 w^4 x^{-1})q^9+\dotsb, \\ H_{2,q} &=wq^3+5(x^2+w^3x^{-1})q^6+ 32w^2xq^9+\dotsb. \end{aligned}
\end{equation*}
\notag
$$
Далее, зададим $\widetilde F_q$, $\widetilde G_q$, $\widetilde H_q$ теми же формулами, что и в п. 4.2, но с добавлением всюду индекса $q$. Например,
$$
\begin{equation*}
\widetilde G_q(x,z,w)=\frac{1}{xq^2}+\frac w{xq}+\frac{w^2}x +\biggl(\frac{w^3}x+\frac xw\biggr)q +\biggl(2x+\frac{w^4}x+\frac zw\biggr)q^2+\dotsb.
\end{equation*}
\notag
$$
Тогда соотношения (3)–(5) принимают вид
$$
\begin{equation}
\widetilde F_q=\frac{qy^{1/2}(1-wq)\widetilde G_q(xy^{1/2},y^{1/2}z,w) +qz^{1/2}(1-xq)\widetilde G_q(wz^{1/2},z^{1/2}y,x)} {1-xq-yq^2-zq^2-wq+xzq^3+ywq^3+xwq^2 },
\end{equation}
\tag{6}
$$
$$
\begin{equation}
\widetilde G_q(x,z,w) =\operatorname{coef}_{u^{-1}}\biggl[q\widetilde F_q\biggl(\frac xu,u^2,\frac zu,w\biggr)\biggr] +\frac1{x(1-wq)q^2},
\end{equation}
\tag{7}
$$
$$
\begin{equation}
\widetilde H_q(x,w)=\operatorname{coef}_{u^{-1}} \biggl[q\widetilde G_q\biggl(\frac xu,u^3,\frac{w}{u^2}\biggr)\biggr].
\end{equation}
\tag{8}
$$
Положим
$$
\begin{equation*}
\begin{aligned} \, g_q(x,t) &= t^{1/2}x^2q^2 \widetilde G_q(x^2t^{-1/2},x^3t^{3/2},xt^{-1}) \\ &=t+xq+t^{-1}x^2q^2+(t^{-2}+t)x^3q^3+(t^{-3}+2+t^3)x^4 q^4+\dotsb. \end{aligned}
\end{equation*}
\notag
$$
Условие четности для индексов ненулевых коэффициентов рядов $G_1$ и $G_2$ (см. рис. 5) обеспечивает отсутствие дробных степеней в ряде $g_q(x,t)$. Более того, $x$ и $q$ входят в каждый моном ряда $g_q$ с одинаковыми степенями, тем самым $g_q(x,t)=g(xq,t)$ для некоторого формального ряда $g(x,t)\in\mathbb Z[t^{\pm1}]((x))$. Подставляя (3) в (4), обозначая знаменатель в (6) через $Q_q(x,y,z,w)$ и замечая, что
$$
\begin{equation}
\operatorname{coef}_{u^{-1}}\bigl[\mathcal F(x,t,u)\bigr] =\operatorname{coef}_{u^{-1}}\bigl[xt^{-1/2}\mathcal F(x,t,uxt^{-1/2})\bigr]
\end{equation}
\tag{9}
$$
для любого формального ряда по $u$, получаем
$$
\begin{equation*}
\begin{aligned} \, g_q(x,t) &\stackrel{(7)}{=} \operatorname{coef}_{u^{-1}}\biggl[t^{1/2} x^2 q^3 \widetilde F_q\biggl(\frac{x^2}{ut^{1/2}},u^2,\frac{x^3t^{3/2}}{u},\frac{x}{t}\biggr)\biggr] +\frac{t^2}{t-xq} \\ &\stackrel{(9)}{=} \operatorname{coef}_{u^{-1}}\biggl[x^3 q^3 \widetilde F_q\biggl(\frac{x}{u},\frac{x^2u^2}{t},\frac{x^2t^2}{u},\frac{x}{t}\biggr)\biggr] +\frac{t^2}{t-xq} \\ &\stackrel{(6)}{=} x^2q^2\operatorname{coef}_{u^{-1}}\biggl[\frac{\frac{u}{t}\bigl(1-\frac{xq}{t}\bigr)g_q(x,t) +\frac{t}{u}\bigl(1-\frac{xq}{u}\bigr)g_q(x,u)} {Q_q\bigl(x/u,\,x^2u^2/t,\,x^2t^2/u,\,x/t\bigr)}\biggr] +\frac{t^2}{t-xq} \\ &= x^2q^2\operatorname{coef}_{u^{-1}}\biggl[\frac{u^3(t-xq)g_q(x,t)+t^3(u-xq)g_q(x,u)}{P(xq,t,u)} \biggr]+\frac{t^2}{t-xq}, \end{aligned}
\end{equation*}
\notag
$$
где
$$
\begin{equation}
P(x,t,u)=u^2t^2-(u+t)utx +(1-t^3-u^3)utx^2+ (t^4+u^4)x^3.
\end{equation}
\tag{10}
$$
Мы видим, что переменные $x$ и $q$ “синхронизированны” в правой части получившегося уравнения: они входят в одинаковых степенях в каждый моном каждого степенного ряда в этом выражении. Это значит, что мы получили следующее тождество в кольце $\mathbb Z[t^{\pm1},u^{\pm1}]((x))$:
$$
\begin{equation}
g(x,t)\Psi(x,t)=\frac{t^2}{t-x}+\operatorname{coef}_{u^{-1}} \biggl[\frac{t^3x^2(u-x)g(x,u)}{P(x,t,u)}\biggr],
\end{equation}
\tag{11}
$$
где
$$
\begin{equation*}
\Psi(x,t)=1-x^2(t-x)\Phi(x,t), \qquad \Phi(x,t)=\operatorname{coef}_{u^{-1}}\biggl[\frac{u^3}{P(x,t,u)}\biggr].
\end{equation*}
\notag
$$
Вот несколько начальных членов этих рядов1:
$$
\begin{equation}
\begin{aligned} \, \notag \Phi(x,t) &=t^{-2}x^2+(t^{-3}+1)x^3+(t^{-4}+2t^{-1}+t^2)x^4 +(t^{-5}+3t^{-2}+3t)x^6+\dotsb, \\ \Psi(x,t) &=1-t^{-1}x^4-tx^5-(1+t^3)x^6-(t^{-1}+2t^2)x^7-(6t^{-2}+3t)x^8-\dotsb. \end{aligned}
\end{equation}
\tag{12}
$$
Найдя $g$ из уравнения (11), можно вычислить и $\widetilde H(x,x)$. Действительно, в силу (5) мы имеем
$$
\begin{equation*}
x\widetilde H_q(x^3,x^3) =\operatorname{coef}_{t^0}\biggl[tx\widetilde G_q \biggl(\frac{x^3}t,t^3,\frac{x^3}{t^2}\biggr)\biggr] =\operatorname{coef}_{t^0}\biggl[t^{1/2}x\widetilde G_q \biggl(\frac{x^3}{t^{1/2}},t^{3/2},\frac{x^3}{t}\biggr)\biggr].
\end{equation*}
\notag
$$
Заменяя $t$ на $x^2t$ (ср. с (9)) и полагая $q=1$, получаем
$$
\begin{equation}
x \widetilde H(x^3,x^3)=\operatorname{coef}_{t^{0}}\bigl[g(x,t)\bigr].
\end{equation}
\tag{13}
$$
4.4. ВычислениеВ этом пункте мы исследуем аналитические функции, задаваемые рядами, обсуждавшимися в п. 4.3. Согласно п. 4.1 нам требуется найти наименьший положительный полюс функции $H^*(x)$, т.е. наименьший положительный нуль $\beta$ функции $1-H(x)$. Можно проверить, что Будучи суммой степенного ряда с положительными коэффициентами, функция $x\widetilde H(x,x)$ возрастает при $x>0$, значит, нам достаточно научиться вычислять значения функции $\widetilde H(x,x)$ для любого $x$ из некоторого интервала, содержащего точку $\beta$. В силу (13) для этого можно численно проинтегрировать функцию $g(x^{1/3},t)$ по некоторому контуру $\Gamma_x$ (ср. с доказательством леммы 3.2). Таким образом, нам надо уметь вычислять $g(x,t)$ при любых $x\in[0,x_0^+]$ и $t\in\Gamma_x$ для некоторого $x_0^+ > x_0=\beta^{1/3}$. Это возможно, так как при фиксированном $x$, заменив $\operatorname{coef}_{u^{-1}}[\dots]$ на $\displaystyle \frac1{2\pi i}\int_{\Gamma_x}(\dots)\,du$, мы из уравнения (11) получим уравнение Фредгольма на функцию $g$, ограниченную на $\Gamma_x$. Перейдем теперь к более подробному изложению.Обозначим
$$
\begin{equation*}
\begin{aligned} \, \Gamma &=\biggl\{(x,t,u)\in\mathbb R\times\mathbb C^2\Bigm| 0<x<\frac 12,\, |t|=|u|=1\biggr\}, \\ \Gamma' &=\biggl\{(x,t)\in\mathbb R\times\mathbb C\Bigm| 0<x<\frac 12,\, |t|=1\biggr\}. \end{aligned}
\end{equation*}
\notag
$$
Лемма 4.1. Многочлен $P(x,t,u)$, определенный в (10), не обращается в нуль на $\Gamma$. При любых фиксированных $(x,t)\in\Gamma'$ многочлен $P(x,t,u)$ имеет два простых корня $u_k(x,t)$, $k=1,2$, в единичном круге $|u|<1$ и два простых корня вне единичного круга. Доказательство. Первое утверждение можно проверить при помощи любой системы символьных вычислений, например, следующим образом. Обозначим через $S^1$ единичную окружность в $\mathbb C$. Тогда $\Gamma=(0,1/2)\times S^1\times S^1$. Отождествим $S^1$ с $\mathbb{RP}^1$ посредством некоторой рациональной параметризации. Тогда $\operatorname{Re} P$ и $\operatorname{Im} P$ станут вещественными рациональными функциями на алгебраическом многообразии $\Gamma$, и, вычисляя результанты, дискриминанты и т.п., можно убедиться в том, что вещественная кривая, заданная уравнениями $\operatorname{Re} P=\operatorname{Im} P=0$, лежит вне слоя $0<r<1/2$. Опишем это вычисление более подробно. Пусть $p(x,T,U)$ и $q(x,T,U)$ – вещественные многочлены такие, что Заметим, что $\zeta(\mathbb R)=S^1\setminus\{-1\}$, значит, $(x,T,U)$ – координаты на аффинной карте $\Gamma\setminus\{(t+1)(u+1)=0\}$ многообразия $\Gamma$. Проекция вещественной алгебраической кривой $\Gamma\cap\{P=0\}$ на плоскость $(x,T)$ задается уравнением $R(x,T)=0$, где $R(x,T)$ – результант многочленов $p$ и $q$ по переменной $U$. Чтобы доказать, что кривая $R(x,T)=0$ не имеет вещественных точек в полосе $0<x<1/2$, достаточно найти на этом интервале все вещественные корни уравнения $D(x)=0$, где $D(x)$ – дискриминант многочлена $R$ по переменной $T$, а затем проверить, что уравнение $R(x_k,T)=0$ при каждом $k=1,\dots,2n+1$ не имеет вещественных корней, где $0<x_1<\dots<x_{2n+1}<1/2$ и числа $x_k$ при четных $k$ – все вещественные корни многочлена $D(x)$ на интервале $0<x<1/2$. Это вычисление показывает, что $P(x,u,t)\ne0$ при $(x,u,t)\in\Gamma$ и $(t+1)(u+1)\ne0$. Затем надо проверить, что $P(x,\zeta(T),-1)\ne0$, $P(x,-1,\zeta(U))\ne0$ и $P(x,-1,-1)\ne0$ при $0<x<1/2$, $T\in\mathbb R$.
Похожим образом можно проверить, что при любых фиксированных $(x,t)\in\Gamma'$ дискриминант многочлена $P$ по переменной $u$ не обращается в нуль, а значит, при $(x,t)\in\Gamma'$ все четыре корня многочлена $P$ (рассматриваемого как многочлен от $u$) попарно различны. В силу вышесказанного число корней многочлена $P$ в диске $|u|<1$ постоянно. Таким образом, для доказательства второго утверждения леммы достаточно его проверить для одного конкретного выбора значений переменных $x$ и $t$, например, для $t=1$ и очень малого $x$. Лемма доказана. Лемма 4.2. (a) Формальный степенной ряд $1/P(x,t,u)\in\mathbb Z[t^{\pm1},u^{\pm1}]((x))$ сходится к функции $1/P(x,t,u)$ в некоторой окрестности множества $\Gamma\cap\{x< 1/4\}$. (b) Формальный степенной ряд $\Phi(x,t)\in\mathbb Z[t^{\pm1}]((x))$ сходится к аналитической функции (которую мы тоже обозначим $\Phi(x,t)$) в некоторой окрестности множества $\Gamma'\cap\{x<1/4\}$. Функция $\Phi(x,t)$ аналитически продолжается в окрестность множества $\Gamma'$ посредством интеграла Коши
$$
\begin{equation}
\Phi(x,t)=\frac{1}{2\pi i}\oint_{|u|=1}\frac{u^3\,du}{P(x,t,u)} =\sum_{k=1}^2\frac{u_k(x,t)^3}{P'_u(x,t,u_k(x,t))},
\end{equation}
\tag{15}
$$
где $u_1(x,t)$ и $u_2(x,t)$ – корни $P$ в единичном круге $|u|<1$; см. лемму 4.1. Доказательство. Степенной ряд $1/P(x,t,u)$, участвующий в определении функции $\Phi(x,t)$, – это разложение по переменной $x$, следовательно, $1/P=a_0^{-1}(1+X+X^2+\cdots)$, где $X=(a_1+a_2+a_3)/a_0$ и $a_k=x^k\operatorname{coef}_{x^k}[P]$. Если $(x,t,u)\in\Gamma$, то $|a_0|=1$, $|a_1|\leqslant 2x$, $|a_2|\leqslant 3x^2$, $|a_3|\leqslant 2x^3$ и, значит, $|X|\leqslant 2x+3x^2+2x^3$. Поэтому $|X|<1$ при $x<1/4$, из чего следует сходимость ряда $1/P$ в требуемой области. Этот факт в сочетании с леммой 4.1 влечет все остальные утверждения доказываемой леммы.
Лемма доказана. Функция Psi на языке программы Mathematica, приведенная ниже, вычисляет $\Psi(x,t)$ при $(x,t)\in\Gamma'$ с любой заданной точностью. Заметим, что одна из функций, $u_1(x,t)$ или $u_2(x,t)$, имеет точку ветвления при $(x,t)=(1/2,1)$ и, значит, $\Phi$ и $\Psi$ тоже ветвятся в этой точке. Разложение Лорана–Пюизё функции $\Psi(x,1)$ по степеням $s=\sqrt{1/2-x}$ имеет вид
$$
\begin{equation*}
\begin{aligned} \, \Psi(x,1) &=-\frac{1}{4\sqrt6}\,s^{-1}+\frac{12-\sqrt2}{8}-\frac{3}{8\sqrt6}\,s -\frac{3}{8\sqrt2}\,s^2 \\ &\qquad+\frac{103}{96\sqrt6}\,s^3-\frac{87}{32\sqrt2}\,s^4 +\frac{2635}{192\sqrt6}\,s^5+\dotsb. \end{aligned}
\end{equation*}
\notag
$$
Пусть $x_0^-={16}/{33}$ и $x_0^+={17}/{35}$. Мы вскоре увидим, что $x_0\in[x_0^-,x_0^+]$; числа $x_0^{\pm}$ задаются начальными отрезками цепной дроби для $x_0$. Используя разложение $\Psi$ в $(1/2,1)$ и вычисляя значения $\Psi(x,t)$ (при помощи нижеприведенной программы Mathematica) на достаточно мелкой сетке на $\Gamma'$, можно проверить, что $\Psi$ не обращается в нуль на $\Gamma'\cap\{x<x_0^+\}$ и
$$
\begin{equation}
\min_{0\leqslant x\leqslant x_0^+,\,|t|=1}|\Psi(x,t)| =\min_{0\leqslant x\leqslant x_0^+,\,|t|=1}\operatorname{Re}\Psi(x,t) =\Psi(x_0^+,1)=0.44768\dots;
\end{equation}
\tag{16}
$$
см. линии уровня функции $\operatorname{Re}\Psi$ на рис. 6 (мы опускаем подробности оценивания ошибки). Применяя к функции $|P(x/4,e^{i\tau},e^{i\theta})|^2$ лемму 5.2 с должным образом выбранным $h$, находим
$$
\begin{equation}
\min_{0\leqslant x\leqslant x_0^+,\,|t|=|u|=1}|P|=P(x_0^+,1,1)=0.02183\dots
\end{equation}
\tag{17}
$$
(мы здесь масштабировали $x$, чтобы уравновесить частные производные). Вычисление можно ускорить, выбирая разные шаги сетки в разных зонах множества $\Gamma$. Мы варьировали шаг от $h=1/300$ возле точки минимума до $h=1/20$ вдали от нее. Для оценки погрешности мы использовали очевидные грубые оценки четвертых производных, а затем с их помощью получали более точные оценки вторых производных в каждой зоне, опять-таки используя лемму 5.2. Лемма 4.3. Формальный ряд $g(x,t)$ (введенный в п. 4.2) сходится в некоторой окрестности множества $\Gamma'\cap\{|x|<2^{-3/2}\}$. Доказательство. По теореме Анклина (см. [1]) число примитивных целочисленных триангуляций целочисленного многоугольника $\Pi$ ограничено сверху величиной $2^N$ для $N=\#\bigl(\Pi\cap(\mathbb Z^2\setminus\frac12\mathbb Z^2)\bigr)$, причем из формулы Пика легко вывести, что $N<3\operatorname{Area}(\Pi)\,{-}\,3/2$. Площадь фигуры, отвечающей коэффициенту $g^{(k)}_{a,c,d}$, равна $(2a+3c+d+3)/2$. Следовательно, $\widetilde g_{a,c,d} < c_0 2^{3(2a+3c+d)/2}$ для некоторой константы $c_0$, и, значит, при $|t|=1$ мы получаем
где $A_n=\#\bigl\{(a,c,d)\in\mathbb Z_+^3\mid 2a+3c+d=n\bigr\}$. Поскольку числа $A_n$ ограничены полиномиальной функцией от $n$, ряд сходится при $x<2^{-3/2}$. Лемма доказана. Из лемм 4.2 и 4.3 в сочетании с (11) и (16) следует, что функция $g(x,t)$ аналитична в окрестности множества $\Gamma'\cap\{x<2^{-3/2}\}$ и удовлетворяет там условию
$$
\begin{equation}
g(x,t)=\frac{t^2}{(t-x)\Psi(x,t)} +\frac{1}{2\pi i}\oint_{|u|=1}\frac{x^2t^3(u-x)g(x,u)\,du}{P(x,t,u)\Psi(x,t)}.
\end{equation}
\tag{18}
$$
При любом фиксированном $x$ это уравнение Фредгольма второго рода на функцию $g(x,t)$, рассматриваемую как функция от $t$. Лемма 4.4. Функция $g(x,t)$ аналитически продолжается в окрестность множества $\Gamma'\cap\{x<x_0^+\}$ и удовлетворяет уравнению (18) в этой области. Доказательство. Перепишем (18) в более привычном виде: где мы полагаем $t=e^{2\pi i\tau}$, $u=e^{2\pi i\theta}$ и
Как мы отметили выше, $g$ удовлетворяет (18) и, значит, $\varphi_g$ удовлетворяет (19) при малых $x$. Таким образом, в силу теоремы единственности для аналитических функций достаточно показать, что при всех $x\in[0,x_0^+]$ существует единственное решение уравнения (19) и что оно аналитично по $(x,\tau)$. По лемме 5.6 для этого достаточно убедиться в том, что $1$ не является собственным значением оператора $\mathcal K_x$ при всех $x\in[0,x_0^+]$, где $\mathcal K_x\colon \mathcal C[0,1]\to\mathcal C[0,1]$ – интегральный оператор Фредгольма, который функции $\varphi(\tau)$ сопоставляет $\displaystyle\psi(\tau)=\int_0^1 K(x,\tau,\theta)\varphi(\theta)\,d\theta$. Это в свою очередь следует из оценки
$$
\begin{equation*}
\max_{0\leqslant x\leqslant x_0^+}\mathcal N_2(x)=\mathcal N_2(x_0^+) =0.88525,
\end{equation*}
\notag
$$
где $\displaystyle\mathcal N_2(x)=\int_{[0,1]^2}|K(x,\tau,\theta)|^2\,d\tau\,d\theta$. Она получена численным интегрированием. Чтобы оценить погрешность приближения, нужны верхние оценки частных производных ядра $K$. Их несложно получить из нижних оценок (16) и (17) функций $|\Psi|$ и $|P|$ в совокупности с верхними оценками производных функции $\Psi$, полученных из ее интегрального представления в (15). В качестве верхних оценок производных от многочленов, участвующих в определении $K$, можно просто брать суммы верхних оценок мономов.
Лемма доказана. Заменяя интегралы интегральными суммами, уравнение (18) можно решить с любой точностью. Затем из (13) и (14) можно численно найти $H(x)$, воспользовавшись интегралом Коши
$$
\begin{equation}
H(x^3)=\frac{x^2}{2\pi i}\oint_{|t|=1}\frac{g(x,t)\,dt}{t} =x^2\int_0^1 \varphi_g(x,\tau)\,d\tau
\end{equation}
\tag{20}
$$
(напомним, что $\varphi_g(x,\tau):=g(x,e^{2\pi i\tau})$; см. (19)). Изложенное в данном пункте можно подытожить следующим образом (напомним, что $f(m,n)$ – это число примитивных целочисленных триангуляций прямоугольника $m\times n$). Предложение 4.5. Имеет место где: $\bullet$ $x_0$ – единственное решение уравнения $H(x^3)=1$ на отрезке $[0,x_0^+]$, $x_0^+={17}/{35}$; $\bullet$ функция $H(x)$ выражается через $g(x,t)$ формулой (20) и монотонна на $[0,x_0^+]$; $\bullet$ $g(x,t)$ является решением уравнения Фредгольма (18), в котором $P$ задается формулой (10), а $\Psi$ задается как $\Psi(x,t)=1-x^2(t-x)\Phi(x,t)$ с функцией $\Phi$, заданной формулой (15); при всех $x\in[0,x_0^+]$ уравнение (18) имеет единственное решение. На рис. 7 мы приводим функцию $H$ на языке Mathematica, которая вычисляет $H(x)$ с любой заданной точностью. Ошибку приближения можно оценить с помощью леммы 5.4. Можно проверить, что функции $P(x,t,u)$ и $\Psi(x,t)$ не обращаются в нуль при $x<x_0^+$, $|u|=1$ и ${10}/{13}<|t|<{13}/{10}$. На рис. 8 и рис. 9 изображен образ кольцевой области ${10}/{13}<|t|<{13}/{10}$ при отображении $t\mapsto\Psi(x_0,t)$. Поэтому можно применить оценку ошибки (27), положив $r=10/13$ и, значит, $a=-\log r/(2\pi)=0.04176$. Оценивая $H(x)$ при $x\approx x_0$, в (27) можно положить
$$
\begin{equation*}
C\leqslant 1, \quad \frac1n\|B\|_1\leqslant 3.05, \quad M\leqslant 3910, \quad M'\leqslant 94.6, \quad M_f\leqslant 258.
\end{equation*}
\notag
$$
Это дает оценку погрешности, приведенную в последнем столбце табл. 7. Мы видим, что она весьма близка к фактической погрешности, приведенной в четвертом столбце. Таблица 7.
§ 5. Приближенное решение уравнений Фредгольма с аналитическими ядрами5.1. Оценка ошибки. Некоторые общие фактыОбозначения в этом пункте не зависят от обозначений в остальных частях статьи. Лемма 5.1. Пусть $f$ – голоморфная функция в окрестности кольца $R_1 < |z| < R_2$, и пусть $f(z)=\sum_{n\in\mathbb Z} c_n z^n$ – ее ряд Лорана. Тогда при $R_1<r<R_2$ и при всех $n>0$ где $\omega=e^{2\pi i/n}$, $q_1=R_1/r$, $q_2=r/R_2$ и $M_j=\max_{|z|=R_j} |f(z)|$ при $j=1,2$. Доказательство. Имеют место равенства
$$
\begin{equation*}
\sum_{k=1}^n f(r\omega^k)=\sum_{k=1}^n\; \sum_{m\in\mathbb Z} c_m (r\omega^k)^m, \qquad \sum_{k=1}^n \omega^{km}= \begin{cases} n, &\text{если $n$ делит $m$}, \\ 0 &\text{в противном случае}, \end{cases}
\end{equation*}
\notag
$$
следовательно, левая часть в (21) равна $\bigl|\sum_{p\in\mathbb Z\setminus\{0\}} c_{pn}r^{pn}\bigr|$ и коэффициенты можно оценить через интеграл Коши.
Лемма доказана. Лемма 5.2. Пусть $h>0$ и $D\subset\mathbb R^d$ – произведение отрезков $[0,n_1h]\times\dots\times[0,n_dh]$ с целыми положительными $n_1,\dots,n_d$. Пусть $f\colon D\to\mathbb R$ – функция класса $\mathcal C^2$ и $M=\max_{i,j}\max_D|\partial_i\partial_j f|$. Тогда где $h\mathbb Z^d=\{h\vec n\mid\vec n\in\mathbb Z^n\}$. Аналогичная оценка есть для $\max_D f$. Доказательство. Применяем индукцию по $d$. Пусть минимум достигается в $x_0\in D$. Если $x_0$ лежит внутри $D$, мы оценим $|f(x)-f(x_0)|$ для ближайшей к $x_0$ точки решетки $x$ при помощи формулы Тейлора–Лагранжа для разложения второго порядка функции $f(x_0+t(x-x_0))$ в точке $t=0$. Если $x_0$ лежит на границе области $D$, мы применим предположение индукции к ограничению функции $f$ на грань области $D$, содержащую $x_0$.
Лемма доказана. 5.2. Ошибка погрешности приближенного решения уравнения ФредгольмаПусть $\varphi\colon \mathbb R\to\mathbb C$ – непрерывное решение интегрального уравнения Фредгольма с аналитическими комплекснозначными функциями $K$ и $f$, которые (би)периодичны с периодом $1$, т.е. $K(x,y)=K(x+1,y)=K(x,y+1)$ и $f(x)=f(x+1)$. Будем предполагать, что $K$ и $f$ продолжаются до комплексно аналитических функций в окрестности множества $(D\times\mathbb R)\cup(\mathbb R\times D_1)$ в $\mathbb C^2$ и в окрестности множества $D$ в $\mathbb C$ соответственно, где
$$
\begin{equation*}
D =\{z\in\mathbb C\mid -a \leqslant \operatorname{Im} z\leqslant a \}, \quad D_1=\{z\in\mathbb C\mid -a_1\leqslant \operatorname{Im} z\leqslant a_1\}, \qquad 0<a_1<a.
\end{equation*}
\notag
$$
Положим
$$
\begin{equation*}
C=\int_0^1|\varphi(x)|\,dx, \qquad M=\max_{D\times\mathbb R}|K|, \quad M'_1=\max_{\mathbb R\times D_1}|K|, \quad M_f=\max_{D}|f|.
\end{equation*}
\notag
$$
Доказательство. При любом $(x_0,y_0)\in\mathbb R^2$ и любом $n$
$$
\begin{equation*}
|\partial_x^n K(x_0,y_0)|\leqslant\biggl|\frac{n!}{2\pi i}\int_{|z|=a}\frac{K(z,y_0)\,dz}{z^{n+1}}\biggr| \leqslant \frac{Mn!}{a^n},
\end{equation*}
\notag
$$
и аналогично $|f^{(n)}(x_0)|\leqslant M_f n!/a^n$. Тогда, дифференцируя (22) $n$ раз по $x$, получим Следовательно, ряд Тейлора функции $\varphi$ в точке $x_0$ сходится в круге $|z-x_0|<a$, и при $|z-x_0|\leqslant a_1$ мы имеем из чего вытекает требуемая оценка на $M_\varphi$.
Лемма доказана. Выясним, что происходит при замене интеграла в (22) на $n$-ю интегральную сумму при целом положительном $n$. А именно, рассмотрим векторы $\varphi^{[n]}=(\varphi_1^{[n]},\dots,\varphi_n^{[n]})$, $f^{[n]}=(f_1^{[n]},\dots,f_n^{[n]})$, а также $(n\times n)$-матрицу $K^{[n]}=(K_{jk}^{[n]})_{jk}$, заданные как
$$
\begin{equation*}
\varphi^{[n]}_j=\varphi\biggl(\frac jn\biggr), \qquad f_j^{[n]}=f\biggl(\frac jn\biggr), \qquad K_{jk}^{[n]}=\frac1n K\biggl(\frac jn,\frac kn\biggr).
\end{equation*}
\notag
$$
Пусть $\widehat\varphi^{[n]}=\bigl(\widehat\varphi^{[n]}_1,\dots,\widehat\varphi^{[n]}_n\bigr)$ – решение уравнения
$$
\begin{equation}
\widehat\varphi^{[n]}=K^{[n]}\widehat\varphi^{[n]}+f^{[n]}.
\end{equation}
\tag{25}
$$
Это уравнение является дискретизацией уравнения (22), поэтому естественно ожидать, что $\widehat\varphi^{[n]}$ хорошо приближает $\varphi$. Используя подход из [5], оценим скорость сходимости. Наша конечная цель – найти хорошую верхнюю оценку для погрешности приближения
$$
\begin{equation*}
E_n:= \biggl|\int_0^1 \varphi(x)\,dx-\frac1n\sum_{j=1}^n \widehat\varphi^{[n]}_j\biggr|.
\end{equation*}
\notag
$$
Определим нормы $\|\cdot\|_p$, $1\leqslant p\leqslant\infty$, на $\mathbb C^n$ обычным способом. Для квадратной матрицы $A=(a_{jk})_{jk}$ с комплексными коэффициентами положим
$$
\begin{equation*}
\|A\|_1=\sum_{j,k} |a_{jk}|, \qquad \|A\|_2=\biggl(\sum_{j,k}|a_{jk}|^2\biggr)^{1/2}.
\end{equation*}
\notag
$$
Лемма 5.4. (a) Предположим, что матрица $A^{[n]}=I-K^{[n]}$ обратима, и обозначим обратную матрицу через $B^{[n]}$. Тогда (b) Предположим, что $\|K^{[n]}\|_2=M_2<1$. Тогда матрица $A^{[n]}$ обратима и $\dfrac1n\|B^{[n]}\|_1\leqslant \dfrac1{1-M_2}$, из чего, в частности, следует, что $\alpha_n<\alpha_0$ для некоторой константы $\alpha_0=\alpha_0(a,a_1,M,M'_1,M_2,M_f)$, и, значит, $C$ можно оценить при помощи (28) при $n>\alpha_0$. Доказательство. (a) Пусть
$$
\begin{equation*}
\begin{gathered} \, J=\int_0^1\varphi(x)\,dx, \qquad S=\frac1n\sum_j\varphi\biggl(\frac jn\biggr), \qquad \widehat S=\frac1n\sum_j\widehat\varphi\biggl(\frac jn\biggr), \\ \rho=\varphi^{[n]}-\widehat\varphi^{[n]}, \qquad \sigma=A^{[n]}\rho. \end{gathered}
\end{equation*}
\notag
$$
В этих обозначениях $E_n=|J-\widehat S|$. Мы имеем
$$
\begin{equation}
\begin{aligned} \, \|\sigma\|_\infty &=\|A^{[n]}\varphi^{[n]}-A^{[n]}\widehat\varphi^{[n]}\|_\infty \stackrel{(25)}{=} \|A^{[n]}\varphi^{[n]}-f^{[n]}\|_\infty \nonumber \\ & =\bigl\|K^{[n]}\varphi^{[n]}-(\varphi^{[n]}-f^{[n]})\bigr\|_\infty \end{aligned}
\end{equation}
\tag{29}
$$
и в силу (22)
$$
\begin{equation*}
\varphi^{[n]}_j-f^{[n]}_j=\int_0^1 K\biggl(\frac jn,y\biggr)\varphi(y)\,dy,
\end{equation*}
\notag
$$
причем $j$-я компонента вектора $K^{[n]}\varphi^{[n]}$ есть $n$-я интегральная сумма для этого интеграла. Следовательно, применяя лемму 5.1 к функции $K(j/n,z(\zeta))\varphi(z(\zeta))$ после замены переменной $\zeta=e^{2\pi iz}$, мы получим $\|\sigma\|_\infty\leqslant M'_1C_1$, где $C_1=2M_\varphi r_1^n/(1-r_1^n)$, и тогда
$$
\begin{equation}
\|\rho\|_1=\|B^{[n]}\sigma\|_1\leqslant\|B^{[n]}\|_1\times\|\sigma\|_\infty\leqslant M'_1C_1\|B^{[n]}\|_1.
\end{equation}
\tag{30}
$$
Лемма 5.1, примененная к $\varphi(z(\zeta))$, дает $|J-S| \leqslant C_1$. Далее, $|S-\widehat S|\leqslant\frac1n\|\rho\|_1$, следовательно,
$$
\begin{equation*}
E_n=|J-\widehat S|\leqslant|J-S|+|S-\widehat S| \leqslant C_1+\frac1n\|\rho\|_1\leqslant C_1+\frac1n M'_1C_1\|B^{[n]}\|_1,
\end{equation*}
\notag
$$
что дает (26) после применения (23). Полагая $a_1=a-1/(2\pi n)$ (и, значит, $r_1=e^{1/n}r$) и $M'_1<M'$ в (26), получаем (27). Докажем (28). Легко проверить, что
$$
\begin{equation*}
nC\leqslant\|\varphi^{[n]}\|_1+\frac14\max_{\mathbb R}|\varphi'| \leqslant\|\widehat\varphi^{[n]}\|_1 +\|\rho\|_1+\frac14\max_{\mathbb R}|\varphi'|.
\end{equation*}
\notag
$$
Используя оценки (30) и (24) при $\|\rho\|_1$ и $|\varphi'|$ соответственно, получаем
$$
\begin{equation*}
nC\leqslant\|\widehat\varphi^{[n]}\|_1 +\frac{2M_1M_\varphi\|B^{[n]}\|_1r_1^n}{1-r_1^n}+\frac{CM+M_f}{4a} \stackrel{(23)}{\leqslant} \|\widehat\varphi^{[n]}\|_1+(CM+M_f)\alpha_n.
\end{equation*}
\notag
$$
(b) Предположим теперь, что $\|K^{[n]}\|_2= M_2<1$. Тогда
$$
\begin{equation*}
\|B^{[n]}\|_2=\|(I-K^{[n]})^{-1}\|_2=\|I+K^{[n]}+(K^{[n]})^2+\dotsb\|_2\leqslant \frac{1}{1-M_2}.
\end{equation*}
\notag
$$
По неравенству Коши–Буняковского $\|B^{[n]}\|_1\leqslant n\|B^{[n]}\|_2$. Лемма доказана. 5.3. Численный критерий существования и единственности решенияЗдесь мы сохраняем все предположения о функциях $K(x,y)$ и $f(x)$, кроме того, что больше не предполагаем априори, что уравнение (22) имеет непрерывное решение $\varphi$. Обозначим через $\mathcal K\colon \mathcal C([0,1])\to\mathcal C([0,1])$ интегральный оператор Фредгольма с ядром $K(x,y)$, т.е. оператор $\varphi\mapsto\psi$, где $\displaystyle\psi(x)=\int_0^1 K(x,y)\varphi(y)\,dy$. Лемма 5.5 (ср. с [5; гл. II, § 1, уравнение (26)]). Предположим, что существует $n$ такое, что матрица $I-K^{[n]}$ обратима и $\alpha_n<n$, где $\alpha_n$ определено в (28) (заметим, что ни $f$, ни $\varphi$ не используются в определении величины $\alpha_n$). Тогда $1$ не является собственным числом оператора $\mathcal K$, и, следовательно, для любой непрерывной функции $f$ уравнение (22) имеет единственное непрерывное решение $\varphi$. Доказательство. Пусть $n$ таково, что $\alpha_n<n$. Применим лемму 5.4, (a) для случая, когда $f=0$ и тем самым $\widehat\varphi^{[n]}=0$. Тогда (28) принимает вид $C\leqslant 0$, из чего вытекает отсутствие ненулевых решений уравнения $\mathcal K\varphi=\varphi$, а это и значит, что $1$ не является собственным числом оператора $\mathcal K$. По теореме Фредгольма (см. [2]) в этом случае (22) имеет единственное непрерывное решение для любой $f$.
Лемма доказана. 5.4. Аналитичность решения по параметруПусть $\Lambda$ – область в $\mathbb C$ и $U=\{z\in\mathbb C\mid -a\leqslant\operatorname{Im} z\leqslant a\}$, $a>0$. Пусть $K(\lambda,x,y)$ – аналитическая функция в окрестности множества $\Lambda\,{\times}\, U^2$ в $\mathbb C^3$, и пусть $f(\lambda,y)$ – аналитическая функция в окрестности множества $\Lambda\,{\times}\, U$ в $\mathbb C^2$. Будем предполагать, что $K(\lambda_0,x,y)$ $(1,1)$-бипериодична и $f(\lambda_0,x)$ $1$-периодична при любом фиксированном $\lambda_0\in\Lambda$. При $\lambda\in\Lambda$ обозначим через $\mathcal K_\lambda\colon \mathcal C([0,1])\to\mathcal C([0,1])$ интегральный оператор Фредгольма $\varphi\mapsto\psi$, $\displaystyle\psi(x)=\int_0^1 K(\lambda,x,y)\varphi(y)\,dy$. Следующая лемма непосредственно вытекает из результатов Фредгольма в его основополагающей статье [2] (более общий факт доказан в [11]). Лемма 5.6. Предположим, что $1$ не является собственным числом оператора $\mathcal K_\lambda$ при всех $\lambda\in\Lambda$. Тогда для любого $\lambda\in\Lambda$ существует единственное решение $\varphi(\lambda,x)$ уравнения и при этом функция $\varphi(\lambda,x)$ аналитична в окрестности множества $\Lambda\times U$. Доказательство. В силу результатов Фредгольма (см. [2], а также [6]) при всех $\lambda\in\Lambda$ решение $\varphi(\lambda,x)$ существует и единственно при наших предположениях и его можно представить в виде
$$
\begin{equation*}
\varphi(\lambda,x)=f(\lambda,x)+\int_0^1\frac{D(\lambda,x,y)}{D(\lambda)}f(\lambda,y)\,dy,
\end{equation*}
\notag
$$
где
$$
\begin{equation}
\begin{gathered} \, D(\lambda)=\sum_{n=0}^\infty\frac{(-1)^n A_n(\lambda)}{n!}, \qquad D(\lambda,x,y)=\sum_{n=0}^\infty\frac{(-1)^n B_n(\lambda,x,y)}{n!}, \\ \notag A_n(\lambda)=\int_{[0,1]^n} K(\lambda,\boldsymbol x,\boldsymbol x)\,d\boldsymbol x, \qquad B_n(\lambda,x,y)=\int_{[0,1]^n} K(\lambda,x,\boldsymbol x,y,\boldsymbol x)\,d\boldsymbol x, \\ \notag K(\lambda,x_1,\dots,x_n,y_1,\dots,y_n)=\det\bigl(K(\lambda,x_i,y_j)\bigr)_{i,j=1}^n. \end{gathered}
\end{equation}
\tag{32}
$$
Как показано в [2], $D(\lambda)$ не обращается в нуль на $U$ (потому что $1$ не является собственным числом оператора $\mathcal K_\lambda$ при $\lambda\in\Lambda$). Ясно также, что функции $A_n$ и $B_n$ аналитичны в $\Lambda$ и в $\Lambda\times U^2$ соответственно, и при этом из неравенства Адамара $|\det N|\leqslant n^{n/2}\max_{i,j}|N_{ij}|$ следует верхняя оценка (ср. с [2; с. 368, строка 4])
$$
\begin{equation*}
|A_n(\lambda)|\leqslant n^{n/2}M(\lambda)^n, \qquad |B_{n-1}(\lambda,x,y)|\leqslant n^{n/2}M(\lambda)^n,
\end{equation*}
\notag
$$
где $M(\lambda)=\sup_{(x,y)\in U^2}|K(\lambda,x,y)|$. Следовательно, ряды (32) сходятся к аналитическим функциям, из чего вытекает доказываемый результат.
Лемма доказана. § 6. Непримитивные целочисленные триангуляцииОбозначим число всех (не обязательно примитивных) целочисленных триангуляций прямоугольника $m\times n$ через $f^{\mathrm{np}}(m,n)$ и положим
$$
\begin{equation*}
c^{\mathrm{np}}=\lim_{n\to\infty}\frac{\log_2 f^{\mathrm{np}}(n,n)}{n^2}.
\end{equation*}
\notag
$$
Доказательство. Обозначим $N=n^2$. Любую целочисленную триангуляцию можно подразбить до примитивной. Следовательно, целочисленная триангуляция однозначно определяется выбором примитивной триангуляции и множеством ее ребер, подлежащих удалению. Обозначим через $f_k^{\mathrm{np}}(n,n)$ число целочисленных триангуляций квадрата $n\times n$, имеющих $k$ внутренних вершин и, значит, $\approx 3k$ ребер. Тогда (напомним, что $2^{cN}$ – это оценка числа примитивных целочисленных триангуляций). С другой стороны, число триангуляций с вершинами в произвольном множестве из $k$ точек на плоскости не превосходит $30^k$ (см. [10]), следовательно, Оценки (33) и (34) в совокупности с формулой Стирлинга дают
$$
\begin{equation}
\begin{gathered} \, c^{\mathrm{np}} \leqslant \max_{0\leqslant x\leqslant 1} \min\bigl(3h(x)+c,h(x)+x\log_2 30\bigr), \\ h(x)=-x\log_2 x-(1-x)\log_2(1-x). \notag \end{gathered}
\end{equation}
\tag{35}
$$
Применяя оценку $c\leqslant 4\log_2 \frac{1+\sqrt5}2$ (см. [7], [12], [13]), получаем требуемый результат (максимум в (35) достигается при $x=0.83206855$).
Предложение доказано.
Цитирование в формате AMSBIB
\RBibitem{Ore22} |
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Обратная связь: |
Пользовательское соглашение
|
Регистрация посетителей портала |
Логотипы |
|