Однородная по степени нижняя оценка на веса многочленов с заданной знаковой функцией

Знаковой функцией целочисленного многочлена $p$ степени $d$ от $n$ переменных называется булева функция $f\colon\{0,1\}^n\to\{0,1\}$ такая, что $f(x)=1$ тогда и только тогда, когда $p(x)>0$. В этом случае многочлен $p$ называется пороговым элементом степени $d$ для функции $f$. Сумма абсолютных значений коэффициентов $p$ называется весом порогового элемента. Для всяких $n$ и $d\le D\le\frac{\varepsilon n^{1/5}}{\log n}$ мы строим функцию $f$, для которой существует пороговый элемент степени $d$, но такую, что всякий пороговый элемент для $f$ степени не выше $D$ имеет вес $2^{(\delta n)^d/D^{4d}}$, где $\varepsilon>0$ и $\delta>0$ – некоторые константы. В частности, если $D$ постоянно, наша функция требует веса $2^{\Omega(n^d)}$ при реализации пороговыми элементами степени $D$. Ранее функции с такими свойствами были известны только для $d=1$ (и произвольного $D$) и для $D=d$. При постоянных $d$ построенные нами функции реализуются в виде ДНФ полиномиального размера. Лучшая нижняя оценка на веса пороговых элементов для таких функций, известная ранее, была $2^{\Omega(n)}$. Наши результаты также переносятся на случай функций вида $f\colon\{-1,1\}^n\to\{-1,1\}$.