Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Here is a (little wild) question about Boolean functions with countably many variables and a wild analog for Fourier-Walsh functions and analysis based on them.

Let $x_1,x_2,\dots,x_n,\dots$ be Boolean variables. We will consider real functions on these countably many variables. Consider the following three classes of functions.

1) (Ultrafilter-Rademacher.) Let $X$ be the set of natural numbers. Let $F$ be an ultrafilter on $X$.

Thus if $A \in F$ and $A \subset B$ then also $B \in F$; If $A,B \in F$ so is their intersection; and every set $Y \subset X$, $Y$ or its complement are in $F$.

Define $W_F (S)=1$ if $S \notin F$ and $W_F(S)=-1$ if $S \in F$.

2) (Ultrafilter-Walsh) Let $G$ be a finite family of ultrafilters. define $W_G$ as the product of all $W_F$ for $F \in G$.

questions:

a) Are all the $W_G$ (or just the $W_F$) linearly independent as real functions on $X$? (Regard 1 as the empty product; if not what are the dependencies?)

b) Is this set of function form (in some sense) an interesting basis for (some) space of Boolean functions on $X$?

One step further

We can go one step further

Let $Z$ be an infinite set and consider Boolean variables $x_z$ (attaining the values $\pm 1$,) one for each element $z \in Z$.

A generalized parity function is a Boolean function on these variables with the property that $f$ is one for the all one vector and $f(y)=-f(x)$ if $y$ differs from $ x$ in one coordinate. Let $Z$ be a set of ultrafilters and let $P$ be a generalized parity function on variables indexed by $Z$. (On a finite set a generalized parity function is simply the parity function.)

The generalized parity product (GP-product) $g$ of the ultrafilters in $Z$ is defined as follows: Let $S$ be a subset of $N$. For $z \in Z$ let $x_z=-1$ if $S \in z$ and $x_z=1$, otherwise. Let

$$g(S)=P(x_z: z \in Z).$$

We can consider a third class of functions

3) (Ultrafilter-ultrawalsh) Let $C$ be the class of all $GP$-products of ultrafilters. This is much more general than functions of the form $W_G$ (for them $Z$ is finite and we have a usual parity function)

Question: What is the space spanned by ultrafilter ultrawalsh functions and what are the linear dependencies among them.

The general question:

The general question is: Can insights (questions, results etc.) regarding Boolean functions on finitely many variables (from combinatorics or complexity theory) be extended to Boolean functions on infinite sets of variables with "dictatorships" being replaced by "ultrafilters."

Another question is if these classes of functions can further be extended to describe a basis/spanning set (just for finite linear combinations) of real functions defined on the discrete cube with countable-dimension.

Remark:

Of course, if these classes of functions were considered (or even used for something) before I will be happy to know. Generalized parity functions appeared in Mike Sipser's work and he used them to show that Borel sets cannot compute them (inspiring the later Furst-Saxe-Sipser paper that (finite) parity is not in $AC^0$. (I thank Avi Wigderson for telling me about it.) I think it might be related to some recent posts (like this one) on Gowers's blog. For more on ultrafilters and mainly ultraproduct see this recent post in Tao's blog.

share|improve this question
    
Since I only answered the first part, would it make sense to make the part starting with "One step further" into a separate question? –  Bjørn Kjos-Hanssen Dec 27 '13 at 6:18
    
Dear Bjørn, The "General question" applies also to the first part and it will be very interesting to find nice applications for the W_Gs and W_Fs. (Of course, even if separated into two we can add this general question to both parts.) Maybe it will be easiest if you simply answer also the second part :). –  Gil Kalai Dec 27 '13 at 6:27
    
Thanks for offering the bounty, hopefully someone else will chime in. I'd like to learn more about Fourier analysis of Boolean functions -- maybe one day... –  Bjørn Kjos-Hanssen Apr 28 at 19:10
add comment

2 Answers 2

up vote 3 down vote accepted
+100

The $W_G$ are linearly independent. First note that given ultrafilters $F_1,\ldots,F_n$ and any $S\subseteq [n]$, we may find an $A_S\in \cap_{i\in S}F_i \setminus \cup_{j\not\in S}F_j$, namely $A_S := \cup_{i\in S}A_i$ where $A_i$ is as in my first answer. Assume $\sum c_G W_G=0$. Each $G$ is $F_S := \cap_{i\in S}F_i$ for some $S$ so we may rewrite as $\sum c_S W_{F_{S}}=0$. If we plug in $A_T$ this says $$\sum_{S\subseteq [n]} c_S (-1)^{\left|S\setminus T\right|}=0.$$ It is now a linear algebra problem to obtain that these $2^n$ equations for $T\subseteq [n]$ implies each of the $2^n$ unknowns $c_S=0$.

share|improve this answer
1  
Dear Bjorn, many thanks x2 –  Gil Kalai Dec 23 '13 at 19:35
add comment

The $W_F$ are linearly independent. Indeed suppose $\sum_{i=1}^n c_i W_{F_i}=0$. Let $A_i$ be a set in $F_i\setminus\cup_{j\ne i} F_{j}$. (This exists because for each pair $(i,j)$ there is a set $A_{i,j}$ in $F_i\setminus F_j$ by maximality of ultrafilters, and then we can let $A_i = \cap_j A_{i,j}$.) Then $$c_i-\sum_{j\ne i} c_j = \left(\sum_{i=1}^n c_i W_{F_i}\right)(A_i)=0$$ So each coefficient is the sum of all the others, which implies that either they are all 0, or $n=2$ and $c_1=c_2$; in the latter case note that $W_{F_i}(\mathbb N)=1$ for both $i$ and so $c_1=c_2=0$.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.