арифметические прогрессии по модулю 3

[rus4]

Я не очень пишу в жж, потому что тут с формулами неудобно. Но тут такой случай, что решение знаменитой задачи можно приложить одной картинкой. Тем более, решается с помощью многочленов, а многочлены наша тема

Comments

[rus4]

Можно, я теперь проще даже умею.

Пусть K --- поле, A --- линейно упорядоченное множество из n элементов (например, A={1,...,n}). Для ненулевой функции f∈ KA из A в K назовём её лидером, соответственно аутсайдером, наименьший, соответственно наибольший, элемент x из A, для которого f(x) не равно 0.

Лемма 1. Пусть X --- линейное подпространство в пространстве KA функций на A размерности m. Тогда количество различных лидеров элементов X равно m. То же и количество аутсайдеров.

Доказательство. Метод Гаусса.

Лемма 2. Пусть в условиях леммы 1 выполняется равенство ∑ x ∈ A f(x)g(x)h(x)=0 для любых функций f,g,h из X. Тогда m ≤ |A|/2.

Доказательство. Пусть не так и 2m>|A|. Тогда по лемме 1 (и принципу Дирихле) найдутся функции f,g ∈ X такие что лидер f совпадает с аутсайдером g. Полагая h=g получаем, что в сумме ∑x ∈ A f(x)g(x)h(x) ровно одно ненулевое слагаемое --- противоречие.

Пусть теперь K=F3 --- поле остатков по модулю 3, A --- подмножество в K^n без 3-прогрессий, то есть a+b+c=0 при a,b,c ∈ A тогда и только когда a=b=c. Пусть X --- пространство функций на A, ортогональных всем многочленам степени не выше 2n/3. Пусть f,g,h ∈ X.

Заметим, что сумма вида ∑a,b,c ∈ A f(a)g(b)h(c) P(a,b,c)=0 для любого многочлена степени не выше 2n. В самом деле, можно считать P одночленом, тогда сумма раскладывается в произведение суммы по a, суммы по b и суммы по c. Одна из них равна 0, поскольку степень P либо по a, либо по b, либо по c не превосходит 2n/3, а такому одночлену соответствующая функция f,g или h ортогональна.

В частности, нулю равна сумма ∑a,b,c ∈ A f(a)g(b)h(c) ∏i=1,...,n (1-(a_i+b_i+c_i)2)=∑a ∈ A f(a)g(a)h(a) (равенство следует из того, что если a,b,c не совпадают, то сумма a+b+с не равна 0, поэтому одна из скобок в произведении 0). Отсюда по лемме 2 получаем, что |A| ≥ 2dim(X) ≥ 2(|A|-d(2n/3)), где d(2n/3) --- количество одночленов от n переменных степени не больше чем 2n/3 и степени не больше 2 по каждой переменной.

Итак, |A| ≤ 2d(2n/3), что экспоненциально меньше чем 3^n в силу оценки из закона больших чисел: d(2n/3)/3^n это в точности вероятность того, что сумма n случайных величин, равномерно распределённых в {-1,0,1}, не больше чем -n/3.