Putnam 2012 обобщение B6 - гипотезы

[Sonic86]

Задача В6 следующая (взял тут):

dm в сообщении #653395 писал(а):

B6
Пусть $p$ --- нечетное простое такое что $p\equiv 2\pmod{3}.$
Определим перестановку
$\pi$ остатков по модулю $p$ формулой $\pi(x)\equiv x^3\pmod{p}.$
Докажите, что перестановка $\pi$ четная если и только
если $p\equiv 3\pmod{4}.$

Как ее доказывать, я вообще не представляю и не понимаю, потому попытался обобщить. Получил следующие гипотезы:

1. Пусть $n$ нечетно, свободно от квадратов. Пусть $\pi_{n,d}(x)\equiv x^d\pmod n$ - перестановка $\mathbb{Z}_n^\times$ (это будет в точности для всех $d:\gcd(d,\varphi(n))=1$). Тогда $\pi$ - четная перестановка для всех $d$ $\Leftrightarrow$ в каноническом разложении $n$ число различных простых вида $p\equiv 1\pmod 4$ четно. В частности, если $n$ разлагается на произведение простых вида $p\equiv -1\pmod 4$, то все перестановки $\pi_{n,d}$ нечетны
В случае остальных $n$ имеют место как четные, так и нечетные перестановки, причем перестановок обеих типов одинаковое число (легко доказать одинаковость числа четных и нечетных перестановок в соответствующим случае).
2. Четность перестановки $x\to x^d\pmod n$ равна сумме четностей перестановок $x\to x^d\bmod {p_j}$, т.е. $s(\pi_{n,d})\equiv \sum\limits_{p\mid n}s(\pi_{p,d})\pmod 2$
3. Если $d\equiv 1\pmod 4$, то для любого $n$, свободного от квадратов, все . перестановки $\pi_{n,d}: x\tox^d\pmod n$ четны. В случае $d\equiv -1\pmod 4$ могут быть как четны, так и нечетны. Случай $d=3$ описан, при $d=5$ все перестановки $\pi_{n,5}$ четны, при $d=7$ (и прочих) описать затрудняюсь.

[zhoraster]

Как решать саму задачу, понятно: $\mathbb{Z}_p^*$ циклическая, поэтому в сущности задача про перестановку, заданную умножением на $3$ в $\mathbb{Z}_{p-1}$.

Только что дальше, не знаю. Единственное, что пока пришло в голову -- если не найдется такого $k$, что $3^k = -1\pmod {p-1}$, то перестановка четная. (Тогда циклы в перестановке очевидно разбиваются на пары.)

-- Чт дек 06, 2012 19:44:36 --

Второе, что пришло в голову -- если $\operatorname{ord}_{p-1} 3$ нечетный, то в перестановке вообще все циклы нечетные.

[Sonic86]

zhoraster в сообщении #655166 писал(а):

Только что дальше, не знаю. Единственное, что пока пришло в голову -- если не найдется такого $k$, что $3^k = -1\pmod {p-1}$, то перестановка четная. (Тогда циклы в перестановке очевидно разбиваются на пары.)

Я считал несколько перестановок явно: там встречаются и перестановки с длиной циклов равным 4. И вообще, думается, что длина цикла в общем случае не ограничена.
Я их много посчитать могу, но это, наверное, бесполезно.

(Оффтоп)

Я вообще не понимаю: каким боком тут четность цикла!? Меня поражает просто.

[zhoraster]

(Оффтоп)

Решил посмотреть, бывает ли такое (второе, что пришло в голову) вообще и нашел ошибку в OEIS, которая утверждает, что $\operatorname{ord}_{112}3=39$, это неверно: на самом деле $\operatorname{ord}_{112}3=12$. А я уже испугался, что что-то не так понимаю.

-- Чт дек 06, 2012 20:42:20 --

А насчет первого я соврал. (У меня почему-то и $p$, и $p-1$ простые.)

-- Чт дек 06, 2012 20:49:56 --

Ага, в одну сторону получилось вроде.

Пытаемся разбить циклы по парам: для $x\neq 0$

$$ x\to x^3\to x^9\to\dots $$

и

$$ -x\to -x^3\to -x^9\to\dots $$

Если не получилось разбить по парам, значит, для каких-то $x$ и $k\ge 1$ имеем $x^{3^k} = -x \pmod p$, то есть $x^{3^{k}-1} = -1 \pmod p$. Тогда $-1$ -- квадратичный вычет, то есть мы доказали... эмм... Необходимость.

[zhoraster]

Идея достаточности: в этом случае $-1$ -- квадратичный вычет. Пусть $i^2=-1\pmod p$. В этом случае разбиваем на пары так, как раньше. То, что не получилось разбить (то есть то, что "спаривается" с собой), разбиваем на пары

$$x\to x^3\to\dots\to -x \to -x^3\to\dots$$

и

$$ix\to -ix^3\to\dots\to -ix \to ix^3\to\dots$$

Вот теперь смелое утверждение, которое я не доказал и которое вообще, может быть, неверное: разобьется все, кроме цикла $i\to -i$. То есть перестановка нечетная.

[Sonic86]

zhoraster в сообщении #655178 писал(а):

Пытаемся разбить циклы по парам: для $x\neq 0$

$$ x\to x^3\to x^9\to\dots $$

и

$$ -x\to -x^3\to -x^9\to\dots $$

Если не получилось разбить по парам, значит, для каких-то $x$ и $k\ge 1$ имеем $x^{3^k} = -x \pmod p$, то есть $x^{3^{k}-1} = -1 \pmod p$. Тогда $-1$ -- квадратичный вычет, то есть мы доказали... эмм... Необходимость.

Не понял
Вы рассматриваете варианты, в которых $\pi$ имеет $1$ или $2$ цикла? Просто $3$ - почти всегда не образующая $\mathbb{Z}_{p-1}^\times$ (это вообще циклическая группа только для простых Жермен), потому, даже если выделить циклы $(x \ x^3 \ x^9 \ ...)$ и $(-x \ -x^3 \ -x^9 \ ...)$, то это почти всегда будут не все циклы. И еще мне непонятно, как соотносятся четность перестановки и длина или количество ее циклов? Я думал, что почти никак.

zhoraster в сообщении #655209 писал(а):

Вот теперь смелое утверждение, которое я не доказал и которое вообще, может быть, неверное: разобьется все, кроме цикла $i\to -i$. То есть перестановка нечетная.

Тоже не уверен, что оно верно по причинам выше.

Я посчитаю несколько перестановок и тут выложу.

[zhoraster]

Четность перестановки и ее циклы связаны очень просто: четность перестановки совпадает с четностью количества четных циклов, которые она содержит.

Я не рассматриваю варианты, в которых у $\pi$ один или два цикла. И не рассматриваю варианты, является $3$ образующей или нет. Мне это не важно. Я разбиваю циклы на пары, причем все (не только какие-то два, которые я написал). И утверждаю, что, если $-1$ не является квадратичным вычетом, то у меня это получится. (Кстати, я доказал все же достаточность, это я все время их путаю.)

[zhoraster]

Кажись придумал. Давайте попробуем доказать необходимость по-честному (напомню, что доказал я достаточность).

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

Итак, пусть $p=2\pmod 3$, $p=1\pmod 4$, то есть $p=12k+5$.

Вспомним, что группа $\mathbb Z_p^*$ циклическая. Пусть $p-1 = 2^k m$, $k\ge 2$, $m$ нечетно. Тогда $\mathbb Z_p^* \simeq \mathbb Z_{2^k}\times \mathbb Z_m $. Будем теперь считать циклы в последнем. Пусть $(a,b)\in \mathbb Z_{2^k}\times \mathbb Z_m$ и $b\neq 0$. Рассмотрим цикл $(a,b)\to (3a,3b)\to \dots$ Его длина равна НОК длин циклов $a\to 3a\to \dots$ и $b\to 3b\to \dots$. Посмотрим на длину $c(a)$ первого.

Несложно доказать, что

$$\operatorname{ord}_{2^n} 3 = \begin{cases} 2^{n-2}, &n\ge 3,\\ 2^{n-1}, &n=1,2.\end{cases}$$

Пусть $a\div 2^{k-r}$, $r\ge 3$. Имеем $a 3^{l} = a\pmod {2^k}\Leftrightarrow 3^{l} = 1\pmod {2^r}$. Отсюда $c(a)=2^{r-2}$. Таких $a$ $2^{r-1}$ штук и каждое из них входит в цикл длины $2^{r-2}$. То есть таких циклов четное количество, и они не влияют на четность перестановки.

Поэтому остались варианты: $a=0,2^{k-1},\pm 2^{k-2}$. Сейчас мы докажем, что с ними нечетное количество четных циклов. С первыми двумя все просто: цикл $(0,b)$ спариваем с циклом $(2^{k-1},b)$ и общее количество четное (NB в терминах $\mathbb Z_p^*$ это именно то самое спаривание цикла с противоположным).

Теперь пусть $b$ содержится в четном цикле $b \to 3b \to 3^2 b\to \dots$. Ему соответствуют два цикла с $a=\pm 2^{k-2}$:

$$ (2^{k-2},b) \to (-2^{k-2},3 b)\to (2^{k-2},3^2 b)\to\dots $$

и

$$ (-2^{k-2},b) \to (2^{k-2},3 b)\to (-2^{k-2},3^2 b)\to\dots $$

То есть общее количество таких циклов будет четное.

Если же $b$ -- нечетное, и $a = \pm 2^{k-2}$, то $(a,b)$ входит в четный цикл (просто потому, что цикл $a$ четный). Но количество нечетных циклов на $C_m$ нечетно, ведь $m$ нечетно! И каждому из них соответствует ровно один цикл с $a = \pm 2^{k-2}$. Значит, получается нечетное количество четных циклов. Поскольку до этого у нас было четное количество четных циклов, то общее количество нечетно, что и требовалось доказать.

Фух.

-- Пт дек 07, 2012 02:28:53 --

Кстати, в необходимости мы простоту $p$ полностью не использовали, только цикличность группы.

В достаточности она действительно нужна, потому что мы там на что-то сокращаем. (Хотя, может быть, можно как-то так же, как необходимость, доказать, не используя простоту $p$.)

[Sonic86]

zhoraster в сообщении #655292 писал(а):

Четность перестановки и ее циклы связаны очень просто: четность перестановки совпадает с четностью количества четных циклов, которые она содержит.

Я не рассматриваю варианты, в которых у $\pi$ один или два цикла. И не рассматриваю варианты, является $3$ образующей или нет. Мне это не важно. Я разбиваю циклы на пары, причем все (не только какие-то два, которые я написал). И утверждаю, что, если $-1$ не является квадратичным вычетом, то у меня это получится.

Ага! Я понял! Каждому циклу $c=(x \ x^3 \ x^9 \ ...)$ ставим в соответствие $c'=(-x \ -x^3 \ -x^9 \ ...)$. Пары $\binom{... \ i \ ... \ j \ ...}{... \pi(i) ... \pi(j) ...}$ переходят в $\binom{\ ... \ p-i \ ... \ p-j \ ...}{... p-\pi(i) ... p-\pi(j) ...}$ и тогда если $\pi(i)\star\pi(j)$, то $\pi(i)\overline{\star}\pi(j)$, где $\star\in\{<;>\}$, но $p-i<p-j$, значит по данной паре $(i;j)$ слагаемые, составляющие четность, совпадают и тогда, если циклы различны, то их произведение - четная перестановка. Остальное Вы написали явно

Здесь $p$ можно заменить на $n$, $3$ - на $d$.

-- Пт дек 07, 2012 17:47:25 --

В обратную сторону завтра осилю...

[Sonic86]

Опять не понимаю
Зачем Вы рассматриваете длины циклов?:

zhoraster в сообщении #655358 писал(а):

Его длина равна НОК длин циклов $a\to 3a\to \dots$ и $b\to 3b\to \dots$. Посмотрим на длину $c(a)$ первого.

zhoraster в сообщении #655358 писал(а):

Отсюда $c(a)=2^{r-2}$. Таких $a$ $2^{r-1}$ штук и каждое из них входит в цикл длины $2^{r-2}$. То есть таких циклов четное количество, и они не влияют на четность перестановки.

И как Вы ушли от сравнения $x^{3^t-1}\equiv -1\pmod p$?

Я пока пытаюсь решить аналогичным способом: разбиваем циклы на пары: $x\to x^3\to x^9\to...$ и $-x\to -x^3\to -x^9\to...$. Если эти циклы не совпадают, то их произведение - четная перестановка. Значит можно искать все $x:(\exists t) x^{3^t-1}\equiv -1\pmod p$ и разбивать их на классы по отношению $y=x^3$. Переходим от $\mathbb{Z}_p^\times$ к $\mathbb{Z}_{2^k}\times\mathbb{Z}_m, 2\nmid m$. Тогда каждому решению уравнения $x:(\exists t) x^{3^t-1}\equiv -1\pmod p$ биективно соответствует пара $(a,b)$: $3^ta\equiv 2^{k-1}+a\pmod{2^k}, 3^tb\equiv b \pmod m$ (элементу $-1$ соответствует пара $(2^{k-1},0)$).
Решаем 1-е:
$3^ta\equiv 2^{k-1}+a\pmod{2^k}$
$(3^t-1)a\equiv 2^{k-1}\pmod{2^k}$
$3^t-1=2^vq, q\nmid q, v<k$
$qa\equiv 2^{k-1-v}\pmod{2^{k-v}}$
$a=2^{k-1-v}a_1$
$qa_1\equiv 1\pmod 2, a_1 := q^{-1} \pmod 2$
$1\leqslant a\leqslant 2^k\Leftrightarrow 1\leqslant a_1\leqslant 2^{v+1}$ решений для заданного $v$, значит всего $\sum\limits_{v=1}^{k-1}2^{v+1}=2^{k+1}-2^2$ решений. Число $b$ подбирается из соотношения $m\mid b(3^t-1)$. А сколькими способами оно подбирается? А как это все потом на классы разбивать?

[zhoraster]

Sonic86 в сообщении #656084 писал(а):

Зачем Вы рассматриваете длины циклов?

zhoraster в сообщении #655292 писал(а):

Четность перестановки и ее циклы связаны очень просто: четность перестановки совпадает с четностью количества четных циклов, которые она содержит.

-- Пн дек 10, 2012 20:15:27 --

Sonic86 в сообщении #656084 писал(а):

И как Вы ушли от сравнения $x^{3^t-1}\equiv -1\pmod p$?

Дело в том, что теперь я почти не строю соответствий, просто считаю четные циклы. Это муторно, но осуществимо.

[Sonic86]

zhoraster в сообщении #656699 писал(а):

Sonic86 писал(а):

Зачем Вы рассматриваете длины циклов?

zhoraster писал(а):

Четность перестановки и ее циклы связаны очень просто: четность перестановки совпадает с четностью количества четных циклов, которые она содержит.

Ну! Вы же не рассматриваете четность циклов или их количество (т.е. количество рассматриваете, но кол-во каких циклов - четных или нечетных?). Вы только их длины рассматриваете...
Не понимаю

[zhoraster]

Четный цикл - это цикл четной длины, прошу прощения за некоторую вольность в терминологии.

В принципе, меня интересует больше не длина, а ее четность. Или для какой-то длины я доказываю, что циклов такой длины четное количество (и они потому не влияют на четность перестановки).

[Sonic86]

zhoraster в сообщении #656707 писал(а):

Четный цикл - это цикл четной длины, прошу прощения за некоторую вольность в терминологии.

В смысле??? Четный цикл - это цикл из $A_n$, т.е. цикл, являющийся произведением четного числа транспозиций! $(132)$ - четный цикл, $(12)$ - нечетный.
Я для них статистику строил - в пределах $n\leqslant 80$ свободных от квадратов все правильно. Могу и дальше подсчитать...

[zhoraster]

Sonic86, ну я так назвал, что поделать. (И даже извинился.) В Вашем смысле четный цикл - цикл нечетной длины, а нечетный цикл - цикл четной длины.