нулевые суммы корней из 1

[maxal]

Пусть $U_n = \{ e^{i\frac{2\pi j}{n}} : j=0,\dots,n-1\}$ это множество корней $n$-ой степени из единицы. Положим $a(n)$ равным числу подмножеств $U_n$, сумма элементов которых равна $0$.

Задачи:

1) Пусть $s(n)$ - это произведение всех различных простых делящих $n$ (т.е. свободное от квадратов ядро $n$). Докажите, что $a(n) = a(s(n))^{n/s(n)}.$

2) Докажите, что $a(p)=2$, где $p$ - простое.

3) Докажите, что $a(pq)=2^p + 2^q - 2$, где $p$ и $q$ различные простые.

4) Найдите $a(pqr)$, где $p,\ q,\ r$ - различные простые.

[Sasha Rybak]

Пусть $\varepsilon_n=e^{2\pi i/n}$. Тогда $U_n=\{\varepsilon_n^0, \varepsilon_n^1, ..., \varepsilon_n^{n-1}\}$. Пусть $F_n=\{q_0\varepsilon_n^0+q_1\varepsilon_n^1+...+q_{n-1}\varepsilon_n^{n-1}|q_0, q_1, ..., q_{n-1} \in \mathbb Q\}$. $F_n$ - это линейное пространство над $\mathbb Q$. Найдём его размерность.
Несложно показать, что $F_n$ также является ПОЛЕМ, порождённым присоединением к $\mathbb Q$ элемента $\varepsilon_n$. В таком случае размерность $F_n$ как линейного пространства над $\mathbb Q$ равна степени неприводимого многочлена с рациональными коэффициентами, корнем которого является $\varepsilon_n$. Укажем этот многочлен.
Рассмотрим многочлен $\Phi_n(x)=\prod\limits_{k:\ 0\le k<n,\ \gcd(k,n)=1}(x-\varepsilon_n^k)$. Очевидно, $\Phi_n(\varepsilon_n)=0$. $\Phi_n(x)$ называется ЦИКЛОТОМИЧЕСКИМ многочленом, или многочленом ДЕЛЕНИЯ КРУГА. Для доказательства того, что он обладает рациональными (даже целыми) коэффициентами применим индукцию по n и используем формулу: $\Phi_n(x)=\frac{(x^n-1)}{\prod_{d:\ d|n,\ 0<d<n}\Phi_d(x)}\ (n \in \mathbb N)$, которая доказывается несложно.
Доказательство неприводимости циклотомического многочлена можно найти здесь: http://planetmath.org/encyclopedia/ProofThatTheCyclotomicPolynomialIsIrreducible.html
Более адаптированное доказательство есть в "Многочленах" Прасолова. Если нужно - могу выложить. Степень $\Phi_n(x)$, а с ней и размерность $F_n$, равна $\varphi(n)$ - функции Эйлера от n.

Теперь перейдём к самой задаче.
1) Заметим, что $F_n=F_{s(n)}+F_{s(n)}*\varepsilon_n+...+F_{s(n)}*\varepsilon_n^{(n/s(n))-1}$. Поскольку $\dim(F_n)=\varphi(n)=\frac{n}{s(n)} \cdot \varphi(s(n))=\dim(F_{s(n)})+...+\dim(F_{s(n)}*\varepsilon_n^{(n/s(n)-1)})$, то пространства $F_{s(n)}, ..., F_{s(n)}*\varepsilon_n^{(n/s(n))-1}$ - линейно независимы. Пусть $X \subset U_n$. Чтобы сумма элементов $X$ была равна 0, необходимо и достаточно, чтобы сумма элементов каждого из подмножеств $X \cap U_{s(n)}, ..., X \cap U_{s(n)}*\varepsilon_n^{(n/s(n))-1}$ была равна 0. По определению, последнее можно сделать $a(s(n))$ способами в каждом подмножестве. Отсюда $a(n)=a(s(n))^{n/s(n)}$.

2) Любая выборка задаёт равенство $a_{p-1}\varepsilon_p^{p-1}+...+a_1\varepsilon_p^1+a_0,\ a_{p-1}, ..., a_1, a_0 \in \{0,1\} \subset \mathbb Q$. Из неприводимости $\Phi_p(x)$ следует, что многочлен $a_{p-1}x+...+a_1x+a_0$ делится на $\Phi_p(x)=x^{p-1}+...+x+1$. Нам подходят только два варианта:
$a_0=...=a_{p-1}=0$ и $a_0=...=a_{p-1}=1$.

3) (И идея для 4.) Рассмотрим линейное пространство
$G_n=\{(q_0, q_1, ..., q_{n-1}) \in \mathbb Q^n|q_0\varepsilon_n^0+q_1\varepsilon_n^1+...+q_{n-1}\varepsilon_n^{n-1}=0\}$. Тогда $\dim(G_n)=n-\dim(F_n)=n-\varphi(n)$. Для $n=pq:\ \dim(G_{pq})=pq-\varphi(pq)=p+q-1$. Заметим, что p-периодические векторы и q-периодические векторы принадлежат $G_{pq}$. Пусть $C_d$ - пространство d-периодических векторов, (d - делитель pq). По формуле включений-исключений, учитывая $C_p \cap C_q=C_1$: $\dim(C_p+C_q)=\dim(C_p)+\dim(C_q)-\dim(C_p \cap C_q)=p+q-1.$ Значит, $G_{pq}=C_p+C_q$. Поэтому, $G_{pq}$ является множеством линейных комбинаций таких строк (пример приведён для p=3, q=2):
(1 0 0 1 0 0),
(0 1 0 0 1 0),
(0 0 1 0 0 1),

(1 0 1 0 1 0),
(0 1 0 1 0 1).

Осталось описать все линейные комбинации указанных строк, состоящие из 0 и 1. Заметим, что у каждой p-периодической строки и каждой q-периодической строки (из указанных выше) есть координата, где ОНИ И ТОЛЬКО ОНИ имеют единицу. Поэтому, если в линейной комбинации взяты p-периодические строки c не всеми одинаковыми коэффициентами, а также q-периодические строки c не всеми одинаковыми коэффициентами, то в сумме мы получим вектор с по крайней мере 3 различными координатами. Значит, нужные нам комбинации имеют равные коэффициенты либо среди p-периодических строк, либо среди q-периодических. Эти равные коэффициенты мы можем считать нулевыми, поскольку сумму всех q-периодических строк можно заменить на сумму всех p-периодических или наоборот. Для p-периодических строк мы имеем $2^p$ подходящих линейных комбинаций, для q-периодических - $2^q$. Одновременно p- и q-периодическими будут только 1-периодические строки, которых 2. По формуле включений-исключений: $a(n)=2^p+2^q-2$.

4) Решать можно аналогично 3. Строк из 0 и 1, обладающих pq-, pr- или qr-периодичностью будет $2^{pq}+2^{pr}+2^{qr}-2^p-2^q-2^r+2$. Осталось исследовать, есть ли другие строки.

[maxal]

Прасолова выкладывать не надо - он свободно доступен тут. Да и общеизвестные факты можно не доказывать, а просто сослаться.

4) Другие есть. Вот точное значение в простейшем случае:
$a(2\cdot 3\cdot 5) = 146854$, в тот время как:
$2^{2\cdot 3}+2^{2\cdot 5}+2^{3\cdot 5}-2^2-2^3-2^5+2 = 33814$.

Еще одна задача:

5) Пусть $b(n)$ - это количество различных значений, которые могут принимать суммы элементов подмножеств $U_n$. Докажите формулу, аналогичную 1):

$$b(n) = b(s(n))^{n/s(n)}.$$

[Sasha Rybak]

И я продолжаю-ю-ю...

Пункт 5) решается абсолютно аналогично 1).

4) Аналогично 3), по формуле включений-исключений показываем, что $\dim(C_{pq}+C_{pr}+C_{qr})=pq+pr+qr-p-q-r+1=pqr-\varphi(pqr)=\dim(G_{pqr})$. Очевидно, что $C_{pq}+C_{pr}+C_{qr} \subset G_{pqr}$. Тогда из равенства размерностей получаем $G_{pqr}=C_{pq}+C_{pr}+C_{qr}$.
Для каждого $j \in \{0, 1, ..., pqr-1\}$ существует единственная, и отличная от остальных, тройка целых чисел $(a,b,c)$, для которой $0 \le a<r, 0 \le b<q, 0 \le c<p$ и $j \equiv apq+bpr+cqr\ (\mathrm{mod}\ pqr)$. Это не слишком очевидно, но доказывается несложно. Поэтому координаты вектора $(x_0, x_1, ..., x_{pqr-1}) \in G_{pqr}$ можно разместить в ячейках параллелепипеда размером $p \times q \times r$ в соответствии с тройками (a, b, c). Тогда pq-, pr- и qr-периодическим строкам, у которых в одном периоде только одна координата равна 1, а остальные - нули, соответствуют строчки, столбики и колонки из единичек. Значит, нам нужно посчитать количество параллелепипедов $p \times q \times r$ с нулями и единичками в ячейках, которые можно получить с при следующей последовательности операций. А именно - на каждом шагу можно добавить одно и то же число ко всем ячейкам некоторой строчки, столбика или колонки. (Вначале во всех ячейках стоят нули.)
Проанализируем параллелепипед, полученный таким образом. Отнимем каждую цифру верхнего слоя от всех цифр, стоящих в её колонке. (Колонки, скажем, соответствуют параметру r.) Рассмотрим нижние r-1 слоёв, полученные таким вычитанием. На их ячейки НЕ ВЛИЯЛИ pq-периодические добавления! Остальные же добавления меняли КАЖДЫЙ СЛОЙ ОТДЕЛЬНО!! В полученном параллелепипеде $p \times q \times (r-1)$, могут быть только цифры -1, 0 или 1. При этом в одной колонке не могут быть одновременно -1 и 1. Если колонка состоит из одних нулей - она восстанавливается 2 способами, независимо от остальных. В других случаях (кроме запретного "-1 и 1") колонка восстанавливается 1 способом.

Теперь покажу, как из этих соображений посчитать a(pqr) для r=2. Даже в этом случае получаются громоздкие формулы, поэтому я думаю, что для всех r ответ в виде формулы представить не получится.

В случае r=2 имеем один слой, полученный последовательными добавлениями одинаковых чисел к столбцам и строкам. В слое могут быть только цифры -1, 0, 1. Каждому варианту слоя соответствует $2^{n(0)}$ параллелепипедов, где n(0) - количество нулей в слое. Естественно, что разным вариантам слоя соответствуют разные параллелепипеды.
Несложно показать, что $|M_p|+|M_q| \le 4$, где $M_p$ - множество различных коэффициентов при базисных p-периодических векторах (строках), а $M_q$ - множество различных коэффициентов при базисных q-периодических векторах (столбцах). В противном случае у нас было бы не менее 4 вариатов цифр в ячейках. Значит, имеем 3 типа слоёв.
A. "Продольный" $(|M_p| \le 3,\ |M_q|=1)$ - столбцы берутся с одинаковыми коэффициентами, которые можно считать нулями, переоформив добавление на строки. Строки, которых p, (после переоформления) берутся с коэффициентами -1, 0 или 1.
B. "Поперечный" $(|M_p|=1,\ |M_q| \le 3)$ - строки берутся с одинаковыми коэффициентами, которые можно считать нулями, переоформив добавление на столбцы. Столбцы, которых q, (после переоформления) берутся с -1, 0 или 1.
C. "Крестообразный" $(|M_p|\le 2,\ |M_q| \le 2)$ - строки берутся с -1 или 0, к столбцы - с 0 или 1. (Остальные варианты можно переоформить к указанному.)

Под $A,\ B,\ C$ будем понимать множества ПАРАЛЛЕЛЕПИПЕДОВ, соответствующих слоям данного типа. Вычислим все возможные пересечения. Далее j - это количество строк, взятых с нулевыми коэффициентами, k - количество аналогичных столбцов.
$|A|=\sum\limits_{j=0}^{p}C_p^j \cdot 2^{qj} \cdot 2^{p-j}=(2^q+2)^p.$ Пояснение: имеем qj нулей в слое, дающих $2^{qj}$ способов. Остальные p-j строк независимо берутся с -1 или 1.
$|B|=\sum\limits_{k=0}^{q}C_q^k \cdot 2^{pk} \cdot 2^{q-k}=(2^p+2)^q.$ Аналогично предыдущему.
$|C|=\sum\limits_{j=0}^{p}C_p^j\sum\limits_{k=0}^{q}C_q^k \cdot 2^{jk+(p-j)(q-k)} - 2^{pq}=\sum\limits_{j=0}^{p}C_p^j(2^{j}+2^{p-j})^q - 2^{pq}.$ Пояснение: $2^{pq}$ вычитается из-за того, что слой из одних нулей мы считаем 2 раза: при j=k=0 и при j=p, k=q.
$|A \cap C|=\sum\limits_{j=0}^{p}C_p^j \cdot 2^{qj} \cdot 2 - 2^{pq}=2\cdot(2^q+1)^p - 2^{pq}.$ Пояснение: строки, взятые не с нулём, - все одновременно будут с -1 или с 1. При j=p это одно и то же, поэтому нужно вычесть $2^{pq}$.
$|B \cap C|=\sum\limits_{k=0}^{q}C_q^k \cdot 2^{pk} \cdot 2 - 2^{pq}=2\cdot(2^p+1)^q - 2^{pq}.$
$|A \cap B|=2^{pq}+2.$ Годятся только однородные слои.
$|A \cap B \cap C|=2^{pq}+2.$

$|A \cup B \cup C|=|A|+|B|+|C|-|A \cap C|-|B \cap C|$, то есть
$a(2pq)=\sum\limits_{j=0}^{p}C_p^j(2^{j}+2^{p-j})^q + (2^q+2)^p+(2^p+2)^q - 2\cdot(2^q+1)^p - 2\cdot(2^p+1)^q + 2^{pq}$.

Для p=5, q=3, r=2 получаем как раз $146854$.

[maxal]

Круто!

Продолжаем:

6) Докажите, что $a(n)\equiv 2^n \pmod{n}$.

[Sasha Rybak]

6) Эта попроще, но красивая. :)
$2^n-a(n)$ - это количество выборок с НЕНУЛЕВОЙ суммой. Все такие выборки разделим на группы таким образом, что две выборки входят в одну группу, если и только если их можно совместить поворотом. Выборка с ненулевой суммой не может самосовместиться при повороте - поскольку сумма тоже поворачивается. :) Поэтому в каждой группе ровно n выборок. Значит, количество таких выборок делится на n.

[Sasha Rybak]

Вопрос автору темы - а откуда Вы взяли такие задачи?

[maxal]

Источник задач - последовательности A103314 и A107847 в OEIS.
Ваша формула для $a(2pq)$, по-видимому, является новым результатом. Она позволяет вычислить значения A103314 вплоть до члена $3\cdot 5\cdot 7 - 1=104$. Я планирую прислать Нилу Слоану соответствующее обновление.

[maxal]

Sasha Rybak писал(а):

Теперь покажу, как из этих соображений посчитать a(pqr) для r=2. Даже в этом случае получаются громоздкие формулы, поэтому я думаю, что для всех r ответ в виде формулы представить не получится.

А мне кажется, что простая формула существует, хотя возможно незамкнутая, в виде комбинаторной суммы, например.

А пока я тут подсчитал численно: $a(3\cdot 5\cdot 7) = 166093023482$
Может потом пригодится для проверки формул

[mfh]

Докажите, что

$$a(n) + \sum_{d|n} 2^d \mu(n/d) = 2^n \iff n=p^k \lor n=pq $$

,
где $p$ и $q$ - простые, $k\in\mathbf{N}\setminus\{0\}$.

($\mu$ - Функция Мёбиуса)

[maxal]

mfh писал(а):

Докажите, что

$$a(n) + \sum_{d|n} 2^d \mu(n/d) = 2^n \iff n=p^k \lor n=pq $$

,
где $p$ и $q$ - простые, $k\in\mathbf{N}\setminus\{0\}$.

Левая часть - это частный случай общей формулы:

$$a(n) = 2^n + n\cdot L_0(n) - n\cdot L(n),$$

где $L(n)=\frac{1}{n}\sum_{d|n} 2^d \mu(n/d)$ - количество бинарных слов Линдона длины $n$ (A001037 в OEIS),
а $L_0(n)$ - количество бинарных слов Линдона длины $n$, соответствующих нулевым суммам корней из 1, где биты слова используются как коэффициенты перед корнями в сумме (A110981 в OEIS).

Ваш утверждение по сути эквивалентно утверждению, что $L_0(n)=0$ тогда и только тогда, когда $n$ является полупростым или положительной степенью простого числа (A102466 в OEIS). В обратную сторону оно доказывается просто из явных формул для $a(pq)$ и $a(p^k)$, а вот в прямую - есть над чем подумать.

[mfh]

Цитата:

Ваш утверждение по сути эквивалентно утверждению, что $L_0(n)=0$ тогда и только тогда, когда $n$ является полупростым или положительной степенью простого числа

Я согласен.

Цитата:

а вот в прямую - есть над чем подумать.

Это было моей целью

Это могло бы находиться в связи с тем, что для omega(n)>1 и Omega(n)>2 получаются не все подмножества нулевых сумм неоднократные профсоюза множеств $e^{i 2\pi k/n}U_d$, d | n. (пересечение или дополнение требуется)

PS: Извините за мое плохое знание русского языка... !