Скалярное произведение

[Профессор Снэйп]

Тоже несложная задача. Всплывала когда-то давно на форуме НГУ.

Пусть $p$ и $q$ --- натуральные, большие $1$. Вектора $u,v \in \mathbb{R}^{pq}$ заданы следующим образом: для $0 \leqslant n < q$, $0 \leqslant m < p$, $1 \leqslant i \leqslant p$ и $1 \leqslant j \leqslant q$ выполняются равенства $u_{np + i} = (-1)^n$, $v_{mq + j} = (-1)^m$. Выразите скалярное произведение $u \cdot v$ через $p$ и $q$.

[ИСН]

Считать клеточки на шахматной доске? Если оба нечётны, то 1, иначе 0, так, что ли?

[Профессор Снэйп]

ИСН в сообщении #399892 писал(а):

Считать клеточки на шахматной доске? Если оба нечётны, то 1, иначе 0, так, что ли?

Да ну? Возьмём $p = q = 3$, получим $u \cdot v = 9$, не так ли?

[ИСН]

Чёрт. Придётся всё-таки прочитать условие.

[EtCetera]

Легко показать, что при $p=q$ искомое скалярное произведение равно $p^2$. А вот при $p\ne q$...
Ниже приведена табличка значений $u\cdot v$ для $p,q\le 20$.
\begin{tabular}{|c||c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|} \hline & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 \\ \hline\hline 2 & 4 & 0 & 0 & 0 & 4 & 0 & 0 & 0 & 4 & 0 & 0 & 0 & 4 & 0 & 0 & 0 & 4 & 0 & 0 \\ \hline 3 & 0 & 9 & 0 & 1 & 0 & 1 & 0 & 9 & 0 & 1 & 0 & 1 & 0 & 9 & 0 & 1 & 0 & 1 & 0 \\ \hline 4 & 0 & 0 & 16 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 16 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 16 \\ \hline 5 & 0 & 1 & 0 & 25 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 25 & 0 & 1 & 0 & 1 & 0 \\ \hline 6 & 4 & 0 & 0 & 0 & 36 & 0 & 0 & 0 & 4 & 0 & 0 & 0 & 4 & 0 & 0 & 0 & 36 & 0 & 0 \\ \hline 7 & 0 & 1 & 0 & 1 & 0 & 49 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 \\ \hline 8 & 0 & 0 & 0 & 0 & 0 & 0 & 64 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ \hline 9 & 0 & 9 & 0 & 1 & 0 & 1 & 0 & 81 & 0 & 1 & 0 & 1 & 0 & 9 & 0 & 1 & 0 & 1 & 0 \\ \hline 10 & 4 & 0 & 0 & 0 & 4 & 0 & 0 & 0 & 100 & 0 & 0 & 0 & 4 & 0 & 0 & 0 & 4 & 0 & 0 \\ \hline 11 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 121 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 \\ \hline 12 & 0 & 0 & 16 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 144 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 16 \\ \hline 13 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 169 & 0 & 1 & 0 & 1 & 0 & 1 & 0 \\ \hline 14 & 4 & 0 & 0 & 0 & 4 & 0 & 0 & 0 & 4 & 0 & 0 & 0 & 196 & 0 & 0 & 0 & 4 & 0 & 0 \\ \hline 15 & 0 & 9 & 0 & 25 & 0 & 1 & 0 & 9 & 0 & 1 & 0 & 1 & 0 & 225 & 0 & 1 & 0 & 1 & 0 \\ \hline 16 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 256 & 0 & 0 & 0 & 0 \\ \hline 17 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 289 & 0 & 1 & 0 \\ \hline 18 & 4 & 0 & 0 & 0 & 36 & 0 & 0 & 0 & 4 & 0 & 0 & 0 & 4 & 0 & 0 & 0 & 324 & 0 & 0 \\ \hline 19 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 361 & 0 \\ \hline 20 & 0 & 0 & 16 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 16 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 400 \\ \hline \end{tabular}

[Профессор Снэйп]

Ого! Сила есть, ума не надо Неленивый Вы человек, однако!

Чтож, формула явно видна из приведённой таблички

[EtCetera]

Профессор Снэйп

Профессор Снэйп в сообщении #400052 писал(а):

Неленивый Вы человек, однако!

Врожденное чувство справедливости вынуждает меня отклонить столь лестный комплимент. На самом деле табличка получилась столь большой как раз из-за моей лени. Ручками дальше $p,q=4$ считать было скучновато, и железный конь друг мне помог.

Профессор Снэйп в сообщении #400052 писал(а):

формула явно видна из приведённой таблички

Не всем.

[Профессор Снэйп]

(Формула тут, не смотреть!)

$$ u \cdot v = \frac{1 - (-1)^{\frac{pq}{(p,q)^2}}}{2} \cdot (p,q)^2, $$

где $(p,q) = \text{НОД}(p,q)$ --- наибольший общий делитель чисел $p$ и $q$.

[Руст]

Пусть $r=gcd(p,q),p=p_1r,q=q_1r$.
Тогда, если $p_1r_1$ четно, получаем 0, иначе $r^2$.

[Профессор Снэйп]

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

Пусть $r=gcd(p,q),p=p_1r,q=q_1r$.
Тогда, если $p_1r_1$ четно, получаем 0, иначе $r^2$.

Только не $p_1r_1$, а $p_1q_1$

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

[bot]

В частичной формулировке эта задача здесь уже была. Показывать не буду - может быть кто-то придумает 4-е доказательство?

[sup]

Не знаю, как насчет изящества, но простое решение можно получить, используя ряды Фурье. Определим $f(x),g(x)$ следующим образом (если угодно, это просто "непрерывный" аналог векторов)
$f(x)=(-1)^k,kq \leqslant x \leqslant (k+1)q$
$g(x)=(-1)^k,kp \leqslant x \leqslant (k+1)p$
Тогда искомое скалярное произведение - это просто интеграл $S=\int \limits_{0}^{pq}f(x)g(x)dx$.
На интервале $(-1, 1)$ имеем:
$sign(x)=4/{\pi}\sum \limits_{k \geqslant 0}\frac {sin((2k+1)\pi x)}{2k+1}$
Продолжим эту функцию периодическим образом на всю ось и обозначим её как $Sign(x)$. Тогда
$S=\int \limits_{0}^{pq}Sign(x/p)Sign(x/q)dx$.
Далее, замена $x=pqy$. Учитывая ортогональность системы синусов, легко получить
$S=8pq/{{\pi}^2}\sum \limits_{ap=bq}1/ab,$
где суммирование идет по нечетным $a,b$, удовлетворяющим указанному равенству.
Дальше уже дело нехитрой техники. Отмечу лишь, что сумма ряда обратного квадратам равна ${\pi}^2/6$, а значит сумма ряда обратного нечетным квадратам равна ${\pi}^2/8$.

[TOTAL]

ИСН в сообщении #399892 писал(а):

Считать клеточки на шахматной доске? Если оба нечётны, то 1, иначе 0, так, что ли?

Почти так. Рассмотрим шахматную доску взаимно простых размеров $p$ на $q$. Из черного угла отправимся по диагонали по чёрным клеткам. Дойдя до какой-нибудь стороны доски, отразимся, как луч света, и продолжим путь уже по белым клеткам. И так далее. Наступив ровно один раз (очевидно) на каждую из $pq$ клеток, упрёмся в угол доски и остановимся. Цвет очередной проходимой клетки указывает на величину очередного слагаемого в скалярном произведении (чёрный - плюс один, белый - минус один).

[Профессор Снэйп]

Хм... Не поленился, написал решение

Для каждого натурального $r \geqslant 1$ пусть $\psi_r : \mathbb{Z} \to \mathbb{Z}$ такая функция, что $\psi_r(z + r) = \psi_r(z)+1$ для всех $z \in \mathbb{Z}$ и $\psi_r(1) = \ldots = \psi_r(r) = 0$. Пусть теперь $p,q \geqslant 1$ --- натуральные числа и даны вектора $u = (\psi_p(1),\ldots,\psi_p(pq))$, $v = (\psi_q(1),\ldots,\psi_q(pq))$. Надо найти их скалярное произведение

$$ \gamma(p,q) = u \cdot v = \sum_{i=1}^{pq} (-1)^{\psi_p(i)+\psi_q(i)} $$

1) Числа $p$ и $q$ --- нечётные взаимно простые. Пусть для натурального $a \geqslant 1$ отображение $\varphi_a$ есть канонический гомоморфизм абелевой группы $\mathbb{Z}$ в абелеву группу $\mathbb{Z}_a$. Так как $p$ и $q$ взаимно просты, то $(\varphi_p(1),\varphi_q(1))$ --- порождающая циклической абелевой группы $\mathbb{Z}_p \times \mathbb{Z}_q$. Пусть для $i \in [1,pq]$ число $\alpha_i$ равно целому числу из отрезка $[1,p]$, такому что $\varphi_p(\alpha_i) = \varphi_p(i)$ (фактически $\alpha_i$ равно остатку от деления $i$ на $p$, к которому, если он равен $0$, прибавлено $p$). Аналогично пусть $\beta_i$ --- целое число, такое что $1 \leqslant \beta_i \leqslant q$ и $\varphi_q(\beta_i) = \varphi_q(i)$. Нетрудно видеть, что каждое $i \in [1,pq]$ расписывается в виде $i = p \psi_p(i) + \alpha_i = q \psi_q(i) + \beta_i$. Но тогда $1 = (-1)^{2i} = (-1)^{p\psi_p(i) + q\psi_q(i)} \cdot (-1)^{\alpha_i + \beta_i}$ и, в силу нечётности $p$ и $q$, выполняется $(-1)^{\psi_p(i) + \psi_q(i)} = (-1)^{\alpha_i + \beta_i}$. Но тогда

$$ \gamma(p,q) = \sum_{i=1}^{pq} (-1)^{\psi_p(i) + \psi_q(i)} = \sum_{i=1}^{pq} (-1)^{\alpha_i + \beta_i} = \sum_{\alpha = 1}^p \sum_{\beta = 1}^q (-1)^{\alpha + \beta} = 1 $$

2) Числа $p$ и $q$ разной чётности. Заметим, что $\psi_p(pq + 1-z) = q -\psi_p(z)-1$ и, аналогично, $\psi_q(pq + 1-z) = p - \psi_q(z)-1$ для всех $z \in \mathbb{Z}$. Для $i \in [1,pq/2]$ получаем $\psi_p(pq+1-i) + \psi_q(pq+1-i) = (p+q) - (\psi_p(i) + \psi_q(i)) - 2$ и

$$ \gamma(p,q) = \sum_{i=1}^{pq} (-1)^{\psi_p(i)+\psi_q(i)} = \sum_{i=1}^{pq/2} (-1)^{\psi_p(i)+\psi_q(i)} + \sum_{i=1}^{pq/2} (-1)^{\psi_p(pq+1-i)+\psi_q(pq+1-i)} = 0 $$

3) Пусть $p,q,d \geqslant 1$ --- произвольные ненулевые натуральные число. Сначала заметим, что для любых натуральных $r,s \geqslant 1$, $i \in [1,s]$ и целого $j$ выполняется $\psi_{rs}(i + (j-1)s) = \psi_r(j)$. Действительно, при данных условиях и $j \in [1,r]$ выполнено $1 \leqslant i + (j-1)s \leqslant rs$, а добавляя к $j$ число $r$, мы увеличиваем аргумент $\psi_{rs}$ на $rs$. Отсюда получаем

$$ \gamma(dp,dq) = \sum_{i=1}^{d^2pq} (-1)^{\psi_{dp}(i) + \psi_{dq}(i)} = \sum_{i=1}^d \sum_{j=1}^{dpq} (-1)^{\psi_{dp}(i + (j-1)d) + \psi_{dq}(i + (j-1)d)} = \sum_{i=1}^d \sum_{j=1}^{dpq} (-1)^{\psi_p(j) + \psi_q(i)} $$

Далее, для любого $z \in\mathbb{Z}$ справедливо $\psi_p(z + kpq) + \psi_q(z + kpq) = \psi_p(z) + \psi_q(z) + k(p + q)$, так что

$$ \gamma(dp,dq) = \sum_{i=1}^d \sum_{j=1}^{dpq} (-1)^{\psi_p(j) + \psi_q(i)} = d \sum_{k=0}^{d-1} \sum_{j=1}^{pq} (-1)^{\psi_p(j) + \psi_q(j)} \cdot (-1)^{k(p+q)} = d \gamma(p,q) \sum_{k=0}^{d-1} (-1)^{k(p+q)} $$

Теперь если число $p + q$ чётное, то сумма по $k$ равна $d$ и $\gamma(dp,dq) = d^2 \gamma(p,q)$. Если же $p+q$ нечётно, то $p$ и $q$ разной чётности, $\gamma(p,q) = 0$, $\gamma(dp,dq) = 0$ и всё равно $\gamma(dp,dq) = d^2 \gamma(p,q)$. Во всех случаях получаем

$$ \gamma(dp,dq) = d^2 \gamma(p,q) $$

[Профессор Снэйп]

А интересно, как-нибудь через линейную алгебру можно?

Вот есть на $\mathbb{R}^{pq}$ линейный оператор

$$ \varphi : (x_1, \ldots, x_{pq}) \mapsto (0,x_1,\ldots,x_{pq-1}) $$

Ну и пусть $e = (1,0,\ldots,0)$. Положим $w_r = (1 + \varphi + \ldots + \varphi^{r-1})e$. У нас вектора $u = (1 - \varphi^p + \varphi^{2p} - \ldots - (-1)^q \varphi^{(q-1)p})w_p$ и $v = (1 - \varphi^q + \varphi^{2q} - \ldots - (-1)^p \varphi^{(p-1)q})w_q$, надо посчитать их скалярное произведение.

Значиццо што? $(1 + \varphi + \ldots + \varphi^{r-1})(1 - \varphi) = 1 - \varphi^r$. Оператор $1 - \varphi$ невырожден, потому что у него матрица верхнетреугольная с единицами на диагонали. Значит,

$$ w_r = (1-\varphi^r)(1-\varphi)^{-1}e$ $$

Далее,

$$ \begin{array}{rcccl} u & = & (1 + \varphi^p)^{-1}w_p & = & (1 + \varphi^p)^{-1}(1-\varphi^p)(1-\varphi)^{-1}e \\ v & = & (1 + \varphi^q)^{-1}w_q & = & (1 + \varphi^q)^{-1}(1-\varphi^q)(1-\varphi)^{-1}e \end{array} $$

Вектор $(1-\varphi)^{-1}e$ равен $(1,1,\ldots,1)$, обозначим его $e_0$. Ага!..

$$ \begin{array}{rcl} (1 + \varphi^p) u & = & (1-\varphi^p)e_0 \\ (1 + \varphi^q) v & = & (1-\varphi^q)e_0 \end{array} $$

Дальше не знаю, что делать. Забыл всё, чему в универе учили