1. На главную
  2. Электронные версии
  3. Доклады Российской академии наук. Математика, информатика, процессы управления
  4. T. 492, № 1, 2020

Доклады Российской академии наук. Математика, информатика, процессы управления, 2020, T. 492, № 1, стр. 89-91

Асимптотические оценки числа пороговых функций и вероятности вырожденности случайных {±1}-матриц

А. А. Ирматов 1, *

1 Московский государственный университет имени М.В. Ломоносова
Москва, Россия

* E-mail: irmatov@intsys.msu.ru

Поступила в редакцию 04.03.2020
После доработки 04.03.2020
Принята к публикации 19.03.2020

Полный текст (PDF)

Аннотация

В работе решены две известные проблемы, касающиеся числа пороговых функций P(2, n) и вероятности ${{\mathbb{P}}_{n}}$ вырожденности случайных (n × n) {±1}-матриц, а именно, получены асимптотики

$P(2,n)\sim 2\left( {\begin{array}{*{20}{c}} {{{2}^{n}} - 1} \\ n \end{array}} \right)\quad {\text{и}}\quad {{\mathbb{P}}_{n}}\sim {{n}^{2}} \cdot {{2}^{{1 - n}}}\quad n \to \infty .$

Ключевые слова: пороговая функция, матрица Бернулли, функция Мёбиуса, супермодулярная функция, комбинаторный флаг .

Определение 1. Функция $f{\text{:}}\;{{{\text{\{ }}{\kern 1pt} \pm {\kern 1pt} 1{\text{\} }}}^{n}} \to {\text{\{ }}{\kern 1pt} \pm {\kern 1pt} 1{\text{\} }}$ называется  пороговой функцией, если существуют действительные числа ${{\alpha }_{0}},{{\alpha }_{1}}, \ldots ,{{\alpha }_{n}}$ такие, что

$f({{x}_{1}},\; \ldots ,\;{{x}_{n}}) = {\text{sign}}\left\langle {\alpha ,(1,x)} \right\rangle ,$
где $(1,x)\, = \,(1,{{x}_{1}}, \ldots ,{{x}_{n}}) \in {{{\mathbf{R}}}^{{n + 1}}}$ и $\alpha \, = \,({{\alpha }_{0}}, \ldots ,{{\alpha }_{n}}) \in {{{\mathbf{R}}}^{{n + 1}}}$.

Через $P(2,n)$ обозначим число пороговых функций. Таким образом, пороговой функции с весовым (n + 1)-вектором $\alpha $ можно сопоставить точку в двойственном пространстве $({{{\mathbf{R}}}^{{n + 1}}}){\text{*}} = {{{\mathbf{R}}}^{{n + 1}}}$. Пусть ${{A}^{ \bot }}$ – конечный центральный пучок (т.е. проходящих через ${\mathbf{0}} \in {{{\mathbf{R}}}^{{n + 1}}}$) гиперплоскостей в ${{{\mathbf{R}}}^{{n + 1}}}$ и $A = {\text{\{ }}{{w}_{1}},\; \ldots ,\;{{w}_{T}}{\text{\} }}$ – множество нормальных векторов его гиперплоскостей. Одномерное подпространство, порожденное вектором $w \in {{{\mathbf{R}}}^{{n + 1}}}{\backslash }0,$ определяет точку 〈w〉 n-мерного проективного пространства RPn. Интерпретация пороговых функций как подмножеств точек двойственного пространства позволяет отождествить P(2, n) с числом $C\left( {\left\langle {{{E}_{n}}} \right\rangle } \right)$ непересекающихся областей дополнения в ${{{\mathbf{R}}}^{{n + 1}}}$ к центральному пучку гиперплоскостей с нормальными векторами из множества En = {(1, b1, ... ..., ${{b}_{n}})|{{b}_{i}} \in {\text{\{ }} \pm 1{\text{\} }},i = 1, \ldots ,n{\text{\} }}$. Данное замечание позволяет использовать формулу Л. Шлефли [1] для верхней оценки P(2, n):

(1)
$P(2,n) = C\left( {\left\langle {{{E}_{n}}} \right\rangle } \right) \leqslant 2\sum\limits_{i = 0}^n {\left( {\begin{array}{*{20}{c}} {{{2}^{n}} - 1} \\ i \end{array}} \right)} .$

Следует отметить, что верхняя оценка (1) была переоткрыта в начале 1960-х гг. несколькими авторами (см. [2]). Первая нижняя оценка для P(2, n) была получена С. Мурога [3]: $P(2,n) \geqslant {{2}^{{0.33048{{n}^{2}}}}}.$ С. Яджима и Т. Ибораки [4] улучшили ее до ${{2}^{{n(n - 1)/2 + 8}}}$ для $n \geqslant 6$. В работе [5] было замечено, что из работ А.М. Одлызко [6] и Т. Заславского [7] следует асимптотика логарифма числа пороговых функций: $lo{{g}_{2}}P(2,n)\sim {{n}^{2}}$. Дальнейшее улучшение нижней оценки было получено в работе [8] с помощью оригинальной геометрической конструкции:

$P(2,n) \geqslant {{2}^{{{{n}^{2}}\left( {1 - \tfrac{7}{{lnn}}} \right)}}}P\left( {2,\left[ {\frac{{7(n - 1)}}{{lo{{g}_{2}}(n - 1)}}} \right]} \right).$

Параллельно нахождению асимптотики числа пороговых функций велись исследования по оценке числа вырожденных {±1} (или {0, 1}) (n × n)-матриц. Пусть ${{M}_{n}} = ({{a}_{{ij}}})$ – случайная (n × n) {±1}-матрица с элементами, являющимися независимыми одинаково распределенными случайными величинами Бернулли: Pr(aij = 1) = Pr(aij = –1) = = $\tfrac{1}{2}$. В 1963 г. Я. Комлас [9] доказал гипотезу П. Эрдёша о том, что вероятность вырожденности случайной бернуллиевой {0, 1}-матрицы с ростом размерности стремится к нулю, что верно и для {±1}-матриц: ${{\mathbb{P}}_{n}}\mathop = \limits^{{\text{def}}} \,Pr({\text{det}}{{M}_{n}}$ = 0) = on(1). В 1977 г. он улучшил свой результат до верхней оценки ${{\mathbb{P}}_{n}} < O(1{\text{/}}\sqrt n )$ (см. [10]). В 1995 г. Дж. Кан, Я. Комлос и Е. Семереди в работе [11] добились экспоненциального убывания верхней оценки: $O({{0.999}^{n}})$. В работе [12] Т. Тао и В. Ву получили оценку (3/4 + + ${{o}_{n}}(1){{)}^{n}}$, а в 2009 г. Ж. Бургейн, В. Ву и П.М. Вуд улучшили ее до ${{(\sqrt 2 {\text{/}}2 + {{o}_{n}}(1))}^{n}}$ (см. [13]). В 2018 г. К. Тихомировым в работе [14] было показано, что ${{\mathbb{P}}_{n}} = \mathop {\left( {1{\text{/}}2 + {{o}_{n}}(1)} \right)}\nolimits^n $.

В данной работе найдены асимптотики P(2, n) и ${{\mathbb{P}}_{n}}$.

Теорема 1. Для асимптотики вероятности ${{\mathbb{P}}_{n}}$ имеет место выражение

${{\mathbb{P}}_{n}}\sim {{n}^{2}} \cdot {{2}^{{1 - n}}},\quad n \to \infty .$

Теорема 2. Для асимптотики числа пороговых функций имеет место выражение

$P(2,n)\sim 2\left( {\begin{array}{*{20}{c}} {{{2}^{n}} - 1} \\ n \end{array}} \right),\quad n \to \infty .$

СУПЕРМОДУЛЯРНАЯ ФУНКЦИЯ ${{{\mathbf{\eta }}}^{ \star }}$ И ЕЕ СВОЙСТВА

Центральный пучок гиперплоскостей ${{H}^{ \bot }}$ с множеством нормальных векторов H = {w1, ... ..., ${{w}_{{\bar {T}}}}{\text{\} }} \in {{{\mathbf{R}}}^{{n + 1}}}{\backslash }0$ здесь рассматривается как подмножество 〈H〉 $\mathop = \limits^{{\text{def}}} $ $\left\{ {\left\langle {{{w}_{1}}} \right\rangle , \ldots ,\left\langle {{{w}_{T}}} \right\rangle } \right\} \subset {\mathbf{R}}{{{\mathbf{P}}}^{n}}$ n-мерного проективного пространства. На множестве конечных подмножеств RPn определим функцию $\eta _{n}^{ \star }{\text{:}}\;2_{{fin}}^{{\mathop {{\mathbf{RP}}}\nolimits^n }} \to {{\mathbb{Z}}_{{ \geqslant 0}}}$ по формуле

$\eta _{n}^{ \star }\left( {\left\langle H \right\rangle } \right) = {\text{rank}}{{H}_{{n - 1}}}({{K}^{H}};{\mathbf{R}}),\quad \left\langle H \right\rangle \subset {\mathbf{R}}{{{\mathbf{P}}}^{n}},$
где по определению симплексами симплициального комплекса KH на вершинах, совпадающих с множеством 〈H〉, являются все подмножества $\left\{ {\left\langle {{{w}_{{{{i}_{1}}}}}} \right\rangle ,\; \ldots ,\;\left\langle {{{w}_{{{{i}_{s}}}}}} \right\rangle } \right\}$ в 〈H〉 такие, что

${\text{span}}\left\langle {{{w}_{{{{i}_{1}}}}},\; \ldots ,\;{{w}_{{{{i}_{s}}}}}} \right\rangle \ne {\text{span}}\left\langle {{{w}_{1}},\; \ldots ,\;{{w}_{T}}} \right\rangle .$

Опираясь на результаты работы [15], можно показать, что $\eta _{n}^{ \star }$ супермодулярна и

(2)
$P(2,n) = C\left( {\left\langle {{{E}_{n}}} \right\rangle } \right) \geqslant 2\eta _{n}^{ \star }\left( {\left\langle {{{E}_{n}}} \right\rangle } \right).$

Для любого конечного $\left\langle H \right\rangle \subset {\mathbf{R}}{{{\mathbf{P}}}^{n}}$ и $\left\langle w \right\rangle \in {\mathbf{R}}{{{\mathbf{P}}}^{n}}$ введем обозначение

$\mathop {\left( {\begin{array}{*{20}{c}} {\left\langle H \right\rangle } \\ {\eta _{n}^{ \star }} \end{array}} \right)}\nolimits^{\langle w\rangle } \mathop = \limits^{{\text{def}}} \sum {\eta _{n}^{ \star }\left( {\left\{ {\left\langle w \right\rangle ,\left\langle {{{w}_{{{{i}_{1}}}}}} \right\rangle , \ldots ,\left\langle {{{w}_{{{{i}_{n}}}}}} \right\rangle } \right\}} \right)} ,$
где суммирование ведется по всем подмножествам $\left\{ {\left\langle {{{w}_{{{{i}_{1}}}}}} \right\rangle ,\; \ldots ,\;\left\langle {{{w}_{{{{i}_{n}}}}}} \right\rangle } \right\} \subset \left\langle H \right\rangle $.

Теорема 3. Для любых n ≥ 1, конечного подмножества $\left\langle H \right\rangle \subset {\mathbf{R}}{{{\mathbf{P}}}^{n}}$ и $\left\langle w \right\rangle \in {\mathbf{R}}{{{\mathbf{P}}}^{n}}$ выполнено неравенство

$\eta _{n}^{ \star }\left( {\left\langle H \right\rangle \cup \left\{ {\left\langle w \right\rangle } \right\}} \right) \leqslant \mathop {\left( {\begin{array}{*{20}{c}} {\left\langle H \right\rangle } \\ {\eta _{n}^{ \star }} \end{array}} \right)}\nolimits^{\left\langle w \right\rangle } .$

Пусть ${{\left\langle H \right\rangle }^{{ \bot w}}}\mathop = \limits^{{\text{def}}} P_{{{{R}^{{n + 1}}}}}^{{\left\langle w \right\rangle }}\left( {\left\langle H \right\rangle } \right),$ где $P_{{{{R}^{{n + 1}}}}}^{{\left\langle w \right\rangle }}$ – ортогональный проектор вдоль линейного подпространства $\left\langle w \right\rangle \subset {{{\mathbf{R}}}^{{n + 1}}}$.

Теорема 4. Для любых $n \geqslant 1$, конечного подмножества $\left\langle H \right\rangle \subset {\mathbf{R}}{{{\mathbf{P}}}^{n}}$, $\langle u\rangle \, \in \,{\mathbf{R}}{{{\mathbf{P}}}^{n}}{\backslash }\langle H\rangle ,\,\,\,\langle u\rangle \, \in \,{\text{span}}\,\langle H\rangle $ существует множество второй категории Бэра $L_{n}^{c}(\langle u\rangle $; $\langle H\rangle ) \subset {{{\mathbf{R}}}^{{n + 1}}}$ такое, что для любого ${v} \in L_{n}^{c}\left( {\left\langle u \right\rangle ;\left\langle H \right\rangle } \right)$ выполнено неравенство

$\eta _{n}^{ \star }\left( {\left\langle H \right\rangle \cup \left\{ {\left\langle u \right\rangle ,\left\langle {v} \right\rangle } \right\}} \right) \geqslant \mathop {\left( {\begin{array}{*{20}{c}} {{{{\left\langle H \right\rangle }}^{{ \bot u}}}} \\ {\eta _{n}^{ \star }} \end{array}} \right)}\nolimits^{\left\langle {v} \right\rangle } .$

Пусть ${{\left\langle H \right\rangle }^{{ \times s}}}$, $s = 1,2,\; \ldots ,\;T$, обозначает множество упорядоченных наборов $\left( {\left\langle {{{w}_{{{{i}_{1}}}}}} \right\rangle ,\; \ldots ,\;\left\langle {{{w}_{{{{i}_{s}}}}}} \right\rangle } \right)$ различных s элементов из 〈H〉 и пусть

$\begin{gathered} \left\langle H \right\rangle _{{ \ne 0}}^{{ \times s}}\mathop = \limits^{{\text{def}}} \left\{ {\left( {\left\langle {{{w}_{{{{i}_{1}}}}}} \right\rangle ,\; \ldots ,\;\left\langle {{{w}_{{{{i}_{s}}}}}} \right\rangle } \right)} \right. \in {{\left\langle H \right\rangle }^{{ \times s}}}| \\ {\text{dim}}\;{\text{span}}\left. {\left\langle {{{w}_{{{{i}_{1}}}}},\; \ldots ,\;{{w}_{{{{i}_{s}}}}}} \right\rangle = s} \right\}. \\ \end{gathered} $

Для любого $W = \left( {\left\langle {{{w}_{{{{i}_{1}}}}}} \right\rangle ,\; \ldots ,\;\left\langle {{{w}_{{{{i}_{n}}}}}} \right\rangle } \right) \in \left\langle H \right\rangle _{{ \ne 0}}^{{ \times n}}$ положим $q_{l}^{W}$ $\mathop = \limits^{{\text{def}}} $ $\left| {{{L}_{l}}(W) \cap \left\langle H \right\rangle } \right|$ $\mathop = \limits^{{\text{def}}} $ $\left| {{\text{span}}\left\langle {\left\langle {{{w}_{{{{i}_{{n - l + 1}}}}}}} \right\rangle , \ldots ,\left\langle {{{w}_{{{{i}_{n}}}}}} \right\rangle } \right\rangle \cap \left\langle H \right\rangle } \right|$ и назовем набор $W(\left\langle H \right\rangle )\mathop = \limits^{{\text{def}}} (q_{n}^{W},q_{{n - 1}}^{W}, \ldots ,q_{1}^{W})$ комбинаторным флагом W на $\left\langle H \right\rangle \subset {\mathbf{R}}{{{\mathbf{P}}}^{n}}$.

Теорема 5. Для любых действительных чисел $p = ({{p}_{1}}, \ldots ,{{p}_{T}})$ таких, что $\sum\limits_{i = 1}^T {{{p}_{i}} = 1} $, выполнено равенство

$\eta _{n}^{ \star }\left( {\left\langle H \right\rangle } \right) = \sum\limits_{W \in \langle H\rangle _{{ \ne 0}}^{{ \times n}}} {\frac{{1 - {{p}_{{{{i}_{1}}}}} - {{p}_{{{{i}_{2}}}}} - \cdots - {{p}_{{{{i}_{{q_{n}^{W}}}}}}}}}{{W[H]}}} .$

Здесь $W[H]\mathop = \limits^{{\text{def}}} q_{n}^{W} \cdot q_{{n - 1}}^{W}\; \cdots \;q_{1}^{W}$ и в числителе вычитаются числа, приписанные элементам из множества ${{L}_{n}}(W) \cap \left\langle H \right\rangle = \left\{ {\left\langle {{{w}_{{{{i}_{1}}}}}} \right\rangle , \ldots ,\left\langle {{{w}_{{{{i}_{n}}}}}} \right\rangle , \ldots ,\langle {{w}_{{{{i}_{{q_{n}^{W}}}}}}}\rangle } \right\}$.

Теоремы 1 и 2 выводятся из теорем 3–5 и неравенств (1), (2).

Список литературы

  1. Schläfli L. Gesammelte Mathematische Abhandlungen I. Verlag Birkhäuser. Springer Basel AG, 1950. P. 209–212.

  2. Cover T.M. Geometrical and Statistical Properties of Systems of Linear Inequalities with Applications in Pattern Recognition // IEEE Transactions on Electronic Computers. 1965. V. 14. Issue 3. P. 326–334. https://doi.org/10.1109/PGEC.1965.264137

  3. Muroga S. Lower Bounds of the Number of Threshold Functions and a Maximum Weight // IEEE Transactions on Electronic Computers. 1965. V. EC-14. Issue 2. P. 136–148. https://doi.org/10.1109/PGEC.1965.263958

  4. Yajima S., Ibaraki T. A Lower Bound of the Number of Threshold Functions // IEEE Transactions on Electronic Computers. 1965. V. 14. Issue 6. P. 926–929. https://doi.org/10.1109/PGEC.1965.264090

  5. Зуев Ю.А. Асимптотика логарифма числа пороговых функций алгебры логики // ДАН. 1989. Т. 306. № 3. С. 528–530. Zbl 0693.94010

  6. Odlyzko A.M. On Subspaces Spanned by Random Selection of ±1 Vectors // J. Combin. Theory Ser. A. 1988. V. 47. P. 124–133. https://doi.org/10.1016/0097-3165(88)90046-5

  7. Zaslavsky T. Facing up to Arrangements: Face-Count Formulas for Partitions of Space by Hyperplanes. Mem. Amer. Math. Soc., 154, Amer. Math. Soc., Providence (RI), 1975.

  8. Ирматов А.А. О числе пороговых функций // Дискрет. матем. 1993. Т. 5. № 3. С. 40–43. http://www.mathnet.ru/links/9c56ab1fba763b5ff56f7f8b82d6172b/dm689.pdf

  9. Komlós J. On the Determinant of (0,1) Matrices // Studia Sci. Math. Hungar. 1967. V. 2. P. 7–21. MR0221962

  10. Komlós J. Manuscript (1977) / In: B. Bollobás (Ed.) “Random Graphs”. N.Y.; L.: Academic Press, 1985. P. 347–350.

  11. Kahn J., Komlós J., Szemerédi E. On the Probability That a Random ±1-Matrix is Singular // J. Amer. Math. Soc. 1995. V. 8. № 1. P. 223–240. https://doi.org/10.1090/S0894-0347-1995-1260107-2

  12. Tao T., Vu V. On the Singularity of Random Bernoulli Matrices // J. Amer. Math. Soc. 2007. V. 20. № 3. P. 603–628. https://doi.org/10.1090/S0894-0347-07-00555-3

  13. Bourgain J., Vu V.H., Wood P.M. On the Singularity Probability of Discrete Random Matrices // J. Functional Analysis. 2010. V. 258. P. 559–663. https://doi.org/10.1016/j.jfa.2009.04.016

  14. Tikhomirov K. Singularity of Random Bernoulli Matrices // Annals of Math. 2020. V. 191. № 2. P. 593–634. https://doi.org/10.4007/annals.2020.191.2.6

  15. Irmatov A.A. Arrangement of Hyperplanes and the Number of Threshold Functions // Acta Applicandae Mathematicae. 2001. V. 68. P. 211–226. https://doi.org/10.1023/A:1012087813557

Дополнительные материалы отсутствуют.

Инструменты

следующая статья выпуска предыдущая статья выпуска содержание выпуска

Доклады Российской академии наук. Математика, информатика, процессы управления

Архивы выпусков Информация о журнале Отправить рукопись в журнал