Теория насыщения. Часть I.

Июль, 2021 Аннотация

Рассматриваются некоторые свойства частичных сумм делителей натуральных чисел и описывается феномен «насыщения» подобных сумм, выражающийся в вытеснении некоторых простых делителей из их факторизаций. Сама исследуемая проблема представляется довольно глубокой и сложной, в силу чего никаких конкретных подтверждённых результатов и полных доказательств, к сожалению, здесь представлено не будет (а имеющиеся рассуждения будут выполнены исключительно элементарными средствами).

Несмотря на ограниченность сообщения констатацией небольшого объёма необходимых дефиниций и эмпирических фактов/догадок вместе с небольшим количеством набросков доказательств (коих, в совокупности, я уже поспешил окрестить «теорией насыщения»), настоящий феномен, я надеюсь, может оказаться интересен любителям теории чисел (впрочем, есть подозрение, что профессиональные математики увидят здесь что-нибудь уже хорошо им известное).

Содержание:

Вводные замечания
Некоторые определения
Основная проблема
Специальный случай
- Факторизация с двойкой
- Факторизация без двойки и без повторов
Заключение
Ссылки

Вводные замечания

Изложение придётся начать с оговорок по поводу выбора использующихся далее терминов «насыщенность», «насыщение» и т.д. Поиск в интернете показывает, что в теоретико-числовом контексте понятие насыщенности, так или иначе, изредка употребляется. Где-то это может означать ограниченность набора цифр, использующихся для записи числа (e.g., попадалось определение насыщенного числа, как многоразрядного числа, десятичная запись которого содержит только две цифры, возможно применённых многократно и в произвольной последовательности), а где-то о насыщенности говорят при обсуждении некоторых вариантов машинной арифметики (вроде стандартной реализации чисел с плавающей точкой во многих современных процессорах и языках программирования), в которых при переполнении число «насыщается», приобретая значение ближайшего экстремального значения (вместо «прыжка» в противоположный конец машинной числовой оси как в модулярной арифметике) [1].

Но за исключением эти редких употреблений понятия насыщения числа, термин «насыщенное число» трудно назвать стандартным (ещё раз подчеркну, что трудно именно с точки зрения поверхностного обследования свободно доступных источников при помощи популярных поисковых систем). Поэтому, заметив интересный феномен при проведении кое-каких численных экспериментов, я поспешил использовать это почти свободное слово для введения условно нового термина, именно с целью описания этого феномена в настоящем дневнике. (Если читателям известны более уместные термины, то рад бы был услышать возможные варианты.)

В моём случае, насыщенность будет использоваться для характеризации «состава», т.е. разнообразия простых делителей, довольно специфичных теоретико-числовых объектов, а именно частичных/частных сумм делителей целых чисел (далее я буду сосредоточен на натуральных числах).

Очень похожие проблемы глубоко исследовались Эрдёшем; возможно, знатоки его работ узнают здесь что-нибудь знакомое (e.g. «странные числа» [2]). Хотя, некоторая новизна, я надеюсь, всё-таки остаётся. :)

Некоторые определения

Пусть дано число $\text{[math]}$ . Все его делители образуют множество $\text{[math]}$ (мощность $\text{[math]}$ традиционно обозначается $\text{[math]}$ ). На $\text{[math]}$ возьмём какое-нибудь отношение полного порядка $\text{[math]}$ , относительно которого делители будут упорядочены. В частности, для получения минимального элемента относительно этого отношения будет использоваться символ $\text{[math]}$ . Если в качестве $\text{[math]}$ используется обычное отношение $\text{[math]}$ , то будем говорить о каноническом порядке (упорядочивании) делителей.

Введём последовательность делителей $\text{[math]}$ (N.B. $\text{[math]}$ ).

Определение

Последовательность частичных сумм делителей обозначим $\text{[math]}$ и определим индуктивно:

$\text{[math]}$

( $\text{[math]}$ здесь как колёса у рыбы, но, формально, эта частичная сумма соответствует суммированию по пустому подмножеству делителей; так что пусть пока будет так.)

В отличии от частичных сумм делителей, сумма всех делителей является очень известным и важным объектом в теории чисел. Обычно сумму всех делителей числа $\text{[math]}$ обозначают как $\text{[math]}$ , хотя в классической работе Эйлера [3] (см. также перевод с латыни [4]) используется интегралоподобный символ $\text{[math]}$ , позволяющий немного экономить на скобках.

Функция Эйлера $\text{[math]}$ подсчитывает количество чисел, не превышающих $\text{[math]}$ и взаимно простых с ним. Т.е. $\text{[math]}$ .

Определение: Кроме количества чисел, меньших $\text{[math]}$ и взаимно простых с ним, далее может понадобиться их произведение: $\text{[math]}$ , а также произведение простых чисел, на которые не делится $\text{[math]}$ : $\text{[math]}$ , где $\text{[math]}$ – множество всех простых чисел.

Вместо $\text{[math]}$ и $\text{[math]}$ будет писаться просто $\text{[math]}$ и $\text{[math]}$ , соответственно. (Связь $\text{[math]}$ с группами Эйлера могла бы быть важным преимуществом, но пока я буду, в основном, пользоваться $\text{[math]}$ .)

Определение: Введём функцию $\text{[math]}$ , подсчитывающую количество простых делителей (размер факторизации) числа $\text{[math]}$ . Пусть $\text{[math]}$ , где $\text{[math]}$ , $\text{[math]}$ и $\text{[math]}$ – максимальная степень $\text{[math]}$ , такая, что $\text{[math]}$ . Тогда $\text{[math]}$ (может быть для неё и есть какое-нибудь стандартное обозначения, но мне оно не известно).

Теперь можно приступить к определению насыщенности как таковой.

Определение

Число $\text{[math]}$ назовём слабо насыщенным если $\text{[math]}$ .

Другими словами, если обозначить через $\text{[math]}$ множество различных простых делителей числа $\text{[math]}$ , то для слабо насыщенного числа $\text{[math]}$ выполняется $\text{[math]}$ . Т.е. слабо насыщенное число использует в своей факторизации все факторы числа $\text{[math]}$ , но, возможно, в других количиствах, и, в общем случае, в слабо насыщенное число могут входит и другие простые делители, отсутствующие в факторизации $\text{[math]}$ .

Определение

Число $\text{[math]}$ назовём насыщенным если $\text{[math]}$ или, что то же самое, если $\text{[math]}$ .

В факторизации насыщенного числа обязательно присутствуют все факторы числа $\text{[math]}$ , причём в тех же степенях (количествах), но могут, кроме этого, быть и другие произвольные факторы.

Определение

Число $\text{[math]}$ – сильно насыщенно если $\text{[math]}$ или, эквивалентно, если $\text{[math]}$ , где функция $\text{[math]}$ (не следует путать с количеством делителей, в этом сообщении обозначаемым через $\text{[math]}$ ) определяется через $\text{[math]}$ , для последовательности $\text{[math]}$ , такой, что $\text{[math]}$ , $\text{[math]}$ . (Условие $\text{[math]}$ имеет тот же смысл, что и $\text{[math]}$ ; также следует заметить, что вместо $\text{[math]}$ можно было бы использовать $\text{[math]}$ .)

Иначе выражаясь, насыщенное число является сильно насыщенным если в его факторизации нет простых множителей, не входящих в факторизацию $\text{[math]}$ . Сильную насыщенность можно считать обобщённой гладкостью числа (напомню, что число называют $\text{[math]}$ -гладким если оно состоит только из факторов, не превышающих $\text{[math]}$ [5]).

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

(N.B., введённые выше степени насыщенности определяются относительно зафиксированного $\text{[math]}$ и из контекста должно быть ясно о каком числе идёт речь, в противном случае рекомендуется делать уточнения в виде «насыщенность относительно $\text{[math]}$ » или, более кратко, « $\text{[math]}$ -насыщенность».)

Предложение 1: Эти степени насыщения образуют иерархию в том смысле, что всякое сильно насыщенное число является ещё и насыщенным, а насыщенное число заодно является слабо насыщенным.

О свойствах насыщенных чисел мне известно не так много. Например:

Утверждение 1

Множество слабо насыщенных чисел замкнуто относительно операций $\text{[math]}$ и $\text{[math]}$ .
Множество насыщенных чисел замкнуто относительно операций $\text{[math]}$ и $\text{[math]}$ .
Сильно насыщенные числа же замкнуты только относительно умножения $\text{[math]}$ .

Набросок доказательства

Если числа $\text{[math]}$ и $\text{[math]}$ – слабо насыщенны, то факторизация каждого содержит все различные простые делители числа $\text{[math]}$ , и, т.о., можно выделить эту общую часть чисел $\text{[math]}$ и $\text{[math]}$ записав их в виде $\text{[math]}$ и $\text{[math]}$ , где число $\text{[math]}$ при разложении на простые делители будет содержать все различные делители $\text{[math]}$ и только их. Тогда, $\text{[math]}$ , но число $\text{[math]}$ – слабо насыщенно (т.е. делится на каждый из простых делителей числа $\text{[math]}$ ).

Случай с умножением аналогичен: произведение $\text{[math]}$ делится на простые делители $\text{[math]}$ .
Пусть теперь $\text{[math]}$ и $\text{[math]}$ – насыщенные числа. Это значит, что каждое из них делится на $\text{[math]}$ , а значит, они могут быть представленны в виде $\text{[math]}$ и $\text{[math]}$ , соответственно. Легко видеть, что и сумма $\text{[math]}$ и произведение $\text{[math]}$ делятся на $\text{[math]}$ , т.е. тоже насыщенны.
Действуя по той же схеме, запишем произведение cильно насыщенных чисел $\text{[math]}$ и $\text{[math]}$ (которые, автоматически будут и насыщенными) в виде $\text{[math]}$ . Видно, что если исходные множители состояли только из простых делителей числа $\text{[math]}$ , то в произведении $\text{[math]}$ новым простым делителям взяться неоткуда. а значит $\text{[math]}$ – тоже сильно насыщенное число.

N.B., а вот относительно сложения, к сожалению, в общем случае, сильная насыщенность не сохраняется. Действительно, сильно насыщенные числа $\text{[math]}$ и $\text{[math]}$ являются насыщенными, что позволяет записать их, с использованием того же трюка, что и выше, как $\text{[math]}$ и $\text{[math]}$ , а их сумму, соответственно как $\text{[math]}$ . Но ведь в подвыражении $\text{[math]}$ могут запросто появиться «чужеродные» факторы, нарушающие сильную насыщенность… Ну. в общем, $\text{[math]}$ :)

Хотя я и старался ограничиться при изложении лишь элементарными средствами, ближе к концу сообщения понадобится хотя и достаточно элементарный, но глубокий классический (если не сказать древний) результат, больше известный как китайская теорема об остатках (кратко К.Т.О.). Конкретно, ниже приведена конструктивная версия К.Т.О.:

Теорема (без доказательства)

Пусть даны $\text{[math]}$ чисел $\text{[math]}$ (остатков) и $\text{[math]}$ чисел $\text{[math]}$ (модулей), таких, что $\text{[math]}$ и $\text{[math]}$ . Тогда система сравнений $\text{[math]}$ имеет ровно одно решение $\text{[math]}$ , где $\text{[math]}$ и

$\text{[math]}$

Т.к. $\text{[math]}$ равна количеству чисел, не превышающих $\text{[math]}$ и взаимно простых с $\text{[math]}$ , то при $\text{[math]}$ функция Эйлера равна $\text{[math]}$ (из-за того, что вообще все натуральные числа из $\text{[math]}$ взаимно просты с простым $\text{[math]}$ ). Это позволяет переписать решение из китайской теоремы об остатках в виде

$\text{[math]}$
для случая простых модулей $\text{[math]}$ . В настоящем сообщении будет применяться именно это следствие К.Т.О. для простых модулей.

Основная проблема

Гипотеза 1

$\text{[math]}$ , где $\text{[math]}$ . Схематично: насыщенность $\text{[math]}$ сильная насыщенность.

Следствие: В частности, $\text{[math]}$ , т.е. из насыщенности некоторой частичной суммы вытекает её сильная насыщенность, причём, независимо от $\text{[math]}$ , т.е. для любого порядка включения делителей $\text{[math]}$ в частичные суммы.

N.B., в гипотезе 1 допустимо не более чем однократное использование каждого из делителей – если некоторый делитель участвует в суммировании многократно, то, вообще говоря, гипотеза может нарушаться.

Некоторые из представленных ниже результатов существенно используют такую последовательность частичных сумм. Более того, некоторые утверждения вместе с их доказательствами подразумевают канонический порядок суммирования делителей. Поэтому, можно сказать, что в этом сообщении не будет почти ничего, касающегося доказательства именно общей гипотезы 1, а, фактически, будут предприниматься попытки обоснования/доказательства лишь следующего частного утверждения:

Гипотеза 2

При каноническом порядке суммирования делителей, выполняется $\text{[math]}$ (т.е., по прежнему, сильная насыщенность логически необходима для насыщенности, но выполнение условия этой гипотезы гарантируется только если делители упорядочены по возрастанию).

Предложение: Ранее, в предложении 1, было замечено, что степени насыщения иерархически упорядочены, и, в частности, сильная насыщенность достаточна для насыщенности. Вместе с утверждаемой в гипотезе 1 необходимостью, это даёт эквивалентность насыщенности и сильной насыщенности: $\text{[math]}$ , где $\text{[math]}$ – сумма по некоторому подмножеству делителей. Очевидно, обе гипотезы 1 и 2 могут быть, при желании, переформулированы в терминах такой эквивалентности.

Рассмотрим небольшой пример. Допустим, $\text{[math]}$ . Множество делителей есть $\text{[math]}$ . Произведение простых чисел (меньших $\text{[math]}$ ), на которые $\text{[math]}$ не делится, равно числу $\text{[math]}$ . Частичные суммы образуют последовательность $\text{[math]}$ . Непосредственная проверка показывает, что суммы $\text{[math]}$ , $\text{[math]}$ и $\text{[math]}$ – слабо насыщенны (в первом случае в факторизации не хватает двух двоек для насыщенности, в последних двух – не хватает по одной двойке), сумма 24 – насыщенна и к тому же сильно насыщенна, остальные суммы ненасыщенны.

Ещё несколько выборочных примеров приведу в виде диаграмм с цветовым кодированием. Жёлтым покрашены «запрещённые» факторы, присутствующие в частичной сумме делителей, но отсутствующие в исходном числе $\text{[math]}$ . Синий цвет имеют факторы присутствующие в $\text{[math]}$ , а также факторы, находящиеся и в $\text{[math]}$ и в частичной сумме одновременно, но не являющиеся критически важными для насыщенности. Красным цветом обозначены факторы частичной суммы, общие с факторизацией $\text{[math]}$ и важные для присвоения той или иной степени насыщенности данной частичной сумме. Сумма будет насыщенной если в ней есть все красные факторы из числа $\text{[math]}$ , т.е. если факторизация $\text{[math]}$ входит в факторизацию $\text{[math]}$ в качестве подпоследовательности. Сумма $\text{[math]}$ будет сильно насыщенной если она насыщенна и не имеет жёлтых факторов. Вот некоторые примеры:

$\text{[math]}$

Обратите внимание, как только факторизация $\text{[math]}$ обнаруживается входящей полностью в факторизацию некоторой $\text{[math]}$ , жёлтые факторы гарантированно вытесняются из факторизации такой частичной суммы (это показано в двух последних примерах; в примере с $\text{[math]}$ , несмотря на слабое насыщение частичной суммы $\text{[math]}$ , в ней тоже нет жёлтых факторов, но это лишь совпадение – см. пример с $\text{[math]}$ ).

Интуитивный смысл гипотезы 2: если некоторая частичная сумма делится на всё, на что делятся её слагаемые, то она не может делиться ни на что другое, потому, что сама сумма только из этих слагаемых и состоит. Здесь существенно, что слагаемые – суть делители числа $\text{[math]}$ , и без этого ограничения такой эвристический (если не метафизический) аргумент не работает. Ведь, в общем случае, факторизация суммы может кардинально отличаться от факторизаций входящих в неё слагаемых; даже просто инкремент числа обычно меняет его факторизацию до неузнаваемости, в чём, по моему мнению, и лежит основная сложность большинства задач и открытых проблем теории чисел. А изучение феномена вытеснения лишних факторов — теория насыщения — может позволить хотя-бы немного разобраться в этом «хаосе» факторизации сумм.

Численные эксперименты вместе с утверждением 1 показывают, что если гипотеза 2 верна, то её утверждение для $\text{[math]}$ зависит не только от слагаемых $\text{[math]}$ , а для своего доказательства требует учёта структурных свойств $\text{[math]}$ . Поэтому, хотя частичные суммы вводились именно с прицелом на применение индукции в возможном доказательстве гипотезы, но пока не ясно, будет ли достаточно этих средств.

Утверждение 2: Гипотеза 2 [тривиально] верна для $\text{[math]}$ .

Доказательство

У простого числа $\text{[math]}$ только два делителя, – это 1 и $\text{[math]}$ . Соответственно, в этом случае будут только две ненулевые частичные суммы. При каноническом порядке делителей, сумма $\text{[math]}$ вообще ни на что не делится (кроме единицы, но $\text{[math]}$ ) и не может быть насыщенной. Сумма $\text{[math]}$ при делении на $\text{[math]}$ даёт остаток 1 и поэтому тоже не может быть насыщенной. При другом порядке делителей, сумма $\text{[math]}$ , поэтому она насыщенна (делится на $\text{[math]}$ ) и заодно сильно насыщенна (взаимно проста с $\text{[math]}$ , по определению числа $\text{[math]}$ ). Следующая сумма $\text{[math]}$ аналогична такой же сумме из уже рассмотренного случая канонического упорядочивания. $\text{[math]}$

Похоже, существует какая-то связь между свойствами насыщения частичных сумм делителей, чётностью $\text{[math]}$ и взаимной простотой $\text{[math]}$ с попарными разностями делителей.

Наблюдение 1: Для нечётных $\text{[math]}$ никакая из частичных сумм делителей не достигает насыщения. Эквивалентно: $\text{[math]}$ . (Всё это работает только для канонического порядка делителей: простой контрпример получается если первым делителем выбрать любой насыщенный делитель, да хоть $\text{[math]}$ .)

Наблюдение 1 скорее-всего не проще основной гипотезы 2, ведь если для нечётного случая насыщенность вообще не достигается, то гипотеза выполняется автоматически, больше доказывать нечего. И именно этот случай $\text{[math]}$ – как назло, самый сложный и интересный. :)

Наивная попытка применить индукцию для доказательства «инварианта» $\text{[math]}$ мало к чему приводит: при каконическом порядке делителей базовый случай очевиден (единица ни на что не делится кроме единицы), самый последний шаг индукции с прибавлением максимального делителя, равного самому числу $\text{[math]}$ , менее очевиден, но тоже вполне элементарен (я пока не буду его пояснять, оставляя его в качестве необязательного упражнения читателю :) ). А вот общий шаг индукции чрезвычайно сложен… По крайней мере у меня ничего не получилось (но попытка доказательства для достаточно показательного частного случая всё же будет приведена ближе к концу сообщения) .

Наблюдение 2: Для чётных $\text{[math]}$ выполняется: $\text{[math]}$ .

(Легко видеть, почему наблюдение 2 не выполняется для нечётных $\text{[math]}$ . Раз в факторизации $\text{[math]}$ нет двойки, то двоек не будет и в факторизации любого делителя. Значит, все делители числа $\text{[math]}$ суть нечётные числа, но т.к. разность любых двух нечётных чисел есть число чётное, то все попарные разности делителей будут делиться на $\text{[math]}$ и будут контрпримерами (хотя и не единственными).)

Набросок доказательства

Пусть $\text{[math]}$ и произвольно выбрано $\text{[math]}$ , причём $\text{[math]}$ . Доказывается утверждение $\text{[math]}$ . Доказательство существования такого $\text{[math]}$ будет проводиться полной индукцией по величине уменьшаемого в разностях $\text{[math]}$ .

База:

Т.к. $\text{[math]}$ , то $\text{[math]}$ больше единицы, а т.к. $\text{[math]}$ чётно, то базовый случай есть $\text{[math]}$ . Поэтому $\text{[math]}$ удовлетворяет доказываемому утверждению. В самом деле, $\text{[math]}$ т.к. $\text{[math]}$ , и $\text{[math]}$ . Очевидно, что раз $\text{[math]}$ , то $\text{[math]}$ .

Предположение индукции: $\text{[math]}$ .

Шаг индукции:

Пусть $\text{[math]}$ . Тогда $\text{[math]}$ . Очевидно, $\text{[math]}$ и $\text{[math]}$ , поэтому, по предположению индукции, $\text{[math]}$ . Остаётся положить $\text{[math]}$ , что даст разность $\text{[math]}$ в которой ни $\text{[math]}$ , ни $\text{[math]}$ , не делятся на $\text{[math]}$ , а значит и $\text{[math]}$ . Вот так вот всё просто для сложных $\text{[math]}$ . :)

А вот для простых $\text{[math]}$ всё, наоборот, сложнее. (Второй раз шутка не срабатывает.) На самом деле, я не знаю как быть с этой веткой доказательства. А чтобы хоть как-то завершить этот набросок, могу лишь привести такой полуэвристический аргумент. Пусть $\text{[math]}$ . И предположим, что всё совсем плохо и $\text{[math]}$ , где $\text{[math]}$ . Попробуем методом от противного опровергнуть эту пессимистическую возможность отсутствия подходящего $\text{[math]}$ .

Пусть $\text{[math]}$ – остатки от деления $\text{[math]}$ и $\text{[math]}$ на $\text{[math]}$ , т.е. $\text{[math]}$ и $\text{[math]}$ . Вычитая из первого сравнения второе, получаем $\text{[math]}$ . Что вместе с предположением $\text{[math]}$ даёт $\text{[math]}$ , или просто $\text{[math]}$ (ведь $\text{[math]}$ ). Утверждение $\text{[math]}$ можно поэтому интерпретировать как $\text{[math]}$ , где $\text{[math]}$ – остаток от деления $\text{[math]}$ на $\text{[math]}$ . Т.е. все делители, не превышающие простой делитель $\text{[math]}$ , при делении на $\text{[math]}$ должны давать одинаковые остатки.

Это не просто звучит удивительно (в конце концов, при нечётном $\text{[math]}$ все делители дают один и тот же остаток по модулю 2, и это, честно говоря, не очень удивляет), но и приводит к более осязаемым последствиям. А именно, первый, минимальный делитель равен единице и при делении на $\text{[math]}$ в остатке даёт единицу. Уже следующий делитель, двойка (а он всегда есть, из-за чётности $\text{[math]}$ ), даёт при делении на $\text{[math]}$ в остатке двойку. Также, каждый последующий простой делитель, не превышающий $\text{[math]}$ будет, при делении на простое число $\text{[math]}$ , давать остаток не меньший двух. Кратко, это можно записать так:

$\text{[math]}$

Понятия не имею, можно ли эти рассуждения довести до формального доказательства, но в качестве подтверждения собственных интуитивных догадок, указанное противоречие (простые делители, не превышающие $\text{[math]}$ , не сравнимы по модулю $\text{[math]}$ с единицей) меня устраивает. Условно буду считать, что утверждение $\text{[math]}$ , в свете приведённого аргумента, нарушается для простых $\text{[math]}$ и, соответственно, выполняется $\text{[math]}$ . (По-настоящему подозрительным в случае с $\text{[math]}$ является игнорирование предположения индукции, но и незаконного здесь ничего нет – методом от противного выводится существование искомого $\text{[math]}$ и, т.о., обеспечивается истинность доказываемого утверждения для данного простого $\text{[math]}$ , что делает возможной работу всех будущих шагов индукции.)

Всё это могло бы успешно завершить шаг индукции и, как следствие, завершить набросок доказательства наблюдения 2. $\text{[math]}$

Специальный случай

Сначала, возможно, стоит попробовать рассмотреть упрощённую версию гипотезы 2, ограничившись числами $\text{[math]}$ , все факторы которых различны (или, лучше сказать, все факторы или простые делители имеют единичную степень). Т.е., если $\text{[math]}$ – последовательность всех простых чисел ( $\text{[math]}$ ), то разложение такого $\text{[math]}$ на простые множители выглядит как $\text{[math]}$ где $\text{[math]}$ . Количество различных простых делителей числа $\text{[math]}$ обычно обозначают $\text{[math]}$ ; с использованием этого обозначения специальный случай можно охарактировать как $\text{[math]}$ .

Последовательностью [модулей] $\text{[math]}$ обозначим простые делители числа $\text{[math]}$ ; чуть выше уже вводилось обозначение $\text{[math]}$ для множества простых делителей, поэтому $\text{[math]}$ . Последовательностью же модулей $\text{[math]}$ обозначим простые числа, меньшие числа $\text{[math]}$ и не делящие его: $\text{[math]}$ .

Количество модулей $\text{[math]}$ , с использованием ранее придуманной функции $\text{[math]}$ , равно $\text{[math]}$ . Очевидно, общее количество модулей $\text{[math]}$ и $\text{[math]}$ равно $\text{[math]}$ , где $\text{[math]}$ – количество простых чисел, не превышающих $\text{[math]}$ . Тогда количество модулей $\text{[math]}$ равно $\text{[math]}$ . Напомню также, что $\text{[math]}$ . В рассматриваемом случае с различными факторами в числе $\text{[math]}$ , можно аналогично записать $\text{[math]}$ .

Гипотеза говорит, что если для некоторого $\text{[math]}$ частичная сумма $\text{[math]}$ делится на все $\text{[math]}$ , то она не делится ни на один из $\text{[math]}$ . Я обозвал числа $\text{[math]}$ и $\text{[math]}$ модулями именно потому что это условие сильного насыщения может быть записано в виде системы сравнений

$\text{[math]}$

Такая запись интересна хотя-бы потому, что, во-первых, намекает на возможность применения некоторых интересных результатов теории чисел, вроде китайской теоремы об остатках (например, К.Т.О. говорит, что, по модулю $\text{[math]}$ , частичная сумма в левых частях всех этих сравнений определяется остатками однозначно; из чего следует, если я ничего не напутал, что у двух частичных сумм [при одном и том же $\text{[math]}$ ] не может быть одного и того же вектора остатков), а во-вторых, подчёркивает удивительность гипотезы 2: делимости на разные простые числа $\text{[math]}$ и $\text{[math]}$ , вроде как, независимы друг от друга, но, тем не менее, в гипотезе утверждается их строгая скоррелированность – как только остатки от деления на все $\text{[math]}$ обнуляются, остатки от деления на $\text{[math]}$ как-то об этом «узнают» и кооперативно, синхронно становятся ненулевыми.

Очевидно, достаточно рассматривать лишь случай $\text{[math]}$ , т.к. если $\text{[math]}$ насыщенна, т.е. если $\text{[math]}$ , то $\text{[math]}$ , но при $\text{[math]}$ гипотеза автоматически выполняется (потому что само число $\text{[math]}$ сильно насыщенно).

Функция $\text{[math]}$ позволяет записать необходимое условие сильной насыщенности в виде $\text{[math]}$ , т.е. переформулировать специальный случай гипотезы как $\text{[math]}$ (причём, тривиально выполняется $\text{[math]}$ , а вот усиление $\text{[math]}$ до $\text{[math]}$ , – по видимому, непростая задача).

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

Лемма 1

Если из насыщенной $\text{[math]}$ выбросить одно слагаемое, то оставшаяся сумма будет делиться на это удалённое слагаемое.

Доказательство

Насыщенная $\text{[math]}$ делится на $\text{[math]}$ (по определению), а это означает, что $\text{[math]}$ делится на любой делитель числа $\text{[math]}$ , в частности, $\text{[math]}$ . Делители $\text{[math]}$ интересны тем, что $\text{[math]}$ выполняется

$\text{[math]}$

Но такая сумма, очевидно, может быть целым числом только если после вычитания $\text{[math]}$ остаётся целая сумма $\text{[math]}$ , т.е. если $\text{[math]}$ или, что то же самое, $\text{[math]}$ делится на $\text{[math]}$ . $\text{[math]}$

Факторизация с двойкой

Если наблюдение 2 выполняется (хотя я и не очень в это верю), то, возможно, это позволяет немного продвинуться для случая $\text{[math]}$ , т.е. для факторизаций, содержащих двойку.

Гипотеза 3 (частный случай гипотезы 2)

Если $\text{[math]}$ – чётное число, то $\text{[math]}$ .

(Первая версия доказательства писалась для специального случая попарно-различных факторов числа $\text{[math]}$ , но потом стало понятно, что без этого требования можно обойтись; так, в нижеслующем варианте доказательства, кроме делимости на 2, других явных ограничений на факторизацию $\text{[math]}$ не накладывается.)

Набросок доказательства

(Предполагается верность [не доказанного окончательно] наблюдения 2.)

Если для некоторого $\text{[math]}$ частичная сумма $\text{[math]}$ достигла насыщения, то $\text{[math]}$ . Из этого следует, что $\text{[math]}$ и, в частности, $\text{[math]}$ .

Дальнейшее доказательство будет вестись от противного, поэтому предположим, что $\text{[math]}$ , т.е., что $\text{[math]}$ , такое, что $\text{[math]}$ .

Т.к. $\text{[math]}$ , то $\text{[math]}$ . Поэтому, если в факторизации $\text{[math]}$ содержится $\text{[math]}$ , то после деления $\text{[math]}$ на $\text{[math]}$ , частное всё-равно будет делиться на $\text{[math]}$ . Т.е. будет выполняться:

$\text{[math]}$

Слагаемое при $\text{[math]}$ можно вынести в $\text{[math]}$ за знак суммирования (cf. лемма 1):

$\text{[math]}$

Для целочисленности суммы $\text{[math]}$ необходимо, чтобы сумма остатков от деления $\text{[math]}$ и единицы на $\text{[math]}$ была кратна $\text{[math]}$ . С использованием обозначения $\text{[math]}$ , обозначающего остаток от деления $\text{[math]}$ на $\text{[math]}$ , это условие можно записать как $\text{[math]}$ .

Т.к. единица не делится на $\text{[math]}$ , то первое слагаемое со знаком суммирования тоже не должно делиться на $\text{[math]}$ . Также следует заметить, что слагаемое $\text{[math]}$ не зависит от $\text{[math]}$ . Всё это приводит к $\text{[math]}$ . Если я не ошибаюсь, такое условие можно снова «умножить» на $\text{[math]}$ (т.е. умножить обе части лежащего в основе сравнения по модулю $\text{[math]}$ ) и получить выражение

$\text{[math]}$

Выражение $\text{[math]}$ было получено выбрасыванием $\text{[math]}$ из $\text{[math]}$ , но этот же процесс можно повторить и для другого индекса $\text{[math]}$ , в результате чего будет получено аналогичное выражение $\text{[math]}$ . Вычитание последнего выражения из $\text{[math]}$ даёт $\text{[math]}$ Суммы в левой части этого сравнения отличаются только наличием/отсутствием слагаемых $\text{[math]}$ и $\text{[math]}$ , поэтому после приведения подобных слагаемых мы получим

$\text{[math]}$

Если наблюдение 2 верно, то для случая $\text{[math]}$ выполняется $\text{[math]}$ . Это входит в противоречие с $\text{[math]}$ и, т.о., опровергает сделанное ранее предположение о том, что $\text{[math]}$ . $\text{[math]}$

Факторизация без двойки и без повторов

Предложение 2 (критерии делителя)

Т.к. число $\text{[math]}$ делится на все «разрешённые» модули $\text{[math]}$ и не делится на «запретные» модули $\text{[math]}$ , то любой делитель $\text{[math]}$ числа $\text{[math]}$ должен делиться хотя-бы на один из модулей $\text{[math]}$ и не должен делиться ни на один из $\text{[math]}$ . Если число $\text{[math]}$ удовлетворяет этим необходимым критериям, то оно, возможно, является делителем $\text{[math]}$ .

Иначе говоря, если число $\text{[math]}$ не делится ни на один из $\text{[math]}$ и/или делится на один или несколько модулей $\text{[math]}$ , то $\text{[math]}$ – точно не делитель числа $\text{[math]}$ . (В силу очевидности, я думаю, предложение 2 в доказательстве не нуждается.)

В контексте разбора случая факторизуемости $\text{[math]}$ без повторов, стоит уделить особое внимание наблюдению 1. Напомню, что это наблюдение утверждает, что для нечётных $\text{[math]}$ , насыщенных частичных сумм не бывает вообще (при каноническом порядке делителей). Я до сих пор не знаю как подступиться к этой проблеме, но хотелось бы сделать следующее «статистическое» замечание о роли нечётности $\text{[math]}$ и о возможном подходе к доказательству. Как я уже говорил ранее, при попытке доказательства по индукции, первый и последний шаги не представляют трудности и могут пока игнорироваться).

Итак.

Набросок доказательства наблюдения 1

Для «общего» шага индукции, предполагается, что очередная $\text{[math]}$ ненасыщенна, т.е. она, возможно, делится на некоторые из модулей $\text{[math]}$ , но совершенно точно не делится на некоторые другие из них. Нужно показать, что новая сумма $\text{[math]}$ ведёт себя так же и не делится хотя-бы на один такой модуль.

Не все комбинации делимостей $\text{[math]}$ и $\text{[math]}$ на $\text{[math]}$ «интересны». Действительно, если из чисел $\text{[math]}$ и $\text{[math]}$ только одно делится без остатка на $\text{[math]}$ , то результат, новая частичная сумма $\text{[math]}$ не будет делиться на $\text{[math]}$ и, т.о., новая частичная сумма автоматически станет ненасыщенной. Если же оба числа делятся на модуль $\text{[math]}$ , то новая частичная сумма $\text{[math]}$ будет делиться на $\text{[math]}$ и здесь уже ничего не поделаешь. Интересным остаётся только случай при котором ни $\text{[math]}$ , ни $\text{[math]}$ не делятся на $\text{[math]}$ .

Именно на этом этапе уместно сделать замечание о возможной роли нечётности $\text{[math]}$ – если $\text{[math]}$ чётно, то $\text{[math]}$ и вышеописанным интересным сравнением может стать сравнение по модулю $\text{[math]}$ , а именно $\text{[math]}$ , выполняющемся если $\text{[math]}$ и $\text{[math]}$ нечётны. Как видите, интересное сравнение становится неинтересным (результат всегда делится на 2) и шансы, грубо говоря, распределяются поровну для делимости и неделимости $\text{[math]}$ на $\text{[math]}$ .

В то время как при $\text{[math]}$ , среди $\text{[math]}$ двойки нет, и у сравнения $\text{[math]}$ , с некоторой «вероятностью», остаток $\text{[math]}$ будет ненулевым и среди всех возможных комбинаций делимостей $\text{[math]}$ и $\text{[math]}$ на $\text{[math]}$ будет некоторый статистический перевес в сторону некратности $\text{[math]}$ модулю $\text{[math]}$ . Заметьте, что этот аргумент касается только одного сравнения по модулю $\text{[math]}$ , и мне неизвестно, может ли всего-лишь это одно сравнение полностью запретить или разрешить насыщенные частичные суммы. Я лишь поделился самим наблюдением о небольшой асимметрии…

Но вернёмся к разработке стратегии индуктивного доказательства запрета насыщенных частичных сумм делителей именно нечётного числа $\text{[math]}$ . Итак, мы находимся на одном из промежуточных шагов индукции, $\text{[math]}$ и $\text{[math]}$ оба не делятся хотя-бы на некоторые модули $\text{[math]}$ . Более конкретно, пусть $\text{[math]}$ и $\text{[math]}$ , где остатки $\text{[math]}$ . Сложение этих двух сравнений даёт $\text{[math]}$ . Допустим, что вопреки ожиданиям и целям, $\text{[math]}$ (предположение для опровержения методом «от противного»). Тогда, вычитая из предпоследнего сравнения последнее получаем $\text{[math]}$ , откуда $\text{[math]}$ . Вместе с $\text{[math]}$ это даёт $\text{[math]}$ (если я нигде не ошибся).

Такую систему (при пробегании индексом $\text{[math]}$ всех допустимых значений) можно решить относительно $\text{[math]}$ с помощью конструктивной версии К.Т.О. Должно получиться что-то вроде $\text{[math]}$ , где

$\text{[math]}$

(N.B. Я пишу $\text{[math]}$ вместо $\text{[math]}$ – чтобы читатель не спутал просто дробь в скобках с каким-нибудь там символом Лежандра. :) )

Значения полученные с помощью $\text{[math]}$ выглядят подозрительно (слишком большими), поэтому я решил в качестве решения использовать $\text{[math]}$ [хотя пока и не знаю как обосновать законность этого, немного «подгоночного» шага]. Но главная идея здесь заключается в проверке полученной оценки «делителя» $\text{[math]}$ числа $\text{[math]}$ на соответствие её критериям из предложения 2 – если $\text{[math]}$ не делится ни на какие модули $\text{[math]}$ или, наоборот, делится пусть даже на всего один модуль из $\text{[math]}$ , то это приведёт к противоречию (т.к. число $\text{[math]}$ , сравнимое с $\text{[math]}$ по модулю $\text{[math]}$ , определённо, по-построению, является делителем $\text{[math]}$ ) и, понятное дело, к опровержению сделанного допущения $\text{[math]}$ .

Находить остаток от деления суммы $\text{[math]}$ на $\text{[math]}$ и проверять его делимости на допустимые $\text{[math]}$ и запрещённые $\text{[math]}$ модули страшновато. Но интересно эмпирическое наблюдение:

Наблюдение 3

Для рассматриваемого случая, т.е. для нечётных $\text{[math]}$ и частичных сумм, отличных от первой, «аппроксимация» $\text{[math]}$ делителя $\text{[math]}$ грубо нарушает критерии предложения 2. А именно, эти аппроксимации почему-то не делятся ни на один $\text{[math]}$ и в то же самое время делятся хотя-бы на один $\text{[math]}$ .

Критерий с делимостью на модули $\text{[math]}$ проверить, возможно, проще. Это ощущение основано на следующем факте.

Предложение: $\text{[math]}$ верно $\text{[math]}$ .

Доказательство

Действительно, обозначим $\text{[math]}$ , тогда $\text{[math]}$ и $\text{[math]}$ для некоторых целых $\text{[math]}$ , $\text{[math]}$ . Также, для целых $\text{[math]}$ и $\text{[math]}$ , $\text{[math]}$ и $\text{[math]}$ . Подставляя, получаем $\text{[math]}$ , т.е. $\text{[math]}$ или $\text{[math]}$ , как и требовалось. $\text{[math]}$

Т.е., т.к. $\text{[math]}$ , то вместо деления $\text{[math]}$ на $\text{[math]}$ и проверки делимости полученного остатка на $\text{[math]}$ можно ограничиться только нахождением остатка от деления на $\text{[math]}$ . Тогда результат численных экспериментов можно упростить до

$\text{[math]}$
где $\text{[math]}$ (из-за $\text{[math]}$ ).

Уже не так страшно; но дальше я продвигался очень неуверенно. Непонятно, как формально показать выполнение этого предположения; и непонятно, действительно ли его выполнение будет искомым противоречием…

Что касается первого вопроса (о выполнении условия $\text{[math]}$ ), то можно попробовать рассмотреть игрушечный случай лишь с двумя факторами в числе $\text{[math]}$ . Итак, пусть $\text{[math]}$ при $\text{[math]}$ и $\text{[math]}$ . Ограничимся проверкой условия $\text{[math]}$ для $\text{[math]}$ (т.к. ситуация с $\text{[math]}$ будет полностью аналогичной). Такая проверка тогда сводится к проверке дробности частного

$\text{[math]}$
Видно, что из-за $\text{[math]}$ в обоих слагаемых не менее двух множителей в числителях (возможно роль нечётности $\text{[math]}$ критически важна и здесь). Поэтому один из множителей $\text{[math]}$ в числителе второй дроби сокращается с $\text{[math]}$ из знаменателя и как минимум один $\text{[math]}$ остаётся в числителе, делая эту дробь целой и сводя проверку условия $\text{[math]}$ к проверке нецелочисленности первой дроби. Также видно, что в первой дроби ничего не сокращается ( $\text{[math]}$ – суть остатки от деления $\text{[math]}$ на $\text{[math]}$ , удовлетворяющие $\text{[math]}$ и в силу этого не могущие сокращаться с $\text{[math]}$ ) и поэтому её значение обязано быть дробным.

Раз то же самое можно проделать и с делением на $\text{[math]}$ , то приходится заключить, что для частного случая $\text{[math]}$ , полученная с помощью К.Т.О. оценка делителей числа $\text{[math]}$ не удовлетворяет критериям делителя и приводит к противоречию, доказывая (при допущении корректности сделанного ранее подгоночного шага со взятием остатка по модулю $\text{[math]}$ ) наблюдение 1 об отсутствии насыщенных частичных сумм для нечётных $\text{[math]}$ .

Для более общего случая $\text{[math]}$ всё немного сложнее (но схема та же). Для проверки делимости выражения из $\text{[math]}$ , разделим его на $\text{[math]}$ и разложим сумму, выделив в ней одно слагаемое:

$\text{[math]}$

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

Т.к. рассматривается случай $\text{[math]}$ (для простых $\text{[math]}$ справедливо утверждение 2), то у числа $\text{[math]}$ больше двух простых делителей, что приводит к неравенству нулю обоих подвыражений $\text{[math]}$ и $\text{[math]}$ (хотя, обращаться к утверждению 2 необязательно – если всё-таки $\text{[math]}$ , то подвыражение $\text{[math]}$ , и только оно, обратится в ноль, но т.к. ноль есть число целое, то подвыражение $\text{[math]}$ всё-равно никак не повлияет на дробность или целочисленность всей суммы подвыражений $\text{[math]}$ и $\text{[math]}$ ).

Сначала проанализируем подвыражение $\text{[math]}$ более подробно. В каждом слагаемом разделим $\text{[math]}$ на $\text{[math]}$ . Т.к. $\text{[math]}$ и степень, в которую возводится каждое слагаемое, не меньше двух (из-за нечётности $\text{[math]}$ ), то $\text{[math]}$ и один из этих $\text{[math]}$ множителей можно будет поделить на $\text{[math]}$ , в результате чего в знаменателе вообще ничего не останется, и текущее слагаемое, — а значит и вся сумма $\text{[math]}$ , — будет целым числом, из-за чего подвыражение $\text{[math]}$ можно в дальнейшем игнорировать.

Теперь, по-аналогии, перейдём к подвыражению $\text{[math]}$ . Деление $\text{[math]}$ на $\text{[math]}$ вычеркивает фактор $\text{[math]}$ из $\text{[math]}$ . Поэтому, подвыражение $\text{[math]}$ можно преобразовать в

$\text{[math]}$
В произведении, возведённом в степень, можно перегруппировать множители, и тогда подвыражение $\text{[math]}$ запишется как
$\text{[math]}$
Видно, что из-за $\text{[math]}$ , вся формула представляет собой дробь, числитель которой – целое число, не содержащее фактора $\text{[math]}$ ( $\text{[math]}$ – есть остаток от деления $\text{[math]}$ на $\text{[math]}$ , т.е. $\text{[math]}$ и, следовательно, тоже не может содержать фактор $\text{[math]}$ ), а в знаменателе находится $\text{[math]}$ . Такая дробь не может быть целой.

Опять получили нарушение предложения 2, а значит и противоречие, доказывающее наблюдение 1.

Строго говоря, чтобы завершить эту попытку доказательства наблюдения 1, понадобится описать ещё базовый случай. При каноническом, возрастающем порядке следования делителей, база индукции будет соответствовать случаю $\text{[math]}$ . Он очевиден, т.к. $\text{[math]}$ и поэтому $\text{[math]}$ не делится ни на какой из $\text{[math]}$ , т.е. $\text{[math]}$ – не является насыщенной.

(Последний шаг интересен сам по себе. Для него, опять же при каноническом порядке делителей, очередной добавляемый делитель равен самому числу $\text{[math]}$ , т.е. следующая сумма выглядит как $\text{[math]}$ , где $\text{[math]}$ , по предположению индукции, ненасыщенна, т.е. не делится на $\text{[math]}$ . Неделимость на $\text{[math]}$ означает, что $\text{[math]}$ для некоторых $\text{[math]}$ и $\text{[math]}$ . Тогда $\text{[math]}$ .)

Набросок доказательства наблюдения 1 для частного случая факторизации без повторов завершён. $\text{[math]}$

И на этой ноте, первую часть вводного мини-отчёта об основах «теории насыщения» я пока прерву. :)

Заключение

Я не знаю, смогут ли приведённые в этом сообщении интуитивные доводы и экспериментальные наблюдения лечь в основу полноценного доказательства феномена из гипотезы 2. Но, надеюсь, я смог поделиться с читателями моей заинтересованностью в «теории насыщения». Феномен, лежащий в основе этой небольшой теории, имеет и самостоятельную ценность и, потенциально, может иметь «прикладное» значение в других задачах теории чисел.

Рассуждения, в основном, проводились для весьма частного случая разложимости данного числа на простые множители без повторов. Особых, принципиальных препятствий для обобщения на произвольные числа пока не видно. (Действительно, что если вместо простых $\text{[math]}$ брать взаимно простые модули вида $\text{[math]}$ из канонического разложения $\text{[math]}$ , где $\text{[math]}$ и $\text{[math]}$ ? Китайская теорема об остатках прекрасно работает с такими модулями; другие фрагменты рассуждений тоже потенциально могут быть адаптированы к взаимно простым модулям вместо простых… Осталось аккуратно переписать всё для этого наиболее общего случая, но желательно после «отладки» имеющейся схемы рассуждений; вдруг там слишком много ошибок?)

Предварительные итоги: наблюдения 1, 2, а также гипотезы 1, 2 и 3 выполняются для всех чисел, до которых я только смог и захотел дотянуться. :) Возможно, хотя я и не уверен, что из наблюдения 1 и гипотезы 3 выводится гипотеза 2 (все связи уже были показаны в этом сообщении; наблюдение 1 покрывает случаи нечётных $\text{[math]}$ , гипотеза 3 – чётных). Ну а сама гипотеза 2 может обобщать некоторые интересные вещи из теории чисел (правда, утверждать это наверняка, тоже пока преждевременно).

Гипотеза 1 остаётся открытой, хотя для моих нужд вполне достаточно и гипотезы 2.

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

Обновление (август, 2021): Я написал продолжение, вторую часть этой серии сообщений. Среди прочего, там, в приложении после списка литературы, размещена «заплатка», позволяющая обобщить результаты, полученные ранее для специального случая равенства степеней факторов единице. По крайней мере, теперь в наличии есть все фрагменты, необходимые для написания [наброска] полного доказательства гипотезы 2. Ситуация с идейной и технической корректностью рассуждений, впрочем, всё так же не прояснилась. :)

Ссылки

1. http://en.wikipedia.org/wiki/saturation_arithmetic
2. Stan B. и др. On Weird and Pseudoperfect Numbers. 1974
3. Euler L. Observation de summis divisorum. 1760 http://eulerarchive.maa.org/backup/E243.html
4. Euler L. An observation on the sums of divisors / пер. Bell J. 2009 http://arxiv.org/abs/math/0411587
5. http://en.wikipedia.org/wiki/smooth_number

М.И.Никитин
г.Алматы, июль, 2021
(последняя правка: август, 2021)

Тео­рия насы­ще­ния. Часть I.

Содер­жа­ние:

Ввод­ные заме­ча­ния

Неко­то­рые опре­де­ле­ния

Основ­ная про­блема

Спе­ци­аль­ный слу­чай

Фак­то­ри­за­ция с двой­кой

Фак­то­ри­за­ция без двойки и без повто­ров

Заклю­че­ние

Ссылки

Теория насыщения. Часть I.

Содержание:

Вводные замечания

Некоторые определения

Основная проблема

Специальный случай

Факторизация с двойкой

Факторизация без двойки и без повторов

Заключение