📐 Интегралы, которые невозможно выразить в элементарных функциях

После этого поста стало очевидно, что дорогие читатели этого канала очень любят интегралы.

А вот знаете ли вы, что далеко не все интегралы можно выразить через "обычные" функции вроде синуса, экспоненты или логарифма? Например, классический интеграл

∫𝑒^{−𝑥^2}𝑑𝑥

не имеет выражения через элементарные функции. Его значение задаётся через специальную функцию — ошибку Гаусса (erf).

🔍 Это открытие уходит к работам Жозефа Лиувилля в 1830-х годах. Он доказал теорему существования первообразной в элементарных функциях для определённых видов подинтегральной функции. Но нам же мало знать, что интеграл можно взять? Мы хотим его вычислить алгоритмически!

🧠 В 1969 году Роберт Риш разработал алгоритм (ныне известный как алгоритм Риша), который позволяет автоматически определить, можно ли взять интеграл в элементарных функциях. Этот алгоритм лёг в основу современных систем компьютерной алгебры: Mathematica, Maple, Maxima.

📚 Среди других ключевых работ:
– Бронштейн (1997) — систематизация алгоритмических методов
– Барри Трейгер (1984) — интегралы от алгебраических функций
– Теория "fewnomials" Хованского — на стыке алгебры и анализа

💡 Примеры неэлементарных интегралов:
– ∫sin⁡(𝑥^2)𝑑𝑥
- ∫sin(𝑥)/𝑥𝑑𝑥
- ∫sqrt(1+𝑥^3)𝑑𝑥

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

✳️ Вывод: даже простые на вид интегралы могут скрывать глубокие слои математической теории.

#ODE #ComputerAlgebra #Computability #Algorithms

@easy_about_complex

1/2

🧠 Что такое Expander-графы и почему это важно?

Помню лет 10-15 назад тема экспандер-графов была очень сильно на слуху. Не знаю как сейчас, вспомнил в связи с нейросетями и их #Interpretability, но даже не знаю, применяются ли там экспандеры...

Однако тема очень прикольная даже независимо от применений...

Expander-граф — это особый тип графа, в котором каждая небольшая группа узлов сильно связана с остальными. То есть даже если случайным образом выбрать 10-20% всех вершин, эти вершины будут иметь множество связей с оставшимися. Граф сохраняет свою «связность» даже при случайном удалении больших частей узлов или рёбер.

📌 Почему это важно? Это имеет большое значение:

— В криптографии: Expander-графы обеспечивают устойчивость к сбоям и атакам.
— В алгоритмах: Они помогают моделировать надёжные и устойчивые системы.
— В теории сложности: Они играют важную роль в решении задач, таких как SAT, и в дискуссиях о проблеме P vs NP.

#ExpanderGraphs #Algorithms #Complexity #SAT #PvsNP

Продолжение 👇

2/2. продолжение. начало тут.

Некоторые подходы к решению задачи SAT используют Expander-графы для создания «жёстких» экземпляров — таких, которые сложно упростить даже при использовании приближённых методов. Это позволяет лучше понять границы между «быстро решаемыми» и «на практике неразрешимыми» задачами.

🔍 Пример: экспандер из 100 узлов, где каждый узел связан с 10 другими. Даже если удалить 20-30% рёбер, граф часто остаётся связанным. Это и есть эффект расширения (expansion).

Кроме того, В таких графах информация распространяется быстро, даже если начинается только с небольшой части узлов. Это свойство делает их так же идеальными для моделирования процессов, таких как заражение, распространение вирусов, распространение новостей и многого другого.

⚙️ Вообще, не зависимо от применений, тут много очень прикольных свойств возникет и это всё не так тривиально, как может показаться на первый взляд, имхо. Надо бы посмотреть более пристально в сторону экспандеров... Думаю, что продолжение на эту тему следует...

#ExpanderGraphs #Algorithms #Complexity #SAT

@easy_about_complex

2/3 Продолжение. Начало тут.

🔍 Пример:
есть ли связь между числом π и его квадратом? Рассмотрим вектор чисел:

x = [1, π, π²]

Вопрос: существуют ли такие целые числа a, b, c, не все нули, что:

a·1 + b·π + c·π² = 0 ?

То есть, есть ли целочисленное линейное соотношение между 1, π и π²?

Запускаем алгоритм PSLQ на численно вычисленных значениях этих чисел (до, скажем, 30 знаков). Алгоритм перебирает линейные комбинации с целыми коэффициентами и проверяет, можно ли получить ноль.

👎Результат:
PSLQ не находит никаких нетривиальных целочисленных соотношений. Это подтверждает, что числа 1, π и π² алгебраически независимы (или, по крайней мере, не линейно зависимы над ℚ).
Но теперь попробуем другой пример.


🔍 Пример: формула Мачина для π
Рассмотрим:

x = [π, 4·arctan(1/5), -arctan(1/239)]

Алгоритм PSLQ находит соотношение:

π - 4·arctan(1/5) + arctan(1/239) ≈ 0

Это — формула Мачина (одна из классических формул для вычисления π):

π = 4·arctan(1/5) - arctan(1/239)

👍 Результат: И здесь PSLQ действительно "угадывает" точную алгебраическую формулу по числам с плавающей точкой.


🔥Почему это круто?

Мы из чисел, вычисленных на компьютере, получаем точные формулы.

Это обратный процесс по сравнению с обычной математикой: не от формулы к числу, а от числа к формуле.

Это один из редких примеров, когда компьютер может "угадать" математику.

#ExperimentalMathematics
#IntegerRelations #Algorithms #PSLQ

@easy_about_complex

3/3 Продолжение. Начало тут и тут.

Integer Relations в Квантовой Теории Поля (QFT)

В квантовой теории поля расчёт физических величин (например, аномальных магнитных моментов, поправок к массе и т.д.) требует вычисления многократных интегралов — так называемых Feynman интегралов, часто очень сложных и не имеющих аналитического выражения в явном виде.

Проблема:
Ты вычисляешь интеграл до, скажем, 100 знаков после запятой, но не знаешь, можно ли выразить его через известные константы — π, ζ(3), ln(2), polylogs и т.д.

Решение:
Алгоритмы типа PSLQ позволяют взять численно вычисленное значение и попробовать найти точную комбинацию известных функций, которая даёт тот же результат.

Пример: 3-петлевые поправки в QED
В 1996 году, когда исследовали высшие порядки поправок в квантовой электродинамике (QED), вычислялись 3- и 4-петлевые Feynman диаграммы, численно — и оказалось, что значения можно выразить через комбинации таких чисел, как:

-ζ(3) (дзета-функция Римана)
-π²
-ln(2)
-Li₄(½) (полилогарифмы)

и других “трансцендентных” чисел.

Кейс:
David Broadhurst и David Bailey использовали PSLQ, чтобы найти точные выражения для десятков интегралов, связанных с Feynman diagrams, которые до этого считались "неразрешимыми".

Они буквально открывали формулы из чисел, полученных с суперкомпьютеров — в полном смысле слова "экспериментальная математика в физике".

Почему это важно?
👉Позволяет проверять и упрощать физические расчёты, даже в очень сложных теориях.
👉Помогает предсказать форму результата, прежде чем будет найден аналитический вывод.
👉В некоторых случаях выводит физику на след новых математических объектов — например, множественные дзета-значения (MZV), которые сейчас изучаются и в физике, и в алгебраической геометрии.


📎 Ссылка на эти работы тут.
.
#ExperimentalMathematics
#IntegerRelations #Algorithms #PSLQ #QuantumFieldTheory

@easy_about_complex

2/2. продолжение. начало тут

🔐 Гомоморфное шифрование: вычисления без раскрытия данных

Гомоморфное шифрование (Homomorphic Encryption, HE) — это криптографический метод, позволяющий производить вычисления непосредственно над зашифрованными данными. При расшифровке результата вы получите тот же ответ, как если бы вычисляли над исходными данными.

📘 Что это значит на практике?


Пример 1: Защищённая аналитика
-У больницы есть зашифрованные данные о пациентах.
- Исследователь хочет посчитать средний возраст пациентов с диабетом.
- Он выполняет вычисления над зашифрованными данными, не получая доступ к реальным возрастам.
- Результат после расшифровки — корректный, но приватность не нарушена.

Пример 2: Облачные вычисления
-Компания шифрует свои бизнес-данные и отправляет их в облако.
-Облачный сервис считает оптимальный маршрут доставки, не зная, что именно обрабатывает.
-Компания получает готовое решение, не жертвуя конфиденциальностью.

🔣 Типы гомоморфного шифрования
PHE (частичное): поддерживает одно арифметическое действие (например, схема RSA — умножение, Paillier — сложение).
SHE (ограниченное): ограниченное число операций.
FHE (полное): любые арифметические операции и неограниченное их количество — теоретически мощно, практически сложно.

⚙️ Сложность и ограничения
Полностью гомоморфные схемы (например, BGV, BFV, CKKS) используют сложные математические конструкции, основанные на задачах на решётках (например, Ring-LWE). Они считаются устойчивыми даже к квантовым атакам.
Но:

Один шаг умножения может быть в 1000 раз медленнее, чем над открытыми данными.
Размеры зашифрованных данных могут вырасти в десятки мегабайт даже при обработке маленьких чисел!

Пример 3:
Сравнение времени:
Обычное сложение: ~100 наносекунд
Гомоморфное сложение: ~10–100 микросекунд
Гомоморфное умножение: ~1–10 миллисекунд


Но что, если таких операций — сотни миллионов, как в настоящих аналитических запросах?

🧠 Реальный сценарий, SQL запрос к базе данных:

SELECT AVG(salary) FROM employees WHERE department_id IN (10, 12, 15);

В открытом виде:
-Выполняется за десятки миллисекунд.
- Сложения и фильтрация — почти бесплатные.

В гомоморфной форме (FHE):
- Фильтрация = миллионы сравнений.
- Суммирование и деление — над зашифрованными значениями.- всё дорого.

🔢 Оценка масштабов:
Если один шаг FHE-умножения ≈ 1–10 миллисекунд, а запрос требует 100 млн арифметических операций,
то:

100,000,000×1 мс=1,000,000  секунд≈11.5 дней

🤯 И это — только один запрос.

Да, можно параллелить, батчить, использовать SIMD, но даже с 1000-ядерным распределением это всё ещё часы на простейший аналитический запрос.

🔍 Почему так медленно?
🚫 Невозможно адресовать конкретные данные напрямую: всё обрабатывается последовательно, от начала до конца.
➕ Даже простая фильтрация превращается в арифметическую маску (массив умножений).
🔐 Все операции идут по "защищённому пути": нет читов, нет оптимизаций из классических DB.

🛠️ Что делают?
⚙️ Используют batching (один шифротекст содержит десятки/сотни значений).
⏱️ Переписывают запросы на арифметику, минимизируя глубину схем.
💡 Комбинируют FHE с другими подходами: MPC, TEE, дифференцированным шифрованием.

📌 Вывод:
Гомоморфные вычисления не подходят для произвольных SQL-запросов по большим базам — пока или вообще никогда?

#RealWorldProblems #Crpyptography
#HomomorphicEncryption
#DataPrivacy #Algorithms #Complexity

2/2. продолжение. начало тут 👆

🔢 У 3×3 кубика — около 43 квинтильонов (4 × 10²⁰) возможных конфигураций. И при этом точно известно: любой из них можно решить за максимум 20 ходов. всего за 20, млять, из такого пространства состояний! Это так называемое число Бога. Красивое, минималистичное, почти мистическое.

Меня это сразу зацепило. С одной стороны — гигантское пространство состояний. С другой — маленькое число. Как такое возможно? И как эффективно найти этот кратчайший путь?

📈 Всё это можно представить как блуждание по графу Кэли: каждая вершина — это состояние кубика, рёбра — допустимые повороты. Задача — найти кратчайший путь между двумя вершинами. Логично, что для 3×3 можно просто перебрать всё (хотя и с оптимизациями). Но если взять кубик побольше — n×n×n — задача становится совсем другой.

🤓 Есть мнение, что число Бога растёт квадратично по n. Над этим размышлял даже Теренс Тао — один из самых известных современных математиков. Он предположил, что структура групп конфигураций устроена так, что можно обойтись полиномиальным числом шагов, но... полного доказательства пока нет. Даже у Тао. Это не решённый вопрос.

❗ Но тут главное не путать:
число ходов для сборки кубика может расти полиномиально,
однако алгоритм, который это оптимальное решение находит, скорее всего, работает за экспоненциальное время.

Хотите — расскажу подробности!

🔍 Всё это — не просто про кубик. Это про сложность, алгоритмы, структуру, границы возможного. И, честно говоря, круто, что такая на вид простая штука может вести к таким глубоким вопросам.

Если интересно, могу потом поделиться тем, как всё это связано с криптографией, случайной генерацией и обучением алгоритмов.

А пока — как вы думаете:
а для 4×4 и выше число Бога действительно растёт медленно?
Или просто пока никто не знает?

@easy_about_complex

#Complexity #Algorithms
#ComputationalAlgebra #ComputatinalGroupTheory #CayleyGraphs #Puzzles

Продолжение, начало тут 👆

Теперь начинается самое интересное.

«Алфавит» этой группы — 12 вращений (пo по две вокруг каждой из 6-ти вершин октаэдра — по часовой стрелке и против). Вращения могут переставлять 48 элементов восьми цветов. Всего у пазла 2 009 078 326 886 400 возможных состояний (примерно 2×10^15, около двух квадриллионов).

Если представить все состояния как вершины в графе Кэли, то таких вершин будет столько же — 2 009 078 326 886 400, и из каждой выходит 12 рёбер — по одному на каждое вращение. Найти кратчайший путь от случайно перемешанного состояния к собранному при таком масштабе стандартными алгоритмами практически невозможно, даже на суперкомпьютере.

Поэтому следующий шаг — обучить нейросеть «языку» движений и перестановок именно для этой головоломки. Посмотрим, что получится. Эксперимент продолжается 🙂 Пока не уверен, какую архитектуру выбрать — есть идеи и интуиция, но это надо проверять. Цель на первом этапе — научить нейросеть ориентироваться в огромных пространствах состояний, где при этом есть довольно регулярная структура.

P.S. Напоминаю, что к этому проекту можно присоединиться:
🔗 https://t.iss.one/sberlogabig/581

Ссылки на уже опубликованные работы:
📄 https://arxiv.org/abs/2502.18663
📄 https://arxiv.org/abs/2502.13266

#Algorithms #Complexity #Algebra #GroupTheory #CayleyGraphs #ML #ChristophersJewelPuzzle #Puzzles