Основное свойство векторных пространств состоит в том, что векторное пространство размерности может характеризоваться линейно независимыми линейными ограничениями, то есть существуют линейно независимых векторов , ортогональных .
С точки зрения Фурье это эквивалентно тому, что индикаторная функция из имеет линейно независимых ненулевых коэффициентов Фурье. Обратите внимание, что имеет в общей сложности ненулевых коэффициентов Фурье, но только из них линейно независимы.
Я ищу примерную версию этого свойства векторных пространств. В частности, я ищу заявление в следующей форме:
Пусть имеет размер . Тогда индикаторная функция имеет не более линейно независимых коэффициентов Фурье, абсолютное значение которых равно не менее .
Этот вопрос можно рассматривать с точки зрения «структура против случайности». Интуитивно понятно, что такое утверждение говорит о том, что каждый большой набор может быть разложен на сумму векторного пространства и небольшого смещенного набора. Хорошо известно, что каждая функция может быть разложена на «линейную часть», в которой большой Фурье коэффициенты и «псевдослучайная часть», которая имеет небольшое смещение. Мой вопрос состоит в том, имеет ли линейная часть только логарифмическое число линейно независимых коэффициентов Фурье.
Ответы:
Не является ли следующий контрпример?
Пусть будет большинством из x 1 , … , x 1 / ϵ 2 , что является индикатором множества размером 2 n / 2 , поэтому d = 1 . Тем не менее, F ( { я } ) = Θ ( ε ) для 1 ≤ я ≤ 1 / ε 2 , так что у вас есть 1 / ε 2f(x) x1,…,x1/ϵ2 2n/2 d=1 f^({i})=Θ(ϵ) 1≤i≤1/ϵ2 1/ϵ2 линейно независимые большие коэффициенты Фурье.
источник
Возможно, вы хотите то, что иногда называют "леммой Чанга" или "леммой Талагранда" ... называемой "неравенством 1-го уровня" здесь: http://analysisofbooleanfunctions.org/?p=885
Это означает, что если имеет среднее значение 2 - d, то число линейно независимых коэффициентов Фурье, квадрат которых не меньше γ 2 - d , не больше O ( d / γ 2 ) . (Это потому, что F 2 -линейное преобразование на входе не меняет среднего значения, поэтому вы всегда можете переместить линейно независимые символы Фурье в степень-1.)1S 2−d γ2−d O(d/γ2) F2
источник