Здравствуйте!

У меня следующий вопрос. Дано множество $%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).$% Я знаю несколько отрицательных результатов по этой теме:

  1. Если мы рассматриваем подмножества размера $%n/2k$% ($%k$% - целое), а не подмножества размера $%n/3$%, то функция $%f$% обязана принимать значения $%\Omega(2^n/poly(n))$% хотя бы на некоторых множествах размера $%n/3$%.

  2. Если мы рассматриваем $%f$% как линейную функцию от $%n$% значений, соответствующих элементам $%V$%, то, опять же, $%f$% на некоторых множествах будет достигать $%\Omega(2^n/poly(n)).$%

Буду благодарен за любые идеи о виде такой функции или за интуицию о том, почему такой функции не может существовать. Спасибо!

UPD: Я забыл сказать, что функция $%f$% может быть вероятностной, но она должна хотя бы с экспоненциально маленькой вероятностью по случайным битам выдавать корректное кодирование (кодирование, удовлетворяющее описанным выше свойствам).

задан 25 Май '13 16:21

изменен 28 Май '13 12:17

@Urt, я думаю, что доказательство в комментарии правильное, но вот уточнение. Мы рассматриваем функцию вида $%\sum_{i\in S} W(i)$%, заданную на множествах $%S$% размера $%n/3$%. Обобщим эту функцию на множества любого размера, покажем, что тогда она принимает значения $%\Omega(2^n/poly(n))$%. Значит, существуют множества размера $%n/3$%, на которых функция принимает значения $%\Omega(2^n/poly(n))$%.

(1 Июн '13 11:37) AlexGolovnev

@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-элементных множеств. Корректность этого должна быть доказана.

(1 Июн '13 14:02) Urt

@Urt Да, мы сначала распространяем линейную функцию на произвольные подмножества. Потом мы говорим, что если бы функция имела одинаковые значения на каких-то множествах размера $%n/2$%, то существовали бы множества размера $%n/3$%, нарушающие свойства кодирования (разобьем множества $%S_2\cup\bar{S_2}$% и $%S_1\cup\bar{S_2}$% на тройки непересекающихся множеств).

(1 Июн '13 14:07) AlexGolovnev

@AlexGolovnev, просьба привести доказательство вашего утверждения (после слов «Потом мы говорим…») , например, в отдельном ответе. Дело в том, что в ваших рассуждениях не используется мощность множеств $% S_1, S_2, $% а для произвольных множеств $% S_1, S_2 $% это утверждение не верно.

(1 Июн '13 15:35) Urt
10|600 символов нужно символов осталось
2

Например: Пусть $%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. $%

Примечания:
1. Исправлена ошибка, обнаруженная @AlexGolovnev'ым (см. комментарий).
2. Пример показывает возможность построения кода с проверочной суммой $% Sum=2^n-n-1 $%. Однако это не улучшает приведенную в задаче асимптотическую оценку.

56

ссылка

отвечен 26 Май '13 2:38

изменен 26 Май '13 13:48

Большое спасибо за ответ! Но я все же думаю, что здесь есть недочет. $$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
10|600 символов нужно символов осталось
0

@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, детализация доказательства этого утверждения очень важна для решения общей задачи: 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
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×845

задан
25 Май '13 16:21

показан
1098 раз

обновлен
4 Июн '13 20:39

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru