линейная независимость

[iou]

Рассмотрим такие формальные степенные ряды $e_i = \sum_{s \ge 1} x^{i+2s} \binom{i+2s-1}{i-1}$ для каждого $i \ge 1$, но думать я буду про них как про элементы в $\mathbb{F}_3 [[x]]$, то есть коэффициенты рассматриваются по модулю 3. Я хочу доказать, что образы элементов $e_1, .., e_k$ линейно независимы как вектора в $\mathbb{F}_3[x]/x^{3k+1}.$

Я попытался доказать это в лоб, но у меня не получилось. А именно, пусть $e_{k+1} = \sum_{i=1}^k a_i e_i$ в $\mathbb{F}_3[x]/x^{3k+4}$, тогда сравнивая коэффициенты получим, что $\sum_{s} a_{j-2s} \binom{j-1}{j-2s-1} = \binom{j-1}{k},$ если $k+3 \le j \le 3k+3$ и $j \equiv k+1 \mod 2$ где суммирование слева идёт по всем индексам $s \ge 1$, что $1 \le j-2s \le k$. Если же $j \equiv k \mod 2,$ то $\sum_{s} a_{j-2s} \binom{j-1}{j-2s-1} = 0,$ поскольку у $e_{k+1}$ слагаемые имеют вид $b_t x^{k+1+2t}$. Если же $3 \le j \le k+2$, то получается что $\sum_{s \ge 1} a_{j-2s} \binom{j-1}{j-2s-1} = 0$ опять же в допустимой зоне суммирования.
Получается некоторая система линейных уравнений от $a_1, .., a_k$, но я не вижу почему она несовместная.

P.S. Я не уверен на 100%, что это утверждение верно. Но с высокой вероятностью оно верно и я проверил его до $k=8$.

[Null]

$x^{-3}e_i$ образуют треугольную матрицу с $1$ на диагонали?

[iou]

Null в сообщении #1556887 писал(а):

$x^{-3}e_i$ образуют треугольную матрицу с $1$ на диагонали?

Если я Вас правильно понял, то нет; не образуют. У $e_k$ может не быть члена $x^{k+2}$, поскольку биномиальный коэффициент может занулиться. Например, для $k=2$ получается утверждение, что $e_1=x^3+x^5, e_2=2x^6$ независимы в $\mathbb{F}_3 [x]/x^7$, в частности на диагонали только один ненулевой элемент.
Первый "нетривиальный" пример это $k=4$, тогда получается утверждение, что $e_1=x^3+x^5+..+x^{11}, e_2=2x^6+x^8+2x^{12}, e_3=x^9, e_4=x^6+2x^8$ независимы в $\mathbb{F}_3[x]/x^{13}$. Как Вы можете видеть, $e_2$ и $e_4$ очень похожи, а именно $e_4=2e_2$ в $\mathbb{F}_3[x]/x^{12}$, но в $\mathbb{F}_3[x]/x^{13}$ они уже независимы из-за члена $2x^{12}$ в $e_2$! Этот пример наводит меня на мысль, что нет совсем тривиальной причины почему утверждение верно.

[nnosipov]

iou в сообщении #1556921 писал(а):

нет совсем тривиальной причины почему утверждение верно

Тоже так показалось. Надо изучать поведение биномиальных коэффициентов по модулю 3, после чего надеяться, что сыщется ненулевой минор порядка $k$.

[xagiwo]

Действительно линейно независимы (я нарисовал треугольник Паскаля, увидел что-то вроде периодичности [хотя постфактум вижу, что она видна и без Паскаля] и у меня получилось действовать так, как будто $e_i = \sum_{s \ge 0} x^{i+2s} \binom{i+2s-1}{i-1}$ — в таком случае матрица действительно треугольная с $1$ на диагонали). А откуда взялась задача, если не секрет?

[iou]

xagiwo в сообщении #1557061 писал(а):

[хотя постфактум вижу, что она видна и без Паскаля] и у меня получилось действовать так, как будто $e_i = \sum_{s \ge 0} x^{i+2s} \binom{i+2s-1}{i-1}$ — в таком случае матрица действительно треугольная с $1$ на диагонали).

А можете объяснить про какую периодичность Вы говорите и как это помогает свести к $e_i = \sum_{s \ge 0} x^{i+2s} \binom{i+2s-1}{i-1}$? Я долго смотрел на эти полиномы и не смог увидеть никакой простой периодичности.

xagiwo в сообщении #1557061 писал(а):

А откуда взялась задача, если не секрет?

Конечно, не секрет: если кратко, то можно посмотреть на такое преобразование $\mathbb{F}_3 [x]/x^n,$ которое переводит $x$ в $\frac{x}{1-x}.$ И я пытаюсь понять структуру инвариантных полиномов относительно такого преобразования.

[xagiwo]

iou в сообщении #1557062 писал(а):

А можете объяснить про какую периодичность Вы говорите

$\binom{n}{i} = \binom{n + 3^k}{i} = \binom{n + 2 \cdot 3^k}{i},$ если $3^k > n \geqslant 0$ и $3^k > i$

[iou]

xagiwo в сообщении #1557063 писал(а):

$\binom{n}{i} = \binom{n + 3^k}{i} = \binom{n + 2 \cdot 3^k}{i},$ если $3^k > n \geqslant 0$ и $3^k > i$

Я посидел несколько часов пытаясь довести задачу используя это наблюдение, но у меня не получилось. А именно я не понимаю про сведение к треугольной матрице с $1$ на диагонали. Например, для $k=5$ имеем $e_3=x^9 + x^{15}$ и $e_5=x^{9}+2x^{15}$. Я что-то упускаю?

[xagiwo]

(Неправильное решение)

Пусть, в Ваших обозначениях, $3^l \geq k$. Тогда коэфф-ты при $x$ в степенях $2 \cdot 3^l$, ... , $2 \cdot 3^l + k - 1$ у векторов $e_1,...,e_{k}$ образуют треугольную матрицу с $1$ на диагонали. Недостижение $s=0$ решается сдвигом нумерации на $3^l$ влево.

Извините, кажется, я идиот. Я доказывал линейную независимость "вообще", а не ограничившись степенями до $3k+1$. Моё решение тогда сработает только когда $k$ — степень тройки.

[iou]

xagiwo в сообщении #1557079 писал(а):

Моё решение тогда сработает только когда $k$ — степень тройки.

Красивое замечание!
Но я не уверен, что это работает. А именно: Вы объяснили как найти единичную диагональ в этой матрице, но дело в том, что над этой диагональю есть ненулевые элементы и это, как мне кажется, не позволяет сделать вывода о ранге (ведь мы хотим аналог нижнетреугольной матрицы с $1$ на диагонали). Например, если $k=9$, то Ваш рецепт выглядит так: заметим, что у $e_1$ есть моном $x^{19}$, у $e_2$ есть моном $x^{20}, \cdots,$ а у $e_9$ есть моном $x^{27}$. Но, например, моном $x^{26}$, который мы присвоили $e_6$, он есть также и у $e_2$ и у $e_4$. Вы можете представить себе блочную матрицу $1000 \times 1000,$ у которой три блока нулевые, а нижний левый $500 \times 500$ блок состоит полностью из единиц, у неё есть единичная диагональ длины 500, но её ранг 1. Или я не так понял Вашу идею?

[xagiwo]

iou в сообщении #1557082 писал(а):

Но, например, моном $x^{26}$, который мы присвоили $e_6$, он есть также и у $e_2$ и у $e_4$.

А может, этого монома не будет у $e_7, e_8, e_9$? Мне почему-то казалось, что матрица будет треугольной, верхне- или нижне-.

В качестве извинений за потраченное время (хотя Вам, может, это уже известно): есть простой способ считать биномиальные коэфф-ты $\mod 3$ https://en.wikipedia.org/wiki/Lucas%27s_theorem