Return to Question

Let fix $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$ for which such a statement is not true.

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}}$.

Let fix $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 $n$ large enough and 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.

Let fix $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$ for which such a statement is not true.

Let fix $c \in \mathbb{F}_2^n$ Define $\sigma: \mathbb{F}_2^n \to \mathbb{F}_2$ the quadratic polynomial defined for $v = (v_1,v_2,...,v_n)$ by:

$$ \sigma (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(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 := \big| \sum_{v \in \mathbb{F}_2^n \\ v \ \text{has exactly} \ k \ 1's} (-1)^{\sigma(v)} \big|$$

$\textbf{Question:}$ Is it possible that there exists $\epsilon > 0$, such that for $n$ large enough and every $k \neq n/2$ one has $a_k < 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.

Let fix $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 $n$ large enough and 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.