Эллиптическая последовательность делимости

В математике эллиптическая последовательность делимости ( EDS ) — это последовательность целых чисел, удовлетворяющая нелинейному рекурсивному соотношению, возникающему в результате деления полиномов на эллиптических кривых . EDS были впервые определены и изучены их арифметические свойства Морганом Уордом. в 1940-х годах. Они привлекали лишь спорадическое внимание примерно до 2000 года, когда EDS стали рассматривать как класс нелинейных повторений, которые более поддаются анализу, чем большинство таких последовательностей. Такая управляемость обусловлена ​​прежде всего тесной связью EDS и эллиптических кривых. Помимо внутреннего интереса, который EDS представляет для теории чисел, EDS имеет приложения и в других областях математики, включая логику и криптографию .

Определение

(Невырожденная) эллиптическая последовательность делимости (EDS) — это последовательность целых чисел ( W _n ) _{n ≥ 1} определяется рекурсивно четырьмя начальными значениями Ж ₁ , Ж ₂ , Ж ₃ , Ж ₄ , с W ₁ W ₂ W ₃ ≠ 0 и с последующими значениями, определяемыми по формулам

${\begin{aligned}W_{2n+1}W_{1}^{3}&=W_{n+2}W_{n}^{3}-W_{n+1}^{3}W_{n-1},\qquad n\geq 2,\\W_{2n}W_{2}W_{1}^{2}&=W_{n+2}W_{n}W_{n-1}^{2}-W_{n}W_{n-2}W_{n+1}^{2},\qquad n\geq 3,\\\end{aligned}}$

Можно показать, что если W ₁ делит каждое из W ₂ , W ₃ , W ₄ и если далее W ₂ делит W ₄ , то каждый член W _n в последовательности является целым числом.

Свойство делимости

EDS — это последовательность делимости в том смысле, что

$m\mid n\Longrightarrow W_{m}\mid W_{n}.$

В частности, каждый терм в EDS делится на W ₁ , поэтомуEDS часто нормализуется так, чтобы W ₁ = 1, путем деления каждого члена на начальный.

Любые три целых числа b , c , d с d, делящимся на b, приводит к нормализованному EDS при настройке

$W_{1}=1,\quad W_{2}=b,\quad W_{3}=c,\quad W_{4}=d.$

Не очевидно, но можно доказать, что условие b | d достаточно, чтобы гарантировать, что каждый членв последовательности является целым числом.

Общая рекурсия

Фундаментальное свойство последовательностей эллиптической делимости.заключается в том, что они удовлетворяют общему рекурсивному соотношению

$W_{n+m}W_{n-m}W_{r}^{2}=W_{n+r}W_{n-r}W_{m}^{2}-W_{m+r}W_{m-r}W_{n}^{2}\quad {\text{for all}}\quad n>m>r.$

(Эта формула часто применяется при r = 1 и W ₁ = 1.)

Несингулярная ЭДС

Дискриминантом нормализованной ЭЦП является величина

$\Delta =W_{4}W_{2}^{15}-W_{3}^{3}W_{2}^{12}+3W_{4}^{2}W_{2}^{10}-20W_{4}W_{3}^{3}W_{2}^{7}+3W_{4}^{3}W_{2}^{5}+16W_{3}^{6}W_{2}^{4}+8W_{4}^{2}W_{3}^{3}W_{2}^{2}+W_{4}^{4}.$

ЭДС является неособой, если ее дискриминант не равен нулю.

Примеры

Простым примером EDS является последовательность натуральных чисел 1, 2, 3,... . Другим интересным примером является (последовательность A006709 в OEIS ) 1, 3, 8, 21, 55, 144, 377, 987,... состоящая из всех остальных членов последовательности Фибоначчи , начиная со второго члена. Однако обе эти последовательности удовлетворяют линейной рекуррентности и обе являются сингулярными EDS. Примером неособого EDS является (последовательность A006769 в OEIS )

${\begin{aligned}&1,\,1,\,-1,\,1,\,2,\,-1,\,-3,\,-5,\,7,\,-4,\,-23,\,29,\,59,\,129,\\&-314,\,-65,\,1529,\,-3689,\,-8209,\,-16264,\dots .\\\end{aligned}}$

Периодичность ЭЦП

Последовательность ( An _. ) _{n ≥ 1} называется периодической если существует число N ≥ 1, точто An _+N = An _для любого n ≥ 1.Если невырожденная ЭДС ( W _n ) _{n ≥ 1} периодична, то один из ее членов обращается в нуль. Наименьший r ≥ 1 с W _r = 0 называется рангом появления ЭДС. Глубокая теорема Мазура подразумевает, что если ранг появления EDS конечен, то он удовлетворяет условию r ≤ 10 или r = 12.

Эллиптические кривые и точки, связанные с EDS

Уорд доказывает, что с любой неособой EDS ( W _n )— эллиптическая кривая E / Q и точка P ε E ( Q ) такой, что

$W_{n}=\psi _{n}(P)\qquad {\text{for all}}~n\geq 1.$

Здесь ψ _n — n полином деления из Е ; корнями ψ _n являютсяненулевые точки порядка n на E . Естьсложная формула для E и P терминах W1 _​ , W2 _​ , W3 _​ и W4 _в .

Существует альтернативное определение EDS, которое напрямую использует эллиптические кривые и дает последовательность, которая с точностью до знака почти удовлетворяет рекурсии EDS. Это определение начинается с эллиптической кривой E / Q, заданной уравнением Вейерштрасса, и точки некручения P ε E ( Q ). записываются Координаты x кратных P как

$x(nP)={\frac {A_{n}}{D_{n}^{2}}}\quad {\text{with}}~\gcd(A_{n},D_{n})=1~{\text{and}}~D_{n}\geq 1.$

Тогда последовательность ( Dn ₎ также называется последовательностью эллиптической делимости . Это последовательность делимости, и существует целое число k такое, что подпоследовательность ( ± D _nk ) _{n ≥ 1} (при соответствующем выборе знаков) является EDS в прежнем смысле.

Рост ЭЦП

Пусть ( W _n ) _{n ≥ 1} — неособая ЭДСэто не периодичность. Тогда последовательность растет квадратично экспоненциально в том смысле, что существуетположительная константа h такая, что

$\lim _{n\to \infty }{\frac {\log |W_{n}|}{n^{2}}}=h>0.$

Число h — каноническая высота точки на эллиптическая кривая, связанная с EDS.

Простые числа и примитивные делители в EDS

Предполагается, что неособая ЭДС содержит лишь конечное число простые числа Однако все члены неособой EDS, кроме конечного числа, допускают примитивное простое число. делитель. Таким образом, для всех, кроме конечного числа n , существует простое число p такое, что делит Wn , _p но p не делит для _n всех m < . Wm Это утверждение является аналогом теоремы Жигмонди .

ЭДС над конечными полями

EDS над конечным полем F _q или, в более общем смысле, над любым полем, представляет собой последовательность элементов этого поля, удовлетворяющую рекурсии EDS. ЭДС над конечным полем всегда периодична и, следовательно, имеет ранг появления r . Тогда период ЭДС над F _q имеет вид rt , где r и t удовлетворяют условиям

$r\leq \left({\sqrt {q}}+1\right)^{2}\quad {\text{and}}\quad t\mid q-1.$

Точнее, есть элементы A и B. в F _q ^* такой, что

$W_{ri+j}=W_{j}\cdot A^{ij}\cdot B^{j^{2}}\quad {\text{for all}}~i\geq 0~{\text{and all}}~j\geq 1.$

Значения A и B связаны с Спаривание Тейта точки на соответствующей эллиптической кривой.

Применение ЭЦП

Бьорн Пунен применил EDS к логике. Он использует существование примитивных делителей в EDS на эллиптических кривых ранга один, чтобы доказать неразрешимость десятой проблемы Гильберта над некоторыми кольцами целых чисел.

Кэтрин Э. Стэндж применил EDS и их обобщения более высокого ранга, называемые эллиптическими сетями. к криптографии. Она показывает, как можно использовать EDS для расчета стоимости. спариваний Вейля и Тейта на эллиптических кривых над конечнымиполя. Эти пары имеют множество применений в криптографии на основе пар .

Дополнительный материал

• Г. Эверест, А. ван дер Портен, И. Шпарлински и Т. Уорд. Рекуррентные последовательности , том 104 Математических обзоров и монографий . Американское математическое общество, Провиденс, Род-Айленд, 2003. ISBN   0-8218-3387-1 . (Глава 10 находится в EDS.)
• Р. Шипси. Последовательности эллиптической делимости. Архивировано 9 июня 2011 г. в Wayback Machine . Докторская диссертация, Голдсмитс-колледж (Лондонский университет), 2000 г.
• К. Штанге. Эллиптические сети . Кандидатская диссертация, Университет Брауна, 2008 г.
• К. Сварт. Последовательности, связанные с эллиптическими кривыми . Кандидатская диссертация, Ройял Холлоуэй (Лондонский университет), 2003 г.

Внешние ссылки

• Веб-страница EDS Грэма Эвереста. Архивировано 11 апреля 2009 г. в Wayback Machine.
• Простые значения последовательностей эллиптической делимости.
• Лекция о p -адических свойствах последовательностей эллиптической делимости.