гипотеза об остатке от деления на x^m + 1

[maxal]

Пусть число $m=2n+1$ свободно от квадратов. Пусть $R(x)$ является остатком от деления многочлена $\prod_{i=1}^n (x^i + x^{m-i})$ на многочлен $(x^m + 1)$, т.е.

$\prod_{i=1}^n (x^i + x^{m-i}) = Q(x) (x^m + 1) + R(x),$ где $\deg R(x)<m.$

Доказать или опровергнуть, что все коэффициенты многочлена $R(x)$ принадлежат множеству $\{-1,0,1\}.$ Более того, коэффициент при $x^k$ отличен от нуля тогда и только тогда, когда $НОД(k,m)=1$.

Пример. Для $m=15$ имеем $R(x)=x^{14} - x^{13} - x^{11} - x^8 - x^7 - x^4 - x^2 + x.$

[maxal]

При решении уперся в такую функцию.

Пусть $m=2n+1$ и нечетное число $t$ такое, что $0<t<m$ и $(t,m)=1.$
Для каждого $k=1,2,\dots,n$ рассмотрим величину $kt\bmod m$, лежащую в отрезке $[1,m-1]$. Пусть $K$ - число таких $k$, что $kt\bmod m$ принадлежит отрезке $[n+1,m-1]$ (другими словами, $kt\bmod m>n$). Меня интересует аналитическое выражение для $(-1)^K$ (т.е. по сути четность числа $K$):

$$f(m,t) = (-1)^{| \{k\ :\ 1\leq k\leq \frac{m-1}{2},\ (kt\bmod m)>\frac{m-1}{2}\}|.$$

Мне кажется, эта функция должна как-то просто выражаться через корень $m$-ой степени из 1, но что-то найти это выражение сходу не получается. Есть идеи?

Добавлено спустя 2 часа 33 минуты 21 секунду:

Альтернативная формулировка:

Для заданных нечетных взаимно-простых чисел $m$ и $t$ определить четность числа

$$\sum_{k=1}^{\frac{m-1}{2}} \left\lfloor\frac{2kt}{m}\right\rfloor = \frac{(m^2-1)t}{4m} - \frac{1}{m}\sum_{k=1}^{\frac{m-1}{2}} (2kt\bmod m).$$

Так как $m$ нечетно, то задача сводится к определению четности числа:

$$\sum_{k=1}^{\frac{m-1}{2}} (2kt\bmod m).$$

[Руст]

Кажется $f(m,t)=(-1)^{(m-1)/2}(\frac{t}{m})$. Посмотри одно из доказателств Гаусса о квадратичной взаимности.

[maxal]

Руст писал(а):

Кажется $f(m,t)=(-1)^{(m-1)/2}(\frac{t}{m})$. Посмотри одно из доказателств Гаусса о квадратичной взаимности.

Точно! С той лишь только поправкой, что $f(m,t)=(\frac{t}{m})$.

Учитывая этот результат, у меня получилось, что коэффициент при $x^k$ в многочлене $R(x)$ равен:

для $m\equiv 1\pmod{4}$:

$$\frac{(-1)^{(m-1)/4}}{\sqrt{m}} \sum_{t=0}^{m-1} \left(\frac{2t+1}{m}\right) \cos\frac{\pi k (2t+1)}{m} $$

для $m\equiv 3\pmod{4}$:

$$\frac{(-1)^{(m-3)/4}}{\sqrt{m}} \sum_{t=0}^{m-1} \left(\frac{2t+1}{m}\right) \sin\frac{\pi k (2t+1)}{m} $$

Осталось понять, почему ничего кроме $\{-1,0,1\}$ получиться не может.

[Руст]

Это же известные Гауссовы суммы. С учётом деления на корень из m они равны +-1 или 0.

[maxal]

Я исправил выражения для сумм. Гауссовы суммы конечно проглядываются, но в чисто виде - это не они. Придется повозиться, чтобы свести их к Гауссовым. Кроме того, там должна быть зависимость от k.

Через экспоненту коэффициент при $x^k$ в $R(x)$ выражается так:

$$\frac{i^{(m-1)/2}}{\sqrt{m}} \sum_{t=0}^{m-1} \left(\frac{2t+1}{m}\right) e^{-\pi i k (2t+1)/m}$$

[Руст]

Получилась несколько странная сумма. Но она выражаема через Гауссовы суммы.

$$\sum_{t=0}^{m-1} \left(\frac{2t+1}{m}\right) e^{-\pi i k (2t+1)/m}=\sum_{t=1}^{m-1}(\frac{t}{m})(-1)^{kt}e^{-\pi ikt/m} =(\frac km )\sum_{t=1}^{m-1}(-1)^{kt}(\frac tm )e^{-\pi it/m}.$$

Для чётных k на множитель $(-1)^{kt}$ можно не обращать внимания, при k нечётном, в суммировании можно считать k=1.

[maxal]

Окончательно имеем:
коэффициент при $x^k$ в $R(x)$ равен $(-1)^{k+\frac{m-1}{2}} \left(\frac km \right).$ Ура!

[Руст]

Тут у тебя получилось, что все коэффициенты $\pm 1$, вначале вроде были и нули.

[maxal]

Руст писал(а):

Тут у тебя получилось, что все коэффициенты +-1, вначале вроде были и нули.

Тут тоже нули есть. Дело в том, что символ Якоби $\left(\frac km \right)$ равен нулю, если $k$ и $m$ не взаимно-просты, и соответствующий коэффициент многочлена $R(x)$ получается нулевой.

[juna]

maxal писал(а):

Окончательно имеем:
коэффициент при $x^k$ в $R(x)$ равен $(-1)^{k+\frac{m-1}{2}} \left(\frac km \right).$ Ура!

maxal, а можно на полное доказательство посмотреть, интересно.

[maxal]

Кратко обозначу основные шаги.

Сначала пользуясь мультисекцией получаем, что коэффициент при $x^k$ в $R(x)$ равен

$$\frac{1}{m} \sum_{t=0}^{m-1} e^{-i \pi k (2t+1)/m}\prod_{j=1}^{(m-1)/2} (e^{i \pi j (2t+1)/m} - e^{-i \pi j (2t+1)/m})$$

Причем суммирование можно ограничить только теми $t,$ для которых $\gcd(m,2t+1)=1$ (если это не так, то один из сомножителей в произведении равен 0).

Внутреннее произведение - это по сути произведение синусов:

$$\prod_{j=1}^{(m-1)/2} (e^{i \pi j (2t+1)/m} - e^{-i \pi j (2t+1)/m}) = (2i)^{(m-1)/2} \prod_{j=1}^{(m-1)/2} \sin \frac{\pi j (2t+1)}{m}$$

Причем, пользуясь разложением $\sin(m \alpha)$ по степеням $\sin(\alpha),$ нетрудно получить, что

$$\prod_{j=1}^{m-1} \sin \frac{\pi j}{m} = \frac{m}{2^{m-1}}.$$

В нашем произведении участвует ровно половина синусов последнего произведения, но вот знаки у них "блуждающие". Вспомогательная задача как раз и являла целью выяснить знак этого произведения. Теперь мы можем утверждать, что

$$\prod_{j=1}^{(m-1)/2} \sin \frac{\pi j (2t+1)}{m} = \left(\frac{2t+1}{m}}\right) \frac{\sqrt{m}}{2^{(m-1)/2}}.$$

Поэтому наше выражение для коэффициента превращается в

$$\frac{i^{(m-1)/2}}{\sqrt{m}} \sum_{t=0}^{m-1} \left(\frac{2t+1}{m}}\right) e^{-i \pi k (2t+1)/m}.$$

Остальное вы уже знаете.

[nnosipov]

Руст в сообщении #38879 писал(а):

Получилась несколько странная сумма. Но она выражаема через Гауссовы суммы.

$$\sum_{t=0}^{m-1} \left(\frac{2t+1}{m}\right) e^{-\pi i k (2t+1)/m}=\sum_{t=1}^{m-1}(\frac{t}{m})(-1)^{kt}e^{-\pi ikt/m} =(\frac km )\sum_{t=1}^{m-1}(-1)^{kt}(\frac tm )e^{-\pi it/m}.$$

Для чётных k на множитель $(-1)^{kt}$ можно не обращать внимания, при k нечётном, в суммировании можно считать k=1.

Здесь, к счастью, ошибка: в последней сумме вместо $(-1)^{kt}$ должно быть просто $(-1)^t$. Сумма

$$\sum_{t=0}^{m-1}\left(\frac{t}{m}\right)(-1)^te^{-\pi it/m}$$

действительно сводится к гауссовой сумме

$$\sum_{t=0}^{m-1}\left(\frac{t}{m}\right)e^{-2\pi it/m},$$

а вот сумма

$$\sum_{t=0}^{m-1}\left(\frac{t}{m}\right)e^{-\pi it/m}$$

равна не пойми чему.