на главную страницу ЛШСМ-2015 к списку курсов ЛШСМ-2015

Федор Владимирович Петров

Полиномиальный метод

Ф. В. Петров планирует провести 4 занятия.

Сравнительно недавно многочлены (с точки зрения коммутативной алгебры и алгебраической геометрии — совсем несложные факты про них, восходящие к классикам XIX века, но крепко забытые) помогли решить ряд старых задач, которые я кратко перечислю, чтобы показать их разнообразие:

  1. Если $A$ — множество из $k\geqslant 2$ остатков по модулю простого числа $p\geqslant 2k-3$, то всевозможные суммы $a+b$, где $a,b\in A$ и $a\ne b$, дают хотя бы $2k-3$ разных остатка по модулю $p$.
  2. Дан планарный граф (возможно, с кратными ребрами), степень каждой его вершины равна $r$. На каждом ребре указан список из $r$ допустимых цветов. Требуется выбрать цвет каждого ребра из списка так, чтобы ребра в каждой вершине были $r$ разных цветов. Теорема: если это возможно в случае, когда все списки совпадают, то это возможно и для произвольных списков. (Гипотеза: то же верно для произвольных графов.)
  3. Для натуральных $\alpha,\beta,\gamma$ имеет место равенство $$ {\int}_0^1\dots{\int}_0^1 \prod_{i=1}^nt_i^{\alpha}(1-t_i)^{\beta} \prod_{1\leqslant i<j\leqslant n}|t_i-t_j|^{2\gamma} dt_1\dots dt_n =\prod_{j=0}^{n-1}\frac{(\alpha+j\gamma)!(\beta+j\gamma)! ((j+1)\gamma)!}{(1+\alpha+\beta+(n+j-1)\gamma)!\gamma!}. $$
  4. Между $N$ точками на плоскости хотя бы $\rm{const}\, N/\log(N)$ различных попарных расстояний.

Как это делается и что ещё можно и нужно делать — тема моего рассказа.

Знания школьной программы достаточно для понимания основной части курса.