| Известия Российской академии наук. Серия математическая |
|
|
|
|
|
Веса точных пороговых функций Л. Бабаиa, К. А. Хансенb, В. В. Подольскийcd, Сяомин Сюнe a University of Chicago, USA b University of Aarhus, Denmark c Математический институт им. В. А. Стеклова Российской академии наук, г. Москва d Национальный исследовательский университет "Высшая школа экономики", г. Москва e Institute of Computing Technology, Chinese Academy of Sciences, China
Англоязычная версия:
Izvestiya: Mathematics, 2021, Volume 85, Issue 6, Pages DOI: https://doi.org/10.1070/IM9113 
Реферативные базы данных:
     § 1. ВведениеЛинейная точная пороговая функция – это булева функция, которая говорит, выполняется ли линейное уравнение над действительными числами от ее булевых переменных. Близкий класс линейных пороговых функций состоит из функций, которые говорят, выполняются ли линейные неравенства над действительными числами от их булевых переменных. Более точно, (линейной) точной пороговой функцией от $n$ булевых переменных $x_1,\dots,x_n$ называется булева функция, которая истинна тогда и только тогда, когда верно $w_1x_1 + \dots + w_nx_n = t$, где $w_1,\dots,w_n$ – действительные веса, а $t$ – действительный порог. Пороговой функцией от $n$ булевых переменных $x_1,\dots,x_n$ называется булева функция, которая истинна тогда и только тогда, когда верно $w_1x_1 + \dots + w_nx_n \geqslant t$. Пороговые функции активно исследовались во многих разделах computer science (см., например, [21], [24], [23]). Точным пороговым функциям уделялось меньше внимания, но они рассматривались в теории сложности булевых схем [6], [14], [16]–[18] и в структурной теории сложности [1]. Мы полагаем, что исследование точных пороговых функций как таковых – естественное и интересное направление. Однако важной причиной такого исследования является то, что оно может дополнительно помочь в исследованиях пороговых функций. Для результатов работ [6], [14], [16], [17], доказанных для точных пороговых функций, в настоящий момент неизвестно, выполняются ли они также для пороговых функций. Давний открытый вопрос для пороговых функций – доказать сильные нижние оценки для схем глубины два (при этом такие нижние оценки известны для случая, когда коэффициенты пороговых функций полиномиальны на любом из двух уровней схемы [15], [13]). Работа [18] показывает, что классы схем, определяемые с помощью точных пороговых функций, тесно переплетаются с обычной иерархией пороговых схем. В частности, доказано, что класс точных пороговых схем глубины два является подклассом класса пороговых схем глубины два. Для этого класса также неизвестно сильных нижних оценок. Некоторые недавние результаты используют связь пороговых схем и точных пороговых схем для исследования первых [19], [29], [8], [28]. Понятие точных пороговых функций, равно как и понятие пороговых функций, естественным образом обобщается на многочлены большей степени. Полиномиальной точной пороговой функцией степени $d$ называется булева функция, которая истинна тогда и только тогда, когда верно, что действительный многочлен степени $d$ обнуляется при подстановке в него булевых переменных функции. Полиномиальные пороговые функции определяются как аналогичное обобщение пороговых функций. В этой работе нас интересуют точные пороговые функции с фундаментальной точки зрения реализации булевых функций. Более точно, нас интересует величина (абсолютное значение) целых весов, необходимых для реализации всех возможных точных пороговых функций. Нетрудно увидеть, что без ограничения общности можно предполагать, что действительные веса и пороги, задающие булевы функции, являются целыми (это также верно и для пороговых функций), что делает постановку вопроса корректной. Аналогичный вопрос о величине весов, необходимых для реализации пороговых функций, изучается достаточно давно. Верхняя оценка величины целых весов, достаточных для реализации всех пороговых функций была получена Мурогой, Тодой и Такасой [22] (см. также [23]). Они показали, что весов величины $\leqslant {(n+1)^{(n+1)/2}/2^n}$ достаточно. Также было известно несколько примеров явных функций, для которых необходимы веса величины $2^{\Omega(n)}$ [23], [24]. Существование таких функций также можно доказать мощностным методом, поскольку существует не меньше $2^{n(n-1)/2}$ пороговых функций от $n$ переменных [31], [27]. Близкая к точной нижняя оценка была получена Хостадом [20]. Пусть $n$ – степень двойки. Хостад построил пороговую функцию, для которой необходимы целые коэффициенты величины не меньше $(1/n)e^{-4 n^\beta} n^{n/2}/2^n$, где $\beta = \log(3/2)$. Таким образом, для случая, когда $n$ является степенью 2, известная верхняя оценка и эта нижняя оценка различаются лишь субэкспоненциальным множителем. Как обобщение этой работы, в [26] для произвольной константы $d$ была построена полиномиальная пороговая функция степени $d$, для которой необходимы целые веса величины $n^{\Omega(n^d)}$, где константа в экспоненте зависит от $d$. Аналогичная верхняя оценка $n^{O(n^d)}$ является несложным наблюдением (вновь, константа в экспоненте зависит от $d$). Алон и Ву [3], основываясь на технике Хостада, предложили новую конструкцию плохо обусловленных матриц. Для невырожденной матрицы $A$ размера $n \times n$, положим $B=A^{-1}=(b_{ij})$ и определим $\chi(A)=\max_{i,j} |b_{ij}|$. Далее, положим $\chi_1(n)$ равным максимуму $\chi(A)$ по всем невырожденным $(0,1)$ матрицам $A$ размера $n \times n$. Положим $\chi_2(n)$ равным аналогичной величине для $(-1,1)$ матриц. В терминах этих определений, Алон и Ву предъявили для всякого $n$ явную $(0,1)$ матрицу $A_1$ размера $n \times n$ и явную $(-1,1)$ матрицу $A_2$ размера $n \times n$ такие, что $\chi(A_i) \geqslant n^{n/2}/2^{n(2-o(1))}$ для $i=1,2$. Если $n$ является степенью двойки, эти оценки улучшаются до $n^{n/2}/2^{n(1-o(1))}$. Верхние оценки для $\chi_i(n)$ выводятся из неравенства Адамара. Алону и Ву удалось применить свою конструкцию плохо обусловленных матриц к различным вопросам о плоских симплексах, весах пороговых функций, задачах о взвешиваниях и неразложимых гиперграфах. В частности, они построили пороговую функцию от $n$ переменных, для которой необходимы целые веса величины не меньше $n^{n/2}/2^{n(2-o(1))}$. Обозначим через $\operatorname{maxw}^T(n)$ минимальное $W$ такое, что всякая пороговая функция от $n$ переменных может быть реализована с использованием целых весов абсолютной величины $\leqslant W$. Описанные выше результаты дают следующую теорему. Теперь мы готовы сформулировать наш первый результат. Определим величину $\operatorname{maxw}^E(n)$ для точных пороговых функций аналогично величине $\operatorname{maxw}^T(n)$. Для этой величины мы получаем следующие верхнюю и нижнюю оценки. Как видно из теорем 1–3, величины $\chi_i(n)$, $\operatorname{maxw}^T(n)$ и $\operatorname{maxw}^E(n)$ очень близки и в действительности равны с точностью до экспоненциальных множителей. Более того, для $n$ равных степени двойки, оценки для $\chi_i(n)$ и $\operatorname{maxw}^T(n)$ отличаются лишь субэкспоненциальными множителями. Мы не знаем, выполняется ли это также для $\operatorname{maxw}^E(n)$. Хотя некоторые из наших методов связаны с методами, использовавшимися для изучения пороговых функций, мы не знаем явных соотношений между величинами $\operatorname{maxw}^T(n)$ и $\operatorname{maxw}^E(n)$. Доказательства теоремы 2 и теоремы 3 в действительности показывают, что
$$
\begin{equation*}
\chi_2(n) \leqslant \operatorname{maxw}^T(n)\quad\text{и}\quad \chi_1(n-1) \leqslant \operatorname{maxw}^E(n),
\end{equation*}
\notag
$$
однако мы не знаем, можно ли преобразовать пороговую функцию, требующую весов определенной величины, в точную пороговую функцию, требующую весов близкой величины, или наоборот. Свойство, которое отличает (линейные) точные пороговые функции, это то, что мы можем говорить о размерности таких функций. Для данной точной пороговой функции $f$, заданной линейным уравнением $w_1x_1 + \dots + w_nx_n\,{=}\,t$, рассмотрим действительное аффинное пространство $V$, порожденное теми точками булева куба, для которых условие выполняется. Мы теперь можем определить размерность $f$ как размерность $V$. Обозначим через $\operatorname{maxw}^E(n,k)$ минимальное $W$ такое, что всякая точная пороговая функция размерности $k$ от $n$ булевых переменных может быть реализована с использованием целых весов величины $\leqslant W$. Наш второй результат дает следующее для этой величины. Для полиномиальных точных пороговых функций обозначим через $\operatorname{maxw}^E_d(n)$ величину весов, необходимых для реализации всех возможных точных полиномиальных пороговых функций степени $d$ от $n$ переменных. Последним нашим результатом является следующее обобщение оценок для линейного случая. Этот результат аналогичен известным результатам для пороговых функций, см. [26]. Из этой работы напрямую вытекают оценки
$$
\begin{equation*}
\biggl(\frac{n}{d}\biggr)^{(1/2)(n/(2d))^d - o((n/d)^d)} \leqslant \operatorname{maxw}^T_d(n) \leqslant \frac{n^{n^d/2}}{2^{n^d}}.
\end{equation*}
\notag
$$
Для нижней оценки в теореме 5 мы доказываем некоторое специальное обобщение теоремы 1. 1.1. Связанные работыВскоре после публикации предварительной версии данной работы наша верхняя оценка в теореме 4 была улучшена в [9] до $O(k^{O(k^2)}n^k)$. Для постоянных $k$ эта оценка по существу точна. Оставшаяся часть работа устроена следующим образом. В § 2 мы даем точные определения используемых нами понятий и приводим некоторые простые наблюдения. В п. 3.1 мы приводим пример точной пороговой функции, для которой элементарными рассуждениями доказываем, что для ее реализации требуются веса экспоненциальной величины. Мы доказываем теорему 3 в п. 3.2. Доказательства верхней и нижней оценок в теореме 4 приводятся в п. 3.3 и п. 3.4 соответственно. Теорема 5 доказывается в п. 3.5. Мы завершаем работу перечислением открытых вопросов в § 4. § 2. Предварительные сведенияПод булевой функцией $f$ мы подразумеваем функцию $f\colon \{0,1\}^n \to \{0,1\}$. Мы говорим, что булева функция $f$ от $n$ переменных является точной пороговой функцией, если существуют действительные числа $w_1,\dots,w_n$ (веса) и действительное число $t$ (пороговое значение) такие, что $f(x)=1$ тогда и только тогда, когда $\sum_{i=1}^n w_ix_i = t$, для всех $x \in \{0,1\}^n$. Мы говорим, что набор весов $w_1,\dots,w_n$ и порог $t$, равно как и выражение $w_1x_1 + \dots + w_nx_n = t$, являются реализацией функции $f$. Аналогично, булева функция $f$ от $n$ переменных является пороговой функцией, если существуют действительные числа $w_1,\dots,w_n$ и действительное число $t$ такие, что $f(x)=1$ тогда и только тогда, когда $\sum_{i=1}^n w_ix_i \geqslant t$ для всякого $x \in \{0,1\}^n$. Можно заметить, что без ограничения общности мы можем предполагать, что действительные веса, равно как и действительное пороговое значение, на самом деле являются целыми. Часто при рассмотрении пороговых функций вместо булева куба $\{0,1\}^n$, который мы рассматриваем в данной работе, рассматривается булев куб $\{-1,1\}^n$. Это не сказывается на весах точных пороговых и пороговых функций. Пусть $f(x_1,\dots,x_n)$ является такой функцией от переменных $x_1,\dots,x_n \in \{0,1\}$. Тогда, подставляя $(y_i+1)/2$ вместо $x_i$ для всех $i$ и умножая полученное выражение на $2$, мы получаем эквивалентную функцию от переменных $y_1,\dots,y_n \in \{-1,1\}^n$ с точно такими же весами. В обратную сторону, пусть $f(y_1,\dots,y_n)$ является такой функцией от переменных $y_1,\dots,y_n\,{\in}\,\{-1,1\}^n$. Подставим $2x_i\,{-}\,1$ вместо $y_i$ и раскроем скобки. Если новое постоянное слагаемое четно, мы можем поделить выражение на $2$. Если постоянное слагаемое нечетно, в случае пороговых функций мы можем разделить на $2$ и округлить пороговое значение до ближайшего целого. В случае точных пороговых функций, равенство в этом случае никогда не может быть достигнуто, и рассматриваемая функция тривиальна. Тогда мы можем заменить новое постоянное слагаемое на достаточно большое четное число и разделить выражение на $2$. Во всех случаях мы получаем эквивалентное выражение от переменных $x_1,\dots,x_n \in \{0,1\}$ с точно такими же весами. Поскольку в данной работе мы интересуемся только весами точных пороговых функций, мы можем без ограничения общности ограничиться рассмотрением точных пороговых функций $f$, для которых $f(0,\dots,0)=1$. Это можно показать следующим образом. Пусть $f$ является непостоянной точной пороговой функцией, для которой $f(0,\dots,0)=0$, рассмотрим произвольную реализацию $f$. Поскольку $f$ непостоянная, положим $\widehat{x} \in \{0,1\}^n$ таким, что $f(\widehat{x})=1$. Для $\widehat{x}_i=1$ подставим $1-y_i$ вместо $x_i$, а для $\widehat{x}_i=0$ подставим $y_i$ вместо $x_i$. Это дает реализацию новой точной пороговой функции $g$, удовлетворяющей $g(0,\dots,0)=1$. Заметим, что величины весов в этих двух реализациях одинаковы. При сопоставлении булевой функции $f$ множества $f^{-1}(1)$, точная пороговая функция соответствует пересечению гиперплоскости в $\mathbb{R}^n$ с булевым $n$-мерным кубом $\{0,1\}^n$, а в случае бо́льших степеней – пересечению гиперповерхности степени $d$ с тем же кубом. В линейном случае из рассуждений выше мы получаем, что для изучения весов точных пороговых функций мы можем ограничиться рассмотрением аффинных подпространств, являющихся линейными подпространствами в $\mathbb{R}^n$ и порождаемыми векторами в булевом кубе $\{0,1\}^n$. Используя этот факт, мы будем в основном формулировать наши теоремы в терминах векторных пространств. § 3. Веса точных пороговых функций3.1. ПримерИнтересным примером точной пороговой функции является функция равенства (последовательностей). Определим функцию равенства $\mathrm{EQ}$ от $2n$ переменных $x_1,\dots,x_n$ и $y_1,\dots,y_n$, положив $\mathrm{EQ}(x,y)=1$ тогда и только тогда, когда $x_i=y_i$ для всех $i$. Оказывается, что множество весов, реализующих эту точную пороговую функцию в точности соответствует решениям хорошо известной задачи нахождения $n$ положительных целых чисел $a_1<\dots<a_n$ таких, что все суммы вида $\sum_{i\in I}a_i$ различны. Используя это наблюдение, нетрудно показать, что для реализации функции равенства $\mathrm{EQ}$ необходимы веса экспоненциальной величины. Предложение 1. Пусть $\mathrm{EQ}$ реализуется как точная пороговая функция выражением Тогда $t=0$ и $w_i=-w'_i$ для всех $i$. Таким образом, $\mathrm{EQ}$ также реализуется выражением Доказательство. Очевидно, что $t=0$, поскольку $\mathrm{EQ}(0\dots0,0\dots0)=1$. Далее, для данного $i$, положим $x_i=y_i=1$ и $x_j=y_j=0$ для $j \neq i$. Поскольку $\mathrm{EQ}(x,y)=1$, мы также получаем $w_i = -w'_i$.
Теперь при данных $x$ и $y$ положим $x'_i=x_i$ и $y'_i=y_i$, если $w_i>0$, и положим $x'_i=y_i$ и $y'_i=x_i$ иначе. Мы получаем, что Предложение доказано.Таким образом, мы получаем следующее описание реализаций $\mathrm{EQ}$ как точной пороговой функции. Следствие 1. Пусть $\mathrm{EQ}$ реализуется точной пороговой функцией, заданной $\sum_{i=1}^n w_ix_i + \sum_{i=1}^n w'_iy_i = t$. Тогда все суммы вида $\sum_{i \in I} |w_i|$ для $I \subseteq [n]$ различны. В обратную сторону, если $w_1,\dots,w_n$ – положительные действительные числа такие, что все суммы вида $\sum_{i \in I} w_i$ для $I \subseteq [n]$ различны, то $\sum_{i=1}^n w_i(x_i-y_i)=0$ задает $\mathrm{EQ}$. Таким образом, задача определения величины целых весов, необходимых для реализации функции $\mathrm{EQ}$ от $2n$ переменных, – это в точности известная задача о нахождении $n$ положительных целых чисел $a_1<\dots<a_n$ таких, что все суммы вида $\sum_{i\in I}a_i$ различны. Легко видеть, что есть реализация с $a_n \,{\leqslant}\, 2^{n-1}$, а также несложно понять, что необходимо $a_n \geqslant 2^n/n$ (иначе все суммы меньше $2^n$). Эрдёш выдвинул гипотезу, что $a_n \geqslant c2^n$ для некоторой константы $c$, но эта гипотеза остается неразрешенной. Эрдёш и Мозер [12] доказали, что $a_n \geqslant 2^n/(4\sqrt n)$. Конвей и Гай [10] доказали, что $a_n\,{<}\,0.23513\,{\cdot}\,2^n$. С тех пор и нижняя, и верхняя оценки были улучшены, однако только на постоянные множители. Верхняя оценка была усилена Бохманом [7] до $a_n < 0.22002 \cdot 2^n$ для достаточно больших $n$. Нижняя оценка была усилена до
$$
\begin{equation*}
a_n > 2^{-n}\binom{2n}{n} \sim \frac{2^n}{\sqrt{\pi n}}
\end{equation*}
\notag
$$
Элкиесом [11], а затем последовательно усилена асимптотически на множитель $\sqrt{3/2}$ Алиевым и на множитель $\sqrt{2}$ Элкиесом и Глисоном [2]. 3.2. Верхняя и нижняя оценки для линейного случаяПрежде чем доказывать верхнюю оценку, мы сформулируем три леммы. Лемма 1 (Фадеев, Соминский, см. [33]). Пусть $A$ – матрица размера $n \times n$, состоящая из $0$ и $1$. Тогда $|{\det(A)}| \leqslant (n+1)^{(n+1)/2}/2^n$. Для полноты изложения мы приводим доказательство. Доказательство. Следуя Уилльямсону [30], определим матрицу $\widehat{A}$ размера $(n+1)\times(n+1)$, состоящую из $-1$ и $1$, как где $J$ – матрица размера $n\times n$, все ячейки которой равны $1$. Прибавляя первый столбец к остальным столбцам и раскладывая определитель по первой строке, мы получаем Применяя неравенство Адамара к $\widehat{A}$, мы получаем Сочетание этих двух неравенств доказывает лемму. Лемма 2. Пусть $v_1,\dots,v_{n-1} \in \{0,1\}^n$ линейно независимы. Тогда существуют целые числа $w_1,\dots,w_n$ такие, что равенство $w_1x_1 + \dots + w_nx_n\,{=}\,0$ задает линейное подпространство $\operatorname{span}(\{v_1,\dots,v_{n-1}\})$, а также $|w_i| \leqslant n^{n/2}/2^{n-1}$. Доказательство. Пусть $A$ – матрица размера $(n-1) \times n$, строками которой являются вектора $v_1,\dots,v_{n-1}$. Тогда $w$ соответствуют ненулевым решениям линейной системы $Aw = 0$. Пусть $A_i$ – матрица размера $(n-1) \times (n-1)$, полученная из $A$ удалением $i$-го столбца. Тогда решение задается как $w_i = (-1)^{i+1}\det(A_i)$. Поскольку все ячейки матриц $A_i$ равны $0$ или $1$, результат вытекает из леммы 1. Лемма 3. Пусть $V$ – векторное пространство и пусть Доказательство. Пусть $\mathcal W$ – совокупность векторных пространств $W$, удовлетворяющих Из соображений размерности достаточно доказать, что
Рассмотрим произвольный $x \in \{0,1\}^n \setminus V$. Мы построим $W \in \mathcal W$ такое, что $x \notin W$. Из этого вытекает утверждение леммы. Это можно сделать с помощью следующей итеративной процедуры. Для $i=1,\dots,n-1$, поскольку $\{0,1\}^n \subsetneq \operatorname{span}(\{v_1,\dots,v_{i-1},x\})$ мы можем выбрать $v_i \in \{0,1\}^n \setminus \operatorname{span}(\{v_1,\dots,v_{i-1},x\})$, и получить $x \notin \operatorname{span}(\{v_1,\dots,v_i\})$. После этой процедуры просто положим $W=\operatorname{span}(\{v_1,\dots,v_{n-1}\})$. Лемма доказана. Теорема 6. Пусть $V$ – векторное подпространство в $\mathbb{R}^n$. Тогда существуют целые числа $w_1,\dots,w_n$ такие, что для всех $x \in \{0,1\}^n$ верно $x \in V$ тогда и только тогда, когда $w_1x_1 + \dots + w_nx_n = 0$, и более того, выполняется $|w_i| \leqslant n^{n/2+1}$ для всех $i$. Таким образом, всякую точную пороговую функцию $f$ от $n$ переменных можно реализовать с помощью целых весов абсолютной величины не больше $n^{n/2+1}$. Доказательство. Пусть $k=n-\dim(\operatorname{span}(V \cap \{0,1\}^n))$. Тогда по лемме 3 существуют векторные подпространства $V_1,\dots,V_k$ размерности $n-1$, порождаемые векторами из $\{0,1\}^n$ такие, что
$$
\begin{equation*}
V \cap \{0,1\}^n = \biggl(\bigcap_{i=1}^k V_i \biggr) \cap \{0,1\}^n.
\end{equation*}
\notag
$$
Для всякого $V_i$ по лемме 2 существуют целые числа $w_{ij}$ такие, что для всех $x \in \{0,1\}^n$ верно $x \in V_i$ тогда и только тогда, когда выполняется равенство $w_{i1}x_1 + \dots + w_{in}x_n = 0$, и более того, $|w_{ij}| \leqslant n^{n/2}/2^{n-1}$. Доказательство завершается с помощью вероятностного метода.
Для $i=1,\dots,k$ выберем $c_i \in \{-2^{n-1},\dots,2^{n-1}\}$ равновероятно и рассмотрим составное равенство $\sum_{i=1}^k \sum_{j=1}^n c_iw_{ij}x_j = 0$. Ясно, что всякий $x \in V \cap \{0,1\}^n$ удовлетворяет этому равенству, поскольку всякий такой $x$ удовлетворяет отдельным равенствам для всех $i$. Теперь рассмотрим $x \in \{0,1\}^n \setminus V$. Существует $i$ такое, что $x \notin V_i$, и для этого $i$ выбранный $x$ не удовлетворяет соответствующему равенству. Отсюда следует, что выбранные $x$ удовлетворяет составному равенству с вероятностью меньше $2^{-n}$. Поскольку $|\{0,1\}^n \setminus V| \leqslant 2^n$, вероятность того, что существует $x \in \{0,1\}^n \setminus V$, удовлетворяющий составному равенству, меньше $1$, а значит существуют значения $\widehat{c}$ для $c$ с тем же свойством. Следовательно, $w_j = \sum_{i=1}^k \widehat{c_i}w_{ij}$ удовлетворяет условиям теоремы, поскольку для каждого слагаемого $|\widehat{c_i}w_{ij}| \leqslant n^{n/2}$. Теорема доказана. Опираясь на результаты теоремы 1, Циглер [32] доказал нижнюю оценку на величину максимального коэффициента неравенства, задающего грань полноразмерного $(0,1)$ многогранника в $\mathbb{R}^n$. Поскольку многогранник полноразмерный, гиперплоскость, задаваемая гранью, однозначно определяется точками из $\{0,1\}^n$, а значит соответствует единственной точной пороговой функции, и эта нижняя оценка применима также к нашей постановке. Мы приводим эту нижнюю оценку и дополнительно отмечаем, что конструкция доказывает нижнюю оценку на величину всех коэффициентов. Теорема 7. Для всякого $n$ существует точная пороговая функция $f$ от $n$ переменных такая, что для всякой реализации $f$ необходимы целые веса величины $n^{n/2}/2^{n(2-o(1))}$. Доказательство (Циглер). Пусть $A$ – $(0,1)$ матрица размера $(n-1)\times (n-1)$ из теоремы 1. Предположим без ограничения общности, что
$$
\begin{equation*}
\chi(A)=\frac{\det(A_{11})}{\det(A)} \geqslant \frac{n^{n/2}}{2^{n(2-o(1))}}.
\end{equation*}
\notag
$$
Зададим матрицу $\widehat{A}$ размера $(n-1)\times n$ как
$$
\begin{equation*}
\widehat{A} = \begin{bmatrix} A & e_1 \end{bmatrix} .
\end{equation*}
\notag
$$
Как в лемме 2, мы получаем, что веса $w$ для точной пороговой функции, определяемой строками $\widehat{A}$, должны быть решениями линейной системы $\widehat{A}w = 0$. Одно такое решение задается как $w_i = (-1)^{i+1}\det(\widehat{A}_i)$, а все остальные решения отличаются от этого скалярным множителем. Далее, $w_1=\det(A_{11})$ и $w_n=(-1)^{n+1}\det(A)$, а следовательно, $|w_1/w_n| = \chi(A)$. Таким образом, целочисленное решение $\widehat{w}$ должно удовлетворять $|\widehat{w}_1| \geqslant \chi(A)$. Теорема доказана. Наблюдение 1. Алон и Ву доказали, что когда $n-1$ – степень двойки, то обратная матрица к матрице $A$ размера $(n-1)\times(n-1)$, которую они построили, в действительности содержит столбец (а на самом деле, много столбцов), в котором все ячейки имеют величину $n^{n/2}/2^{\Theta(n)}$. Это означает, что в конструкции выше, когда $n-1$ является степенью двойки, можно показать, что все первые $n-1$ коэффициентов имеют такую величину. Другими словами, для всякого $n$, выполняется не только то, что может потребоваться использовать $\Omega(n \log n)$ бит для хранения самого большого веса, но также для хранения всех весов может потребоваться использовать $\Omega(n^2\log n)$ бит. 3.3. Верхняя оценка для маленькой размерностиТеорема 8. Пусть $V$ – векторное подпространство в $\mathbb{R}^n$ и пусть $k = \dim(\operatorname{span}(V \cap \{0,1\}^n))$. Тогда существуют целые числа $w_1,\dots,w_n$ такие, что для всех $x \in \{0,1\}^n$ верно $x \in V$ тогда и только тогда, когда $w_1x_1 + \dots + w_nx_n\,{=}\,0$, и более того, выполняется $|w_i| \leqslant n^{2^k}$ для всех $i$. Таким образом, всякую точную пороговую функцию $f$ от $n$ переменных размерности не больше $k$ можно реализовать с помощью целых весов с абсолютным значением не больше $n^{2^k}$. Доказательство. Пусть $v_1,\dots,v_k \in \{0,1\}^n$ – базис $\operatorname{span}(V \cap \{0,1\}^n)$. Для $\alpha \in \{0,1\}^k$ определим множество $S_\alpha = \{ i \in \{1,\dots,n\} \mid \forall\, j \in \{1,\dots,k\} \colon (v_j)_i = \alpha_j\}$. Пронумеруем непустые такие множества: $S_1,\dots,S_K$ для $K \leqslant 2^k$. Для $i \in \{1,\dots,K\}$ положим $n_i = |S_i|$ и предположим $S_i = \{a_{i1},\dots,a_{i n_i}\}$. Далее, определим $\chi_i \in \{0,1\}^n$ как характеристические векторы множества $S_i$.
Рассмотрим векторное подпространство $W$ в $\mathbb{R}^K$, определяемое следующим образом: $y \in W$ тогда и только тогда, когда $\sum_{i=1}^K y_i \chi_i \in V$. Заметим, что если $\sum_{i=1}^K y_i \chi_i \in \{0,1\}^n$, то по построению выполняется $y \in \{0,1\}^K$. По теореме 6 существуют целые веса $\widehat{w}_1,\dots,\widehat{w}_K$ такие, что для всех $y \in \{0,1\}^K$ верно $y \in W$ тогда и только тогда, когда $\widehat{w}_1y_1 + \dots + \widehat{w}_Ky_K = 0$, и более того выполняется $|\widehat{w}_i| \leqslant K^{K/2+1}$. Таким образом, мы также получаем, что для всех $y \in \{0,1\}^K$ выполняется $\sum_{i=1}^K y_i \chi_i \in V$ тогда и только тогда, когда $\widehat{w}_1y_1 + \dots + \widehat{w}_Ky_K = 0$. Теперь мы определяем целые веса $w_1,\dots,w_n$ следующим образом. Положим $N=\prod_{l=1}^K n_l$. Если $n_i=1$, мы просто определяем $w_{a_{i1}}= N\widehat{w}_i$. Иначе мы полагаем первому элементу каждого множества $S_i$ вес $w_{a_{i1}} = -(n_i-1)\prod_{l=1}^{i-1}n_l + N\widehat{w}_i$, а остальным элементам – вес $w_{a_{ij}} = \prod_{l=1}^{i-1}n_l$, для $j=2,\dots,n_i$. По построению мы получаем такое свойство, что если $w_1x_1 + \dots + w_nx_n = 0$ для $x \in \{0,1\}^n$, то обязательно для всех $i$ все координаты $x_{a_{ij}}$ имеют одинаковые значения, $0$ или $1$. Таким образом, $x$ должен быть вида $\sum_{i=1}^K y_i \chi_i \in W$ для $y \in \{0,1\}^K$. Обратное, очевидно, также выполняется. Наконец, заметим, что для всех $i$ верно Теорема доказана.3.4. Нижняя оценка для маленькой размерностиПусть $k\leqslant n/2$, положим $d=\lfloor n/k\rfloor$ и зададим $k$-мерное векторное пространство $V$ как
$$
\begin{equation*}
V=\operatorname{span}\{\overbrace{1\dots 1}^d\overbrace{0\dots 0}^{n-d}\, ,\, \overbrace{0\dots 0}^d\overbrace{1\dots 1}^d\overbrace{0\dots 0}^{n-2d} \, ,\, \dots,\, \overbrace{0\dots 0}^{(k-1)d}\overbrace{1\dots 1}^d\overbrace{0\dots 0}^{n-kd}\}.
\end{equation*}
\notag
$$
Теорема 9. Пусть $w_1,\dots,w_n$ – целые числа, для которых выполняется $x\in V$ тогда и только тогда, когда $\sum_{i=1}^{n} w_i x_i=0$, для всех $x\in \{0,1\}^n$. Тогда выполняется Таким образом, существует точная пороговая функция от $n$ переменных размерности $k$, для которой необходимы целые веса с абсолютным значением не меньше $(d^k-1)/2k$. Доказательство. Во-первых, перенумеруем веса $w_1,\dots,w_{kd}$ как $w_{1,1},\dots, w_{1,d}$; $w_{2,1},\dots,w_{2,d}$; $\dots$; $w_{k,1},\dots,w_{k,d}$, где $w_{i,j}=w_{(i-1)d+j}$ ($i\in [k]$, $j\in [d]$). Для всякого $i\in [k]$ определим (мульти)-множество $S_i$ как $S_i=\{w_{i,1}, w_{i,2},\dots, w_{i,d}\}$. Для (мульти)-множества $S\subset \mathbf{Z}$ определим $\operatorname{sum}(S)=\sum_{y\in S}y$. По предположению и по определению $V$ выполняется $\operatorname{sum}(S_i)=0$ для всех $i$. Мы утверждаем, что если $\max_{i}|w_i|<(d^k-1)/(2k)$, то существуют подмножества $\widetilde{S}_i\subseteq S_i$ для всякого $i\in [k]$ такие, что $\sum_{i=1}^{k}\operatorname{sum}(\widetilde{S}_i)=0$, и хотя бы одно $\widetilde{S}_i$ удовлетворяет $\widetilde{S}_i\neq \varnothing$ и $\widetilde{S}_i\neq S_i$. Другими словами, в этом случае существовал бы $x\in \{0,1\}^n$, удовлетворяющий $\sum_{i=1}^n w_i x_i = 0$ и $x\notin V$, что приводит к противоречию. Следовательно, мы можем заключить, что $\max_{i}|w_i|\geqslant (d^k-1)/(2k)$. Далее мы доказываем указанное утверждение, тем самым завершая доказательство теоремы.
Пусть $M=\max_{i}|w_i|$. По предположению выполняется $M<(d^k-1)/(2k)$. Поскольку $\operatorname{sum}(S_i)=0$, т. е. $w_{i,1}+w_{i,2}+\dots+w_{i,d}=0$, мы можем переставить $\{w_{i,1},\dots, w_{i,d}\}$ в порядке $\{\widetilde{w}_{i,1},\dots, \widetilde{w}_{i,d}\}$, так что (1) $\widetilde{w}_{i,1}\geqslant 0$; (2) для всякого $2\leqslant j\leqslant d$, если $\sum_{l=1}^{j-1}\widetilde{w}_{i,l}\geqslant 0$, то $\widetilde{w}_{i,j}\leqslant 0$, иначе $\widetilde{w}_{i,j}>0$. Легко видеть, что для всех $i\in [k]$, $j\in [d]$ выполняется $-M\leqslant \widetilde{w}_{i,1}+\widetilde{w}_{i,2}+\dots+\widetilde{w}_{i,j}\leqslant M$. Далее, для каждого $k$-набора $(l_1,\dots,l_k)\in [d]^{k}$ рассмотрим двойную сумму $\sum_{i=1}^{k}\sum_{j=1}^{l_i}\widetilde{w}_{i,j}$. Согласно предыдущему неравенству выполняется
$$
\begin{equation*}
-kM\leqslant \sum_{i=1}^{k}\sum_{j=1}^{l_i}\widetilde{w}_{i,j}\leqslant kM.
\end{equation*}
\notag
$$
Но в совокупности есть всего $d^k$ различных $k$-наборов $(l_1,\dots,l_k)$ и $2kM+1<2k\cdot (d^k-1)/(2k)+1=d^k$. Следовательно, существуют два $k$-набора $(l_1,\dots,l_k)\neq (l'_1,\dots,l'_k)$ таких, что $\sum_{i=1}^{k}\sum_{j=1}^{l_i}\widetilde{w}_{i,j} =\sum_{i=1}^{k}\sum_{j=1}^{l'_i}\widetilde{w}_{i,j}$.
Для всякого $i\,{\in}\,[k]$ определим множество $\widetilde{S}_i$ следующим образом. Если $l_i\,{\geqslant}\, l'_i$, положим $\widetilde{S}_i=\{\widetilde{w}_{i,l'_i+1},\dots,\widetilde{w}_{i,l_i}\}$. Иначе, положим $\widetilde{S}_i=S_i\setminus \{\widetilde{w}_{i,l_i+1},\dots,\widetilde{w}_{i,l'_i}\}$. Комбинируя предыдущее равенство с тем фактом, что $\operatorname{sum}(S_i)=0$, мы получаем $\sum_{i=1}^{k}\operatorname{sum}(\widetilde{S}_i)=0$. Ясно, что $\widetilde{S_i}\neq S_i$ для всех $i$, и поскольку $(l_1,\dots,l_k)\neq (l'_1,\dots,l'_k)$, должно существовать $i$ такое, что $\widetilde{S}_i\neq \varnothing$. Теорема доказана. 3.5. Оценки для бо́льших степенейВерхняя оценка для полиномиальных точных пороговых функций в теореме 5 легко следует из верхней оценки для линейного случая. Действительно, рассмотрим полиномиальную точную пороговую функцию степени $d$ от $n$ переменных. Пусть $p(x)$ – соответствующий целочисленный многочлен степени $d$. Заменим каждый моном новой переменной $u_{i}$. В многочлене $p$ не больше $n^d$ мономов (поскольку он предполагается мультилинейным), так что нам потребуется не больше $n^d$ новых переменных $u = (u_1,\dots,u_{n^d})$. Таким образом, мы получили линейный многочлен от переменных $u_i$. Обозначим этот многочлен через $q(u)$ и рассмотрим соответствующую $q$ линейную точную пороговую функцию. По теореме 6 мы получаем линейный многочлен $q'(u)$, соответствующий этой функции с целыми весами с абсолютными значениями не больше $(n^d)^{n^d/2+1}=n^{dn^d/2+d}$. Теперь мы можем просто подставить обратно в многочлен $q'(u)$ вместо всех переменных $u_i$ соответствующие мономы от переменных $x_i$. Мы получаем многочлен $p'(x)$ с целыми весами с абсолютными значениями не больше $n^{dn^d/2+d}$, соответствующий точной пороговой функции $f(x)$. Что касается нижней оценки, рассуждение следует тому же плану, что для случая степени $1$. Мы начнем с некоторого специального обобщения нижней оценки Алона и Ву на $\chi(A)$ [3]. Его можно получить переносом анализа из [26] в матричную терминологию аналогично тому, как Алон и Ву перенесли анализ из результата Хостада [20]. Но вместо этого мы предпочитаем привести технически более простое доказательство в матричных терминах, основанное на результатах [3]. Однако отметим, что хотя это доказательство и отличается от доказательства в [26], в его основе лежат те же идеи. Ниже мы используем параметры $n$ и $d$, где $d$ обозначает степень многочлена, а $nd$ равно числу переменных. Мы обозначаем входные переменные через $x_{ij}$ для $i = 1, \dots, d$, $j = 1, \dots, n$ и предполагаем, что они принимают значения в $\{0,1\}$. Положим $\overline{x}^{\,1} = (x_{1,1},\dots, x_{1,n})$, $\dots$, $\overline{x}^{\,d} = (x_{d,1},\dots, x_{d,n})$. Положим $x = (\overline{x}^{\,1}, \dots, \overline{x}^{\,d})$. Мы обозначаем через $M_d$ множество мономов $\{x_{1,j_1}x_{2,j_2}\cdots x_{d,j_d} \mid j_1,\dots, j_{d} \in \{1,\dots,n\}\}$ (т. е. мы берем ровно одну переменную из каждого $\overline{x}^{\,i}$). Для матрицы $A$ мы обозначаем через $A_{ij}$ ее подматрицу, полученную удалением $i$-й строки и $j$-го столбца. Чтобы сформулировать наше обобщение нам потребуется следующее определение. Определение 1. Матрица $A \in \{0,1\}^{m\times m}$ называется $d$-порождаемой, если можно пометить каждый столбец $A$ уникальным мономом из $M_d$ и пометить каждую строку $A$ набором значений переменных (входом) таким образом, что каждая ячейка $a_{ij}$ равна значению монома, соответствующего столбцу $j$, при подстановке переменных, соответствующих строке $i$. Теперь мы можем привести обобщение нижней оценки Алона и Ву. Теорема 10. Для всякого $d$ и всякого $n$ существует (явная) матрица $A^{(d)} \in \{0,1\}^{n^d \times n^d}$ такая, что $A^{(d)}$ является $d$-порождаемой, и $A^{(d)}$ имеет вид $\left[\begin{smallmatrix} e_1^{T} \\ B \end{smallmatrix}\right]$, где $e_{1}^{T}$ – строка $(1,0,\dots,0)$ длины $n^d$, а $B$ – матрица размера $(n^d-1) \times n^d$. (Заметим, что функция, спрятанная в $o$-обозначении выше зависит от $n$, но не зависит от $d$.) Доказательство ведется индукцией по $d$. Для $d=1$ каждая матрица $A \in \{0,1\}^{n \times n}$ является $1$-порождаемой. Таким образом, если бы у нас не было дополнительного ограничения на первую строку, мы могли бы просто взять в качестве матрицы $A^{(1)}$ матрицу, построенную Алоном и Ву. Чтобы выполнить это последнее ограничение, обозначим через $C \in \{0,1\}^{(n-1) \times (n-1)}$ матрицу, построенную Алоном и Ву, такую, что $\chi(C) = |{\det C_{1,n-1}/\det C}| \geqslant n^{n/2}/2^{2n - o(n)}$, и положим Легко проверить, что $|{\det A^{(1)}_{1,n}/\det A^{(1)}}| = |{\det C_{1,n-1}/\det C}|$.
Теперь предположим, что у нас есть матрица $A^{(d-1)} \in \{0,1\}^{n^{d-1} \times n^{d-1}}$, удовлетворяющая утверждению теоремы. Мы построим матрицу $A^{(d)}\,{\in}\, \{0,1\}^{n^d \times n^d}$. Заметим, что число столбцов совпадает с числом мономов в $M_d$, так что нам потребуются использовать все мономы для меток столбцов. Определим эти метки. Разделим столбцы на $n$ блоков: первый блок состоит из первых $n^{d-1}$ столбцов, второй блок – из следующих $n^{d-1}$ столбцов и так далее. Обозначим через $m_{1}, m_{2}, \dots, m_{n^{d-1}}$ мономы, соответствующие столбцам $A^{(d-1)}$. Пометим столбцы $j$-го блока мономами $m_{1}x_{d,j}, m_{2}x_{d,j}, \dots, m_{n^{d-1}}x_{d,j}$. Для матрицы $A = \{a_{ij}\}_{i,j=1}^n$ обозначим через $\overline{A}$ матрицу, полученную отражением $A$ относительно вертикальной оси, т. е.
$$
\begin{equation*}
\overline{A} = \begin{bmatrix} a_{1,n} & a_{1,n-1} & \dots & a_{1,1} \\ a_{2,n} & a_{2,n-1} & \dots & a_{2,1} \\ \dots & \dots & \dots & \dots \\ a_{n,n} & a_{n,n-1} & \dots & a_{n,1} \end{bmatrix}.
\end{equation*}
\notag
$$
Тогда матрица $A^{(d)}$ определяется как
$$
\begin{equation*}
\left[ \begin{array}{c|c|c|c} { 1\ 0\ \dots\ \fbox{0}} & \hspace{14mm} & \hspace{14mm} & \hspace{14mm} \\ A^{(d-1)} & & & \\ \hline {0\ \dots\ 0\ 1} & \fbox{0} \ \dots\ 0\ 1 & & \\ & \overline{A}^{\,(d-1)} & & \\ \hline & {1\ 0\ \dots\ 0} & 1\ 0\ \dots\ \fbox{0} & \\ & & A^{(d-1)} & \\ \hline & & & \\ & & \ddots & \ddots \\ & & & \\ \end{array} \right].
\end{equation*}
\notag
$$
В диагональных блоках расположены матрицы $A^{(d-1)}, \overline{A}^{\,(d-1)}, A^{(d-1)}, \dots$ . На диаграмме мы выписали первую строку каждого блока отдельно, и мы выделили прямоугольником ячейки, для которых
$$
\begin{equation*}
\biggl|\frac{\det B}{\det A^{(d-1)}}\biggr| \geqslant \frac{n^{n^{d-1}/2}}{2^{2n^{d-1} + o(n^{d-1})}},
\end{equation*}
\notag
$$
где через $B$ мы обозначаем соответствующую подматрицу. В блоках прямо под диагональю ненулевыми являются только первые строки, и эти строки равны $e_n^T$, $e_1^T$, $e_n^T$, $\dots$ . Все остальные блоки состоят только из нулей.
Проверим, что матрица $A^{(d)}$ удовлетворяет всем требуемым свойствам (возможно после перестановки столбцов). Во-первых, первая строка, очевидно, имеет нужный вид. Теперь покажем, что матрица является $d$-порождаемой. Мы уже описали метки столбцов. Теперь пометим строки. Наши строки естественным образом поделены на $n$ блоков и мы пометим каждый блок отдельно. Рассмотрим $k$-ю строку $l$-го блока. Положим значения переменных $x_{ij}$ для $i = 1, \dots, d-1$, $j = 1, \dots, n$ такими же, как для $k$-й строки матрицы $A^{(d-1)}$. Если $k > 1$ или $l = 1$, то положим $x_{dl}=1$ и $x_{dj}=0$ для $j \neq l$. Если $k=1$ и $l>1$, то положим $x_{d,l-1} = x_{d,l}=1$ и $x_{dj}=0$ для $j \neq l-1,l$. Легко видеть, что с такими метками столбцов и строк, каждый элемент матрицы совпадает со значением монома, соответствующего столбцу, на значениях переменных, соответствующих строке. Заметим, что ровно для этого шага нам потребовалось отражать некоторые блоки. Иначе у нас возникли бы проблемы с $d$-порождаемостью из-за первых строк блоков. В следующем доказательстве нам потребуется лемма 2.3.1 из [3]. Мы формулируем ее здесь для полноты изложения. Лемма 4 (Алон и Ву). Пусть $S = \{s_{i,j}\}_{i,j=1}^{n_1}$ и $T = \{t_{i,j}\}_{i,j=1}^{n_2}$ – две матрицы, и пусть Нам остается лишь доказать нижнюю оценку на $|{\det A^{(d)}_{1,n^d}/\det A^{(d)}}|$. Повторяя трюк из леммы 4, мы можем доказать следующее утверждение. Доказательство. Мы доказываем индукцией по $i$, что для главной подматрицы $B^{(i)}$ матрицы $A^{(d)}$, состоящей из первых $i$ блоков строк и столбцов, и для некоторого $j$ верно, что Более того, выполняется $j = i n^{d-1}$ для нечетных $i$ и $j = n^{d-1}(i-1)+1$ для четных $i$. Таким образом, $j$ является номером последнего столбца $B^{(i)}$ для нечетных $i$ и $j$ является номером первого столбца последнего блока $B^{(i)}$ для четных $i$.
База индукции очевидна. Для шага индукции рассмотрим матрицу $B^{(i)}$ и предположим, для определенности, что $i$ четно. Тогда $B^{(i)}$ имеет вид
$$
\begin{equation*}
\left[ \begin{array}{c|c} { 1\ 0\ \dots\ \fbox{0}} & \hspace{14mm} \\ B^{(i-1)} & \\ \hline { 0\ \dots\ 0\ 1} & \fbox{0} \ \dots\ 0\ 1 \\ & \overline{A}^{\,(d-1)} \\ \end{array} \right].
\end{equation*}
\notag
$$
Мы знаем, что
$$
\begin{equation*}
\biggl| \frac{\det B^{(i-1)}_{1,(i-1)n^d}}{\det B^{(i-1)}}\biggr| \geqslant \frac{n^{(1/2)n^{d-1}(i-1)}}{2^{2n^{d-1}(i-1) + o(n^{d-1})(i-1)}}, \qquad \biggl|\frac{\det \overline{A}^{\,(d-1)}_{1,1}}{\det \overline{A}^{\,(d-1)}}\biggr| \geqslant \frac{n^{(1/2)n^{d-1}}}{2^{2n^{d-1} + o(n^{d-1})}}.
\end{equation*}
\notag
$$
Из леммы 4 (примененной после очевидной перестановки столбцов) сразу следует, что одна из ячеек матрицы, обратной к $B^{(i)}$, больше произведения двух величин, указанных выше. Более точно, Утверждение доказано. Таким образом, если в матрице $A^{(d)}$ мы переставим $k$-й столбец и $n^d$-й столбец, мы получим матрицу, требуемую в теореме 10. Теорема доказана. Теперь мы докажем основной результат этого параграфа. Теорема 11. Справедлива оценка $\operatorname{maxw}^E_d(2dn) \geqslant n^{n^d/2}/2^{2n^d + o(n^d) + d}$. Доказательство. Теперь у нас будут переменные $x_{ij}, y_{ij} \in \{0,1\}$ для $i = 1,\dots,d$ и $j = 1, \dots,n$ (т. е. у нас в два раза больше переменных), и мы будем рассматривать целочисленные многочлены $p(x,y)$ степени $d$. В действительности нам будет удобнее рассматривать вместо этого многочлены $q(x-y,x+y)$ (напомним, что $x$ и $y$ – векторы переменных). Нетрудно проверить, что мы всегда можем преобразовать многочлен $p(x,y)$ в эквивалентный многочлен $q(x-y, x+y)$ и наоборот. Более того, если в $q(x-y,x+y)$ есть большой коэффициент, то и в соответствующем многочлене $p(x,y)$ также есть большой коэффициент.
Наблюдение 2. Пусть все коэффициенты целочисленного многочлена $p(x,y)$ степени $d$ имеют абсолютное значение не больше $s$. Пусть $q(u,v) = p((v+u)/2, (v-u)/2)$. Тогда $p(x,y) = q(x-y,x+y)$, и $2^dq(u,v)$ имеет целые коэффициенты с абсолютным значением не больше $2^ds$. Теперь мы построим полиномиальную точную пороговую функцию с требуемыми свойствами. Мы начнем с матрицы $A^{(d)}$, заданной в теореме 10. Во-первых, мы поменяем пометки в матрице: в каждом мономе в метках $A^{(d)}$ мы заменяем каждую переменную $x_{ij}$ на выражение $x_{ij} - y_{ij}$. Таким образом, теперь столбцы соответствуют мономам в переменных $x-y$. Обозначим это новое множество мономов, соответствующих столбцам $A^{(d)}$ через $M_{d}'$. Для завершения размечивания матрицы нам нужно соответствующе поменять метки на строках. Это возможно, поскольку мы можем подобрать значения $x_{ij}$ и $y_{ij}$ так, чтобы старые значения $x_{ij}$ были равны новым значениям $x_{ij}-y_{ij}$. Теперь мы можем продолжить доказательство. Рассмотрим матрицу $B = \begin{bmatrix} A^{(d)} & e_1 \end{bmatrix}$, полученную добавлением одного столбца к матрице $A^{(d)}$. Пусть $z \in \{0,1\}$ – новая переменная, и пусть новый столбец соответствует моному $\theta = (x_{11}-y_{11})(x_{21}-y_{21}) \cdots (x_{d1}-y_{d1}) z$. Нам нужно расширить наборы значений переменных, соответствующие строкам, включив в них значение для $z$. Для первой строки мы полагаем $z=1$, а для остальных строк полагаем $z=0$. Теперь нетрудно видеть, что каждая ячейка $B$ равна значению монома, соответствующего столбцу, на значениях переменных, соответствующих строке. Теперь рассмотрим точную полиномиальную пороговую функцию на множестве мономов $M_{d}' \cup \{\theta\}$ с вектором коэффициентов $w$, равным ненулевому целочисленному решению системы $B w = 0$. Заметим, что размерность пространства решений этой системы равна $1$, поскольку $A^{(d)}$ невырожденная, а значит $w$ определяется однозначно с точностью до мультипликативного множителя. Обозначим этот многочлен через $p(x-y,z)$ и соответствующую точную пороговую функцию – через $f(x,y,z)$. Теперь мы докажем, что всякая целочисленная реализация $w'$ той же точной пороговой функции на множестве всех мономов над переменными $x-y$, $x+y$ и мономе $\theta$ обязана иметь большую координату. Сначала заметим, что такая реализация должна удовлетворять системе
$$
\begin{equation}
\begin{bmatrix} B & B' \end{bmatrix} \begin{pmatrix} u \\ v \end{pmatrix} = 0,
\end{equation}
\tag{3.1}
$$
где столбцы $B'$ соответствуют мономам от переменных $x-y$ и $x+y$, не входящим в $M_{d}'$, и $\left(\begin{smallmatrix} u \\ v\end{smallmatrix}\right)$ равен $w'$, где $u$ соответствует $B$-части и $v$ соответствует $B'$-части. Ячейки матрицы $B'$ как обычно равны значениям мономов, соответствующих столбцам, на входах, соответствующих строкам. Таким образом, $B'$ является $\{0,\pm 1\}$-матрицей. Доказательство. Это доказательство похоже на доказательство леммы 3 из [26].
Напомним, что выполняется равенство
$$
\begin{equation*}
\begin{bmatrix} B & B' \end{bmatrix} \begin{pmatrix} u \\ v \end{pmatrix} = 0.
\end{equation*}
\notag
$$
Обозначим через $B_1$ матрицу, состоящую из столбцов из $B'$ таких, что в соответствующих мономах содержится четное число переменных из $(\overline{x}^{\,1} - \overline{y}^{\,1})$. Далее, обозначим через $B_2$ матрицу, состоящую из столбцов из $B'$ таких, что они не входят в $B_1$ и в соответствующих мономах содержится четное число переменных из $(\overline{x}^{\,2} - \overline{y}^{\,2})$. В общем виде, обозначим через $B_{i}$ матрицу, состоящую из столбцов из $B'$ таких, что они не входят в $B_1,B_{2},\dots, B_{i-1}$ и в соответствующих мономах содержится четное число переменных из $(\overline{x}^{\,i} - \overline{y}^{\,i})$. Заметим, что каждый столбец $B'$ попадает в одну из матриц $B_{1},\dots, B_{n}$, поскольку мономы, соответствующие столбцам в $B'$, не лежат в $M_{d}'$ и имеют степень не больше $d$. Следовательно, каждый моном, соответствующий столбцу в $B'$, не содержит переменных из $\overline{x}^{\,i} - \overline{y}^{\,i}$ для некоторого $i$. В этих обозначениях мы можем записать нашу систему в более развернутой форме:
$$
\begin{equation}
\begin{bmatrix} B & B_1 & \dots & B_n \end{bmatrix} \begin{pmatrix} u \\ v_1 \\ \vdots \\ v_n \end{pmatrix} = 0,
\end{equation}
\tag{3.2}
$$
где $v_{1}, \dots, v_n$ – это координаты $v$, соответствующие $B_{1}, \dots, B_{n}$.
Теперь с помощью рассуждения, основанного на симметрии, мы избавимся от части $v$ в множестве коэффициентов. Заметим, что каждый моном в $M_{d}' \cup \{\theta\}$ меняет знак, если мы поменяем местами $\overline{x}^{\,i}$ и $\overline{y}^{\,i}$ для какого-то $i$. Тогда тоже самое верно и для многочлена $p$. Это означает, что если мы возьмем значения входов, соответствующие какой-то строке в $B$ и поменяем местами значения $\overline{x}^{\,i}$ и $\overline{y}^{\,i}$, значение $p$ все еще будет равно $0$, и таким образом, значение $f$ все еще будет равно $1$. Поскольку многочлен с коэффициентами $w'$ реализует функцию $f$, значение этого многочлена тоже должно быть равно $0$ на таком входе. Применяя это для $i=1$ и всех строк матрицы мы получаем
$$
\begin{equation*}
\begin{bmatrix} - B & B_1 & - B_{2} & \dots & - B_n \end{bmatrix} \begin{pmatrix} u \\ v_1 \\ v_2 \\ \vdots \\ v_n \end{pmatrix} = 0,
\end{equation*}
\notag
$$
поскольку все мономы, соответствующие столбцам вне $B_1$ содержат нечетное число переменных из $(\overline{x}^{\,1} - \overline{y}^{\,1})$. Вычитая эту систему из (3.2) и деля на $2$, мы получаем
$$
\begin{equation*}
\begin{bmatrix} B & 0 & B_{2} & \dots & B_n \end{bmatrix} \begin{pmatrix} u \\ v_1 \\ v_2 \\ \vdots \\ v_n \end{pmatrix} = 0,
\end{equation*}
\notag
$$
что равносильно Рассуждая аналогично последовательно для $(\overline{x}^{\,2}-\overline{y}^{\,2})$, $\dots$, $(\overline{x}^{\,d}-\overline{y}^{\,d})$, мы получаем систему Предложение доказано. Теперь, если мы отделим последний столбец матрицы и перенесем его в правую часть, то получим систему с квадратной матрицей:
$$
\begin{equation*}
A^{(d)} \begin{pmatrix} u_1 \\ u_2 \\ \vdots \\ u_{n^d} \end{pmatrix} = \begin{pmatrix} u_{n^d+1} \\ 0 \\ \vdots \\ 0 \end{pmatrix}.
\end{equation*}
\notag
$$
Заметим, что $u_{n^d+1}$ не может быть нулем, поскольку иначе все $u_i$ равны нулю (напомним, что $A^{(d)}$ невырождена). Теперь, по правилу Крамера мы получаем, что
$$
\begin{equation*}
| u_{n^d} | = \biggl| \frac{u_{n^d+1} \det A^{(d)}_{1,n^d}}{\det A^{(d)}} \biggr| \geqslant \biggl|\frac{\det A^{(d)}_{1,n^d}}{\det A^{(d)}} \biggr|.
\end{equation*}
\notag
$$
Теперь мы избавимся от $z$. Определим функцию $g(x,y)=f(x,y,0)$. Очевидно, она является полиномиальной точной пороговой функцией. Более того, всякий целочисленный многочлен степени $d$, реализующий $g(x,y)$, можно преобразовать в целочисленный многочлен степени $d$, реализующий $f(x,y,z)$. Действительно, пусть многочлен для $g$ задается вектором коэффициентов $u$. Добавим к нему целый коэффициент для монома $\theta$ таким образом, чтобы получившийся вектор $u'$ удовлетворял первой строке системы (3.1). Заметим, что он автоматически удовлетворяет всем остальным строкам системы (поскольку они все соответствуют входам с $z=0$). Таким образом, $u'$ является решением системы (3.1), и следовательно,
$$
\begin{equation*}
|u_{n^d}| \geqslant \biggl|\frac{\det A^{(d)}_{1,n^d}}{\det A^{(d)}} \biggr| \geqslant \frac{n^{n^d/2}}{2^{2n^d + o(n^d)}}.
\end{equation*}
\notag
$$
Мы доказали нижнюю оценку на коэффициенты целочисленного многочлена степени не больше $d$ от переменных $x-y$ и $x+y$, реализующего $g(x,y)$. И согласно наблюдению 2 мы получаем требуемую нижнюю оценку для многочленов от переменных $x$ и $y$ (в этом месте появляется множитель $2^d$ в знаменателе). Теорема доказана. Замечание 1. Заметим, что новая переменная $z$ требуется в предложении 2. Если мы попробуем вместо этого записать систему без переменной $z$ и с нетривиaльной правой частью, мы не сможем провести рассуждение, основанное на симметрии. Наконец, заметим, что мы можем передоказать нижнюю оценку на величину $\operatorname{maxw}^T_d(n)$ (которая является обобщением $\operatorname{maxw}^T(n)$ на пороговые функции степени $d$) из [26] аналогично обобщению доказательства нижней оценки на $\operatorname{maxw}^T(n)$ из [3]. Доказательство. Как в доказательстве теоремы 11, у нас есть переменные $x_{ij}, y_{ij} \in \{0,1\}$ для $i = 1,\dots,d$ и $j = 1,\dots,n$ и мы рассматриваем многочлены от переменных $x-y$ и $x+y$. Как в доказательстве теоремы 11 мы рассматриваем матрицу $A^{(d)}$ и, вновь, в метках $A^{(d)}$ заменяем всякую переменную $x_{ij}$ на $x_{ij} - y_{ij}$.
Положим
$$
\begin{equation*}
\alpha_i = \operatorname{sign} (-1)^{i} \det A^{(d)}_{i,n^d} \det A^{(d)}
\end{equation*}
\notag
$$
для $i=1, \dots, n^d$ и положим вектор $w$ равным решению системы Пусть $f(x,y)$ – полиномиальная пороговая функция степени $d$, реализуемая многочленом $w$.
Рассмотрим произвольную реализацию $w'$ этой функции. Мы получаем
$$
\begin{equation}
\begin{bmatrix} A^{(d)} & B' \end{bmatrix} \begin{pmatrix} u \\ v \end{pmatrix} = \beta,
\end{equation}
\tag{3.3}
$$
где обозначения $B', u, v$ такие же, как в доказательстве теоремы 11, а $\beta$ – целочисленный вектор (поскольку $w'$ – целочисленный вектор) такой, что $\operatorname{sign} \beta_i = \alpha_i$.
По рассуждению, основанному на симметрии, аналогичному рассуждению из доказательства теоремы 11, мы можем получить $A^{(d)}u = \beta'$, где $\beta'_i$ – рациональные числа со знаменателями $2^d$ и $\operatorname{sign} \beta'_i = \alpha_i$. Теперь, если мы рассмотрим это уравнение как систему линейных уравнений от переменных $u$, то по правилу Крамера мы получим
$$
\begin{equation*}
|w_{n^d}| = \biggl| \sum_{i=1}^{n^d} (-1)^{i} \frac{\beta'_i A^{(d)}_{i,n^d}}{A^{(d)}}\biggr| = \sum_{i=1}^{n^d} \biggl| \frac{\beta'_i A^{(d)}_{i,n^d}}{A^{(d)}} \biggr| \geqslant \biggl| \frac{\beta'_1 A^{(d)}_{1,n^d}}{A^{(d)}} \biggr| \geqslant \frac{n^{n^d/2}}{2^{2n^d + o(n^d) + 2d}},
\end{equation*}
\notag
$$
где второе равенство следует из выбора $\alpha$. Теорема доказана. § 4. ЗаключениеМы получили верхние и нижние оценки величины целых весов, необходимых для реализации точных пороговых функций, как для линейных точных пороговых функций, так и в более общем виде для полиномиальных точных пороговых функций. Для линейного случая мы также получили оценки для интересного частного случая функций маленькой размерности. В случае маленькой размерности оценки все еще далеки от точных для непостоянного $k$. В остальных случаях полученные оценки очень близки, особенно в линейном случае, где почти не остается возможностей для улучшений. Для доказательства нижних оценок для полиномиальных точных пороговых функций мы построили плохо обусловленные матрицы с дополнительными свойствами, они могут быть полезны для других приложений. Еще один вопрос возникает из сравнения результатов, известных для пороговых функций и для точных пороговых функций. Бейгель [5] строит технику для доказательства того, что существуют простые линейные пороговые функции, для которых необходимы экспоненциальные веса даже у реализаций степени $n^{1/2-\epsilon}$. Эта техника была обобщена в [25] на случай полиномиальных пороговых функций большей степени. Не видно, как переносить метод Бейгеля и его обобщения на точные пороговые функции. Таким образом, получение аналогичных результатов для точных пороговых функций является открытым вопросом. 
Цитирование в формате AMSBIB
\RBibitem{BabHanPod21} |
|
||||||||||||||||||||||||||||||||||||
|
Обратная связь: |
Пользовательское соглашение
|
Регистрация посетителей портала |
Логотипы |
|