For any $c \in \mathbb{F}_2^n$ define $\sigma_c: \mathbb{F}_2^n \to \mathbb{F}_2$ the quadratic polynomial defined for $v = (v_1,v_2,...,v_n)$ by:

$$ \sigma_c (v) = \sum_{i=1}^n v_iv_{i+1} + c_iv_i $$

One can prove that $$\big| \sum_{v \in \mathbb{F}_2^n} (-1)^{\sigma_c(v)} \big| \leq 4 \times 2^{n/2}$$

And one expect such cancellations because there are $2^n$ summands and for a random choice of $2^n$ $\pm1$'s one expect a sum of order of $\sqrt{2^n}$. This can be proven by squaring this sum and making a change of variable that reduces the sum to similar sums over linear polynomials on $\mathbb{F_2}^n$. See Green and Tao's https://arxiv.org/pdf/0711.3191.pdf, Lemma 1.6.

For each fixed $k$, $1 \leq k \leq n$, let

$$ a_k(c) := \big| \sum_{v \in \mathbb{F}_2^n \\ v \ \text{has exactly} \ k \ 1's} (-1)^{\sigma_c(v)} \big|$$

$\textbf{Question:}$ Is it possible that there exists $\epsilon > 0$, such that for any $n$ large enough there exists $c$ such that for every $k \neq n/2$ one has $a_k(c) < 2^{n/2}e^{-\epsilon n}$?.

Observe that when $k$ is small, this estimate is not saying anything, but when $k$ is close to $n/2$, this is unlikely as there are ${n \choose k} \approx \text{poly}(n)^{-1}2^n$ summands and these would say that in these type of sums one has much more cancellations than expected.

Anything information that is vaguely related to this question, would be very much appreciated, I have a more general set of similar sums and similar questions and this might be the easiest one I have.

EDIT: The answer below by Will Sawin shows that for any $n$, there exists $c$ such that $|a_k(c)|\geq \sqrt{ {n \choose k}}$.



The key to the solution is to not fix $c \in \mathbb F_2^n$, as you command. Instead, view $a_k(c)$ as a function of the variable $c$. It is clearly the Fourier transform over $\mathbb F_2^n$ of the function $(-1)^{ \sum_{i=1}^n v_i v_{i+1}}$, with its support restricted to the $v$ with $k$ ones, and zero elsewhere. Hence by Plancherel, the average of $|a_k(c)|^2$ is the $L^2$ norm of the original function, which is ${n \choose k}$. So for some $c$, $|a_k(c)| \geq \sqrt{{ n \choose k}}$.

  • $\begingroup$ Dear Will, thanks for your answer. This only shows that there exists $c$ for which the statement doesn't hold, and not that is not true for any $c$ as I think it might be true. Do you see a way of proving the same for any $c$? $\endgroup$ – shurtados May 13 '19 at 6:18
  • $\begingroup$ I'll modify the question to make that more clear. $\endgroup$ – shurtados May 13 '19 at 6:19
  • 2
    $\begingroup$ @shurtados It seems that the squaring and change of variables method can be used to give a lower bound on the original sum $| \sum_k a_k(c) |$, at least when (in the odd case) the sum of $c_i$ vanishes mod two or (in the even case) the sums of $c_i$ over both odd and even $i$ vanish. In this case, one of the $a_k$ must be large. If one of the $a_k$ is large for $c$, the same is true after adding the all-ones vector. This handles the entire odd case and half the even case. $\endgroup$ – Will Sawin May 13 '19 at 13:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.