I am certainly going to make a mess of any serious algebraic terminology, so bear with me as I present my problem arising from a probability problem.

Consider the space of sequences of $n$ zero-one valued bits -- that is, $\mathbb{Z}_2^n$. For any element $\omega = (\omega_1,\omega_2,\ldots,\omega_n)$ we can of course define $|\omega|$ to be the number of $i$ such that $\omega_i = 1$. In some sense, $|\omega| = \sum_i \omega_i$.

Now define the function $f: \mathbb{Z}_2^n \to \mathbb{R^{\geq 0}}$ by $f(\omega) = 1_{|\omega|>0}\frac{1}{|\omega|^2} = 1_{|\omega|>0}\left(\sum_{i,j} \omega_i\omega_j\right)^{-1}$. If you accept that last equality, this is very nearly a second-degree rational function, except for at $\omega=(0,0,\ldots,0)$, where we define it to be zero.

Now, this function $f$ can be written as a polynomial -- this is clear just by polynomial interpolation, and there only being a finite number of points in $\mathbb{Z}_2^n$ to fit the polynomial at. I am interested in what the coefficients of this polynomial are -- these are also the Fourier coefficients of $f$ when we endow $\mathbb{Z}_2^n$ with the uniform probability measure, so it is a natural thing to want.

The remark about Fourier coefficients does give one expression for the coefficients of this polynomial as an expectation (inner product of the function with the characters), specifically if we take $X_i$ to be iid uniform on $\{-1,1\}$, we have $$\hat{f}(S) = \mathbb{E}\left[1_{\sum_i X_i+1 > 0}\frac{\prod_{i\in S} X_i}{\left(\sum_i \frac{X_i +1}{2}\right)^2}\right]$$

Unfortunately, it isn't clear to me how to compute that expectation.

So I was hoping that there was some other approach -- I know there has been a lot of work on computing things in algebraic geometry, and this question involves enough polynomials and finite fields that it might be relevant. But the sum total of my knowledge of algebraic geometry is half a master's class several years ago, so I have no idea if it actually is. Thus I am asking here, to see if the problem has already been solved somewhere.


1 Answer 1


You want Kravchuk polynomials, and the following identity $$ \sum_{\substack{(\omega_{1},\ldots,\omega_{n}) \in \{0,1\}^{n}\\ \omega_{1}+...+\omega_{n}=\ell}} \prod_{j \in S} (-1)^{\omega_{j}} = \sum_{j=0}^{\ell} (-1)^{j} \binom{|S|}{j}\binom{n-|S|}{\ell-j}. $$

For some probabilistic reasons I prefer to work with $\{-1,1\}^{n}$. Let $f : \{-1,1\}^{n} \to X$ , where $X$ is a normed space, be a function such that $f(x_{1}, \ldots, x_{n}) = g(x_{1}+...+x_{n})$. Let $x=(x_{1}, \ldots, x_{n}) \in \mathrm{unif}(\{-1,1\}^{n})$. Then for any $S \subset \{1, \ldots, n\}$ we have $$ \widehat{f}(S) :=\mathbb{E}\, f(x)\prod_{j \in S}x_{j} = \frac{1}{2^{n}} \sum_{\ell=0}^{n}g(2\ell-n)\sum_{\substack{(\omega_{1},\ldots,\omega_{n}) \in \{0,1\}^{n}\\ \omega_{1}+...+\omega_{n}=\ell}} \prod_{j \in S} (-1)^{\omega_{j}+1}=\\ \frac{(-1)^{|S|}}{2^{n}} \sum_{\ell=0}^{n}g(2\ell-n)K_{\ell}(|S|;n,2), $$ where $K_{\ell}(x;n,2) = \sum_{j=0}^{\ell} (-1)^{j} \binom{x}{j}\binom{n-x}{\ell-j}$ are called Kravchuk polynomials. See, for example, Dimension-free Maximal Inequalities for Spherical Means in the Hypercube by Ben Krause, and the references therein.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .