Явная сбалансированная матрица

Можно ли построить явное 0 / 1 -матрица с N 1,5 из них таким образом, что каждый N 0,499 × N 0,499 подматрица содержит менее N 0,501 из них?$N \times N$ $0/1$$N^{1.5}$$N^{0.499} \times N^{0.499}$$N^{0.501}$

Или, возможно, для такого свойства можно построить явный ударный набор.

Легко видеть, что случайная матрица обладает этим свойством с вероятностью, экспоненциально близкой к . Кроме того, лемма о расширении смешивания недостаточна для получения этого свойства.$1$

Я предполагаю, что псевдослучайные генераторы, которые дурачат комбинаторные прямоугольники, могли бы здесь помочь, но они предназначены для равномерного распределения, и мне здесь нужен .$B(N^2, N^{-0.5})$

То, что вы ищете, это однобитный экстрактор для двух независимых источников: функция , такая, что при условии, что X, Y являются случайными переменными с минимальной энтропией 0,499 * log (N), E (X, Y) почти сбалансирован.$E:[N]\times [N]\to \{0,1\}$

Это печально сложная проблема. Для параметров, которые вы хотите, я думаю, что это было решено Bourgain. Смотрите здесь: http://www.cs.washington.edu/homes/anuprao/pubs/bourgain.pdf

Этот ответ основан на идее Даны в ее ответе выше.

Я думаю, что вы можете построить такую ​​матрицу, используя конденсаторы с двумя источниками с потерями. Зафиксируйте и скажите N = 2 n . Предположим, что имеется явная функция F ( х , у ) , который принимает любые два независимых случайных источников ( X , Y ) , каждый из которых длины п и имеющих мин-энтропии по крайней мере , к = п ( 1 / 2 - δ ) и выводит последовательность из n ′ = n /$\delta = 0.001$$N=2^n$$f(x,y)$$(X, Y)$$n$$k = n(1/2 - \delta)$$n' = n/2$Биты , что является -близко к распределению с мин-энтропии по крайней мере , к ' = п ( 1 / 2 - 3 δ ) . Я думаю, что вы можете использовать стандартные вероятностные аргументы, чтобы показать, что случайная функция удовлетворяет этим свойствам (с подавляющей вероятностью), если 2 k > k ′ + log ( 1 / ϵ ) + O ( 1 ) . По вероятностному аргументу должно быть похоже на то, что используется в следующей статье для конденсаторов без потерь и более общих проводников:$\epsilon$$k'=n(1/2-3\delta)$$2k > k'+\log(1/\epsilon)+O(1)$

М. Капальбо, О. Рейнгольд, С. Вадхан, А. Вигдерсон. Проводники случайности и расширение в постоянных степенях за пределы степени 2

В нашем случае мы полагаем , поэтому мы уверены в существовании нужной нам функции. Теперь аргумент усреднения показывает, что существует n ′ -битная строка z такая, что число ( x , y ) с f ( x , y ) = z составляет не менее 2 1,5 n . Предположим, вы знаете такой z и исправляете его (вы можете выбрать любой произвольный $\epsilon = 2^{-k'}$$n'$$z$$(x,y)$$f(x,y)=z$$2^{1.5 n}$$z$$z$если вы дополнительно знаете, что ваша функция отображает полностью равномерное распределение на распределение, которое является близко к равномерному). Теперь определите элементы вашей матрицы N × N по возможностям ( x , y ) и поместите 1 в положение ( x , y ), если f ( x , y ) = z . По нашему выбору z , эта матрица имеет не менее 2 1,5 $O(2^{-n/2})$$N \times N$$(x,y)$$1$$(x,y)$$f(x,y)=z$$z$$2^{1.5n}$ из них.

Теперь возьмем любую подматрицу и пусть X , Y будут равномерными распределениями по выбранным строкам и столбцам соответственно. По выбору f мы знаем, что f ( X , Y ) является ϵ- близким к наличию минимальной энтропии k ′ . Поэтому, если мы выберем равномерно случайную запись подматрицы, вероятность наличия 1 будет не более 2 - k ′ + ϵ ≤ 2 - k ′ + $2^k \times 2^k$$X, Y$$f$$f(X,Y)$$\epsilon$$k'$$1$$2^{-k'}+\epsilon\leq 2^{-k'+1}$, Это означает, что у вас есть не более единиц в подматрице, по желанию.$2^{2k-k'+1} = O(2^{n/2 + \delta})$

Конечно, создание явного с желаемыми параметрами (в частности, почти оптимальной выходной длиной) является очень сложной задачей, и такой функции пока не известно.$f$