Recently I have come across the following question, while meditating about Matt Young's answer to this question of mine, explaining the heuristic (or at least, one possible heuristic) behind Montgomery's conjecture on the error term in Dirichlet theorem on primes in arithmetic progressions (see below for exactly how the question arose and is related to Montgomery's conjecture)
Let $n$ be an integer. For $h: \mathbb Z/n\mathbb Z \rightarrow S^1$ (the unit circle in $\mathbb C$), let $\hat{h}$ be its Fourier transform, $\hat{h}(a) = \frac{1}{n} \sum_{j=0}^{n-1} h(j) e^{2 i \pi a j/n}$. For a subset $A$ of $\mathbb Z/n\mathbb Z$, let $$b(A,h) = | \sum_{a \in A} \hat{h}(a) |,$$ and for $r \leq n$ an integer, let $$b(r,h) = \sup_{A \subset \mathbb Z / n \mathbb Z, |A|=r} b(A,h).$$ I am interested in the lower bound on $e(r,h)$ when $h$ runs among functions $\mathbb Z / n \mathbb Z \rightarrow S^1$. Let us call this lower bound $b(r,n)$, so $b(r,n) = \inf_h b(r,h)$.
How to estimate $b(r,n)$ when $r$ and $n$ tends to infinity ? For example, what about $b([n/2],n)$ ?
I am not sure how difficult this question is. When $r$ is fixed to $r=1$, it is closely related to this question. The answer, according to Ben Green's comment, is that $b(1,n) >> \sqrt{n}$ and that this is essentially the best possible lower bound. But even in this case I don't know the proof, and I'd like any hint or references.
Motivation: To explain it, I summarizes in my own term Matt Young's answer. If $f : (\mathbb Z / q \mathbb Z)^\ast \rightarrow \mathbb C$, and $\psi(f,x) = \sum_{n < x} f(n) \Lambda(n)$, we are interested in the error term $e(f,x) = \psi(f, x) - E(f) x$ where $E(f)$ is the average (or expectation) of $f$. When $f$ is a Dirichlet character $\chi$, the error term $e(\chi,x)$ should be, as GRH predicts, essentially in $O(x^{1/2})$ (neglecting $\log x$ and $\log q$ factors) but not better; however, when computing the error term $e(1_a,x)$ (where $a \in (\mathbb Z / q \mathbb Z)^\ast$ and $1_a$ is the indicator function of the singleton $\{a\}$ -- that is the error term in Dirichlet's theorem for the arithmetic progression $a+q \mathbb N$), using $$e(1_a,x) = \frac{1}{\phi(q)} \sum_\chi \overline{\chi(a)} e(\chi,x)$$ their should be "$\sqrt{q}$"-cancellations between the (roughly, $q$) terms so that their sum is of order of magnitude $\sqrt{q}$ times the order of the individual terms, hence $e(1_a,x) = O(x^{1/2}/q^{1/2})$ up to $\log$ terms, which is roughly Montgomery's conjecture.)
At first I found hard to believe that those $\sqrt{q}$-cancellations could happen for all $a$ in $\mathbb Z / q \mathbb Z$, but after a while I convinced myself that this could happen, and that this was even probably the generic situation, which happens when the $e(\chi,x)$ have for $x$ fixed and $\chi$ variable their expected order of magnitude but random complex arguments.
I am interested in understanding generalizations of Montgomery's conjecture to union of arithmetic progression, that is:
What is a plausible upper bound for $e(1_A,x)$ (where $1_A$ is the indicator function of a subset $A$ of $(\mathbb Z/q \mathbb Z)^\ast$) in terms of $|A|$ and $q$, and $x$? Does the heuristic above still work, or does it stop to work when $|A|$ becomes too big?
Precisely, the relation between this question and the one asked above is as follows: Let us assume that $(\mathbb Z/q\mathbb Z)^\ast$ is cyclic, to simplify, of some order $n$. Then we can identify it with $\mathbb Z / n \mathbb Z$, so $A$ becomes a subset of $\mathbb Z/n \mathbb Z$ and the multiplicative characters $\chi$ of $(\mathbb Z/q\mathbb Z)^\ast$ are identified with the additive character $\chi_j : a \mapsto e^{2 i \pi a j /n}$ of $\mathbb Z / n \mathbb Z$, for $j \in \mathbb Z/n\mathbb Z$. Since the values $e(\chi_j,x)$ (for $x$ fixed) are of the same order of magnitude, let us divides all of them by this magnitude (roughly $x^{1/2}$), so that we get a function $h$ of $j \in \mathbb Z / n \mathbb Z$, which is roughly unimodular of modulus $1$. This is the function $h$ of the first part of this post, and one sees that $$e(1_A,x) \simeq x^{1/2} b(A,h).$$ Since we want a bound on $e(1_A,x)$ uniform for every $A$ of a given size $r$, we are led to consider $b(r,h) = sup_{A, |A|=r} b(A,h)$ as in the first part. Now the heuristic would be that $h$ is so random that $b(r,h)$ would be close to its minimum possible value $b(r,n)$ (this is at least Matt Young's heuristic in the case $r=1$). Hence an intrepid generalization of Montgomery's conjecture would be
Bold Conjecture: $$ e(1_A,x) = O(x^{1/2} b(|A|,n) / q),$$ up to log terms. But to test this conjecture numerically or otherwise, I would need an estimate of $b(r,n)$.
