RUS  ENG
Полная версия
ЖУРНАЛЫ // Дискретный анализ и исследование операций // Архив

Дискретн. анализ и исслед. опер., 2018, том 25, выпуск 4, страницы 97–111 (Mi da911)

Число $k$-сумм в абелевой группе

А. А. Сапоженко, В. Г. Саргсян

Московский гос. университет им. М. В. Ломоносова, Ленинские горы, 1, 119991 Москва, Россия

Аннотация: Сумма подмножеств $A_1,\dots,A_k$ абелевой группы $G$ определяется как совокупность всех сумм $k$ элементов из множеств $A_1,\dots,A_k$, т.е. $A_1+\dots+A_k=\{a_1+\dots+a_k\mid a_1\in A_1,\dots,a_k\in A_k\}$. Подмножество, представимое в виде суммы $k$ подмножеств абелевой группы $G$, назовём $k$-суммой. Рассматривается задача о числе $k$-сумм в абелевой группе $G$. Очевидно, что любое подмножество $A$ абелевой группы $G$ является $k$-суммой, так как подмножество $A$ можно представить в виде суммы $A=A_1+\dots+A_k$, где $A_1=A$ и $A_2=\dots=A_k=\{0\}$. Тем самым число $k$-сумм равно количеству всех подмножеств абелевой группы $G$. Однако если ввести ограничение на мощность слагаемых $A_1,\dots,A_k,$ то число $k$-сумм становится существенно меньше. Получены нижняя и верхняя асимптотические оценки на число $k$-сумм в абелевых группах при условии, что существует слагаемое $A_i$ такое, что $|A_i|\geq n\log^qn$ и $|A_1+\dots+A_{i-1}+A_{i+1}+\dots+A_k|\geq n\log^qn$, где $q=-1/8$ и $i\in\{1,\dots,k\}$. Библиогр. 8.

Ключевые слова: множество, характеристическая функция, группа, прогрессия, смежный класс.

УДК: 519.1

Статья поступила: 29.01.2018
Переработанный вариант: 13.06.2018

DOI: 10.17377/daio.2018.25.608


 Англоязычная версия: Journal of Applied and Industrial Mathematics, 2018, 12:4, 729–737

Реферативные базы данных:


© МИАН, 2024