[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, 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. 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
