2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 нулевые суммы корней из 1
Сообщение06.09.2007, 21:37 
Модератор
Аватара пользователя


11/01/06
5660
Пусть $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$ - различные простые.

 Профиль  
                  
 
 Solution of 1-3
Сообщение09.09.2007, 22:51 
Аватара пользователя


08/06/07
52
Киев
Пусть $\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$. Осталось исследовать, есть ли другие строки.

 Профиль  
                  
 
 
Сообщение09.09.2007, 23:04 
Модератор
Аватара пользователя


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

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)}.$$

 Профиль  
                  
 
 Partial solution of 4
Сообщение20.09.2007, 19:46 
Аватара пользователя


08/06/07
52
Киев
И я продолжаю-ю-ю...

Пункт 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) - количество нулей в слое. Естественно, что разным вариантам слоя соответствуют разные параллелепипеды. :D
Несложно показать, что $|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$.

 Профиль  
                  
 
 
Сообщение21.09.2007, 04:57 
Модератор
Аватара пользователя


11/01/06
5660
Круто!

Продолжаем:

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

 Профиль  
                  
 
 Solution of 6
Сообщение21.09.2007, 22:06 
Аватара пользователя


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

 Профиль  
                  
 
 Where did you get such tasks?
Сообщение24.09.2007, 11:12 
Аватара пользователя


08/06/07
52
Киев
Вопрос автору темы - а откуда Вы взяли такие задачи?

 Профиль  
                  
 
 
Сообщение24.09.2007, 22:29 
Модератор
Аватара пользователя


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

 Профиль  
                  
 
 Re: Partial solution of 4
Сообщение18.01.2008, 16:41 
Модератор
Аватара пользователя


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


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

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

 Профиль  
                  
 
 
Сообщение01.02.2008, 00:06 


31/01/08
3
Докажите, что
$$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$ - Функция Мёбиуса)

 Профиль  
                  
 
 
Сообщение01.02.2008, 00:38 
Модератор
Аватара пользователя


11/01/06
5660
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)$, а вот в прямую - есть над чем подумать.

 Профиль  
                  
 
 
Сообщение01.02.2008, 08:19 


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

Я согласен.
Цитата:
а вот в прямую - есть над чем подумать.

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

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

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

 Профиль  
                  
 
 Re: нулевые суммы корней из 1
Сообщение04.11.2014, 15:33 
Модератор
Аватара пользователя


11/01/06
5660
Представил эту и смежные задачи на проблемной сессии конференции DIMACS Conference on Challenges of Identifying Integer Sequences: http://vimeo.com/album/3082332/video/109813739
(предупреждение: слайды на видео содержат ошибки, вот исправленные слайды)

Видео с других проблемных сессий (в том числе представление 1000-долларовых задач Конвея) и пленарных докладов этой конференции доступны на сайте: http://www.math.rutgers.edu/~zeilberg/oeis50.html

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 13 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group