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](http://gowers.wordpress.com/2013/11/03/dbd1-initial-post/)) on Gowers's blog. For more on ultrafilters and mainly ultraproduct see [this recent post](http://terrytao.wordpress.com/2013/12/07/ultraproducts-as-a-bridge-between-discrete-and-continuous-analysis/) in Tao's blog.



Ultrafilter-based Fourier-Walsh-like Functions
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$.


