Линейно независимые коэффициенты Фурье

19

Основное свойство векторных пространств состоит в том, что векторное пространство размерности может характеризоваться линейно независимыми линейными ограничениями, то есть существуют линейно независимых векторов , ортогональных .ВF2NN-dddвес1,...,весdF2NВ

С точки зрения Фурье это эквивалентно тому, что индикаторная функция из имеет линейно независимых ненулевых коэффициентов Фурье. Обратите внимание, что имеет в общей сложности ненулевых коэффициентов Фурье, но только из них линейно независимы.1ВВd 1В2dd

Я ищу примерную версию этого свойства векторных пространств. В частности, я ищу заявление в следующей форме:

Пусть имеет размер . Тогда индикаторная функция имеет не более линейно независимых коэффициентов Фурье, абсолютное значение которых равно не менее .SF2N2N-d1Sdжурнал(1/ε) ε

Этот вопрос можно рассматривать с точки зрения «структура против случайности». Интуитивно понятно, что такое утверждение говорит о том, что каждый большой набор может быть разложен на сумму векторного пространства и небольшого смещенного набора. Хорошо известно, что каждая функция может быть разложена на «линейную часть», в которой большой Фурье коэффициенты и «псевдослучайная часть», которая имеет небольшое смещение. Мой вопрос состоит в том, имеет ли линейная часть только логарифмическое число линейно независимых коэффициентов Фурье.е:F2NF2поLY(1/ε)

Или Меир
источник
3
Привет Или, не могли бы вы дать ссылку на свое последнее утверждение, что каждая функция может быть разложена на линейную часть + псевдослучайную часть? Благодарность!
Генри Юн
2
Я не уверен, где это впервые появилось. Это прямое следствие неравенства Парсеваля: из Парсеваля вы получите, что каждая булева функция имеет не более символа, чьи коэффициенты Фурье имеют абсолютное значение, по крайней мере, . Теперь возьмем «линейную» часть как сумму последних символов (с теми же коэффициентами), а «псевдослучайную часть» за сумму всех других символов (с теми же коэффициентами). 1/ε2ε
Или Меир

Ответы:

12

Не является ли следующий контрпример?

Пусть будет большинством из x 1 , , x 1 / ϵ 2 , что является индикатором множества размером 2 n / 2 , поэтому d = 1 . Тем не менее, F ( { я } ) = Θ ( ε ) для 1 я 1 / ε 2 , так что у вас есть 1 / ε 2f(x)x1,,x1/ϵ22n/2d=1f^({i})=Θ(ϵ)1i1/ϵ21/ϵ2 линейно независимые большие коэффициенты Фурье.

За австрина
источник
9

Возможно, вы хотите то, что иногда называют "леммой Чанга" или "леммой Талагранда" ... называемой "неравенством 1-го уровня" здесь: http://analysisofbooleanfunctions.org/?p=885

Это означает, что если имеет среднее значение 2 - d, то число линейно независимых коэффициентов Фурье, квадрат которых не меньше γ 2 - d , не больше O ( d / γ 2 ) . (Это потому, что F 2 -линейное преобразование на входе не меняет среднего значения, поэтому вы всегда можете переместить линейно независимые символы Фурье в степень-1.)1S2dγ2dO(d/γ2)F2

Райан О'Доннелл
источник
Большое спасибо! Это определенно близко к тому, что я искал, но для приложения, которое я имел в виду, было крайне важно иметь логарифмическую зависимость от (что в ваших обозначениях также подразумевало бы логарифмическую зависимость от γ ). Увы, пример Пера показывает, что это невозможно. ϵγ
Или Меир