Содержание к диссертации
Введение
1 Вспомогательные определения и результаты - 12
1.1 Используемые обозначения 12
1.2 Разделимые множества 13
1.3 Вспомогательные теоретико-числовые утверждения . 17
1.4 Вспомогательные элементы комбинаторики 24
2 Порождение бинарных распределений рациональных вероятностей 25
2.1 Постановка задачи 25
2.2 Вспомогательные определения и утверждения 27
2.3 Доказательство теоремы 2 30
2.4 Замкнутые классы в PQ 31
2.5 Замыкания одноэлементных множеств чисел 38
2.6 Критерий порождаемости множеств G[{p}] 48
2.7 Критерий порождаемости множеств С?[{П}] для произвольного П 52
2.8 Основная лемма 57
2.9 Вспомогательные результаты для замыканий числовых множеств 64
2.10 Замыкания конечных множеств чисел 75
2.11 Проверка порождаемости чисел конечными множествами . 78
2.12 Замыкания бесконечных множеств чисел 80
2.13 Конечно порожденные замкнутые классы в PQ 82
2.14 Структура замкнутых классов в PQ 85
3 Порождение конечных распределений рациональных вероятностей 89
3.1 Постановка задачи 89
3.2 Вспомогательные определения и утверждения 91
3.3 Замкнутые классы в SQ 94
3.4 Вспомогательные результаты для стохастических векторов 100
3.5 Замыкания одноэлементных множеств двумерных векторов 120
3.6 Замыкания одноэлементных множеств векторов произвольной размерности 130
3.7 Замыкания конечных множеств двумерных векторов . 161
3.8 Замыкания конечных множеств векторов произвольной размерности 163
3.9 Проверка порождаемости стохастических векторов конечными множествами 164
3.10 Замыкания бесконечных множеств векторов произвольной размерности 168
3.11 Конечно порожденные замкнутые классы в SQ 170
3.12 Структура замкнутых классов в SQ 172
Заключение 175
Литература 176
- Вспомогательные теоретико-числовые утверждения
- Замыкания одноэлементных множеств чисел
- Замыкания бесконечных множеств чисел
- Замыкания одноэлементных множеств векторов произвольной размерности
Введение к работе
Работа посвящена исследованиям дискретных преобразований независимых вероятностных распределений. Под дискретным преобразованием вероятностных распределений понимается вероятностное распределение конечной случайной величины, значение которой является функцией от значений случайных величин с исходными вероятностными, распределениями. Такие преобразования играют важную роль в вопросах реализации случайностей, имеющих большое значение для многих разделов дискретной математики и математической кибернетики (см. [1, 29]), поскольку задача реализации случайностей фактически заключается в построении некоторой случайной величины 0 с произвольным требуемым распределением из имеющихся в распоряжении исходных источников случайностей Ci,...,Cfc с фиксированными вероятностными распределениями, отличными от требуемого распределения. Значение случайной величины Со, очевидно, должно быть функцией от значений случайных величин Сі, , Cfe- Поэтому построение величины Со состоит в задании функции / : fii х ... х fijfe —^ Г2о, где Пі — множество значений случайной величины Q, і = 0,1,...,к. Отметим, что если случайные величины Ci,---,Cfc являются независимыми в совокупности, вероятностное распределение случайной величины Со однозначно определяется функцией / и вероятностными распределениями величин Сі, , Cfc- Поэтому в этом случае мы можем говорить о том, что вероятностное распределение величины Со порождается множеством вероятностных распределений величин Ci> j Cfc посредством функции /. Соответственно, мы говорим, что вероятностное распределение порождается множеством вероятностных распределений, если это распределение порождается данным множеством посредством какой-либо подходящей функции.
При исследовании данного порождения вероятностных распределений мы, в первую очередь, сталкиваемся с проблемой выразимости, т. е. проблемой, заключающейся в том, чтобы выяснить, порождается ли задан-
ное вероятностное распределение заданным множеством исходных вероятностных распределений. Принципиальная трудность этой проблемы состоит, очевидно, в невозможности непосредственного описания произвольных множеств вероятностных распределений, поскольку даже в случае распределений случайных величин, принимающих только два значения, (бинарных вероятностных распределений) мощность множества всех таких распределений равна континууму. Поэтому естественным подходом в исследовании проблемы выразимости является рассмотрение этой проблемы для не более чем счетных подмножеств вероятностных распределений, всюду плотных на множестве всех вероятностных распределений. В случае распределений конечных случайных величин (конечных распределений) наиболее подходящим примером такого подмножества представляется множество SQ всевозможных конечных распределений, состоящих из рациональных вероятностей. В этом случае мы имеем проблему выразимости для распределений из SQ, т. е. проблему определения порожда-емости заданного вероятностного распределения заданным множеством исходных вероятностных распределений из SQ.
Для произвольного непустого множества П различных простых чисел во множестве SQ естественным образом выделяется подмножество jSGfn] всевозможных распределений вероятностей, представимых дробями, все простые делители знаменателей которых принадлежат множеству П. Отметим, что с практической точки зрения среди множеств вероятностных распределений наибольший интерес представляют конечно порожденные множества, т. е. множества, порождаемые своими конечными подмножествами.
Сначала мы исследуем наиболее изученный случай бинарных вероятностных распределений. Поскольку бинарное вероятностное распределение однозначно определяется какой-либо одной из вероятностей этого распределения, мы имеем взаимно однозначное соответствие между бинарными распределениями и числами из сегмента [0;1]. Поэтому для удобства вместо бинарных распределений мы рассматриваем соответствующие этим распределениям числа. В таком случае множеству всех бинарных распределений из SQ соответствует множество PQ всех рациональных чисел из сегмента [0; 1], а множеству всех бинарных распределений из 5(7(11] соответствует множество G[H] всех чисел из PQ, представимых дробями, знаменатели которых являются произведениями степеней чисел из множества П. Изучение порождения рациональных чисел из PQ было начато Р. Схиртладзе в работе [19], в которой установлено, что множество С?[{2}] порождается одним числом ^, и показано таким образом, что это
множество является конечно порожденным. Им же в [20] доказан аналогичный результат для множества С7[{3}]. Ф. Салимовым в [14] получено, что для любого конечного П, содержащего числа 2 или 3, существуют двухэлементные подмножества множества G[H], порождающие это множество.. Им же в [17] установлена конечная порожденность множеств G[U] для любого конечного П, и таким образом показано, что множество б^П] является конечно порожденным тогда и только тогда, когда П конечно. В настоящей работе для любого множества чисел из PQ дано явное описание всех чисел, порождаемых этим множеством, и тем самым получено полное решение проблемы выразимости для бинарных распределений из SQ. Предложен также эффективный алгоритм, который за полиномиальное время позволяет определить для любого заданного числа и любого заданного конечного множества чисел из PQ, порождается ли данное число данным множеством.
Другой важной проблемой, тесно связанной с проблемой выразимости, является проблема описания всех множеств распределений из SQ, замкнутых относительно рассматриваемого порождения распределений. Простейший пример таких замкнутых множеств представляют упомянутые выше множества 5G[n]. Ф. Салимовым в [17] доказано, что в случае бинарных распределений для любого множества П различных простых чисел и любого числа р из П множество G[II \ {р}] является предпол-ным1 замкнутым классом в множестве G[H]. Таким образом, была установлена структура диаграммы включений для множеств С[П]. Кроме того, в [17] было показано, что существуют замкнутые множества бинарных распределений из SQ, отличные от множеств Ст[П]. Используя полученное в настоящей работе решение проблемы выразимости для бинарных распределений из SQ, мы находим все замкнутые множества таких распределений. Мы также определяем структуру диаграммы включений для этих множеств. Кроме того, мы устанавливаем, какие из этих замкнутых множеств являются конечно порожденными, и для каждого конечно порожденного замкнутого множества непосредственно предъявляем конечное подмножество, порождающее это множество. В качестве следствий из полученных результатов мы приводим ряд результатов, касающихся структуры замкнутых множеств бинарных распределений из SQ.
После изучения бинарных вероятностных распределений мы переходим к исследованию порождения произвольных распределений из SQ.
1 Замкнутое множество А называется предполным классом в множестве В, если А С В и не существует замкнутого множества С такого, что А С С С В.
Заметим, что каждому конечному вероятностному распределению может быть сопоставлен вектор вероятностей этого распределения. Отметим, что этот вектор является стохастическим, т. е. все его компоненты неотрицательны и их сумма равна 1. Таким образом, без ограничения общности вероятностные распределения из SQ могут рассматриваться как стохастические векторы, все компоненты которых являются рациональными числами. Случай произвольных распределений из SQ исследовался ранее Ф. Салимовым в работах [15, 16, 18]. В [15] им было показано, что все множества S'Gfll], где П конечно, порождаются одноэлементными подмножествами, и тем самым установлено, что множество 5С?[П] является конечно порожденным тогда и только тогда, когда П конечно. Им же в [16] доказано, что для любого множества П различных простых чисел и любого числам из П множество 5С?[П\{р}] является предполным классом в мно- ' жестве SG[U]. Таким образом, диаграмма включений для множеств ^Cfll] полностью совпадает с диаграммой включений для множеств С?[П]. Кроме того, в [16] было найдено дополнительное семейство замкнутых множеств распределений из SQ, являющихся предполными классами в множествах iSG^n], и показано таким образом, что в каждом множестве 77(11] имеется по крайней мере счетное число предполных классов. Из результатов настоящей диссертации вытекает, что никаких других предполных классов, кроме найденных в [16], в множествах SGfll] не существует, т. е. что в [16] были в действительности найдены все предполные классы в множествах SG[U]. В диссертации результаты, полученные для бинарных распределений из SQ, обобщаются на случай произвольных распределений из SQ: для любого множества распределений из SQ дается явное описание всех распределений, порождаемых этим множеством, и предлагается эффек- * тивный алгоритм, который для любого заданного распределения и любого заданного конечного множества распределений из SQ за полиномиальное время позволяет определить, порождается ли данное распределение данным множеством. Исходя из полученного решения проблемы выразимости произвольных распределений из SQ, описываются все замкнутые множества таких распределений и определяется структура диаграммы включений для этих множеств. Также устанавливается, какие из этих множеств являются конечно порожденными, и для каждого конечно порожденного множества непосредственно указывается одноэлементное подмножество, порождающее это множество. Кроме того, аналогично случаю бинарных распределений приводится ряд результатов, касающихся структуры замкнутых множеств произвольных распределений из SQ.
Следует отметить, что в ряде работ рассматривалось порождение ве-
роятностных распределений с наложенными на него дополнительными ограничениями. Одним из таких ограничений является ограничение на класс функций, используемых для порождения распределений. Например, в [19, 20] рассматривалось порождение бинарных распределений в классе булевых функций, реализуемых бесповторными формулами над базисом {&, V}. Автором в работе [4]2 было показано, что в данном классе функций конечно порожденным является любое множество С^П], где П конечно и содержит по крайней мере два числа. Остается открытым вопрос о конечной порожденности в классе булевых функций, реализуемых бесповторными формулами над базисом {&,V}, множеств С7[{^}], где р — простое число, большее 3. Ряд результатов, связанных с порождением бинарных распределений в более широком классе булевых функций, реализуемых бесповторными контактными схемами, получен автором в [5]. Из этих результатов вытекает, что в плане своих выразительных возможностей данный класс функций является значительно более слабым, чем класс всех булевых функций. Поэтому представляется интересным выявление классов булевых функций, сопоставимых по выразительности с классом всех булевых функций. В разделе 2.3 главы 2 показывается, что таким классом может оказаться класс всех монотонных булевых функций: для некоторых конечных систем бинарных распределений замыкания этих систем относительно порождения в классе всех монотонных булевых функций совпадают с их замыканиями относительно порождения в классе всех булевых функций.
Другим естественным ограничением, которое может быть наложено на порождение вероятностных распределений, является ограничение на число исходных случайных величин. В данной работе мы полагаем, что для порождения распределений можно использовать неограниченное число независимых копий случайных величин с вероятностными распределениями из исходного множества распределений. Если ограничить возможное число таких копий, то мы имеем задачу оценки сложности порождения вероятностных распределений, где под сложностью порождения распределения понимается минимальное число исходных случайных величин, необходимое для порождения данного распределения. Такая сложность, очевидно, существенным образом зависит от исходного множества распределений. В работах [19, 20, 6, 7, 8, 24, 9] был получен ряд оценок сложности порождения бинарных распределений из SQ как в классе булевых
2Эта и другие работы автора, касающиеся вопросов, связанных с дополнительными ограничениями на порождение распределений, не включены в данную диссертацию.
функций, реализуемых бесповторными формулами над базисом {&, V}, так и в классе всех булевых функций. Однако в общем случае эта задача остается нерешенной даже для класса всех булевых функций. Отметим, что предложенные в данной работе методы порождения вероятностных распределений являются экономными в плане использования исходных случайных величин и поэтому могут оказаться полезными для решения данной проблемы. Другим сложностным аспектом порождения вероятностных распределений, изучавшимся ранее в литературе [3, 12], является минимальная сложность реализации функций, применяемых для порождения этих распределений.
Тесно связанной с задачей оценки сложности порождения вероятностных распределений является задача приближенного порождения вероятностных распределений, заключающаяся в том, чтобы из заданного числа исходных случайных величин с заданными распределениями построить случайную величину с распределением, наиболее близким к требуемому вероятностному распределению. Интересные результаты, касающиеся приближенного порождения распределений, получены Р. Схиртладзе и Н. Нурмеевым в работах [20, 11]. Важной задачей, близкой по тематике к рассматриваемым вопросам, является также задача о минимальном имплицирующем векторе [10].
Отметим, что в данной работе мы рассматриваем порождение распределений посредством функций, все значения которых являются значениями реализуемых ими случайных величин. Такое порождение можно назвать синхронным. Начиная с середины прошлого века, в ряде работ [25, 23, 21, 13] рассматривалось порождение распределений посредством функций, которые кроме значений реализуемых случайных величин принимают также "неопределенное"значение. "Неопреде-ленное"значение функции означает, что мы не можем получить значение реализуемой случайной величины на данном наборе значений исходных случайных величин и поэтому надо использовать новую порцию исходных случайных величин для повторной попытки реализации требуемой случайной величины. Поскольку в таком случае требуемая случайная величина может быть получена с некоторой задержкой, пропорциональной числу повторных попыток ее реализации, в отличие от рассматриваемого синхронного порождения такое порождение можно назвать асинхронным. Асинхронное порождение распределений является практичным в случае, если реализуется большая серия случайных величин и допускается неограниченно большая задержка в реализации между двумя последовательными случайными величинами из этой серии. В противном слу-
чае такой подход к порождению распределений является неприемлемым. Одним из возможных путей устранения этого недостатка асинхронного порождения представляется комбинирование асинхронного порождения с синхронным порождением, заключающееся в том, чтобы в случае достаточно большой задержки при реализации случайной величины применять синхронное порождение, т. е. функцию, не принимающую "неопределен-ное"значение.
Еще раз отметим, что в данной работе все исходные случайные величины, используемые для порождения распределений, преполагаются независимыми в совокупности. Н. Нисаном и Д. Зукерманом в [27] было показано, что для приближенного порождения распределений с произвольной точностью могут также использоваться исходные случайные величины, не являющиеся независимыми. Функции, применяемые в таком случае, называются экстракторами. В последние годы за рубежом проводились активные исследования экстракторов (см., например, [26, 28, 29, 30]). Существенным недостатком экстракторов является их сравнительно высокая сложность: экстракторы требуют большого числа исходных случайных величин, и, соответственно, большой оказывается также сложность вычисления значений экстрактора.
Полученные результаты представлены в работе следующим образом. Диссертация состоит из трех глав.
В главе 1 приведены вспомогательные теоретико-числовые и комбинаторные понятия и утверждения, используемые в работе. В частности, вводятся базовые для данной работы понятия разделимого множества натуральных чисел и наибольшего общего делителя разделимых множеств.
Вспомогательные теоретико-числовые утверждения
В работе мы используем следующие известные теоретико-числовые факты (см., например, [2]). Теорема 1 (Эйлера). Если (а, т) = 1 и тп 1, то av = 1 (mod га). Утверждение 8. Если (п,тп) = 1 их пробегает полную систему вычетов по модулю тп, то пх + п , где п — любое целое, тоже пробегает полную систему вычетов по модулю т. Рассмотрим сравнение первой степени с одним неизвестным Лемма 2. Сравнение (1.1) имеет решения тогда и только тогда, когда b делится на d = (п, тп). В этом случае все решения данного сравнения образуют класс вычетов по модулю m/d. . Следствие 1. Сравнение (1.1) является разрешимым в случае (n,m) = 1. Рассмотрим теперь систему сравнений с одним неизвестным где гп\, 7П2,..., rnk — попарно простые числа. Лемма 3. Система (1.2) всегда разрешима и все ее решения образуют класс вычетов по модулю т\ТП2 -.. rrik Согласно лемме 2 в случае, если b делится на d, сравнение (1.1) имеет решение. Это означает, что существуют целые хну такие, что nx+my Ь. Таким образом, мы получаем следующее утверждение. Утверждение 9. Если п,т Є N и b делится на (n,m), то уравнение nx + my = b разрешимо в целых числах. Из этого следствия нетрудно получить Следствие 2. Если п,т Є N и b делится на (п,тп), то найдутся натуральные , у такие, что х тп, у п и пх Л-my = b (mod mri). Утверждение 9 может быть обощено на случай уравнения с произвольным числом переменных Утверждение 10. Если b делится на (щ,..., щ), то уравнение (1.3) разрешимо в целых числах. Доказательство. Докажем данное утверждение индукцией по t. Базисом индукции для t = 2 служит утверждение 9. Предположим, что утверждение 10 справедливо для некоторого t 2. Пусть щ,..., nt+i є N и b делится на (щ,..., nm). Поскольку (пь ..., щ+х) = ((щ,..., nt), nt+1), согласно утверждению 9 существуют целые х , х" такие, что b = (ni,..., nt)x + nt.\-ix". По индуктивному предположению существуют целые xi,...,xt такие, что (n1}..., nt)x = щхі + ... + ntxt. Таким образом, 6 = щхі + ... + ntxt + nt+ix". В дальнейшем для удобства любое решение Х\ — ct\,..., xt = at уравнения (1.3) будем обозначать вектором (a\\...; at) и будем предполагать, что щ является максимальным среди натуральных чисел Щ,... ,nt. В этом случае утверждение 10 может быть усилено следующим образом. Утверждение 11. Если b делится на {щ,..., щ), то уравнение (1.3) имеет целочисленное решение (a\\...; at) такое, что Доказательство. Отметим, что, если b кратно (щ, ..., щ), то согласно утверждению 10 уравнение (1.3) имеет хотя бы одно целочисленное решение, и для любого целочисленного решения (/?i;...; /) этого уравнения имеется лишь конечное число других целочисленных решений (/?[;...; (5 t) таких, что max,-/?, — тіПгД- maxf/ — тгпгД. Поэтому найдется целочисленное решение {а.\;...; at) с минимальной разностью max сц — т\щ 0. Предположим, что Пусть среди ,, чисел a\,...,at максимальными, являются числа cfy(i),... ,aj (M), а минимальными — числа 0 /( ,...,0 /(,,). Рассмотрим случай i± v.
Для г = 1,..., t положим Заметим, что (о ;...; a t) также является целочисленным решением уравнения (1.3). Учитывая неравенство (1.5), нетрудно проверить, что любое число а { удовлетворяет неравенствам тіпг- щ а[ maxj 0. Таким образом, имеем неравенство max; а[ — minj о тахг- оц — minj о , противоречащее минимальности разности max 0 — пищ 0. Аналогичным образом получаем противоречие в случае ц р. Поэтому [а\;... ;at) удовлетворяет соотношению (1.4). Следствие 3. Если b делится на (щ,..., nt) и b п\ Y2i=i ni то уравнение (1.3) имеет целочисленное решение (ai;...; at) такое, что любое число а{ удовлетворяет неравенствам Доказательство. Если b кратно (щ,... ,nt), то согласно утверждению 11 уравнение (1.3) имеет целочисленное решение (оті;...; at), удовлетворяющее соотношению (1.4). Предположим, что aj 0 для некоторого j. Тогда из соотношения (1.4) следует, что ai aj + щ щ для любого Следовательно, в этом случае (cui;... ;at) не может быть решением урав нения (1.3). Предположим теперь, что maXjQfi Л \-п\. Тогда из соот ношения (1.4) вытекаетет, что щ =— для любого г = 1,...,2. Поэтому Y i Щ&І b. Следовательно, в этом случае мы снова получаем противоречие с тем, что (ai;...;at) является решением уравнения (1.3). Таким образом, все числа щ удовлетворяют требуемым неравенствам. Будем теперь дополнительно предполагать, что t 3 и (щ,..., щ) = 1. Для і —. 1,2,... ,2 обозначим через Аг- наибольший общий делитель всех, чисел пі,..., щ, кроме числа щ, и положим Л = Л1Л2 -Xt. Отметим, что Поэтому все числа Ai,..., At являются попарно простыми. Пусть к Є N5"1. Обозначим через d наибольший общий делитель всех чисел n nv, где и = 2,3,...,2, v = 1,2,...,2 и v ф и. Обозначив через d наибольший общий делитель чисел n nv, где v = 1,2,...,2 и v ф и, равный числу нЛи, получим, что d — {с№\ d 3\... ,d ) = (пА2, П3А3,..., n\Xt). Следовательно, d является общим делителем чисел n2 А2 ... Xt, П3А2 ... At,..., п А2 ... А(, и поэтому d является делителем числа (п%Х2 ... At, п%А2... At,..., п Х2 ... At) = (п, nj,..., nkt)X2 ...Xt = A A2 ... Xt. С другой стороны, каждое из чисел А , A2,..., Xt является общим делителем чисел d(2\ d 3\ ..., dy и, следовательно, является делителем числа d. Поскольку числа Aj,A2,...,At являются попарно простыми, получаем тогда, что Aj А2 ... Xt является делителем числа d. Таким образом, d = AjA2 . А = А А. Утверждение 12. Для любого целого Ь, кратного числу X, найдутся целые неотрицательные числа а, где u,v — 2,3,... ,2 и и ф v, такие, что ос щ и выполняется соотношение Доказательство. Поскольку числа Л2,..., А( являются попарно простыми делителями числа щ, то п\ делится на А2...А4. Пусть щ = п[Х2---Af и b = п Х. Рассмотрим сравнение X\ lx = п (mod п[). Так как (ггьАі) = (щ, п2,..., nt) — 1, то (n A 1) = 1. Поэтому согласно следствию 1 это сравнение является разрешимым. Пусть х = /3 — произвольное решение этого сравнения. Согласно утверждению 10 существуют целые числа а", где и = 2,3,..., t, v = 1,2,..., t и v ф и, такие, что
Замыкания одноэлементных множеств чисел
Сначала исследуем случай замыканий одноэлементных множеств чисел из PQ. Очевидно, что {{0}) = ({1}) = {0,1}: Поэтому далее мы1 рассматриваем числа из интервала (0; 1). Поскольку любое рациональное число однозначно выражается некоторой несократимой дробью, без ограничения общности можно рассматривать только несократимые дроби из этого интервала. Пусть — произвольная несократимая дробь из интервала (0; 1). Тогда (1(п — 1),п) = 1. Поэтому мы-можем рассмотреть множество G[T(n); 1{п — 1) : 1]. Лемма 5. Пусть — несократимая дробь из интервала (1/2; 1). Тогда для любого є 0 существует К (є) такое, что для любой дроби - из G[T(n);l(n — I) : 1], удовлетворяющей условиям к К {є) и є - 1 — є, существует булева функция f(x\,..., Xk) такая, что /(0,..., 0) = /(1,...,1) = 0н = Р{/(1,.. .,!)} Доказательство. Из условия Є (1/2; 1), т. е. / п — I, получаем, что Пусть є 0. В качестве К (є) выберем такое число, чтобы любое к К(є) удовлетворяло следующим двум неравенствам: Без ограничения общности можно также считать, что к 3. Рассмотрим произвольную дробь -, удовлетворяющую условиям леммы. Поскольку Є G[X(n); l{n — l) : 1], числитель т кратен числу 1{п 1). Обозначим через т целое число jr zn- Заметим, что для любого двоичного набора о = ( 7i.. .Ok) из {0,1}к выполняется соотношение Для удобства величину n P } ( --- ) = J"ff"(n — 1)к № обозначим через т(д). Величину f/ч = № l(n — / НИ-1 обозначим через т (а). Если о ф (0,..., 0), (1,..., 1), то, очевидно, т (а) является целым числом.-Аналогично, если /(хі,...,хк) — булева функция, то положим m(f) = п Р {/ (I,..., )} и m {f) = . Очевидно, что Таким образом, если /(0,..., 0) = /(1,..., 1) = 0, то m (f) является целым числом. Кроме того, с учетом формулы для вычисления величины т (а), предыдущее равенство можно переписать в следующем виде: Формулу (2.17) можно также обобщить следующим образом. Пусть f (xi,... ,хк), /"fa,... ,хк) — булевы функции, и пусть Si = \Af(f") П ВкЩ\ - W(f ) п ВЇШ\ для t = 0,1,..., А. Тогда из равенства (2.17) непосредственно следует, что Построим последовательность ао, «і,... ,Cbk-2 чисел из множества {0,1,...,/ — 1} такую, что для любого г = 0,1,..., к — 2 выполняется Будем строить числа а из данной последовательности индукцией по г. Положим ао = 0. При этом, очевидно, выполняется соотношение (2.19) для г = 0. Предположим, что для некоторого г Є {0,1,..., -3} уже построены числа ао, а\,..., аг и тем самым для г = г справедливо соотношение (2.19). Следовательно, число га — Y j=oajV l{n 1)к 1 делится на V. Обозначим целое число (га — X f=o ajV l{n О --7-1) / 1Г через ЬГ. Так как (1,п — I) = 1 и тем самым (/, (п — l)k r 2) = 1, то согласно утверждению 8 в полной системе вычетов {0,1,...,/-1} по модулю I найдется такое число аг+\, что будет выполнено соотношение
Домноживобе части и модуль данного сравнения на V, получим соотношение, эквивалентное соотношению (2.19) для і = г + 1. Таким образом, мы можем найти все числа а\,..., afc_2 искомой последовательности. Заметим, что поскольку в силу неравенства (2.14) и утверждения 17 для любого і = 1,...,/:-2 выполняется а / к В [2], можно построить булеву функцию fo(xi,. ...-уХк) такую, что Поэтому, используя соотношение (2.19) для г = к — 2 с учетом равенства ао = 0, получаем, что га (/о) = га (mod lk 2). Используя соотношения (2.20), (2.13) и (2.15) и учитывая, что 1, можно оценить сверху Построение функции fi из данной последовательности будем проводить индукцией по і = 0,1,..., t. Для г = 0 искомая функция /о уже построена. Предположим, что построена функция /г_і, удовлетворяющая требуемым условиям. Если в каждом из слоев В [2],... ,В _2[2] число наборов, на которых /,-_! принимает значение 0, меньше, чем /, положим ft = /г_і, и тем самым завершим построение искомой последовательности. Предположим, что в некоторых из слоев {i?f[2],..., J3_2[2]} содержится не менее / наборов, на которых /j_i принимает значение 0. Среди этих слоев выберем слой, наборы которого имеют наименьший вес. Пусть таким слоем является слой ? [2], Будем последовательно строить fc-местные булевы функции /,-,...,/ 2, принимающие значение 1 только на наборах из слоев В±[2],..., В\[2] и удовлетворяющие для любого j = г;(г),..., к — 2 соотношениям m (fi) ЕЕ т! (mod/ ), (2.24) m (fj) mVrl) + V{ri-l)k-l-\ (2.25) где /t- = /t-i- Функцию /г- можно построить, выбрав во множе стве В1, [2] П N (fi-i) произвольное подмножество С, состоящее ровно из I наборов, и положив M{fl ) = Af(fi-i) U С. Тогда, используя равенство (2.18), получаем, что Тем самым функция /г- удовлетворяет неравенству (2.25) и в силу справедливости соотношения (2.22)для функции /,-_i соотношению (2.24). Пусть для некоторого j Є {г;(г + 1),..., к — 2} уже построены функции ./г --ч//-1 удовлетворяющие соотношениям (2.24) и (2.25). Обозначим через Ь целое число (га — га (// ))//-7-1. Так как в силу неравенства (2.14) и утверждения 17 имеем
Замыкания бесконечных множеств чисел
Мы также можем обобщить полученные результаты на случай замыканий произвольных бесконечных множеств чисел из PQ. Как и в предыдущих разделах, без ограничения общности мы рассматриваем множества несократимых дробей из интервала (0; 1). Пусть Н = S TT2"? г — бесконечное множество несократимых дробей из PQ+. Тогда обозначаем через Т(Н) множество Кроме того, положим 11(H) = USi Z(ni)- Пользуясь утверждением 4, аналогично утверждению 30 можно доказать Утверждение 31. Множество Т(Н) является конечным, разделимым и взаимно простым с каждым из чисел П\,П2, Таким образом, конечное разделимое множество Т(Н) является взаимно простым с любым числом из П(Я). Поэтому мы можем рассмотреть множество G[H(H);T(H) 2]. Следующая теорема является обобщением теоремы 11 на случай замыканий бесконечных подмножеств множества PQ. Теорема 13. Для любого бесконечного множества Я несократимых дробей из PQ+ выполняется соотношение Доказательство. Для любой дроби н. из Я множество Т(Н) 2, очевидно, разбивается на два подмножества ТІ, Т" чисел, являющихся делителями чисел ТПІ и щ — rrii соответственно. В силу взаимной простоты всех чисел множества Т(Н) числа ті ИЩ — ПІІ должны быть кратными числам \\Т-\\ и \\Т{ \\ соответственно. Поэтому Таким образом, Я С G[U(H);T(H) 2] и согласно лемме 4 множество С[П(Я);Т(Я) 2] замкнуто. Следовательно, (Я) С 3[П(Я);Т(Я) 2]. Докажем теперь, что 2[П(Я);Т(Я) 2] С (Я). Для этого рассмотрим произвольную дробь 21 из С?[П(Я);Т(Я) 2]. Обозначим через Яг-, і = 1,2,..., подмножество ї 1»---» 1} множества Я. Согласно лемме 1 существует такое j, что Т(Н) = T(Hj) = T{Hj+1) = ... и тем самым Т{Н) 2 = T{Hj) 2 = T(Hj+l) 2 = .... Поскольку Х(п) С П(Я), для любого р из Х{п) найдется jp такое, что р Є X(nJp). Положим j = max (j, тахрЄі(п) jp) и П = [Л=гХ(щ). Согласно теореме 11 имеем (Нґ) = G[n ]T(Hj.) 2] = С[П ;Т(Я) 2]. Так как Х{п) С П , дробь а содержится в G[U ;T(H) 2]. Поэтому є (Я,-.) С (Я). Таким образом, С[П;Т(Я) 2] = (Я . Пример 12. Теоремы 11 и 13 позволяют описать все замкнутые классы чисел из PQ. Заметим, что любой из этих классов является замыканием некоторого своего подмножества (например, самого этого класса). Поэтому из теорем 11 и 13 следует, что любой замкнутый класс чисел из PQ является элементом множества G. Таким образом, учитывая лемму 4, получаем, что справедлива Теорема 14. Множество G является множеством всех замкнутых подмножеств множества PQ. Среди замкнутых классов чисел наибольшее значение с практической точки зрения имеют классы, порождаемые конечными числовыми множествами.
Поэтому представляет большой интерес вопрос описания всех конечно порожденных замкнутых подмножеств множества PQ. Обозначим через Gfln подмножество множества G, состоящее из всех множеств С?[П;Т] таких, что П конечно. Из теоремы 11 следует, что все конечно порожденные замкнутые подмножества множества PQ являются элементами множества Gfin. Справедливо также обратное утверждение Доказательство. Пусть G[H;T] — произвольное множество из Gfin. В силу утверждения 27 без ограничения общности можно полагать, что Т = Т-2. Поскольку С?[П; Т] состоит из счетного множества рациональных чисел, можно представить С?[П;Т] в виде бесконечной последовательности несократимых дробей которую обозначим через Н. Очевидно, что U i (n ) = П. Поэтому согласно теореме 11 имеем Так как по лемме 4 множество G[Yl;T] замкнуто, то {Н) = G[U;T], тем самым С?[П;Т] = G[U;T(H) 2]. Из этого равенства в силу пункта 2 утверждения 29 вытекает Т = Т(Н) 2. Обозначим через НІ, і = 1, 2,..., множество -1-,..., . Согласно лемме 1 существует такое j, что Т{Н) = T(Hj) = T(Hj+l) = ... и, следовательно, Т = Т(Н) 2 = T(Hj) 2 = T(Hj+\) 2 = — Поскольку П = и і-Цпї) и П конечно, для некоторого достаточно большого s имеем П = Ui=i (n )- Положим к = max(j, 5). Заметим, что Т = T(Hk) 2 и Ui=i (nt) = П, поэтому согласно теореме 11 получаем (Нк) = С[П;Т]. Из леммы 19 непосредственно вытекает Теорема 15. Множество Gfin является множеством всех конечно порож- денных замкнутых подмножеств множества PQ. Используя теорему 11, мы можем также непосредственно предъявить конечные порождающие подмножества для множеств из Gfin, получив следующее обобщение следствия 13. Теорема 16. Любое множество С[П, Т], где П конечно, порождается подмножеством, содержащим не более \Т\ + 2 чисел. Доказательство. Если Т = 0, то данное утверждение вытекает из следствия 13. Поэтому можно полагать, что Т непусто, т. е. Т = {ti,... ,tq}, где q 1. Согласно утверждению 27 можно также полагать, что Т = Т 2. Покажем, что в этом случае множество G[U, Т] порождает- -ся подмножеством, содержащим q 4-1 число. В случае q 1 для каждого і = 1,..., q — 1 обозначим через 7 подмножество {ti,..., ,-} множества Т и рассмотрим произвольную несократимую дробь Щ из подмножества 7[П;7 : ЦТ \ Ті] множества G[U;T]. Индукцие/по і = 1,..., -1 докажем соотношение (2.93) Поскольку - Є G[U; ti : t2 ... tq], числа mi и щ — m\ кратны числам t\ и t2-.. .q соответственно. Поэтому из (т1? щ — гп\) вытекает, что (mi, t2 ... tq) = (тії — mi,ti) = 1. Следовательно, (Т, mi) = (tit2 ...q, ттц) = (ti, mi) = ti. Аналогичным образом имеем (Т, щ— mi) = {t\t2-.. .q, щ — m\) = (h tq, щ - mi) = t2 ... tq. Таким образом, ({T}, {mb щ — Ші} 1) = {t\,t2 ... tq}. Предположим теперь, что соотношение (2.93) справедливо для некоторого і Є {1,...,(/-2}. Тогда Поскольку 1 Є G[U;ti ... і+1 : іі+2 ... tq], числа ті и nL — mi кратны числам -...- +1 и і +2 tq соответственно. Поэтому из (mi+i, m+i - mi+i) вытекает, что (тг+ь ti+2 .. tq) = (ra,-+i - mi+1, -... U+l) = 1. Следовательно, ДЛЯ КаЖДОГО J = 1, . . . , І ИМЄЄМ (ij, mj+1) = - и (tj,ni+i - mi+i) = 1. Кроме того, имеем (ti+i -...q, mi+1) = (ti+1, mi+i) = U+l И (U+i . . . tg, Пі+і — тг-+і) = (U+2 tqi Щ+1 — ГПі+і) = U+2 . . . tq. Таким образом, .,..
Замыкания одноэлементных множеств векторов произвольной размерности
Лемма 26 может быть обобщена на случай замыканий множеств, со стоящих из одного произвольного вектора из SQ. Для этого рассмотрим произвольный позитивный вектор Т = {d\,...; dt) из SQ, где t 3. Без ограничения общности предполагаем, что компоненты вектора Т пред ставлены дробями, приведенными к наименьшему общему знаменателю п, т. е. di = -, где і = 1,..., t и (mi,... ,mt) = 1. Положим П(Х ) = Т(п). Для j = 1,...,t обозначим через Ц наибольший общий делитель всех чисел rri\,... ,mt кроме числа rrij. Через Т(Т ) обозначим в этом случае Утверждение 41. Для любого Т из SQ множество Т(Т ) является разделимым и взаимно простым с числом п. Доказательство. Справедливость утверждения в случае двумерного вектора Т показана в разделе 3.5. Предположим, что размерность вектора Т не меньше, чем 3. Пусть lj — произвольное число из Т(Т ). Тогда ЧИСЛО = (lj,n) ЯВЛЯеТСЯ Делителем ЧИСЛа П И Всех ЧИСеЛ ГПі, где І ф j. Следовательно, является делителем числа rrij — п — X i j m - Таким образом, является общим делителем всех чисел mi,..., mt. Поэтому из (mi,..., mt) = 1 следует, что {lj, ті) = 1. Кроме того, заметим, что для любых двух различных чисел If, lj» из Т(Х ) имеем (lj , lj») = (mi,..., mt) = 1. Положим I = \\T(T )\\. В силу утверждения 41 можно рассмотреть множество SG[U(T ); Т{Т )]. Докажем, что это множество содержится в ({Х }). Рассмотрим отдельно два различных случая в зависимости от количества максимальных элементов среди чисел mi, 77,..., mt. Лемма 27. Пусть среди чисел mi, mi,... ,mt имеется единственный мак Доказательство. В силу утверждения 33 без ограничения общности А л л. можно полагать, что mi /7 тз ... т . Пусть Т = (di,...; dh) — произвольный позитивный вектор из SG[U(V);T(V)]. Положим Д = min(di,... ,dh). Пусть п — общий знаменатель компонент вектора І) такой, что Х{п) С П( ). Так как И(Т ) = Х{п), то h является делителем некоторой достаточно большой степени nk числа п.
Обозначим через к достаточно большое натуральное число, не меньшее ко и удовлетворяющее неравенствам 1,...,/. Положим /i0 = 0 и /ij = ]С}=1 i Для г = 1»«-ч — 1- Так как ї є 56 [Ц(Х ),-Т(ї )], то существуют подмножества Ті Э Т2 Э ... D Тд_х множества Т(Т ) такие, что для любого і = 1,..., h — 1 справедливы соотношения щ = 0 (mod Т;-), /ц = пк (mod Г(2?)\ 7їЦ). (3.121) Положив Т0 = T(V), получим, что соотношения (3.121) справедливы так же для г = 0. Кроме того, имеем ; Для любого множества U наборов из Ек обозначим пкРи(Т ,..., Т ) че рез M{U). Из утверждения 38 следует, что M([jsi=1 Ui) — 5ZJ=1 M{Ui) для любых непересекающихся множеств Ui,..., Us С Ек. Для любого неоднородного набора о Є Ек из формулы (3.1) можно получить, что где В — слой множества Ек, содержащий д. В случае однородного набора а = (г;...; г) из Ек согласно формуле (3.1) получаем Таким образом, величина Л4(11) может быть вычислена по следующей формуле: Отметим, что если множество U состоит только из однородных наборов, то где \в — \V П В\ — \U П В\. Кроме того, при доказательстве леммы мы будем пользоваться очевидным равенством ,=2 тз п mi Слой В множества Е% будем называть слоем г-го уровня, где і = 0,1,..., к — 1, если В состоит из наборов, содержащих ровно і символов 0. Для j = 2, 3,..., t обозначим через В3к_1 слой (к — 1)-го уровня из наборов, содержащих к — 1 символов 0 и один символ j — 1. Для г = 0,..., к — 2 и j, s — 2,3,..., t, где j ф s, обозначим через B\,s слой г -го уровня из наборов, содержащих помимо символов 0 ровно один символ 5 — 1 и к — і — 1 символов j — 1 (и соответственно не содержащих никаких других символов). В случае і = 1, ...,& — 2 и j = s = 2,3,..., t через B? s будем обозначать слой г-го уровня из наборов, содержащих г символов 0 и к — г символов j — 1. Все обозначенные нами слои будем называть специальными слоями. Согласно утверждению 18 и неравенству (3.118) в каждом слое множества Ejf содержится не менее (h — l)mim2 наборов.
Поэтому в каждом из слоев Bl__lf... ,Вк\}1 можно выделить по {h — \)tmim2 различных наборов, приписав каждому из этих наборов некоторый целочисленный ранг от 1 до h — 1 так, чтобы в любом из этих слоев содержалось ровно по tmi7Ti2 различных наборов каждого ранга. Аналогичным образом можно приписать ранги от 1 до h — 1 наборам всех остальных специальных слоев от нулевого до (к — 2)-го уровня так, чтобы в каждом из этих слоев содержалось ровно по ті различных наборов каждого ранга. Всем остальным неоднородным наборам множества Е\ припишем ранг 0. Согласно формуле (3.123) для любого набора а из слоя г-го уровня, где г = 0,1,... ,к — 1, величина -М({а}) делится на т\, т. е. Л4 ({&})/т\ является целым числом. Исходя из этого наблюдения, мы разбиваем все неоднородные наборы множества Е% на категории 0,1,..., ті — 1 следующим образом: неоднородный набор а из слоя г-го уровня принадлежит категории j, если M-({&})/m\ = j (mod mi). Рассмотрим произвольный однородный набор (г; г;...; г) из Ек. Если li+i 1, то Іі+і Є T(V) = Т0, т. е. среди множеств 7o,7i,... ,ТЛ_і по крайней мере множество Т0 содержит /,+1 1. Поэтому среди этих множеств найдется множество с максимальным порядковым индексом, содержащее число /j+і. Обозначим этот порядковый индекс через хі})- В случае /г+і = 1 положим х(0 = 0. Разобьем множество Ск на непересекающиеся подмножества UQ , t/f,..., U _x, где Uj состоит из всех однородных наборов (г; г;...; г) таких, что х(г) = І- Покажем, что для любого j = 0,1,..., h — 2 и любого /j из (ї ) выполняется соотношение
Похожие диссертации на Дискретные преобразования конечных распределений рациональных вероятностей
