G3 Шур и SOS-разложение

Метод состоит в том, что симметричные неравенства для трёх и более переменных доказываются либо через неравенство Шура, либо через SOS-разложение (Sum of Squares — сумма квадратов).

Это инструменты высшего уровня олимпиадных неравенств — для задач, где AM-GM и КБШ не дают прямого результата. Они позволяют систематически «разложить» неравенство в сумму неотрицательных слагаемых, каждое из которых очевидно неотрицательно.

Неравенство Шура: для неотрицательных $a, b, c$ и $t > 0$:$$a^t(a-b)(a-c) + b^t(b-a)(b-c) + c^t(c-a)(c-b) \geq 0.$$ При $t=1$ это раскрывается в $a^3+b^3+c^3+abc \geq ab(a+b)+bc(b+c)+ca(c+a)$.

SOS-разложение: представить доказываемое выражение $E$ в виде $\sum_i p_i(a,b,c) \cdot (a-b)^2 + \sum_j q_j(a,b,c)\cdot(b-c)^2 + \ldots$, где все $p_i, q_j \geq 0$. Так как каждый квадрат неотрицателен, всё выражение $\geq 0$.

Интуиция: «доказать неравенство» означает показать, что нечто $\geq 0$. Если это «нечто» есть сумма квадратов, то это очевидно. SOS — это систематический способ найти такое представление.

• Неравенство Шура ($t=1$): $a^3+b^3+c^3+abc \geq ab(a+b)+bc(b+c)+ca(c+a)$ для $a,b,c \geq 0$. Равенство при $a=b=c$ или при одном из них равном 0 и двух равных. Когда использовать: симметричные неравенства степени 3 после введения $p=a+b+c$, $q=ab+bc+ca$, $r=abc$.

• Неравенство Шура (общий вид): $\sum_{\text{cyc}} a^t(a-b)(a-c) \geq 0$ для $t > 0$. Когда использовать: неравенства степени $t+2$.

• SOS для двух переменных: $f(a,b) \geq 0$ ⟺ $f$ представляется как сумма квадратов полиномов. Для трёх — сложнее, но идея та же.

• Связь с $p, q, r$: неравенство Шура при $t=1$ в терминах $p, q, r$: $p^3 - 4pq + 9r \geq 0$, то есть $9r \geq 4pq-p^3$. Когда использовать: оценить $r = abc$ снизу через $p$ и $q$.

• SOS с коэффициентами: $E = \alpha(a-b)^2 + \beta(b-c)^2 + \gamma(a-c)^2 + \delta(a-b)^2(b-c)^2 + \ldots$ Если $\alpha, \beta, \gamma \geq 0$ — готово.

• Перейти к симметрическим многочленам. Обозначить $p=a+b+c$, $q=ab+bc+ca$, $r=abc$ и переписать неравенство через $p, q, r$. Неравенство Шура при $t=1$ принимает вид $p^3+9r \geq 4pq$.

• Проверить равенство. Сначала найди, при каких значениях равенство — это подскажет структуру SOS-разложения (квадраты должны обращаться в ноль в этих точках).

• Искать SOS-разложение. Попробуй записать $E = \lambda_1(a-b)^2 + \lambda_2(b-c)^2 + \lambda_3(a-c)^2$ с константами $\lambda_i \geq 0$. Раскрой и сравни коэффициенты.

• Использовать нормировку. При $a+b+c=1$ (или $a+b+c=3$) сокращается число параметров. WLOG предположить $a \geq b \geq c \geq 0$.

• Svensen trick (подстановка $c=0$). Иногда полезно проверить неравенство на границе (один из параметров = 0) и затем показать, что «добавление» третьей переменной только улучшает оценку.

• Применить Шур + AM-GM. Неравенство Шура оценивает $r$ снизу, AM-GM оценивает $q$ сверху — вместе они дают полную систему оценок для симметричных выражений.

• Разложение на неприводимые квадраты. Для выражения от двух переменных: выдели полный квадрат и проверь остаток.

Поверхностные признаки (что буквально написано):
- «Докажите для $a, b, c \geq 0$: [симметричное неравенство степени 3 или 4]».
- «Докажите, что $f(a,b,c) \geq 0$ для всех вещественных (или неотрицательных) $a, b, c$».
- AM-GM и КБШ «не хотят» работать в лоб.

Структурные признаки (форма выражения, объекты):
- Выражение симметрично по $a, b, c$ (не меняется при всех перестановках).
- Степень выражения 3 или 4 по совокупности переменных.
- Равенство достигается не только при $a=b=c$, но и при другом значении (например, $c=0$, $a=b$).

Цель задачи (что от тебя хотят):
- Доказать «трудное» симметричное неравенство, которое не берётся AM-GM или КБШ.
- Найти все случаи равенства.
- Оценить симметрическую функцию трёх переменных через другие симметрические функции.

Задача 1. Докажите неравенство Шура: для $a, b, c \geq 0$ и $t=1$

$$a(a-b)(a-c)+b(b-a)(b-c)+c(c-a)(c-b) \geq 0.$$

Источник: неравенство Шура, классическое, тренировочная.

Как думать (рассуждение ученика):
1. Вижу симметричное выражение с разностями $(a-b)$, $(b-c)$... Это и есть неравенство Шура — стоит знать его наизусть.
2. Но нужно доказать! Основная идея: WLOG $a \geq b \geq c \geq 0$. Тогда $a-b \geq 0$, $a-c \geq 0$, $b-c \geq 0$.
3. Первое слагаемое $a(a-b)(a-c) \geq 0$. Третье $c(c-a)(c-b) = c(-(a-c))(-(b-c)) = c(a-c)(b-c) \geq 0$. А второе слагаемое $b(b-a)(b-c) \leq 0$ (так как $b-a \leq 0$, $b-c \geq 0$).
4. Группирую первое и второе: $a(a-b)(a-c)+b(b-a)(b-c) = (a-b)[a(a-c)-b(b-c)] = (a-b)[a^2-ac-b^2+bc]=(a-b)[(a-b)(a+b)-c(a-b)]=(a-b)^2(a+b-c)$.

Решение:

WLOG $a \geq b \geq c \geq 0$. Перегруппируем:

$$a(a-b)(a-c)+b(b-a)(b-c) = (a-b)[a(a-c)-b(b-c)].$$

Внутри скобок:$$a(a-c)-b(b-c) = a^2-ac-b^2+bc = (a^2-b^2)-c(a-b) = (a-b)(a+b-c).$$

Поэтому первые два слагаемых равны $(a-b)^2(a+b-c)$.

Третье слагаемое: $c(c-a)(c-b) = c(a-c)(b-c) \geq 0$ (так как $a \geq c$, $b \geq c$).

При $a+b \geq c$ (что верно, так как $a \geq b \geq c$, поэтому $a+b \geq 2c \geq c$): первые два слагаемых $\geq 0$, третье $\geq 0$, всё доказано.

Ответ: неравенство доказано. Равенство при $a=b=c$ или при $c=0$, $a=b$.

Что в этой задаче было главным: группировка первых двух слагаемых и факторизация $(a-b)^2(a+b-c)$ — это типичный приём для SOS-стиля доказательств.

Задача 2. Докажите: для $a, b, c > 0$ с $a+b+c=1$ выполнено $ab+bc+ca \leq \dfrac{1}{3}$.

Источник: тренировочная (следствие AM-GM, иллюстрирует SOS).

Как думать (рассуждение ученика):
1. Хочу доказать $\frac{1}{3} - (ab+bc+ca) \geq 0$. Подставлю $a+b+c=1$, то есть $1 = (a+b+c)^2 = a^2+b^2+c^2+2(ab+bc+ca)$.
2. Из этого: $a^2+b^2+c^2 = 1 - 2(ab+bc+ca)$. Нужно $3(ab+bc+ca) \leq 1 = a^2+b^2+c^2+2(ab+bc+ca)$.
3. То есть нужно $a^2+b^2+c^2 \geq ab+bc+ca$. Это знакомое неравенство!
4. SOS: $a^2+b^2+c^2 - ab-bc-ca = \frac{1}{2}[(a-b)^2+(b-c)^2+(a-c)^2] \geq 0$.

Решение:

Так как $(a-b)^2 \geq 0$, $(b-c)^2 \geq 0$, $(a-c)^2 \geq 0$:$$\frac{1}{2}[(a-b)^2+(b-c)^2+(a-c)^2] = a^2+b^2+c^2 - ab-bc-ca \geq 0.$$

При $a+b+c=1$: $1 = (a+b+c)^2 = a^2+b^2+c^2+2(ab+bc+ca)$, откуда$$3(ab+bc+ca) \leq a^2+b^2+c^2+2(ab+bc+ca) = 1.$$

Ответ: $ab+bc+ca \leq \dfrac{1}{3}$, равенство при $a=b=c=\dfrac{1}{3}$.

Что в этой задаче было главным: стандартное тождество $a^2+b^2+c^2-ab-bc-ca = \frac{1}{2}\sum(a-b)^2$ — это «кирпич» SOS-разложений, который нужно знать наизусть.

• Ошибка: не проверить, что все коэффициенты в SOS неотрицательны. SOS работает только если все слагаемые неотрицательны. Если хотя бы один коэффициент отрицательный, разложение неверно. → После нахождения разложения явно проверь знаки всех коэффициентов.

• Ошибка: применить Шур при $t \leq 0$. Неравенство Шура верно при $t > 0$; при отрицательных $t$ знак меняется. → Всегда уточняй ограничения на $t$.

• Ошибка: не учесть случаи равенства. У Шура два случая равенства ($a=b=c$ и граничный $c=0$, $a=b$). Пропуск одного из них — неполный ответ. → Всегда выписывай все случаи равенства.

• Ошибка: путать $pqr$-нотацию. $p=a+b+c$, $q=ab+bc+ca$, $r=abc$. Часто путают $q$ и $r$. → Явно определи обозначения в начале.

• Ошибка: считать, что SOS всегда существует. Не каждое неотрицательное выражение является суммой квадратов над $\mathbb{Q}$ (контрпример — некоторые формы степени $\geq 6$). Для степеней 3–4 в олимпиадных задачах SOS почти всегда найдётся. → Если SOS не ищется, попробуй Шур + AM-GM.