Журнал вычислительной математики и математической физики, 2022, T. 62, № 9, стр. 1447-1457

1. ВВЕДЕНИЕ

Линейные диофантовы уравнения и неравенства являются стандартным объектом для различного рода математических моделей, относящихся к целочисленной оптимизации, защите информации, теории чисел, геометрии и т.д.

Это уравнение имеет вид

где компоненты n-мерного вектора ${\mathbf{x}} = ({{x}_{1}},...,{{x}_{n}})$, а также коэффициенты b, a₁, …, a_n – неотрицательные целые числа.

Вопросы разрешимости этого уравнения, нахождения решения и числа всех решений этого уравнения – частные случаи известной в области исследования операций и комбинаторной оптимизации задачи целочисленного линейного программирования. Эта задача или ее обобщения и сужения занимают ключевое место среди задач дискретной оптимизации, как это показано, например, в [1]. То, что задача о рюкзаке и задача целочисленного линейного программирования в общем случае являются NP-полными, было установлено в числе первых результатов подобных исследований (см., например, [1], [2]). Кроме того, в классической публикации [2] можно найти многочисленные примеры известных задач, которые к ним сводятся, и, наоборот, задача целочисленного линейного программирования (или ее булев вариант) сводится к той или иной прикладной проблеме.

С другой стороны, дифантово уравнение и его частные случаи – предмет исследования в таких областях, как алгебра, теория чисел, криптография и др. Примерами здесь могут служить работы [3]–[6].

Данная статья в одной из своих частей является продолжением исследований авторов, опубликованных в [7], [8], где речь шла про задачу о рюкзаке. Ключевую роль в получении результатов там сыграл аппарат производящих функций (см. [9]), который используется и в настоящей статье. Как видно, в частности, из подробной монографии [10], где приводится обширный обзор результатов, связанных с задачей о рюкзаке, данный подход позволил в [7] и [8] получить ряд новых свойств и соотношений, касающихся числа решений этой задачи и множества ее решений.

С прикладной точки зрения, изучаемая проблематика затрагивалась авторами данной статьи в [11] и [12] в связи с криптографическими объектами: аннигиляторами и алгебраической иммунностью. Одно из ключевых утверждений публикации [11], посвященной аннигиляторам и алгебраической иммунности, базируется на анализе совместимости системы уравнений и сводится к нахождению комбинаторной характеристики (аналога ранга) матрицы.

Исследования в той же области, но другими методами проводились, например, в [13] и [14].

В данной статье уделено внимание линейному диофантову уравнению специального вида, связанного с проблемой Фробениуса.

Пусть А = {a₁, …, a_k} — возрастающая последовательность натуральных чисел, k > 1, $\left\langle A \right\rangle $ — аддитивная полугруппа, порожденная множеством А. Полугруппа $\left\langle A \right\rangle $ состоит из всех линейных комбинаций чисел a₁, …, a_k с целыми неотрицательными коэффициентами.

Множество А называется примитивным, если НОД(a₁, …, a_k ) = 1.

Для случая частного случая k = 2 известен следующий результат (см. [15], [16]).

Теорема Сильвестра. Порожденная взаимно простыми числами a и b полугруппа содержит все целые числа, начиная с N(a, b) = (a – 1)(b – 1).

Добавляя образующие, из этой теоремы легко вывести общий результат для любого k.

Теорема 1. Если множество А примитивное, то найдется N(a₁, …, a_k) такое, что $t \in \left\langle A \right\rangle $ при любом натуральном t ≥ N(a₁, …, a_k).

В большинстве публикаций на эту тему именно N(a₁, …, a_k) называется числом Фробениуса (см., например, [17]). Однако заметим, что есть и разночтения в терминологии. В некоторых источниках, например в [3], числом Фробениуса называют величину N(a₁, …, a_k) – 1, т.е. максимальное $t \notin \left\langle A \right\rangle $.

Мы в нашем тексте будем придерживаться первого варианта.

Пусть N – множество всех натуральных чисел. Обозначим через С(А) множество всех чисел t таких, что $t \notin N{\text{/}}\left\langle A \right\rangle $.

Задача нахождения числа N(a₁, …, a_k) известна как диофантова проблема Фробениуса (ПФ). Нахождение же всего множества С(А) обычно называется расширенной проблемой Фробениуса (РПФ).

ПФ и РПФ – популярная тематика исследований алгебраистов, специалистов в теории чисел, криптографов, а в последние десятилетия она привлекает внимание специалистов в области защиты информации (см., например, [3]–[5]).

В [5] опубликован достаточно подробный обзор основных результатов по этим проблемам, полученных до 2005 г.

Как было уже сказано выше, ПФ и РПФ для k = 2 были решены еще в 1884 г. (см. [15], [16]). Для произвольного случая изучались асимптотика и оценки числа Фробениуса, например, в [18], [19].

Алгоритм решения РПФ при k = 3 получен в [20], оценена сложность алгоритма.

Формула решения ПФ при k > 2 не была получена, уже при k = 3 в [21] доказаны утверждения, объясняющие принципиальные затруднения, связанные с этой проблемой.

Точные формулы имеются лишь для частных случаев. Различные частные случаи для k = 3 изучаются во многих работах, например, в статьях [22] и [23]. В [22] наряду с собственными результатами дается и обзор некоторых аспектов состояния проблемы на 2017 г.

Существуют и специфические постановки, которые выглядят как обобщение ПФ. В качестве примера можно привести [24].

С алгебраической точки зрения можно наложить определенные ограничения на полугруппу $\left\langle A \right\rangle $ и решать ПФ для полученного частного случая, как это делается в статьях [25]–[27].

Проблема исследовалась и с алгоритмической точки зрения. Например, в [28] представлен теоретико-графовый алгоритм определения N(a₁, …, a_k) со сложностью $O({{a}_{1}}(k + \log {{a}_{1}}))$. Здесь ПФ сведена к поиску определенного вида наибольшего кратчайшего пути в орграфе с а₁ вершинами и с ka₁ дугами, где из каждой вершины исходит k дуг весов a₁, …, a_k соответственно.

В [29] для РПФ и ПФ предложена редукция множества А к собственному подмножеству, снижающая сложность задачи в ряде случаев. Алгоритмы не дают аналитической формулы для числа Фробениуса.

Верхние оценки для числа Фробениуса тоже представляют прикладной интерес, как это, например, указано в учебнике по криптографическим методам защиты информации [3]. В [3], [4] и [5] приведены примеры результатов на эту тему.

Настоящая работа является продолжением исследований о разрешимости и нахождению числа решений линейных дифантовых уравнений, систем таких уравнений, неравенств и систем неравенств.

Данная статья в одной из своих частей является продолжением исследований авторов, опубликованных в [7], [8], где речь шла про задачу о рюкзаке, и непосредственным продолжением работы [30].

Статья состоит из введения, трех разделов и заключения. В разд. 2 исследуются линейное диофантово уравнение общего вида и один частный случай. Разд. 3 посвящен проблеме разбиения. В разд. 4 исследуются задачи, связанные с двухмерной проблемой Фробениуса.

2. О ЧИСЛЕ РЕШЕНИЙ ДИОФАНТОВА БУЛЕВА УРАВНЕНИЯ

Обозначим через ${{t}_{b}}({{a}_{1}},...,{{a}_{n}})$ число решений уравнения (1). Ясно, например, что положительность этого числа влечет за собой разрешимость уравнения.

Если на область определения переменных наложены ограничения, то, чем шире область определения, тем “вероятнее” разрешимость уравнения (1).

Заметим, что нахождение числа решений уравнения (1) тесно связано с известной задачей о разбиениях, т.е. с нахождением числа решений уравнения:

Если на x₁, x₂, …, x_k нет никаких ограничений, то число решений уравнения – это число разбиений n на натуральные слагаемые. Этот факт формально может быть выражен в терминах преобразования вектора x = (x₁, …, x_k) в вектор y = (y₁, …, y_n), где y_r, r = 1, …, n, – это число координат вектора x, равных натуральному r.

Таким образом, нахождения числа разбиений P_n для фиксированного n эквивалентно нахождению числа решений линейного диофантова уравнения

Пусть L(x₁, …, x_n) – линейная форма:

Для случая булевых переменных через L*(x₁, …, x_n) обозначим множество значений этой формы. Тогда вопрос о разрешимости уравнения (1) эквивалентен вопросу о принадлежности числа b этому множеству.

Рассмотрим производящую функцию последовательности {${{t}_{b}}({{a}_{1}},...,{{a}_{n}})$}:

Для нее известно соотношение

Оно является простым следствием определения, представленного соотношением (3). Действительно, из (3) следует

Утверждение 1. Справедливо соотношение

Очевидно, что эти формулы позволяют найти ${{t}_{b}}({{a}_{1}},...,{{a}_{n}})$ путем сравнения коэффициентов в левой и правой части. Кроме того, с их помощью можно найти оценки для ${{t}_{b}}({{a}_{1}},...,{{a}_{n}})$ и некоторые характеристики этой величины.

Пример 1. Если все a_i = 1, i = 1, …, n, то ${{F}_{{1,...,1}}}(z) = {{(1 - z)}^{{ - n}}}$ и ${{t}_{b}}(1,...,1) = {{( - 1)}^{b}}C_{b}^{{ - n}} = C_{b}^{{n + b - 1}} = C_{{n - 1}}^{{n + b - 1}}$.

Это хорошо известная формула для числа разбиений натурального b в сумму не более n слагаемых.

Пример 2. Если n = 2, то поведение функции ${{t}_{b}}({{a}_{1}},{{a}_{2}})$ в значительной мере определяется упомянутой выше теоремой Сильвестра (см., например, [14], [15]).

Согласно ей при условии взаимной простоты $({{a}_{1}},{{a}_{2}})$ = 1 уравнение разрешимо, если $b > {{a}_{1}}{{a}_{2}}$, и эта граница достижима. Таким образом, если ${{t}_{b}}({{a}_{1}},...,{{a}_{n}}) > 0$ для всех $b \geqslant {{b}_{0}}$ и ${{t}_{b}}({{a}_{1}},...,{{a}_{n}}) = 0$ для b = b₀ – 1, то значение числа Фробениуса равно ${{b}_{0}}$.

Для случая булевых переменных формула (4) имеет вид

Из (5) следует выражение для ${{t}_{{{{b}_{{}}}}}}({{a}_{1}},...,{{a}_{n}})$:

Пусть теперь ${{x}_{1}} \in {{A}_{1}},...{{,}^{{}}}{{x}_{n}} \in {{A}_{n}}$, где ${{A}_{1}},...,{{A}_{n}}$ – произвольные подмножества натурального ряда.

Тогда производящая функция ${{t}_{{{{b}_{{}}}}}}({{A}_{1}},...,{{A}_{n}})$ для числа решений уравнения (1) с такой структурой множества аргументов имеет вид:

И она может быть представлена следующим образом.

Пусть

есть производящая функция для множества ${{A}_{k}}$.

Непосредственно из (6) и (7) получаем

Утверждение 2. Справедлива формула

Пример 3. Пусть ${{A}_{k}} = \left\{ {0,1,2} \right\},k = 1,...,n$. Тогда ${{F}_{k}}(z) = \sum\nolimits_{x \in {{A}_{k}}}^{} {z_{{}}^{x}} = 1 + z + {{z}^{2}}$.

Отсюда следует ${{F}_{{{{A}_{1}},...,{{A}_{n}}}}}(z) = \prod\nolimits_{i = 1}^n {(1 + {{z}^{{{{a}_{i}}}}} + {{z}^{{2{{a}_{i}}}}})} $.

Определение 1. Среднее число решений уравнения (1) – это величина вида

Перейдем теперь к рассмотрению величины ${{\bar {t}}_{b}}$.

Заметим, что ни один коэффициент в разрешимом уравнении не может превосходить b. Поэтому он может принимать значения от 1 до b. Кроме того, мы предполагаем, что в уравнении ровно n слагаемых. Таким образом, при равномерном распределении значений b величина ${{\bar {t}}_{b}}$ – это среднее число представлений правой части уравнения линейной формой $\sum\nolimits_{i = 1}^n {{{a}_{i}}{{x}_{i}}} $.

Пусть

Лемма 1. Справедливо соотношение

где A_i – это число делителей числа i в множестве $\{ {{a}_{1}},...,{{a}_{n}}\} $.

Доказательство. Из (9) следует

Найдем коэффициент при z^N в (11). Вхождение z^N в s-ю сумму означает, что N = ra_s для какого-то r. Поэтому $N \equiv 0\left( {\bmod {{a}_{s}}} \right)$, что и доказывает утверждение леммы.

Теорема 2. Справедлива формула

Доказательство. По определению и из (8) имеем

Теперь используем предыдущую лемму и получаем соотношение

где $\tau (r)$ – число делителей r.

Производящая функция для числа делителей изучалась во многих работах (см., например, [6]). Для нее известно следующее соотношение:

Подставляем (14) в (13) и получаем (12).

Это завершает доказательство теоремы.

Следствие 1. Справедливо соотношение

3. ЗАДАЧА О РАЗБИЕНИИ

Рассмотрим задачу о разбиении – нахождении числа разбиений P_n для фиксированного n, что эквивалентно нахождению числа решений диофантова уравнения

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

Найдем методом коэффициентов выражение производящей функции для числа разбиений:

Из (16) и (17) следует

Отсюда и следует выражение для производящей функции

Мы привели классическое выражение для производящей функции числа разбиений.

Если все x_i различны, то на языке {y_i} это будет означать, что y_i ≤ 1, i = 1, …, n.

Пусть теперь $P_{n}^{0}$ – число разбиений n на различные слагаемые и $P_{n}^{0}(z) = \sum\nolimits_{n = 1}^\infty {P_{n}^{0}z_{{}}^{{{{n}_{{}}}}}} $ – производящая функция для него. Тогда аналогично предыдущему рассуждению, имеем

Отсюда следует

Теорема 3. Число разбиений на нечетные слагаемые равно числу разбиений на различные слагаемые.

Доказательство. Если все x_iнечетные, то на языке {y_i} это будет означать, что y_2r = 0, r = 1, …, [n/2].

Пусть теперь $P_{n}^{r}$ – число разбиений n на нечетные слагаемые и $P_{n}^{r}(z) = \sum\nolimits_{n = 1}^\infty {P_{n}^{r}z_{{}}^{{{{n}_{{}}}}}} $ – производящая функция для него.

Для краткости обозначим через ${v}(z)$ выражение

а через u(z) выражение $\prod\nolimits_{k = 1}^\infty {(1 + {{z}^{k}})} $.

Далее заметим, что

Но это означает, что

Тогда из (18) следует

Но в этом случае из (20) мы имеем равенство

Но тогда из этого равенства получаем

Этим завершается доказательство утверждения.

Таким образом, мы здесь привели новое доказательство известного факта из теории разбиений (см., например, [31]).

4. О ПРОБЛЕМЕ ФРОБЕНИУСА

Рассмотрим диофантово уравнение (21) с двумя переменными. Введенные ниже обозначения будут использованы всюду в дальнейшем тексте.

Здесь все числа натуральные. Как известно, эти уравнения разрешимы для всех n, начиная с некоторого – границы разрешимости: n₀(a, b, c) или n₀(a, b). По теореме Сильвестра для взаимно простых a и b:

В [30] используя метод производящих функций, получена формула для числа решений ${{t}_{n}}(a,b)$ уравнения (21) при условии (a, b) = 1, из которой следует не только результат Сильвестра, но и формула для x₀ и y₀, на которых “лежит” граница разрешимости.

Теорема 4. Если (a, b) = 1, то

где ${{x}_{0}}(n)$ и ${{y}_{0}}(n)$ – минимальные решения сравнений: $ax \equiv n(\bmod b)$ и $by \equiv n(\bmod a)$.

Следствие 2. При взаимно простых a и b из неравенства n > ab – (a + b) следует неравенство ${{t}_{n}}(a,b)$ > 0.

Доказательство. Так ${{x}_{0}} \leqslant b - 1$ и ${{y}_{0}} \leqslant a - 1$, то

Но по условию n > ab – (a + b). Отсюда и следует неравенство ${{t}_{n}}(a,b)$ > 0.

А это известная формула Сильвестра для двухмерного числа Фробениуса.

Формулу (22) можно записать в более “строгой” форме. Пусть $\varphi (k)$ – функция Эйлера (число чисел, меньших k и взаимно простых с k). Тогда очевидно, что сравнения $ax \equiv n(\bmod b)$ и $by \equiv n(\bmod a)$при взаимно простых a и b имеют единственные минимальные решения, представимые в виде:

Отсюда и получается другое выражение для формулы, задающей число решений уравнения (21):

Пример 4. Рассмотрим уравнение 4x + 7y = n.

При n = 12 из (017) следует ${{t}_{{12}}}(4,7) = \frac{{12}}{{28}} - \frac{{{{x}_{0}}(n)4 + {{y}_{0}}(n)7}}{{28}} + 1.$ Сравнения $4x \equiv 12(\bmod 7)$ и $7y \equiv 12(\bmod 4)$ имеют минимальные решения: ${{x}_{0}}(n) = 3$ и ${{y}_{0}}(n) = 0$. Отсюда ${{t}_{{12}}}(4,7) = \frac{{12}}{{28}} - $ $ - \;\frac{{12}}{{28}} + 1 = 1.$ Что и соответствует решению (3, 0).

При n = 13 из (017) следует ${{t}_{{13}}}(4,7) = \frac{{13}}{{28}} - \frac{{{{x}_{0}}(n)4 + {{y}_{0}}(n)7}}{{28}} + 1.$ Сравнения $4x \equiv 13(\bmod 7)$ и $7y \equiv 13(\bmod 4)$ имеют минимальные решения: ${{x}_{0}}(n) = 5$ и ${{y}_{0}}(n) = 3$. Отсюда ${{t}_{{13}}}(4,7) = \frac{{13}}{{28}} - $ $ - \;\frac{{41}}{{28}} + 1 = 0.$ Что и соответствует тому факту, что решений у уравнения нет.

При n = 32 из (017) следует ${{t}_{{32}}}(4,7) = \frac{{32}}{{28}} - \frac{{{{x}_{0}}(n)4 + {{y}_{0}}(n)7}}{{28}} + 1.$ Сравнения $4x \equiv 32(\bmod 7)$ и $7y \equiv 32(\bmod 4)$ имеют минимальные решения: ${{x}_{0}}(n) = 1$ и ${{y}_{0}}(n) = 0$. Отсюда ${{t}_{{32}}}(4,7) = \frac{{32}}{{28}} - $ $ - \;\frac{4}{{28}} + 1 = 2.$ Что и соответствует двум решениям: (8, 0) и (1, 4).

Следствие 3. Справедлива формула

Доказательство. Рассмотрим функцию

Заметим, что ${{L}_{{n + ab}}}(a,b) = {{L}_{n}}(a,b)$. Имеем периодическую функцию с периодом ab.

Из этого факта и (23) следует (24).

Рассмотрим теперь вопрос о “среднем числе” решений уравнения (21).

Очевидно, что $a,b \leqslant n$. Если параметры a и b равномерно распределены в квадрате nxn, то в качестве “среднего числа” решений можно взять следующую величину:

Величина ${{\bar {t}}_{n}}$ представляет определенный интерес, так как уравнение (21) может вовсе не иметь решений (например, если $(a,b)\not {\backslash }n$), быть разрешимым для всех n (если $(a,b) = 1,$ $n \geqslant (a - 1)(b - 1) - 1$ или находиться в любом из “промежуточных” случаев.

Пусть все параметры распределены независимо.

Лемма 2. Пусть $V = \left\{ {{{{v}}_{1}},...,{{{v}}_{k}}} \right\}$ – произвольное подмножество натуральных чисел. Тогда имеет место формула:

где ${{B}_{N}}$ – число делителей числа N, лежащих в множестве V и ${{B}_{0}} = k$.

Равенство (26) обосновывается следующим.

Во-первых, по определению справедливо равенство

Во-вторых, ${{B}_{N}}$ равно числу вхождений ${{z}^{N}}$ в (27). В-третьих, вхождение ${{z}^{N}}$ в s-ю сумму в (27) эквивалентно тому, что $N = r{{{v}}_{s}}$ для некоторого r. Поэтому $N \equiv {{0}_{{\bmod {{{v}}_{s}}}}}$. Из этого и вытекает утверждение леммы.

Пример 5. Если $V = \left\{ {2,4} \right\}$, то

тогда из леммы мы получаем, что

В качестве следствия из этой леммы можно получить соотношение

при N > 0.

Пусть

Тогда из леммы следует, что

Но это означает, что

Из (26) и (28) следует соотношение

Теорема 5. Справедливо соотношение

где $\tau (0) = n.$

Доказательство. Согласно введенным обозначениям, производящая функция для ${{t}_{n}}(a,b)$ выглядит следующим образом:

Далее, используя формулу Коши, получаем

Подставляем (31) в (25) и получаем соотношение

Далее обращаем внимание на то, что

Из (28), (31) и (32) следует, что

Но тогда из (26), (29) и (34) вытекает утверждение теоремы.

Следствие 4. Справедливо неравенство ${{\bar {t}}_{n}} \leqslant {{\log }^{2}}n$.

Доказательство. Применяем неравенство Коши к (34), учитывая (28), и получаем

Так как

то из (28) следует

Известно, что

Из (36) и (37) следует соотношение

Из этого соотношения и (34) получаем требуемое неравенство

Следствие доказано.

5. ЗАКЛЮЧЕНИЕ

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

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

В каждом из трех основных разделов работы главные результаты (их четыре) названы теоремами. Прикладные области, где они могут быть использованы, обсуждены частично во введении, где дан краткий экскурс по возможным постановкам задач и полученным результатам.