Seminar on Computer Algebra, CMC faculty of MSU & CCAS / Cеминар «Компьютерная алгебра» факультета ВМК МГУ и ВЦ РАН
Contact Persons: Sergei Abramov (sergeyabramov [AT] mail [DOT] ru), Alla Bogolubskaya (abogol [AT] jinr [DOT] ru), Anna Ryabenko (anna [DOT] ryabenko [AT] gmail [DOT] com) / Контактные лица: Сергей Александрович Абрамов (sergeyabramov [AT] mail [DOT] ru), Алла Анатольевна Боголюбская (abogol [AT] jinr [DOT] ru), Анна Андреевна Рябенко (anna [DOT] ryabenko [AT] gmail [DOT] com).
Russian Computer Algebra Community page
Computer algebra seminar of Limoges University, France
From the history of computer algebra / Из истории компьютерной алгебры:
Next meeting/Следующее заседание
Очередное заседание семинара «Компьютерная алгебра» состоится в среду 15 января 2025 года в 16:30 по московскому времени в дистанционном режиме через Zoom. Cоответствующая ссылка для подключения будет сообщена письмом приглашенным участникам.
Jean-Paul Allouche, Michel Mendès France. Automata and automatic sequences.
И.В.Горючкина (ИПМ им. М.В. Келдыша РАН, Москва). Доклад основан на совместной работе с Р.Р.Гонцовым.
О неформальных решениях уравнения Малера
Аннотация
Аналитические уравнения Малера — это функциональные уравнения вида
F(x,y(x), y(x^l),…, y(x^(l^n)))=0, l ∈ N, l>=2, (1)
где F(x,y0,y1,…, yn) — аналитическая функция в окрестности 0 ∈ C^(n+2). Будем также использовать эквивалентную запись уравнения (1): F(x,y, μ y,…, μ^n y)=0, где μ: y(x) —> y(x^l) — разностный оператор Малера.
Уравнения Малера (сначала линейные) возникли в начале 20-го века в работах Курта Малера, крупного специалиста по аналитической теории чисел. Он использовал их как аппарат для исследования и классификации трансцендентности чисел. До 80-ых годов 20-го века они использовались только в этом направлении математики. Но в начале 80-ых годов оказалось, что они также имеют связь с теорией автоматов, которая переживала невероятный подъем в то время. На данный момент уравнения Малера являются источником новых специальных функций, используются в теории чисел, теории автоматов, в теорий функций комплексного переменного, связаны с теорией последовательностей и символьной динамикой.
Так же как и аналитические дифференциальные уравнения, уравнения Малера в общем случае на разрешаются в виде конечного числа комбинаций и композиций элементарных и специальных функций. Поэтому их решения также принято искать в виде формальных рядов, а затем ставить вопрос об их сходимости, асимптотичности или суммируемости. Так же как и дифференциальные уравнения, уравнения Малера могут иметь формальные решения в виде степенных рядов с комплексными показателями степени (обобщенных степенных рядов). Например, уравнение μy-y^l=0 имеет решение y=x^r, r ∈ C — произвольная постоянная. Кроме того, уравнения Малера могут обладать формальными решениями в виде степенных рядов с дробными показателями степени, но которые не являются рядами Пюизо, поскольку имеют точки накопления в множестве их показателей степени. Такие ряды являются примерами рядов Хана. Так, линейное уравнение Малера aμy-y=x, a ∈ C*, имеет формальное решение y=θ в виде ряда Хана
θ = sum_{k>=1} (1/a)^k x^(1/l^k),
сходящегося при |a|>1 и расходящегося при |a|< = 1 для всех x ∈ C*. Множество показателей степени этого ряда {1/l^k: k ∈ N} имеет одну точку накопления 0. В этом докладе мы будем обсуждать условия сходимости обобщенных степенных рядов с комплексными показателями степени, которые удовлетворяют уравнению (1).
—————————————————————————————————
The next meeting of the seminar on Computer Algebra of Faculty of Computational Mathematics and Cybernetics of MSU, and Computing Centre of RAS will be on Wednesday, January 15, 2025 at 16:30 Moscow time online via Zoom. The corresponding connection link will be e-mailed to the invited participants.
I.V.Goryuchkina (Keldysh Institute of Applied Mathematics of RAS, Moscow). The talk is based on joint work with R.R.Gontsov.
On nonformal solutions of a Mahler equation
Abstract
Analytical Mahler equations are functional equations of the form
F(x,y(x), y(x^l),…, y(x^(l^n)))=0, l ∈ N , l>=2, (1)
where F(x,y0,y1,…, yn) is an analytical function in the neighborhood of 0 ∈ C^(n+2). We will also use the equivalent notation of the equation (1): F(x,y, μ y,…, μ^n y)=0, where μ: y(x) —> y(x^l) is Mahler difference operator.
Mahler equations (at first linear) originated in the early 20th century in the work of Kurt Mahler, a major expert on analytical number theory. He used them as a device for investigating and classifying the transcendence of numbers. Until the 80s of the 20th century, they were used only in this area of mathematics. But in the early 80s, it turned out that they also had a connection with the theory of automata, which was on an incredible rise at the time. At the moment, Mahler equations are a source of new special functions, used in number theory, automata theory, and complex variable function theory, related to sequence theory and symbolic dynamics.
Like analytical differential equations, in general case Mahler equations are not solved in the form of a finite number of combinations and compositions of elementary and special functions. Therefore, it is also usual to look for their solutions in the form of formal series, and then raise the question of their convergence, asymptotic properties, or summability. Like differential equations, Mahler equations can have formal solutions in the form of power series with complex power exponents (generalized power series). For example, the equation μy-y^l=0 has a solution of y=x^r, r ∈ C is an arbitrary constant. Beside that Mahler equations can have formal solutions in the form of power series with fractional power exponents, but which are not Puiseaux series, since they have accumulation points in the set of their exponents. Such series are examples of Hahn series. For instance, the linear Mahler equation aμy-y=x, a ∈ C*, has a formal solution of y=θ in the form of a Hahn series
θ = sum_{k>=1} (1/a)^k x^(1/l^k),
converging for all x ∈ C* if |a|>1 and diverging for all x ∈ C* if |a|< = 1. The set of exponents of this series {1/l^k: k ∈ N} has a single accumulation point 0. In this talk, we will discuss the conditions for convergence of generalized power series with complex power exponents that satisfy the equation (1).
Dec 18, 2024/ 18 декабря 2024 г.
А.С.Кулешов (Механико-математический факультет МГУ им. М.В. Ломоносова).
Применение алгоритма Ковачича для исследования задачи о качении тяжелого однородного шара по поверхности вращения
Аннотация
Задача о качении без скольжения однородного шара по неподвижной поверхности под действием силы тяжести является одной из классических задач механики неголономных систем. Обычно при рассмотрении этой задачи, следуя подходу, предложенному в трактате Э. Дж. Рауса, принято задавать в явном виде поверхность, по которой движется центр шара, а не опорную поверхность, по которой катится шар. Поверхность, по которой движется центр шара, является эквидистантной к поверхности, по которой движется точка контакта. Еще из работ Э. Дж. Рауса и Ф. Нетера было известно, что если при качении шара по поверхности под действием силы тяжести его центр движется по поверхности вращения, то задача сводится к интегрированию одного линейного дифференциального уравнения второго порядка относительно компоненты скорости центра шара в проекции на направление касательной к параллели поверхности вращения. В общем случае (для произвольной поверхности вращения) получить решение этого уравнения в явном виде невозможно. Поэтому представляет интерес вопрос, для каких поверхностей вращения соответствующее линейное дифференциальное уравнение второго порядка допускает общее решение, выражающееся в явном виде, например через лиувиллевы функции. Лиувиллевы функции – это функции, которые строятся последовательно из рациональных функций с использованием алгебраических операций, неопределенного интегрирования и взятия экспоненты заданного выражения. Необходимые и достаточные условия существования решения линейного дифференциального уравнения второго порядка, выражающегося через лиувиллевы функции, дает так называемый алгоритм Ковачича.
В данном докладе мы приводим наш собственный способ получения линейного дифференциального уравнения второго порядка, к интегрированию которого сводится задача о качении тяжелого шара по неподвижной поверхности такой, что центр шара при качении движется по заданной поверхности вращения. Задавая затем различные поверхности вращения, которым принадлежит центр катящегося шара, и применяя алгоритм Ковачича, мы показываем, в каких случаях общее решение соответствующего линейного уравнения второго порядка выражается через лиувиллевы функции.
—————————————————————————————————
A.S.Kuleshov (Department of Mechanics and Mathematics, M.V.Lomonosov Moscow State University).
Application of the Kovacic algorithm for investigation the problem of rolling a heavy homogeneous ball on a surface of revolution
Abstract
The problem of rolling without sliding of a heavy homogeneous ball on a fixed surface is the classical problem of nonholonomic system dynamics. Usually, when considering this problem, following the E. J. Routh approach it is convenient to define explicitly the surface, on which the ball’s centre of gravity is moving and not the supporting surface along which the ball rolls. The surface, on which the ball’s centre of gravity is moving, is equidistant to the surface, over which the ball rolls. From the classical works of E. J. Routh and F. Noether it was known that if the ball rolls on a surface such that its centre of gravity moves along a surface of revolution, then the problem is reduced to solving the second order linear differential equation with respect to the projection of velocity of the ball’s centre of gravity onto the tangent to the parallel of the corresponding surface of revolution. However it is impossible to find the general solution of the corresponding second order linear differential equation for the arbitrary surface of revolution in explicit form. Therefore it is interesting to study for which surface of revolution the general solution of the corresponding second order linear differential equation can be expressed explicitly, in particular, in terms of Liouvillian functions. Recall that Liouvillian functions are functions constructed from rational functions by algebraic operations, taking exponentials, and integration. Necessary and sufficient conditions of existence of Liouvillian solutions of the given second order linear differential equation can be obtained using the so-called Kovacic algorithm.
In this talk we present our own method to derive the corresponding second order linear differential equation, the integration of which leads to the solution of the problem of motion of a heavy homogeneous ball on a fixed surface, such that its centre of gravity moves along the given surface of revolution. Considering the motion of the centre of gravity of the ball on various surfaces of revolution and applying the Kovacic algorithm, we found several cases when the general solution of the corresponding second order linear differential equation is expressed in terms of Liouvillian functions for all values of parameters of the problem.
Nov 20, 2024/ 20 ноября 2024 г.
Карлос Аррече (Техасский университет в Далласе, Отделение математических наук). Совместная работа с Мэтью Бэббитом.
Панорбитальные вычеты для эллиптической суммируемости
Аннотация
Суммируемость является центральным объектом изучения в разностной алгебре со времен пионерских работ С. Абрамова 1970-х годов. Она служит основой алгебраических методов изучения линейных рекуррентных соотношений над различными полями коэффициентов относительно тех или иных видов разностных операторов. Недавно Дрейфус, Ардуэн, Рок и Зингер ввели понятие эллиптических орбитальных вычетов, которые служат частичным препятствием к суммируемости рациональных функций на эллиптической кривой относительно сдвига к точке без кручения по правилам эллиптической группы. Мы выясняем, как привести это к полному препятствию с помощью того, что мы называем панорбитальными вычетами. Это обещает быть полезным для разностных уравнений над эллиптическими кривыми, задаваемыми эллиптическими гипергеометрическими функциями и возникающих в комбинаторике блужданий в четверти плоскости.
—————————————————————————————————
Carlos Arreche (The University of Texas at Dallas Department of Mathematical Sciences). This is joint work with Matthew Babbitt.
Panorbital residues for elliptic summability
Abstract
Summability has been a central object of study in difference algebra since the pioneering works of Sergei Abramov in the 1970s. It serves as a cornerstone of algebraic methods to study linear recurrences over various fields of coefficients and with respect to various kinds of difference operators. Recently, Dreyfus, Hardouin, Roques, and Singer introduced a notion of elliptic orbital residues, which altogether serve as a partial obstruction to summability for rational functions on an elliptic curve with respect to the shift by a non-torsion point with respect to the elliptic group law. We explain how to refine this into a complete obstruction with the introduction of what we call panorbital residues, which promises to be useful in applications of difference equations over elliptic curves, such as elliptic hypergeometric functions and the combinatorics of walks in the quarter plane.
Oct 16, 2024/16 октября 2024 г.
А.В. Селиверстов (ИППИ РАН, Москва). Совместная работа с О.А. Зверковым.
Алгоритм полиномиального времени для распознавания существования (0, 1)-решения системы немногих линейных уравнений по модулю три.
Аннотация
Распознавание существования (0, 1)-решения для системы линейных уравнений по модулю три служит примером NP-полной задачи. Однако в случае, когда количество уравнений ограничено сверху достаточно медленно растущей функцией от числа переменных, предложен новый алгоритм полиномиального времени для распознавания существования (0, 1)-решения у такой системы. Алгоритм основан на замечании: если в матрице коэффициентов присутствуют ненулевые пропорциональные друг другу столбцы, то элиминация соответствующих переменных сохраняет свойство отсутствия (0, 1)-решения системы. В частности, каждая система из двух уравнений от пяти переменных допускает элиминацию некоторых переменных, при которой сохраняется свойство отсутствия (0, 1)-решения системы. Кроме того, мы предлагаем безошибочный эвристический алгоритм, который реализован на языке программирования Python. Для представления матриц и выполнения базовых операций используется библиотека NumPy. Входом служит расширенная матрица системы. С использованием этой реализации была рассчитана эмпирическая оценка времени работы. Экспериментально показано, что алгоритм эффективнее для разреженных систем уравнений.
—————————————————————————————————
A.V. Seliverstov (IITP RAS, Moscow). This is joint work with O.A. Zverkov.
A polynomial-time algorithm for recognizing the existence of a (0, 1)-solutions to a system of several linear equations modulo three.
Abstract
Recognizing the existence of a (0, 1)-solution to a system of linear equations modulo three is an example of an NP-complete problem. In case the number of equations is less than a sufficiently slowly growing function of the number of variables, a new polynomial-time algorithm is proposed to recognize the existence of a (0, 1)-solution to such a system. The algorithm is based on the note that if the coefficient matrix contains non-zero columns proportional to each other, then the elimination of the corresponding variables preserves the property of having no (0, 1)-solution to the system. In particular, every system of two equations in five variables allows the elimination of some variables that preserves the property of having no (0, 1)-solution to the system. Moreover, we propose an errorless heuristic algorithm, which is implemented using the Python programming language. The NumPy library is used to represent matrices and perform basic operations. The input is the augmented matrix. An empirical running time estimate has been calculated using the implementation. It has been experimentally shown that the algorithm is more efficient for sparse systems of equations.
Sep 18, 2024/18 сентября 2024 г.
Жак-Артюр Вейль (Лиможский университет). Совместная работа с Ги Казалем и Примитиво Акоста-Уманезом.
Вычисление (нелинейного) группоида Мальгранжа-Галуа для уравнений Пенлеве посредством линеаризации
Аннотация
Для некоторых классов дифференциальных уравнений Пенлеве описывается подход к вычислению нелинейного аналога дифференциальной группы Галуа — группоида Мальгранжа. Мы концентрируемся на классах уравнений Пенлеве, которые допускают одно рациональное или алгебраическое решение. Линеаризация вдоль этого конкретного решения, позволяет выяснить
(1) как на практике могут вычисляться дифференциальные группы Галуа последовательных вариационных уравнений,
(2) что группоид Мальгранжа содержит, в некотором смысле, все эти дифференциальные группы Галуа,
(3) что, если размерность одной из этих дифференциальных групп Галуа больше 8, то уравнение Пенлеве имеет «очень большой» группоид Мальгранжа, и, следовательно, обладает свойствами сильной неприводимости.
Изложение будет фокусироваться на примерах, чтобы сделать в формате семинара теорию понятной.
—————————————————————————————————
Jacques-Arthur Weil (Limoges University). This is joint work with Guy Casale and Primitivo Acosta-Humanez.
Computing the Malgrange-Galois (non-linear) grouppoïd for Painlevé equations via linearizations
Abstract
In this work, we show an approach to compute the non-linear analog of the differential Galois group, the Malgrange groupoïd, for some classes of Painlevé differential equations. We focus on classes of Painlevé equations which admit one rational or algebraic solution. Linearizing along this particular solution, we will explain how :
(1) the differential Galois groups of the successive variational equations can be computed in practice
(2) the Malgrange groupoïd contains, in a sense, all these differential Galois groups
(3) if the dimension of one of these differential Galois groups is bigger than 8, the Painlevé equation has a Malgrange groupoïd which is “very big” and hence has strong irreducibility properties.
The talk will focus on examples to make the theory understandable in a seminar format.
