|
Здравствуйте! У меня следующий вопрос. Дано множество $%V=\{0,\ldots\,n-1\}$% мощности $%n$%, $%n$% делится на $%3$%. Необходимо найти функцию $%f$%, которая каждому множеству размера $%n/3$% ставит в соответствие неторое целое неотрицательное число так, что по сумме значений функций от трех множеств, мы могли бы понять пересекаются ли эти множества. Более формально: $$\forall S_1,S_2,S_3, T_1, T_2,T_3\in V, |S_i|=|T_i|=\frac{n}{3},$$ если $$S_1\cup S_2\cup S_3=V, T_1\cup T_2\cup T_3\neq V,$$ то $$f(S_1)+f(S_2)+f(S_3)\neq f(T_1)+f(T_2)+f(T_3).$$ Примером такой функции может служить функция $$h(U)=\sum_{i\in U}2^i.$$ Тогда три множества $%S_1, S_2, S_3$% размера $%n/3$% не пересекаются тогда и только тогда, когда $$h(S_1)+h(S_2)+h(S_3)=2^n-1.$$ Легко видеть, что $%h$% на некоторых множествах достигает значений близких к $%2^n.$% Вопрос заключается в следующем, можно ли найти такую функцию $%f$%, что ее значение на любом множестве размера $%n/3$% будет меньше $%1.99^n\cdot poly(n).$% Я знаю несколько отрицательных результатов по этой теме:
Буду благодарен за любые идеи о виде такой функции или за интуицию о том, почему такой функции не может существовать. Спасибо! UPD: Я забыл сказать, что функция $%f$% может быть вероятностной, но она должна хотя бы с экспоненциально маленькой вероятностью по случайным битам выдавать корректное кодирование (кодирование, удовлетворяющее описанным выше свойствам). задан 25 Май '13 16:21 
AlexGolovnev |
|
Например:
Пусть $%n=6, V=\lbrace 0, 1,…, 5 \rbrace; $% для i= 0,1,…,5 соответственно $% a_i= 0, 1, 3, 7, 15, 31; h(U)= \sum_{i \in U} a_i . $% Тогда при $% |S|=2: h(S_1)+ h(S_2)+ h(S_3)=57 <=>S_1 \cup S_2 \cup S_3 =V. $% Примечания: 56 отвечен 26 Май '13 2:38 
Urt Большое спасибо за ответ! Но я все же думаю, что здесь есть недочет. $$S_1=\{a_0,a_4\}, S_2=\{a_0,a_4\}, S_3=\{a_0,a_5\}.$$ Тогда $$h(S_1)+h(S_2)+h(S_3)=49,$$ но множества пересекаются. Под асимптотически меньше $$1.99^n\cdot poly(n)$$ я имел в виду, что мы можем построить такие функции для бесконечного числа различных n. Но, возможно, решение получится как раз из удачного примера для малого значения n.
(26 Май '13 3:37)
AlexGolovnev
Задача понятна. Я хотел для начала найти простой пример, дающий улучшенную оценку. Это пересечение почему-то выпало из рассмотрения. Посмотрю, можно ли что-нибудь поправить или фатально.
(26 Май '13 8:27)
Urt
@AlexGolovnev, можете привести какой-нибудь пример (известны ли примеры) искомой функции с проверочной суммой меньше 2^n-n-1 ?
(27 Май '13 21:47)
Urt
Нет, я не знаю примеров с проверочной суммой меньше $%2^n-n-1$%. Еще я просто хочу обратить Ваше внимание на то, что можно иметь много проверочных сумм. Я не очень подробно рассматривал этот случай, так как для случая "линейного кодирования" можно показать нижнюю оценку $%2^n/poly(n)$%.
(28 Май '13 12:04)
AlexGolovnev
То есть, если $$f(S)=\sum_{i\in S}W(i),$$ то $%f$% достигает значений $%\Omega(2^n/poly(n))$% на некоторых множествах размера $%n/3$%. Действительно, если значения $%f$% совпадают на двух множествах $%S_1, S_2$% размера $%n/2$%, то $%f$% не удовлетворяет свойству кодирования:$$f(S_2\cup \bar{S_2})=f(S_1\cup \bar{S_2}),$$ но $%S_2\cup\bar{S_2}=V$%, a $%S_1\cup\bar{S_2}\neq V$%. Следовательно, количество различных значений $%f$% на множествах размера $%n/2$% не меньше количества различных множеств размера $%n/2={n \choose n/2}=\Omega(2^n/poly(n))$%.
(28 Май '13 12:05)
AlexGolovnev
@AlexGolovnev, понятно, что применительно к неизвестным $% h(S_i) $% задача состоит в подборе такой совокупности их значений, что множество сумм $% h(S_i), $% заданных на пересекающихся множествах $% S_i , $% и множество сумм, заданных на непересекающихся множествах $% S_i , $% не пересекаются. Задача интересная, но в силу занятости осмысливаю лишь в фоновом режиме. Оценка $% h_max > 3(1.88988)^n/4 sqr(n), $% наверное, общеизвестна (если я не ошибся).
(28 Май '13 15:46)
Urt
Да, оценка снизу получается сразу, а в общем виде задача весьма интересно звучит. Я, правда, не знаю, занимался ли ей кто-нибудь. Может, на дружественном сайте mathoverflow имеет смысл спросить?
(28 Май '13 17:06)
falcao
@Urt, да, нижние оценки вида $%{n \choose n/3}/poly(n)$% получаются подобными рассуждениями. @falcao, год назад я спрашивал очень похожий вопрос на cstheory: http://cstheory.stackexchange.com/questions/12103/subset-numbering Не уверен, что его стоит повторять на mathoverflow теперь.
(30 Май '13 6:57)
AlexGolovnev
@AlexGolovnev: возможно, Вы правы. Тут расчёт мог быть на то, что вдруг кто-нибудь этот же вопрос уже исследовал, и тогда могли предложить какие-нибудь ссылки.
(30 Май '13 9:08)
falcao
@AlexGolovnev, Ваше доказательство (в комментарии) асимптотической оценки числа различных значений f, на мой взгляд, требует небольшого уточнения в отношении возможности использования критерия для множеств с $%|S_i|=n/2 $%, поскольку в задаче заведомо известно, что $% |S_i|=n/3 $%.
(30 Май '13 23:54)
Urt
показано 5 из 10
показать еще 5
|
|
@Urt: Пусть $%w(i) -$% вес элемента $%i$%. Если $%f(S)=\sum_{i\in S}{w(i)}-$% кодирование множеств размера $%n/3$%, удовлетворяющее условию, то $%f$% достигает значений $%\Omega(2^n/poly(n))$%. Рассмотрим суммы вида $%\sum_{i\in U}{w(i)}$% на множествах $%U$% размера $%n/2$%. Если бы значения таких сумм совпали на каких-то двух множествах $%U_1$% и $%U_2$% размера $%n/2$%, то нарушилось бы свойство кодирования. Действительно, рассмотрим три произвольных непересекающихся множества $%S_1,S_2,S_3$% размера $%n/3$%, рассмотрим три множества $%T_1, T_2, T_3$% размера $%n/3$%, что $%T_1\cup T_2\cup T_3=U_1\cup\bar U_2$% как мультимножества (с учетом кратности элементов). Теперь $$f(S_1)+f(S_2)+f(S_3)=\sum_{i\in V}w(i)=\sum_{i\in U_2}{w(i)}+\sum_{i\in\bar U_2}{w(i)}=\sum_{i\in U_1}{w(i)}+\sum_{i\in\bar U_2}{w(i)}=f(T_1)+f(T_2)+f(T_3),$$ но $$S_1\cup S_2\cup S_3=V, T_1\cup T_2\cup T_3\neq V.$$ Следовательно, суммы $%\sum_{i\in U}{w(i)}$% различны на множествах размера $%n/2$%. Значит, эти суммы достигают значений $%\Omega(2^n/poly(n))$%. Тогда $%w(i)$% достигает значений $%\Omega(2^n/poly(n))$%. Следовательно, $%f(S)$% на множествах размера $%n/3$% достигает значений $%\Omega(2^n/poly(n))$%. отвечен 3 Июн '13 15:46
AlexGolovnev @AlexGolovnev, детализация доказательства этого утверждения очень важна для решения общей задачи: 1) если бы оно проходило в таком виде, то его нетрудно было бы обобщить на произвольные функции (поэтому смотрим, в каком виде оно проходит); 2) если его корректно провести, то оно приведет к более сильному и интересному утверждению. По сути доказательства: последнее равенство в формуле с суммами необоснованно и, вообще говоря, не верно.
(3 Июн '13 19:14)
Urt
@Urt: почему последнее равенство неверно? В множествах $%T_1, T_2, T_3$% встречаются элементы из $%U_1$% и $%\bar{U_2}$%.
(3 Июн '13 19:28)
AlexGolovnev
@AlexGolovnev, множество $% S= S_1 \cup U_2’ $% в виде объединения $% S=T_1 \cup T_2 \cup T_3 $% может представляться по-разному с разными значениями сумм $% Sum= f(T_1)+ f(T_2)+ f(T_3). $% Так, для $% S = \lbrace 0,2,3,4,5 \rbrace S = \lbrace 0,2 \rbrace \cup \lbrace 2,3 \rbrace \cup \lbrace 4,5 \rbrace =\lbrace 0,3 \rbrace \cup \lbrace 2,3 \rbrace \cup \lbrace 4,5 \rbrace =… , $% причем $% Sum \ne f(S) $% (пример из ответа) . Для $% S = T_1 \cup T_2 $% представление тройками имеет вид $% S = T_1 \cup T_1 \cup T_2 = T_1 \cup T_2 \cup T_2. $%
(3 Июн '13 20:24)
Urt
@Urt: мы выбираем $%T_1,T_2,T_3$% так, что $$T_1\cup T_2\cup T_3 \text{ и } U_1\cup \bar{U_2}$$ равны как мультимножества (с учетом кратности элементов). Другими словами, кладем в $%T_1$% первые $%n/3$% элементов из $%U_1$%, кладем в $%T_2$% первые $%n/3$% элементов из $%\bar{U_2}$%, кладем в $%T_3$% последние $%n/6$% элементов из $%U_1$% и последние $%n/6$% элементов из $%\bar{U_2}$%.
(4 Июн '13 2:11)
AlexGolovnev
@AlexGolovnev,@Urt: я вчера прочитал рассуждение, и когда понял возможный способ раскладки мультимножества по трём частям, то мне оно показалось верным. По-моему, тут никакой ошибки нет.
(4 Июн '13 8:53)
falcao
@Falcao, @AlexGolovnev, В правильности утверждения и возможности его доказательства сомнений не было. Приведенные рассуждения при их уточнении, по-видимому, ведут к доказательству. Но, чтобы не упустить детали (случаи-то бывают разные) и посмотреть особенности доказательства для нелинейных функций, хотелось бы увидеть описание нужных n/3-троек для двух рассматриваемых n/2-множеств на нормальном математическом языке.
(4 Июн '13 18:44)
Urt
@Urt, Нам нужно показать, что два множества $%U_1, \bar{U_2}$% размера $%3k$% можно покрыть с учетом кратности тремя множествами $%T_1,T_2,T_3$% размера $%2k$%. Положим $%T_1$% равным первым $%2k$% элементам множества $%U_1$%. Положим в $%T_2$% оставшиеся $%k$% элементов множества $%U_1$%. Теперь среди $%3k$% различных элементов множества $%\bar{U_2}$% можно выбрать $%k$% элементов, которые не встречаются среди $%k$% элементов $%T_2$%, добавим их в $%T_2$%. Оставшиеся $%2k$% элементов $%\bar{U_2}$% положим в $%T_3$%. Скажите, пожалуйста, к какому более сильному утверждению это ведет?
(4 Июн '13 19:01)
AlexGolovnev
@Urt: способ раскладки вообще-то заслуживает описания. Но я смог быстро проверить, что он всегда возможен. @AlexGolovnev: тот способ, который Вы сейчас привели, может не пройти, так как в $%T_3$% могут оказаться повторения. Там принцип немного другой должен быть. Грубо говоря, если $%a,b,c$% есть и в $%U_1$%, и в $%\bar{U_2}$%, то их надо разнести по трём множествам как $%b,c\in T_1$%, $%a,c\in T_2$%, $%a,b\in T_3$%. Так поступаем со всеми тройками шаг за шагом, и с оставшейся неполной тройкой по тому же принципу (if any). Понятно, что переполнение не произойдёт даже при $%U_1=\bar{U_2}$%.
(4 Июн '13 19:34)
falcao
@falcao, $%U_1$% и $%\bar{U_2} - $% множества без повторений, поэтому множества $%T_1,T_2,T_3$% также не будут содержать повторных элементов. В частности, $%T_3$% не содержит повторений, т.к. $%T_3\subset\bar{U_2}$%.
(4 Июн '13 19:39)
AlexGolovnev
@AlexGolovnev: со вторым способом раскладки, описание которого я только что увидел, я согласен. Но первоначальное описание не подходило, там могли оказаться общие элементы среди последних $%n/6$% из $%U_1$% и последних $%n/6$% из $%\bar{U_2}$%. P.S. Это только у меня исказился шрифт на форуме (он стал очень мелким), или у других тоже?
(4 Июн '13 19:51)
falcao
@Falcao, @AlexGolovnev, спасибо за интересное обсуждение (меня тоже смущали варианты пересечений $% U_1, U_2 $%). По существу "усиления": я просматривал подходы к доказательству утв. "значения f на множествах одинаковой мощности различны" (линейный случай, интересна интерпретация в терминах чисел). Но напрямую обобщение приведенного доказательства не проходит. Есть другие мысли - при случае постараюсь изложить.
(4 Июн '13 20:39)
Urt
показано 5 из 11
показать еще 6
|
@Urt, я думаю, что доказательство в комментарии правильное, но вот уточнение. Мы рассматриваем функцию вида $%\sum_{i\in S} W(i)$%, заданную на множествах $%S$% размера $%n/3$%. Обобщим эту функцию на множества любого размера, покажем, что тогда она принимает значения $%\Omega(2^n/poly(n))$%. Значит, существуют множества размера $%n/3$%, на которых функция принимает значения $%\Omega(2^n/poly(n))$%.
@AlexGolovnev, действие линейной функции f действительно можно распространить на любые множества $% S_i \subseteq V $% , но критерий пересечения множеств в виде $% S_i \bigcup S_j \bigcup S_k =V <=> f(S_i)+ f(S_j)+ f(S_k)=f(V) $% по условию задачи действует для трех n/3-элементных множеств. В общем случае он не применим даже для трех различных множеств $% S_i, S_j ,S_k $% (см. мой пример в ответе). Вы его в доказательстве используете для n/2-элементных множеств. Корректность этого должна быть доказана.
@Urt Да, мы сначала распространяем линейную функцию на произвольные подмножества. Потом мы говорим, что если бы функция имела одинаковые значения на каких-то множествах размера $%n/2$%, то существовали бы множества размера $%n/3$%, нарушающие свойства кодирования (разобьем множества $%S_2\cup\bar{S_2}$% и $%S_1\cup\bar{S_2}$% на тройки непересекающихся множеств).
@AlexGolovnev, просьба привести доказательство вашего утверждения (после слов «Потом мы говорим…») , например, в отдельном ответе. Дело в том, что в ваших рассуждениях не используется мощность множеств $% S_1, S_2, $% а для произвольных множеств $% S_1, S_2 $% это утверждение не верно.