[Edit: added details on the Reed-Muller codes]


Are there explicit (non random) constructions of probability measures on $D\_N = \{0,1\}^N$ with support of size $O(N)$ and with all nontrivial Fourier coefficients less than $\frac 1 2$ is absolute value ?


I would expect that such questions are very well understood, but being from a different background I probably lack the common knowledge. Pointers to the relevent litterature are very much welcome.


Below are some explanations on the terminology and on the $O(N)$. I am happy with any answer with $\frac 1 2$ replaced by $c<1$ (but independent from $N$).




---


When I write that *$\mu$ has all nontrivial Fourier coefficients less than $\frac 1 2$ in absolute value*, I mean that $|\hat \mu(A)| \leq \frac 1 2$ for every nonempty subset $A$ of $\{1,\dots,N\}$, where $\hat \mu(A)$ is the Fourier (or Fourier-Walsh) coefficient:
$$ \hat \mu(A) = \int (-1)^{\sum\_{i \in A} \varepsilon\_i} d\mu(\varepsilon).$$
The trivial Fourier coefficient, corresponding to $A=\emptyset$, is always $1$.
The uniform probability measure on $D\_N$ has all non-trivial Fourier coefficients equal to $0$, but has full support of size $2^N$. So I am looking for a probability measure that looks like the uniform probability on the Fourier side, but is very far on the other side, having very small support.




---


Why the $O(N)$? Because it is the optimal rate for the mere existence of $\mu$.


Indeed, seeing $D\_N$ as a vector space of dimension $N$ over the field with two elements, the question can be translated in linear algebra terms. In particular, we see that for all nontrivial Fourier coefficients of $\mu$ to be $\neq 1$, we need that the support of $\mu$ contains at least a basis of $D\_N$ and therefore has to have cardinality at least $N$.


Conversely, taking for $\mu$ the uniform measure on a subset of cardinality $K N$ chosen uniformly at random, a basic application of union bound and large deviation (Hoeffding's inequality) arguments gives that $\mu$ works with high probability, provided that $K$ is large enough. What I am looking for is explicit non-random constructions.




---


Using [Reed-Muller codes](https://en.wikipedia.org/wiki/Reed%E2%80%93Muller_code), a back-of-the enveloppe-computation seems to provide an explicit $\mu$ with support $N^{K \log \log N}$.


[Added after request in comments]
Here is the construction. I do not know how standard it is ; I learnt it from [the MIP\*=RE paper](https://arxiv.org/abs/2001.04383).
There is an integer parameter $a$, and we using the code coming from multilinear functions over the field $\mathbf{F}\_q$ with $q=2^{a}$ elements in $m = 2^{a-1}$ variables.


Denote $\mathcal{P}(m)$ the set of all subsets of $\{1,\dots,m\}$, and define a map $\alpha:\mathbf{F}\_q^{m+1} \to \mathbf{F}\_q^{\mathcal{P}(m)}$ by setting
$$\alpha(u\_1,\dots,u\_m,a) = (a \prod\_{i \in A} u\_i \prod\_{i \notin A} (1-u\_i))\_{A \in \mathcal{P}(m)}.$$
We can identify $\mathbf{F}\_q^{\mathcal{P}(m)}$ as an additive group with $D\_N$ for $N=a 2^m = a 2^{2^{a-1}}$, and I claim that $\mu$, the image by $\alpha$ of the uniform measure on $\mathbf{F}\_q^{m+1}$ does the job.


$\mu$ clearly has support of size $q^{m+1} = 2^{a +a2^{a-1}} = 2^{O(\log N \log\log N)}$, so we are fine as far as the support is concerned.


Let me prove that $|\hat\mu(\chi)|\leq \frac 1 2$ for every nontrivial character $\chi$. Let us fix a nonzero character $\eta$ of $\mathbf{F\_q}$. Then by counting, every character of $\mathbf{F\_q}^{\mathcal P(m)}$ is of the form $\eta \circ T$ for a $\mathbf{F}\_q$-linear map $T:\mathbf{F}\_q^{\mathcal{P}(m)} \to \mathbf{F}\_q$. Moreover, for every $x \in \mathbf{F}\_q$, we have $\mathbf{E}\_{a \in \mathbf{F\_q}} \eta(ax)=1\_{x=0}$, so we can compute


\begin{align\*}\hat \mu(\chi) &= \mathbf{E}\_{u \in \mathbf{F}\_q^m} \mathbf{E}\_{a \in \mathbf{F}\_q} \eta(a T(\alpha(u,1)))\\
&= \mathbf{E}\_{u \in \mathbf{F}\_q^m} 1\_{T(\alpha(u,1))}=0\\
& = \mathbf{P}\_{u \in\mathbf{F}\_q^m}( T(\alpha(u,1))).
\end{align\*}


But if $T$ is a nonzero linear map, then $T(\alpha(u,1))$ is a nonzero polynomial in $m$ variables of individual degree $\leq 1$, so the last probability is $\leq\frac{m}{q} = \frac 1 2$. QED



Probability measure on the boolean cube with small support and small Fourier transform
Just to close the lid on my comment: the desired construction is known as an $\epsilon$-biased space, where here $\epsilon = 1/2$. The best known construction seems to be by Ta-Shma from 2017 (<https://eccc.weizmann.ac.il/report/2017/041/>), which yields a subset with support size $O(N/\epsilon^{2+o(1)})$. This is near-optimal, as it is known that $\Omega(N/\epsilon^2\log(1/\epsilon))$ is necessary. However, for the special case of $\epsilon = 1/2$ where the precise $\epsilon$-dependence is not relevant, it appears that earlier constructions based on well-known codes suffice to obtain $O(N)$.


