Выражение функции XOR через медианы

Задача:

Докажите, что $x_0 \oplus x_1 \oplus \ldots \oplus x_{2m} = \langle \neg x_0, s_1, s_2, \ldots, s_{2m} \rangle$, $s_j = \langle x_0, x_j, x_{j+1}, \ldots, x_{j+m-1}, \neg x_{j+m}, \neg x_{j+m+1}, \ldots, \neg x_{j+2m-1} \rangle$, где $x_{2m+k}$ обозначает то же, что и $x_k$, при $k \ge 1$.

Определение:

Медиана или функция большинства (англ. Majority function) — функция (в данном случае) с нечетным числом входов, возвращающая $1$ тогда и только тогда, когда среди ее аргументов не меньше половины единиц.

Разберемся с условием. Нам предлагается выразить $\mathrm {XOR}$ с $2m+1$ аргументами с помощью медианы с $2m+1$ аргументом. Ей на вход подается набор $\{s_i\}$, получаемый следующим образом:

• Выпишем последовательность $x_1, x_2, \ldots, x_{2m}$
• Первую половину аргументов (а их ровно $m$) возьмем с отрицанием ($\neg x_1, \neg x_2, \ldots, \neg x_m, x_{m+1}, x_{m+2}, \ldots, x_{2m}$)
• Слева к этой последовательности припишем $x_0$ и дадим на вход медиане: $\langle x_0, \neg x_1, \neg x_2, \ldots, \neg x_m, x_{m+1}, x_{m+2}, \ldots, x_{2m} \rangle$ - так мы получили $s_{m+1}$
• Остальные $s_i$ получаются циклическим сдвигом отрицания (без учета $x_0$), например, вправо (так мы получим все циклические сдвиги отрицаний):
  • $s_{m+2} = \langle x_0, x_1, \neg x_2, \neg x_3, \ldots, \neg x_m, \neg x_{m+1}, x_{m+2}, \ldots, x_{2m} \rangle$,
  • $s_{m+3} = \langle x_0, x_1, x_2, \neg x_3, \neg x_4, \ldots, \neg x_m, \neg x_{m+1}, \neg x_{m+2}, x_{m+3}, \ldots, x_{2m} \rangle$,
  • $s_{m} = \langle x_0, \neg x_1, \neg x_2, \neg x_3, \ldots, \neg x_{m-1}, x_m, x_{m+1}, x_{m+2}, \ldots, x_{2m-1}, \neg x_{2m} \rangle$
  • $s_{1} = \langle x_0, x_1, x_2, x_3, \ldots, x_{m-1}, x_m, \neg x_{m+1}, \neg x_{m+2}, \ldots, \neg x_{2m-1}, \neg x_{2m} \rangle$

И весь этот набор ${s_i}$, вместе с $\neg x_0$, передается на вход еще одной медиане: $\langle \neg x_0, s_1, s_2, \ldots, s_{2m} \rangle$

Далее на время исключим $x_0$ из рассмотрения аргументов $s_i$.

Общие соображения

• В каждой $s_i$ ровно $m$ переменных с отрицанием и столько же без него.
• Каждой $s_i$ можно однозначно сопоставить пару $s_j$ такую, что все переменные с отрицанием из $s_i$ в $s_j$ будут без отрицания и наоборот. Это следует из того, как мы строим набор ${s_i}$ — циклически сдвигаем "крышу отрицания" над переменными, пока не получим все такие. Для нахождения нужно сдвинуть "крышу" ровно на $m$ позиций (вправо или влево, это не важно — получится одно и то же). Назовем такую пару $(s_i, s_j)$ двойственной, и пусть $s_j = \neg s_i$ (на самом деле $\neg s_i = s_{i+m}$).
• Назовем самостоятельной единицей для $s_i$ любой ее единичный аргумент.
• Если самостоятельных единиц в $s_i$ "достаточно много" (а сколько именно, будет зависеть от $x_0$), то в $\neg s_i$ их будет "достаточно мало".

Утверждение:

Если в $s_i$ ровно $n$ самостоятельных единиц, то в $\neg s_i$ их будет $(2m - n)$.

[math]\triangleright[/math]

Пусть $A$ - множество аргументов $s_i$ с отрицанием, $B$ - без отрицания. Оба множества по условию мощности $m$. Пусть среди $A$ ровно $a$ переменных равны $1$, тогда оставшиеся $(m - a)$ из них — нули. Аналогично среди $B$ ровно $b$ единиц и $(m - b)$ нулей. Самостоятельные единицы $s_i$ получаются из нулей среди $A$ и единиц среди $B$. Тогда в $s_i$ будет $(m - a) + b$ самостоятельных единиц. В двойственной $s_i$ переменные заменятся на их отрицания, поэтому самостоятельные единицы $\neg s_i$ получаются из единиц среди $A$ и нулей среди $B$. Поэтому количество самостоятельных единиц в $\neg s_i$ будет $a + (m - b)$. Нетрудно убедиться, что нужное соотношение выполняется: $(m - a) + b = 2m - (a + (m - b)) \Leftrightarrow m - a + b = 2m - a - m + b$

[math]\triangleleft[/math]

Утверждение:

Среди ${x_i}$ четное число единиц $\Leftrightarrow$ найдется двойственная пара с одинаковым количеством самостоятельных единиц, равным $m$.

[math]\triangleright[/math]

Импликация влево. Из утверждения выше мы поняли структуру аргументов $s_i$. Нужно приравнять количества (в обозначениях выше): $(m - a) + b = a + (m - b) \Leftrightarrow a = b$ А $a$ и $b$ — количества единиц в $A$ и в $B$ соответственно, и, так как множество всех аргументов $s_i$ это $A \cup B$, то $(a+b)$ и есть количество единиц среди ее аргументов. Но $a = b$, значит $a + b$ четное. Вообще, утверждения "нашлась двойственная пара с одинаковым числом самостоятельных единиц" (1) и "нашлась $s_i$ с количеством самостоятельных единиц, равным $m$" (2) равносильны. И правда, выше мы поняли, что (1) $\Leftrightarrow a = b$. Посчитаем количества самостоятельных единиц в $s_i$. $((m - a) + b) = m \Leftrightarrow a = b$. Таким образом, равносильность доказана. Импликация вправо.

[math]\triangleleft[/math]